--- ray/src/common/malloc.c 1990/09/25 17:14:04 1.1 +++ ray/src/common/malloc.c 1990/11/13 14:39:05 1.10 @@ -7,26 +7,42 @@ static char SCCSid[] = "$SunId$ LBL"; /* * Fast malloc for memory hogs and VM environments. * Performs a minimum of searching through free lists. - * bmalloc() doesn't keep track of free lists -- it's basically - * just a buffered call to sbrk(). - * bfree() puts memory from any source into malloc() free lists. * malloc(), realloc() and free() use buckets * containing blocks in powers of two, similar to CIT routines. + * bfree() puts memory from any source into malloc free lists. + * bmalloc() doesn't keep track of free lists -- it's usually + * just a buffered call to sbrk(2). However, bmalloc will + * call mscrounge() if sbrk fails. + * mscrounge() returns whatever free memory it can find to satisfy the + * request along with the number of bytes (modified). * * Greg Ward Lawrence Berkeley Laboratory */ +#include + +#ifdef MSTATS +#include +static unsigned b_nalloced = 0; +static unsigned b_nfreed = 0; +static unsigned b_nscrounged = 0; +static unsigned m_nalloced = 0; +static unsigned m_nfreed = 0; +static unsigned m_nwasted = 0; +#else #define NULL 0 +#endif #ifndef ALIGN #define ALIGN int /* align type */ #endif #define BYTES_WORD sizeof(ALIGN) +#define MAXINCR (1<<16) /* largest sbrk(2) increment */ + #ifdef NOVMEM #define getpagesize() BYTES_WORD #endif - /* malloc free lists */ typedef union m_head { union m_head *next; @@ -39,20 +55,50 @@ typedef union m_head { static M_HEAD *free_list[NBUCKETS]; +static char DUMMYLOC[BYTES_WORD]; + char * +mscrounge(np) /* search free lists to satisfy request */ +register unsigned *np; +{ + char *p; + register int bucket; + register unsigned bsiz; + + for (bucket = FIRSTBUCKET, bsiz = 1<= *np) { + *np = bsiz+sizeof(M_HEAD); + p = (char *)free_list[bucket]; + free_list[bucket] = free_list[bucket]->next; +#ifdef MSTATS + b_nscrounged += *np; +#endif + return(p); + } + *np = 0; + return(NULL); +} + + +char * bmalloc(n) /* allocate a block of n bytes, sans header */ register unsigned n; { extern char *sbrk(); - static int pagesz = 0; - static int amnt; + static unsigned pagesz = 0; + static unsigned amnt; static char *bpos; - static int nrem; + static unsigned nrem; + unsigned thisamnt; register char *p; +#ifdef MSTATS + b_nalloced += n; +#endif if (pagesz == 0) { /* initialize */ - amnt = pagesz = getpagesize(); + pagesz = amnt = getpagesize(); nrem = (int)sbrk(0); /* page align break */ nrem = pagesz - (nrem&(pagesz-1)); bpos = sbrk(nrem); /* word aligned! */ @@ -63,17 +109,25 @@ register unsigned n; n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */ if (n > nrem) { /* need more core */ - if (n > amnt) /* increase amount */ - amnt = (n+(pagesz-1))&~(pagesz-1); - p = sbrk(amnt); - if ((int)p == -1) - return(NULL); - if (p != bpos+nrem) { /* someone called sbrk()! */ - bfree(bpos, nrem); - bpos = p; - nrem = amnt; + if (n > amnt) { /* big chunk */ + thisamnt = (n+(pagesz-1))&~(pagesz-1); + if (thisamnt <= MAXINCR) /* increase amnt */ + amnt = thisamnt; } else - nrem += amnt; + thisamnt = amnt; + p = sbrk(thisamnt); + if ((int)p == -1) { /* uh-oh, ENOMEM */ + thisamnt = n; /* search free lists */ + p = mscrounge(&thisamnt); + if (p == NULL) /* we're really out */ + return(NULL); + } + if (p != bpos+nrem) { /* not an increment */ + bfree(bpos, nrem); /* free what we have */ + bpos = p; + nrem = thisamnt; + } else /* otherwise tack on */ + nrem += thisamnt; } p = bpos; bpos += n; /* advance */ @@ -83,27 +137,30 @@ register unsigned n; bfree(p, n) /* free n bytes of random memory */ -char *p; -unsigned n; +register char *p; +register unsigned n; { - register M_HEAD *mp; register int bucket; register unsigned bsiz; - /* find largest bucket */ - bucket = 0; - for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1) - bucket++; - mp = (M_HEAD *)p; - while (bucket > FIRSTBUCKET) { - bsiz >>= 1; - bucket--; - if (n < bsiz+sizeof(M_HEAD)) /* nothing for this bucket */ - continue; - mp->next = free_list[bucket]; - free_list[bucket] = mp; - (char *)mp += bsiz+sizeof(M_HEAD); - n -= bsiz+sizeof(M_HEAD); + +#ifdef MSTATS + b_nfreed += n; +#endif + /* align pointer */ + bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1)); + if (bsiz < BYTES_WORD) { + p += bsiz; + n -= bsiz; } + /* fill big buckets first */ + for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1); + bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1) + if (n >= bsiz+sizeof(M_HEAD)) { + ((M_HEAD *)p)->next = free_list[bucket]; + free_list[bucket] = (M_HEAD *)p; + p += bsiz+sizeof(M_HEAD); + n -= bsiz+sizeof(M_HEAD); + } } @@ -111,47 +168,59 @@ char * malloc(n) /* allocate n bytes of memory */ unsigned n; { + extern int errno; register M_HEAD *mp; register int bucket; register unsigned bsiz; - - bucket = FIRSTBUCKET; - for (bsiz = 1<= n) + break; + if (bucket >= NBUCKETS) { + errno = EINVAL; + return(NULL); + } +#ifdef MSTATS + m_nalloced += bsiz + sizeof(M_HEAD); + m_nwasted += bsiz + sizeof(M_HEAD) - n; +#endif + if (free_list[bucket] == NULL) { /* need more core */ mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD)); if (mp == NULL) return(NULL); - } else { + } else { /* got it */ mp = free_list[bucket]; free_list[bucket] = mp->next; } - mp->bucket = bucket; + mp->bucket = bucket; /* tag block */ return((char *)(mp+1)); } char * realloc(op, n) /* reallocate memory using malloc() */ -char *op; +register char *op; unsigned n; { - register char *p; + char *p; register unsigned on; - - if (op != NULL) + /* get old size */ + if (op != NULL && op != DUMMYLOC) on = 1 << ((M_HEAD *)op-1)->bucket; else on = 0; - if (n <= on && n > on>>1) + if (n <= on && (n > on>>1 || on == 1<on ? on : n); + bcopy(op, p, n>on ? on : n); #else - (void)memcpy(p, op, n>on ? on : n); + (void)memcpy(p, op, n>on ? on : n); #endif free(op); return(p); @@ -164,10 +233,15 @@ char *p; register M_HEAD *mp; register int bucket; + if (p == NULL || p == DUMMYLOC) + return; mp = (M_HEAD *)p - 1; bucket = mp->bucket; mp->next = free_list[bucket]; free_list[bucket] = mp; +#ifdef MSTATS + m_nfreed += (1 << bucket) + sizeof(M_HEAD); +#endif } @@ -177,14 +251,41 @@ char *p; int getpagesize() /* use SYSV var structure to get page size */ { - static int pagesz = 0; struct var v; - if (pagesz == 0) { - uvar(&v); - pagesz = 1 << v.v_pageshift; - } - return(pagesz); + uvar(&v); + return(1 << v.v_pageshift); } #endif +#endif + + +#ifdef MSTATS +printmemstats(fp) /* print memory statistics to stream */ +FILE *fp; +{ + register int i; + int n; + register M_HEAD *mp; + unsigned int total = 0; + + fprintf(fp, "Memory statistics:\n"); + fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced); + fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed); + fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged); + fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced); + fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted, + 100.0*m_nwasted/m_nalloced); + fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed); + for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) { + n = 0; + for (mp = free_list[i]; mp != NULL; mp = mp->next) + n++; + if (n) { + fprintf(fp, "\t%d * %u\n", n, 1<