klish/lub/heap/node.c

/*
 * node.c
 */
#include <stdio.h>
#include <string.h>
#include <assert.h>

#include "private.h"
#include "context.h"
#include "node.h"

int lub_heap_leak_verbose = 0;
/*--------------------------------------------------------- */
int lub_heap_node_compare(const void *clientnode, const void *clientkey)
{
	const lub_heap_node_t *node = clientnode;
	const lub_heap_node_key_t *key = clientkey;

	return ((long)node - (long)key->node);
}

/*--------------------------------------------------------- */
/* we simply use the node address as the index */
void lub_heap_node_getkey(const void *clientnode, lub_bintree_key_t * key)
{
	lub_heap_node_key_t clientkey;
	clientkey.node = clientnode;
	memcpy(key, &clientkey, sizeof(lub_heap_node_key_t));
}

/*--------------------------------------------------------- */
static void lub_heap_node_meta_init(void)
{
	static bool_t initialised = BOOL_FALSE;

	if (BOOL_FALSE == initialised) {
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		initialised = BOOL_TRUE;
		/* initialise the node tree */
		lub_bintree_init(&leak->m_node_tree,
				 offsetof(lub_heap_node_t, bt_node),
				 lub_heap_node_compare, lub_heap_node_getkey);
		/* initialise the clear node tree */
		lub_bintree_init(&leak->m_clear_node_tree,
				 offsetof(lub_heap_node_t, bt_node),
				 lub_heap_node_compare, lub_heap_node_getkey);
		lub_heap_leak_release(leak);
	}
}

/*--------------------------------------------------------- */
void lub_heap_node_init(lub_heap_node_t * this, lub_heap_context_t * context)
{
	lub_heap_node_meta_init();

	/* initialise the control blocks */
	lub_bintree_node_init(&this->bt_node);

	lub_heap_node__set_context(this, context);
	lub_heap_node__set_leaked(this, BOOL_FALSE);
	lub_heap_node__set_partial(this, BOOL_FALSE);
	lub_heap_node__set_next(this, NULL);
	lub_heap_node__set_scanned(this, BOOL_FALSE);
	this->prev = NULL;
	{
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		/* add this to the node tree */
		lub_bintree_insert(context ? &leak->m_node_tree : &leak->
				   m_clear_node_tree, this);
		lub_heap_leak_release(leak);
	}
	if (context) {
		/* add ourselves to this context */
		lub_heap_context_insert_node(context, this);

		/* maintain the leak statistics */
		++context->allocs;
		context->alloc_bytes += lub_heap_node__get_size(this);
		context->alloc_overhead += lub_heap_node__get_overhead(this);
	}
}

/*--------------------------------------------------------- */
void lub_heap_node_fini(lub_heap_node_t * this)
{
	/* remove this node from this context */
	lub_heap_node_clear(this, 0);
	{
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		/* remove this from the clear_node tree */
		lub_bintree_remove(&leak->m_clear_node_tree, this);
		lub_heap_leak_release(leak);
	}
}

/*--------------------------------------------------------- */
size_t lub_heap_node__get_instanceSize(void)
{
	return sizeof(lub_heap_node_t);
}

/*--------------------------------------------------------- */
size_t lub_heap_node__get_size(const lub_heap_node_t * this)
{
	size_t size =
	    lub_heap__get_block_size(lub_heap_node__get_context(this)->heap,
				     this);
	size -= sizeof(lub_heap_node_t);
	return size;
}

/*--------------------------------------------------------- */
size_t lub_heap_node__get_overhead(const lub_heap_node_t * this)
{
	size_t overhead;

	overhead =
	    lub_heap__get_block_overhead(lub_heap_node__get_context(this)->heap,
					 lub_heap_node__get_ptr(this));

	overhead += sizeof(lub_heap_node_t);
	return overhead;
}

/*--------------------------------------------------------- */
char *lub_heap_node__get_ptr(const lub_heap_node_t * this)
{
	return (char *)&this[1];
}

