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.10 by greg, Tue Nov 13 14:39:05 1990 UTC vs.
Revision 2.9 by greg, Tue Oct 24 09:45:07 1995 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 15 | Line 15 | static char SCCSid[] = "$SunId$ LBL";
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;
# Line 38 | Line 49 | static unsigned        m_nwasted = 0;
49   #endif
50   #define  BYTES_WORD     sizeof(ALIGN)
51  
52 + #ifndef  MAXINCR
53   #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42 –
43 – #ifdef  NOVMEM
44 – #define  getpagesize()  BYTES_WORD
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 char     DUMMYLOC[BYTES_WORD];
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 + 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 +                while (compactfree())
164 +                        ;
165 +                                        /* find largest block */
166 +                tab = mtab(&cptab); tablen = mtablen(&cptab);
167 +                big = tab;
168 +                bp = tab + tablen;
169 +                while (--bp > tab)
170 +                        if (bp->siz > big->siz)
171 +                                big = bp;
172 +                if (big->siz >= *np) {          /* big enough? */
173 +                        *np = big->siz;
174 +                        big->siz = 0;           /* remove from table */
175 +                        return(big->ptr);       /* return it */
176 +                }
177 +                if (mtablen(big) <= tablen) {
178 +                        *np = 0;                /* cannot grow table */
179 +                        return(NULL);           /* report failure */
180 +                }
181 +                                /* enlarge table, free old one */
182 +                mtab(big)[0].ptr = cptab.ptr;
183 +                mtab(big)[0].siz = cptab.siz;
184 +                cptab.ptr = big->ptr;
185 +                cptab.siz = big->siz;
186 +                big->siz = 0;                   /* clear and copy */
187 +                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
188 +                                tablen*sizeof(struct mblk));
189 +                bzero((char *)(mtab(&cptab)+tablen+1),
190 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
191 +        }                       /* next round */
192 + }
193 + #endif          /* MCOMP */
194 +
195 +
196 + char *
197   mscrounge(np)           /* search free lists to satisfy request */
198   register unsigned       *np;
199   {
# Line 77 | Line 212 | register unsigned      *np;
212   #endif
213                          return(p);
214                  }
215 + #ifdef MCOMP
216 +        return(mcompact(np));           /* try compaction */
217 + #else
218          *np = 0;
219          return(NULL);
220 + #endif
221   }
222  
223  
# Line 94 | Line 233 | register unsigned  n;
233          unsigned  thisamnt;
234          register char   *p;
235  
97 – #ifdef MSTATS
98 –        b_nalloced += n;
99 – #endif
236          if (pagesz == 0) {                              /* initialize */
237                  pagesz = amnt = getpagesize();
238                  nrem = (int)sbrk(0);                    /* page align break */
239                  nrem = pagesz - (nrem&(pagesz-1));
240 <                bpos = sbrk(nrem);                      /* word aligned! */
240 >                bpos = sbrk(nrem);
241                  if ((int)bpos == -1)
242                          return(NULL);
243 + #ifdef MSTATS
244 +                b_nsbrked += nrem;
245 + #endif
246 +                bpos += nrem & (BYTES_WORD-1);          /* align pointer */
247 +                nrem &= ~(BYTES_WORD-1);
248 +                memlim[0] = bpos;
249 +                memlim[1] = bpos + nrem;
250          }
251  
252          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
253  
254          if (n > nrem) {                                 /* need more core */
255 +        tryagain:
256                  if (n > amnt) {                         /* big chunk */
257                          thisamnt = (n+(pagesz-1))&~(pagesz-1);
258                          if (thisamnt <= MAXINCR)        /* increase amnt */
# Line 117 | Line 261 | register unsigned  n;
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 */
264 >                        errno = 0;                      /* call cavalry */
265 >                        if (thisamnt >= n+pagesz) {
266 >                                amnt = pagesz;          /* minimize request */
267 >                                goto tryagain;
268 >                        }
269 >                        thisamnt = n;
270 >                        p = mscrounge(&thisamnt);       /* search free lists */
271 >                        if (p == NULL) {                /* we're really out */
272 >                                errno = ENOMEM;
273                                  return(NULL);
274 +                        }
275                  }
276 + #ifdef MSTATS
277 +                else b_nsbrked += thisamnt;
278 + #endif
279                  if (p != bpos+nrem) {                   /* not an increment */
280                          bfree(bpos, nrem);              /* free what we have */
281                          bpos = p;
282                          nrem = thisamnt;
283                  } else                                  /* otherwise tack on */
284                          nrem += thisamnt;
285 +                if (bpos < memlim[0])
286 +                        memlim[0] = bpos;
287 +                if (bpos + nrem > memlim[1])
288 +                        memlim[1] = bpos + nrem;
289          }
290          p = bpos;
291          bpos += n;                                      /* advance */
292          nrem -= n;
293 + #ifdef MSTATS
294 +        b_nalloced += n;
295 + #endif
296          return(p);
297   }
298  
# Line 143 | Line 304 | register unsigned  n;
304          register int    bucket;
305          register unsigned       bsiz;
306  
307 +        if (n < 1<<FIRSTBUCKET)
308 +                return;
309   #ifdef MSTATS
310          b_nfreed += n;
311   #endif
# Line 152 | Line 315 | register unsigned  n;
315                  p += bsiz;
316                  n -= bsiz;
317          }
318 +        if (p < memlim[0])
319 +                memlim[0] = p;
320 +        if (p + n > memlim[1])
321 +                memlim[1] = p + n;
322                                          /* fill big buckets first */
323          for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
324                          bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
# Line 168 | Line 335 | char *
335   malloc(n)                       /* allocate n bytes of memory */
336   unsigned        n;
337   {
171 –        extern int  errno;
338          register M_HEAD *mp;
339          register int    bucket;
340          register unsigned       bsiz;
# Line 184 | Line 350 | unsigned       n;
350                  errno = EINVAL;
351                  return(NULL);
352          }
187 – #ifdef MSTATS
188 –        m_nalloced += bsiz + sizeof(M_HEAD);
189 –        m_nwasted += bsiz + sizeof(M_HEAD) - n;
190 – #endif
353          if (free_list[bucket] == NULL) {        /* need more core */
354                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
355                  if (mp == NULL)
# Line 196 | Line 358 | unsigned       n;
358                  mp = free_list[bucket];
359                  free_list[bucket] = mp->next;
360          }
361 <        mp->bucket = bucket;                    /* tag block */
361 > #ifdef MSTATS
362 >        m_nalloced += bsiz + sizeof(M_HEAD);
363 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
364 > #endif
365 >        mp->a.magic = MAGIC;                    /* tag block */
366 >        mp->a.bucket = bucket;
367          return((char *)(mp+1));
368   }
369  
# Line 209 | Line 376 | unsigned       n;
376          char    *p;
377          register unsigned       on;
378                                          /* get old size */
379 <        if (op != NULL && op != DUMMYLOC)
380 <                on = 1 << ((M_HEAD *)op-1)->bucket;
379 >        if (op != DUMMYLOC && !BADPTR(op) &&
380 >                        ((M_HEAD *)op-1)->a.magic == MAGIC)
381 >                on = 1 << ((M_HEAD *)op-1)->a.bucket;
382          else
383                  on = 0;
384          if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
385                  return(op);             /* same bucket */
386 <        p = malloc(n);
387 <        if (p != NULL)
388 < #ifdef  BSD
386 >        if ((p = malloc(n)) == NULL)
387 >                return(n<=on ? op : NULL);
388 >        if (on) {
389                  bcopy(op, p, n>on ? on : n);
390 < #else
391 <                (void)memcpy(p, op, n>on ? on : n);
224 < #endif
225 <        free(op);
390 >                free(op);
391 >        }
392          return(p);
393   }
394  
# Line 233 | Line 399 | char   *p;
399          register M_HEAD *mp;
400          register int    bucket;
401  
402 <        if (p == NULL || p == DUMMYLOC)
403 <                return;
402 >        if (p == DUMMYLOC)
403 >                return(1);
404 >        if (BADPTR(p))
405 >                goto invalid;
406          mp = (M_HEAD *)p - 1;
407 <        bucket = mp->bucket;
407 >        if (mp->a.magic != MAGIC)               /* sanity check */
408 >                goto invalid;
409 >        bucket = mp->a.bucket;
410 >        if (bucket < FIRSTBUCKET | bucket >= NBUCKETS)
411 >                goto invalid;
412          mp->next = free_list[bucket];
413          free_list[bucket] = mp;
414   #ifdef MSTATS
415          m_nfreed += (1 << bucket) + sizeof(M_HEAD);
416   #endif
417 +        return(1);
418 + invalid:
419 +        errno = EINVAL;
420 +        return(0);
421   }
422  
423  
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 –
424   #ifdef MSTATS
425   printmemstats(fp)               /* print memory statistics to stream */
426   FILE    *fp;
# Line 270 | Line 431 | FILE   *fp;
431          unsigned int    total = 0;
432  
433          fprintf(fp, "Memory statistics:\n");
434 +        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
435          fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
436          fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
437          fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
438 +        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
439          fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
440          fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
441                          100.0*m_nwasted/m_nalloced);

Diff Legend

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