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.2 by greg, Tue Sep 25 18:56:37 1990 UTC vs.
Revision 1.4 by greg, Wed Sep 26 08:26:11 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 memory it can find to satisfy the
17 + *      request along with the number of bytes (modified).
18   *
19   *      Greg Ward       Lawrence Berkeley Laboratory
20   */
# Line 23 | Line 26 | static char SCCSid[] = "$SunId$ LBL";
26   #endif
27   #define  BYTES_WORD     sizeof(ALIGN)
28  
29 + #define  MAXINCR        (1<<18)                 /* largest sbrk(2) increment */
30 +
31   #ifdef  NOVMEM
32   #define  getpagesize()  BYTES_WORD
33   #endif
29 –
34                                          /* malloc free lists */
35   typedef union m_head {
36          union m_head    *next;
# Line 41 | Line 45 | static M_HEAD  *free_list[NBUCKETS];
45  
46  
47   char *
48 + mscrounge(np)           /* search free lists to satisfy request */
49 + register unsigned       *np;
50 + {
51 +        char    *p;
52 +        register int    bucket;
53 +        register unsigned       bsiz;
54 +
55 +        for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
56 +                        bucket < NBUCKETS; bucket++, bsiz <<= 1)
57 +                if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
58 +                        *np = bsiz+sizeof(M_HEAD);
59 +                        p = (char *)free_list[bucket];
60 +                        free_list[bucket] = free_list[bucket]->next;
61 +                        return(p);
62 +                }
63 +        *np = 0;
64 +        return(NULL);
65 + }
66 +
67 +
68 + char *
69   bmalloc(n)              /* allocate a block of n bytes, sans header */
70   register unsigned  n;
71   {
72          extern char  *sbrk();
73 <        static int  pagesz = 0;
74 <        static int  amnt;
73 >        static unsigned  pagesz = 0;
74 >        static unsigned  amnt;
75          static char  *bpos;
76 <        static int  nrem;
76 >        static unsigned  nrem;
77 >        unsigned  thisamnt;
78          register char   *p;
79  
80          if (pagesz == 0) {                              /* initialize */
# Line 63 | Line 89 | register unsigned  n;
89          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
90  
91          if (n > nrem) {                                 /* need more core */
92 <                if (n > amnt)                   /* increase amount */
93 <                        amnt = (n+(pagesz-1))&~(pagesz-1);
94 <                p = sbrk(amnt);
95 <                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;
92 >                if (n > amnt) {                         /* big chunk */
93 >                        thisamnt = (n+(pagesz-1))&~(pagesz-1);
94 >                        if (thisamnt <= MAXINCR)        /* increase amnt */
95 >                                amnt = thisamnt;
96                  } else
97 <                        nrem += amnt;
97 >                        thisamnt = amnt;
98 >                p = sbrk(thisamnt);
99 >                if ((int)p == -1) {                     /* uh-oh, ENOMEM */
100 >                        thisamnt = n;                   /* search free lists */
101 >                        p = mscrounge(&thisamnt);
102 >                        if (p == NULL)                  /* we're really out */
103 >                                return(NULL);
104 >                }
105 >                if (p != bpos+nrem) {                   /* not an increment */
106 >                        bfree(bpos, nrem);              /* free what we have */
107 >                        bpos = p;
108 >                        nrem = thisamnt;
109 >                } else                                  /* otherwise tack on */
110 >                        nrem += thisamnt;
111          }
112          p = bpos;
113          bpos += n;                                      /* advance */
# Line 88 | Line 122 | register unsigned  n;
122   {
123          register int    bucket;
124          register unsigned       bsiz;
125 <                                        /* find largest bucket */
126 <        bucket = 0;
127 <        for (bsiz = 1; bsiz+sizeof(M_HEAD) <= n; bsiz <<= 1)
128 <                bucket++;
129 <        while (bucket > FIRSTBUCKET) {
96 <                bsiz >>= 1;
97 <                bucket--;
98 <                if (n < bsiz+sizeof(M_HEAD))    /* nothing for this bucket */
99 <                        continue;
100 <                ((M_HEAD *)p)->next = free_list[bucket];
101 <                free_list[bucket] = (M_HEAD *)p;
102 <                p += bsiz+sizeof(M_HEAD);
103 <                n -= bsiz+sizeof(M_HEAD);
125 >                                        /* align pointer */
126 >        bsiz = BYTES_WORD - ((unsigned)p&~(BYTES_WORD-1));
127 >        if (bsiz < BYTES_WORD) {
128 >                p += bsiz;
129 >                n -= bsiz;
130          }
131 +                                        /* fill big buckets first */
132 +        for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
133 +                        bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
134 +                if (n >= bsiz+sizeof(M_HEAD)) {
135 +                        ((M_HEAD *)p)->next = free_list[bucket];
136 +                        free_list[bucket] = (M_HEAD *)p;
137 +                        p += bsiz+sizeof(M_HEAD);
138 +                        n -= bsiz+sizeof(M_HEAD);
139 +                }
140   }
141  
142  
# Line 119 | Line 154 | unsigned       n;
154          bucket = FIRSTBUCKET;
155          for (bsiz = 1<<FIRSTBUCKET; bsiz < n; bsiz <<= 1)
156                  bucket++;
157 <        if (free_list[bucket] == NULL) {
157 >        if (free_list[bucket] == NULL) {        /* need more core */
158                  mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
159                  if (mp == NULL)
160                          return(NULL);
161 <        } else {
161 >        } else {                                /* got it */
162                  mp = free_list[bucket];
163                  free_list[bucket] = mp->next;
164          }
165 <        mp->bucket = bucket;
165 >        mp->bucket = bucket;                    /* tag block */
166          return((char *)(mp+1));
167   }
168  
# Line 137 | Line 172 | realloc(op, n)                 /* reallocate memory using malloc() *
172   char    *op;
173   unsigned        n;
174   {
175 +        extern char     *memcpy();
176          register char   *p;
177          register unsigned       on;
178  
179 <        if (op != NULL)
180 <                on = 1 << ((M_HEAD *)op-1)->bucket;
181 <        else
182 <                on = 0;
183 <        if (n <= on && n > on>>1)
148 <                return(op);             /* same bucket */
149 <        p = malloc(n);
150 <        if (p != NULL)
179 >        free(op);                       /* free it first */
180 >        p = malloc(n);                  /* p==op if same bucket */
181 >        if (p == NULL)
182 >                return(NULL);
183 >        if (p != op)                    /* different bucket, do copy */
184   #ifdef  BSD
185                  bcopy(op, p, n>on ? on : n);
186   #else
187                  (void)memcpy(p, op, n>on ? on : n);
188   #endif
156 –        free(op);
189          return(p);
190   }
191  

Diff Legend

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