/*--------------------------------------------------------- */
bool_t lub_heap_validate_pointer(lub_heap_t * this, char *ptr)
{
	bool_t result = BOOL_FALSE;
	do {
		lub_heap_segment_t *seg;
		if ((0 < lub_heap_frame_count)) {
			/*
			 * When leak detection is enabled we can perform detailed 
			 * validation of pointers.
			 */
			lub_heap_node_t *node =
			    lub_heap_node_from_start_of_block_ptr(ptr);
			if (NULL != node) {
				lub_heap_context_t *context =
				    lub_heap_node__get_context(node);
				/* we've found a context so can give a definative answer */
				if (this == context->heap) {
					result = BOOL_TRUE;
				}
				break;
			}
		}
		/* iterate around each of the segments belonging to this heap */
		for (seg = &this->first_segment; seg; seg = seg->next) {
			char *start = (char *)&seg[1];
			if (ptr >= start) {
				char *end = start + (seg->words << 2);
				if (ptr < end) {
					/* we've found a parent segment for this pointer */
					result = BOOL_TRUE;
					break;
				}
			}
		}
	} while (0);
	ptr = 0;		/* don't leave a pointer on the stack */
	return result;
}

/*--------------------------------------------------------- */
static lub_heap_node_t *_lub_heap_node_from_ptr(lub_bintree_t * tree,
						const char *ptr,
						bool_t start_of_block)
{
	lub_heap_node_t *result = 0;
	if (tree->root) {
		lub_heap_node_key_t key;

		/* search for the node which comes immediately before this pointer */
		key.node = (lub_heap_node_t *) ptr;
		result = lub_bintree_findprevious(tree, &key);

		if (NULL != result) {
			char *tmp = lub_heap_node__get_ptr(result);
			/* ensure that the pointer is within the scope of this node */
			if (start_of_block) {
				if (ptr != tmp) {
					/* 
					 * this should be an exact match and isn't
					 */
					result = NULL;
				}
			} else if (ptr < tmp) {
				/* 
				 * this is referencing part of the node header
				 */
				result = NULL;
			} else {
				/* compare with the end of the allocated memory */
				tmp += lub_heap_node__get_size(result);
				/* ensure that the pointer is within the scope of this node */
				if (ptr >= tmp) {
					/* out of range of this node */
					result = NULL;
				}
			}
			tmp = 0;	/* don't leave a pointer on the stack */
		}
	}
	ptr = 0;		/* don't leave a pointer on the stack */
	return result;
}

/*--------------------------------------------------------- */
lub_heap_node_t *lub_heap_node_from_start_of_block_ptr(char *ptr)
{
	lub_heap_node_t *result = 0;
	if (lub_heap_leak_query_node_tree()) {
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		result =
		    _lub_heap_node_from_ptr(&leak->m_node_tree, ptr, BOOL_TRUE);
		lub_heap_leak_release(leak);
	}
	if ((0 == result) && lub_heap_leak_query_clear_node_tree()) {
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		result =
		    _lub_heap_node_from_ptr(&leak->m_clear_node_tree, ptr,
					    BOOL_TRUE);
		lub_heap_leak_release(leak);
	}
	ptr = 0;		/* don't leave a pointer on the stack */
	return result;
}

/*--------------------------------------------------------- */
void
lub_heap_node__set_context(lub_heap_node_t * this, lub_heap_context_t * value)
{
	unsigned long mask =
	    ((unsigned long)value & ~(LEAKED_MASK | PARTIAL_MASK));
	this->_context = (lub_heap_context_t *) mask;
}

/*--------------------------------------------------------- */
lub_heap_context_t *lub_heap_node__get_context(const lub_heap_node_t * this)
{
	unsigned long mask =
	    (unsigned long)this->_context & ~(LEAKED_MASK | PARTIAL_MASK);
	return (lub_heap_context_t *) mask;
}

