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.8 by greg, Wed Oct 3 16:20:38 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   #define  NULL           0
25  
26   #ifndef ALIGN
# Line 23 | Line 28 | static char SCCSid[] = "$SunId$ LBL";
28   #endif
29   #define  BYTES_WORD     sizeof(ALIGN)
30  
31 + #define  MAXINCR        (1<<18)                 /* largest sbrk(2) increment */
32 +
33   #ifdef  NOVMEM
34   #define  getpagesize()  BYTES_WORD
35   #endif
29 –
36                                          /* malloc free lists */
37   typedef union m_head {
38          union m_head    *next;
# Line 41 | Line 47 | static M_HEAD  *free_list[NBUCKETS];
47  
48  
49   char *
50 + mscrounge(np)           /* search free lists to satisfy request */
51 + register unsigned       *np;
52 + {
53 +        char    *p;
54 +        register int    bucket;
55 +        register unsigned       bsiz;
56 +
57 +        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
58 +                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
59 +                if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
60 +                        *np = bsiz+sizeof(M_HEAD);
61 +                        p = (char *)free_list[bucket];
62 +                        free_list[bucket] = free_list[bucket]->next;
63 +                        return(p);
64 +                }
65 +        *np = 0;
66 +        return(NULL);
67 + }
68 +
69 +
70 + char *
71   bmalloc(n)              /* allocate a block of n bytes, sans header */
72   register unsigned  n;
73   {
74          extern char  *sbrk();
75 <        static int  pagesz = 0;
76 <        static int  amnt;
75 >        static unsigned  pagesz = 0;
76 >        static unsigned  amnt;
77          static char  *bpos;
78 <        static int  nrem;
78 >        static unsigned  nrem;
79 >        unsigned  thisamnt;
80          register char   *p;
81  
82          if (pagesz == 0) {                              /* initialize */
83 <                amnt = pagesz = getpagesize();
83 >                pagesz = amnt = getpagesize();
84                  nrem = (int)sbrk(0);                    /* page align break */
85                  nrem = pagesz - (nrem&(pagesz-1));
86                  bpos = sbrk(nrem);                      /* word aligned! */
# Line 63 | Line 91 | register unsigned  n;
91          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
92  
93          if (n > nrem) {                                 /* need more core */
94 <                if (n > amnt)                   /* increase amount */
95 <                        amnt = (n+(pagesz-1))&~(pagesz-1);
96 <                p = sbrk(amnt);
97 <                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;
94 >                if (n > amnt) {                         /* big chunk */
95 >                        thisamnt = (n+(pagesz-1))&~(pagesz-1);
96 >                        if (thisamnt <= MAXINCR)        /* increase amnt */
97 >                                amnt = thisamnt;
98                  } else
99 <                        nrem += amnt;
99 >                        thisamnt = amnt;
100 >                p = sbrk(thisamnt);
101 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
102 >                        thisamnt = n;                   /* search free lists */
103 >                        p = mscrounge(&thisamnt);
104 >                        if (p == NULL)                  /* we're really out */
105 >                                return(NULL);
106 >                }
107 >                if (p != bpos+nrem) {                   /* not an increment */
108 >                        bfree(bpos, nrem);              /* free what we have */
109 >                        bpos = p;
110 >                        nrem = thisamnt;
111 >                } else                                  /* otherwise tack on */
112 >                        nrem += thisamnt;
113          }
114          p = bpos;
115          bpos += n;                                      /* advance */
# Line 83 | Line 119 | register unsigned  n;
119  
120  
121   bfree(p, n)                     /* free n bytes of random memory */
122 < char  *p;
123 < unsigned  n;
122 > register char  *p;
123 > register unsigned  n;
124   {
89 –        register M_HEAD *mp;
125          register int    bucket;
126          register unsigned       bsiz;
127 <                                        /* find largest bucket */
128 <        bucket = 0;
129 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
130 <                bucket++;
131 <        mp = (M_HEAD *)p;
97 <        while (bucket > FIRSTBUCKET) {
98 <                bsiz >>= 1;
99 <                bucket--;
100 <                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);
127 >                                        /* align pointer */
128 >        bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
129 >        if (bsiz < BYTES_WORD) {
130 >                p += bsiz;
131 >                n -= bsiz;
132          }
133 +                                        /* fill big buckets first */
134 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
135 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
136 +                if (n >= bsiz+sizeof(M_HEAD)) {
137 +                        ((M_HEAD *)p)->next = free_list[bucket];
138 +                        free_list[bucket] = (M_HEAD *)p;
139 +                        p += bsiz+sizeof(M_HEAD);
140 +                        n -= bsiz+sizeof(M_HEAD);
141 +                }
142   }
143  
144  
# Line 111 | Line 146 | char *
146   malloc(n)                       /* allocate n bytes of memory */
147   unsigned        n;
148   {
149 +        extern int  errno;
150          register M_HEAD *mp;
151          register int    bucket;
152          register unsigned       bsiz;
153 <
154 <        bucket = FIRSTBUCKET;
155 <        for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
156 <                bucket++;
157 <        if (free_list[bucket] == NULL) {
153 >                                        /* find first bucket that fits */
154 >        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
155 >                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
156 >                if (bsiz >= n)
157 >                        break;
158 >        if (bucket >= NBUCKETS) {
159 >                errno = EINVAL;
160 >                return(NULL);
161 >        }
162 >        if (free_list[bucket] == NULL) {        /* need more core */
163                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
164                  if (mp == NULL)
165                          return(NULL);
166 <        } else {
166 >        } else {                                /* got it */
167                  mp = free_list[bucket];
168                  free_list[bucket] = mp->next;
169          }
170 <        mp->bucket = bucket;
170 >        mp->bucket = bucket;                    /* tag block */
171          return((char *)(mp+1));
172   }
173  
174  
175   char *
176   realloc(op, n)                  /* reallocate memory using malloc() */
177 < char    *op;
177 > register char   *op;
178   unsigned        n;
179   {
180 <        register char   *p;
180 >        char    *p;
181          register unsigned       on;
182 <
182 >                                        /* get old size */
183          if (op != NULL)
184                  on = 1 << ((M_HEAD *)op-1)->bucket;
185          else
186                  on = 0;
187 <        if (n <= on && n > on>>1)
187 >        if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
188                  return(op);             /* same bucket */
189          p = malloc(n);
190 <        if (p == NULL)
150 <                return(NULL);
190 >        if (p != NULL)
191   #ifdef  BSD
192 <        bcopy(op, p, n>on ? on : n);
192 >                bcopy(op, p, n>on ? on : n);
193   #else
194 <        (void)memcpy(p, op, n>on ? on : n);
194 >                (void)memcpy(p, op, n>on ? on : n);
195   #endif
196          free(op);
197          return(p);
# Line 164 | Line 204 | char   *p;
204          register M_HEAD *mp;
205          register int    bucket;
206  
207 +        if (p == NULL)
208 +                return;
209          mp = (M_HEAD *)p - 1;
210          bucket = mp->bucket;
211          mp->next = free_list[bucket];
# Line 177 | Line 219 | char   *p;
219   int
220   getpagesize()                   /* use SYSV var structure to get page size */
221   {
180 –        static int  pagesz = 0;
222          struct var  v;
223  
224 <        if (pagesz == 0) {
225 <                uvar(&v);
185 <                pagesz = 1 << v.v_pageshift;
186 <        }
187 <        return(pagesz);
224 >        uvar(&v);
225 >        return(1 << v.v_pageshift);
226   }
227   #endif
228   #endif

Diff Legend

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