--- ray/src/common/malloc.c 1990/09/25 17:14:04 1.1
+++ ray/src/common/malloc.c 2003/02/22 02:07:22 2.12
@@ -1,109 +1,386 @@
-/* Copyright (c) 1990 Regents of the University of California */
-
#ifndef lint
-static char SCCSid[] = "$SunId$ LBL";
+static const char RCSid[] = "$Id: malloc.c,v 2.12 2003/02/22 02:07:22 greg Exp $";
#endif
-
/*
* 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).
+ * 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
*/
-#define NULL 0
+/* ====================================================================
+ * The Radiance Software License, Version 1.0
+ *
+ * Copyright (c) 1990 - 2002 The Regents of the University of California,
+ * through Lawrence Berkeley National Laboratory. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution,
+ * if any, must include the following acknowledgment:
+ * "This product includes Radiance software
+ * (http://radsite.lbl.gov/)
+ * developed by the Lawrence Berkeley National Laboratory
+ * (http://www.lbl.gov/)."
+ * Alternately, this acknowledgment may appear in the software itself,
+ * if and wherever such third-party acknowledgments normally appear.
+ *
+ * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
+ * and "The Regents of the University of California" must
+ * not be used to endorse or promote products derived from this
+ * software without prior written permission. For written
+ * permission, please contact radiance@radsite.lbl.gov.
+ *
+ * 5. Products derived from this software may not be called "Radiance",
+ * nor may "Radiance" appear in their name, without prior written
+ * permission of Lawrence Berkeley National Laboratory.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of Lawrence Berkeley National Laboratory. For more
+ * information on Lawrence Berkeley National Laboratory, please see
+ * .
+ */
-#ifndef ALIGN
-#define ALIGN int /* align type */
+#include
+
+#ifndef BSD
+#define bcopy(s,d,n) (void)memcpy(d,s,n)
+#define bzero(d,n) (void)memset(d,0,n)
#endif
-#define BYTES_WORD sizeof(ALIGN)
-#ifdef NOVMEM
-#define getpagesize() BYTES_WORD
+#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 ALIGNT
+#define ALIGNT int /* align type */
+#endif
+#define BYTES_WORD sizeof(ALIGNT)
+
+#ifndef MAXINCR
+#define MAXINCR (1<<16) /* largest sbrk(2) increment */
+#endif
/* malloc free lists */
typedef union m_head {
union m_head *next;
- int bucket;
- ALIGN dummy;
+ struct {
+ short magic;
+ short bucket;
+ } a;
+ ALIGNT dummy;
} M_HEAD;
+#define MAGIC 0x1a2 /* magic number for allocated memory */
+
#define FIRSTBUCKET 3
#define NBUCKETS 30
static M_HEAD *free_list[NBUCKETS];
+static ALIGNT 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 *
+mcompact(np) /* compact free lists to satisfy request */
+unsigned *np;
+{
+ struct mblk *tab;
+ unsigned tablen;
+ register struct mblk *bp, *big;
+
+ for ( ; ; ) {
+ /* compact free lists */
+ while (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;
+ 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);
+ }
+#ifdef MCOMP
+ return(mcompact(np)); /* try compaction */
+#else
+ *np = 0;
+ return(NULL);
+#endif
+}
+
+
+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! */
+ 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 */
- 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;
+ tryagain:
+ 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 */
+ 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); /* free what we have */
+ bpos = p;
+ nrem = thisamnt;
+ } 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);
}
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);
+
+ 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);
+ }
}
@@ -114,46 +391,57 @@ unsigned n;
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;
+#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);
+ if ((p = malloc(n)) == NULL)
+ return(n<=on ? op : NULL);
+ if (on) {
+ bcopy(op, p, n>on ? on : n);
+ free(op);
+ }
return(p);
}
@@ -164,27 +452,56 @@ char *p;
register M_HEAD *mp;
register int bucket;
+ 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<