ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/malloc.c
(Generate patch)

Comparing ray/src/common/malloc.c (file contents):
Revision 1.1 by greg, Tue Sep 25 17:14:04 1990 UTC vs.
Revision 1.15 by greg, Mon Aug 26 10:49:08 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 */
297 <                        continue;
298 <                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 >        if (n < 1<<FIRSTBUCKET)
290 >                return;
291 > #ifdef MSTATS
292 >        b_nfreed += n;
293 > #endif
294 >                                        /* align pointer */
295 >        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
296 >        if (bsiz < BYTES_WORD) {
297 >                p += bsiz;
298 >                n -= bsiz;
299          }
300 +                                        /* fill big buckets first */
301 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
302 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
303 +                if (n >= bsiz+sizeof(M_HEAD)) {
304 +                        ((M_HEAD *)p)->next = free_list[bucket];
305 +                        free_list[bucket] = (M_HEAD *)p;
306 +                        p += bsiz+sizeof(M_HEAD);
307 +                        n -= bsiz+sizeof(M_HEAD);
308 +                }
309   }
310  
311  
# Line 111 | Line 313 | char *
313   malloc(n)                       /* allocate n bytes of memory */
314   unsigned        n;
315   {
316 +        extern int  errno;
317          register M_HEAD *mp;
318          register int    bucket;
319          register unsigned       bsiz;
320 <
321 <        bucket = FIRSTBUCKET;
322 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
323 <                bucket++;
324 <        if (free_list[bucket] == NULL) {
320 >                                        /* don't return NULL on 0 request */
321 >        if (n == 0)
322 >                return(DUMMYLOC);
323 >                                        /* find first bucket that fits */
324 >        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
325 >                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
326 >                if (bsiz >= n)
327 >                        break;
328 >        if (bucket >= NBUCKETS) {
329 >                errno = EINVAL;
330 >                return(NULL);
331 >        }
332 >        if (free_list[bucket] == NULL) {        /* need more core */
333                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
334                  if (mp == NULL)
335                          return(NULL);
336 <        } else {
336 >        } else {                                /* got it */
337                  mp = free_list[bucket];
338                  free_list[bucket] = mp->next;
339          }
340 <        mp->bucket = bucket;
340 > #ifdef MSTATS
341 >        m_nalloced += bsiz + sizeof(M_HEAD);
342 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
343 > #endif
344 >        mp->a.magic = MAGIC;                    /* tag block */
345 >        mp->a.bucket = bucket;
346          return((char *)(mp+1));
347   }
348  
349  
350   char *
351   realloc(op, n)                  /* reallocate memory using malloc() */
352 < char    *op;
352 > register char   *op;
353   unsigned        n;
354   {
355 <        register char   *p;
355 >        char    *p;
356          register unsigned       on;
357 <
358 <        if (op != NULL)
359 <                on = 1 << ((M_HEAD *)op-1)->bucket;
357 >                                        /* get old size */
358 >        if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
359 >                on = 1 << ((M_HEAD *)op-1)->a.bucket;
360          else
361                  on = 0;
362 <        if (n <= on && n > on>>1)
362 >        if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
363                  return(op);             /* same bucket */
364 <        p = malloc(n);
149 <        if (p == NULL)
364 >        if ((p = malloc(n)) == NULL)
365                  return(NULL);
366 +        if (on) {
367   #ifdef  BSD
368 <        bcopy(op, p, n>on ? on : n);
368 >                bcopy(op, p, n>on ? on : n);
369   #else
370 <        (void)memcpy(p, op, n>on ? on : n);
370 >                (void)memcpy(p, op, n>on ? on : n);
371   #endif
372 <        free(op);
372 >                free(op);
373 >        }
374          return(p);
375   }
376  
# Line 164 | Line 381 | char   *p;
381          register M_HEAD *mp;
382          register int    bucket;
383  
384 +        if (p == NULL || p == DUMMYLOC)
385 +                return(1);
386          mp = (M_HEAD *)p - 1;
387 <        bucket = mp->bucket;
387 >        if (mp->a.magic != MAGIC)               /* sanity check */
388 >                return(0);
389 >        bucket = mp->a.bucket;
390          mp->next = free_list[bucket];
391          free_list[bucket] = mp;
392 + #ifdef MSTATS
393 +        m_nfreed += (1 << bucket) + sizeof(M_HEAD);
394 + #endif
395 +        return(1);
396   }
397  
398  
# Line 177 | Line 402 | char   *p;
402   int
403   getpagesize()                   /* use SYSV var structure to get page size */
404   {
180 –        static int  pagesz = 0;
405          struct var  v;
406  
407 <        if (pagesz == 0) {
408 <                uvar(&v);
185 <                pagesz = 1 << v.v_pageshift;
186 <        }
187 <        return(pagesz);
407 >        uvar(&v);
408 >        return(1 << v.v_pageshift);
409   }
410   #endif
411 + #endif
412 +
413 +
414 + #ifdef MSTATS
415 + printmemstats(fp)               /* print memory statistics to stream */
416 + FILE    *fp;
417 + {
418 +        register int    i;
419 +        int     n;
420 +        register M_HEAD *mp;
421 +        unsigned int    total = 0;
422 +
423 +        fprintf(fp, "Memory statistics:\n");
424 +        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
425 +        fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
426 +        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
427 +        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
428 +        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
429 +        fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
430 +        fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
431 +                        100.0*m_nwasted/m_nalloced);
432 +        fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
433 +        for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
434 +                n = 0;
435 +                for (mp = free_list[i]; mp != NULL; mp = mp->next)
436 +                        n++;
437 +                if (n) {
438 +                        fprintf(fp, "\t%d * %u\n", n, 1<<i);
439 +                        total += n * ((1<<i) + sizeof(M_HEAD));
440 +                }
441 +        }
442 +        fprintf(fp, "\t %u total bytes in free list\n", total);
443 + }
444   #endif

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines