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

Diff Legend

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