path: root/cpukit/httpd/balloc.c

/*
 * balloc.c -- Block allocation module
 *
 * Copyright (c) GoAhead Software Inc., 1995-1999. All Rights Reserved.
 *
 * See the file "license.txt" for usage and redistribution license requirements
 */

/******************************** Description *********************************/

/*
 *	This module implements a very fast block allocation scheme suitable for
 *	ROMed environments. It maintains block class queues for rapid allocation
 *	and minimal fragmentation. This modules does not coalesce blocks. The 
 *	storage space may be populated statically or via the traditional malloc 
 *	mechanisms. Large blocks greater than the maximum class size may be 
 *	allocated from the O/S or run-time system via malloc. To permit the use 
 *	of malloc, call bopen with flags set to B_USE_MALLOC (this is the default).
 *	It is recommended that bopen be called first thing in the application. 
 *	If it is not, it will be called with default values on the first call to 
 *	balloc(). Note that this code is not designed for multi-threading purposes
 *	and it depends on newly declared variables being initialized to zero.
 */  

/********************************* Includes ***********************************/

#define IN_BALLOC

#if UEMF
	#include	"uemf.h"
#else
	#include	"basic/basicInternal.h"
#endif

#include	<stdarg.h>
#include	<stdlib.h>

#if !NO_BALLOC
/********************************* Defines ************************************/

typedef struct {
	union {
		void	*next;							/* Pointer to next in q */
		int		size;							/* Actual requested size */
	} u;
	int			flags;							/* Per block allocation flags */
} bType;

/*
 *	Define B_STATS if you wish to track memory block and stack usage
 */
#if B_STATS
/*
 *	Optional statistics
 */

typedef struct {
	long	alloc;								/* Block allocation calls */
	long	inuse;								/* Blocks in use */
} bStatsType;

typedef struct {
	char_t 	file[FNAMESIZE];
	long	allocated;							/* Bytes currently allocated */
	long	count;								/* Current block count */
	long	allocs;								/* Count of alloc attempts */
} bStatsFileType;

/*
 *	This one is very expensive but great stats
 */
typedef struct {
	void			*ptr;						/* Pointer to memory */
	bStatsFileType	*who;						/* Who allocated the memory */
} bStatsBlkType;

static bStatsType		bStats[B_MAX_CLASS];	/* Per class stats */
static bStatsFileType 	bStatsFiles[B_MAX_FILES];/* Per file stats */
static bStatsBlkType 	bStatsBlks[B_MAX_BLOCKS];/* Per block stats */
static int			 	bStatsBlksMax;			/* Max block entry */
static int			 	bStatsFilesMax;			/* Max file entry */
static int 				bStatsMemInUse;			/* Memory currently in use */
static int 				bStatsMemMax;			/* Max memory ever used */
static void				*bStackMin = (void*) -1;/* Miniumum stack position */
static void				*bStackStart;			/* Starting stack position */
static int 				bStatsMemMalloc;		/* Malloced memory */
#endif /* B_STATS */


/********************************** Locals ************************************/
/*
 *	bQhead blocks are created as the original memory allocation is freed up.
 *	See bfree.
 */
static bType			*bQhead[B_MAX_CLASS];	/* Per class block q head */
static char				*bFreeBuf;				/* Pointer to free memory */
static char				*bFreeNext;				/* Pointer to next free mem */
static int				bFreeSize;				/* Size of free memory */
static int				bFreeLeft;				/* Size of free left for use */
static int				bFlags = B_USE_MALLOC;	/* Default to auto-malloc */

/*************************** Forward Declarations *****************************/

#if B_STATS
static void bStatsAlloc(B_ARGS_DEC, void *ptr, int q, int size);
static void bStatsFree(B_ARGS_DEC, void *ptr, int q, int size);
static void bstatsWrite(int handle, char_t *fmt, ...);
static int 	bStatsFileSort(const void *cp1, const void *cp2);
#endif /* B_STATS */

