Return to memo.cpp CVS log

Up to [Pegasus] / pegasus_unsupported / utils / memo

PEP#: 240
TITLE: Add new tool (memo)

DESCRIPTION: Add new tool.  Note readme explains tool.

/*
**==============================================================================
**
** Copyright (c) 2003, 2004, 2005 Michael E. Brasher
** 
** Permission is hereby granted, free of charge, to any person obtaining a
** copy of this software and associated documentation files (the "Software"),
** to deal in the Software without restriction, including without limitation
** the rights to use, copy, modify, merge, publish, distribute, sublicense,
** and/or sell copies of the Software, and to permit persons to whom the
** Software is furnished to do so, subject to the following conditions:
** 
** The above copyright notice and this permission notice shall be included in
** all copies or substantial portions of the Software.
** 
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
** LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
** OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
** SOFTWARE.
**
**==============================================================================
*/

#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <unistd.h>
#include <new>
#include "memo.h"

#ifndef __USE_GNU
#define __USE_GNU
#endif
#include <pthread.h>

//#define USE_HOOKS
#ifdef USE_HOOKS
static void _custom_init_hook();
void (*__malloc_initialize_hook)() = _custom_init_hook;
#endif

//==============================================================================
//
// Log file:
//
//==============================================================================

static FILE* _log = stderr;

//==============================================================================
//
// Needed on PowerPC to force initialization of this module.
//
//==============================================================================

class Dummy
{
public:
    Dummy() { }
};

static Dummy dummy;

//==============================================================================
//
// Data types:
//
//==============================================================================

typedef unsigned int uint32;
typedef unsigned long long uint64;

//==============================================================================
//
// Every memory block begins with this definition and ends with a uint32 magic
// number.
//
//==============================================================================

typedef struct _Block
{
    uint32 size;
    uint32 magic;
    struct _Block* next;
    struct _Block* prev;
}
Block;

static size_t _bytes_allocated = 0;

//==============================================================================
//
// _hex_dump()
//
//==============================================================================

static void _hex_dump(
    FILE* out,
    const void* data_,
    size_t size)
{
    unsigned char* data = (unsigned char*)data_;
    const size_t NUM_COLUMNS = 16;
    unsigned char bytes[NUM_COLUMNS];
    size_t n = 0;

    for (size_t i = 0, column = 0; i < size; i++)
    {
	unsigned char c = data[i];
	bytes[n++] = c;

	if (column == 0)
	    fprintf(out, "%06d ", i);

	fprintf(out, "%02X ", c);

	if (column + 1 == NUM_COLUMNS || i + 1 == size)
	{
	    // Pad up to where ASCII output starts.

	    for (size_t j = column + 1; j < NUM_COLUMNS; j++)
		fprintf(out, "   ");

	    // Print the accumulated bytes.

	    for (size_t j = 0; j < n; j++)
	    {
		c = bytes[j];

		if (c >= ' ' && c <= '~')
		    fprintf(out, "%c", bytes[j]);
		else
		    fprintf(out, ".");
	    }

	    fprintf(out, "\n");
	    n = 0;
	}

	if (column + 1 == NUM_COLUMNS)
	    column = 0;
	else
	    column++;
    }
}

//==============================================================================
//
// Magic number validation functions:
//
//==============================================================================

static const uint32 ALLOC_MAGIC_LO = 0xA0A0A0A0;
static const uint32 ALLOC_MAGIC_HI = 0x0A0A0A0A;
static const uint32 LIMBO_MAGIC_LO = 0xB0B0B0B0;
static const uint32 LIMBO_MAGIC_HI = 0x0B0B0B0B;
static const uint32 FREE_MAGIC_LO = 0xF0F0F0F0;
static const uint32 FREE_MAGIC_HI = 0x0F0F0F0F;

static void _set_magic(Block* block, uint32 magic_lo, uint32 magic_hi)
{
    block->magic = magic_lo;
    memcpy((char*)(block + 1) + block->size, &magic_hi, sizeof(magic_hi));
}

