src/common/malloc.c

/* Copyright (c) 1990 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 memory it can find to satisfy the
 *      request along with the number of bytes (modified).
 *
 *      Greg Ward       Lawrence Berkeley Laboratory
 */

#define  NULL           0

#ifndef ALIGN
#define  ALIGN          int                     /* align type */
#endif
#define  BYTES_WORD     sizeof(ALIGN)

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

#ifdef  NOVMEM
#define  getpagesize()  BYTES_WORD
#endif
                                        /* malloc free lists */
typedef union m_head {
        union m_head    *next;
        int             bucket;
        ALIGN           dummy;
} M_HEAD;

#define FIRSTBUCKET     3
#define NBUCKETS        30

static M_HEAD   *free_list[NBUCKETS];


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;
                        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;
        return(p);
}


bfree(p, n)                     /* free n bytes of random memory */
register char  *p;
register unsigned  n;
{
        register int    bucket;
        register unsigned       bsiz;
                                        /* 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;
{
        register M_HEAD *mp;
        register int    bucket;
        register unsigned       bsiz;

        if (n == 0)
                return(NULL);
                                        /* find first bucket that fits */
        bucket = FIRSTBUCKET;
        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
                bucket++;
        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;
        }
        mp->bucket = bucket;                    /* tag block */
        return((char *)(mp+1));
}


char *
realloc(op, n)                  /* reallocate memory using malloc() */
char    *op;
unsigned        n;
{
        extern char     *memcpy();
        register char   *p;
        register unsigned       on;

        free(op);                       /* free it first */
        p = malloc(n);                  /* p==op if same bucket */
        if (p == NULL)
                return(NULL);
        if (p != op)                    /* different bucket, do copy */
#ifdef  BSD
                bcopy(op, p, n>on ? on : n);
#else
                (void)memcpy(p, op, n>on ? on : n);
#endif
        return(p);
}


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

        if (p == NULL)
                return;
        mp = (M_HEAD *)p - 1;
        bucket = mp->bucket;
        mp->next = free_list[bucket];
        free_list[bucket] = mp;
}


