URL
https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk
Subversion Repositories openrisc_me
[/] [openrisc/] [trunk/] [rtos/] [rtems/] [c/] [src/] [libnetworking/] [rtems_webserver/] [balloc.c] - Rev 30
Go to most recent revision | Compare with Previous | Blame | View Log
/* * 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 */ /******************************************************************************/
Go to most recent revision | Compare with Previous | Blame | View Log