static void _check_magic(
    Block* block, 
    uint32 magic_lo, 
    uint32 magic_hi, 
    const char* file, 
    size_t line)
{
    if (block->magic != magic_lo)
    {
	fprintf(_log, "MEMO: %s(%d): bad low magic\n", file, (int)line);
	assert(0);
    }

    if (memcmp(
	(char*)(block + 1) + block->size, &magic_hi, sizeof(magic_hi)) != 0)
    {
	fprintf(_log, "MEMO: %s(%d): bad hight magic\n", file, (int)line);
	assert(0);
    }
}

static void _check_0xDD(
    const unsigned char* data, size_t size, const char* file, size_t line)
{
    const unsigned char* p = data;
    size_t n = size;

    while (n--)
    {
	if (*p++ != 0xDD)
	{
	    fprintf(_log, 
		"MEMO: %s(%d): corrupted memory\n", file, (int)line);

	    printf("size: %d\n", (int)size);

	    if (size > 1024)
		size = 1024;

	    _hex_dump(_log, data, size);

	    assert(0);
	}
    }
}

static void _check_block(
    Block* block, 
    uint32 magic_lo, 
    uint32 magic_hi, 
    const char* file, 
    size_t line)
{
    _check_magic(block, magic_lo, magic_hi, file, line);

    // Check that block is filled with 0xDD bytes

    unsigned char* p = (unsigned char*)(block + 1);
    size_t n = block->size;

    _check_0xDD(p, n, file, line);
}

//==============================================================================
//
// Limbo_List implementation:
//
//==============================================================================

typedef struct _Limbo_List
{
    Block* head;
    Block* tail;
    size_t bytes;
}
Limbo_List;

static Limbo_List _limbo_list;

static const uint32 MAX_LIMBO_BYTES = (64 * 1024);

static void Limbo_List_evict_block(Limbo_List* self)
{
    if (!self->head)
	return;

    Block* block = self->tail;

    if (self->tail == self->head)
    {
	self->head = 0;
	self->tail = 0;
    }
    else
    {
	self->tail->prev->next = 0;
	self->tail = self->tail->prev;
    }

    _set_magic(block, FREE_MAGIC_LO, FREE_MAGIC_HI);
    _check_block(block, FREE_MAGIC_LO, FREE_MAGIC_HI, __FILE__, __LINE__);
    self->bytes -= block->size;

    free(block);
}

static void Limbo_List_put(Limbo_List* self, Block* block)
{
    // Insert new block into limbo list:

    block->prev = 0;
    _set_magic(block, LIMBO_MAGIC_LO, LIMBO_MAGIC_HI);
    _check_block(block, LIMBO_MAGIC_LO, LIMBO_MAGIC_HI, __FILE__, __LINE__);

    if (self->head == 0)
    {
	self->head = block;
	self->tail = block;
	block->next = 0;
    }
    else
    {
	block->next = self->head;
	self->head->prev = block;
	self->head = block;
    }

    self->bytes += block->size;

    while (self->bytes > MAX_LIMBO_BYTES)
	Limbo_List_evict_block(&_limbo_list);
}

static void Limbo_List_check(Limbo_List* self)
{
    Block* p;

    for (p = self->head; p; p = p->next)
	_check_block(p, LIMBO_MAGIC_LO, LIMBO_MAGIC_HI, __FILE__, __LINE__);
}

//==============================================================================
//
// Hash_Set implementation:
//
//==============================================================================

#define NUM_CHAINS (16*1024)

typedef struct _Hash_Set
{
    Block* chains[NUM_CHAINS];
}
Hash_Set;

static Hash_Set _hash_set;

int Hash_Set_find(Hash_Set* self, Block* block)
{
    Block* p;
    size_t h = (uint64)block % NUM_CHAINS;

    assert(h < NUM_CHAINS);

    for (p = self->chains[h]; p; p = p->next)
    {
	if (p == block)
	    return 1;
    }

    /* Not found */
    return 0;
}

