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.3 by greg, Wed Sep 26 06:23:10 1990 UTC vs.
Revision 2.8 by greg, Thu Oct 8 12:27:02 1992 UTC

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

Diff Legend

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