--- ray/src/common/malloc.c 1991/04/02 09:36:21 1.12
+++ ray/src/common/malloc.c 2003/02/22 02:07:22 2.12
@@ -1,9 +1,6 @@
-/* Copyright (c) 1991 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.
@@ -15,17 +12,84 @@ static char SCCSid[] = "$SunId$ LBL";
* 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
*/
+/* ====================================================================
+ * 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
+ * .
+ */
+
#include
+#ifndef BSD
+#define bcopy(s,d,n) (void)memcpy(d,s,n)
+#define bzero(d,n) (void)memset(d,0,n)
+#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;
@@ -33,15 +97,13 @@ static unsigned m_nwasted = 0;
#define NULL 0
#endif
-#ifndef ALIGN
-#define ALIGN int /* align type */
+#ifndef ALIGNT
+#define ALIGNT int /* align type */
#endif
-#define BYTES_WORD sizeof(ALIGN)
+#define BYTES_WORD sizeof(ALIGNT)
+#ifndef MAXINCR
#define MAXINCR (1<<16) /* largest sbrk(2) increment */
-
-#ifdef NOVMEM
-#define getpagesize() 1024
#endif
/* malloc free lists */
typedef union m_head {
@@ -50,7 +112,7 @@ typedef union m_head {
short magic;
short bucket;
} a;
- ALIGN dummy;
+ ALIGNT dummy;
} M_HEAD;
#define MAGIC 0x1a2 /* magic number for allocated memory */
@@ -60,12 +122,131 @@ typedef union m_head {
static M_HEAD *free_list[NBUCKETS];
-static ALIGN dummy_mem;
+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;
{
@@ -84,8 +265,12 @@ register unsigned *np;
#endif
return(p);
}
+#ifdef MCOMP
+ return(mcompact(np)); /* try compaction */
+#else
*np = 0;
return(NULL);
+#endif
}
@@ -101,21 +286,26 @@ register unsigned n;
unsigned thisamnt;
register char *p;
-#ifdef MSTATS
- b_nalloced += n;
-#endif
if (pagesz == 0) { /* initialize */
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 */
@@ -124,21 +314,38 @@ register unsigned n;
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 */
+ 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);
}
@@ -150,6 +357,8 @@ register unsigned n;
register int bucket;
register unsigned bsiz;
+ 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)
@@ -175,7 +388,6 @@ char *
malloc(n) /* allocate n bytes of memory */
unsigned n;
{
- extern int errno;
register M_HEAD *mp;
register int bucket;
register unsigned bsiz;
@@ -191,10 +403,6 @@ unsigned n;
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)
@@ -203,6 +411,10 @@ unsigned n;
mp = free_list[bucket];
free_list[bucket] = mp->next;
}
+#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));
@@ -217,20 +429,19 @@ unsigned n;
char *p;
register unsigned on;
/* get old size */
- if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
+ 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 || on == 1<on ? on : n);
-#else
- (void)memcpy(p, op, n>on ? on : n);
-#endif
- free(op);
+ free(op);
+ }
return(p);
}
@@ -241,35 +452,28 @@ char *p;
register M_HEAD *mp;
register int bucket;
- if (p == NULL || p == DUMMYLOC)
- return;
+ if (p == DUMMYLOC)
+ return(1);
+ if (BADPTR(p))
+ goto invalid;
mp = (M_HEAD *)p - 1;
if (mp->a.magic != MAGIC) /* sanity check */
- return;
+ 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 */
-{
- struct var v;
-
- uvar(&v);
- return(1 << v.v_pageshift);
-}
-#endif
-#endif
-
-
#ifdef MSTATS
printmemstats(fp) /* print memory statistics to stream */
FILE *fp;
@@ -280,9 +484,11 @@ FILE *fp;
unsigned int total = 0;
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);