--- ray/src/common/malloc.c 1990/09/25 17:14:04 1.1 +++ ray/src/common/malloc.c 1990/10/03 16:20:38 1.8 @@ -7,15 +7,20 @@ 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 + #define NULL 0 #ifndef ALIGN @@ -23,10 +28,11 @@ static char SCCSid[] = "$SunId$ LBL"; #endif #define BYTES_WORD sizeof(ALIGN) +#define MAXINCR (1<<18) /* largest sbrk(2) increment */ + #ifdef NOVMEM #define getpagesize() BYTES_WORD #endif - /* malloc free lists */ typedef union m_head { union m_head *next; @@ -41,18 +47,40 @@ static M_HEAD *free_list[NBUCKETS]; 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; + 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; 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 +91,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 +119,26 @@ 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); + /* 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 +146,52 @@ 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); + } + 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; - + /* get old size */ if (op != NULL) 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,6 +204,8 @@ char *p; register M_HEAD *mp; register int bucket; + if (p == NULL) + return; mp = (M_HEAD *)p - 1; bucket = mp->bucket; mp->next = free_list[bucket]; @@ -177,14 +219,10 @@ 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