#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
static void bFillBlock(void *buf, int bufsize);
#endif

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
static void verifyUsedBlock(bType *bp, int q);
static void verifyFreeBlock(bType *bp, int q);
static void verifyBallocSpace();
#endif

/********************************** Code **************************************/
/*
 *	Initialize the balloc module. bopen should be called the very first thing
 *	after the application starts and bclose should be called the last thing 
 *	before exiting. If bopen is not called, it will be called on the first 
 *	allocation with default values. "buf" points to memory to use of size 
 *	"bufsize". If buf is NULL, memory is allocated using malloc. flags may 
 *	be set to B_USE_MALLOC if using malloc is okay. This routine will allocate
 *	an initial buffer of size bufsize for use by the application.
 */

int bopen(void *buf, int bufsize, int flags)
{
	bFlags = flags;

	if (buf == NULL) {
		if (bufsize == 0) {
			bufsize = B_DEFAULT_MEM;
		}
		if ((buf = malloc(bufsize)) == NULL) {
			return -1;
		}
#if B_STATS
		bStatsMemMalloc += bufsize;
#endif
	} else {
		bFlags |= B_USER_BUF;
	}

	bFreeSize = bFreeLeft = bufsize;
	bFreeBuf = bFreeNext = buf;
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
	bFillBlock(buf, bufsize);
#endif
#if B_STATS
	bStackStart = &buf;
#endif
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyFreeBlock(buf, bufsize);
#endif
	return 0;
}

/******************************************************************************/
/*
 *	Close down the balloc module and free all malloced memory.
 */

void bclose()
{
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	if (! (bFlags & B_USER_BUF)) {
		free(bFreeBuf);
	}
}

/******************************************************************************/
/*
 *	Allocate a block of the requested size. First check the block 
 *	queues for a suitable one.
 */

void *balloc(B_ARGS_DEC, int size)
{
	bType	*bp;
	int		q, memSize, mask;

/*
 *	Call bopen with default values if the application has not yet done so
 */
	if (bFreeBuf == NULL) {
		if (bopen(NULL, B_DEFAULT_MEM , 0) < 0) {
			return NULL;
		}
	}
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	if (size < 0) {
		return NULL;
	}

/*
 *	Determine the relevant block queue with a block big enough --  
 *	include room for the block header. 
 */
	mask = (size + sizeof(bType)) >> B_SHIFT;
	for (q = 0; mask; mask >>= 1) {
		q++;
	}

	a_assert(0 <= q && q <= B_MAX_CLASS);
	memSize = (1 << (B_SHIFT + q));

	if (q >= B_MAX_CLASS) {
/*
 *		Size if bigger than the maximum class. Malloc if use has been okayed
 */
		if (bFlags & B_USE_MALLOC) {
#if B_STATS
			bstats(0, NULL);
#endif
			bp = (bType*) malloc(memSize);
			if (bp == NULL) {
				trace(0, T("B: malloc failed for %s:%d, size %d\n"),
					B_ARGS, memSize);
				return NULL;
			}
#if B_STATS
			bStatsMemMalloc += memSize;
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
			bFillBlock(bp, memSize);
#endif

		} else {
			trace(0, T("B: balloc failed for %s:%d, size %d\n"),
				B_ARGS, memSize);
			return NULL;
		}
		bp->u.size = size;
		bp->flags = B_MALLOCED;

	} else if ((bp = bQhead[q]) != NULL) {
/*
 *		Take first block off the relevant q if non-empty
 */
		bQhead[q] = bp->u.next;
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
		verifyFreeBlock(bp, q);
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
		bFillBlock(bp, memSize);
#endif
		bp->u.size = size;
		bp->flags = 0;

	} else {
		if (bFreeLeft > memSize) {
/*
 *			The q was empty, and the free list has spare memory so 
 *			create a new block out of the primary free block
 */
			bp = (bType*) bFreeNext;
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
			verifyFreeBlock(bp, q);
#endif
			bFreeNext += memSize;
			bFreeLeft -= memSize;
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
			bFillBlock(bp, memSize);
#endif
			bp->u.size = size;
			bp->flags = 0;

		} else if (bFlags & B_USE_MALLOC) {
			static int once = 0;
			if (once++ < 20) {
#if B_STATS
				bstats(0, NULL);
#endif
			}
/*
 *			Nothing left on the primary free list, so malloc a new block
 */
			if ((bp = (bType*) malloc(memSize)) == NULL) {
				trace(0, T("B: malloc failed for %s:%d size %d\n"),
					B_ARGS, memSize);
				return NULL;
			}
#if B_STATS
			bStatsMemMalloc += memSize;
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
			bFillBlock(bp, memSize);
#endif
			bp->u.size = size;
			bp->flags = B_MALLOCED;

		} else {
			trace(0, T("B: alloc failed for %s:%d size %d\n"), B_ARGS, size);
			return NULL;
		}
	}

#if B_STATS
	bStatsAlloc(B_ARGS, bp, q, size);
#endif
	bp->flags |= B_INTEGRITY;

	return (void*) ((char*) bp + sizeof(bType));
}

