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.3 by greg, Wed Sep 26 06:23:10 1990 UTC vs.
Revision 1.11 by greg, Tue Dec 4 20:46:46 1990 UTC

# 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(2).  However, bmalloc will
12 – *      call mscrounge() if sbrk fails.
13 – * 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 < * mscrounge() returns whatever memory it can find to satisfy the
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<<18)                 /* largest sbrk(2) increment */
41 > #define  MAXINCR        (1<<16)                 /* largest sbrk(2) increment */
42  
43   #ifdef  NOVMEM
44 < #define  getpagesize()  BYTES_WORD
44 > #define  getpagesize()  1024
45   #endif
46                                          /* malloc free lists */
47   typedef union m_head {
# Line 43 | Line 55 | typedef union m_head {
55  
56   static M_HEAD   *free_list[NBUCKETS];
57  
58 + static char     DUMMYLOC[BYTES_WORD];
59  
60 +
61   char *
62 < mscrounge(np)           /* search free lists trying to satisfy request */
62 > mscrounge(np)           /* search free lists to satisfy request */
63   register unsigned       *np;
64   {
65          char    *p;
# Line 58 | Line 72 | register unsigned      *np;
72                          *np = bsiz+sizeof(M_HEAD);
73                          p = (char *)free_list[bucket];
74                          free_list[bucket] = free_list[bucket]->next;
75 + #ifdef MSTATS
76 +                        b_nscrounged += *np;
77 + #endif
78                          return(p);
79                  }
80          *np = 0;
# Line 77 | Line 94 | register unsigned  n;
94          unsigned  thisamnt;
95          register char   *p;
96  
97 + #ifdef MSTATS
98 +        b_nalloced += n;
99 + #endif
100          if (pagesz == 0) {                              /* initialize */
101                  pagesz = amnt = getpagesize();
102                  nrem = (int)sbrk(0);                    /* page align break */
# Line 96 | Line 116 | register unsigned  n;
116                  } else
117                          thisamnt = amnt;
118                  p = sbrk(thisamnt);
119 <                if ((int)p == -1) {                     /* uh-oh */
119 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
120                          thisamnt = n;                   /* search free lists */
121                          p = mscrounge(&thisamnt);
122                          if (p == NULL)                  /* we're really out */
123                                  return(NULL);
124                  }
125                  if (p != bpos+nrem) {                   /* not an increment */
126 <                        bfree(bpos, nrem);
126 >                        bfree(bpos, nrem);              /* free what we have */
127                          bpos = p;
128                          nrem = thisamnt;
129 <                } else
129 >                } else                                  /* otherwise tack on */
130                          nrem += thisamnt;
131          }
132          p = bpos;
# Line 122 | Line 142 | register unsigned  n;
142   {
143          register int    bucket;
144          register unsigned       bsiz;
145 <                                        /* find largest bucket */
146 <        bucket = 0;
147 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
148 <                bucket++;
149 <        while (bucket > FIRSTBUCKET) {
150 <                bsiz >>= 1;
151 <                bucket--;
152 <                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
153 <                        continue;
134 <                ((M_HEAD *)p)->next = free_list[bucket];
135 <                free_list[bucket] = (M_HEAD *)p;
136 <                p += bsiz+sizeof(M_HEAD);
137 <                n -= bsiz+sizeof(M_HEAD);
145 >
146 > #ifdef MSTATS
147 >        b_nfreed += n;
148 > #endif
149 >                                        /* align pointer */
150 >        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
151 >        if (bsiz < BYTES_WORD) {
152 >                p += bsiz;
153 >                n -= bsiz;
154          }
155 +                                        /* fill big buckets first */
156 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
157 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
158 +                if (n >= bsiz+sizeof(M_HEAD)) {
159 +                        ((M_HEAD *)p)->next = free_list[bucket];
160 +                        free_list[bucket] = (M_HEAD *)p;
161 +                        p += bsiz+sizeof(M_HEAD);
162 +                        n -= bsiz+sizeof(M_HEAD);
163 +                }
164   }
165  
166  
# Line 143 | Line 168 | char *
168   malloc(n)                       /* allocate n bytes of memory */
169   unsigned        n;
170   {
171 +        extern int  errno;
172          register M_HEAD *mp;
173          register int    bucket;
174          register unsigned       bsiz;
175 <
175 >                                        /* don't return NULL on 0 request */
176          if (n == 0)
177 <                return(NULL);
177 >                return(DUMMYLOC);
178                                          /* find first bucket that fits */
179 <        bucket = FIRSTBUCKET;
180 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
181 <                bucket++;
182 <        if (free_list[bucket] == NULL) {
179 >        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
180 >                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
181 >                if (bsiz >= n)
182 >                        break;
183 >        if (bucket >= NBUCKETS) {
184 >                errno = EINVAL;
185 >                return(NULL);
186 >        }
187 > #ifdef MSTATS
188 >        m_nalloced += bsiz + sizeof(M_HEAD);
189 >        m_nwasted += bsiz + sizeof(M_HEAD) - n;
190 > #endif
191 >        if (free_list[bucket] == NULL) {        /* need more core */
192                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
193                  if (mp == NULL)
194                          return(NULL);
195 <        } else {
195 >        } else {                                /* got it */
196                  mp = free_list[bucket];
197                  free_list[bucket] = mp->next;
198          }
199 <        mp->bucket = bucket;
199 >        mp->bucket = bucket;                    /* tag block */
200          return((char *)(mp+1));
201   }
202  
203  
204   char *
205   realloc(op, n)                  /* reallocate memory using malloc() */
206 < char    *op;
206 > register char   *op;
207   unsigned        n;
208   {
209 <        register char   *p;
209 >        char    *p;
210          register unsigned       on;
211 <
212 <        if (op != NULL)
211 >                                        /* get old size */
212 >        if (op != NULL && op != DUMMYLOC)
213                  on = 1 << ((M_HEAD *)op-1)->bucket;
214          else
215                  on = 0;
216 <        if (n <= on && n > on>>1)
216 >        if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
217                  return(op);             /* same bucket */
218          p = malloc(n);
219          if (p != NULL)
# Line 198 | Line 233 | char   *p;
233          register M_HEAD *mp;
234          register int    bucket;
235  
236 <        if (p == NULL)
236 >        if (p == NULL || p == DUMMYLOC)
237                  return;
238          mp = (M_HEAD *)p - 1;
239          bucket = mp->bucket;
240          mp->next = free_list[bucket];
241          free_list[bucket] = mp;
242 + #ifdef MSTATS
243 +        m_nfreed += (1 << bucket) + sizeof(M_HEAD);
244 + #endif
245   }
246  
247  
# Line 213 | Line 251 | char   *p;
251   int
252   getpagesize()                   /* use SYSV var structure to get page size */
253   {
216 –        static int  pagesz = 0;
254          struct var  v;
255  
256 <        if (pagesz == 0) {
257 <                uvar(&v);
221 <                pagesz = 1 << v.v_pageshift;
222 <        }
223 <        return(pagesz);
256 >        uvar(&v);
257 >        return(1 << v.v_pageshift);
258   }
259   #endif
260 + #endif
261 +
262 +
263 + #ifdef MSTATS
264 + printmemstats(fp)               /* print memory statistics to stream */
265 + FILE    *fp;
266 + {
267 +        register int    i;
268 +        int     n;
269 +        register M_HEAD *mp;
270 +        unsigned int    total = 0;
271 +
272 +        fprintf(fp, "Memory statistics:\n");
273 +        fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
274 +        fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
275 +        fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
276 +        fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
277 +        fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
278 +                        100.0*m_nwasted/m_nalloced);
279 +        fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
280 +        for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
281 +                n = 0;
282 +                for (mp = free_list[i]; mp != NULL; mp = mp->next)
283 +                        n++;
284 +                if (n) {
285 +                        fprintf(fp, "\t%d * %u\n", n, 1<<i);
286 +                        total += n * ((1<<i) + sizeof(M_HEAD));
287 +                }
288 +        }
289 +        fprintf(fp, "\t %u total bytes in free list\n", total);
290 + }
291   #endif

Diff Legend

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