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).
 *
 *      Greg Ward       Lawrence Berkeley Laboratory
 */

#include  <errno.h>

#ifdef MSTATS
#include  <stdio.h>
static unsigned b_nalloced = 0;
static unsigned b_nfreed = 0;
static unsigned b_nscrounged = 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)


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);
                }
        *np = 0;
        return(NULL);
}


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);
        }

        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);
                }
                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;

#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 allocated\n", b_nalloced);
        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
        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.13
Committed:	Wed Jul 17 11:35:47 1991 UTC (34 years, 3 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.12:	+15 -12 lines
Log Message:	fixed realloc() so as not to free op if malloc fails
#	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.1	*
19			* Greg Ward Lawrence Berkeley Laboratory
20			*/
21
22	greg	1.6	#include <errno.h>
23
24	greg	1.9	#ifdef MSTATS
25			#include <stdio.h>
26			static unsigned b_nalloced = 0;
27			static unsigned b_nfreed = 0;
28			static unsigned b_nscrounged = 0;
29			static unsigned m_nalloced = 0;
30			static unsigned m_nfreed = 0;
31			static unsigned m_nwasted = 0;
32			#else
33	greg	1.1	#define NULL 0
34	greg	1.9	#endif
35	greg	1.1
36			#ifndef ALIGN
37			#define ALIGN int /* align type */
38			#endif
39			#define BYTES_WORD sizeof(ALIGN)
40
41	greg	1.9	#define MAXINCR (1<<16) /* largest sbrk(2) increment */
42	greg	1.3
43	greg	1.1	#ifdef NOVMEM
44	greg	1.11	#define getpagesize() 1024
45	greg	1.1	#endif
46			/* malloc free lists */
47			typedef union m_head {
48			union m_head *next;
49	greg	1.12	struct {
50			short magic;
51			short bucket;
52			} a;
53	greg	1.1	ALIGN dummy;
54			} M_HEAD;
55
56	greg	1.12	#define MAGIC 0x1a2 /* magic number for allocated memory */
57
58	greg	1.1	#define FIRSTBUCKET 3
59			#define NBUCKETS 30
60
61			static M_HEAD *free_list[NBUCKETS];
62
63	greg	1.12	static ALIGN dummy_mem;
64	greg	1.1
65	greg	1.12	#define DUMMYLOC ((char *)&dummy_mem)
66	greg	1.10
67	greg	1.12
68	greg	1.1	char *
69	greg	1.4	mscrounge(np) /* search free lists to satisfy request */
70	greg	1.3	register unsigned *np;
71			{
72			char *p;
73			register int bucket;
74			register unsigned bsiz;
75
76			for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
77			bucket < NBUCKETS; bucket++, bsiz <<= 1)
78			if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
79			*np = bsiz+sizeof(M_HEAD);
80			p = (char *)free_list[bucket];
81			free_list[bucket] = free_list[bucket]->next;
82	greg	1.9	#ifdef MSTATS
83			b_nscrounged += *np;
84			#endif
85	greg	1.3	return(p);
86			}
87			*np = 0;
88			return(NULL);
89			}
90
91
92			char *
93	greg	1.1	bmalloc(n) /* allocate a block of n bytes, sans header */
94			register unsigned n;
95			{
96			extern char *sbrk();
97	greg	1.3	static unsigned pagesz = 0;
98			static unsigned amnt;
99	greg	1.1	static char *bpos;
100	greg	1.3	static unsigned nrem;
101			unsigned thisamnt;
102	greg	1.1	register char *p;
103
104			if (pagesz == 0) { /* initialize */
105	greg	1.2	pagesz = amnt = getpagesize();
106	greg	1.1	nrem = (int)sbrk(0); /* page align break */
107			nrem = pagesz - (nrem&(pagesz-1));
108			bpos = sbrk(nrem); /* word aligned! */
109			if ((int)bpos == -1)
110			return(NULL);
111			}
112
113			n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
114
115			if (n > nrem) { /* need more core */
116	greg	1.3	if (n > amnt) { /* big chunk */
117			thisamnt = (n+(pagesz-1))&~(pagesz-1);
118			if (thisamnt <= MAXINCR) /* increase amnt */
119			amnt = thisamnt;
120			} else
121			thisamnt = amnt;
122			p = sbrk(thisamnt);
123	greg	1.4	if ((int)p == -1) { /* uh-oh, ENOMEM */
124	greg	1.3	thisamnt = n; /* search free lists */
125			p = mscrounge(&thisamnt);
126			if (p == NULL) /* we're really out */
127			return(NULL);
128			}
129			if (p != bpos+nrem) { /* not an increment */
130	greg	1.4	bfree(bpos, nrem); /* free what we have */
131	greg	1.1	bpos = p;
132	greg	1.3	nrem = thisamnt;
133	greg	1.4	} else /* otherwise tack on */
134	greg	1.3	nrem += thisamnt;
135	greg	1.1	}
136			p = bpos;
137			bpos += n; /* advance */
138			nrem -= n;
139	greg	1.13	#ifdef MSTATS
140			b_nalloced += n;
141			#endif
142	greg	1.1	return(p);
143			}
144
145
146			bfree(p, n) /* free n bytes of random memory */
147	greg	1.2	register char *p;
148			register unsigned n;
149	greg	1.1	{
150			register int bucket;
151			register unsigned bsiz;
152	greg	1.9
153			#ifdef MSTATS
154			b_nfreed += n;
155			#endif
156	greg	1.4	/* align pointer */
157	greg	1.6	bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
158	greg	1.4	if (bsiz < BYTES_WORD) {
159			p += bsiz;
160			n -= bsiz;
161	greg	1.1	}
162	greg	1.4	/* fill big buckets first */
163			for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
164			bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
165			if (n >= bsiz+sizeof(M_HEAD)) {
166			((M_HEAD *)p)->next = free_list[bucket];
167			free_list[bucket] = (M_HEAD *)p;
168			p += bsiz+sizeof(M_HEAD);
169			n -= bsiz+sizeof(M_HEAD);
170			}
171	greg	1.1	}
172
173
174			char *
175			malloc(n) /* allocate n bytes of memory */
176			unsigned n;
177			{
178	greg	1.6	extern int errno;
179	greg	1.1	register M_HEAD *mp;
180			register int bucket;
181			register unsigned bsiz;
182	greg	1.10	/* don't return NULL on 0 request */
183			if (n == 0)
184			return(DUMMYLOC);
185	greg	1.2	/* find first bucket that fits */
186	greg	1.6	for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
187			bucket < NBUCKETS; bucket++, bsiz <<= 1)
188			if (bsiz >= n)
189			break;
190			if (bucket >= NBUCKETS) {
191			errno = EINVAL;
192			return(NULL);
193			}
194	greg	1.4	if (free_list[bucket] == NULL) { /* need more core */
195	greg	1.1	mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
196			if (mp == NULL)
197			return(NULL);
198	greg	1.4	} else { /* got it */
199	greg	1.1	mp = free_list[bucket];
200			free_list[bucket] = mp->next;
201			}
202	greg	1.13	#ifdef MSTATS
203			m_nalloced += bsiz + sizeof(M_HEAD);
204			m_nwasted += bsiz + sizeof(M_HEAD) - n;
205			#endif
206	greg	1.12	mp->a.magic = MAGIC; /* tag block */
207			mp->a.bucket = bucket;
208	greg	1.1	return((char *)(mp+1));
209			}
210
211
212			char *
213			realloc(op, n) /* reallocate memory using malloc() */
214	greg	1.6	register char *op;
215	greg	1.1	unsigned n;
216			{
217	greg	1.6	char *p;
218	greg	1.1	register unsigned on;
219	greg	1.6	/* get old size */
220	greg	1.12	if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
221			on = 1 << ((M_HEAD *)op-1)->a.bucket;
222	greg	1.5	else
223			on = 0;
224	greg	1.6	if (n <= on && (n > on>>1 \|\| on == 1<<FIRSTBUCKET))
225	greg	1.5	return(op); /* same bucket */
226	greg	1.13	if ((p = malloc(n)) == NULL)
227			return(NULL);
228			if (on) {
229	greg	1.1	#ifdef BSD
230	greg	1.2	bcopy(op, p, n>on ? on : n);
231	greg	1.1	#else
232	greg	1.2	(void)memcpy(p, op, n>on ? on : n);
233	greg	1.1	#endif
234	greg	1.13	free(op);
235			}
236	greg	1.1	return(p);
237			}
238
239
240			free(p) /* free memory allocated by malloc */
241			char *p;
242			{
243			register M_HEAD *mp;
244			register int bucket;
245
246	greg	1.10	if (p == NULL \|\| p == DUMMYLOC)
247	greg	1.13	return(1);
248	greg	1.1	mp = (M_HEAD *)p - 1;
249	greg	1.12	if (mp->a.magic != MAGIC) /* sanity check */
250	greg	1.13	return(0);
251	greg	1.12	bucket = mp->a.bucket;
252	greg	1.1	mp->next = free_list[bucket];
253			free_list[bucket] = mp;
254	greg	1.9	#ifdef MSTATS
255			m_nfreed += (1 << bucket) + sizeof(M_HEAD);
256			#endif
257	greg	1.13	return(1);
258	greg	1.1	}
259
260
261			#ifndef NOVMEM
262			#ifndef BSD
263			#include <sys/var.h>
264			int
265			getpagesize() /* use SYSV var structure to get page size */
266			{
267			struct var v;
268
269	greg	1.8	uvar(&v);
270			return(1 << v.v_pageshift);
271	greg	1.1	}
272			#endif
273	greg	1.9	#endif
274
275
276			#ifdef MSTATS
277			printmemstats(fp) /* print memory statistics to stream */
278			FILE *fp;
279			{
280			register int i;
281			int n;
282			register M_HEAD *mp;
283			unsigned int total = 0;
284
285			fprintf(fp, "Memory statistics:\n");
286			fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
287			fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
288			fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
289			fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
290			fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
291			100.0*m_nwasted/m_nalloced);
292			fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
293			for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
294			n = 0;
295			for (mp = free_list[i]; mp != NULL; mp = mp->next)
296			n++;
297			if (n) {
298			fprintf(fp, "\t%d * %u\n", n, 1<<i);
299			total += n * ((1<<i) + sizeof(M_HEAD));
300			}
301			}
302			fprintf(fp, "\t %u total bytes in free list\n", total);
303			}
304	greg	1.1	#endif