/******************************************************************************/
/*
 *	Free a block back to the relevant free q. We don't free back to the O/S
 *	or run time system unless the block is greater than the maximum class size.
 *	We also do not coalesce blocks.
 */

void bfree(B_ARGS_DEC, void *mp)
{
	bType	*bp;
	int		mask, q;

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	a_assert(mp);

	bp = (bType*) ((char*) mp - sizeof(bType));
	a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
	if ((bp->flags & B_INTEGRITY_MASK) != B_INTEGRITY) {
		return;
	}

/*
 *	Determine the relevant block queue
 */
	mask = (bp->u.size + sizeof(bType)) >> B_SHIFT;
	for (q = 0; mask; mask >>= 1) {
		q++;
	}
	a_assert(0 <= q && q <= B_MAX_CLASS);

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyUsedBlock(bp,q);
#endif
	if (bp->flags & B_MALLOCED) {
		free(bp);
		return;
	}
		
#if B_STATS
	bStatsFree(B_ARGS, bp, q, bp->u.size);
#endif
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
	bFillBlock(bp, 1 << (B_SHIFT + q));
#endif

/*
 *	Simply link onto the head of the relevant q
 */
	bp->u.next = bQhead[q];
	bQhead[q] = bp;
}

/******************************************************************************/
/*
 *	Safe free
 */

void bfreeSafe(B_ARGS_DEC, void *mp)
{
	if (mp) {
		bfree(B_ARGS, mp);
	}
}

/******************************************************************************/
#if UNICODE
/*
 *	Duplicate a string, allow NULL pointers and then dup an empty string.
 */

char *bstrdupA(B_ARGS_DEC, char *s)
{
	char	*cp;
	int		len;

	if (s == NULL) {
		s = "";
	}
	len = strlen(s) + 1;
	if (cp = balloc(B_ARGS, len)) {
		strcpy(cp, s);
	}
	return cp;
}

#endif /* UNICODE */
/******************************************************************************/
/*
 *	Duplicate an ascii string, allow NULL pointers and then dup an empty string.
 *	If UNICODE, bstrdup above works with wide chars, so we need this routine
 *	for ascii strings. 
 */

char_t *bstrdup(B_ARGS_DEC, char_t *s)
{
	char_t	*cp;
	int		len;

	if (s == NULL) {
		s = T("");
	}
	len = gstrlen(s) + 1;
	if ((cp = balloc(B_ARGS, len * sizeof(char_t))) != NULL) {
		gstrcpy(cp, s);
	}
	return cp;
}

/******************************************************************************/
/*
 *	Reallocate a block. Allow NULL pointers and just do a malloc.
 *	Note: if the realloc fails, we return NULL and the previous buffer is 
 *	preserved.
 */