#ifndef NOVMEM
#ifndef BSD
#include <sys/var.h>
int
getpagesize()                   /* use SYSV var structure to get page size */
{
        static int  pagesz = 0;
        struct var  v;

        if (pagesz == 0) {
                uvar(&v);
                pagesz = 1 << v.v_pageshift;
        }
        return(pagesz);
}
#endif
#endif
Revision:	1.4
Committed:	Wed Sep 26 08:26:11 1990 UTC (33 years, 7 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.3:	+31 -33 lines
Log Message:	minor improvements to bfree() and realloc()
#	User	Rev	Content
1	greg	1.1	/* Copyright (c) 1990 Regents of the University of California */
2
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			* mscrounge() returns whatever memory it can find to satisfy the
17			* request along with the number of bytes (modified).
18	greg	1.1	*
19			* Greg Ward Lawrence Berkeley Laboratory
20			*/
21
22			#define NULL 0
23
24			#ifndef ALIGN
25			#define ALIGN int /* align type */
26			#endif
27			#define BYTES_WORD sizeof(ALIGN)
28
29	greg	1.3	#define MAXINCR (1<<18) /* largest sbrk(2) increment */
30
31	greg	1.1	#ifdef NOVMEM
32			#define getpagesize() BYTES_WORD
33			#endif
34			/* malloc free lists */
35			typedef union m_head {
36			union m_head *next;
37			int bucket;
38			ALIGN dummy;
39			} M_HEAD;
40
41			#define FIRSTBUCKET 3
42			#define NBUCKETS 30
43
44			static M_HEAD *free_list[NBUCKETS];
45
46
47			char *
48	greg	1.4	mscrounge(np) /* search free lists to satisfy request */
49	greg	1.3	register unsigned *np;
50			{
51			char *p;
52			register int bucket;
53			register unsigned bsiz;
54
55			for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
56			bucket < NBUCKETS; bucket++, bsiz <<= 1)
57			if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
58			*np = bsiz+sizeof(M_HEAD);
59			p = (char *)free_list[bucket];
60			free_list[bucket] = free_list[bucket]->next;
61			return(p);
62			}
63			*np = 0;
64			return(NULL);
65			}
66
67
68			char *
69	greg	1.1	bmalloc(n) /* allocate a block of n bytes, sans header */
70			register unsigned n;
71			{
72			extern char *sbrk();
73	greg	1.3	static unsigned pagesz = 0;
74			static unsigned amnt;
75	greg	1.1	static char *bpos;
76	greg	1.3	static unsigned nrem;
77			unsigned thisamnt;
78	greg	1.1	register char *p;
79
80			if (pagesz == 0) { /* initialize */
81	greg	1.2	pagesz = amnt = getpagesize();
82	greg	1.1	nrem = (int)sbrk(0); /* page align break */
83			nrem = pagesz - (nrem&(pagesz-1));
84			bpos = sbrk(nrem); /* word aligned! */
85			if ((int)bpos == -1)
86			return(NULL);
87			}
88
89			n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
90
91			if (n > nrem) { /* need more core */
92	greg	1.3	if (n > amnt) { /* big chunk */
93			thisamnt = (n+(pagesz-1))&~(pagesz-1);
94			if (thisamnt <= MAXINCR) /* increase amnt */
95			amnt = thisamnt;
96			} else
97			thisamnt = amnt;
98			p = sbrk(thisamnt);
99	greg	1.4	if ((int)p == -1) { /* uh-oh, ENOMEM */
100	greg	1.3	thisamnt = n; /* search free lists */
101			p = mscrounge(&thisamnt);
102			if (p == NULL) /* we're really out */
103			return(NULL);
104			}
105			if (p != bpos+nrem) { /* not an increment */
106	greg	1.4	bfree(bpos, nrem); /* free what we have */
107	greg	1.1	bpos = p;
108	greg	1.3	nrem = thisamnt;
109	greg	1.4	} else /* otherwise tack on */
110	greg	1.3	nrem += thisamnt;
111	greg	1.1	}
112			p = bpos;
113			bpos += n; /* advance */
114			nrem -= n;
115			return(p);
116			}
117
118
119			bfree(p, n) /* free n bytes of random memory */
120	greg	1.2	register char *p;
121			register unsigned n;
122	greg	1.1	{
123			register int bucket;
124			register unsigned bsiz;
125	greg	1.4	/* align pointer */
126			bsiz = BYTES_WORD - ((unsigned)p&~(BYTES_WORD-1));
127			if (bsiz < BYTES_WORD) {
128			p += bsiz;
129			n -= bsiz;
130	greg	1.1	}
131	greg	1.4	/* fill big buckets first */
132			for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
133			bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
134			if (n >= bsiz+sizeof(M_HEAD)) {
135			((M_HEAD *)p)->next = free_list[bucket];
136			free_list[bucket] = (M_HEAD *)p;
137			p += bsiz+sizeof(M_HEAD);
138			n -= bsiz+sizeof(M_HEAD);
139			}
140	greg	1.1	}
141
142
143			char *
144			malloc(n) /* allocate n bytes of memory */
145			unsigned n;
146			{
147			register M_HEAD *mp;
148			register int bucket;
149			register unsigned bsiz;
150
151	greg	1.2	if (n == 0)
152			return(NULL);
153			/* find first bucket that fits */
154	greg	1.1	bucket = FIRSTBUCKET;
155			for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
156			bucket++;
157	greg	1.4	if (free_list[bucket] == NULL) { /* need more core */
158	greg	1.1	mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
159			if (mp == NULL)
160			return(NULL);
161	greg	1.4	} else { /* got it */
162	greg	1.1	mp = free_list[bucket];
163			free_list[bucket] = mp->next;
164			}
165	greg	1.4	mp->bucket = bucket; /* tag block */
166	greg	1.1	return((char *)(mp+1));
167			}
168
169
170			char *
171			realloc(op, n) /* reallocate memory using malloc() */
172			char *op;
173			unsigned n;
174			{
175	greg	1.4	extern char *memcpy();
176	greg	1.1	register char *p;
177			register unsigned on;
178
179	greg	1.4	free(op); /* free it first */
180			p = malloc(n); /* p==op if same bucket */
181			if (p == NULL)
182			return(NULL);
183			if (p != op) /* different bucket, do copy */
184	greg	1.1	#ifdef BSD
185	greg	1.2	bcopy(op, p, n>on ? on : n);
186	greg	1.1	#else
187	greg	1.2	(void)memcpy(p, op, n>on ? on : n);
188	greg	1.1	#endif
189			return(p);
190			}
191
192
193			free(p) /* free memory allocated by malloc */
194			char *p;
195			{
196			register M_HEAD *mp;
197			register int bucket;
198
199	greg	1.2	if (p == NULL)
200			return;
201	greg	1.1	mp = (M_HEAD *)p - 1;
202			bucket = mp->bucket;
203			mp->next = free_list[bucket];
204			free_list[bucket] = mp;
205			}
206
207
208			#ifndef NOVMEM
209			#ifndef BSD
210			#include <sys/var.h>
211			int
212			getpagesize() /* use SYSV var structure to get page size */
213			{
214			static int pagesz = 0;
215			struct var v;
216
217			if (pagesz == 0) {
218			uvar(&v);
219			pagesz = 1 << v.v_pageshift;
220			}
221			return(pagesz);
222			}
223			#endif
224			#endif