1 /* Memory allocator `malloc'.
2 Copyright 1990, 1991, 1992 Free Software Foundation
4 Written May 1989 by Mike Haertel.
5 Heavily modified Mar 1992 by Fred Fish for mmap'd version.
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.
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.
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.
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. */
25 #include <string.h> /* Prototypes for memcpy, memmove, memset, etc */
27 #include "mmprivate.h"
29 /* Prototypes for local functions */
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));
35 /* Aligned allocation. */
43 unsigned long int adj;
45 result = mdp -> morecore (mdp, size);
46 adj = RESIDUAL (result, BLOCKSIZE);
49 adj = BLOCKSIZE - adj;
50 mdp -> morecore (mdp, adj);
51 result = (char *) result + adj;
56 /* Set everything up and remember that we have. */
62 mdp -> heapsize = HEAP / BLOCKSIZE;
63 mdp -> heapinfo = (malloc_info *)
64 align (mdp, mdp -> heapsize * sizeof (malloc_info));
65 if (mdp -> heapinfo == NULL)
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;
73 mdp -> heapbase = (char *) mdp -> heapinfo;
74 mdp -> flags |= MMALLOC_INITIALIZED;
78 /* Get neatly aligned memory, initializing or
79 growing the heap info table as necessary. */
87 malloc_info *newinfo, *oldinfo;
90 result = align (mdp, size);
96 /* Check if we need to grow the info table. */
97 if ((size_t) BLOCK ((char *) result + size) > mdp -> heapsize)
99 newsize = mdp -> heapsize;
100 while ((size_t) BLOCK ((char *) result + size) > newsize)
104 newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
107 mdp -> morecore (mdp, -size);
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;
122 mdp -> heaplimit = BLOCK ((char *) result + size);
126 /* Allocate memory from the heap. */
135 size_t block, blocks, lastblocks, start;
145 mdp = MD_TO_MDP (md);
147 if (mdp -> mmalloc_hook != NULL)
149 return ((*mdp -> mmalloc_hook) (md, size));
152 if (!(mdp -> flags & MMALLOC_INITIALIZED))
154 if (!initialize (mdp))
160 if (size < sizeof (struct list))
162 size = sizeof (struct list);
165 /* Determine the allocation policy based on the request size. */
166 if (size <= BLOCKSIZE / 2)
168 /* Small allocation to receive a fragment of a block.
169 Determine the logarithm to base two of the fragment size. */
172 while ((size /= 2) != 0)
177 /* Look in the fragment lists for a
178 free fragment of the desired size. */
179 next = mdp -> fraghead[log].next;
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. */
186 next -> prev -> next = next -> next;
187 if (next -> next != NULL)
189 next -> next -> prev = next -> prev;
191 block = BLOCK (result);
192 if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
194 mdp -> heapinfo[block].busy.info.frag.first =
195 RESIDUAL (next -> next, BLOCKSIZE) >> log;
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;
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);
214 /* Link all fragments but the first into the free list. */
215 for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
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)
223 next -> next -> prev = next;
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;
233 mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
234 mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
235 mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
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)
248 block = mdp -> heapinfo[block].free.next;
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)
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;
266 mdp -> heapinfo[block].free.size += (blocks - lastblocks);
267 mdp -> heapstats.bytes_free +=
268 (blocks - lastblocks) * BLOCKSIZE;
271 result = morecore(mdp, blocks * BLOCKSIZE);
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;
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)
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;
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--;
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;
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). */
335 result = mmalloc ((PTR) NULL, size);