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.1 by greg, Tue Sep 25 17:14:04 1990 UTC vs.
Revision 1.14 by greg, Mon Aug 26 10:12:24 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().
12	–	* 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	+	* 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	+	* 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		*
22		*      Greg Ward       Lawrence Berkeley Laboratory
23		*/
24
25	+	#include  <errno.h>
26	+
27	+	#ifdef MSTATS
28	+	#include  <stdio.h>
29	+	static unsigned b_nsbrked = 0;
30	+	static unsigned b_nalloced = 0;
31	+	static unsigned b_nfreed = 0;
32	+	static unsigned b_nscrounged = 0;
33	+	static unsigned b_ncompacted = 0;
34	+	static unsigned m_nalloced = 0;
35	+	static unsigned m_nfreed = 0;
36	+	static unsigned m_nwasted = 0;
37	+	#else
38		#define  NULL           0
39	+	#endif
40
41		#ifndef ALIGN
42		#define  ALIGN          int                     /* align type */
43		#endif
44		#define  BYTES_WORD     sizeof(ALIGN)
45
46	+	#define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
47	+
48		#ifdef  NOVMEM
49	<	#define  getpagesize()  BYTES_WORD
49	>	#define  getpagesize()  1024
50		#endif
29	–
51		/* malloc free lists */
52		typedef union m_head {
53		union m_head    *next;
54	<	int             bucket;
54	>	struct {
55	>	short           magic;
56	>	short           bucket;
57	>	}       a;
58		ALIGN           dummy;
59		} M_HEAD;
60
61	+	#define MAGIC           0x1a2           /* magic number for allocated memory */
62	+
63		#define FIRSTBUCKET     3
64		#define NBUCKETS        30
65
66		static M_HEAD   *free_list[NBUCKETS];
67
68	+	static ALIGN    dummy_mem;
69
70	+	#define DUMMYLOC        ((char *)&dummy_mem)
71	+
72	+	#ifdef  MCOMP                   /* memory compaction routines */
73	+	static char     seedtab[1024];          /* seed for compaction table */
74	+
75	+	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		char *
146	+	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	+	mscrounge(np)           /* search free lists to satisfy request */
196	+	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	+	#ifdef MSTATS
209	+	b_nscrounged += *np;
210	+	#endif
211	+	return(p);
212	+	}
213	+	#ifdef MCOMP
214	+	return(mcompact(np));           /* try compaction */
215	+	#else
216	+	*np = 0;
217	+	return(NULL);
218	+	#endif
219	+	}
220	+
221	+
222	+	char *
223		bmalloc(n)              /* allocate a block of n bytes, sans header */
224		register unsigned  n;
225		{
226		extern char  *sbrk();
227	<	static int  pagesz = 0;
228	<	static int  amnt;
227	>	static unsigned  pagesz = 0;
228	>	static unsigned  amnt;
229		static char  *bpos;
230	<	static int  nrem;
230	>	static unsigned  nrem;
231	>	unsigned  thisamnt;
232		register char   *p;
233
234		if (pagesz == 0) {                              /* initialize */
235	<	amnt = pagesz = getpagesize();
235	>	pagesz = amnt = getpagesize();
236		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	+	#ifdef MSTATS
242	+	b_nsbrked += nrem;
243	+	#endif
244		}
245
246		n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
247
248		if (n > nrem) {                                 /* need more core */
249	<	if (n > amnt)                   /* increase amount */
250	<	amnt = (n+(pagesz-1))&~(pagesz-1);
251	<	p = sbrk(amnt);
252	<	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;
249	>	if (n > amnt) {                         /* big chunk */
250	>	thisamnt = (n+(pagesz-1))&~(pagesz-1);
251	>	if (thisamnt <= MAXINCR)        /* increase amnt */
252	>	amnt = thisamnt;
253		} else
254	<	nrem += amnt;
254	>	thisamnt = amnt;
255	>	p = sbrk(thisamnt);
256	>	if ((int)p == -1) {                     /* uh-oh, ENOMEM */
257	>	thisamnt = n;                   /* search free lists */
258	>	p = mscrounge(&thisamnt);
259	>	if (p == NULL)                  /* we're really out */
260	>	return(NULL);
261	>	}
262	>	#ifdef MSTATS
263	>	else b_nsbrked += thisamnt;
264	>	#endif
265	>	if (p != bpos+nrem) {                   /* not an increment */
266	>	bfree(bpos, nrem);              /* free what we have */
267	>	bpos = p;
268	>	nrem = thisamnt;
269	>	} else                                  /* otherwise tack on */
270	>	nrem += thisamnt;
271		}
272		p = bpos;
273		bpos += n;                                      /* advance */
274		nrem -= n;
275	+	#ifdef MSTATS
276	+	b_nalloced += n;
277	+	#endif
278		return(p);
279		}
280
281
282		bfree(p, n)                     /* free n bytes of random memory */
283	<	char  *p;
284	<	unsigned  n;
283	>	register char  *p;
284	>	register unsigned  n;
285		{
89	–	register M_HEAD *mp;
286		register int    bucket;
287		register unsigned       bsiz;
288	<	/* find largest bucket */
289	<	bucket = 0;
290	<	for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
291	<	bucket++;
292	<	mp = (M_HEAD *)p;
293	<	while (bucket > FIRSTBUCKET) {
294	<	bsiz >>= 1;
295	<	bucket--;
296	<	if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
101	<	continue;
102	<	mp->next = free_list[bucket];
103	<	free_list[bucket] = mp;
104	<	(char *)mp += bsiz+sizeof(M_HEAD);
105	<	n -= bsiz+sizeof(M_HEAD);
288	>
289	>	#ifdef MSTATS
290	>	b_nfreed += n;
291	>	#endif
292	>	/* align pointer */
293	>	bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
294	>	if (bsiz < BYTES_WORD) {
295	>	p += bsiz;
296	>	n -= bsiz;
297		}
298	+	/* fill big buckets first */
299	+	for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
300	+	bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
301	+	if (n >= bsiz+sizeof(M_HEAD)) {
302	+	((M_HEAD *)p)->next = free_list[bucket];
303	+	free_list[bucket] = (M_HEAD *)p;
304	+	p += bsiz+sizeof(M_HEAD);
305	+	n -= bsiz+sizeof(M_HEAD);
306	+	}
307		}
308
309
#	Line 111 | Line 311 | char *
311		malloc(n)                       /* allocate n bytes of memory */
312		unsigned        n;
313		{
314	+	extern int  errno;
315		register M_HEAD *mp;
316		register int    bucket;
317		register unsigned       bsiz;
318	<
319	<	bucket = FIRSTBUCKET;
320	<	for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
321	<	bucket++;
322	<	if (free_list[bucket] == NULL) {
318	>	/* don't return NULL on 0 request */
319	>	if (n == 0)
320	>	return(DUMMYLOC);
321	>	/* find first bucket that fits */
322	>	for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
323	>	bucket < NBUCKETS; bucket++, bsiz <<= 1)
324	>	if (bsiz >= n)
325	>	break;
326	>	if (bucket >= NBUCKETS) {
327	>	errno = EINVAL;
328	>	return(NULL);
329	>	}
330	>	if (free_list[bucket] == NULL) {        /* need more core */
331		mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
332		if (mp == NULL)
333		return(NULL);
334	<	} else {
334	>	} else {                                /* got it */
335		mp = free_list[bucket];
336		free_list[bucket] = mp->next;
337		}
338	<	mp->bucket = bucket;
338	>	#ifdef MSTATS
339	>	m_nalloced += bsiz + sizeof(M_HEAD);
340	>	m_nwasted += bsiz + sizeof(M_HEAD) - n;
341	>	#endif
342	>	mp->a.magic = MAGIC;                    /* tag block */
343	>	mp->a.bucket = bucket;
344		return((char *)(mp+1));
345		}
346
347
348		char *
349		realloc(op, n)                  /* reallocate memory using malloc() */
350	<	char    *op;
350	>	register char   *op;
351		unsigned        n;
352		{
353	<	register char   *p;
353	>	char    *p;
354		register unsigned       on;
355	<
356	<	if (op != NULL)
357	<	on = 1 << ((M_HEAD *)op-1)->bucket;
355	>	/* get old size */
356	>	if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
357	>	on = 1 << ((M_HEAD *)op-1)->a.bucket;
358		else
359		on = 0;
360	<	if (n <= on && n > on>>1)
360	>	if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
361		return(op);             /* same bucket */
362	<	p = malloc(n);
149	<	if (p == NULL)
362	>	if ((p = malloc(n)) == NULL)
363		return(NULL);
364	+	if (on) {
365		#ifdef  BSD
366	<	bcopy(op, p, n>on ? on : n);
366	>	bcopy(op, p, n>on ? on : n);
367		#else
368	<	(void)memcpy(p, op, n>on ? on : n);
368	>	(void)memcpy(p, op, n>on ? on : n);
369		#endif
370	<	free(op);
370	>	free(op);
371	>	}
372		return(p);
373		}
374
#	Line 164 | Line 379 | char   *p;
379		register M_HEAD *mp;
380		register int    bucket;
381
382	+	if (p == NULL || p == DUMMYLOC)
383	+	return(1);
384		mp = (M_HEAD *)p - 1;
385	<	bucket = mp->bucket;
385	>	if (mp->a.magic != MAGIC)               /* sanity check */
386	>	return(0);
387	>	bucket = mp->a.bucket;
388		mp->next = free_list[bucket];
389		free_list[bucket] = mp;
390	+	#ifdef MSTATS
391	+	m_nfreed += (1 << bucket) + sizeof(M_HEAD);
392	+	#endif
393	+	return(1);
394		}
395
396
#	Line 177 | Line 400 | char   *p;
400		int
401		getpagesize()                   /* use SYSV var structure to get page size */
402		{
180	–	static int  pagesz = 0;
403		struct var  v;
404
405	<	if (pagesz == 0) {
406	<	uvar(&v);
185	<	pagesz = 1 << v.v_pageshift;
186	<	}
187	<	return(pagesz);
405	>	uvar(&v);
406	>	return(1 << v.v_pageshift);
407		}
408		#endif
409	+	#endif
410	+
411	+
412	+	#ifdef MSTATS
413	+	printmemstats(fp)               /* print memory statistics to stream */
414	+	FILE    *fp;
415	+	{
416	+	register int    i;
417	+	int     n;
418	+	register M_HEAD *mp;
419	+	unsigned int    total = 0;
420	+
421	+	fprintf(fp, "Memory statistics:\n");
422	+	fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
423	+	fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
424	+	fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
425	+	fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
426	+	fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
427	+	fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
428	+	fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
429	+	100.0*m_nwasted/m_nalloced);
430	+	fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
431	+	for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
432	+	n = 0;
433	+	for (mp = free_list[i]; mp != NULL; mp = mp->next)
434	+	n++;
435	+	if (n) {
436	+	fprintf(fp, "\t%d * %u\n", n, 1<<i);
437	+	total += n * ((1<<i) + sizeof(M_HEAD));
438	+	}
439	+	}
440	+	fprintf(fp, "\t %u total bytes in free list\n", total);
441	+	}
442		#endif

Diff Legend

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