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.1 by greg, Tue Sep 25 17:14:04 1990 UTC vs.
Revision 1.13 by greg, Wed Jul 17 11:35:47 1991 UTC

# Line 1 | Line 1
1 < /* Copyright (c) 1990 Regents of the University of California */
1 > /* Copyright (c) 1991 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   *
19   *      Greg Ward       Lawrence Berkeley Laboratory
20   */
21  
22 + #include  <errno.h>
23 +
24 + #ifdef MSTATS
25 + #include  <stdio.h>
26 + static unsigned b_nalloced = 0;
27 + static unsigned b_nfreed = 0;
28 + static unsigned b_nscrounged = 0;
29 + static unsigned m_nalloced = 0;
30 + static unsigned m_nfreed = 0;
31 + static unsigned m_nwasted = 0;
32 + #else
33   #define  NULL           0
34 + #endif
35  
36   #ifndef ALIGN
37   #define  ALIGN          int                     /* align type */
38   #endif
39   #define  BYTES_WORD     sizeof(ALIGN)
40  
41 + #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42 +
43   #ifdef  NOVMEM
44 < #define  getpagesize()  BYTES_WORD
44 > #define  getpagesize()  1024
45   #endif
29 –
46                                          /* malloc free lists */
47   typedef union m_head {
48          union m_head    *next;
49 <        int             bucket;
49 >        struct {
50 >                short           magic;
51 >                short           bucket;
52 >        }       a;
53          ALIGN           dummy;
54   } M_HEAD;
55  
56 + #define MAGIC           0x1a2           /* magic number for allocated memory */
57 +
58   #define FIRSTBUCKET     3
59   #define NBUCKETS        30
60  
61   static M_HEAD   *free_list[NBUCKETS];
62  
63 + static ALIGN    dummy_mem;
64  
65 + #define DUMMYLOC        ((char *)&dummy_mem)
66 +
67 +
68   char *
69 + mscrounge(np)           /* search free lists to satisfy request */
70 + register unsigned       *np;
71 + {
72 +        char    *p;
73 +        register int    bucket;
74 +        register unsigned       bsiz;
75 +
76 +        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
77 +                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
78 +                if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
79 +                        *np = bsiz+sizeof(M_HEAD);
80 +                        p = (char *)free_list[bucket];
81 +                        free_list[bucket] = free_list[bucket]->next;
82 + #ifdef MSTATS
83 +                        b_nscrounged += *np;
84 + #endif
85 +                        return(p);
86 +                }
87 +        *np = 0;
88 +        return(NULL);
89 + }
90 +
91 +
92 + char *
93   bmalloc(n)              /* allocate a block of n bytes, sans header */
94   register unsigned  n;
95   {
96          extern char  *sbrk();
97 <        static int  pagesz = 0;
98 <        static int  amnt;
97 >        static unsigned  pagesz = 0;
98 >        static unsigned  amnt;
99          static char  *bpos;
100 <        static int  nrem;
100 >        static unsigned  nrem;
101 >        unsigned  thisamnt;
102          register char   *p;
103  
104          if (pagesz == 0) {                              /* initialize */
105 <                amnt = pagesz = getpagesize();
105 >                pagesz = amnt = getpagesize();
106                  nrem = (int)sbrk(0);                    /* page align break */
107                  nrem = pagesz - (nrem&(pagesz-1));
108                  bpos = sbrk(nrem);                      /* word aligned! */
# Line 63 | Line 113 | register unsigned  n;
113          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
114  
115          if (n > nrem) {                                 /* need more core */
116 <                if (n > amnt)                   /* increase amount */
117 <                        amnt = (n+(pagesz-1))&~(pagesz-1);
118 <                p = sbrk(amnt);
119 <                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;
116 >                if (n > amnt) {                         /* big chunk */
117 >                        thisamnt = (n+(pagesz-1))&~(pagesz-1);
118 >                        if (thisamnt <= MAXINCR)        /* increase amnt */
119 >                                amnt = thisamnt;
120                  } else
121 <                        nrem += amnt;
121 >                        thisamnt = amnt;
122 >                p = sbrk(thisamnt);
123 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
124 >                        thisamnt = n;                   /* search free lists */
125 >                        p = mscrounge(&thisamnt);
126 >                        if (p == NULL)                  /* we're really out */
127 >                                return(NULL);
128 >                }
129 >                if (p != bpos+nrem) {                   /* not an increment */
130 >                        bfree(bpos, nrem);              /* free what we have */
131 >                        bpos = p;
132 >                        nrem = thisamnt;
133 >                } else                                  /* otherwise tack on */
134 >                        nrem += thisamnt;
135          }
136          p = bpos;
137          bpos += n;                                      /* advance */
138          nrem -= n;
139 + #ifdef MSTATS
140 +        b_nalloced += n;
141 + #endif
142          return(p);
143   }
144  
145  
146   bfree(p, n)                     /* free n bytes of random memory */
147 < char  *p;
148 < unsigned  n;
147 > register char  *p;
148 > register unsigned  n;
149   {
89 –        register M_HEAD *mp;
150          register int    bucket;
151          register unsigned       bsiz;
152 <                                        /* find largest bucket */
153 <        bucket = 0;
154 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
155 <                bucket++;
156 <        mp = (M_HEAD *)p;
157 <        while (bucket > FIRSTBUCKET) {
158 <                bsiz >>= 1;
159 <                bucket--;
160 <                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
101 <                        continue;
102 <                mp->next = free_list[bucket];
103 <                free_list[bucket] = mp;
104 <                (char *)mp += bsiz+sizeof(M_HEAD);
105 <                n -= bsiz+sizeof(M_HEAD);
152 >
153 > #ifdef MSTATS
154 >        b_nfreed += n;
155 > #endif
156 >                                        /* align pointer */
157 >        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
158 >        if (bsiz < BYTES_WORD) {
159 >                p += bsiz;
160 >                n -= bsiz;
161          }
162 +                                        /* fill big buckets first */
163 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
164 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
165 +                if (n >= bsiz+sizeof(M_HEAD)) {
166 +                        ((M_HEAD *)p)->next = free_list[bucket];
167 +                        free_list[bucket] = (M_HEAD *)p;
168 +                        p += bsiz+sizeof(M_HEAD);
169 +                        n -= bsiz+sizeof(M_HEAD);
170 +                }
171   }
172  
173  
# Line 111 | Line 175 | char *
175   malloc(n)                       /* allocate n bytes of memory */
176   unsigned        n;
177   {
178 +        extern int  errno;
179          register M_HEAD *mp;
180          register int    bucket;
181          register unsigned       bsiz;
182 <
183 <        bucket = FIRSTBUCKET;
184 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
185 <                bucket++;
186 <        if (free_list[bucket] == NULL) {
182 >                                        /* don't return NULL on 0 request */
183 >        if (n == 0)
184 >                return(DUMMYLOC);
185 >                                        /* find first bucket that fits */
186 >        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
187 >                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
188 >                if (bsiz >= n)
189 >                        break;
190 >        if (bucket >= NBUCKETS) {
191 >                errno = EINVAL;
192 >                return(NULL);
193 >        }
194 >        if (free_list[bucket] == NULL) {        /* need more core */
195                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
196                  if (mp == NULL)
197                          return(NULL);
198 <        } else {
198 >        } else {                                /* got it */
199                  mp = free_list[bucket];
200                  free_list[bucket] = mp->next;
201          }
202 <        mp->bucket = bucket;
202 > #ifdef MSTATS
203 >        m_nalloced += bsiz + sizeof(M_HEAD);
204 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
205 > #endif
206 >        mp->a.magic = MAGIC;                    /* tag block */
207 >        mp->a.bucket = bucket;
208          return((char *)(mp+1));
209   }
210  
211  
212   char *
213   realloc(op, n)                  /* reallocate memory using malloc() */
214 < char    *op;
214 > register char   *op;
215   unsigned        n;
216   {
217 <        register char   *p;
217 >        char    *p;
218          register unsigned       on;
219 <
220 <        if (op != NULL)
221 <                on = 1 << ((M_HEAD *)op-1)->bucket;
219 >                                        /* get old size */
220 >        if (op != NULL && op != DUMMYLOC && ((M_HEAD *)op-1)->a.magic == MAGIC)
221 >                on = 1 << ((M_HEAD *)op-1)->a.bucket;
222          else
223                  on = 0;
224 <        if (n <= on && n > on>>1)
224 >        if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
225                  return(op);             /* same bucket */
226 <        p = malloc(n);
149 <        if (p == NULL)
226 >        if ((p = malloc(n)) == NULL)
227                  return(NULL);
228 +        if (on) {
229   #ifdef  BSD
230 <        bcopy(op, p, n>on ? on : n);
230 >                bcopy(op, p, n>on ? on : n);
231   #else
232 <        (void)memcpy(p, op, n>on ? on : n);
232 >                (void)memcpy(p, op, n>on ? on : n);
233   #endif
234 <        free(op);
234 >                free(op);
235 >        }
236          return(p);
237   }
238  
# Line 164 | Line 243 | char   *p;
243          register M_HEAD *mp;
244          register int    bucket;
245  
246 +        if (p == NULL || p == DUMMYLOC)
247 +                return(1);
248          mp = (M_HEAD *)p - 1;
249 <        bucket = mp->bucket;
249 >        if (mp->a.magic != MAGIC)               /* sanity check */
250 >                return(0);
251 >        bucket = mp->a.bucket;
252          mp->next = free_list[bucket];
253          free_list[bucket] = mp;
254 + #ifdef MSTATS
255 +        m_nfreed += (1 << bucket) + sizeof(M_HEAD);
256 + #endif
257 +        return(1);
258   }
259  
260  
# Line 177 | Line 264 | char   *p;
264   int
265   getpagesize()                   /* use SYSV var structure to get page size */
266   {
180 –        static int  pagesz = 0;
267          struct var  v;
268  
269 <        if (pagesz == 0) {
270 <                uvar(&v);
185 <                pagesz = 1 << v.v_pageshift;
186 <        }
187 <        return(pagesz);
269 >        uvar(&v);
270 >        return(1 << v.v_pageshift);
271   }
272   #endif
273 + #endif
274 +
275 +
276 + #ifdef MSTATS
277 + printmemstats(fp)               /* print memory statistics to stream */
278 + FILE    *fp;
279 + {
280 +        register int    i;
281 +        int     n;
282 +        register M_HEAD *mp;
283 +        unsigned int    total = 0;
284 +
285 +        fprintf(fp, "Memory statistics:\n");
286 +        fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
287 +        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
288 +        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
289 +        fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
290 +        fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
291 +                        100.0*m_nwasted/m_nalloced);
292 +        fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
293 +        for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
294 +                n = 0;
295 +                for (mp = free_list[i]; mp != NULL; mp = mp->next)
296 +                        n++;
297 +                if (n) {
298 +                        fprintf(fp, "\t%d * %u\n", n, 1<<i);
299 +                        total += n * ((1<<i) + sizeof(M_HEAD));
300 +                }
301 +        }
302 +        fprintf(fp, "\t %u total bytes in free list\n", total);
303 + }
304   #endif

Diff Legend

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