ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/common/malloc.c

Comparing ray/src/common/malloc.c (file contents):
Revision 1.3 by greg, Wed Sep 26 06:23:10 1990 UTC vs.
Revision 1.12 by greg, Tue Apr 2 09:36:21 1991 UTC

#	Line 1 | Line 1
1	<	/* Copyright (c) 1990 Regents of the University of California */
1	>	/* Copyright (c) 1991 Regents of the University of California */
2
3		#ifndef lint
4		static char SCCSid[] = "$SunId$ LBL";
#	Line 7 | Line 7 | static char SCCSid[] = "$SunId$ LBL";
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(2).  However, bmalloc will
12	–	*      call mscrounge() if sbrk fails.
13	–	* bfree() puts memory from any source into malloc free lists.
10		* malloc(), realloc() and free() use buckets
11		*      containing blocks in powers of two, similar to CIT routines.
12	<	* mscrounge() returns whatever memory it can find to satisfy the
12	>	* bfree() puts memory from any source into malloc free lists.
13	>	* bmalloc() doesn't keep track of free lists -- it's usually
14	>	*      just a buffered call to sbrk(2).  However, bmalloc will
15	>	*      call mscrounge() if sbrk fails.
16	>	* mscrounge() returns whatever free memory it can find to satisfy the
17		*      request along with the number of bytes (modified).
18		*
19		*      Greg Ward       Lawrence Berkeley Laboratory
20		*/
21
22	+	#include  <errno.h>
23	+
24	+	#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		#define  NULL           0
34	+	#endif
35
36		#ifndef ALIGN
37		#define  ALIGN          int                     /* align type */
38		#endif
39		#define  BYTES_WORD     sizeof(ALIGN)
40
41	<	#define  MAXINCR        (1<<18)                 /* largest sbrk(2) increment */
41	>	#define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42
43		#ifdef  NOVMEM
44	<	#define  getpagesize()  BYTES_WORD
44	>	#define  getpagesize()  1024
45		#endif
46		/* malloc free lists */
47		typedef union m_head {
48		union m_head    *next;
49	<	int             bucket;
49	>	struct {
50	>	short           magic;
51	>	short           bucket;
52	>	}       a;
53		ALIGN           dummy;
54		} M_HEAD;
55
56	+	#define MAGIC           0x1a2           /* magic number for allocated memory */
57	+
58		#define FIRSTBUCKET     3
59		#define NBUCKETS        30
60
61		static M_HEAD   *free_list[NBUCKETS];
62
63	+	static ALIGN    dummy_mem;
64
65	+	#define DUMMYLOC        ((char *)&dummy_mem)
66	+
67	+
68		char *
69	<	mscrounge(np)           /* search free lists trying to satisfy request */
69	>	mscrounge(np)           /* search free lists to satisfy request */
70		register unsigned       *np;
71		{
72		char    *p;
#	Line 58 | Line 79 | register unsigned      *np;
79		*np = bsiz+sizeof(M_HEAD);
80		p = (char *)free_list[bucket];
81		free_list[bucket] = free_list[bucket]->next;
82	+	#ifdef MSTATS
83	+	b_nscrounged += *np;
84	+	#endif
85		return(p);
86		}
87		*np = 0;
#	Line 77 | Line 101 | register unsigned  n;
101		unsigned  thisamnt;
102		register char   *p;
103
104	+	#ifdef MSTATS
105	+	b_nalloced += n;
106	+	#endif
107		if (pagesz == 0) {                              /* initialize */
108		pagesz = amnt = getpagesize();
109		nrem = (int)sbrk(0);                    /* page align break */
#	Line 96 | Line 123 | register unsigned  n;
123		} else
124		thisamnt = amnt;
125		p = sbrk(thisamnt);
126	<	if ((int)p == -1) {                     /* uh-oh */
126	>	if ((int)p == -1) {                     /* uh-oh, ENOMEM */
127		thisamnt = n;                   /* search free lists */
128		p = mscrounge(&thisamnt);
129		if (p == NULL)                  /* we're really out */
130		return(NULL);
131		}
132		if (p != bpos+nrem) {                   /* not an increment */
133	<	bfree(bpos, nrem);
133	>	bfree(bpos, nrem);              /* free what we have */
134		bpos = p;
135		nrem = thisamnt;
136	<	} else
136	>	} else                                  /* otherwise tack on */
137		nrem += thisamnt;
138		}
139		p = bpos;
#	Line 122 | Line 149 | register unsigned  n;
149		{
150		register int    bucket;
151		register unsigned       bsiz;
152	<	/* find largest bucket */
153	<	bucket = 0;
154	<	for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
155	<	bucket++;
156	<	while (bucket > FIRSTBUCKET) {
157	<	bsiz >>= 1;
158	<	bucket--;
159	<	if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
160	<	continue;
134	<	((M_HEAD *)p)->next = free_list[bucket];
135	<	free_list[bucket] = (M_HEAD *)p;
136	<	p += bsiz+sizeof(M_HEAD);
137	<	n -= bsiz+sizeof(M_HEAD);
152	>
153	>	#ifdef MSTATS
154	>	b_nfreed += n;
155	>	#endif
156	>	/* align pointer */
157	>	bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
158	>	if (bsiz < BYTES_WORD) {
159	>	p += bsiz;
160	>	n -= bsiz;
161		}
162	+	/* 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		}
172
173
#	Line 143 | Line 175 | char *
175		malloc(n)                       /* allocate n bytes of memory */
176		unsigned        n;
177		{
178	+	extern int  errno;
179		register M_HEAD *mp;
180		register int    bucket;
181		register unsigned       bsiz;
182	<
182	>	/* don't return NULL on 0 request */
183		if (n == 0)
184	<	return(NULL);
184	>	return(DUMMYLOC);
185		/* find first bucket that fits */
186	<	bucket = FIRSTBUCKET;
187	<	for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
188	<	bucket++;
189	<	if (free_list[bucket] == NULL) {
186	>	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	>	#ifdef MSTATS
195	>	m_nalloced += bsiz + sizeof(M_HEAD);
196	>	m_nwasted += bsiz + sizeof(M_HEAD) - n;
197	>	#endif
198	>	if (free_list[bucket] == NULL) {        /* need more core */
199		mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
200		if (mp == NULL)
201		return(NULL);
202	<	} else {
202	>	} else {                                /* got it */
203		mp = free_list[bucket];
204		free_list[bucket] = mp->next;
205		}
206	<	mp->bucket = bucket;
206	>	mp->a.magic = MAGIC;                    /* tag block */
207	>	mp->a.bucket = bucket;
208		return((char *)(mp+1));
209		}
210
211
212		char *
213		realloc(op, n)                  /* reallocate memory using malloc() */
214	<	char    *op;
214	>	register char   *op;
215		unsigned        n;
216		{
217	<	register char   *p;
217	>	char    *p;
218		register unsigned       on;
219	<
220	<	if (op != NULL)
221	<	on = 1 << ((M_HEAD *)op-1)->bucket;
219	>	/* get old size */
220	>	if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
221	>	on = 1 << ((M_HEAD *)op-1)->a.bucket;
222		else
223		on = 0;
224	<	if (n <= on && n > on>>1)
224	>	if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
225		return(op);             /* same bucket */
226		p = malloc(n);
227		if (p != NULL)
#	Line 198 | Line 241 | char   *p;
241		register M_HEAD *mp;
242		register int    bucket;
243
244	<	if (p == NULL)
244	>	if (p == NULL || p == DUMMYLOC)
245		return;
246		mp = (M_HEAD *)p - 1;
247	<	bucket = mp->bucket;
247	>	if (mp->a.magic != MAGIC)               /* sanity check */
248	>	return;
249	>	bucket = mp->a.bucket;
250		mp->next = free_list[bucket];
251		free_list[bucket] = mp;
252	+	#ifdef MSTATS
253	+	m_nfreed += (1 << bucket) + sizeof(M_HEAD);
254	+	#endif
255		}
256
257
#	Line 213 | Line 261 | char   *p;
261		int
262		getpagesize()                   /* use SYSV var structure to get page size */
263		{
216	–	static int  pagesz = 0;
264		struct var  v;
265
266	<	if (pagesz == 0) {
267	<	uvar(&v);
221	<	pagesz = 1 << v.v_pageshift;
222	<	}
223	<	return(pagesz);
266	>	uvar(&v);
267	>	return(1 << v.v_pageshift);
268		}
269		#endif
270	+	#endif
271	+
272	+
273	+	#ifdef MSTATS
274	+	printmemstats(fp)               /* print memory statistics to stream */
275	+	FILE    *fp;
276	+	{
277	+	register int    i;
278	+	int     n;
279	+	register M_HEAD *mp;
280	+	unsigned int    total = 0;
281	+
282	+	fprintf(fp, "Memory statistics:\n");
283	+	fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
284	+	fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
285	+	fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
286	+	fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
287	+	fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
288	+	100.0*m_nwasted/m_nalloced);
289	+	fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
290	+	for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
291	+	n = 0;
292	+	for (mp = free_list[i]; mp != NULL; mp = mp->next)
293	+	n++;
294	+	if (n) {
295	+	fprintf(fp, "\t%d * %u\n", n, 1<<i);
296	+	total += n * ((1<<i) + sizeof(M_HEAD));
297	+	}
298	+	}
299	+	fprintf(fp, "\t %u total bytes in free list\n", total);
300	+	}
301		#endif

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)