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 /* Copyright (c) 2010. The SimGrid Team.
8 * All rights reserved. */
10 /* This program is free software; you can redistribute it and/or modify it
11 * under the terms of the license (GNU LGPL) which comes with this package. */
13 #include <string.h> /* Prototypes for memcpy, memmove, memset, etc */
15 #include "mmprivate.h"
17 /* Prototypes for local functions */
19 static int initialize (struct mdesc *mdp);
20 static void* morecore (struct mdesc *mdp, size_t size);
21 static void* align (struct mdesc *mdp, size_t size);
23 /* Aligned allocation. */
26 align (struct mdesc *mdp, size_t size)
29 unsigned long int adj;
31 result = mdp -> morecore (mdp, size);
32 adj = RESIDUAL (result, BLOCKSIZE);
35 adj = BLOCKSIZE - adj;
36 mdp -> morecore (mdp, adj);
37 result = (char*) result + adj;
42 /* Set everything up and remember that we have. */
45 initialize (struct mdesc *mdp)
47 mdp -> heapsize = HEAP / BLOCKSIZE;
48 mdp -> heapinfo = (malloc_info *)
49 align (mdp, mdp -> heapsize * sizeof (malloc_info));
50 if (mdp -> heapinfo == NULL)
54 memset ((void*)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
55 mdp -> heapinfo[0].free.size = 0;
56 mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
58 mdp -> heapbase = (void*) mdp -> heapinfo;
59 mdp -> flags |= MMALLOC_INITIALIZED;
63 /* Get neatly aligned memory, initializing or
64 growing the heap info table as necessary. */
67 morecore (struct mdesc *mdp, size_t size)
70 malloc_info *newinfo, *oldinfo;
73 result = align (mdp, size);
79 /* Check if we need to grow the info table. */
80 if ((size_t) BLOCK ((char*) result + size) > mdp -> heapsize)
82 newsize = mdp -> heapsize;
83 while ((size_t) BLOCK ((char*) result + size) > newsize)
87 newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
90 mdp -> morecore (mdp, -size);
93 memset ((void*) newinfo, 0, newsize * sizeof (malloc_info));
94 memcpy ((void*) newinfo, (void*) mdp -> heapinfo,
95 mdp -> heapsize * sizeof (malloc_info));
96 oldinfo = mdp -> heapinfo;
97 newinfo[BLOCK (oldinfo)].busy.type = 0;
98 newinfo[BLOCK (oldinfo)].busy.info.size
99 = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
100 mdp -> heapinfo = newinfo;
101 __mmalloc_free (mdp, (void*)oldinfo);
102 mdp -> heapsize = newsize;
105 mdp -> heaplimit = BLOCK ((char*) result + size);
109 /* Allocate memory from the heap. */
118 size_t block, blocks, lastblocks, start;
128 mdp = MD_TO_MDP (md);
130 if (mdp -> mmalloc_hook != NULL)
132 return ((*mdp -> mmalloc_hook) (md, size));
135 if (!(mdp -> flags & MMALLOC_INITIALIZED))
137 if (!initialize (mdp))
143 if (size < sizeof (struct list))
145 size = sizeof (struct list);
148 /* Determine the allocation policy based on the request size. */
149 if (size <= BLOCKSIZE / 2)
151 /* Small allocation to receive a fragment of a block.
152 Determine the logarithm to base two of the fragment size. */
155 while ((size /= 2) != 0)
160 /* Look in the fragment lists for a
161 free fragment of the desired size. */
162 next = mdp -> fraghead[log].next;
165 /* There are free fragments of this size.
166 Pop a fragment out of the fragment list and return it.
167 Update the block's nfree and first counters. */
168 result = (void*) next;
169 next -> prev -> next = next -> next;
170 if (next -> next != NULL)
172 next -> next -> prev = next -> prev;
174 block = BLOCK (result);
175 if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
177 mdp -> heapinfo[block].busy.info.frag.first =
178 RESIDUAL (next -> next, BLOCKSIZE) >> log;
181 /* Update the statistics. */
182 mdp -> heapstats.chunks_used++;
183 mdp -> heapstats.bytes_used += 1 << log;
184 mdp -> heapstats.chunks_free--;
185 mdp -> heapstats.bytes_free -= 1 << log;
189 /* No free fragments of the desired size, so get a new block
190 and break it into fragments, returning the first. */
191 result = mmalloc (md, BLOCKSIZE);
197 /* Link all fragments but the first into the free list. */
198 for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
200 next = (struct list *) ((char*) result + (i << log));
201 next -> next = mdp -> fraghead[log].next;
202 next -> prev = &mdp -> fraghead[log];
203 next -> prev -> next = next;
204 if (next -> next != NULL)
206 next -> next -> prev = next;
210 /* Initialize the nfree and first counters for this block. */
211 block = BLOCK (result);
212 mdp -> heapinfo[block].busy.type = log;
213 mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
214 mdp -> heapinfo[block].busy.info.frag.first = i - 1;
216 mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
217 mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
218 mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
223 /* Large allocation to receive one or more blocks.
224 Search the free list in a circle starting at the last place visited.
225 If we loop completely around without finding a large enough
226 space we will have to get more memory from the system. */
227 blocks = BLOCKIFY(size);
228 start = block = MALLOC_SEARCH_START;
229 while (mdp -> heapinfo[block].free.size < blocks)
231 block = mdp -> heapinfo[block].free.next;
234 /* Need to get more from the system. Check to see if
235 the new core will be contiguous with the final free
236 block; if so we don't need to get as much. */
237 block = mdp -> heapinfo[0].free.prev;
238 lastblocks = mdp -> heapinfo[block].free.size;
239 if (mdp -> heaplimit != 0 &&
240 block + lastblocks == mdp -> heaplimit &&
241 mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
242 (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
244 /* Which block we are extending (the `final free
245 block' referred to above) might have changed, if
246 it got combined with a freed info table. */
247 block = mdp -> heapinfo[0].free.prev;
249 mdp -> heapinfo[block].free.size += (blocks - lastblocks);
250 mdp -> heapstats.bytes_free +=
251 (blocks - lastblocks) * BLOCKSIZE;
254 result = morecore(mdp, blocks * BLOCKSIZE);
259 block = BLOCK (result);
260 mdp -> heapinfo[block].busy.type = 0;
261 mdp -> heapinfo[block].busy.info.size = blocks;
262 mdp -> heapstats.chunks_used++;
263 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
268 /* At this point we have found a suitable free list entry.
269 Figure out how to remove what we need from the list. */
270 result = ADDRESS(block);
271 if (mdp -> heapinfo[block].free.size > blocks)
273 /* The block we found has a bit left over,
274 so relink the tail end back into the free list. */
275 mdp -> heapinfo[block + blocks].free.size
276 = mdp -> heapinfo[block].free.size - blocks;
277 mdp -> heapinfo[block + blocks].free.next
278 = mdp -> heapinfo[block].free.next;
279 mdp -> heapinfo[block + blocks].free.prev
280 = mdp -> heapinfo[block].free.prev;
281 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
282 = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
283 = mdp -> heapindex = block + blocks;
287 /* The block exactly matches our requirements,
288 so just remove it from the list. */
289 mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
290 = mdp -> heapinfo[block].free.prev;
291 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
292 = mdp -> heapindex = mdp -> heapinfo[block].free.next;
293 mdp -> heapstats.chunks_free--;
296 mdp -> heapinfo[block].busy.type = 0;
297 mdp -> heapinfo[block].busy.info.size = blocks;
298 mdp -> heapstats.chunks_used++;
299 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
300 mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
306 /* When using this package, provide a version of malloc/realloc/free built
307 on top of it, so that if we use the default sbrk() region we will not
308 collide with another malloc package trying to do the same thing, if
309 the application contains any "hidden" calls to malloc/realloc/free (such
310 as inside a system library). */
316 result = mmalloc (NULL, size);