void *brealloc(B_ARGS_DEC, void *mp, int newsize)
{
	bType*	bp;
	void	*newbuf;

	if (mp == NULL) {
		return balloc(B_ARGS, newsize);
	}
	bp = (bType*) ((char*) mp - sizeof(bType));
	a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
	if ((newbuf = balloc(B_ARGS, newsize)) != NULL) {
		memcpy(newbuf, mp, bp->u.size);
		bfree(B_ARGS, mp);
	}
	return newbuf;
}


/******************************************************************************/
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
/*
 *	Fill the block (useful during development to catch zero fill assumptions)
 */

static void bFillBlock(void *buf, int bufsize)
{
	memset(buf, B_FILL_CHAR, bufsize);
}
#endif

/******************************************************************************/
#if B_STATS
/*
 *	Statistics. Do output via calling the writefn callback function with 
 *	"handle" as the output file handle.
 */

void bstats(int handle, void (*writefn)(int handle, char_t *fmt, ...))
{
	bStatsFileType	*fp;
	bType			*bp;
	int				q, count, mem, total;
	static	int 	recurseProtect = 0;

	if (recurseProtect++ > 0) {
		return;
	}

	if (writefn == NULL) {
		writefn = bstatsWrite;
	}

/*
 *	Print stats for each memory block
 */
	(*writefn)(handle, T("\nMemory Stats\n"));

/*
 *	The following tabular format is now used for the output.
 *   Q  Size  Free Bytes Inuse Bytes Allocs
 *	dd ddddd   ddd ddddd  dddd ddddd   dddd
 */
	(*writefn)(handle, " Q  Size  Free Bytes Inuse Bytes Allocs\n");

	total = 0;
	for (q = 0; q < B_MAX_CLASS; q++) {
		count = 0;
		for (bp = bQhead[q]; bp; bp = bp->u.next) {
			a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
			count++;
		}
		mem = count * (1 << (q + B_SHIFT));
		total += mem;
		(*writefn)(handle, 
			T("%2d %5d   %3d %5d  %4d %5d   %4d\n"),
			q, 1 << (q + B_SHIFT), count, mem, bStats[q].inuse, 
			bStats[q].inuse * (1 << (q + B_SHIFT)), bStats[q].alloc);
	}

	(*writefn)(handle, T("\n"));

/*
 *	Print summary stats
 */
	(*writefn)(handle, T("Initial free list size    %7d\n"), bFreeSize);
	(*writefn)(handle, T("Max memory malloced       %7d\n"), bStatsMemMalloc);
	(*writefn)(handle, T("Max memory ever used      %7d\n"), bStatsMemMax);
	(*writefn)(handle, T("Memory currently in use   %7d\n"), bStatsMemInUse);
	(*writefn)(handle, T("Max blocks allocated      %7d\n"), bStatsBlksMax);
	(*writefn)(handle, T("Maximum stack used        %7d\n"), 
		(int) bStackStart - (int) bStackMin);

	(*writefn)(handle, T("Free memory on all queues %7d\n"), total);
	(*writefn)(handle, T("Free list buffer left     %7d\n"), bFreeLeft);
	(*writefn)(handle, T("Total free memory         %7d\n"), bFreeLeft + total);

/*
 *	Print per file allocation stats
 */
	qsort(bStatsFiles, bStatsFilesMax, sizeof(bStatsFileType), bStatsFileSort);
	(*writefn)(handle, T("\nPer File Memory Stats\n"));
	total = 0;
	for (fp = bStatsFiles; fp < &bStatsFiles[bStatsFilesMax]; fp++) {
		if (fp->file[0]) {
			(*writefn)(handle, 
				T("%18s, bytes %7d, blocks in use %5d, total allocs %6d\n"),
				fp->file, fp->allocated, fp->count, fp->allocs);
			total += fp->allocated;
		}
	}
	(*writefn)(handle, T("\nTotal allocated %7d\n"), total);
	recurseProtect--;
}

/******************************************************************************/
/*
 *	File sort function. Used to sort per file stats
 */

