/* Copyright 1989-93 GROUPE BULL -- See license conditions in file COPYRIGHT */ /*****************************************************************************\ * * * KLONE malloc: * * A fast malloc, with optional: * * -DSTATS stats * * -DMLEAK memory lossage tracing via hash coding * * -DDEBUG debugging information * * range checking (on_line and with a dbx call) * * implies -DMALLOCDEBUG0 * * -DMALLOCDEBUG : on each malloc/free, sacns ALL the heap for correctness * * (quite slow!) * * -DMALLOCDEBUG0 : verification code compiled in, but not used till you set * * to 1 the variable KlMDcheck in a C debugger * * e.g., in gdb: set KlMDcheck=1 * * In C code, you can also call KlMallocCheckOnce() * * * * -DUSE_STANDARD_MALLOC : use the system malloc functions * * * \*****************************************************************************/ /* Why a malloc module? * Klone bases it speed on a liberal use of mallocfree, so it needs a fast * allocator. moreover it does quite a heavy use of realloc for dynamic * structures, so a bucket system where most reallocs (as long as you stay in * the same buckets) are nearly immediate is needed too. * Nowadays most modern reallocs offers these characteristics, but this realloc * is a safe bet. You can make non-Klone code liked to it use this malloc * (default), or Klone use its malloc and the other code the libc one * (with -DDO_NOT_REDEFINE_MALLOC), or both Klone and the foreign code use * the libc one (with -DUSE_STANDARD_MALLOC) * * Klone malloc offers quite a number of debugging options (watchdogs, * memory leak counts), but nothing comparable to insight or purify, which you * must use after compiling everything with -DUSE_STANDARD_MALLOC */ /* To use this module outside Klone: * you must define KlMallocError (which takes one int as argument, the * number of bytes asked for to handle allocation failures... that was true * at some time, but now a lot of defines have migrated to klone.h too. */ #include "EXTERN.h" #include #include "klone.h" /*****************************************************************************\ * USE_STANDARD_MALLOC: rest of module not used * \*****************************************************************************/ #ifdef USE_STANDARD_MALLOC /* nothing done in this case */ int KlMallocInit(){ KlInitState = 16; } /* we suppose block malloc works with 2^n chunks, less a header of the size * of a pointer. Note that this is an optimisation, no harm is done if we guess * wrong, perhaps either too frequent realloc calls (guess too short) or too * much memory consumed for KlStreamString objects */ int KlMallocChunkSize(nbytes) { int amt = 32; while (nbytes > (amt + sizeof (int *))) { amt <<= 1; } return (amt + sizeof (int *)); } KlO KlMallocStats() {return NIL;} #else /* !USE_STANDARD_MALLOC */ /*****************************************************************************\ * rest of file: MODULE USED * \*****************************************************************************/ #include "kl_list.h" #if defined(STATS) || defined (MLEAK) #include "kl_string.h" #include "kl_stream.h" #else #ifndef NULL #define NULL 0 #endif #endif /* !STATS */ #ifdef STANDARD_MALLOC /* no SBRK */ # ifndef DO_NOT_REDEFINE_MALLOC # define DO_NOT_REDEFINE_MALLOC # endif # ifndef DO_NOT_USE_SBRK # define DO_NOT_USE_SBRK # endif #endif #ifdef MLEAK #include "kl_atom.h" KlAtom *KlHashSlot(); int MLEAK_on = 0; int MLEAK_count = 0; int MLEAK_num = 0; MLEAK_break() { } /* MLEAK_num reached! */ extern KlAtom KlAtomFindNextPrefixedAtom(); extern int KlHashTableSize; #else/* !MLEAK */ #ifdef DEBUGGABLE MLEAK_break() {} #endif /* DEBUGGABLE */ #endif /* !MLEAK */ #ifdef MALLOCDEBUG0 #define MALLOCDEBUG #endif #ifdef MALLOCDEBUG #include "kl_number.h" #include "kl_list.h" #endif #ifdef VOID_MALLOC #define KlMallocType void * #else #define KlMallocType char * #endif unsigned KlM_amt_init; int KlM_bucket_init; /* BSD-4.3 derived malloc * This storage allocator trades space for speed in separate arenas for each * 2^n sizes (minus the header of 4 bytes (12 with debug on) * * The overhead on a block is at least 4 bytes. When free, this space * contains a pointer to the next free block, and the bottom two bits must * be zero. When in use, the first byte is set to MAGIC, and the second * byte is the size index. The remaining bytes are for alignment. * Whith DEBUG enabled, if the size of the block fits * in two bytes, then the top two bytes hold the size of the requested block * plus the range checking words, and the header word MINUS ONE. */ union overhead { union overhead *ov_next; /* when free */ struct { unsigned char ovu_magic; /* magic number */ unsigned char ovu_index; /* bucket # */ #ifdef DEBUG unsigned short ovu_rmagic; /* range magic number */ unsigned int ovu_size; /* actual block size */ #endif } ovu; #ifdef DOUBLE_ALIGN double dummy; /* Put union on double word boundary */ #endif /* DOUBLE_ALIGN */ #ifdef MALLOC_ALIGN /* minimum align */ char dummy_c[MALLOC_ALIGN]; #endif /* MALLOC_ALIGN */ }; /* shorthand for union fields */ #define ov_magic ovu.ovu_magic #define ov_index ovu.ovu_index #define ov_rmagic ovu.ovu_rmagic #define ov_size ovu.ovu_size /* magic markers are defined in klone.h: * #define KlMAGIC 0xef = 239 magic # on accounting info * #define KlRMAGIC 0x5555 = 21845 magic # on range info * #define KlFREED_MAGIC 0x77 block has been freed * #define KlUNINIT_MAGIC 0x88 malloced uninitialized block */ /* magic marker after data. Thus total header size */ #ifdef DEBUG #define KlRSLOP sizeof (unsigned short) #else #define KlRSLOP 0 #endif #define header_size (sizeof(union overhead) + KlRSLOP) /* Speed enhancement: we pre-compute the bucket for the lowest sizes (most used) * to avoid the iteration used otherwise. yeilds 20% more speed! * compile this file with -DBUCKET_STATS to have a dump of number of calls * per size to malloc, to tweak this number. * Most hits are <36. 64 is more than enough. After 160 no gain is shown. * MUST be between 33 and 8191, bus error otherwise! */ #define KlMAX_PRECALC_MSIZE 160 unsigned char KlPrecalcMSize[KlMAX_PRECALC_MSIZE]; /* the variable is needed to detect if malloc is called before KlMallocInit */ unsigned int KlMaxPrecalcMSize = 0; /* * KlMallocNextf[i] is the pointer to the next free block of size 2^(i+3). The * smallest allocatable block is 8 bytes. The overhead information * precedes the data area returned to the user. */ #define NBUCKETS 30 union overhead *KlMallocNextf[NBUCKETS]; long KlMallocBlocksInBucket[NBUCKETS]; extern char *KlSbrk(); static int pagesz = -1; /* page size */ static int pagebucket; /* page size bucket */ static void morecore(); #ifdef STATS /* * KlMallocNMalloc[i] is the difference between the number of mallocs and frees * for a given block size. */ unsigned int KlMallocNMalloc[NBUCKETS]; #endif char *KlMallocZoneBegin = 0, *KlMallocZoneEnd = 0; /* Some magic-number handling routines */ #ifdef DEBUG int KlIsBytes(p, size, byte) char *p; int size; int byte; { char *last = p+size; while (p < last) { if (*p++ != byte) { return 0; } } return 1; } #ifdef NO_BCOPY #define KlFillBytes(p, size, byte) memset(p, byte, size) #else /* !NO_BCOPY */ KlFillBytes(p, size, byte) char *p; int size; int byte; { char *last = p+size; while (p < last) { *p++ = byte; } } #endif /* !NO_BCOPY */ #endif /* DEBUG */ /* KlMallocCheck is a routine that you can call regularily to verify validity * of the whole malloced blocks * you MUST compile with -DMALLOCDEBUG, but not necessarily with -DDEBUG * then malloc, free & realloc will call it each time */ #ifdef MALLOCDEBUG #define KlMDbucketMax 10000 char *KlMDbuckets[KlMDbucketMax]; int KlMDbucketsSize[KlMDbucketMax]; int KlMDbucket = 0; int KlMDcount = 0; /* the number of the mallocheck */ int KlMDstop = 0; /* set this to a value to stop at */ #ifdef MALLOCDEBUG0 int KlMDcheck = 0; #else int KlMDcheck = 1; #endif int KlMallocCheck() { int i, j, sz, nblks, bucket; union overhead *op; union overhead *pop; /* here for dbx browsing */ #ifdef TRACEALL fprintf(stderr, "KlMDcount = %d\n", KlMDcount); #endif KlMDcount++; if (KlMDstop && KlMDstop == KlMDcount) stop_if_in_dbx("Malloc number KlMDstop reached"); if (!KlMDcheck) return 0; for (i = 0; i < KlMDbucket; i++) { sz = KlMDbucketsSize[i]; bucket = 0; while (sz > (1 << (bucket + 3))) bucket++; if (sz < pagesz) { nblks = pagesz / sz; } else { nblks = 1; } for (j = 0; j < nblks; j++) { op = (union overhead *) (KlMDbuckets[i] + j * sz); if (((int) (op->ovu.ovu_magic)) == KlMAGIC) { /* in use */ char *why = 0; if (op->ovu.ovu_index != bucket) { why = "bad bucket index in malloced block"; } #ifdef DEBUG if (op->ovu.ovu_rmagic != KlRMAGIC) { why = "starting magic number overwritten"; } if (*((unsigned short *) ((caddr_t) (op + 1) + op->ovu.ovu_size)) != KlRMAGIC) { why = "end magic number overwritten"; } /* size */ if (op->ovu.ovu_size >= (unsigned int) sz) { why = "size too big for bucket!"; } #endif /* DEBUG */ if (why) { KlMallocCheckError(op, why); return 1; } } else { /* free, follow chain */ #ifdef DEBUG /* check magic numbers */ char *cp = (((char *) op) + sizeof(*op)); if (!KlIsBytes(cp, sz - sizeof(*op), KlFREED_MAGIC)) { KlMallocCheckError(cp - sizeof(union overhead), "freed block data modified"); return 1; } #endif /* DEBUG */ pop = op; while (op) { if (((char *) op) >= KlMallocZoneBegin && ((char *) op) < KlMallocZoneEnd) { op = op->ov_next; } else { KlMallocCheckError(op, "next free block out of bounds"); return 1; } } } } } return 0; } int KlMallocCheckOnce() { int KlMDcheck_old = KlMDcheck; int res; KlMDcheck = 1; res = KlMallocCheck(); KlMDcheck = KlMDcheck_old; return res; } /* what to do in case of memory corruption */ KlMallocCheckError(op, why) char *op; char *why; { fprintf(stderr, "KlMallocCheck: corruption detected! Block 0x%x (obj at 0x%x)\n", op, op + sizeof(union overhead)); fprintf(stderr, "Problem: %s\nKlMDcount = %d (to be used for for KlMDstop)\n", why, KlMDcount); stop_if_in_dbx(why); } /* inconditional check, for use from debugger */ int KlMC() { int oldKlMDcheck = KlMDcheck; int res; KlMDcheck = 1; res = KlMallocCheck(); KlMDcheck = oldKlMDcheck; return res; } /* routine to set/unset KlMDcheck and perform a check (no args) from klone */ KlO KlMDCheckKl(argc, argv) int argc; KlO *argv; { if (argc) { /* set KlMDcheck to value */ if (KlFalseP(argv[0]) || (KlIsANumber(argv[0]) && ((KlNumber)argv[0])->number == 0)) { KlMDcheck = 0; return NIL; } else { KlMDcheck = 1; return TRU; } } else { /* no args, perform a check */ if (KlMC()) { return TRU; } else { return NIL; } } } #endif /* MALLOCDEBUG */ #ifndef DO_NOT_USE_SBRK #define KlSbrk(n) sbrk(n) #else /* DO_NOT_USE_SBRK */ #ifndef DO_NOT_REDEFINE_MALLOC error=DO_NOT_REDEFINE_MALLOC_must_be_defined_if_DO_NOT_USE_SBRK_is_defined; #endif /* for OSes with buggy malloc, we cannot use sbrk directly, so we just waste * memory... */ /* TO_DO: be smart, allocate a big arena, and do the splitting ourselves */ char * KlSbrk(amt) int amt; { char *op = (char *) malloc(amt); if (op < KlMallocZoneBegin) KlMallocZoneBegin = op; if (op + amt > KlMallocZoneEnd) KlMallocZoneEnd = op + amt; return op; } #endif /* DO_NOT_USE_SBRK */ /* * Init malloc lists: to be called AT THE TOP of your program!!! * setup page size and align break pointer so all data will be page aligned. */ KlMallocInit() { union overhead *op; int bucket; unsigned amt, n, nbytes, precalc_index; if (pagesz == -1) { /* do not do it twice */ bzero(KlMallocNextf, NBUCKETS * sizeof(union overhead *)); bzero(KlMallocBlocksInBucket, NBUCKETS * sizeof(long)); #ifdef STATS bzero(KlMallocNMalloc, NBUCKETS * sizeof(unsigned int)); #endif pagesz = n = getpagesize(); op = (union overhead *) KlSbrk(0); #ifndef DO_NOT_USE_SBRK KlMallocZoneBegin = (char *) op; #endif n = n - sizeof(*op) - (((Int) op) & (n - 1)); if ((Int) n < 0) n += pagesz; if (n) { if ((char *) KlSbrk(n) == (char *) -1) KlMallocError(1); } /* compute minimal buckets size (that holds header + 1 byte) */ bucket = 0, amt = 8; while (amt <= header_size) bucket++, amt <<= 1; KlM_amt_init = amt; KlM_bucket_init = bucket; /* now compute minimal bucket for non pre-calc sizes */ while (KlMAX_PRECALC_MSIZE > (amt - header_size)) bucket++, amt <<= 1; /* fill up precalc buckets sizes */ bucket = KlM_bucket_init; amt = KlM_amt_init; precalc_index = 0; while (pagesz > amt) { if (precalc_index < KlMAX_PRECALC_MSIZE) { nbytes = amt - header_size; while (precalc_index <= nbytes && precalc_index < KlMAX_PRECALC_MSIZE ) KlPrecalcMSize[precalc_index++] = bucket; } amt <<= 1; bucket++; } KlMaxPrecalcMSize = KlMAX_PRECALC_MSIZE; pagebucket = bucket; KlInitState = 16; } #ifndef USE_STANDARD_MALLOC #ifdef DEBUG { /* fill magic word markers */ char *p = (char *) &KlFREED_MAGIC_PTR; char *q = (char *) &KlUNINIT_MAGIC_PTR; char *end = p + (sizeof(void *) / sizeof(char)); for (;p < end; p++, q++) { *p = KlFREED_MAGIC; *q = KlUNINIT_MAGIC; } } #endif /* DEBUG */ #endif /* !USE_STANDARD_MALLOC */ } /* a stat package outputting the sizes asked for in a running program */ #ifdef BUCKET_STATS #define bucket_stats_size 1000 /* multiple of 5 */ int bucket_stats[bucket_stats_size]; Klbucket_stat(n) unsigned int n; { if (n < bucket_stats_size) bucket_stats[n]++; } Klbucket_print() { int i; for (i = bucket_stats_size-1; i >=4 ; i-=5) fprintf(stderr, " |% 4d :%6d |% 4d :%6d |% 4d :%6d |% 4d :%6d |% 4d :%6d\n" ,i , bucket_stats[i] ,i-1 , bucket_stats[i-1] ,i-2 , bucket_stats[i-2] ,i-3 , bucket_stats[i-3] ,i-4 , bucket_stats[i-4] ); } KlEnd(n) int n;{Klbucket_print();} #else /* !BUCKET_STATS */ #define Klbucket_stat(n) #endif /* !BUCKET_STATS */ /* * Convert amount of memory requested into closest block size stored in * hash buckets which satisfies request. Account for space used per block * for accounting. */ KlMallocType KlMalloc(nbytes) unsigned nbytes; { union overhead *op; int bucket; unsigned int amt; #ifdef DEBUG char *result; #endif Klbucket_stat(nbytes); #ifdef MALLOCDEBUG KlMallocCheck(); #endif #ifdef DEBUG if ((nbytes > 10000000) /* mallocs of more than 10M */ # ifdef DEBUG2 || (nbytes == 0) # endif ) { fprintf(stderr, "MALLOC: trying to allocate %d bytes\n", nbytes); stop_if_in_dbx("malloc of 0 or huge number of bytes"); } #endif /* DEBUG */ if (nbytes < KlMaxPrecalcMSize) { bucket = KlPrecalcMSize[nbytes]; } else { if (((int) nbytes) <= (pagesz - header_size)) { amt = KlM_amt_init; /* size of first bucket */ bucket = KlM_bucket_init; } else if (pagesz == -1) { /* malloc called before init */ /* may happen in some systems that call malloc from _main */ /* by doing the test here we reduce overhead */ KlMallocInit(); return KlMalloc(nbytes); } else { /* big chunk */ amt = pagesz; bucket = pagebucket; } while (nbytes > (amt - header_size)) { /* find bucket */ amt <<= 1; bucket++; } } /* if no hash bucket, allocates more memory */ if ((op = KlMallocNextf[bucket]) == NULL) { morecore(bucket); if ((op = KlMallocNextf[bucket]) == NULL) /* TO_DO: compact space? */ KlMallocError(nbytes); } /* remove from linked list */ KlMallocNextf[bucket] = op->ov_next; op->ovu.ovu_index = bucket; #ifdef STATS KlMallocNMalloc[bucket]++; #endif #ifdef DEBUG op->ovu.ovu_size = (nbytes + KlRSLOP - 1) & ~(KlRSLOP - 1); /* fill data with unitialized values */ KlFillBytes((char *) (op + 1), op->ovu.ovu_size, KlUNINIT_MAGIC); /* Record allocated size of block and bound space with magic numbers. */ op->ovu.ovu_magic = KlMAGIC; op->ovu.ovu_rmagic = KlRMAGIC; *((unsigned short *) ((caddr_t) (op + 1) + op->ovu.ovu_size)) = KlRMAGIC; ASSERT(((char *) (op + 1))); #else # ifdef MALLOCDEBUG op->ovu.ovu_magic = KlMAGIC; # endif #endif /* DEBUG */ #ifndef MLEAK #ifdef DEBUG result = ((char *) (op + 1)); return result; #else return ((char *) (op + 1)); #endif /* DEBUG */ #else /* MLEAK */ if (MLEAK_on) { char name[20]; KlAtom atom; char *ptr = (char *) (op + 1); sprintf(name + 1, "0x%x", ptr); name[0] = '\r'; MLEAK_on = 0; atom = KlIntern(name); MLEAK_on = 1; atom->c_val = (KlO)++ MLEAK_count; if (MLEAK_num == MLEAK_count) MLEAK_break(); return ptr; } else { return ((char *) (op + 1)); } #endif /* MLEAK */ } /* mallocs but from a specified bucket (faster) */ KlMallocType KlMallocBucket(bucket) int bucket; { union overhead *op; int n; #ifdef DEBUG char *result; unsigned int nbytes = KlMallocSizeOfBucket(bucket); #endif #ifdef MALLOCDEBUG KlMallocCheck(); #endif /* if no hash bucket, allocates more memory */ if (!(op = KlMallocNextf[bucket])) { morecore(bucket); if (!(op = KlMallocNextf[bucket])) /* TO_DO: compact space? */ KlMallocError(KlMallocSizeOfBucket(bucket)); } KlMallocNextf[bucket] = op->ov_next; /* remove from linked list */ op->ovu.ovu_index = bucket; #ifdef STATS KlMallocNMalloc[bucket]++; #endif #ifdef DEBUG op->ovu.ovu_size = (nbytes + KlRSLOP - 1) & ~(KlRSLOP - 1); /* fill data with unitialized values */ KlFillBytes((char *) (op + 1), op->ovu.ovu_size, KlUNINIT_MAGIC); /* Record allocated size of block and bound space with magic numbers. */ op->ovu.ovu_magic = KlMAGIC; op->ovu.ovu_rmagic = KlRMAGIC; *((unsigned short *) ((caddr_t) (op + 1) + op->ovu.ovu_size)) = KlRMAGIC; ASSERT(((char *) (op + 1))); #else /* !DEBUG */ # ifdef MALLOCDEBUG op->ovu.ovu_magic = KlMAGIC; # endif #endif /* !DEBUG */ #ifndef MLEAK #ifdef DEBUG result = ((char *) (op + 1)); return result; #else return ((char *) (op + 1)); #endif /* DEBUG */ #else /* MLEAK */ if (MLEAK_on) { char name[20]; KlAtom atom; char *ptr = (char *) (op + 1); sprintf(name + 1, "0x%x", ptr); name[0] = '\r'; MLEAK_on = 0; atom = KlIntern(name); MLEAK_on = 1; atom->c_val = (KlO)++ MLEAK_count; if (MLEAK_num == MLEAK_count) MLEAK_break(); return ptr; } else { return ((char *) (op + 1)); } #endif /* MLEAK */ } /* * Allocate more memory to the indicated bucket. */ static void morecore(bucket) int bucket; { union overhead *op; int sz; /* size of desired block */ int amt; /* amount to allocate */ int nblks; /* how many blocks we get */ sz = 1 << (bucket + 3); if (sz < pagesz) { amt = pagesz; nblks = amt / sz; } else { amt = sz + pagesz; nblks = 1; } op = (union overhead *) KlSbrk(amt); #ifdef DEBUG KlFillBytes((char *) (op), amt, KlFREED_MAGIC); #endif #ifndef DO_NOT_USE_SBRK KlMallocZoneEnd = ((char *) op) + amt; #endif #ifdef MALLOCDEBUG ASSERT(KlMDbucket < KlMDbucketMax); KlMDbuckets[KlMDbucket] = (char *) op; KlMDbucketsSize[KlMDbucket] = sz; KlMDbucket++; #endif /* no more room! */ if ((Int) op == -1) return; KlMallocBlocksInBucket[bucket] += nblks; /* Add new memory allocated to that on free list for this hash bucket. */ KlMallocNextf[bucket] = op; while (--nblks > 0) { op->ov_next = (union overhead *) ((caddr_t) op + sz); op = (union overhead *) ((caddr_t) op + sz); } op->ov_next = NULL; } #ifndef NO_VOID void #endif KlFree(cp) #ifdef VOID_MALLOCARG void *cp; #else char *cp; #endif { int size; union overhead *op; #ifdef MALLOCDEBUG KlMallocCheck(); #endif #ifdef MLEAK if (KlHashTableSize) { char name[20]; KlAtom *patom; sprintf(name + 1, "0x%x", cp); name[0] = '\r'; patom = KlHashSlot(name); if (*patom) (*patom)->c_val = 0; } #endif /* MLEAK */ #ifdef DEBUG2 ASSERT(cp != NULL); #endif /* DEBUG2 */ if (!cp) return; op = (union overhead *) ((caddr_t) cp - sizeof(union overhead)); #ifdef MALLOCDEBUG ASSERT(op->ovu.ovu_magic != KlFREED_MAGIC); /* freeing a freed block! */ #endif ASSERT(op->ovu.ovu_magic == KlMAGIC); /* make sure it was in use */ /* make sure start marker was not overwritten */ ASSERT(op->ovu.ovu_rmagic == KlRMAGIC); /* make sure data was not written too far (check end marker) */ ASSERT(*(unsigned short *)((caddr_t)(op + 1)+op->ovu.ovu_size)==KlRMAGIC); size = op->ovu.ovu_index; ASSERT(size < NBUCKETS); #ifdef MALLOCDEBUG /* we erase all the data zone, to detect earlier re-using a freed block */ KlFillBytes(cp, (8<<(size)) - (sizeof(*op)), KlFREED_MAGIC); #endif /* DEBUG */ op->ov_next = KlMallocNextf[size]; KlMallocNextf[size] = op; #ifdef STATS KlMallocNMalloc[size]--; #endif } /* * Simple realloc without storage compaction * can be handled NULL pointer, but not 0 size... */ KlMallocType KlRealloc(cp, nbytes) #ifdef VOID_MALLOCARG void *cp; #else char *cp; #endif unsigned nbytes; { unsigned int onb, i; union overhead *op; char *res; #ifdef MALLOCDEBUG KlMallocCheck(); ASSERT(nbytes); #endif if (!cp) return KlMalloc(nbytes); op = (union overhead *) ((caddr_t) cp - sizeof(union overhead)); i = op->ovu.ovu_index; onb = 1 << (i + 3); if (onb < pagesz) onb -= header_size; else onb += pagesz - header_size; /* avoid the copy if same size block */ if (i) { i = 1 << (i + 2); if (i < pagesz) i -= header_size; else i += pagesz - header_size; } if (nbytes <= onb && nbytes > i) { #ifdef DEBUG op->ovu.ovu_size = (nbytes + KlRSLOP - 1) & ~(KlRSLOP - 1); *((unsigned short *) ((caddr_t) (op + 1) + op->ovu.ovu_size)) = KlRMAGIC; #endif return (cp); } else { if ((res = KlMalloc(nbytes)) == NULL) return (NULL); ASSERT(cp != res); bcopy(cp, res, (nbytes < onb) ? nbytes : onb); KlFree(cp); return (res); } } KlMallocType KlCalloc(nelem, elsize) unsigned nelem, elsize; { char *result = KlMalloc(nelem * elsize); if (result) bzero(result, nelem * elsize); return result; } /*****************************************************************************\ * misc utilities * \*****************************************************************************/ /* returns room in current chunk * we set up things in debug mode so that all the chunk can be allocated * without trashing end markers */ int KlMallocedSize(cp) char *cp; { unsigned int onb, i; union overhead *op; if (!cp) return 0; op = (union overhead *) ((caddr_t) cp - sizeof(union overhead)); i = op->ovu.ovu_index; onb = 1 << (i + 3); if (onb < pagesz) onb -= header_size; else onb += pagesz - header_size; #ifdef DEBUG /* set Recorded allocated size to max */ op->ovu.ovu_size = (onb + KlRSLOP - 1) & ~(KlRSLOP - 1); op->ovu.ovu_magic = KlMAGIC; op->ovu.ovu_rmagic = KlRMAGIC; *((unsigned short *) ((caddr_t) (op + 1) + op->ovu.ovu_size)) = KlRMAGIC; #endif return onb; } /* same but checks args, returns 0 if invalid */ int KlMallocedSizeAndCheck(cp) char *cp; { if (cp >= KlMallocZoneBegin && cp < KlMallocZoneEnd && !(((Int) cp) % sizeof(union overhead)) && (((union overhead *) ((caddr_t) cp - sizeof(union overhead))) ->ovu.ovu_index) < NBUCKETS) return KlMallocedSize(cp) + sizeof(union overhead); else return 0; } /* KlMallocChunkSize * returns the number to malloc to maximize room */ int KlMallocChunkSize(nbytes) unsigned int nbytes; { union overhead *op; unsigned amt; if (nbytes < KlMaxPrecalcMSize) { return (8<<(KlPrecalcMSize[nbytes])) - header_size; } else { if (((int) nbytes) <= (pagesz - header_size)) { amt = KlM_amt_init; /* size of first bucket */ } else { amt = pagesz; } while (nbytes > (amt - header_size)) { /* find bucket */ amt <<= 1; } return amt - header_size; } } /* KlMallocBucketOfSize * returns the bucket number holding a size */ int KlMallocBucketOfSize(nbytes) int nbytes; { union overhead *op; int bucket; unsigned amt; if (nbytes < KlMaxPrecalcMSize) { return KlPrecalcMSize[nbytes]; } else { if (((int) nbytes) <= (pagesz - header_size)) { amt = KlM_amt_init; /* size of first bucket */ bucket = KlM_bucket_init; } else { amt = pagesz; bucket = pagebucket; } while (nbytes > (amt - header_size)) { /* find bucket */ amt <<= 1; bucket++; } return bucket; } } int KlMallocSizeOfBucket(bucket) int bucket; { union overhead *op; return (8<<(bucket)) - header_size; } /* *:memory * returns a triplet: used_bytes, free_bytes, and * a list of triplets: (bucket_size, used_blocks, free_blocks) */ KlO KlMallocStats() { int i, j; union overhead *p; int totfree = 0, totused = 0; long used[NBUCKETS], free[NBUCKETS], size[NBUCKETS]; KlList res, subres; int Nbuckets = 0; for (i = 0; i < NBUCKETS; i++) { size[i] = (long) (1 << (i + 3)); for (j = 0, p = KlMallocNextf[i]; p; p = p->ov_next, j++); free[i] = (long) j; totfree += j * (1 << (i + 3)); used[i] = (long) KlMallocBlocksInBucket[i] - free[i]; totused += used[i] * (1 << (i + 3)); } /* make result */ for (i = NBUCKETS-1; i >= 0; i--) { if (KlMallocBlocksInBucket[i]) { Nbuckets = i + 1; break; } } res = KlListMakeV(3, KlNumberMake(totused), KlNumberMake(totfree), subres = KlListNMake(Nbuckets)); for (i = 0; i < Nbuckets; i++) { KlListStore(subres, i, KlListTripletMake(KlNumberMake(size[i]), KlNumberMake(used[i]), KlNumberMake(free[i]))); } return (KlO) res; } /************\ * * * DBX tools * * * \************/ #ifdef DEBUG /* * verify if pointer is still valid */ int KlVerifyMalloc(cp) char *cp; { int size; union overhead *op; if (cp == NULL) return 0; op = (union overhead *) ((caddr_t) cp - sizeof(union overhead)); ASSERT(op->ovu.ovu_magic == KlMAGIC); /* make sure it was in use */ if (op->ovu.ovu_magic != KlMAGIC) return 0; /* sanity */ ASSERT(op->ovu.ovu_rmagic ==KlRMAGIC); ASSERT(*((unsigned short *)((caddr_t)(op+1)+op->ovu.ovu_size))==KlRMAGIC); size = op->ovu.ovu_index; ASSERT(size < NBUCKETS); return 1; } #endif /* DEBUG */ #ifdef MLEAK /*****************************************************************************\ * * * malloc-leak tracing: (colas: uses the hash table!) * * * * Under dbx: * * * * Turn tracing on by setting MLEAK_on to 1 * * When malloced blocks are done, reset it to 0 * * then MLEAK_print(file,n) prints the nth first (if any) traced blocks * * remain allocated then. (file=0 means stdout) * * * * then by re-executing the program and setting MLEAK_num to the desired * * number and setting a beakpoint in MLEAK_break, bdx will halt when the * * desired block will be allocated * * * * Exemple of test file, to test code segment (foo) * * * * (initialisations) * * (foo) * * (setq mleak 1) * * (foo) * * (setq mleak 0) * * (foo) * * (mleak-print) * * (break) * * then under gdb, restart exactly, but before, do a: * * set MLEAK_num= * * * \*****************************************************************************/ typedef struct _KlMleakCell { int number; char *object_addr; } *KlMleakCell; #define KlMleakCellSize 100 static struct _KlMleakCell klmltab[KlMleakCellSize]; static int KlMleakCellCompare(a, b) KlMleakCell a, b; { return (a->number - b->number); } static int KlMleakCellMax(tab, size) KlMleakCell tab; int size; { int i; int max = 0; for (i = 0; i< size; i++) { if (tab[i].number > max) { max = tab[i].number; } } return max; } MLEAK_print(filename, n) char *filename; int n; { int i = 0, old_MLEAK_on = MLEAK_on; KlAtom atom; FILE *ptr; KlStream stream; int curcell = 0; int max_dirty = 1; int max_index; MLEAK_on = 0; if ((!filename) || filename[0] == '\0') { filename = NULL; ptr = NULL; stream = KlStdout; } else { ptr = fopen(filename, "w+"); stream = KlStreamMake(ptr, 2, filename); } /* collect entries */ KlAtomFindNextPrefixedAtom('\0'); while ((atom = KlAtomFindNextPrefixedAtom('\r')) && i++ < n) { int slot; if (curcell >= KlMleakCellSize) { if (max_dirty) { max_index = KlMleakCellMax(klmltab, KlMleakCellSize); max_dirty = 0; } if (((int) atom->c_val) < klmltab[max_index].number) { max_dirty = 1; slot = max_index; } else { curcell++; continue; } } else { slot = curcell; } klmltab[slot].number = (int) atom->c_val; klmltab[slot].object_addr = atom->p_name + 1; curcell++; } /* sort entries */ qsort(klmltab, Min(KlMleakCellSize, curcell), sizeof(struct _KlMleakCell), KlMleakCellCompare); /* print entries */ fprintf((ptr ? ptr : stdout), "\n"); if (curcell > KlMleakCellSize) { fprintf((ptr ? ptr : stdout), "Too many leaks (%d), printing only the first %d ones\n", curcell, KlMleakCellSize); curcell = KlMleakCellSize; } for (i = 0; i < curcell; i++) { KlO obj; union overhead *op; fprintf((ptr ? ptr : stdout), "%2d th malloc at %s remains", klmltab[i].number, klmltab[i].object_addr); sscanf(klmltab[i].object_addr, "0x%x", &obj); op = (union overhead *) (((caddr_t) obj) - sizeof(union overhead)); fprintf((ptr ? ptr : stdout), " bucket#%d", op->ovu.ovu_index); #ifdef DEBUG fprintf((ptr ? ptr : stdout), " size %3d bytes", op->ovu.ovu_size); #endif if (KlObjectIsValid(obj)) { fprintf((ptr ? ptr : stdout), " of type: %s\n = ", KlTypeCName(obj->type)); KlSend_print(obj, stream); } fprintf((ptr ? ptr : stdout), "\n"); } if (filename) fclose(ptr); MLEAK_on = old_MLEAK_on; } KlO MLEAK_printKl() { MLEAK_print(0, 100000); return NIL; } #endif /* MLEAK */ #ifdef DEBUG /* KlDoMallocBlocks * applyies function to each allocated block * as f(ptr, size, chunk_size) */ int KlDoMallocBlocks(f) int (*f)(); { int i, j, sz, nblks, bucket; union overhead *op; union overhead *pop; /* here for dbx browsing */ for (i = 0; i < KlMDbucket; i++) { sz = KlMDbucketsSize[i]; bucket = 0; while (sz > (1 << (bucket + 3))) bucket++; if (sz < pagesz) { nblks = pagesz / sz; } else { nblks = 1; } for (j = 0; j < nblks; j++) { op = (union overhead *) (KlMDbuckets[i] + j * sz); if (((int) (op->ovu.ovu_magic)) == KlMAGIC) { /* in use */ char *why = 0; CFAPPLY(f, (((char *) (op + 1)), op->ovu.ovu_size, sz)); } } } return 0; } #endif /* DEBUG */ #endif /* !USE_STANDARD_MALLOC */