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.13 by greg, Wed Jul 17 11:35:47 1991 UTC vs.
Revision 2.6 by greg, Fri Sep 4 09:57:43 1992 UTC

# Line 1 | Line 1
1 < /* Copyright (c) 1991 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 + extern int      errno;
28 +
29   #ifdef MSTATS
30   #include  <stdio.h>
31 + static unsigned b_nsbrked = 0;
32   static unsigned b_nalloced = 0;
33   static unsigned b_nfreed = 0;
34   static unsigned b_nscrounged = 0;
35 + static unsigned b_ncompacted = 0;
36   static unsigned m_nalloced = 0;
37   static unsigned m_nfreed = 0;
38   static unsigned m_nwasted = 0;
# Line 38 | Line 45 | static unsigned        m_nwasted = 0;
45   #endif
46   #define  BYTES_WORD     sizeof(ALIGN)
47  
48 + #ifndef  MAXINCR
49   #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42 –
43 – #ifdef  NOVMEM
44 – #define  getpagesize()  1024
50   #endif
51                                          /* malloc free lists */
52   typedef union m_head {
# Line 62 | Line 67 | static M_HEAD  *free_list[NBUCKETS];
67  
68   static ALIGN    dummy_mem;
69  
70 + static char     *memlim[2];
71 +
72   #define DUMMYLOC        ((char *)&dummy_mem)
73  
74 + #define BADPTR(p)       ((p) < memlim[0] | (p) >= memlim[1])
75  
76 + #ifdef  MCOMP                   /* memory compaction routines */
77 + static char     seedtab[1024];          /* seed for compaction table */
78 +
79 + static struct mblk {
80 +        char            *ptr;   /* pointer to memory block */
81 +        unsigned        siz;    /* size of memory block */
82 + }       cptab = {seedtab, sizeof(seedtab)};
83 +
84 + #define mtab(mb)        ((struct mblk *)(mb)->ptr)
85 + #define mtablen(mb)     ((mb)->siz/sizeof(struct mblk))
86 +
87 +
88 + static int
89 + mbcmp(m1, m2)           /* compare memory block locations */
90 + register struct mblk    *m1, *m2;
91 + {
92 +                                /* put empty blocks at end */
93 +        if (m1->siz == 0)
94 +                return(m2->siz == 0 ? 0 : 1);
95 +        if (m2->siz == 0)
96 +                return(-1);
97 +                                /* otherwise, ascending order */
98 +        return(m1->ptr - m2->ptr);
99 + }
100 +
101 +
102 + int
103 + compactfree()           /* compact free lists (moving to table) */
104 + {
105 +        register struct mblk    *tp;
106 +        register int    bucket;
107 +        unsigned        n, bsiz, ncomp;
108 +                                /* fill table from free lists */
109 +        tp = mtab(&cptab); n = mtablen(&cptab);
110 +        bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
111 +        ncomp = 0;
112 +        for ( ; ; ) {
113 +                while (tp->siz) {       /* find empty slot */
114 +                        if (--n == 0)
115 +                                goto loopexit;
116 +                        tp++;
117 +                }
118 +                while (free_list[bucket] == NULL) {     /* find block */
119 +                        if (--bucket < FIRSTBUCKET)
120 +                                goto loopexit;
121 +                        bsiz >>= 1;
122 +                }
123 +                tp->ptr = (char *)free_list[bucket];
124 +                ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
125 +                free_list[bucket] = free_list[bucket]->next;
126 +        }
127 + loopexit:
128 +        if (ncomp == 0)
129 +                return(0);              /* nothing new to compact */
130 + #ifdef MSTATS
131 +        b_ncompacted += ncomp;
132 + #endif
133 +        tp = mtab(&cptab); n = mtablen(&cptab);         /* sort table */
134 +        qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
135 +        ncomp = 0;                                      /* collect blocks */
136 +        while (--n && tp[1].siz) {
137 +                if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
138 +                        tp[1].ptr = tp[0].ptr;
139 +                        tp[1].siz += tp[0].siz;
140 +                        ncomp += tp[0].siz;
141 +                        tp[0].siz = 0;
142 +                }
143 +                tp++;
144 +        }
145 +        return(ncomp);
146 + }
147 +
148 +
149   char *
150 + mcompact(np)            /* compact free lists to satisfy request */
151 + unsigned        *np;
152 + {
153 +        struct mblk     *tab;
154 +        unsigned        tablen;
155 +        register struct mblk    *bp, *big;
156 +
157 +        for ( ; ; ) {
158 +                                        /* compact free lists */
159 +                compactfree();
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+1) {
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 + #ifdef BSD
183 +                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
184 +                                tablen*sizeof(struct mblk));
185 +                bzero((char *)(mtab(&cptab)+tablen+1),
186 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
187 + #else
188 +                (void)memcpy((char *)(mtab(&cptab)+1), (char *)tab,
189 +                                tablen*sizeof(struct mblk));
190 +                memset((char *)(mtab(&cptab)+tablen+1), 0,
191 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
192 + #endif
193 +        }                       /* next round */
194 + }
195 + #endif          /* MCOMP */
196 +
197 +
198 + char *
199   mscrounge(np)           /* search free lists to satisfy request */
200   register unsigned       *np;
201   {
# Line 84 | Line 214 | register unsigned      *np;
214   #endif
215                          return(p);
216                  }
217 + #ifdef MCOMP
218 +        return(mcompact(np));           /* try compaction */
219 + #else
220          *np = 0;
221          return(NULL);
222 + #endif
223   }
224  
225  
# Line 105 | Line 239 | register unsigned  n;
239                  pagesz = amnt = getpagesize();
240                  nrem = (int)sbrk(0);                    /* page align break */
241                  nrem = pagesz - (nrem&(pagesz-1));
242 <                bpos = sbrk(nrem);                      /* word aligned! */
242 >                bpos = sbrk(nrem);
243                  if ((int)bpos == -1)
244                          return(NULL);
245 + #ifdef MSTATS
246 +                b_nsbrked += nrem;
247 + #endif
248 +                bpos += nrem & (BYTES_WORD-1);          /* align pointer */
249 +                nrem &= ~(BYTES_WORD-1);
250 +                memlim[0] = bpos;
251 +                memlim[1] = bpos + nrem;
252          }
253  
254          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
# Line 126 | Line 267 | register unsigned  n;
267                          if (p == NULL)                  /* we're really out */
268                                  return(NULL);
269                  }
270 + #ifdef MSTATS
271 +                else b_nsbrked += thisamnt;
272 + #endif
273                  if (p != bpos+nrem) {                   /* not an increment */
274                          bfree(bpos, nrem);              /* free what we have */
275                          bpos = p;
276                          nrem = thisamnt;
277                  } else                                  /* otherwise tack on */
278                          nrem += thisamnt;
279 +                if (bpos < memlim[0])
280 +                        memlim[0] = bpos;
281 +                if (bpos + nrem > memlim[1])
282 +                        memlim[1] = bpos + nrem;
283          }
284          p = bpos;
285          bpos += n;                                      /* advance */
# Line 150 | Line 298 | register unsigned  n;
298          register int    bucket;
299          register unsigned       bsiz;
300  
301 +        if (n < 1<<FIRSTBUCKET)
302 +                return;
303   #ifdef MSTATS
304          b_nfreed += n;
305   #endif
# Line 159 | Line 309 | register unsigned  n;
309                  p += bsiz;
310                  n -= bsiz;
311          }
312 +        if (p < memlim[0])
313 +                memlim[0] = p;
314 +        if (p + n > memlim[1])
315 +                memlim[1] = p + n;
316                                          /* fill big buckets first */
317          for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
318                          bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
# Line 175 | Line 329 | char *
329   malloc(n)                       /* allocate n bytes of memory */
330   unsigned        n;
331   {
178 –        extern int  errno;
332          register M_HEAD *mp;
333          register int    bucket;
334          register unsigned       bsiz;
# Line 217 | Line 370 | unsigned       n;
370          char    *p;
371          register unsigned       on;
372                                          /* get old size */
373 <        if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
373 >        if (op != DUMMYLOC && !BADPTR(op) &&
374 >                        ((M_HEAD *)op-1)->a.magic == MAGIC)
375                  on = 1 << ((M_HEAD *)op-1)->a.bucket;
376          else
377                  on = 0;
378          if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
379                  return(op);             /* same bucket */
380          if ((p = malloc(n)) == NULL)
381 <                return(NULL);
381 >                return(n<=on ? op : NULL);
382          if (on) {
383   #ifdef  BSD
384                  bcopy(op, p, n>on ? on : n);
# Line 243 | Line 397 | char   *p;
397          register M_HEAD *mp;
398          register int    bucket;
399  
400 <        if (p == NULL || p == DUMMYLOC)
400 >        if (p == DUMMYLOC)
401                  return(1);
402 +        if (BADPTR(p))
403 +                goto invalid;
404          mp = (M_HEAD *)p - 1;
405          if (mp->a.magic != MAGIC)               /* sanity check */
406 <                return(0);
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  
261 – #ifndef NOVMEM
262 – #ifndef BSD
263 – #include <sys/var.h>
264 – int
265 – getpagesize()                   /* use SYSV var structure to get page size */
266 – {
267 –        struct var  v;
268 –
269 –        uvar(&v);
270 –        return(1 << v.v_pageshift);
271 – }
272 – #endif
273 – #endif
274 –
275 –
422   #ifdef MSTATS
423   printmemstats(fp)               /* print memory statistics to stream */
424   FILE    *fp;
# Line 283 | Line 429 | FILE   *fp;
429          unsigned int    total = 0;
430  
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);

Diff Legend

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