int Hash_Set_insert(Hash_Set* self, Block* block)
{
    Block* p;
    size_t h = (uint64)block % NUM_CHAINS;

    assert(h < NUM_CHAINS);

    for (p = self->chains[h]; p; p = p->next)
    {
	if (p == block)
	    return 0;
    }

    block->next = self->chains[h];
    self->chains[h] = block;
    return 1;
}

int Hash_Set_remove(Hash_Set* self, Block* block)
{
    Block* p;
    Block* prev = 0;
    size_t h = (uint64)block % NUM_CHAINS;

    assert(h < NUM_CHAINS);

    for (p = self->chains[h]; p; p = p->next)
    {
	if (p == block)
	{
	    if (prev)
		prev->next = p->next;
	    else
		self->chains[h] = p->next;

	    return 1;
	}

	prev = p;
    }

    /* Not found */
    return 0;
}

static void Hash_Set_check_blocks(Hash_Set* self)
{
    size_t i;

    for (i = 0; i < NUM_CHAINS; i++)
    {
	Block* p;

	for (p = self->chains[i]; p; p = p->next)
	    _check_magic(p, ALLOC_MAGIC_LO, ALLOC_MAGIC_HI, __FILE__, __LINE__);
    }
}

//==============================================================================
//
// Pointer_Array implementation:
//
//==============================================================================

typedef struct _Pointer_Array
{
    void** data;
    size_t size;
    size_t capacity;
}
Pointer_Array;

static void Pointer_Array_append(Pointer_Array* self, void* ptr)
{
    if (self->size == self->capacity)
    {
	self->capacity += 128;
	self->data = (void**)realloc(self->data, self->capacity);
    }

    self->data[self->size++] = ptr;
}

static void Pointer_Array_clear(Pointer_Array* self)
{
    if (self->data)
    {
	free(self->data);
	self->data = 0;
    }

    self->size = 0;
    self->capacity = 0;
}

static int Pointer_Array_contains(Pointer_Array* self, void* ptr)
{
    size_t i;

    for (i = 0; i < self->size; i++)
    {
	if (self->data[i] == ptr)
	    return 1;
    }

    return 0;
}

//==============================================================================
//
// Locking functions:
//
//==============================================================================

static pthread_mutex_t _mutex = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;

static void _lock()
{
    pthread_mutex_lock(&_mutex);
}

static void _unlock()
{
    pthread_mutex_unlock(&_mutex);
}

//==============================================================================
//
// memo_malloc(), memo_realloc(), and memo_free()
//
//==============================================================================

void* memo_malloc(size_t size)
{
    Block* block = (Block*)malloc(sizeof(Block) + size + sizeof(uint32));

    if (!block)
    {
	fprintf(_log, 
	    "MEMO: %s(%d): out of memory\n", __FILE__, __LINE__);
	assert(0);
    }

    block->size = size;
    _set_magic(block, ALLOC_MAGIC_LO, ALLOC_MAGIC_HI);

    if (size)
	memset(block + 1, 0xAA, size);

    int flag = Hash_Set_insert(&_hash_set, block);

    if (!flag)
    {
	fprintf(_log, 
	    "MEMO: %s(%d): internal error\n", __FILE__, __LINE__);
	assert(0);
    }

    _bytes_allocated += size;

    assert(block->size == size);
    assert(block->magic == ALLOC_MAGIC_LO);

    return block + 1;
}

