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.
 * bmalloc() doesn't keep track of free lists -- it's basically
 *      just a buffered call to sbrk().
 * bfree() puts memory from any source into malloc() free lists.
 * malloc(), realloc() and free() use buckets
 *      containing blocks in powers of two, similar to CIT routines.
 *
 *      Greg Ward       Lawrence Berkeley Laboratory
 */

#define  NULL           0

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

#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 *
bmalloc(n)              /* allocate a block of n bytes, sans header */
register unsigned  n;
{
        extern char  *sbrk();
        static int  pagesz = 0;
        static int  amnt;
        static char  *bpos;
        static int  nrem;
        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)                   /* increase amount */
                        amnt = (n+(pagesz-1))&~(pagesz-1);
                p = sbrk(amnt);
                if ((int)p == -1)
                        return(NULL);
                if (p != bpos+nrem) {           /* someone called sbrk()! */
                        bfree(bpos, nrem);
                        bpos = p;
                        nrem = amnt;
                } else
                        nrem += amnt;
        }
        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;
                                        /* find largest bucket */
        bucket = 0;
        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
                bucket++;
        while (bucket > FIRSTBUCKET) {
                bsiz >>= 1;
                bucket--;
                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
                        continue;
                ((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) {
                mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
                if (mp == NULL)
                        return(NULL);
        } else {
                mp = free_list[bucket];
                free_list[bucket] = mp->next;
        }
        mp->bucket = bucket;
        return((char *)(mp+1));
}


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

        if (op != NULL)
                on = 1 << ((M_HEAD *)op-1)->bucket;
        else
                on = 0;
        if (n <= on && n > on>>1)
                return(op);             /* same bucket */
        p = malloc(n);
        if (p != NULL)
#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)
                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.2
Committed:	Tue Sep 25 18:56:37 1990 UTC (33 years, 7 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.1:	+14 -12 lines
Log Message:	minor cleanup changes
#	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			* bmalloc() doesn't keep track of free lists -- it's basically
11			* just a buffered call to sbrk().
12			* bfree() puts memory from any source into malloc() free lists.
13			* malloc(), realloc() and free() use buckets
14			* containing blocks in powers of two, similar to CIT routines.
15			*
16			* Greg Ward Lawrence Berkeley Laboratory
17			*/
18
19			#define NULL 0
20
21			#ifndef ALIGN
22			#define ALIGN int /* align type */
23			#endif
24			#define BYTES_WORD sizeof(ALIGN)
25
26			#ifdef NOVMEM
27			#define getpagesize() BYTES_WORD
28			#endif
29
30			/* malloc free lists */
31			typedef union m_head {
32			union m_head *next;
33			int bucket;
34			ALIGN dummy;
35			} M_HEAD;
36
37			#define FIRSTBUCKET 3
38			#define NBUCKETS 30
39
40			static M_HEAD *free_list[NBUCKETS];
41
42
43			char *
44			bmalloc(n) /* allocate a block of n bytes, sans header */
45			register unsigned n;
46			{
47			extern char *sbrk();
48			static int pagesz = 0;
49			static int amnt;
50			static char *bpos;
51			static int nrem;
52			register char *p;
53
54			if (pagesz == 0) { /* initialize */
55	greg	1.2	pagesz = amnt = getpagesize();
56	greg	1.1	nrem = (int)sbrk(0); /* page align break */
57			nrem = pagesz - (nrem&(pagesz-1));
58			bpos = sbrk(nrem); /* word aligned! */
59			if ((int)bpos == -1)
60			return(NULL);
61			}
62
63			n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
64
65			if (n > nrem) { /* need more core */
66			if (n > amnt) /* increase amount */
67			amnt = (n+(pagesz-1))&~(pagesz-1);
68			p = sbrk(amnt);
69			if ((int)p == -1)
70			return(NULL);
71			if (p != bpos+nrem) { /* someone called sbrk()! */
72			bfree(bpos, nrem);
73			bpos = p;
74			nrem = amnt;
75			} else
76			nrem += amnt;
77			}
78			p = bpos;
79			bpos += n; /* advance */
80			nrem -= n;
81			return(p);
82			}
83
84
85			bfree(p, n) /* free n bytes of random memory */
86	greg	1.2	register char *p;
87			register unsigned n;
88	greg	1.1	{
89			register int bucket;
90			register unsigned bsiz;
91			/* find largest bucket */
92			bucket = 0;
93			for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
94			bucket++;
95			while (bucket > FIRSTBUCKET) {
96			bsiz >>= 1;
97			bucket--;
98			if (n < bsiz+sizeof(M_HEAD)) /* nothing for this bucket */
99			continue;
100	greg	1.2	((M_HEAD *)p)->next = free_list[bucket];
101			free_list[bucket] = (M_HEAD *)p;
102			p += bsiz+sizeof(M_HEAD);
103	greg	1.1	n -= bsiz+sizeof(M_HEAD);
104			}
105			}
106
107
108			char *
109			malloc(n) /* allocate n bytes of memory */
110			unsigned n;
111			{
112			register M_HEAD *mp;
113			register int bucket;
114			register unsigned bsiz;
115
116	greg	1.2	if (n == 0)
117			return(NULL);
118			/* find first bucket that fits */
119	greg	1.1	bucket = FIRSTBUCKET;
120			for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
121			bucket++;
122			if (free_list[bucket] == NULL) {
123			mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
124			if (mp == NULL)
125			return(NULL);
126			} else {
127			mp = free_list[bucket];
128			free_list[bucket] = mp->next;
129			}
130			mp->bucket = bucket;
131			return((char *)(mp+1));
132			}
133
134
135			char *
136			realloc(op, n) /* reallocate memory using malloc() */
137			char *op;
138			unsigned n;
139			{
140			register char *p;
141			register unsigned on;
142
143			if (op != NULL)
144			on = 1 << ((M_HEAD *)op-1)->bucket;
145			else
146			on = 0;
147			if (n <= on && n > on>>1)
148			return(op); /* same bucket */
149			p = malloc(n);
150	greg	1.2	if (p != NULL)
151	greg	1.1	#ifdef BSD
152	greg	1.2	bcopy(op, p, n>on ? on : n);
153	greg	1.1	#else
154	greg	1.2	(void)memcpy(p, op, n>on ? on : n);
155	greg	1.1	#endif
156			free(op);
157			return(p);
158			}
159
160
161			free(p) /* free memory allocated by malloc */
162			char *p;
163			{
164			register M_HEAD *mp;
165			register int bucket;
166
167	greg	1.2	if (p == NULL)
168			return;
169	greg	1.1	mp = (M_HEAD *)p - 1;
170			bucket = mp->bucket;
171			mp->next = free_list[bucket];
172			free_list[bucket] = mp;
173			}
174
175
176			#ifndef NOVMEM
177			#ifndef BSD
178			#include <sys/var.h>
179			int
180			getpagesize() /* use SYSV var structure to get page size */
181			{
182			static int pagesz = 0;
183			struct var v;
184
185			if (pagesz == 0) {
186			uvar(&v);
187			pagesz = 1 << v.v_pageshift;
188			}
189			return(pagesz);
190			}
191			#endif
192			#endif