/*--------------------------------------------------------- */
void lub_heap_node__set_next(lub_heap_node_t * this, lub_heap_node_t * value)
{
	unsigned long mask = ((unsigned long)value & ~(SCANNED_MASK));
	this->_next = (lub_heap_node_t *) mask;
}

/*--------------------------------------------------------- */
lub_heap_node_t *lub_heap_node__get_next(const lub_heap_node_t * this)
{
	unsigned long mask = (unsigned long)this->_next & ~(SCANNED_MASK);
	return (lub_heap_node_t *) mask;
}

/*--------------------------------------------------------- */
bool_t lub_heap_node__get_leaked(const lub_heap_node_t * this)
{
	return ((unsigned long)this->
		_context & LEAKED_MASK) ? BOOL_TRUE : BOOL_FALSE;
}

/*--------------------------------------------------------- */
bool_t lub_heap_node__get_partial(const lub_heap_node_t * this)
{
	return ((unsigned long)this->
		_context & PARTIAL_MASK) ? BOOL_TRUE : BOOL_FALSE;
}

/*--------------------------------------------------------- */
bool_t lub_heap_node__get_scanned(const lub_heap_node_t * this)
{
	return ((unsigned long)this->
		_next & SCANNED_MASK) ? BOOL_TRUE : BOOL_FALSE;
}

/*--------------------------------------------------------- */
void lub_heap_node__set_leaked(lub_heap_node_t * this, bool_t value)
{
	unsigned long mask = (unsigned long)this->_context;
	if (BOOL_TRUE == value) {
		mask |= LEAKED_MASK;
	} else {
		mask &= ~LEAKED_MASK;
	}
	this->_context = (lub_heap_context_t *) mask;
}

/*--------------------------------------------------------- */
void lub_heap_node__set_partial(lub_heap_node_t * this, bool_t value)
{
	unsigned long mask = (unsigned long)this->_context;
	if (BOOL_TRUE == value) {
		mask |= PARTIAL_MASK;
	} else {
		mask &= ~PARTIAL_MASK;
	}
	this->_context = (lub_heap_context_t *) mask;
}

/*--------------------------------------------------------- */
void lub_heap_node__set_scanned(lub_heap_node_t * this, bool_t value)
{
	unsigned long mask = (unsigned long)this->_next;
	if (BOOL_TRUE == value) {
		mask |= SCANNED_MASK;
	} else {
		mask &= ~SCANNED_MASK;
	}
	this->_next = (lub_heap_node_t *) mask;
}

/*--------------------------------------------------------- */
void lub_heap_foreach_node(void (*fn) (lub_heap_node_t *, void *), void *arg)
{
	lub_heap_leak_t *leak = lub_heap_leak_instance();
	lub_heap_node_t *node;
	lub_heap_node_key_t key;

	for (node = lub_bintree_findfirst(&leak->m_node_tree);
	     node; node = lub_bintree_findnext(&leak->m_node_tree, &key)) {
		lub_heap_leak_release(leak);

		lub_heap_node_getkey(node, (lub_bintree_key_t *) & key);
		/* invoke the specified method on this node */
		fn(node, arg);

		leak = lub_heap_leak_instance();
	}
	lub_heap_leak_release(leak);
}

/*--------------------------------------------------------- */
void lub_heap_node_clear(lub_heap_node_t * this, void *arg)
{
	/* clearing a node removes it from it's context */
	lub_heap_context_t *context = lub_heap_node__get_context(this);
	if (NULL != context) {
		lub_heap_leak_t *leak = lub_heap_leak_instance();
		/* remove from the node tree and place into the clear tree */
		lub_bintree_remove(&leak->m_node_tree, this);
		lub_bintree_insert(&leak->m_clear_node_tree, this);
		lub_heap_leak_release(leak);

		/* maintain the leak statistics */
		--context->allocs;
		context->alloc_bytes -= lub_heap_node__get_size(this);
		context->alloc_overhead -= lub_heap_node__get_overhead(this);

		lub_heap_node__set_context(this, NULL);
		lub_heap_node__set_leaked(this, BOOL_FALSE);
		lub_heap_node__set_partial(this, BOOL_FALSE);

		lub_heap_context_remove_node(context, this);
	}
}

