src/common/malloc.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 * Fast malloc for memory hogs and VM environments.
 * Performs a minimum of searching through 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
 */

/* ====================================================================
 * 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 [email protected].
 *
 * 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
 * <http://www.lbl.gov/>.
 */

#include  <errno.h>

#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  <stdio.h>
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;
        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<<FIRSTBUCKET;
                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
                if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *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 unsigned  pagesz = 0;
        static unsigned  amnt;
        static char  *bpos;
        static unsigned  nrem;
        unsigned  thisamnt;
        register char   *p;

        if (pagesz == 0) {                              /* initialize */
                pagesz = amnt = getpagesize();
                nrem = (int)sbrk(0);                    /* page align break */
                nrem = pagesz - (nrem&(pagesz-1));
                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 */
                                amnt = thisamnt;
                } else
                        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 */
register char  *p;
register unsigned  n;
{
        register int    bucket;
        register unsigned       bsiz;

        if (n < 1<<FIRSTBUCKET || p == NULL)
                return;
#ifdef MSTATS
        b_nfreed += n;
#endif
                                        /* align pointer */
        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
        if (bsiz < BYTES_WORD) {
                p += bsiz;
                n -= bsiz;
        }
        if (p < memlim[0])
                memlim[0] = p;
        if (p + n > 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);
                }
}


char *
malloc(n)                       /* allocate n bytes of memory */
unsigned        n;
{
        register M_HEAD *mp;
        register int    bucket;
        register unsigned       bsiz;
                                        /* don't return NULL on 0 request */
        if (n == 0)
                return(DUMMYLOC);
                                        /* find first bucket that fits */
        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
                if (bsiz >= 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 {                                /* got it */
                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));
}


char *
realloc(op, n)                  /* reallocate memory using malloc() */
register char   *op;
unsigned        n;
{
        char    *p;
        register unsigned       on;
                                        /* 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 || on == 1<<FIRSTBUCKET))
                return(op);             /* same bucket */
        if ((p = malloc(n)) == NULL)
                return(n<=on ? op : NULL);
        if (on) {
                bcopy(op, p, n>on ? on : n);
                free(op);
        }
        return(p);
}


free(p)                 /* free memory allocated by malloc */
char    *p;
{
        register M_HEAD *mp;
        register int    bucket;

        if (p == DUMMYLOC)
                return(1);
        if (BADPTR(p))
                goto invalid;
        mp = (M_HEAD *)p - 1;
        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);
}


