--- ray/src/common/malloc.c 1990/09/26 06:23:10 1.3 +++ ray/src/common/malloc.c 1992/10/08 12:27:02 2.8 @@ -1,4 +1,4 @@ -/* Copyright (c) 1990 Regents of the University of California */ +/* Copyright (c) 1992 Regents of the University of California */ #ifndef lint static char SCCSid[] = "$SunId$ LBL"; @@ -7,45 +7,193 @@ 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(2). However, bmalloc will - * call mscrounge() if sbrk fails. - * 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. - * mscrounge() returns whatever memory it can find to satisfy the + * 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). + * mcompact() takes the same arguments as mscrounge() (and is in fact + * called by mscrounge() under dire circumstances), but it uses + * memory compaction to return a larger block. (MCOMP) * * Greg Ward Lawrence Berkeley Laboratory */ +#include + +#ifndef BSD +#define bcopy(s,d,n) (void)memcpy(d,s,n) +#define bzero(d,n) (void)memset(d,0,n) +extern char *memcpy(), *memset(); +#endif + +#ifdef MSTATS +#include +static unsigned b_nsbrked = 0; +static unsigned b_nalloced = 0; +static unsigned b_nfreed = 0; +static unsigned b_nscrounged = 0; +static unsigned b_ncompacted = 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<<18) /* largest sbrk(2) increment */ - -#ifdef NOVMEM -#define getpagesize() BYTES_WORD +#ifndef MAXINCR +#define MAXINCR (1<<16) /* largest sbrk(2) increment */ #endif /* malloc free lists */ typedef union m_head { union m_head *next; - int bucket; + struct { + short magic; + short bucket; + } a; ALIGN dummy; } M_HEAD; +#define MAGIC 0x1a2 /* magic number for allocated memory */ + #define FIRSTBUCKET 3 #define NBUCKETS 30 static M_HEAD *free_list[NBUCKETS]; +static ALIGN dummy_mem; +static char *memlim[2]; + +#define DUMMYLOC ((char *)&dummy_mem) + +#define BADPTR(p) ((p) < memlim[0] | (p) >= memlim[1]) + +#ifdef MCOMP /* memory compaction routines */ +static char seedtab[1024]; /* seed for compaction table */ + +static struct mblk { + char *ptr; /* pointer to memory block */ + unsigned siz; /* size of memory block */ +} cptab = {seedtab, sizeof(seedtab)}; + +#define mtab(mb) ((struct mblk *)(mb)->ptr) +#define mtablen(mb) ((mb)->siz/sizeof(struct mblk)) + + +static int +mbcmp(m1, m2) /* compare memory block locations */ +register struct mblk *m1, *m2; +{ + /* put empty blocks at end */ + if (m1->siz == 0) + return(m2->siz == 0 ? 0 : 1); + if (m2->siz == 0) + return(-1); + /* otherwise, ascending order */ + return(m1->ptr - m2->ptr); +} + + +int +compactfree() /* compact free lists (moving to table) */ +{ + register struct mblk *tp; + register int bucket; + unsigned n, bsiz, ncomp; + /* fill table from free lists */ + tp = mtab(&cptab); n = mtablen(&cptab); + bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1); + ncomp = 0; + for ( ; ; ) { + while (tp->siz) { /* find empty slot */ + if (--n == 0) + goto loopexit; + tp++; + } + while (free_list[bucket] == NULL) { /* find block */ + if (--bucket < FIRSTBUCKET) + goto loopexit; + bsiz >>= 1; + } + tp->ptr = (char *)free_list[bucket]; + ncomp += (tp->siz = bsiz + sizeof(M_HEAD)); + free_list[bucket] = free_list[bucket]->next; + } +loopexit: + if (ncomp == 0) + return(0); /* nothing new to compact */ +#ifdef MSTATS + b_ncompacted += ncomp; +#endif + tp = mtab(&cptab); n = mtablen(&cptab); /* sort table */ + qsort((char *)tp, n, sizeof(struct mblk), mbcmp); + ncomp = 0; /* collect blocks */ + while (--n && tp[1].siz) { + if (tp[0].ptr + tp[0].siz == tp[1].ptr) { + tp[1].ptr = tp[0].ptr; + tp[1].siz += tp[0].siz; + ncomp += tp[0].siz; + tp[0].siz = 0; + } + tp++; + } + return(ncomp); +} + + char * -mscrounge(np) /* search free lists trying to satisfy request */ +mcompact(np) /* compact free lists to satisfy request */ +unsigned *np; +{ + struct mblk *tab; + unsigned tablen; + register struct mblk *bp, *big; + + for ( ; ; ) { + /* compact free lists */ + compactfree(); + /* find largest block */ + tab = mtab(&cptab); tablen = mtablen(&cptab); + big = tab; + bp = tab + tablen; + while (--bp > tab) + if (bp->siz > big->siz) + big = bp; + if (big->siz >= *np) { /* big enough? */ + *np = big->siz; + big->siz = 0; /* remove from table */ + return(big->ptr); /* return it */ + } + if (mtablen(big) <= tablen) { + *np = 0; /* cannot grow table */ + return(NULL); /* report failure */ + } + /* enlarge table, free old one */ + mtab(big)[0].ptr = cptab.ptr; + mtab(big)[0].siz = cptab.siz; + cptab.ptr = big->ptr; + cptab.siz = big->siz; + big->siz = 0; /* clear and copy */ + bcopy((char *)tab, (char *)(mtab(&cptab)+1), + tablen*sizeof(struct mblk)); + bzero((char *)(mtab(&cptab)+tablen+1), + (mtablen(&cptab)-tablen-1)*sizeof(struct mblk)); + } /* next round */ +} +#endif /* MCOMP */ + + +char * +mscrounge(np) /* search free lists to satisfy request */ register unsigned *np; { char *p; @@ -58,10 +206,17 @@ register unsigned *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); } +#ifdef MCOMP + return(mcompact(np)); /* try compaction */ +#else *np = 0; return(NULL); +#endif } @@ -81,14 +236,22 @@ register unsigned n; pagesz = amnt = getpagesize(); nrem = (int)sbrk(0); /* page align break */ nrem = pagesz - (nrem&(pagesz-1)); - bpos = sbrk(nrem); /* word aligned! */ + bpos = sbrk(nrem); if ((int)bpos == -1) return(NULL); +#ifdef MSTATS + b_nsbrked += nrem; +#endif + bpos += nrem & (BYTES_WORD-1); /* align pointer */ + nrem &= ~(BYTES_WORD-1); + memlim[0] = bpos; + memlim[1] = bpos + nrem; } n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */ if (n > nrem) { /* need more core */ + tryagain: if (n > amnt) { /* big chunk */ thisamnt = (n+(pagesz-1))&~(pagesz-1); if (thisamnt <= MAXINCR) /* increase amnt */ @@ -96,22 +259,39 @@ register unsigned n; } else thisamnt = amnt; p = sbrk(thisamnt); - if ((int)p == -1) { /* uh-oh */ - thisamnt = n; /* search free lists */ - p = mscrounge(&thisamnt); - if (p == NULL) /* we're really out */ + if ((int)p == -1) { /* uh-oh, ENOMEM */ + errno = 0; /* call cavalry */ + if (thisamnt >= n+pagesz) { + amnt = pagesz; /* minimize request */ + goto tryagain; + } + thisamnt = n; + p = mscrounge(&thisamnt); /* search free lists */ + if (p == NULL) { /* we're really out */ + errno = ENOMEM; return(NULL); + } } +#ifdef MSTATS + else b_nsbrked += thisamnt; +#endif if (p != bpos+nrem) { /* not an increment */ - bfree(bpos, nrem); + bfree(bpos, nrem); /* free what we have */ bpos = p; nrem = thisamnt; - } else + } else /* otherwise tack on */ nrem += thisamnt; + if (bpos < memlim[0]) + memlim[0] = bpos; + if (bpos + nrem > memlim[1]) + memlim[1] = bpos + nrem; } p = bpos; bpos += n; /* advance */ nrem -= n; +#ifdef MSTATS + b_nalloced += n; +#endif return(p); } @@ -122,20 +302,31 @@ register unsigned n; { register int bucket; register unsigned bsiz; - /* find largest bucket */ - bucket = 0; - for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1) - bucket++; - while (bucket > FIRSTBUCKET) { - bsiz >>= 1; - bucket--; - if (n < bsiz+sizeof(M_HEAD)) /* nothing for this bucket */ - continue; - ((M_HEAD *)p)->next = free_list[bucket]; - free_list[bucket] = (M_HEAD *)p; - p += bsiz+sizeof(M_HEAD); - n -= bsiz+sizeof(M_HEAD); + + if (n < 1< memlim[1]) + memlim[1] = p + n; + /* 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); + } } @@ -146,48 +337,57 @@ unsigned n; register M_HEAD *mp; register int bucket; register unsigned bsiz; - + /* don't return NULL on 0 request */ if (n == 0) - return(NULL); + return(DUMMYLOC); /* find first bucket that fits */ - bucket = FIRSTBUCKET; - for (bsiz = 1<= n) + break; + if (bucket >= NBUCKETS) { + errno = EINVAL; + return(NULL); + } + 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; +#ifdef MSTATS + m_nalloced += bsiz + sizeof(M_HEAD); + m_nwasted += bsiz + sizeof(M_HEAD) - n; +#endif + mp->a.magic = MAGIC; /* tag block */ + mp->a.bucket = bucket; 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) - on = 1 << ((M_HEAD *)op-1)->bucket; + /* get old size */ + if (op != DUMMYLOC && !BADPTR(op) && + ((M_HEAD *)op-1)->a.magic == MAGIC) + on = 1 << ((M_HEAD *)op-1)->a.bucket; else on = 0; - if (n <= on && n > on>>1) + if (n <= on && (n > on>>1 || on == 1<on ? on : n); -#else - (void)memcpy(p, op, n>on ? on : n); -#endif - free(op); + free(op); + } return(p); } @@ -198,29 +398,56 @@ char *p; register M_HEAD *mp; register int bucket; - if (p == NULL) - return; + if (p == DUMMYLOC) + return(1); + if (BADPTR(p)) + goto invalid; mp = (M_HEAD *)p - 1; - bucket = mp->bucket; + if (mp->a.magic != MAGIC) /* sanity check */ + goto invalid; + bucket = mp->a.bucket; + if (bucket < FIRSTBUCKET | bucket >= NBUCKETS) + goto invalid; mp->next = free_list[bucket]; free_list[bucket] = mp; +#ifdef MSTATS + m_nfreed += (1 << bucket) + sizeof(M_HEAD); +#endif + return(1); +invalid: + errno = EINVAL; + return(0); } -#ifndef NOVMEM -#ifndef BSD -#include -int -getpagesize() /* use SYSV var structure to get page size */ +#ifdef MSTATS +printmemstats(fp) /* print memory statistics to stream */ +FILE *fp; { - static int pagesz = 0; - struct var v; + register int i; + int n; + register M_HEAD *mp; + unsigned int total = 0; - if (pagesz == 0) { - uvar(&v); - pagesz = 1 << v.v_pageshift; + fprintf(fp, "Memory statistics:\n"); + fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked); + 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, "\tbmalloc: %d bytes compacted\n", b_ncompacted); + 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<