static int bStatsFileSort(const void *cp1, const void *cp2)
{
	bStatsFileType	*s1, *s2;

	s1 = (bStatsFileType*) cp1;
	s2 = (bStatsFileType*) cp2;

	if (s1->allocated < s2->allocated)
		return -1;
	else if (s1->allocated == s2->allocated)
		return 0;
	return 1;
}

/******************************************************************************/
/*
 *	Default output function. Just send to trace channel.
 */

static void bstatsWrite(int handle, char_t *fmt, ...)
{
	va_list		args;
	char_t		*buf;

	va_start(args, fmt);
	buf = NULL;
	gvsnprintf(&buf, VALUE_MAX_STRING, fmt, args);
	va_end(args);
	trace(0, buf);
	if (buf) {
		bfree(B_L, buf);
	}
}

/******************************************************************************/
/*
 *	Accumulate allocation statistics
 */

static void bStatsAlloc(B_ARGS_DEC, void *ptr, int q, int size)
{
	bStatsFileType	*fp;
	bStatsBlkType	*bp;
	char_t			name[FNAMESIZE + 10];

	a_assert(file && *file);
	a_assert(0 <= q && q <= B_MAX_CLASS);
	a_assert(size > 0);

	gsprintf(name, T("%s:%d"), B_ARGS);

	bStats[q].alloc++;
	bStats[q].inuse++;
	bStatsMemInUse += size;

	if (bStatsMemInUse > bStatsMemMax) {
		bStatsMemMax = bStatsMemInUse;
	}

/*
 *	Track maximum stack usage. Assumes a stack growth down. Approximate as
 *	we only measure this on block allocation.
 */
	if ((void*) &file < bStackMin) {
		bStackMin = (void*) &file;
	}

/*
 *	Find the file and adjust the stats for this file
 */
	for (fp = bStatsFiles; fp < &bStatsFiles[bStatsFilesMax]; fp++) {
		if (fp->file[0] == file[0] && gstrcmp(fp->file, name) == 0) {
			fp->allocated += size;
			fp->count++;
			fp->allocs++;
			break;
		}
	}

/*
 *	Find the first free slot for this file and add current block size.
 */
	if (fp >= &bStatsFiles[bStatsFilesMax]) {
		for (fp = bStatsFiles; fp < &bStatsFiles[B_MAX_FILES]; fp++) {
			if (fp->file[0] == '\0') {
				gstrncpy(fp->file, name, TSZ(fp->file));
				fp->allocated += size;
				fp->count++;
				fp->allocs++;
				if ((fp - bStatsFiles) >= bStatsFilesMax) {
					bStatsFilesMax = (fp - bStatsFiles) + 1;
				}
				break;
			}
		}
	}

/*
 *	Update the per block stats. Allocate a new slot.
 */
	for (bp = bStatsBlks; bp < &bStatsBlks[B_MAX_BLOCKS]; bp++) {
		if (bp->ptr == NULL) {
			bp->ptr = ptr;
			bp->who = fp;
			if ((bp - bStatsBlks) >= bStatsBlksMax) {
				bStatsBlksMax = (bp - bStatsBlks) + 1;
			}
			break;
		}
	}
}

/******************************************************************************/
/*
 *	Free statistics
 */

static void bStatsFree(B_ARGS_DEC, void *ptr, int q, int size)
{
	bStatsFileType	*fp;
	bStatsBlkType	*bp;
	char_t			name[FNAMESIZE + 10];

	a_assert(file && *file);
	a_assert(0 <= q && q <= B_MAX_CLASS);
	a_assert(size > 0);

	bStatsMemInUse -= size;
	bStats[q].inuse--;

	gsprintf(name, T("%s:%d"), B_ARGS);

/*
 *	Update the per block stats 
 */
	for (bp = bStatsBlks; bp < &bStatsBlks[bStatsBlksMax]; bp++) {
		if (bp->ptr == ptr) {
			bp->ptr = NULL;
			fp = bp->who;
			fp->allocated -= size;
			fp->count--;
			return;
		}
	}
	a_assert(0);

}