#if 0
void* memo_realloc(void* ptr, size_t size)
{
    if (size == 0)
	return 0;

    assert(size != 0);

    Block* block;

    if (ptr)
    {
	block = (Block*)ptr - 1;
	int flag = Hash_Set_remove(&_hash_set, block);
	assert(flag == 1);

	if (size < block->size)
	    memset((char*)ptr + size, 0xDD, block->size - size);

	block = (Block*)realloc(block, sizeof(Block) + size + sizeof(uint32));
	assert(block != 0);
	ptr = block + 1;

	if (size > block->size)
	    memset((char*)ptr + block->size, 0xFF, size - block->size);
    }
    else
    {
	block = (Block*)realloc(
	    0, sizeof(Block) + size + sizeof(uint32));
	assert(block != 0);
	ptr = block + 1;
	memset(ptr, 0xFF, size);
    }

    block->size = size;

    _set_magic(block, ALLOC_MAGIC_LO, ALLOC_MAGIC_HI);
    _check_magic(block, ALLOC_MAGIC_LO, ALLOC_MAGIC_HI, __FILE__, __LINE__);

    int flag = Hash_Set_insert(&_hash_set, block);
    assert(flag);

    _bytes_allocated += size;

    return ptr;
}
#endif

void memo_free(void* ptr)
{
    if (ptr)
    {
	Block* block = (Block*)ptr - 1;
	int flag = Hash_Set_remove(&_hash_set, block);

	if (!flag)
	{
	    fprintf(_log, 
		"MEMO: %s(%d): internal error\n", __FILE__, __LINE__);
	    assert(0);
	}

	_check_magic(block, ALLOC_MAGIC_LO, ALLOC_MAGIC_HI, __FILE__, __LINE__);
	memset(ptr, 0xDD, block->size);
	_bytes_allocated -= block->size;

	Limbo_List_put(&_limbo_list, block);
    }
}

//==============================================================================
//
// Externally visible API:
//
//==============================================================================

static Pointer_Array _visited_array;

static size_t _memo_deep_size_aux(const void* ptr, size_t size)
{
    //// Add this pointer to the visited array:

    Pointer_Array_append(&_visited_array, (void*)ptr);

    //// Recursively calculate the full size of this object.

    size_t total = size;
    void** start = (void**)ptr;
    void** end = start + (size / sizeof(void*));

    while (start != end)
    {
	void* ptr = *start++;
	Block* block = (Block*)ptr - 1;

	if (Hash_Set_find(&_hash_set, block))
	{
	    assert(block->magic == ALLOC_MAGIC_LO);

	    if (!Pointer_Array_contains(&_visited_array, ptr))
		total += memo_deep_size(block + 1, block->size);
	}
    }

    return total;
}

size_t memo_deep_size(const void* ptr, size_t size)
{
    _lock();
    size_t total = _memo_deep_size_aux(ptr, size);
    Pointer_Array_clear(&_visited_array);
    _unlock();

    return total;
}

size_t memo_total_bytes()
{
    _lock();
    size_t tmp = _bytes_allocated;
    _unlock();
    return tmp;
}

void memo_check()
{
    Limbo_List_check(&_limbo_list);
    Hash_Set_check_blocks(&_hash_set);
}

//==============================================================================
//
// GCC hooks
//
//==============================================================================

#ifdef USE_HOOKS

static void* (*_glibc_malloc_hook)(size_t, const void*);
static void* (*_glibc_realloc_hook)(void* ptr, size_t, const void*);
static void (*_glibc_free_hook)(void*, const void*);
static void* (*_glibc_memalign_hook)(size_t, size_t, const void*);

static void _custom_init_hook();
static void* _custom_malloc_hook(size_t, const void*);
static void* _custom_realloc_hook(void*, size_t, const void*);
static void _custom_free_hook(void*, const void*);
static void* _custom_memalign_hook(size_t, size_t, const void*);

static void* _custom_malloc_hook(size_t size, const void* caller)
{
    _lock();

    void* result;

    __malloc_hook = _glibc_malloc_hook;

#ifdef USE_SYSTEM
    result = malloc(size);
#else
    result = memo_malloc(size);
#endif

    _glibc_malloc_hook = __malloc_hook;
    __malloc_hook = _custom_malloc_hook;

    _unlock();

    return result;
}

