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

Diff Legend

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