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.7 by greg, Fri Sep 4 18:36:05 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 + #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;
# Line 38 | Line 51 | static unsigned        m_nwasted = 0;
51   #endif
52   #define  BYTES_WORD     sizeof(ALIGN)
53  
54 + #ifndef  MAXINCR
55   #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42 –
43 – #ifdef  NOVMEM
44 – #define  getpagesize()  1024
56   #endif
57                                          /* malloc free lists */
58   typedef union m_head {
# Line 62 | Line 73 | 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   {
# Line 84 | Line 213 | register unsigned      *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  
# Line 105 | Line 238 | register unsigned  n;
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. */
# Line 126 | Line 266 | register unsigned  n;
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 */
# Line 150 | Line 297 | register unsigned  n;
297          register int    bucket;
298          register unsigned       bsiz;
299  
300 +        if (n < 1<<FIRSTBUCKET)
301 +                return;
302   #ifdef MSTATS
303          b_nfreed += n;
304   #endif
# Line 159 | Line 308 | register unsigned  n;
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)
# Line 175 | Line 328 | char *
328   malloc(n)                       /* allocate n bytes of memory */
329   unsigned        n;
330   {
178 –        extern int  errno;
331          register M_HEAD *mp;
332          register int    bucket;
333          register unsigned       bsiz;
# Line 217 | Line 369 | unsigned       n;
369          char    *p;
370          register unsigned       on;
371                                          /* get old size */
372 <        if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
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 || on == 1<<FIRSTBUCKET))
378                  return(op);             /* same bucket */
379          if ((p = malloc(n)) == NULL)
380 <                return(NULL);
380 >                return(n<=on ? op : NULL);
381          if (on) {
229 – #ifdef  BSD
382                  bcopy(op, p, n>on ? on : n);
231 – #else
232 –                (void)memcpy(p, op, n>on ? on : n);
233 – #endif
383                  free(op);
384          }
385          return(p);
# Line 243 | Line 392 | char   *p;
392          register M_HEAD *mp;
393          register int    bucket;
394  
395 <        if (p == NULL || p == DUMMYLOC)
395 >        if (p == DUMMYLOC)
396                  return(1);
397 +        if (BADPTR(p))
398 +                goto invalid;
399          mp = (M_HEAD *)p - 1;
400          if (mp->a.magic != MAGIC)               /* sanity check */
401 <                return(0);
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  
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 –
417   #ifdef MSTATS
418   printmemstats(fp)               /* print memory statistics to stream */
419   FILE    *fp;
# Line 283 | Line 424 | FILE   *fp;
424          unsigned int    total = 0;
425  
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);

Diff Legend

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