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.3 by greg, Fri Feb 7 15:10:32 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 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   */
# Line 23 | Line 26 | static char SCCSid[] = "$SunId$ LBL";
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;
# Line 38 | Line 43 | static unsigned        m_nwasted = 0;
43   #endif
44   #define  BYTES_WORD     sizeof(ALIGN)
45  
46 + #ifndef  MAXINCR
47   #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42 –
43 – #ifdef  NOVMEM
44 – #define  getpagesize()  1024
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 char     DUMMYLOC[BYTES_WORD];
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 + 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   {
# Line 77 | Line 208 | register unsigned      *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 94 | Line 229 | register unsigned  n;
229          unsigned  thisamnt;
230          register char   *p;
231  
97 – #ifdef MSTATS
98 –        b_nalloced += n;
99 – #endif
232          if (pagesz == 0) {                              /* initialize */
233                  pagesz = amnt = getpagesize();
234                  nrem = (int)sbrk(0);                    /* page align break */
235                  nrem = pagesz - (nrem&(pagesz-1));
236 <                bpos = sbrk(nrem);                      /* word aligned! */
236 >                bpos = sbrk(nrem);
237                  if ((int)bpos == -1)
238                          return(NULL);
239 + #ifdef MSTATS
240 +                b_nsbrked += nrem;
241 + #endif
242 +                thisamnt = BYTES_WORD - ((unsigned)bpos&(BYTES_WORD-1));
243 +                if (thisamnt < BYTES_WORD) {            /* align pointer */
244 +                        bpos += thisamnt;
245 +                        nrem -= thisamnt;
246 +                }
247          }
248  
249          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
# Line 122 | Line 262 | register unsigned  n;
262                          if (p == NULL)                  /* we're really out */
263                                  return(NULL);
264                  }
265 + #ifdef MSTATS
266 +                else b_nsbrked += thisamnt;
267 + #endif
268                  if (p != bpos+nrem) {                   /* not an increment */
269                          bfree(bpos, nrem);              /* free what we have */
270                          bpos = p;
# Line 132 | Line 275 | register unsigned  n;
275          p = bpos;
276          bpos += n;                                      /* advance */
277          nrem -= n;
278 + #ifdef MSTATS
279 +        b_nalloced += n;
280 + #endif
281          return(p);
282   }
283  
# Line 143 | Line 289 | register unsigned  n;
289          register int    bucket;
290          register unsigned       bsiz;
291  
292 +        if (n < 1<<FIRSTBUCKET)
293 +                return;
294   #ifdef MSTATS
295          b_nfreed += n;
296   #endif
# Line 184 | Line 332 | unsigned       n;
332                  errno = EINVAL;
333                  return(NULL);
334          }
187 – #ifdef MSTATS
188 –        m_nalloced += bsiz + sizeof(M_HEAD);
189 –        m_nwasted += bsiz + sizeof(M_HEAD) - n;
190 – #endif
335          if (free_list[bucket] == NULL) {        /* need more core */
336                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
337                  if (mp == NULL)
# Line 196 | Line 340 | unsigned       n;
340                  mp = free_list[bucket];
341                  free_list[bucket] = mp->next;
342          }
343 <        mp->bucket = bucket;                    /* tag block */
343 > #ifdef MSTATS
344 >        m_nalloced += bsiz + sizeof(M_HEAD);
345 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
346 > #endif
347 >        mp->a.magic = MAGIC;                    /* tag block */
348 >        mp->a.bucket = bucket;
349          return((char *)(mp+1));
350   }
351  
# Line 209 | Line 358 | unsigned       n;
358          char    *p;
359          register unsigned       on;
360                                          /* get old size */
361 <        if (op != NULL && op != DUMMYLOC)
362 <                on = 1 << ((M_HEAD *)op-1)->bucket;
361 >        if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
362 >                on = 1 << ((M_HEAD *)op-1)->a.bucket;
363          else
364                  on = 0;
365          if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
366                  return(op);             /* same bucket */
367 <        p = malloc(n);
368 <        if (p != NULL)
367 >        if ((p = malloc(n)) == NULL)
368 >                return(NULL);
369 >        if (on) {
370   #ifdef  BSD
371                  bcopy(op, p, n>on ? on : n);
372   #else
373                  (void)memcpy(p, op, n>on ? on : n);
374   #endif
375 <        free(op);
375 >                free(op);
376 >        }
377          return(p);
378   }
379  
# Line 233 | Line 384 | char   *p;
384          register M_HEAD *mp;
385          register int    bucket;
386  
387 <        if (p == NULL || p == DUMMYLOC)
388 <                return;
387 >        if (p == NULL | p == DUMMYLOC)
388 >                return(1);
389          mp = (M_HEAD *)p - 1;
390 <        bucket = mp->bucket;
390 >        if (mp->a.magic != MAGIC)               /* sanity check */
391 >                return(0);
392 >        bucket = mp->a.bucket;
393 >        if (bucket < FIRSTBUCKET | bucket >= NBUCKETS)
394 >                return(0);
395          mp->next = free_list[bucket];
396          free_list[bucket] = mp;
397   #ifdef MSTATS
398          m_nfreed += (1 << bucket) + sizeof(M_HEAD);
399   #endif
400 +        return(1);
401   }
402  
403  
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 –
404   #ifdef MSTATS
405   printmemstats(fp)               /* print memory statistics to stream */
406   FILE    *fp;
# Line 270 | Line 411 | FILE   *fp;
411          unsigned int    total = 0;
412  
413          fprintf(fp, "Memory statistics:\n");
414 +        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
415          fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
416          fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
417          fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
418 +        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
419          fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
420          fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
421                          100.0*m_nwasted/m_nalloced);

Diff Legend

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