src/common/malloc.c

/* Copyright (c) 1991 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#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
 */

#include  <errno.h>

#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 ALIGN
#define  ALIGN          int                     /* align type */
#endif
#define  BYTES_WORD     sizeof(ALIGN)

#define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */

#ifdef  NOVMEM
#define  getpagesize()  1024
#endif
                                        /* malloc free lists */
typedef union m_head {
        union m_head    *next;
        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;

#define DUMMYLOC        ((char *)&dummy_mem)

#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 */
                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+1) {
                        *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 */
#ifdef BSD
                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
                                tablen*sizeof(struct mblk));
                bzero((char *)(mtab(&cptab)+tablen+1),
                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
#else
                (void)memcpy((char *)(mtab(&cptab)+1), (char *)tab,
                                tablen*sizeof(struct mblk));
                memset((char *)(mtab(&cptab)+tablen+1), 0,
                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
#endif
        }                       /* 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);                      /* word aligned! */
                if ((int)bpos == -1)
                        return(NULL);
#ifdef MSTATS
                b_nsbrked += nrem;
#endif
        }

        n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */

        if (n > nrem) {                                 /* need more core */
                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 */
                        thisamnt = n;                   /* search free lists */
                        p = mscrounge(&thisamnt);
                        if (p == NULL)                  /* we're really out */
                                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;
        }
        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)
                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;
        }
                                        /* 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;
{
        extern int  errno;
        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 != NULL && op != DUMMYLOC && ((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(NULL);
        if (on) {
#ifdef  BSD
                bcopy(op, p, n>on ? on : n);
#else
                (void)memcpy(p, op, n>on ? on : n);
#endif
                free(op);
        }
        return(p);
}


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

        if (p == NULL || p == DUMMYLOC)
                return(1);
        mp = (M_HEAD *)p - 1;
        if (mp->a.magic != MAGIC)               /* sanity check */
                return(0);
        bucket = mp->a.bucket;
        mp->next = free_list[bucket];
        free_list[bucket] = mp;
#ifdef MSTATS
        m_nfreed += (1 << bucket) + sizeof(M_HEAD);
#endif
        return(1);
}


