ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/malloc.c
Revision: 2.16
Committed: Mon Jun 30 14:59:11 2003 UTC (20 years, 9 months ago) by schorsch
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R6P1, rad3R6
Changes since 2.15: +5 -8 lines
Log Message:
Replaced most outdated BSD function calls with their posix equivalents, and cleaned up a few other platform dependencies.

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: malloc.c,v 2.15 2003/05/13 17:58:32 greg Exp $";
3 #endif
4 /*
5 * Fast malloc for memory hogs and VM environments.
6 * Performs a minimum of searching through free lists.
7 * malloc(), realloc() and free() use buckets
8 * containing blocks in powers of two, similar to CIT routines.
9 * bfree() puts memory from any source into malloc free lists.
10 * bmalloc() doesn't keep track of free lists -- it's usually
11 * just a buffered call to sbrk(2). However, bmalloc will
12 * call mscrounge() if sbrk fails.
13 * mscrounge() returns whatever free memory it can find to satisfy the
14 * request along with the number of bytes (modified).
15 * mcompact() takes the same arguments as mscrounge() (and is in fact
16 * called by mscrounge() under dire circumstances), but it uses
17 * memory compaction to return a larger block. (MCOMP)
18 *
19 * Greg Ward Lawrence Berkeley Laboratory
20 */
21
22 #include "copyright.h"
23
24 #include <errno.h>
25 #include <string.h>
26
27
28 #ifdef MSTATS
29 #include <stdio.h>
30 static unsigned b_nsbrked = 0;
31 static unsigned b_nalloced = 0;
32 static unsigned b_nfreed = 0;
33 static unsigned b_nscrounged = 0;
34 static unsigned b_ncompacted = 0;
35 static unsigned m_nalloced = 0;
36 static unsigned m_nfreed = 0;
37 static unsigned m_nwasted = 0;
38 #else
39 #define NULL 0
40 #endif
41
42 #ifndef ALIGNT
43 #define ALIGNT int /* align type */
44 #endif
45 #define BYTES_WORD sizeof(ALIGNT)
46
47 #ifndef MAXINCR
48 #define MAXINCR (1<<16) /* largest sbrk(2) increment */
49 #endif
50 /* malloc free lists */
51 typedef union m_head {
52 union m_head *next;
53 struct {
54 short magic;
55 short bucket;
56 } a;
57 ALIGNT dummy;
58 } M_HEAD;
59
60 #define MAGIC 0x1a2 /* magic number for allocated memory */
61
62 #define FIRSTBUCKET 3
63 #define NBUCKETS 30
64
65 static M_HEAD *free_list[NBUCKETS];
66
67 static ALIGNT dummy_mem;
68
69 static char *memlim[2];
70
71 #define DUMMYLOC ((char *)&dummy_mem)
72
73 #define BADPTR(p) ((p) < memlim[0] | (p) >= memlim[1])
74
75 #ifdef MCOMP /* memory compaction routines */
76 static char seedtab[1024]; /* seed for compaction table */
77
78 static struct mblk {
79 char *ptr; /* pointer to memory block */
80 unsigned siz; /* size of memory block */
81 } cptab = {seedtab, sizeof(seedtab)};
82
83 #define mtab(mb) ((struct mblk *)(mb)->ptr)
84 #define mtablen(mb) ((mb)->siz/sizeof(struct mblk))
85
86
87 static int
88 mbcmp(m1, m2) /* compare memory block locations */
89 register struct mblk *m1, *m2;
90 {
91 /* put empty blocks at end */
92 if (m1->siz == 0)
93 return(m2->siz == 0 ? 0 : 1);
94 if (m2->siz == 0)
95 return(-1);
96 /* otherwise, ascending order */
97 return(m1->ptr - m2->ptr);
98 }
99
100
101 int
102 compactfree() /* compact free lists (moving to table) */
103 {
104 register struct mblk *tp;
105 register int bucket;
106 unsigned n, bsiz, ncomp;
107 /* fill table from free lists */
108 tp = mtab(&cptab); n = mtablen(&cptab);
109 bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
110 ncomp = 0;
111 for ( ; ; ) {
112 while (tp->siz) { /* find empty slot */
113 if (--n == 0)
114 goto loopexit;
115 tp++;
116 }
117 while (free_list[bucket] == NULL) { /* find block */
118 if (--bucket < FIRSTBUCKET)
119 goto loopexit;
120 bsiz >>= 1;
121 }
122 tp->ptr = (char *)free_list[bucket];
123 ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
124 free_list[bucket] = free_list[bucket]->next;
125 }
126 loopexit:
127 if (ncomp == 0)
128 return(0); /* nothing new to compact */
129 #ifdef MSTATS
130 b_ncompacted += ncomp;
131 #endif
132 tp = mtab(&cptab); n = mtablen(&cptab); /* sort table */
133 qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
134 ncomp = 0; /* collect blocks */
135 while (--n && tp[1].siz) {
136 if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
137 tp[1].ptr = tp[0].ptr;
138 tp[1].siz += tp[0].siz;
139 ncomp += tp[0].siz;
140 tp[0].siz = 0;
141 }
142 tp++;
143 }
144 return(ncomp);
145 }
146
147
148 char *
149 mcompact(np) /* compact free lists to satisfy request */
150 unsigned *np;
151 {
152 struct mblk *tab;
153 unsigned tablen;
154 register struct mblk *bp, *big;
155
156 for ( ; ; ) {
157 /* compact free lists */
158 while (compactfree())
159 ;
160 /* find largest block */
161 tab = mtab(&cptab); tablen = mtablen(&cptab);
162 big = tab;
163 bp = tab + tablen;
164 while (--bp > tab)
165 if (bp->siz > big->siz)
166 big = bp;
167 if (big->siz >= *np) { /* big enough? */
168 *np = big->siz;
169 big->siz = 0; /* remove from table */
170 return(big->ptr); /* return it */
171 }
172 if (mtablen(big) <= tablen) {
173 *np = 0; /* cannot grow table */
174 return(NULL); /* report failure */
175 }
176 /* enlarge table, free old one */
177 mtab(big)[0].ptr = cptab.ptr;
178 mtab(big)[0].siz = cptab.siz;
179 cptab.ptr = big->ptr;
180 cptab.siz = big->siz;
181 big->siz = 0; /* clear and copy */
182 memcpy((char *)(mtab(&cptab)+1), (char *)tab,
183 tablen*sizeof(struct mblk));
184 memset((char *)(mtab(&cptab)+tablen+1), '\0',
185 (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
186 } /* next round */
187 }
188 #endif /* MCOMP */
189
190
191 char *
192 mscrounge(np) /* search free lists to satisfy request */
193 register unsigned *np;
194 {
195 char *p;
196 register int bucket;
197 register unsigned bsiz;
198
199 for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
200 bucket < NBUCKETS; bucket++, bsiz <<= 1)
201 if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
202 *np = bsiz+sizeof(M_HEAD);
203 p = (char *)free_list[bucket];
204 free_list[bucket] = free_list[bucket]->next;
205 #ifdef MSTATS
206 b_nscrounged += *np;
207 #endif
208 return(p);
209 }
210 #ifdef MCOMP
211 return(mcompact(np)); /* try compaction */
212 #else
213 *np = 0;
214 return(NULL);
215 #endif
216 }
217
218
219 char *
220 bmalloc(n) /* allocate a block of n bytes, sans header */
221 register unsigned n;
222 {
223 extern char *sbrk();
224 static unsigned pagesz = 0;
225 static unsigned amnt;
226 static char *bpos;
227 static unsigned nrem;
228 unsigned thisamnt;
229 register char *p;
230
231 if (pagesz == 0) { /* initialize */
232 pagesz = amnt = getpagesize();
233 nrem = (int)sbrk(0); /* page align break */
234 nrem = pagesz - (nrem&(pagesz-1));
235 bpos = sbrk(nrem);
236 if ((int)bpos == -1)
237 return(NULL);
238 #ifdef MSTATS
239 b_nsbrked += nrem;
240 #endif
241 bpos += nrem & (BYTES_WORD-1); /* align pointer */
242 nrem &= ~(BYTES_WORD-1);
243 memlim[0] = bpos;
244 memlim[1] = bpos + nrem;
245 }
246
247 n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1); /* word align rqst. */
248
249 if (n > nrem) { /* need more core */
250 tryagain:
251 if (n > amnt) { /* big chunk */
252 thisamnt = (n+(pagesz-1))&~(pagesz-1);
253 if (thisamnt <= MAXINCR) /* increase amnt */
254 amnt = thisamnt;
255 } else
256 thisamnt = amnt;
257 p = sbrk(thisamnt);
258 if ((int)p == -1) { /* uh-oh, ENOMEM */
259 errno = 0; /* call cavalry */
260 if (thisamnt >= n+pagesz) {
261 amnt = pagesz; /* minimize request */
262 goto tryagain;
263 }
264 thisamnt = n;
265 p = mscrounge(&thisamnt); /* search free lists */
266 if (p == NULL) { /* we're really out */
267 errno = ENOMEM;
268 return(NULL);
269 }
270 }
271 #ifdef MSTATS
272 else b_nsbrked += thisamnt;
273 #endif
274 if (p != bpos+nrem) { /* not an increment */
275 bfree(bpos, nrem); /* free what we have */
276 bpos = p;
277 nrem = thisamnt;
278 } else /* otherwise tack on */
279 nrem += thisamnt;
280 if (bpos < memlim[0])
281 memlim[0] = bpos;
282 if (bpos + nrem > memlim[1])
283 memlim[1] = bpos + nrem;
284 }
285 p = bpos;
286 bpos += n; /* advance */
287 nrem -= n;
288 #ifdef MSTATS
289 b_nalloced += n;
290 #endif
291 return(p);
292 }
293
294
295 bfree(p, n) /* free n bytes of random memory */
296 register char *p;
297 register unsigned n;
298 {
299 register int bucket;
300 register unsigned bsiz;
301
302 if (n < 1<<FIRSTBUCKET || p == NULL)
303 return;
304 #ifdef MSTATS
305 b_nfreed += n;
306 #endif
307 /* align pointer */
308 bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
309 if (bsiz < BYTES_WORD) {
310 p += bsiz;
311 n -= bsiz;
312 }
313 if (p < memlim[0])
314 memlim[0] = p;
315 if (p + n > memlim[1])
316 memlim[1] = p + n;
317 /* fill big buckets first */
318 for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
319 bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
320 if (n >= bsiz+sizeof(M_HEAD)) {
321 ((M_HEAD *)p)->next = free_list[bucket];
322 free_list[bucket] = (M_HEAD *)p;
323 p += bsiz+sizeof(M_HEAD);
324 n -= bsiz+sizeof(M_HEAD);
325 }
326 }
327
328
329 char *
330 malloc(n) /* allocate n bytes of memory */
331 unsigned n;
332 {
333 register M_HEAD *mp;
334 register int bucket;
335 register unsigned bsiz;
336 /* don't return NULL on 0 request */
337 if (n == 0)
338 return(DUMMYLOC);
339 /* find first bucket that fits */
340 for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
341 bucket < NBUCKETS; bucket++, bsiz <<= 1)
342 if (bsiz >= n)
343 break;
344 if (bucket >= NBUCKETS) {
345 errno = EINVAL;
346 return(NULL);
347 }
348 if (free_list[bucket] == NULL) { /* need more core */
349 mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
350 if (mp == NULL)
351 return(NULL);
352 } else { /* got it */
353 mp = free_list[bucket];
354 free_list[bucket] = mp->next;
355 }
356 #ifdef MSTATS
357 m_nalloced += bsiz + sizeof(M_HEAD);
358 m_nwasted += bsiz + sizeof(M_HEAD) - n;
359 #endif
360 mp->a.magic = MAGIC; /* tag block */
361 mp->a.bucket = bucket;
362 return((char *)(mp+1));
363 }
364
365
366 char *
367 realloc(op, n) /* reallocate memory using malloc() */
368 register char *op;
369 unsigned n;
370 {
371 char *p;
372 register unsigned on;
373 /* get old size */
374 if (op != DUMMYLOC && !BADPTR(op) &&
375 ((M_HEAD *)op-1)->a.magic == MAGIC)
376 on = 1 << ((M_HEAD *)op-1)->a.bucket;
377 else
378 on = 0;
379 if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
380 return(op); /* same bucket */
381 if ((p = malloc(n)) == NULL)
382 return(n<=on ? op : NULL);
383 if (on) {
384 memcpy(p, op, n>on ? on : n);
385 free(op);
386 }
387 return(p);
388 }
389
390
391 free(p) /* free memory allocated by malloc */
392 char *p;
393 {
394 register M_HEAD *mp;
395 register int bucket;
396
397 if (p == DUMMYLOC)
398 return(1);
399 if (BADPTR(p))
400 goto invalid;
401 mp = (M_HEAD *)p - 1;
402 if (mp->a.magic != MAGIC) /* sanity check */
403 goto invalid;
404 bucket = mp->a.bucket;
405 if (bucket < FIRSTBUCKET | bucket >= NBUCKETS)
406 goto invalid;
407 mp->next = free_list[bucket];
408 free_list[bucket] = mp;
409 #ifdef MSTATS
410 m_nfreed += (1 << bucket) + sizeof(M_HEAD);
411 #endif
412 return(1);
413 invalid:
414 errno = EINVAL;
415 return(0);
416 }
417
418
419 #ifdef MSTATS
420 printmemstats(fp) /* print memory statistics to stream */
421 FILE *fp;
422 {
423 register int i;
424 int n;
425 register M_HEAD *mp;
426 unsigned int total = 0;
427
428 fprintf(fp, "Memory statistics:\n");
429 fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
430 fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
431 fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
432 fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
433 fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
434 fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
435 fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
436 100.0*m_nwasted/m_nalloced);
437 fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
438 for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
439 n = 0;
440 for (mp = free_list[i]; mp != NULL; mp = mp->next)
441 n++;
442 if (n) {
443 fprintf(fp, "\t%d * %u\n", n, 1<<i);
444 total += n * ((1<<i) + sizeof(M_HEAD));
445 }
446 }
447 fprintf(fp, "\t %u total bytes in free list\n", total);
448 }
449 #endif