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 2.12 by greg, Sat Feb 22 02:07:22 2003 UTC

# Line 1 | Line 1
1 /* Copyright (c) 1990 Regents of the University of California */
2
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ LBL";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6
4   /*
5   * Fast malloc for memory hogs and VM environments.
6   * 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.
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 < #define  NULL           0
22 > /* ====================================================================
23 > * The Radiance Software License, Version 1.0
24 > *
25 > * Copyright (c) 1990 - 2002 The Regents of the University of California,
26 > * through Lawrence Berkeley National Laboratory.   All rights reserved.
27 > *
28 > * Redistribution and use in source and binary forms, with or without
29 > * modification, are permitted provided that the following conditions
30 > * are met:
31 > *
32 > * 1. Redistributions of source code must retain the above copyright
33 > *         notice, this list of conditions and the following disclaimer.
34 > *
35 > * 2. Redistributions in binary form must reproduce the above copyright
36 > *       notice, this list of conditions and the following disclaimer in
37 > *       the documentation and/or other materials provided with the
38 > *       distribution.
39 > *
40 > * 3. The end-user documentation included with the redistribution,
41 > *           if any, must include the following acknowledgment:
42 > *             "This product includes Radiance software
43 > *                 (http://radsite.lbl.gov/)
44 > *                 developed by the Lawrence Berkeley National Laboratory
45 > *               (http://www.lbl.gov/)."
46 > *       Alternately, this acknowledgment may appear in the software itself,
47 > *       if and wherever such third-party acknowledgments normally appear.
48 > *
49 > * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
50 > *       and "The Regents of the University of California" must
51 > *       not be used to endorse or promote products derived from this
52 > *       software without prior written permission. For written
53 > *       permission, please contact [email protected].
54 > *
55 > * 5. Products derived from this software may not be called "Radiance",
56 > *       nor may "Radiance" appear in their name, without prior written
57 > *       permission of Lawrence Berkeley National Laboratory.
58 > *
59 > * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
60 > * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
61 > * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
62 > * DISCLAIMED.   IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
63 > * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
64 > * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
65 > * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
66 > * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
67 > * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
68 > * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
69 > * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
70 > * SUCH DAMAGE.
71 > * ====================================================================
72 > *
73 > * This software consists of voluntary contributions made by many
74 > * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
75 > * information on Lawrence Berkeley National Laboratory, please see
76 > * <http://www.lbl.gov/>.
77 > */
78  
79 < #ifndef ALIGN
80 < #define  ALIGN          int                     /* align type */
79 > #include  <errno.h>
80 >
81 > #ifndef  BSD
82 > #define  bcopy(s,d,n)           (void)memcpy(d,s,n)
83 > #define  bzero(d,n)             (void)memset(d,0,n)
84   #endif
24 #define  BYTES_WORD     sizeof(ALIGN)
85  
86 < #ifdef  NOVMEM
87 < #define  getpagesize()  BYTES_WORD
86 > #ifdef MSTATS
87 > #include  <stdio.h>
88 > static unsigned b_nsbrked = 0;
89 > static unsigned b_nalloced = 0;
90 > static unsigned b_nfreed = 0;
91 > static unsigned b_nscrounged = 0;
92 > static unsigned b_ncompacted = 0;
93 > static unsigned m_nalloced = 0;
94 > static unsigned m_nfreed = 0;
95 > static unsigned m_nwasted = 0;
96 > #else
97 > #define  NULL           0
98   #endif
99  
100 + #ifndef ALIGNT
101 + #define  ALIGNT         int                     /* align type */
102 + #endif
103 + #define  BYTES_WORD     sizeof(ALIGNT)
104 +
105 + #ifndef  MAXINCR
106 + #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
107 + #endif
108                                          /* malloc free lists */
109   typedef union m_head {
110          union m_head    *next;
111 <        int             bucket;
112 <        ALIGN           dummy;
111 >        struct {
112 >                short           magic;
113 >                short           bucket;
114 >        }       a;
115 >        ALIGNT          dummy;
116   } M_HEAD;
117  
118 + #define MAGIC           0x1a2           /* magic number for allocated memory */
119 +
120   #define FIRSTBUCKET     3
121   #define NBUCKETS        30
122  
123   static M_HEAD   *free_list[NBUCKETS];
124  
125 + static ALIGNT   dummy_mem;
126  
127 + static char     *memlim[2];
128 +
129 + #define DUMMYLOC        ((char *)&dummy_mem)
130 +
131 + #define BADPTR(p)       ((p) < memlim[0] | (p) >= memlim[1])
132 +
133 + #ifdef  MCOMP                   /* memory compaction routines */
134 + static char     seedtab[1024];          /* seed for compaction table */
135 +
136 + static struct mblk {
137 +        char            *ptr;   /* pointer to memory block */
138 +        unsigned        siz;    /* size of memory block */
139 + }       cptab = {seedtab, sizeof(seedtab)};
140 +
141 + #define mtab(mb)        ((struct mblk *)(mb)->ptr)
142 + #define mtablen(mb)     ((mb)->siz/sizeof(struct mblk))
143 +
144 +
145 + static int
146 + mbcmp(m1, m2)           /* compare memory block locations */
147 + register struct mblk    *m1, *m2;
148 + {
149 +                                /* put empty blocks at end */
150 +        if (m1->siz == 0)
151 +                return(m2->siz == 0 ? 0 : 1);
152 +        if (m2->siz == 0)
153 +                return(-1);
154 +                                /* otherwise, ascending order */
155 +        return(m1->ptr - m2->ptr);
156 + }
157 +
158 +
159 + int
160 + compactfree()           /* compact free lists (moving to table) */
161 + {
162 +        register struct mblk    *tp;
163 +        register int    bucket;
164 +        unsigned        n, bsiz, ncomp;
165 +                                /* fill table from free lists */
166 +        tp = mtab(&cptab); n = mtablen(&cptab);
167 +        bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
168 +        ncomp = 0;
169 +        for ( ; ; ) {
170 +                while (tp->siz) {       /* find empty slot */
171 +                        if (--n == 0)
172 +                                goto loopexit;
173 +                        tp++;
174 +                }
175 +                while (free_list[bucket] == NULL) {     /* find block */
176 +                        if (--bucket < FIRSTBUCKET)
177 +                                goto loopexit;
178 +                        bsiz >>= 1;
179 +                }
180 +                tp->ptr = (char *)free_list[bucket];
181 +                ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
182 +                free_list[bucket] = free_list[bucket]->next;
183 +        }
184 + loopexit:
185 +        if (ncomp == 0)
186 +                return(0);              /* nothing new to compact */
187 + #ifdef MSTATS
188 +        b_ncompacted += ncomp;
189 + #endif
190 +        tp = mtab(&cptab); n = mtablen(&cptab);         /* sort table */
191 +        qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
192 +        ncomp = 0;                                      /* collect blocks */
193 +        while (--n && tp[1].siz) {
194 +                if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
195 +                        tp[1].ptr = tp[0].ptr;
196 +                        tp[1].siz += tp[0].siz;
197 +                        ncomp += tp[0].siz;
198 +                        tp[0].siz = 0;
199 +                }
200 +                tp++;
201 +        }
202 +        return(ncomp);
203 + }
204 +
205 +
206   char *
207 + mcompact(np)            /* compact free lists to satisfy request */
208 + unsigned        *np;
209 + {
210 +        struct mblk     *tab;
211 +        unsigned        tablen;
212 +        register struct mblk    *bp, *big;
213 +
214 +        for ( ; ; ) {
215 +                                        /* compact free lists */
216 +                while (compactfree())
217 +                        ;
218 +                                        /* find largest block */
219 +                tab = mtab(&cptab); tablen = mtablen(&cptab);
220 +                big = tab;
221 +                bp = tab + tablen;
222 +                while (--bp > tab)
223 +                        if (bp->siz > big->siz)
224 +                                big = bp;
225 +                if (big->siz >= *np) {          /* big enough? */
226 +                        *np = big->siz;
227 +                        big->siz = 0;           /* remove from table */
228 +                        return(big->ptr);       /* return it */
229 +                }
230 +                if (mtablen(big) <= tablen) {
231 +                        *np = 0;                /* cannot grow table */
232 +                        return(NULL);           /* report failure */
233 +                }
234 +                                /* enlarge table, free old one */
235 +                mtab(big)[0].ptr = cptab.ptr;
236 +                mtab(big)[0].siz = cptab.siz;
237 +                cptab.ptr = big->ptr;
238 +                cptab.siz = big->siz;
239 +                big->siz = 0;                   /* clear and copy */
240 +                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
241 +                                tablen*sizeof(struct mblk));
242 +                bzero((char *)(mtab(&cptab)+tablen+1),
243 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
244 +        }                       /* next round */
245 + }
246 + #endif          /* MCOMP */
247 +
248 +
249 + char *
250 + mscrounge(np)           /* search free lists to satisfy request */
251 + register unsigned       *np;
252 + {
253 +        char    *p;
254 +        register int    bucket;
255 +        register unsigned       bsiz;
256 +
257 +        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
258 +                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
259 +                if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
260 +                        *np = bsiz+sizeof(M_HEAD);
261 +                        p = (char *)free_list[bucket];
262 +                        free_list[bucket] = free_list[bucket]->next;
263 + #ifdef MSTATS
264 +                        b_nscrounged += *np;
265 + #endif
266 +                        return(p);
267 +                }
268 + #ifdef MCOMP
269 +        return(mcompact(np));           /* try compaction */
270 + #else
271 +        *np = 0;
272 +        return(NULL);
273 + #endif
274 + }
275 +
276 +
277 + char *
278   bmalloc(n)              /* allocate a block of n bytes, sans header */
279   register unsigned  n;
280   {
281          extern char  *sbrk();
282 <        static int  pagesz = 0;
283 <        static int  amnt;
282 >        static unsigned  pagesz = 0;
283 >        static unsigned  amnt;
284          static char  *bpos;
285 <        static int  nrem;
285 >        static unsigned  nrem;
286 >        unsigned  thisamnt;
287          register char   *p;
288  
289          if (pagesz == 0) {                              /* initialize */
290 <                amnt = pagesz = getpagesize();
290 >                pagesz = amnt = getpagesize();
291                  nrem = (int)sbrk(0);                    /* page align break */
292                  nrem = pagesz - (nrem&(pagesz-1));
293 <                bpos = sbrk(nrem);                      /* word aligned! */
293 >                bpos = sbrk(nrem);
294                  if ((int)bpos == -1)
295                          return(NULL);
296 + #ifdef MSTATS
297 +                b_nsbrked += nrem;
298 + #endif
299 +                bpos += nrem & (BYTES_WORD-1);          /* align pointer */
300 +                nrem &= ~(BYTES_WORD-1);
301 +                memlim[0] = bpos;
302 +                memlim[1] = bpos + nrem;
303          }
304  
305          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
306  
307          if (n > nrem) {                                 /* need more core */
308 <                if (n > amnt)                   /* increase amount */
309 <                        amnt = (n+(pagesz-1))&~(pagesz-1);
310 <                p = sbrk(amnt);
311 <                if ((int)p == -1)
312 <                        return(NULL);
71 <                if (p != bpos+nrem) {           /* someone called sbrk()! */
72 <                        bfree(bpos, nrem);
73 <                        bpos = p;
74 <                        nrem = amnt;
308 >        tryagain:
309 >                if (n > amnt) {                         /* big chunk */
310 >                        thisamnt = (n+(pagesz-1))&~(pagesz-1);
311 >                        if (thisamnt <= MAXINCR)        /* increase amnt */
312 >                                amnt = thisamnt;
313                  } else
314 <                        nrem += amnt;
314 >                        thisamnt = amnt;
315 >                p = sbrk(thisamnt);
316 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
317 >                        errno = 0;                      /* call cavalry */
318 >                        if (thisamnt >= n+pagesz) {
319 >                                amnt = pagesz;          /* minimize request */
320 >                                goto tryagain;
321 >                        }
322 >                        thisamnt = n;
323 >                        p = mscrounge(&thisamnt);       /* search free lists */
324 >                        if (p == NULL) {                /* we're really out */
325 >                                errno = ENOMEM;
326 >                                return(NULL);
327 >                        }
328 >                }
329 > #ifdef MSTATS
330 >                else b_nsbrked += thisamnt;
331 > #endif
332 >                if (p != bpos+nrem) {                   /* not an increment */
333 >                        bfree(bpos, nrem);              /* free what we have */
334 >                        bpos = p;
335 >                        nrem = thisamnt;
336 >                } else                                  /* otherwise tack on */
337 >                        nrem += thisamnt;
338 >                if (bpos < memlim[0])
339 >                        memlim[0] = bpos;
340 >                if (bpos + nrem > memlim[1])
341 >                        memlim[1] = bpos + nrem;
342          }
343          p = bpos;
344          bpos += n;                                      /* advance */
345          nrem -= n;
346 + #ifdef MSTATS
347 +        b_nalloced += n;
348 + #endif
349          return(p);
350   }
351  
352  
353   bfree(p, n)                     /* free n bytes of random memory */
354 < char  *p;
355 < unsigned  n;
354 > register char  *p;
355 > register unsigned  n;
356   {
89        register M_HEAD *mp;
357          register int    bucket;
358          register unsigned       bsiz;
359 <                                        /* find largest bucket */
360 <        bucket = 0;
361 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
362 <                bucket++;
363 <        mp = (M_HEAD *)p;
364 <        while (bucket > FIRSTBUCKET) {
365 <                bsiz >>= 1;
366 <                bucket--;
367 <                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
368 <                        continue;
369 <                mp->next = free_list[bucket];
103 <                free_list[bucket] = mp;
104 <                (char *)mp += bsiz+sizeof(M_HEAD);
105 <                n -= bsiz+sizeof(M_HEAD);
359 >
360 >        if (n < 1<<FIRSTBUCKET || p == NULL)
361 >                return;
362 > #ifdef MSTATS
363 >        b_nfreed += n;
364 > #endif
365 >                                        /* align pointer */
366 >        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
367 >        if (bsiz < BYTES_WORD) {
368 >                p += bsiz;
369 >                n -= bsiz;
370          }
371 +        if (p < memlim[0])
372 +                memlim[0] = p;
373 +        if (p + n > memlim[1])
374 +                memlim[1] = p + n;
375 +                                        /* fill big buckets first */
376 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
377 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
378 +                if (n >= bsiz+sizeof(M_HEAD)) {
379 +                        ((M_HEAD *)p)->next = free_list[bucket];
380 +                        free_list[bucket] = (M_HEAD *)p;
381 +                        p += bsiz+sizeof(M_HEAD);
382 +                        n -= bsiz+sizeof(M_HEAD);
383 +                }
384   }
385  
386  
# Line 114 | Line 391 | unsigned       n;
391          register M_HEAD *mp;
392          register int    bucket;
393          register unsigned       bsiz;
394 <
395 <        bucket = FIRSTBUCKET;
396 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
397 <                bucket++;
398 <        if (free_list[bucket] == NULL) {
394 >                                        /* don't return NULL on 0 request */
395 >        if (n == 0)
396 >                return(DUMMYLOC);
397 >                                        /* find first bucket that fits */
398 >        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
399 >                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
400 >                if (bsiz >= n)
401 >                        break;
402 >        if (bucket >= NBUCKETS) {
403 >                errno = EINVAL;
404 >                return(NULL);
405 >        }
406 >        if (free_list[bucket] == NULL) {        /* need more core */
407                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
408                  if (mp == NULL)
409                          return(NULL);
410 <        } else {
410 >        } else {                                /* got it */
411                  mp = free_list[bucket];
412                  free_list[bucket] = mp->next;
413          }
414 <        mp->bucket = bucket;
414 > #ifdef MSTATS
415 >        m_nalloced += bsiz + sizeof(M_HEAD);
416 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
417 > #endif
418 >        mp->a.magic = MAGIC;                    /* tag block */
419 >        mp->a.bucket = bucket;
420          return((char *)(mp+1));
421   }
422  
423  
424   char *
425   realloc(op, n)                  /* reallocate memory using malloc() */
426 < char    *op;
426 > register char   *op;
427   unsigned        n;
428   {
429 <        register char   *p;
429 >        char    *p;
430          register unsigned       on;
431 <
432 <        if (op != NULL)
433 <                on = 1 << ((M_HEAD *)op-1)->bucket;
431 >                                        /* get old size */
432 >        if (op != DUMMYLOC && !BADPTR(op) &&
433 >                        ((M_HEAD *)op-1)->a.magic == MAGIC)
434 >                on = 1 << ((M_HEAD *)op-1)->a.bucket;
435          else
436                  on = 0;
437 <        if (n <= on && n > on>>1)
437 >        if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
438                  return(op);             /* same bucket */
439 <        p = malloc(n);
440 <        if (p == NULL)
441 <                return(NULL);
442 < #ifdef  BSD
443 <        bcopy(op, p, n>on ? on : n);
444 < #else
154 <        (void)memcpy(p, op, n>on ? on : n);
155 < #endif
156 <        free(op);
439 >        if ((p = malloc(n)) == NULL)
440 >                return(n<=on ? op : NULL);
441 >        if (on) {
442 >                bcopy(op, p, n>on ? on : n);
443 >                free(op);
444 >        }
445          return(p);
446   }
447  
# Line 164 | Line 452 | char   *p;
452          register M_HEAD *mp;
453          register int    bucket;
454  
455 +        if (p == DUMMYLOC)
456 +                return(1);
457 +        if (BADPTR(p))
458 +                goto invalid;
459          mp = (M_HEAD *)p - 1;
460 <        bucket = mp->bucket;
460 >        if (mp->a.magic != MAGIC)               /* sanity check */
461 >                goto invalid;
462 >        bucket = mp->a.bucket;
463 >        if (bucket < FIRSTBUCKET | bucket >= NBUCKETS)
464 >                goto invalid;
465          mp->next = free_list[bucket];
466          free_list[bucket] = mp;
467 + #ifdef MSTATS
468 +        m_nfreed += (1 << bucket) + sizeof(M_HEAD);
469 + #endif
470 +        return(1);
471 + invalid:
472 +        errno = EINVAL;
473 +        return(0);
474   }
475  
476  
477 < #ifndef NOVMEM
478 < #ifndef BSD
479 < #include <sys/var.h>
177 < int
178 < getpagesize()                   /* use SYSV var structure to get page size */
477 > #ifdef MSTATS
478 > printmemstats(fp)               /* print memory statistics to stream */
479 > FILE    *fp;
480   {
481 <        static int  pagesz = 0;
482 <        struct var  v;
481 >        register int    i;
482 >        int     n;
483 >        register M_HEAD *mp;
484 >        unsigned int    total = 0;
485  
486 <        if (pagesz == 0) {
487 <                uvar(&v);
488 <                pagesz = 1 << v.v_pageshift;
486 >        fprintf(fp, "Memory statistics:\n");
487 >        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
488 >        fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
489 >        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
490 >        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
491 >        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
492 >        fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
493 >        fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
494 >                        100.0*m_nwasted/m_nalloced);
495 >        fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
496 >        for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
497 >                n = 0;
498 >                for (mp = free_list[i]; mp != NULL; mp = mp->next)
499 >                        n++;
500 >                if (n) {
501 >                        fprintf(fp, "\t%d * %u\n", n, 1<<i);
502 >                        total += n * ((1<<i) + sizeof(M_HEAD));
503 >                }
504          }
505 <        return(pagesz);
505 >        fprintf(fp, "\t %u total bytes in free list\n", total);
506   }
189 #endif
507   #endif

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines