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.1 by greg, Tue Nov 12 16:54:29 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(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 + #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<<18)                 /* largest sbrk(2) increment */
47 <
31 < #ifdef  NOVMEM
32 < #define  getpagesize()  BYTES_WORD
46 > #ifndef  MAXINCR
47 > #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
48   #endif
49                                          /* malloc free lists */
50   typedef union m_head {
51          union m_head    *next;
52 <        int             bucket;
52 >        struct {
53 >                short           magic;
54 >                short           bucket;
55 >        }       a;
56          ALIGN           dummy;
57   } M_HEAD;
58  
59 + #define MAGIC           0x1a2           /* magic number for allocated memory */
60 +
61   #define FIRSTBUCKET     3
62   #define NBUCKETS        30
63  
64   static M_HEAD   *free_list[NBUCKETS];
65  
66 + static ALIGN    dummy_mem;
67  
68 + #define DUMMYLOC        ((char *)&dummy_mem)
69 +
70 + #ifdef  MCOMP                   /* memory compaction routines */
71 + static char     seedtab[1024];          /* seed for compaction table */
72 +
73 + static struct mblk {
74 +        char            *ptr;   /* pointer to memory block */
75 +        unsigned        siz;    /* size of memory block */
76 + }       cptab = {seedtab, sizeof(seedtab)};
77 +
78 + #define mtab(mb)        ((struct mblk *)(mb)->ptr)
79 + #define mtablen(mb)     ((mb)->siz/sizeof(struct mblk))
80 +
81 +
82 + static int
83 + mbcmp(m1, m2)           /* compare memory block locations */
84 + register struct mblk    *m1, *m2;
85 + {
86 +                                /* put empty blocks at end */
87 +        if (m1->siz == 0)
88 +                return(m2->siz == 0 ? 0 : 1);
89 +        if (m2->siz == 0)
90 +                return(-1);
91 +                                /* otherwise, ascending order */
92 +        return(m1->ptr - m2->ptr);
93 + }
94 +
95 +
96 + int
97 + compactfree()           /* compact free lists (moving to table) */
98 + {
99 +        register struct mblk    *tp;
100 +        register int    bucket;
101 +        unsigned        n, bsiz, ncomp;
102 +                                /* fill table from free lists */
103 +        tp = mtab(&cptab); n = mtablen(&cptab);
104 +        bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
105 +        ncomp = 0;
106 +        for ( ; ; ) {
107 +                while (tp->siz) {       /* find empty slot */
108 +                        if (--n == 0)
109 +                                goto loopexit;
110 +                        tp++;
111 +                }
112 +                while (free_list[bucket] == NULL) {     /* find block */
113 +                        if (--bucket < FIRSTBUCKET)
114 +                                goto loopexit;
115 +                        bsiz >>= 1;
116 +                }
117 +                tp->ptr = (char *)free_list[bucket];
118 +                ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
119 +                free_list[bucket] = free_list[bucket]->next;
120 +        }
121 + loopexit:
122 +        if (ncomp == 0)
123 +                return(0);              /* nothing new to compact */
124 + #ifdef MSTATS
125 +        b_ncompacted += ncomp;
126 + #endif
127 +        tp = mtab(&cptab); n = mtablen(&cptab);         /* sort table */
128 +        qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
129 +        ncomp = 0;                                      /* collect blocks */
130 +        while (--n && tp[1].siz) {
131 +                if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
132 +                        tp[1].ptr = tp[0].ptr;
133 +                        tp[1].siz += tp[0].siz;
134 +                        ncomp += tp[0].siz;
135 +                        tp[0].siz = 0;
136 +                }
137 +                tp++;
138 +        }
139 +        return(ncomp);
140 + }
141 +
142 +
143   char *
144 < mscrounge(np)           /* search free lists trying to satisfy request */
144 > mcompact(np)            /* compact free lists to satisfy request */
145 > unsigned        *np;
146 > {
147 >        struct mblk     *tab;
148 >        unsigned        tablen;
149 >        register struct mblk    *bp, *big;
150 >
151 >        for ( ; ; ) {
152 >                                        /* compact free lists */
153 >                compactfree();
154 >                                        /* find largest block */
155 >                tab = mtab(&cptab); tablen = mtablen(&cptab);
156 >                big = tab;
157 >                bp = tab + tablen;
158 >                while (--bp > tab)
159 >                        if (bp->siz > big->siz)
160 >                                big = bp;
161 >                if (big->siz >= *np) {          /* big enough? */
162 >                        *np = big->siz;
163 >                        big->siz = 0;           /* remove from table */
164 >                        return(big->ptr);       /* return it */
165 >                }
166 >                if (mtablen(big) < tablen+1) {
167 >                        *np = 0;                /* cannot grow table */
168 >                        return(NULL);           /* report failure */
169 >                }
170 >                                /* enlarge table, free old one */
171 >                mtab(big)[0].ptr = cptab.ptr;
172 >                mtab(big)[0].siz = cptab.siz;
173 >                cptab.ptr = big->ptr;
174 >                cptab.siz = big->siz;
175 >                big->siz = 0;                   /* clear and copy */
176 > #ifdef BSD
177 >                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
178 >                                tablen*sizeof(struct mblk));
179 >                bzero((char *)(mtab(&cptab)+tablen+1),
180 >                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
181 > #else
182 >                (void)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 > #endif
187 >        }                       /* next round */
188 > }
189 > #endif          /* MCOMP */
190 >
191 >
192 > char *
193 > mscrounge(np)           /* search free lists to satisfy request */
194   register unsigned       *np;
195   {
196          char    *p;
# Line 58 | Line 203 | register unsigned      *np;
203                          *np = bsiz+sizeof(M_HEAD);
204                          p = (char *)free_list[bucket];
205                          free_list[bucket] = free_list[bucket]->next;
206 + #ifdef MSTATS
207 +                        b_nscrounged += *np;
208 + #endif
209                          return(p);
210                  }
211 + #ifdef MCOMP
212 +        return(mcompact(np));           /* try compaction */
213 + #else
214          *np = 0;
215          return(NULL);
216 + #endif
217   }
218  
219  
# Line 84 | Line 236 | register unsigned  n;
236                  bpos = sbrk(nrem);                      /* word aligned! */
237                  if ((int)bpos == -1)
238                          return(NULL);
239 + #ifdef MSTATS
240 +                b_nsbrked += nrem;
241 + #endif
242          }
243  
244          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
# Line 96 | Line 251 | register unsigned  n;
251                  } else
252                          thisamnt = amnt;
253                  p = sbrk(thisamnt);
254 <                if ((int)p == -1) {                     /* uh-oh */
254 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
255                          thisamnt = n;                   /* search free lists */
256                          p = mscrounge(&thisamnt);
257                          if (p == NULL)                  /* we're really out */
258                                  return(NULL);
259                  }
260 + #ifdef MSTATS
261 +                else b_nsbrked += thisamnt;
262 + #endif
263                  if (p != bpos+nrem) {                   /* not an increment */
264 <                        bfree(bpos, nrem);
264 >                        bfree(bpos, nrem);              /* free what we have */
265                          bpos = p;
266                          nrem = thisamnt;
267 <                } else
267 >                } else                                  /* otherwise tack on */
268                          nrem += thisamnt;
269          }
270          p = bpos;
271          bpos += n;                                      /* advance */
272          nrem -= n;
273 + #ifdef MSTATS
274 +        b_nalloced += n;
275 + #endif
276          return(p);
277   }
278  
# Line 122 | Line 283 | register unsigned  n;
283   {
284          register int    bucket;
285          register unsigned       bsiz;
286 <                                        /* find largest bucket */
287 <        bucket = 0;
288 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
289 <                bucket++;
290 <        while (bucket > FIRSTBUCKET) {
291 <                bsiz >>= 1;
292 <                bucket--;
293 <                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
294 <                        continue;
295 <                ((M_HEAD *)p)->next = free_list[bucket];
296 <                free_list[bucket] = (M_HEAD *)p;
136 <                p += bsiz+sizeof(M_HEAD);
137 <                n -= bsiz+sizeof(M_HEAD);
286 >
287 >        if (n < 1<<FIRSTBUCKET)
288 >                return;
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 143 | 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 <
318 >                                        /* don't return NULL on 0 request */
319          if (n == 0)
320 <                return(NULL);
320 >                return(DUMMYLOC);
321                                          /* find first bucket that fits */
322 <        bucket = FIRSTBUCKET;
323 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
324 <                bucket++;
325 <        if (free_list[bucket] == NULL) {
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);
363 <        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);
367   #else
368                  (void)memcpy(p, op, n>on ? on : n);
369   #endif
370 <        free(op);
370 >                free(op);
371 >        }
372          return(p);
373   }
374  
# Line 198 | Line 379 | char   *p;
379          register M_HEAD *mp;
380          register int    bucket;
381  
382 <        if (p == NULL)
383 <                return;
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  
397 < #ifndef NOVMEM
398 < #ifndef BSD
399 < #include <sys/var.h>
213 < int
214 < getpagesize()                   /* use SYSV var structure to get page size */
397 > #ifdef MSTATS
398 > printmemstats(fp)               /* print memory statistics to stream */
399 > FILE    *fp;
400   {
401 <        static int  pagesz = 0;
402 <        struct var  v;
401 >        register int    i;
402 >        int     n;
403 >        register M_HEAD *mp;
404 >        unsigned int    total = 0;
405  
406 <        if (pagesz == 0) {
407 <                uvar(&v);
408 <                pagesz = 1 << v.v_pageshift;
406 >        fprintf(fp, "Memory statistics:\n");
407 >        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
408 >        fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
409 >        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
410 >        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
411 >        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
412 >        fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
413 >        fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
414 >                        100.0*m_nwasted/m_nalloced);
415 >        fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
416 >        for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
417 >                n = 0;
418 >                for (mp = free_list[i]; mp != NULL; mp = mp->next)
419 >                        n++;
420 >                if (n) {
421 >                        fprintf(fp, "\t%d * %u\n", n, 1<<i);
422 >                        total += n * ((1<<i) + sizeof(M_HEAD));
423 >                }
424          }
425 <        return(pagesz);
425 >        fprintf(fp, "\t %u total bytes in free list\n", total);
426   }
225 – #endif
427   #endif

Diff Legend

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