static void* _custom_realloc_hook(void* ptr, size_t size, const void* caller)
{
    _lock();

    void* result;

    __realloc_hook = _glibc_realloc_hook;

#ifdef USE_SYSTEM
    result = realloc(ptr, size);
#else
    if (!ptr || ((Block*)ptr - 1)->magic == ALLOC_MAGIC_LO)
	result = memo_realloc(ptr, size);
    else
	result = realloc(ptr, size);
#endif

    _glibc_realloc_hook = __realloc_hook;
    __realloc_hook = _custom_realloc_hook;

    _unlock();

    return result;
}

static void _custom_free_hook(void *ptr, const void* caller)
{
    _lock();

    __free_hook = _glibc_free_hook;

    if (ptr)
    {
#ifdef USE_SYSTEM
	free(ptr);
#else
	if (((Block*)ptr - 1)->magic == ALLOC_MAGIC_LO)
	    memo_free(ptr);
	else
	    free(ptr);
#endif
    }

    _glibc_free_hook = __free_hook;
    __free_hook = _custom_free_hook;

    _unlock();
}

static void* _custom_memalign_hook(
    size_t align, size_t size, const void* caller)
{
    assert(0);
    return NULL;
}

static void _custom_init_hook()
{
    _glibc_malloc_hook = __malloc_hook;
    _glibc_realloc_hook = __realloc_hook;
    _glibc_free_hook = __free_hook;
    _glibc_memalign_hook = __memalign_hook;

    __malloc_hook = _custom_malloc_hook;
    __realloc_hook = _custom_realloc_hook;
    __free_hook = _custom_free_hook;
    __memalign_hook = _custom_memalign_hook;
}

#endif /* USE_HOOKS */

//==============================================================================
//
// C++ new and delete operators:
//
//==============================================================================

#ifndef USE_HOOKS

void* operator new(size_t size) throw (std::bad_alloc)
{
    _lock();
    void* ptr = memo_malloc(size);
    _unlock();
    return ptr;
}

void* operator new[](size_t size) throw(std::bad_alloc)
{
    _lock();
    void* ptr = memo_malloc(size);
    _unlock();
    return ptr;
}

void operator delete(void* ptr)
{
    _lock();
    memo_free(ptr);
    _unlock();
}

void operator delete(void* ptr, size_t size)
{
    _lock();
    memo_free(ptr);
    _unlock();
}

void operator delete[](void* ptr)
{
    _lock();
    memo_free(ptr);
    _unlock();
}

void operator delete[](void* ptr, size_t)
{
    _lock();
    memo_free(ptr);
    _unlock();
}

void* operator new(std::size_t size, const std::nothrow_t&) throw()
{
    _lock();
    void* ptr = memo_malloc(size);
    _unlock();
    return ptr;
}

void* operator new[](std::size_t size, const std::nothrow_t&) throw()
{
    _lock();
    void* ptr = memo_malloc(size);
    _unlock();
    return ptr;
}

void operator delete(void* ptr, const std::nothrow_t&) throw()
{
    _lock();
    memo_free(ptr);
    _unlock();
}

void operator delete[](void* ptr, const std::nothrow_t&) throw()
{
    _lock();
    memo_free(ptr);
    _unlock();
}

#endif /* USE_CXX_OPERATORS */

//==============================================================================
//
// This is the server execution thread.
//
//==============================================================================

static void* _server_thread(void* arg)
{
    extern void run_server();
    run_server();
    return 0;
}

//==============================================================================
//
// Process constructors and destructors.
//
//==============================================================================

static void __attribute__((constructor)) _process_constructor()
{
    // _log = _open_log_file();

    pthread_t thread;
    pthread_create(&thread, NULL, _server_thread, NULL);
}

static void __attribute__((destructor)) _process_destructor()
{
    // fprintf(_log, "MEMO: exiting\n");

    memo_check();

    // printf("MEMO: summary: total-allocated: %u\n", (int)_bytes_allocated);

    unlink("/tmp/memo.port");
}