#else /* not B_STATS */
/******************************************************************************/
/*
 *	Dummy bstats for external calls that aren't protected by #if B_STATS.
 */

void bstats(int handle, void (*writefn)(int handle, char_t *fmt, ...))
{
}
#endif /* B_STATS */

/******************************************************************************/
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
/*
 *	The following routines verify the integrity of the balloc memory space.
 *	These functions depend use the B_FILL feature.  Corruption is defined
 *	as bad integrity flags in allocated blocks or data other than B_FILL_CHAR
 *	being found anywhere in the space which is unallocated and that is not a
 *	next pointer in the free queues.  a_assert is called if any corruption is
 *	found.  CAUTION:  These functions add severe processing overhead and should
 *	only be used when searching for a tough corruption problem.
 */

/******************************************************************************/
/*
 *	verifyUsedBlock verifies that a block which was previously allocated is
 *	still uncorrupted.  
 */

static void verifyUsedBlock(bType *bp, int q)
{
	int		memSize, size;
	char	*p;

	memSize = (1 << (B_SHIFT + q));
	a_assert((bp->flags & ~B_MALLOCED) == B_INTEGRITY );
	size = bp->u.size;
	for (p = ((char *)bp)+sizeof(bType)+size; p < ((char*)bp)+memSize; p++) {
		a_assert(*p == B_FILL_CHAR);
	}
}

/******************************************************************************/
/*
 *	verifyFreeBlock verifies that a previously free'd block in one of the queues
 *	is still uncorrupted.
 */

static void verifyFreeBlock(bType *bp, int q)
{
	int		memSize;
	char	*p;

	memSize = (1 << (B_SHIFT + q));
	for (p = ((char *)bp)+sizeof(void*); p < ((char*)bp)+memSize; p++) {
		a_assert(*p == B_FILL_CHAR);
	}
	bp = (bType *)p;
	a_assert((bp->flags & ~B_MALLOCED) == B_INTEGRITY ||
				bp->flags == B_FILL_WORD);
}

/******************************************************************************/
/*
 *	verifyBallocSpace reads through the entire balloc memory space and
 *	verifies that all allocated blocks are uncorrupted and that with the
 *	exception of free list next pointers all other unallocated space is
 *	filled with B_FILL_CHAR.
 */

static void verifyBallocSpace()
{
	char	*p;
	bType	*bp;

	p = bFreeBuf;
	while (p < (bFreeBuf + bFreeSize)) {
		bp = (bType *)p;
		if (bp->u.size > 0xFFFFF) {
			p += sizeof(bp->u);
			while (p < (bFreeBuf + bFreeSize) && *p == B_FILL_CHAR) {
				p++;
			}
		} else {
			a_assert(((bp->flags & ~B_MALLOCED) == B_INTEGRITY) ||
						bp->flags == B_FILL_WORD);
			p += (sizeof(bType) + bp->u.size);
			while (p < (bFreeBuf + bFreeSize) && *p == B_FILL_CHAR) {
				p++;
			}
		}
	}
}
#endif /* B_VERIFY_CAUSES_SEVERE_OVERHEAD */

/******************************************************************************/

#else /* NO_BALLOC */
int bopen(void *buf, int bufsize, int flags)
{
	return 0;
}

/******************************************************************************/

void bclose()
{
}

/******************************************************************************/
#if UNICODE
char_t* bstrdupNoBalloc(char_t* s)
{
	if (s) {
		return wcsdup(s);
	} else {
		return wcsdup(T(""));
	}
}
#endif /* UNICODE */

/******************************************************************************/
char* bstrdupANoBalloc(char* s)
{
	char*	buf;

	if (s == NULL) {
		s = "";
	}
	buf = malloc(strlen(s)+1);
	strcpy(buf, s);
	return buf;
}

#endif /* NO_BALLOC */
/******************************************************************************/