#ifndef NOVMEM
#ifndef BSD
#include <sys/var.h>
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;
{
        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:	1.15
Committed:	Mon Aug 26 10:49:08 1991 UTC (32 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.14:	+2 -0 lines
Log Message:	fixed potential bug in bfree()
#	User	Rev	Content
1	greg	1.12	/* Copyright (c) 1991 Regents of the University of California */
2	greg	1.1
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ LBL";
5			#endif
6
7			/*
8			* Fast malloc for memory hogs and VM environments.
9			* Performs a minimum of searching through free lists.
10	greg	1.4	* malloc(), realloc() and free() use buckets
11			* containing blocks in powers of two, similar to CIT routines.
12			* bfree() puts memory from any source into malloc free lists.
13			* bmalloc() doesn't keep track of free lists -- it's usually
14	greg	1.3	* just a buffered call to sbrk(2). However, bmalloc will
15			* call mscrounge() if sbrk fails.
16	greg	1.8	* mscrounge() returns whatever free memory it can find to satisfy the
17	greg	1.3	* request along with the number of bytes (modified).
18	greg	1.14	* mcompact() takes the same arguments as mscrounge() (and is in fact
19			* called by mscrounge() under dire circumstances), but it uses
20			* memory compaction to return a larger block. (MCOMP)
21	greg	1.1	*
22			* Greg Ward Lawrence Berkeley Laboratory
23			*/
24
25	greg	1.6	#include <errno.h>
26
27	greg	1.9	#ifdef MSTATS
28			#include <stdio.h>
29	greg	1.14	static unsigned b_nsbrked = 0;
30	greg	1.9	static unsigned b_nalloced = 0;
31			static unsigned b_nfreed = 0;
32			static unsigned b_nscrounged = 0;
33	greg	1.14	static unsigned b_ncompacted = 0;
34	greg	1.9	static unsigned m_nalloced = 0;
35			static unsigned m_nfreed = 0;
36			static unsigned m_nwasted = 0;
37			#else
38	greg	1.1	#define NULL 0
39	greg	1.9	#endif
40	greg	1.1
41			#ifndef ALIGN
42			#define ALIGN int /* align type */
43			#endif
44			#define BYTES_WORD sizeof(ALIGN)
45
46	greg	1.9	#define MAXINCR (1<<16) /* largest sbrk(2) increment */
47	greg	1.3
48	greg	1.1	#ifdef NOVMEM
49	greg	1.11	#define getpagesize() 1024
50	greg	1.1	#endif
51			/* malloc free lists */
52			typedef union m_head {
53			union m_head *next;
54	greg	1.12	struct {
55			short magic;
56			short bucket;
57			} a;
58	greg	1.1	ALIGN dummy;
59			} M_HEAD;
60
61	greg	1.12	#define MAGIC 0x1a2 /* magic number for allocated memory */
62
63	greg	1.1	#define FIRSTBUCKET 3
64			#define NBUCKETS 30
65
66			static M_HEAD *free_list[NBUCKETS];
67
68	greg	1.12	static ALIGN dummy_mem;
69	greg	1.1
70	greg	1.12	#define DUMMYLOC ((char *)&dummy_mem)
71	greg	1.10
72	greg	1.14	#ifdef MCOMP /* memory compaction routines */
73			static char seedtab[1024]; /* seed for compaction table */
74	greg	1.12
75	greg	1.14	static struct mblk {
76			char ptr; / pointer to memory block */
77			unsigned siz; /* size of memory block */
78			} cptab = {seedtab, sizeof(seedtab)};
79
80			#define mtab(mb) ((struct mblk *)(mb)->ptr)
81			#define mtablen(mb) ((mb)->siz/sizeof(struct mblk))
82
83
84			static int
85			mbcmp(m1, m2) /* compare memory block locations */
86			register struct mblk m1, m2;
87			{
88			/* put empty blocks at end */
89			if (m1->siz == 0)
90			return(m2->siz == 0 ? 0 : 1);
91			if (m2->siz == 0)
92			return(-1);
93			/* otherwise, ascending order */
94			return(m1->ptr - m2->ptr);
95			}
96
97
98			int
99			compactfree() /* compact free lists (moving to table) */
100			{
101			register struct mblk *tp;
102			register int bucket;
103			unsigned n, bsiz, ncomp;
104			/* fill table from free lists */
105			tp = mtab(&cptab); n = mtablen(&cptab);
106			bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
107			ncomp = 0;
108			for ( ; ; ) {
109			while (tp->siz) { /* find empty slot */
110			if (--n == 0)
111			goto loopexit;
112			tp++;
113			}
114			while (free_list[bucket] == NULL) { /* find block */
115			if (--bucket < FIRSTBUCKET)
116			goto loopexit;
117			bsiz >>= 1;
118			}
119			tp->ptr = (char *)free_list[bucket];
120			ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
121			free_list[bucket] = free_list[bucket]->next;
122			}
123			loopexit:
124			if (ncomp == 0)
125			return(0); /* nothing new to compact */
126			#ifdef MSTATS
127			b_ncompacted += ncomp;
128			#endif
129			tp = mtab(&cptab); n = mtablen(&cptab); /* sort table */
130			qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
131			ncomp = 0; /* collect blocks */
132			while (--n && tp[1].siz) {
133			if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
134			tp[1].ptr = tp[0].ptr;
135			tp[1].siz += tp[0].siz;
136			ncomp += tp[0].siz;
137			tp[0].siz = 0;
138			}
139			tp++;
140			}
141			return(ncomp);
142			}
143
144
145	greg	1.1	char *
146	greg	1.14	mcompact(np) /* compact free lists to satisfy request */
147			unsigned *np;
148			{
149			struct mblk *tab;
150			unsigned tablen;
151			register struct mblk bp, big;
152
153			for ( ; ; ) {
154			/* compact free lists */
155			compactfree();
156			/* find largest block */
157			tab = mtab(&cptab); tablen = mtablen(&cptab);
158			big = tab;
159			bp = tab + tablen;
160			while (--bp > tab)
161			if (bp->siz > big->siz)
162			big = bp;
163			if (big->siz >= np) { / big enough? */
164			*np = big->siz;
165			big->siz = 0; /* remove from table */
166			return(big->ptr); /* return it */
167			}
168			if (mtablen(big) < tablen+1) {
169			np = 0; / cannot grow table */
170			return(NULL); /* report failure */
171			}
172			/* enlarge table, free old one */
173			mtab(big)[0].ptr = cptab.ptr;
174			mtab(big)[0].siz = cptab.siz;
175			cptab.ptr = big->ptr;
176			cptab.siz = big->siz;
177			big->siz = 0; /* clear and copy */
178			#ifdef BSD
179			bcopy((char )tab, (char )(mtab(&cptab)+1),
180			tablen*sizeof(struct mblk));
181			bzero((char *)(mtab(&cptab)+tablen+1),
182			(mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
183			#else
184			(void)memcpy((char )(mtab(&cptab)+1), (char )tab,
185			tablen*sizeof(struct mblk));
186			memset((char *)(mtab(&cptab)+tablen+1), 0,
187			(mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
188			#endif
189			} /* next round */
190			}
191			#endif /* MCOMP */
192
193
194			char *
195	greg	1.4	mscrounge(np) /* search free lists to satisfy request */
196	greg	1.3	register unsigned *np;
197			{
198			char *p;
199			register int bucket;
200			register unsigned bsiz;
201
202			for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
203			bucket < NBUCKETS; bucket++, bsiz <<= 1)
204			if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
205			*np = bsiz+sizeof(M_HEAD);
206			p = (char *)free_list[bucket];
207			free_list[bucket] = free_list[bucket]->next;
208	greg	1.9	#ifdef MSTATS
209			b_nscrounged += *np;
210			#endif
211	greg	1.3	return(p);
212			}
213	greg	1.14	#ifdef MCOMP
214			return(mcompact(np)); /* try compaction */
215			#else
216	greg	1.3	*np = 0;
217			return(NULL);
218	greg	1.14	#endif
219	greg	1.3	}
220
221
222			char *
223	greg	1.1	bmalloc(n) /* allocate a block of n bytes, sans header */
224			register unsigned n;
225			{
226			extern char *sbrk();
227	greg	1.3	static unsigned pagesz = 0;
228			static unsigned amnt;
229	greg	1.1	static char *bpos;
230	greg	1.3	static unsigned nrem;
231			unsigned thisamnt;
232	greg	1.1	register char *p;
233
234			if (pagesz == 0) { /* initialize */
235	greg	1.2	pagesz = amnt = getpagesize();
236	greg	1.1	nrem = (int)sbrk(0); /* page align break */
237			nrem = pagesz - (nrem&(pagesz-1));
238			bpos = sbrk(nrem); /* word aligned! */
239			if ((int)bpos == -1)
240			return(NULL);
241	greg	1.14	#ifdef MSTATS
242			b_nsbrked += nrem;
243			#endif
244	greg	1.1	}
245
246			n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
247
248			if (n > nrem) { /* need more core */
249	greg	1.3	if (n > amnt) { /* big chunk */
250			thisamnt = (n+(pagesz-1))&~(pagesz-1);
251			if (thisamnt <= MAXINCR) /* increase amnt */
252			amnt = thisamnt;
253			} else
254			thisamnt = amnt;
255			p = sbrk(thisamnt);
256	greg	1.4	if ((int)p == -1) { /* uh-oh, ENOMEM */
257	greg	1.3	thisamnt = n; /* search free lists */
258			p = mscrounge(&thisamnt);
259			if (p == NULL) /* we're really out */
260			return(NULL);
261			}
262	greg	1.14	#ifdef MSTATS
263			else b_nsbrked += thisamnt;
264			#endif
265	greg	1.3	if (p != bpos+nrem) { /* not an increment */
266	greg	1.4	bfree(bpos, nrem); /* free what we have */
267	greg	1.1	bpos = p;
268	greg	1.3	nrem = thisamnt;
269	greg	1.4	} else /* otherwise tack on */
270	greg	1.3	nrem += thisamnt;
271	greg	1.1	}
272			p = bpos;
273			bpos += n; /* advance */
274			nrem -= n;
275	greg	1.13	#ifdef MSTATS
276			b_nalloced += n;
277			#endif
278	greg	1.1	return(p);
279			}
280
281
282			bfree(p, n) /* free n bytes of random memory */
283	greg	1.2	register char *p;
284			register unsigned n;
285	greg	1.1	{
286			register int bucket;
287			register unsigned bsiz;
288	greg	1.9
289	greg	1.15	if (n < 1<<FIRSTBUCKET)
290			return;
291	greg	1.9	#ifdef MSTATS
292			b_nfreed += n;
293			#endif
294	greg	1.4	/* align pointer */
295	greg	1.6	bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
296	greg	1.4	if (bsiz < BYTES_WORD) {
297			p += bsiz;
298			n -= bsiz;
299	greg	1.1	}
300	greg	1.4	/* fill big buckets first */
301			for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
302			bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
303			if (n >= bsiz+sizeof(M_HEAD)) {
304			((M_HEAD *)p)->next = free_list[bucket];
305			free_list[bucket] = (M_HEAD *)p;
306			p += bsiz+sizeof(M_HEAD);
307			n -= bsiz+sizeof(M_HEAD);
308			}
309	greg	1.1	}
310
311
312			char *
313			malloc(n) /* allocate n bytes of memory */
314			unsigned n;
315			{
316	greg	1.6	extern int errno;
317	greg	1.1	register M_HEAD *mp;
318			register int bucket;
319			register unsigned bsiz;
320	greg	1.10	/* don't return NULL on 0 request */
321			if (n == 0)
322			return(DUMMYLOC);
323	greg	1.2	/* find first bucket that fits */
324	greg	1.6	for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
325			bucket < NBUCKETS; bucket++, bsiz <<= 1)
326			if (bsiz >= n)
327			break;
328			if (bucket >= NBUCKETS) {
329			errno = EINVAL;
330			return(NULL);
331			}
332	greg	1.4	if (free_list[bucket] == NULL) { /* need more core */
333	greg	1.1	mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
334			if (mp == NULL)
335			return(NULL);
336	greg	1.4	} else { /* got it */
337	greg	1.1	mp = free_list[bucket];
338			free_list[bucket] = mp->next;
339			}
340	greg	1.13	#ifdef MSTATS
341			m_nalloced += bsiz + sizeof(M_HEAD);
342			m_nwasted += bsiz + sizeof(M_HEAD) - n;
343			#endif
344	greg	1.12	mp->a.magic = MAGIC; /* tag block */
345			mp->a.bucket = bucket;
346	greg	1.1	return((char *)(mp+1));
347			}
348
349
350			char *
351			realloc(op, n) /* reallocate memory using malloc() */
352	greg	1.6	register char *op;
353	greg	1.1	unsigned n;
354			{
355	greg	1.6	char *p;
356	greg	1.1	register unsigned on;
357	greg	1.6	/* get old size */
358	greg	1.12	if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
359			on = 1 << ((M_HEAD *)op-1)->a.bucket;
360	greg	1.5	else
361			on = 0;
362	greg	1.6	if (n <= on && (n > on>>1 \|\| on == 1<<FIRSTBUCKET))
363	greg	1.5	return(op); /* same bucket */
364	greg	1.13	if ((p = malloc(n)) == NULL)
365			return(NULL);
366			if (on) {
367	greg	1.1	#ifdef BSD
368	greg	1.2	bcopy(op, p, n>on ? on : n);
369	greg	1.1	#else
370	greg	1.2	(void)memcpy(p, op, n>on ? on : n);
371	greg	1.1	#endif
372	greg	1.13	free(op);
373			}
374	greg	1.1	return(p);
375			}
376
377
378			free(p) /* free memory allocated by malloc */
379			char *p;
380			{
381			register M_HEAD *mp;
382			register int bucket;
383
384	greg	1.10	if (p == NULL \|\| p == DUMMYLOC)
385	greg	1.13	return(1);
386	greg	1.1	mp = (M_HEAD *)p - 1;
387	greg	1.12	if (mp->a.magic != MAGIC) /* sanity check */
388	greg	1.13	return(0);
389	greg	1.12	bucket = mp->a.bucket;
390	greg	1.1	mp->next = free_list[bucket];
391			free_list[bucket] = mp;
392	greg	1.9	#ifdef MSTATS
393			m_nfreed += (1 << bucket) + sizeof(M_HEAD);
394			#endif
395	greg	1.13	return(1);
396	greg	1.1	}
397
398
399			#ifndef NOVMEM
400			#ifndef BSD
401			#include <sys/var.h>
402			int
403			getpagesize() /* use SYSV var structure to get page size */
404			{
405			struct var v;
406
407	greg	1.8	uvar(&v);
408			return(1 << v.v_pageshift);
409	greg	1.1	}
410			#endif
411	greg	1.9	#endif
412
413
414			#ifdef MSTATS
415			printmemstats(fp) /* print memory statistics to stream */
416			FILE *fp;
417			{
418			register int i;
419			int n;
420			register M_HEAD *mp;
421			unsigned int total = 0;
422
423			fprintf(fp, "Memory statistics:\n");
424	greg	1.14	fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
425	greg	1.9	fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
426			fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
427			fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
428	greg	1.14	fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
429	greg	1.9	fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
430			fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
431			100.0*m_nwasted/m_nalloced);
432			fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
433			for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
434			n = 0;
435			for (mp = free_list[i]; mp != NULL; mp = mp->next)
436			n++;
437			if (n) {
438			fprintf(fp, "\t%d * %u\n", n, 1<<i);
439			total += n * ((1<<i) + sizeof(M_HEAD));
440			}
441			}
442			fprintf(fp, "\t %u total bytes in free list\n", total);
443			}
444	greg	1.1	#endif