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

Diff Legend

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