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

Diff Legend

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