/*--------------------------------------------------------- */
#define RELEASE_COUNT 2048
void lub_heap_scan_memory(const void *mem, size_t size)
{
	size_t bytes_left = size;
	typedef const void *void_ptr;
	void_ptr *ptr, last_ptr = 0;
	lub_heap_leak_t *leak = lub_heap_leak_instance();
	unsigned release_count = RELEASE_COUNT;
	if (lub_heap_leak_verbose) {
		printf("lub_heap_scan_memory(%p,%" SIZE_FMT ")\n", mem, size);
	}
	++leak->m_stats.scanned;

	/* scan all the words in this allocated block of memory */
	for (ptr = (void_ptr *) mem; bytes_left;) {
		if (0 == --release_count) {
			/* make space for other memory tasks to get in... */
			lub_heap_leak_release(leak);
			leak = lub_heap_leak_instance();
			release_count = RELEASE_COUNT;
		}
		if (*ptr != last_ptr) {
			lub_heap_node_t *node;
			lub_heap_node_key_t key;

			/* search for a node */
			key.node = (lub_heap_node_t *) ptr;
			node = lub_bintree_find(&leak->m_node_tree, &key);
			if (NULL != node) {
				/*
				 * If we stumble across a node don't scan it's contents as this could cause
				 * false negatives. This situation could occur if an allocated block of memory
				 * was used as a heap in it's own right.
				 */
				char *tmp = lub_heap_node__get_ptr(node);
				size_t node_size =
				    lub_heap_node__get_size(node);

				/* skip forward past the node contents */
				ptr = (void_ptr *) (tmp + node_size);
				bytes_left -=
				    (node_size + sizeof(lub_heap_node_t));
				tmp = 0;	/* don't leave pointers on our stack */
				last_ptr = 0;
				continue;
			}
			/* 
			 * see whether this is a reference to a node 
			 * NB. we only resolve a node if the pointer lies
			 * within the memory allocated to the client; any direct
			 * references to nodes will not resolve to a node
			 * object.
			 */
			node =
			    _lub_heap_node_from_ptr(&leak->m_node_tree, *ptr,
						    BOOL_FALSE);
			if ((NULL != node)) {
				/* this looks like a valid node */
				lub_heap_context_t *context =
				    lub_heap_node__get_context(node);
				size_t node_size =
				    lub_heap_node__get_size(node);
				size_t node_overhead =
				    lub_heap_node__get_overhead(node);
				char *tmp = lub_heap_node__get_ptr(node);
				if (tmp == *ptr) {
					/* reference to start of block */
					if (BOOL_TRUE ==
					    lub_heap_node__get_partial(node)) {
						lub_heap_node__set_partial(node,
									   BOOL_FALSE);

						if (NULL != context) {
							--context->partials;
							context->
							    partial_bytes -=
							    node_size;
							context->
							    partial_overhead -=
							    node_overhead;
						}
					}
				}
				tmp = 0;	/* don't leave pointers on our stack */
				/* this is definately not a leak */
				if (BOOL_TRUE ==
				    lub_heap_node__get_leaked(node)) {
					lub_heap_node__set_leaked(node,
								  BOOL_FALSE);

					if (NULL != context) {
						--context->leaks;
						context->leaked_bytes -=
						    node_size;
						context->leaked_overhead -=
						    node_overhead;

						--leak->m_stats.leaks;
						leak->m_stats.leaked_bytes -=
						    node_size;
						leak->m_stats.leaked_overhead -=
						    node_overhead;
					}
				}
			}
		}
		last_ptr = *ptr++;
		bytes_left -= sizeof(void *);
	}
	lub_heap_leak_release(leak);
	last_ptr = ptr = 0;	/* don't leave pointers on the stack */
}

/*--------------------------------------------------------- */