ext/paho.mqtt.c/src/Heap.c - a71ch-crypto-support - Git at Google

 /*******************************************************************************
  * Copyright (c) 2009, 2020 IBM Corp.
  *
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v2.0
  * and Eclipse Distribution License v1.0 which accompany this distribution.
  *
  * The Eclipse Public License is available at
  *    https://www.eclipse.org/legal/epl-2.0/
  * and the Eclipse Distribution License is available at
  *   http://www.eclipse.org/org/documents/edl-v10.php.
  *
  * Contributors:
  *    Ian Craggs - initial API and implementation and/or initial documentation
  *    Ian Craggs - use tree data structure instead of list
  *    Ian Craggs - change roundup to Heap_roundup to avoid macro name clash on MacOSX
  *******************************************************************************/

 /**
  * @file
  * \brief functions to manage the heap with the goal of eliminating memory leaks
  *
  * For any module to use these functions transparently, simply include the Heap.h
  * header file.  Malloc and free will be redefined, but will behave in exactly the same
  * way as normal, so no recoding is necessary.
  *
  * */

 #include "Tree.h"
 #include "Log.h"
 #include "StackTrace.h"
 #include "Thread.h"

 #if defined(HEAP_UNIT_TESTS)
 char* Broker_recordFFDC(char* symptoms);
 #endif /* HEAP_UNIT_TESTS */

 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 #include <stddef.h>

 #include "Heap.h"

 #if !defined(NO_HEAP_TRACKING)

 #undef malloc
 #undef realloc
 #undef free

 #if defined(_WIN32) || defined(_WIN64)
 mutex_type heap_mutex;
 #else
 static pthread_mutex_t heap_mutex_store = PTHREAD_MUTEX_INITIALIZER;
 static mutex_type heap_mutex = &heap_mutex_store;
 #endif

 static heap_info state = {0, 0}; /**< global heap state information */

 typedef double eyecatcherType;
 static eyecatcherType eyecatcher = (eyecatcherType)0x8888888888888888;

 /*#define HEAP_STACK 1 */

 /**
  * Each item on the heap is recorded with this structure.
  */
 typedef struct
 {
 	char* file;		/**< the name of the source file where the storage was allocated */
 	int line;		/**< the line no in the source file where it was allocated */
 	void* ptr;		/**< pointer to the allocated storage */
 	size_t size;    /**< size of the allocated storage */
 #if defined(HEAP_STACK)
 	char* stack;
 #endif
 } storageElement;

 static Tree heap;	/**< Tree that holds the allocation records */
 static const char *errmsg = "Memory allocation error";


 static size_t Heap_roundup(size_t size);
 static int ptrCompare(void* a, void* b, int value);
 /*static void Heap_check(char* string, void* ptr);*/
 static void checkEyecatchers(char* file, int line, void* p, size_t size);
 static int Internal_heap_unlink(char* file, int line, void* p);
 static void HeapScan(enum LOG_LEVELS log_level);


 /**
  * Round allocation size up to a multiple of the size of an int.  Apart from possibly reducing fragmentation,
  * on the old v3 gcc compilers I was hitting some weird behaviour, which might have been errors in
  * sizeof() used on structures and related to packing.  In any case, this fixes that too.
  * @param size the size actually needed
  * @return the rounded up size
  */
 static size_t Heap_roundup(size_t size)
 {
 	static int multsize = 4*sizeof(int);

 	if (size % multsize != 0)
 		size += multsize - (size % multsize);
 	return size;
 }


 /**
  * List callback function for comparing storage elements
  * @param a pointer to the current content in the tree (storageElement*)
  * @param b pointer to the memory to free
  * @return boolean indicating whether a and b are equal
  */
 static int ptrCompare(void* a, void* b, int value)
 {
 	a = ((storageElement*)a)->ptr;
 	if (value)
 		b = ((storageElement*)b)->ptr;

 	return (a > b) ? -1 : (a == b) ? 0 : 1;
 }

 /*
 static void Heap_check(char* string, void* ptr)
 {
 	Node* curnode = NULL;
 	storageElement* prev, *s = NULL;

 	printf("Heap_check start %p\n", ptr);
 	while ((curnode = TreeNextElement(&heap, curnode)) != NULL)
 	{
 		prev = s;
 		s = (storageElement*)(curnode->content);

 		if (prev)
 		{
 		if (ptrCompare(s, prev, 1) != -1)
 		{
 			printf("%s: heap order error %d %p %p\n", string, ptrCompare(s, prev, 1), prev->ptr, s->ptr);
 			exit(99);
 		}
 		else
 			printf("%s: heap order good %d %p %p\n", string, ptrCompare(s, prev, 1), prev->ptr, s->ptr);
 		}
 	}
 }*/


 /**
  * Allocates a block of memory.  A direct replacement for malloc, but keeps track of items
  * allocated in a list, so that free can check that a item is being freed correctly and that
  * we can check that all memory is freed at shutdown.
  * @param file use the __FILE__ macro to indicate which file this item was allocated in
  * @param line use the __LINE__ macro to indicate which line this item was allocated at
  * @param size the size of the item to be allocated
  * @return pointer to the allocated item, or NULL if there was an error
  */
 void* mymalloc(char* file, int line, size_t size)
 {
 	storageElement* s = NULL;
 	size_t space = sizeof(storageElement);
 	size_t filenamelen = strlen(file)+1;
 	void* rc = NULL;

 	Thread_lock_mutex(heap_mutex);
 	size = Heap_roundup(size);
 	if ((s = malloc(sizeof(storageElement))) == NULL)
 	{
 		Log(LOG_ERROR, 13, errmsg);
 		goto exit;
 	}
 	memset(s, 0, sizeof(storageElement));

 	s->size = size; /* size without eyecatchers */
 	if ((s->file = malloc(filenamelen)) == NULL)
 	{
 		Log(LOG_ERROR, 13, errmsg);
 		free(s);
 		goto exit;
 	}
 	memset(s->file, 0, sizeof(filenamelen));

 	space += filenamelen;
 	strcpy(s->file, file);
 #if defined(HEAP_STACK)
 #define STACK_LEN 300
 	if ((s->stack = malloc(STACK_LEN)) == NULL)
 	{
 		Log(LOG_ERROR, 13, errmsg);
 		free(s->file);
 		free(s);
 		goto exit;
 	}
 	memset(s->stack, 0, sizeof(filenamelen));
 	StackTrace_get(Thread_getid(), s->stack, STACK_LEN);
 #endif
 	s->line = line;
 	/* Add space for eyecatcher at each end */
 	if ((s->ptr = malloc(size + 2*sizeof(eyecatcherType))) == NULL)
 	{
 		Log(LOG_ERROR, 13, errmsg);
 		free(s->file);
 		free(s);
 		goto exit;
 	}
 	memset(s->ptr, 0, size + 2*sizeof(eyecatcherType));
 	space += size + 2*sizeof(eyecatcherType);
 	*(eyecatcherType*)(s->ptr) = eyecatcher; /* start eyecatcher */
 	*(eyecatcherType*)(((char*)(s->ptr)) + (sizeof(eyecatcherType) + size)) = eyecatcher; /* end eyecatcher */
 	Log(TRACE_MAX, -1, "Allocating %d bytes in heap at file %s line %d ptr %p\n", (int)size, file, line, s->ptr);
 	TreeAdd(&heap, s, space);
 	state.current_size += size;
 	if (state.current_size > state.max_size)
 		state.max_size = state.current_size;
 	rc = ((eyecatcherType*)(s->ptr)) + 1;	/* skip start eyecatcher */
 exit:
 	Thread_unlock_mutex(heap_mutex);
 	return rc;
 }


 static void checkEyecatchers(char* file, int line, void* p, size_t size)
 {
 	eyecatcherType *sp = (eyecatcherType*)p;
 	char *cp = (char*)p;
 	eyecatcherType us;
 	static const char *msg = "Invalid %s eyecatcher %d in heap item at file %s line %d";

 	if ((us = *--sp) != eyecatcher)
 		Log(LOG_ERROR, 13, msg, "start", us, file, line);

 	cp += size;
 	if ((us = *(eyecatcherType*)cp) != eyecatcher)
 		Log(LOG_ERROR, 13, msg, "end", us, file, line);
 }


 /**
  * Remove an item from the recorded heap without actually freeing it.
  * Use sparingly!
  * @param file use the __FILE__ macro to indicate which file this item was allocated in
  * @param line use the __LINE__ macro to indicate which line this item was allocated at
  * @param p pointer to the item to be removed
  */
 static int Internal_heap_unlink(char* file, int line, void* p)
 {
 	Node* e = NULL;
 	int rc = 0;

 	e = TreeFind(&heap, ((eyecatcherType*)p)-1);
 	if (e == NULL)
 		Log(LOG_ERROR, 13, "Failed to remove heap item at file %s line %d", file, line);
 	else
 	{
 		storageElement* s = (storageElement*)(e->content);
 		Log(TRACE_MAX, -1, "Freeing %d bytes in heap at file %s line %d, heap use now %d bytes\n",
 											 (int)s->size, file, line, (int)state.current_size);
 		checkEyecatchers(file, line, p, s->size);
 		/* free(s->ptr); */
 		free(s->file);
 		state.current_size -= s->size;
 		TreeRemoveNodeIndex(&heap, e, 0);
 		free(s);
 		rc = 1;
 	}
 	return rc;
 }


 /**
  * Frees a block of memory.  A direct replacement for free, but checks that a item is in
  * the allocates list first.
  * @param file use the __FILE__ macro to indicate which file this item was allocated in
  * @param line use the __LINE__ macro to indicate which line this item was allocated at
  * @param p pointer to the item to be freed
  */
 void myfree(char* file, int line, void* p)
 {
 	if (p) /* it is legal und usual to call free(NULL) */
 	{
 		Thread_lock_mutex(heap_mutex);
 		if (Internal_heap_unlink(file, line, p))
 			free(((eyecatcherType*)p)-1);
 		Thread_unlock_mutex(heap_mutex);
 	}
 	else
 	{
 		Log(LOG_ERROR, -1, "Call of free(NULL) in %s,%d",file,line);
 	}
 }


 /**
  * Remove an item from the recorded heap without actually freeing it.
  * Use sparingly!
  * @param file use the __FILE__ macro to indicate which file this item was allocated in
  * @param line use the __LINE__ macro to indicate which line this item was allocated at
  * @param p pointer to the item to be removed
  */
 void Heap_unlink(char* file, int line, void* p)
 {
 	Thread_lock_mutex(heap_mutex);
 	Internal_heap_unlink(file, line, p);
 	Thread_unlock_mutex(heap_mutex);
 }


 /**
  * Reallocates a block of memory.  A direct replacement for realloc, but keeps track of items
  * allocated in a list, so that free can check that a item is being freed correctly and that
  * we can check that all memory is freed at shutdown.
  * We have to remove the item from the tree, as the memory is in order and so it needs to
  * be reinserted in the correct place.
  * @param file use the __FILE__ macro to indicate which file this item was reallocated in
  * @param line use the __LINE__ macro to indicate which line this item was reallocated at
  * @param p pointer to the item to be reallocated
  * @param size the new size of the item
  * @return pointer to the allocated item, or NULL if there was an error
  */
 void *myrealloc(char* file, int line, void* p, size_t size)
 {
 	void* rc = NULL;
 	storageElement* s = NULL;

 	Thread_lock_mutex(heap_mutex);
 	s = TreeRemoveKey(&heap, ((eyecatcherType*)p)-1);
 	if (s == NULL)
 		Log(LOG_ERROR, 13, "Failed to reallocate heap item at file %s line %d", file, line);
 	else
 	{
 		size_t space = sizeof(storageElement);
 		size_t filenamelen = strlen(file)+1;

 		checkEyecatchers(file, line, p, s->size);
 		size = Heap_roundup(size);
 		state.current_size += size - s->size;
 		if (state.current_size > state.max_size)
 			state.max_size = state.current_size;
 		if ((s->ptr = realloc(s->ptr, size + 2*sizeof(eyecatcherType))) == NULL)
 		{
 			Log(LOG_ERROR, 13, errmsg);
 			goto exit;
 		}
 		space += size + 2*sizeof(eyecatcherType) - s->size;
 		*(eyecatcherType*)(s->ptr) = eyecatcher; /* start eyecatcher */
 		*(eyecatcherType*)(((char*)(s->ptr)) + (sizeof(eyecatcherType) + size)) = eyecatcher; /* end eyecatcher */
 		s->size = size;
 		space -= strlen(s->file);
 		s->file = realloc(s->file, filenamelen);
 		space += filenamelen;
 		strcpy(s->file, file);
 		s->line = line;
 		rc = s->ptr;
 		TreeAdd(&heap, s, space);
 	}
 exit:
 	Thread_unlock_mutex(heap_mutex);
 	return (rc == NULL) ? NULL : ((eyecatcherType*)(rc)) + 1;	/* skip start eyecatcher */
 }


 /**
  * Utility to find an item in the heap.  Lets you know if the heap already contains
  * the memory location in question.
  * @param p pointer to a memory location
  * @return pointer to the storage element if found, or NULL
  */
 void* Heap_findItem(void* p)
 {
 	Node* e = NULL;

 	Thread_lock_mutex(heap_mutex);
 	e = TreeFind(&heap, ((eyecatcherType*)p)-1);
 	Thread_unlock_mutex(heap_mutex);
 	return (e == NULL) ? NULL : e->content;
 }


 /**
  * Scans the heap and reports any items currently allocated.
  * To be used at shutdown if any heap items have not been freed.
  */
 static void HeapScan(enum LOG_LEVELS log_level)
 {
 	Node* current = NULL;

 	Thread_lock_mutex(heap_mutex);
 	Log(log_level, -1, "Heap scan start, total %d bytes", (int)state.current_size);
 	while ((current = TreeNextElement(&heap, current)) != NULL)
 	{
 		storageElement* s = (storageElement*)(current->content);
 		Log(log_level, -1, "Heap element size %d, line %d, file %s, ptr %p", (int)s->size, s->line, s->file, s->ptr);
 		Log(log_level, -1, "  Content %.*s", (10 > current->size) ? (int)s->size : 10, (char*)(((eyecatcherType*)s->ptr) + 1));
 #if defined(HEAP_STACK)
 		Log(log_level, -1, "  Stack:\n%s", s->stack);
 #endif
 	}
 	Log(log_level, -1, "Heap scan end");
 	Thread_unlock_mutex(heap_mutex);
 }


 /**
  * Heap initialization.
  */
 int Heap_initialize(void)
 {
 	TreeInitializeNoMalloc(&heap, ptrCompare);
 	heap.heap_tracking = 0; /* no recursive heap tracking! */
 	return 0;
 }


 /**
  * Heap termination.
  */
 void Heap_terminate(void)
 {
 	Log(TRACE_MIN, -1, "Maximum heap use was %d bytes", (int)state.max_size);
 	if (state.current_size > 20) /* One log list is freed after this function is called */
 	{
 		Log(LOG_ERROR, -1, "Some memory not freed at shutdown, possible memory leak");
 		HeapScan(LOG_ERROR);
 	}
 }


 /**
  * Access to heap state
  * @return pointer to the heap state structure
  */
 heap_info* Heap_get_info(void)
 {
 	return &state;
 }


 /**
  * Dump a string from the heap so that it can be displayed conveniently
  * @param file file handle to dump the heap contents to
  * @param str the string to dump, could be NULL
  */
 int HeapDumpString(FILE* file, char* str)
 {
 	int rc = 0;
 	size_t len = str ? strlen(str) + 1 : 0; /* include the trailing null */

 	if (fwrite(&(str), sizeof(char*), 1, file) != 1)
 		rc = -1;
 	else if (fwrite(&(len), sizeof(int), 1 ,file) != 1)
 		rc = -1;
 	else if (len > 0 && fwrite(str, len, 1, file) != 1)
 		rc = -1;
 	return rc;
 }


 /**
  * Dump the state of the heap
  * @param file file handle to dump the heap contents to
  */
 int HeapDump(FILE* file)
 {
 	int rc = 0;
 	Node* current = NULL;

 	while (rc == 0 && (current = TreeNextElement(&heap, current)))
 	{
 		storageElement* s = (storageElement*)(current->content);

 		if (fwrite(&(s->ptr), sizeof(s->ptr), 1, file) != 1)
 			rc = -1;
 		else if (fwrite(&(current->size), sizeof(current->size), 1, file) != 1)
 			rc = -1;
 		else if (fwrite(s->ptr, current->size, 1, file) != 1)
 			rc = -1;
 	}
 	return rc;
 }

 #endif


 #if defined(HEAP_UNIT_TESTS)

 void Log(enum LOG_LEVELS log_level, int msgno, char* format, ...)
 {
 	printf("Log %s", format);
 }

 char* Broker_recordFFDC(char* symptoms)
 {
 	printf("recordFFDC");
 	return "";
 }

 #define malloc(x) mymalloc(__FILE__, __LINE__, x)
 #define realloc(a, b) myrealloc(__FILE__, __LINE__, a, b)
 #define free(x) myfree(__FILE__, __LINE__, x)

 int main(int argc, char *argv[])
 {
 	char* h = NULL;
 	Heap_initialize();

 	h = malloc(12);
 	free(h);
 	printf("freed h\n");

 	h = malloc(12);
 	h = realloc(h, 14);
 	h = realloc(h, 25);
 	h = realloc(h, 255);
 	h = realloc(h, 2225);
 	h = realloc(h, 22225);
     printf("freeing h\n");
 	free(h);
 	Heap_terminate();
 	printf("Finishing\n");
 	return 0;
 }

 #endif /* HEAP_UNIT_TESTS */

 /* Local Variables: */
 /* indent-tabs-mode: t */
 /* c-basic-offset: 8 */
 /* End: */
	/*******************************************************************************
	* Copyright (c) 2009, 2020 IBM Corp.
	*
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v2.0
	* and Eclipse Distribution License v1.0 which accompany this distribution.
	*
	* The Eclipse Public License is available at
	* https://www.eclipse.org/legal/epl-2.0/
	* and the Eclipse Distribution License is available at
	* http://www.eclipse.org/org/documents/edl-v10.php.
	*
	* Contributors:
	* Ian Craggs - initial API and implementation and/or initial documentation
	* Ian Craggs - use tree data structure instead of list
	* Ian Craggs - change roundup to Heap_roundup to avoid macro name clash on MacOSX
	*******************************************************************************/

	/**
	* @file
	* \brief functions to manage the heap with the goal of eliminating memory leaks
	*
	* For any module to use these functions transparently, simply include the Heap.h
	* header file. Malloc and free will be redefined, but will behave in exactly the same
	* way as normal, so no recoding is necessary.
	*
	* */

	#include "Tree.h"
	#include "Log.h"
	#include "StackTrace.h"
	#include "Thread.h"

	#if defined(HEAP_UNIT_TESTS)
	char* Broker_recordFFDC(char* symptoms);
	#endif /* HEAP_UNIT_TESTS */

	#include <stdlib.h>
	#include <string.h>
	#include <stdio.h>
	#include <stddef.h>

	#include "Heap.h"

	#if !defined(NO_HEAP_TRACKING)

	#undef malloc
	#undef realloc
	#undef free

	#if defined(_WIN32) \|\| defined(_WIN64)
	mutex_type heap_mutex;
	#else
	static pthread_mutex_t heap_mutex_store = PTHREAD_MUTEX_INITIALIZER;
	static mutex_type heap_mutex = &heap_mutex_store;
	#endif

	static heap_info state = {0, 0}; /*< global heap state information /

	typedef double eyecatcherType;
	static eyecatcherType eyecatcher = (eyecatcherType)0x8888888888888888;

	/#define HEAP_STACK 1 /

	/**
	* Each item on the heap is recorded with this structure.
	*/
	typedef struct
	{
	char* file; /*< the name of the source file where the storage was allocated /
	int line; /*< the line no in the source file where it was allocated /
	void* ptr; /*< pointer to the allocated storage /
	size_t size; /*< size of the allocated storage /
	#if defined(HEAP_STACK)
	char* stack;
	#endif
	} storageElement;

	static Tree heap; /*< Tree that holds the allocation records /
	static const char *errmsg = "Memory allocation error";


	static size_t Heap_roundup(size_t size);
	static int ptrCompare(void* a, void* b, int value);
	/static void Heap_check(char string, void* ptr);*/
	static void checkEyecatchers(char* file, int line, void* p, size_t size);
	static int Internal_heap_unlink(char* file, int line, void* p);
	static void HeapScan(enum LOG_LEVELS log_level);


	/**
	* Round allocation size up to a multiple of the size of an int. Apart from possibly reducing fragmentation,
	* on the old v3 gcc compilers I was hitting some weird behaviour, which might have been errors in
	* sizeof() used on structures and related to packing. In any case, this fixes that too.
	* @param size the size actually needed
	* @return the rounded up size
	*/
	static size_t Heap_roundup(size_t size)
	{
	static int multsize = 4*sizeof(int);

	if (size % multsize != 0)
	size += multsize - (size % multsize);
	return size;
	}


	/**
	* List callback function for comparing storage elements
	* @param a pointer to the current content in the tree (storageElement*)
	* @param b pointer to the memory to free
	* @return boolean indicating whether a and b are equal
	*/
	static int ptrCompare(void* a, void* b, int value)
	{
	a = ((storageElement*)a)->ptr;
	if (value)
	b = ((storageElement*)b)->ptr;

	return (a > b) ? -1 : (a == b) ? 0 : 1;
	}

	/*
	static void Heap_check(char* string, void* ptr)
	{
	Node* curnode = NULL;
	storageElement* prev, *s = NULL;

	printf("Heap_check start %p\n", ptr);
	while ((curnode = TreeNextElement(&heap, curnode)) != NULL)
	{
	prev = s;
	s = (storageElement*)(curnode->content);

	if (prev)
	{
	if (ptrCompare(s, prev, 1) != -1)
	{
	printf("%s: heap order error %d %p %p\n", string, ptrCompare(s, prev, 1), prev->ptr, s->ptr);
	exit(99);
	}
	else
	printf("%s: heap order good %d %p %p\n", string, ptrCompare(s, prev, 1), prev->ptr, s->ptr);
	}
	}
	}*/


	/**
	* Allocates a block of memory. A direct replacement for malloc, but keeps track of items
	* allocated in a list, so that free can check that a item is being freed correctly and that
	* we can check that all memory is freed at shutdown.
	* @param file use the __FILE__ macro to indicate which file this item was allocated in
	* @param line use the __LINE__ macro to indicate which line this item was allocated at
	* @param size the size of the item to be allocated
	* @return pointer to the allocated item, or NULL if there was an error
	*/
	void* mymalloc(char* file, int line, size_t size)
	{
	storageElement* s = NULL;
	size_t space = sizeof(storageElement);
	size_t filenamelen = strlen(file)+1;
	void* rc = NULL;

	Thread_lock_mutex(heap_mutex);
	size = Heap_roundup(size);
	if ((s = malloc(sizeof(storageElement))) == NULL)
	{
	Log(LOG_ERROR, 13, errmsg);
	goto exit;
	}
	memset(s, 0, sizeof(storageElement));

	s->size = size; /* size without eyecatchers */
	if ((s->file = malloc(filenamelen)) == NULL)
	{
	Log(LOG_ERROR, 13, errmsg);
	free(s);
	goto exit;
	}
	memset(s->file, 0, sizeof(filenamelen));

	space += filenamelen;
	strcpy(s->file, file);
	#if defined(HEAP_STACK)
	#define STACK_LEN 300
	if ((s->stack = malloc(STACK_LEN)) == NULL)
	{
	Log(LOG_ERROR, 13, errmsg);
	free(s->file);
	free(s);
	goto exit;
	}
	memset(s->stack, 0, sizeof(filenamelen));
	StackTrace_get(Thread_getid(), s->stack, STACK_LEN);
	#endif
	s->line = line;
	/* Add space for eyecatcher at each end */
	if ((s->ptr = malloc(size + 2*sizeof(eyecatcherType))) == NULL)
	{
	Log(LOG_ERROR, 13, errmsg);
	free(s->file);
	free(s);
	goto exit;
	}
	memset(s->ptr, 0, size + 2*sizeof(eyecatcherType));
	space += size + 2*sizeof(eyecatcherType);
	(eyecatcherType)(s->ptr) = eyecatcher; /* start eyecatcher */
	(eyecatcherType)(((char)(s->ptr)) + (sizeof(eyecatcherType) + size)) = eyecatcher; / end eyecatcher */
	Log(TRACE_MAX, -1, "Allocating %d bytes in heap at file %s line %d ptr %p\n", (int)size, file, line, s->ptr);
	TreeAdd(&heap, s, space);
	state.current_size += size;
	if (state.current_size > state.max_size)
	state.max_size = state.current_size;
	rc = ((eyecatcherType)(s->ptr)) + 1; / skip start eyecatcher */
	exit:
	Thread_unlock_mutex(heap_mutex);
	return rc;
	}


	static void checkEyecatchers(char* file, int line, void* p, size_t size)
	{
	eyecatcherType sp = (eyecatcherType)p;
	char cp = (char)p;
	eyecatcherType us;
	static const char *msg = "Invalid %s eyecatcher %d in heap item at file %s line %d";

	if ((us = *--sp) != eyecatcher)
	Log(LOG_ERROR, 13, msg, "start", us, file, line);

	cp += size;
	if ((us = (eyecatcherType)cp) != eyecatcher)
	Log(LOG_ERROR, 13, msg, "end", us, file, line);
	}


	/**
	* Remove an item from the recorded heap without actually freeing it.
	* Use sparingly!
	* @param file use the __FILE__ macro to indicate which file this item was allocated in
	* @param line use the __LINE__ macro to indicate which line this item was allocated at
	* @param p pointer to the item to be removed
	*/
	static int Internal_heap_unlink(char* file, int line, void* p)
	{
	Node* e = NULL;
	int rc = 0;

	e = TreeFind(&heap, ((eyecatcherType*)p)-1);
	if (e == NULL)
	Log(LOG_ERROR, 13, "Failed to remove heap item at file %s line %d", file, line);
	else
	{
	storageElement* s = (storageElement*)(e->content);
	Log(TRACE_MAX, -1, "Freeing %d bytes in heap at file %s line %d, heap use now %d bytes\n",
	(int)s->size, file, line, (int)state.current_size);
	checkEyecatchers(file, line, p, s->size);
	/* free(s->ptr); */
	free(s->file);
	state.current_size -= s->size;
	TreeRemoveNodeIndex(&heap, e, 0);
	free(s);
	rc = 1;
	}
	return rc;
	}


	/**
	* Frees a block of memory. A direct replacement for free, but checks that a item is in
	* the allocates list first.
	* @param file use the __FILE__ macro to indicate which file this item was allocated in
	* @param line use the __LINE__ macro to indicate which line this item was allocated at
	* @param p pointer to the item to be freed
	*/
	void myfree(char* file, int line, void* p)
	{
	if (p) /* it is legal und usual to call free(NULL) */
	{
	Thread_lock_mutex(heap_mutex);
	if (Internal_heap_unlink(file, line, p))
	free(((eyecatcherType*)p)-1);
	Thread_unlock_mutex(heap_mutex);
	}
	else
	{
	Log(LOG_ERROR, -1, "Call of free(NULL) in %s,%d",file,line);
	}
	}


	/**
	* Remove an item from the recorded heap without actually freeing it.
	* Use sparingly!
	* @param file use the __FILE__ macro to indicate which file this item was allocated in
	* @param line use the __LINE__ macro to indicate which line this item was allocated at
	* @param p pointer to the item to be removed
	*/
	void Heap_unlink(char* file, int line, void* p)
	{
	Thread_lock_mutex(heap_mutex);
	Internal_heap_unlink(file, line, p);
	Thread_unlock_mutex(heap_mutex);
	}


	/**
	* Reallocates a block of memory. A direct replacement for realloc, but keeps track of items
	* allocated in a list, so that free can check that a item is being freed correctly and that
	* we can check that all memory is freed at shutdown.
	* We have to remove the item from the tree, as the memory is in order and so it needs to
	* be reinserted in the correct place.
	* @param file use the __FILE__ macro to indicate which file this item was reallocated in
	* @param line use the __LINE__ macro to indicate which line this item was reallocated at
	* @param p pointer to the item to be reallocated
	* @param size the new size of the item
	* @return pointer to the allocated item, or NULL if there was an error
	*/
	void myrealloc(char file, int line, void* p, size_t size)
	{
	void* rc = NULL;
	storageElement* s = NULL;

	Thread_lock_mutex(heap_mutex);
	s = TreeRemoveKey(&heap, ((eyecatcherType*)p)-1);
	if (s == NULL)
	Log(LOG_ERROR, 13, "Failed to reallocate heap item at file %s line %d", file, line);
	else
	{
	size_t space = sizeof(storageElement);
	size_t filenamelen = strlen(file)+1;

	checkEyecatchers(file, line, p, s->size);
	size = Heap_roundup(size);
	state.current_size += size - s->size;
	if (state.current_size > state.max_size)
	state.max_size = state.current_size;
	if ((s->ptr = realloc(s->ptr, size + 2*sizeof(eyecatcherType))) == NULL)
	{
	Log(LOG_ERROR, 13, errmsg);
	goto exit;
	}
	space += size + 2*sizeof(eyecatcherType) - s->size;
	(eyecatcherType)(s->ptr) = eyecatcher; /* start eyecatcher */
	(eyecatcherType)(((char)(s->ptr)) + (sizeof(eyecatcherType) + size)) = eyecatcher; / end eyecatcher */
	s->size = size;
	space -= strlen(s->file);
	s->file = realloc(s->file, filenamelen);
	space += filenamelen;
	strcpy(s->file, file);
	s->line = line;
	rc = s->ptr;
	TreeAdd(&heap, s, space);
	}
	exit:
	Thread_unlock_mutex(heap_mutex);
	return (rc == NULL) ? NULL : ((eyecatcherType)(rc)) + 1; / skip start eyecatcher */
	}


	/**
	* Utility to find an item in the heap. Lets you know if the heap already contains
	* the memory location in question.
	* @param p pointer to a memory location
	* @return pointer to the storage element if found, or NULL
	*/
	void* Heap_findItem(void* p)
	{
	Node* e = NULL;

	Thread_lock_mutex(heap_mutex);
	e = TreeFind(&heap, ((eyecatcherType*)p)-1);
	Thread_unlock_mutex(heap_mutex);
	return (e == NULL) ? NULL : e->content;
	}


	/**
	* Scans the heap and reports any items currently allocated.
	* To be used at shutdown if any heap items have not been freed.
	*/
	static void HeapScan(enum LOG_LEVELS log_level)
	{
	Node* current = NULL;

	Thread_lock_mutex(heap_mutex);
	Log(log_level, -1, "Heap scan start, total %d bytes", (int)state.current_size);
	while ((current = TreeNextElement(&heap, current)) != NULL)
	{
	storageElement* s = (storageElement*)(current->content);
	Log(log_level, -1, "Heap element size %d, line %d, file %s, ptr %p", (int)s->size, s->line, s->file, s->ptr);
	Log(log_level, -1, " Content %.s", (10 > current->size) ? (int)s->size : 10, (char)(((eyecatcherType*)s->ptr) + 1));
	#if defined(HEAP_STACK)
	Log(log_level, -1, " Stack:\n%s", s->stack);
	#endif
	}
	Log(log_level, -1, "Heap scan end");
	Thread_unlock_mutex(heap_mutex);
	}


	/**
	* Heap initialization.
	*/
	int Heap_initialize(void)
	{
	TreeInitializeNoMalloc(&heap, ptrCompare);
	heap.heap_tracking = 0; /* no recursive heap tracking! */
	return 0;
	}


	/**
	* Heap termination.
	*/
	void Heap_terminate(void)
	{
	Log(TRACE_MIN, -1, "Maximum heap use was %d bytes", (int)state.max_size);
	if (state.current_size > 20) /* One log list is freed after this function is called */
	{
	Log(LOG_ERROR, -1, "Some memory not freed at shutdown, possible memory leak");
	HeapScan(LOG_ERROR);
	}
	}


	/**
	* Access to heap state
	* @return pointer to the heap state structure
	*/
	heap_info* Heap_get_info(void)
	{
	return &state;
	}


	/**
	* Dump a string from the heap so that it can be displayed conveniently
	* @param file file handle to dump the heap contents to
	* @param str the string to dump, could be NULL
	*/
	int HeapDumpString(FILE* file, char* str)
	{
	int rc = 0;
	size_t len = str ? strlen(str) + 1 : 0; /* include the trailing null */

	if (fwrite(&(str), sizeof(char*), 1, file) != 1)
	rc = -1;
	else if (fwrite(&(len), sizeof(int), 1 ,file) != 1)
	rc = -1;
	else if (len > 0 && fwrite(str, len, 1, file) != 1)
	rc = -1;
	return rc;
	}


	/**
	* Dump the state of the heap
	* @param file file handle to dump the heap contents to
	*/
	int HeapDump(FILE* file)
	{
	int rc = 0;
	Node* current = NULL;

	while (rc == 0 && (current = TreeNextElement(&heap, current)))
	{
	storageElement* s = (storageElement*)(current->content);

	if (fwrite(&(s->ptr), sizeof(s->ptr), 1, file) != 1)
	rc = -1;
	else if (fwrite(&(current->size), sizeof(current->size), 1, file) != 1)
	rc = -1;
	else if (fwrite(s->ptr, current->size, 1, file) != 1)
	rc = -1;
	}
	return rc;
	}

	#endif


	#if defined(HEAP_UNIT_TESTS)

	void Log(enum LOG_LEVELS log_level, int msgno, char* format, ...)
	{
	printf("Log %s", format);
	}

	char* Broker_recordFFDC(char* symptoms)
	{
	printf("recordFFDC");
	return "";
	}

	#define malloc(x) mymalloc(__FILE__, __LINE__, x)
	#define realloc(a, b) myrealloc(__FILE__, __LINE__, a, b)
	#define free(x) myfree(__FILE__, __LINE__, x)

	int main(int argc, char *argv[])
	{
	char* h = NULL;
	Heap_initialize();

	h = malloc(12);
	free(h);
	printf("freed h\n");

	h = malloc(12);
	h = realloc(h, 14);
	h = realloc(h, 25);
	h = realloc(h, 255);
	h = realloc(h, 2225);
	h = realloc(h, 22225);
	printf("freeing h\n");
	free(h);
	Heap_terminate();
	printf("Finishing\n");
	return 0;
	}

	#endif /* HEAP_UNIT_TESTS */

	/* Local Variables: */
	/* indent-tabs-mode: t */
	/* c-basic-offset: 8 */
	/* End: */