/*
* 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) {
goahead_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 {
goahead_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) {
goahead_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 {
goahead_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);
goahead_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 */
/******************************************************************************/
