/*
 * balloc.c -- Block allocation module
 *
 * Copyright (c) GoAhead Software Inc., 1995-2000. All Rights Reserved.
 *
 * See the file "license.txt" for usage and redistribution license requirements
 *
 * $Id: balloc.c,v 1.2 2001/12/06 16:28:24 bporter Exp $
 */

/******************************** 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 module 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

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

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

#ifndef NO_BALLOC
/********************************* Defines ************************************/

/*
 *	Define B_STATS if you wish to track memory block and stack usage
 */
#ifdef 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	times;								/* Count of alloc attempts */
	long	largest;							/* largest allocated here */
	int		q;
} 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 = 0;		/* Max block entry */
static int			 	bStatsFilesMax = 0;		/* Max file entry */
static int 				bStatsMemInUse = 0;		/* Memory currently in use */
static int 				bStatsBallocInUse = 0;	/* Memory currently balloced */
static int 				bStatsMemMax = 0;		/* Max memory ever used */
static int 				bStatsBallocMax = 0;	/* Max memory ever balloced */
static void				*bStackMin = (void*) -1;/* Miniumum stack position */
static void				*bStackStart;			/* Starting stack position */
static int 				bStatsMemMalloc = 0;	/* Malloced memory */
#endif /* B_STATS */

/*
 *	ROUNDUP4(size) returns the next higher integer value of size that is 
 *	divisible by 4, or the value of size if size is divisible by 4.
 *	ROUNDUP4() is used in aligning memory allocations on 4-byte boundaries.
 *
 *	Note:  ROUNDUP4() is only required on some operating systems (IRIX).
 */

#define ROUNDUP4(size) ((size) % 4) ? (size) + (4 - ((size) % 4)) : (size)

/********************************** 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 */
static int				bopenCount = 0;			/* Num tasks using balloc */

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

#ifdef 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 (defined (B_FILL) || defined (B_VERIFY_CAUSES_SEVERE_OVERHEAD))
static void bFillBlock(void *buf, int bufsize);
#endif

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

static int ballocGetSize(int size, int *q);

/********************************** 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;

#ifdef BASTARD_TESTING
	srand(time(0L));
#endif /* BASTARD_TESTING */

/*
 *	If bopen already called by a shared process, just increment the count
 *	and return;
 */
	if (++bopenCount > 1) {
		return 0;
	}

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

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

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

void bclose()
{
#ifdef B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	if (--bopenCount <= 0 && !(bFlags & B_USER_BUF)) {
		free(bFreeBuf);
		bopenCount = 0;
	}
}

/******************************************************************************/
/*
 *	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;

/*
 *	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;
		}
	}
#ifdef B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	if (size < 0) {
		return NULL;
	}

#ifdef BASTARD_TESTING
	if (rand() == 0x7fff) {
		return NULL;
	}
#endif /* BASTARD_TESTING */


	memSize = ballocGetSize(size, &q);

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

		} else {
			traceRaw(T("B: malloc failed\n"));
			return NULL;
		}

/*
 *		the u.size is the actual size allocated for data
 */
		bp->u.size = memSize - sizeof(bType);
		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;
#ifdef B_VERIFY_CAUSES_SEVERE_OVERHEAD
		verifyFreeBlock(bp, q);
#endif
#if (defined (B_FILL) || defined (B_VERIFY_CAUSES_SEVERE_OVERHEAD))
		bFillBlock(bp, memSize);
#endif
		bp->u.size = memSize - sizeof(bType);
		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;
#ifdef B_VERIFY_CAUSES_SEVERE_OVERHEAD
			verifyFreeBlock(bp, q);
#endif
			bFreeNext += memSize;
			bFreeLeft -= memSize;
#if (defined (B_FILL) || defined (B_VERIFY_CAUSES_SEVERE_OVERHEAD))
			bFillBlock(bp, memSize);
#endif
			bp->u.size = memSize - sizeof(bType);
			bp->flags = 0;

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

		} else {
			traceRaw(T("B: malloc failed\n"));
			return NULL;
		}
	}

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

/*
 *	The following is a good place to put a breakpoint when trying to reduce
 *	determine and reduce maximum memory use.
 */
#if 0
#ifdef B_STATS
	if (bStatsBallocInUse == bStatsBallocMax) {
		bstats(0, NULL);
	}
#endif
#endif
	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		q, memSize;

#ifdef B_VERIFY_CAUSES_SEVERE_OVERHEAD
	verifyBallocSpace();
#endif
	bp = (bType*) ((char*) mp - sizeof(bType));

	a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);

	if ((bp->flags & B_INTEGRITY_MASK) != B_INTEGRITY) {
		return;
	}

	memSize = ballocGetSize(bp->u.size, &q);

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

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

	bp->flags = B_FILL_WORD;
}

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

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

/******************************************************************************/
#ifdef 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 the allocated memory already has enough room just return the previously
 *	allocated address.
 */
	if (bp->u.size >= newsize) {