#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 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<<i);
                        total += n * ((1<<i) + sizeof(M_HEAD));
                }
        }
        fprintf(fp, "\t %u total bytes in free list\n", total);
}
#endif
Revision:	2.12
Committed:	Sat Feb 22 02:07:22 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.11:	+63 -9 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.12	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4			/*
5			* Fast malloc for memory hogs and VM environments.
6			* Performs a minimum of searching through free lists.
7	greg	1.4	* malloc(), realloc() and free() use buckets
8			* containing blocks in powers of two, similar to CIT routines.
9			* bfree() puts memory from any source into malloc free lists.
10			* bmalloc() doesn't keep track of free lists -- it's usually
11	greg	1.3	* just a buffered call to sbrk(2). However, bmalloc will
12			* call mscrounge() if sbrk fails.
13	greg	1.8	* mscrounge() returns whatever free memory it can find to satisfy the
14	greg	1.3	* request along with the number of bytes (modified).
15	greg	1.14	* mcompact() takes the same arguments as mscrounge() (and is in fact
16			* called by mscrounge() under dire circumstances), but it uses
17			* memory compaction to return a larger block. (MCOMP)
18	greg	1.1	*
19			* Greg Ward Lawrence Berkeley Laboratory
20			*/
21
22	greg	2.12	/* ====================================================================
23			* The Radiance Software License, Version 1.0
24			*
25			* Copyright (c) 1990 - 2002 The Regents of the University of California,
26			* through Lawrence Berkeley National Laboratory. All rights reserved.
27			*
28			* Redistribution and use in source and binary forms, with or without
29			* modification, are permitted provided that the following conditions
30			* are met:
31			*
32			* 1. Redistributions of source code must retain the above copyright
33			* notice, this list of conditions and the following disclaimer.
34			*
35			* 2. Redistributions in binary form must reproduce the above copyright
36			* notice, this list of conditions and the following disclaimer in
37			* the documentation and/or other materials provided with the
38			* distribution.
39			*
40			* 3. The end-user documentation included with the redistribution,
41			* if any, must include the following acknowledgment:
42			* "This product includes Radiance software
43			* (http://radsite.lbl.gov/)
44			* developed by the Lawrence Berkeley National Laboratory
45			* (http://www.lbl.gov/)."
46			* Alternately, this acknowledgment may appear in the software itself,
47			* if and wherever such third-party acknowledgments normally appear.
48			*
49			* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
50			* and "The Regents of the University of California" must
51			* not be used to endorse or promote products derived from this
52			* software without prior written permission. For written
53			* permission, please contact [email protected].
54			*
55			* 5. Products derived from this software may not be called "Radiance",
56			* nor may "Radiance" appear in their name, without prior written
57			* permission of Lawrence Berkeley National Laboratory.
58			*
59			* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
60			* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
61			* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
62			* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
63			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
64			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
65			* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
66			* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
67			* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
68			* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
69			* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
70			* SUCH DAMAGE.
71			* ====================================================================
72			*
73			* This software consists of voluntary contributions made by many
74			* individuals on behalf of Lawrence Berkeley National Laboratory. For more
75			* information on Lawrence Berkeley National Laboratory, please see
76			* <http://www.lbl.gov/>.
77			*/
78
79	greg	1.6	#include <errno.h>
80
81	greg	2.7	#ifndef BSD
82			#define bcopy(s,d,n) (void)memcpy(d,s,n)
83			#define bzero(d,n) (void)memset(d,0,n)
84			#endif
85
86	greg	1.9	#ifdef MSTATS
87			#include <stdio.h>
88	greg	2.6	static unsigned b_nsbrked = 0;
89	greg	1.9	static unsigned b_nalloced = 0;
90			static unsigned b_nfreed = 0;
91			static unsigned b_nscrounged = 0;
92	greg	1.14	static unsigned b_ncompacted = 0;
93	greg	1.9	static unsigned m_nalloced = 0;
94			static unsigned m_nfreed = 0;
95			static unsigned m_nwasted = 0;
96			#else
97	greg	1.1	#define NULL 0
98	greg	1.9	#endif
99	greg	1.1
100	greg	2.12	#ifndef ALIGNT
101			#define ALIGNT int /* align type */
102	greg	1.1	#endif
103	greg	2.12	#define BYTES_WORD sizeof(ALIGNT)
104	greg	1.1
105	greg	1.16	#ifndef MAXINCR
106	greg	1.9	#define MAXINCR (1<<16) /* largest sbrk(2) increment */
107	greg	1.1	#endif
108			/* malloc free lists */
109			typedef union m_head {
110			union m_head *next;
111	greg	1.12	struct {
112			short magic;
113			short bucket;
114			} a;
115	greg	2.12	ALIGNT dummy;
116	greg	1.1	} M_HEAD;
117
118	greg	1.12	#define MAGIC 0x1a2 /* magic number for allocated memory */
119
120	greg	1.1	#define FIRSTBUCKET 3
121			#define NBUCKETS 30
122
123			static M_HEAD *free_list[NBUCKETS];
124
125	greg	2.12	static ALIGNT dummy_mem;
126	greg	1.1
127	greg	2.6	static char *memlim[2];
128
129	greg	1.12	#define DUMMYLOC ((char *)&dummy_mem)
130	greg	1.10
131	greg	2.6	#define BADPTR(p) ((p) < memlim[0] \| (p) >= memlim[1])
132
133	greg	1.14	#ifdef MCOMP /* memory compaction routines */
134			static char seedtab[1024]; /* seed for compaction table */
135	greg	1.12
136	greg	1.14	static struct mblk {
137			char ptr; / pointer to memory block */
138			unsigned siz; /* size of memory block */
139			} cptab = {seedtab, sizeof(seedtab)};
140
141			#define mtab(mb) ((struct mblk *)(mb)->ptr)
142			#define mtablen(mb) ((mb)->siz/sizeof(struct mblk))
143
144
145			static int
146			mbcmp(m1, m2) /* compare memory block locations */
147			register struct mblk m1, m2;
148			{
149			/* put empty blocks at end */
150			if (m1->siz == 0)
151			return(m2->siz == 0 ? 0 : 1);
152			if (m2->siz == 0)
153			return(-1);
154			/* otherwise, ascending order */
155			return(m1->ptr - m2->ptr);
156			}
157
158
159			int
160			compactfree() /* compact free lists (moving to table) */
161			{
162			register struct mblk *tp;
163			register int bucket;
164			unsigned n, bsiz, ncomp;
165			/* fill table from free lists */
166			tp = mtab(&cptab); n = mtablen(&cptab);
167			bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
168			ncomp = 0;
169			for ( ; ; ) {
170			while (tp->siz) { /* find empty slot */
171			if (--n == 0)
172			goto loopexit;
173			tp++;
174			}
175			while (free_list[bucket] == NULL) { /* find block */
176			if (--bucket < FIRSTBUCKET)
177			goto loopexit;
178			bsiz >>= 1;
179			}
180			tp->ptr = (char *)free_list[bucket];
181			ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
182			free_list[bucket] = free_list[bucket]->next;
183			}
184			loopexit:
185			if (ncomp == 0)
186			return(0); /* nothing new to compact */
187			#ifdef MSTATS
188			b_ncompacted += ncomp;
189			#endif
190			tp = mtab(&cptab); n = mtablen(&cptab); /* sort table */
191			qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
192			ncomp = 0; /* collect blocks */
193			while (--n && tp[1].siz) {
194			if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
195			tp[1].ptr = tp[0].ptr;
196			tp[1].siz += tp[0].siz;
197			ncomp += tp[0].siz;
198			tp[0].siz = 0;
199			}
200			tp++;
201			}
202			return(ncomp);
203			}
204
205
206	greg	1.1	char *
207	greg	1.14	mcompact(np) /* compact free lists to satisfy request */
208			unsigned *np;
209			{
210			struct mblk *tab;
211			unsigned tablen;
212			register struct mblk bp, big;
213
214			for ( ; ; ) {
215			/* compact free lists */
216	greg	2.9	while (compactfree())
217			;
218	greg	1.14	/* find largest block */
219			tab = mtab(&cptab); tablen = mtablen(&cptab);
220			big = tab;
221			bp = tab + tablen;
222			while (--bp > tab)
223			if (bp->siz > big->siz)
224			big = bp;
225			if (big->siz >= np) { / big enough? */
226			*np = big->siz;
227			big->siz = 0; /* remove from table */
228			return(big->ptr); /* return it */
229			}
230	greg	2.7	if (mtablen(big) <= tablen) {
231	greg	1.14	np = 0; / cannot grow table */
232			return(NULL); /* report failure */
233			}
234			/* enlarge table, free old one */
235			mtab(big)[0].ptr = cptab.ptr;
236			mtab(big)[0].siz = cptab.siz;
237			cptab.ptr = big->ptr;
238			cptab.siz = big->siz;
239			big->siz = 0; /* clear and copy */
240			bcopy((char )tab, (char )(mtab(&cptab)+1),
241			tablen*sizeof(struct mblk));
242			bzero((char *)(mtab(&cptab)+tablen+1),
243			(mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
244			} /* next round */
245			}
246			#endif /* MCOMP */
247
248
249			char *
250	greg	1.4	mscrounge(np) /* search free lists to satisfy request */
251	greg	1.3	register unsigned *np;
252			{
253			char *p;
254			register int bucket;
255			register unsigned bsiz;
256
257			for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
258			bucket < NBUCKETS; bucket++, bsiz <<= 1)
259			if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
260			*np = bsiz+sizeof(M_HEAD);
261			p = (char *)free_list[bucket];
262			free_list[bucket] = free_list[bucket]->next;
263	greg	1.9	#ifdef MSTATS
264			b_nscrounged += *np;
265			#endif
266	greg	1.3	return(p);
267			}
268	greg	1.14	#ifdef MCOMP
269			return(mcompact(np)); /* try compaction */
270			#else
271	greg	1.3	*np = 0;
272			return(NULL);
273	greg	1.14	#endif
274	greg	1.3	}
275
276
277			char *
278	greg	1.1	bmalloc(n) /* allocate a block of n bytes, sans header */
279			register unsigned n;
280			{
281			extern char *sbrk();
282	greg	1.3	static unsigned pagesz = 0;
283			static unsigned amnt;
284	greg	1.1	static char *bpos;
285	greg	1.3	static unsigned nrem;
286			unsigned thisamnt;
287	greg	1.1	register char *p;
288
289			if (pagesz == 0) { /* initialize */
290	greg	1.2	pagesz = amnt = getpagesize();
291	greg	1.1	nrem = (int)sbrk(0); /* page align break */
292			nrem = pagesz - (nrem&(pagesz-1));
293	greg	2.3	bpos = sbrk(nrem);
294	greg	1.1	if ((int)bpos == -1)
295			return(NULL);
296	greg	1.14	#ifdef MSTATS
297			b_nsbrked += nrem;
298			#endif
299	greg	2.4	bpos += nrem & (BYTES_WORD-1); /* align pointer */
300			nrem &= ~(BYTES_WORD-1);
301	greg	2.6	memlim[0] = bpos;
302			memlim[1] = bpos + nrem;
303	greg	1.1	}
304
305			n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
306
307			if (n > nrem) { /* need more core */
308	greg	2.8	tryagain:
309	greg	1.3	if (n > amnt) { /* big chunk */
310			thisamnt = (n+(pagesz-1))&~(pagesz-1);
311			if (thisamnt <= MAXINCR) /* increase amnt */
312			amnt = thisamnt;
313			} else
314			thisamnt = amnt;
315			p = sbrk(thisamnt);
316	greg	1.4	if ((int)p == -1) { /* uh-oh, ENOMEM */
317	greg	2.8	errno = 0; /* call cavalry */
318			if (thisamnt >= n+pagesz) {
319			amnt = pagesz; /* minimize request */
320			goto tryagain;
321			}
322			thisamnt = n;
323			p = mscrounge(&thisamnt); /* search free lists */
324			if (p == NULL) { /* we're really out */
325			errno = ENOMEM;
326	greg	1.3	return(NULL);
327	greg	2.8	}
328	greg	1.3	}
329	greg	1.14	#ifdef MSTATS
330			else b_nsbrked += thisamnt;
331			#endif
332	greg	1.3	if (p != bpos+nrem) { /* not an increment */
333	greg	1.4	bfree(bpos, nrem); /* free what we have */
334	greg	1.1	bpos = p;
335	greg	1.3	nrem = thisamnt;
336	greg	1.4	} else /* otherwise tack on */
337	greg	1.3	nrem += thisamnt;
338	greg	2.6	if (bpos < memlim[0])
339			memlim[0] = bpos;
340			if (bpos + nrem > memlim[1])
341			memlim[1] = bpos + nrem;
342	greg	1.1	}
343			p = bpos;
344			bpos += n; /* advance */
345			nrem -= n;
346	greg	1.13	#ifdef MSTATS
347			b_nalloced += n;
348			#endif
349	greg	1.1	return(p);
350			}
351
352
353			bfree(p, n) /* free n bytes of random memory */
354	greg	1.2	register char *p;
355			register unsigned n;
356	greg	1.1	{
357			register int bucket;
358			register unsigned bsiz;
359	greg	1.9
360	gwlarson	2.11	if (n < 1<<FIRSTBUCKET \|\| p == NULL)
361	greg	1.15	return;
362	greg	1.9	#ifdef MSTATS
363			b_nfreed += n;
364			#endif
365	greg	1.4	/* align pointer */
366	greg	1.6	bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
367	greg	1.4	if (bsiz < BYTES_WORD) {
368			p += bsiz;
369			n -= bsiz;
370	greg	1.1	}
371	greg	2.6	if (p < memlim[0])
372			memlim[0] = p;
373			if (p + n > memlim[1])
374			memlim[1] = p + n;
375	greg	1.4	/* fill big buckets first */
376			for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
377			bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
378			if (n >= bsiz+sizeof(M_HEAD)) {
379			((M_HEAD *)p)->next = free_list[bucket];
380			free_list[bucket] = (M_HEAD *)p;
381			p += bsiz+sizeof(M_HEAD);
382			n -= bsiz+sizeof(M_HEAD);
383			}
384	greg	1.1	}
385
386
387			char *
388			malloc(n) /* allocate n bytes of memory */
389			unsigned n;
390			{
391			register M_HEAD *mp;
392			register int bucket;
393			register unsigned bsiz;
394	greg	1.10	/* don't return NULL on 0 request */
395			if (n == 0)
396			return(DUMMYLOC);
397	greg	1.2	/* find first bucket that fits */
398	greg	1.6	for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
399			bucket < NBUCKETS; bucket++, bsiz <<= 1)
400			if (bsiz >= n)
401			break;
402			if (bucket >= NBUCKETS) {
403			errno = EINVAL;
404			return(NULL);
405			}
406	greg	1.4	if (free_list[bucket] == NULL) { /* need more core */
407	greg	1.1	mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
408			if (mp == NULL)
409			return(NULL);
410	greg	1.4	} else { /* got it */
411	greg	1.1	mp = free_list[bucket];
412			free_list[bucket] = mp->next;
413			}
414	greg	1.13	#ifdef MSTATS
415			m_nalloced += bsiz + sizeof(M_HEAD);
416			m_nwasted += bsiz + sizeof(M_HEAD) - n;
417			#endif
418	greg	1.12	mp->a.magic = MAGIC; /* tag block */
419			mp->a.bucket = bucket;
420	greg	1.1	return((char *)(mp+1));
421			}
422
423
424			char *
425			realloc(op, n) /* reallocate memory using malloc() */
426	greg	1.6	register char *op;
427	greg	1.1	unsigned n;
428			{
429	greg	1.6	char *p;
430	greg	1.1	register unsigned on;
431	greg	1.6	/* get old size */
432	greg	2.6	if (op != DUMMYLOC && !BADPTR(op) &&
433			((M_HEAD *)op-1)->a.magic == MAGIC)
434	greg	1.12	on = 1 << ((M_HEAD *)op-1)->a.bucket;
435	greg	1.5	else
436			on = 0;
437	greg	1.6	if (n <= on && (n > on>>1 \|\| on == 1<<FIRSTBUCKET))
438	greg	1.5	return(op); /* same bucket */
439	greg	1.13	if ((p = malloc(n)) == NULL)
440	greg	2.5	return(n<=on ? op : NULL);
441	greg	1.13	if (on) {
442	greg	1.2	bcopy(op, p, n>on ? on : n);
443	greg	1.13	free(op);
444			}
445	greg	1.1	return(p);
446			}
447
448
449			free(p) /* free memory allocated by malloc */
450			char *p;
451			{
452			register M_HEAD *mp;
453			register int bucket;
454
455	greg	2.6	if (p == DUMMYLOC)
456	greg	1.13	return(1);
457	greg	2.6	if (BADPTR(p))
458			goto invalid;
459	greg	1.1	mp = (M_HEAD *)p - 1;
460	greg	1.12	if (mp->a.magic != MAGIC) /* sanity check */
461	greg	2.6	goto invalid;
462	greg	1.12	bucket = mp->a.bucket;
463	greg	2.2	if (bucket < FIRSTBUCKET \| bucket >= NBUCKETS)
464	greg	2.6	goto invalid;
465	greg	1.1	mp->next = free_list[bucket];
466			free_list[bucket] = mp;
467	greg	1.9	#ifdef MSTATS
468			m_nfreed += (1 << bucket) + sizeof(M_HEAD);
469			#endif
470	greg	1.13	return(1);
471	greg	2.6	invalid:
472			errno = EINVAL;
473			return(0);
474	greg	1.1	}
475	greg	1.9
476
477			#ifdef MSTATS
478			printmemstats(fp) /* print memory statistics to stream */
479			FILE *fp;
480			{
481			register int i;
482			int n;
483			register M_HEAD *mp;
484			unsigned int total = 0;
485
486			fprintf(fp, "Memory statistics:\n");
487	greg	1.14	fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
488	greg	1.9	fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
489			fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
490			fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
491	greg	1.14	fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
492	greg	1.9	fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
493			fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
494			100.0*m_nwasted/m_nalloced);
495			fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
496			for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
497			n = 0;
498			for (mp = free_list[i]; mp != NULL; mp = mp->next)
499			n++;
500			if (n) {
501			fprintf(fp, "\t%d * %u\n", n, 1<<i);
502			total += n * ((1<<i) + sizeof(M_HEAD));
503			}
504			}
505			fprintf(fp, "\t %u total bytes in free list\n", total);
506			}
507	greg	1.1	#endif