1 /* Memory allocator `malloc'.
2 Copyright 1990, 1991, 1992 Free Software Foundation
3
4 Written May 1989 by Mike Haertel.
5 Heavily modified Mar 1992 by Fred Fish for mmap'd version.
6
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public License as
9 published by the Free Software Foundation; either version 2 of the
10 License, or (at your option) any later version.
11
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Library General Public License for more details.
16
17 You should have received a copy of the GNU Library General Public
18 License along with the GNU C Library; see the file COPYING.LIB. If
19 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.
21
22 The author may be reached (Email) at the address mike@ai.mit.edu,
23 or (US mail) as Mike Haertel c/o Free Software Foundation. */
24
25 #include <string.h> /* Prototypes for memcpy, memmove, memset, etc */
26
27 #include "mmprivate.h"
28
29 /* Prototypes for local functions */
30
31 static int initialize PARAMS ((struct mdesc *));
32 static PTR morecore PARAMS ((struct mdesc *, size_t));
33 static PTR align PARAMS ((struct mdesc *, size_t));
34
35 /* Aligned allocation. */
36
37 static PTR
align(mdp,size)38 align (mdp, size)
39 struct mdesc *mdp;
40 size_t size;
41 {
42 PTR result;
43 unsigned long int adj;
44
45 result = mdp -> morecore (mdp, size);
46 adj = RESIDUAL (result, BLOCKSIZE);
47 if (adj != 0)
48 {
49 adj = BLOCKSIZE - adj;
50 mdp -> morecore (mdp, adj);
51 result = (char *) result + adj;
52 }
53 return (result);
54 }
55
56 /* Set everything up and remember that we have. */
57
58 static int
initialize(mdp)59 initialize (mdp)
60 struct mdesc *mdp;
61 {
62 mdp -> heapsize = HEAP / BLOCKSIZE;
63 mdp -> heapinfo = (malloc_info *)
64 align (mdp, mdp -> heapsize * sizeof (malloc_info));
65 if (mdp -> heapinfo == NULL)
66 {
67 return (0);
68 }
69 memset ((PTR)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
70 mdp -> heapinfo[0].free.size = 0;
71 mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
72 mdp -> heapindex = 0;
73 mdp -> heapbase = (char *) mdp -> heapinfo;
74 mdp -> flags |= MMALLOC_INITIALIZED;
75 return (1);
76 }
77
78 /* Get neatly aligned memory, initializing or
79 growing the heap info table as necessary. */
80
81 static PTR
morecore(mdp,size)82 morecore (mdp, size)
83 struct mdesc *mdp;
84 size_t size;
85 {
86 PTR result;
87 malloc_info *newinfo, *oldinfo;
88 size_t newsize;
89
90 result = align (mdp, size);
91 if (result == NULL)
92 {
93 return (NULL);
94 }
95
96 /* Check if we need to grow the info table. */
97 if ((size_t) BLOCK ((char *) result + size) > mdp -> heapsize)
98 {
99 newsize = mdp -> heapsize;
100 while ((size_t) BLOCK ((char *) result + size) > newsize)
101 {
102 newsize *= 2;
103 }
104 newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
105 if (newinfo == NULL)
106 {
107 mdp -> morecore (mdp, -size);
108 return (NULL);
109 }
110 memset ((PTR) newinfo, 0, newsize * sizeof (malloc_info));
111 memcpy ((PTR) newinfo, (PTR) mdp -> heapinfo,
112 mdp -> heapsize * sizeof (malloc_info));
113 oldinfo = mdp -> heapinfo;
114 newinfo[BLOCK (oldinfo)].busy.type = 0;
115 newinfo[BLOCK (oldinfo)].busy.info.size
116 = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
117 mdp -> heapinfo = newinfo;
118 __mmalloc_free (mdp, (PTR)oldinfo);
119 mdp -> heapsize = newsize;
120 }
121
122 mdp -> heaplimit = BLOCK ((char *) result + size);
123 return (result);
124 }
125
126 /* Allocate memory from the heap. */
127
128 PTR
mmalloc(md,size)129 mmalloc (md, size)
130 PTR md;
131 size_t size;
132 {
133 struct mdesc *mdp;
134 PTR result;
135 size_t block, blocks, lastblocks, start;
136 register size_t i;
137 struct list *next;
138 register size_t log;
139
140 if (size == 0)
141 {
142 return (NULL);
143 }
144
145 mdp = MD_TO_MDP (md);
146
147 if (mdp -> mmalloc_hook != NULL)
148 {
149 return ((*mdp -> mmalloc_hook) (md, size));
150 }
151
152 if (!(mdp -> flags & MMALLOC_INITIALIZED))
153 {
154 if (!initialize (mdp))
155 {
156 return (NULL);
157 }
158 }
159
160 if (size < sizeof (struct list))
161 {
162 size = sizeof (struct list);
163 }
164
165 /* Determine the allocation policy based on the request size. */
166 if (size <= BLOCKSIZE / 2)
167 {
168 /* Small allocation to receive a fragment of a block.
169 Determine the logarithm to base two of the fragment size. */
170 log = 1;
171 --size;
172 while ((size /= 2) != 0)
173 {
174 ++log;
175 }
176
177 /* Look in the fragment lists for a
178 free fragment of the desired size. */
179 next = mdp -> fraghead[log].next;
180 if (next != NULL)
181 {
182 /* There are free fragments of this size.
183 Pop a fragment out of the fragment list and return it.
184 Update the block's nfree and first counters. */
185 result = (PTR) next;
186 next -> prev -> next = next -> next;
187 if (next -> next != NULL)
188 {
189 next -> next -> prev = next -> prev;
190 }
191 block = BLOCK (result);
192 if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
193 {
194 mdp -> heapinfo[block].busy.info.frag.first =
195 RESIDUAL (next -> next, BLOCKSIZE) >> log;
196 }
197
198 /* Update the statistics. */
199 mdp -> heapstats.chunks_used++;
200 mdp -> heapstats.bytes_used += 1 << log;
201 mdp -> heapstats.chunks_free--;
202 mdp -> heapstats.bytes_free -= 1 << log;
203 }
204 else
205 {
206 /* No free fragments of the desired size, so get a new block
207 and break it into fragments, returning the first. */
208 result = mmalloc (md, BLOCKSIZE);
209 if (result == NULL)
210 {
211 return (NULL);
212 }
213
214 /* Link all fragments but the first into the free list. */
215 for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
216 {
217 next = (struct list *) ((char *) result + (i << log));
218 next -> next = mdp -> fraghead[log].next;
219 next -> prev = &mdp -> fraghead[log];
220 next -> prev -> next = next;
221 if (next -> next != NULL)
222 {
223 next -> next -> prev = next;
224 }
225 }
226
227 /* Initialize the nfree and first counters for this block. */
228 block = BLOCK (result);
229 mdp -> heapinfo[block].busy.type = log;
230 mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
231 mdp -> heapinfo[block].busy.info.frag.first = i - 1;
232
233 mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
234 mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
235 mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
236 }
237 }
238 else
239 {
240 /* Large allocation to receive one or more blocks.
241 Search the free list in a circle starting at the last place visited.
242 If we loop completely around without finding a large enough
243 space we will have to get more memory from the system. */
244 blocks = BLOCKIFY(size);
245 start = block = MALLOC_SEARCH_START;
246 while (mdp -> heapinfo[block].free.size < blocks)
247 {
248 block = mdp -> heapinfo[block].free.next;
249 if (block == start)
250 {
251 /* Need to get more from the system. Check to see if
252 the new core will be contiguous with the final free
253 block; if so we don't need to get as much. */
254 block = mdp -> heapinfo[0].free.prev;
255 lastblocks = mdp -> heapinfo[block].free.size;
256 if (mdp -> heaplimit != 0 &&
257 block + lastblocks == mdp -> heaplimit &&
258 mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
259 (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
260 {
261 /* Which block we are extending (the `final free
262 block' referred to above) might have changed, if
263 it got combined with a freed info table. */
264 block = mdp -> heapinfo[0].free.prev;
265
266 mdp -> heapinfo[block].free.size += (blocks - lastblocks);
267 mdp -> heapstats.bytes_free +=
268 (blocks - lastblocks) * BLOCKSIZE;
269 continue;
270 }
271 result = morecore(mdp, blocks * BLOCKSIZE);
272 if (result == NULL)
273 {
274 return (NULL);
275 }
276 block = BLOCK (result);
277 mdp -> heapinfo[block].busy.type = 0;
278 mdp -> heapinfo[block].busy.info.size = blocks;
279 mdp -> heapstats.chunks_used++;
280 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
281 return (result);
282 }
283 }
284
285 /* At this point we have found a suitable free list entry.
286 Figure out how to remove what we need from the list. */
287 result = ADDRESS(block);
288 if (mdp -> heapinfo[block].free.size > blocks)
289 {
290 /* The block we found has a bit left over,
291 so relink the tail end back into the free list. */
292 mdp -> heapinfo[block + blocks].free.size
293 = mdp -> heapinfo[block].free.size - blocks;
294 mdp -> heapinfo[block + blocks].free.next
295 = mdp -> heapinfo[block].free.next;
296 mdp -> heapinfo[block + blocks].free.prev
297 = mdp -> heapinfo[block].free.prev;
298 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
299 = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
300 = mdp -> heapindex = block + blocks;
301 }
302 else
303 {
304 /* The block exactly matches our requirements,
305 so just remove it from the list. */
306 mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
307 = mdp -> heapinfo[block].free.prev;
308 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
309 = mdp -> heapindex = mdp -> heapinfo[block].free.next;
310 mdp -> heapstats.chunks_free--;
311 }
312
313 mdp -> heapinfo[block].busy.type = 0;
314 mdp -> heapinfo[block].busy.info.size = blocks;
315 mdp -> heapstats.chunks_used++;
316 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
317 mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
318 }
319
320 return (result);
321 }
322
323 /* When using this package, provide a version of malloc/realloc/free built
324 on top of it, so that if we use the default sbrk() region we will not
325 collide with another malloc package trying to do the same thing, if
326 the application contains any "hidden" calls to malloc/realloc/free (such
327 as inside a system library). */
328
329 PTR
malloc(size)330 malloc (size)
331 size_t size;
332 {
333 PTR result;
334
335 result = mmalloc ((PTR) NULL, size);
336 return (result);
337 }
338