From c1cdaa0ce8017b075487e6670f89eb4e715258ea Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Wed, 27 Oct 1999 12:50:33 +0000 Subject: Patch from Emmanuel Raguet and Eric Valette to add a port of the GoAhead web server (httpd) to the RTEMS build tree. They have successfully used this BSP on i386/pc386 and PowerPC/mcp750. Mark and Joel spoke with Nick Berliner on 26 Oct 1999 about this port and got verbal approval to include it in RTEMS distributions. --- c/src/libnetworking/rtems_webserver/balloc.c | 836 +++++++++++++++++++++++++++ 1 file changed, 836 insertions(+) create mode 100644 c/src/libnetworking/rtems_webserver/balloc.c (limited to 'c/src/libnetworking/rtems_webserver/balloc.c') diff --git a/c/src/libnetworking/rtems_webserver/balloc.c b/c/src/libnetworking/rtems_webserver/balloc.c new file mode 100644 index 0000000000..20612ed148 --- /dev/null +++ b/c/src/libnetworking/rtems_webserver/balloc.c @@ -0,0 +1,836 @@ +/* + * 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 +#include + +#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 */ +/******************************************************************************/ + -- cgit v1.2.3