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. */
25 static void* align (struct mdesc *mdp, size_t size) {
27 unsigned long int adj;
29 result = mdp -> morecore (mdp, size);
30 adj = RESIDUAL (result, BLOCKSIZE);
33 adj = BLOCKSIZE - adj;
34 mdp -> morecore (mdp, adj);
35 result = (char*) result + adj;
40 /* Set everything up and remember that we have. */
42 static int initialize (struct mdesc *mdp)
44 mdp -> heapsize = HEAP / BLOCKSIZE;
45 mdp -> heapinfo = (malloc_info *)
46 align (mdp, mdp -> heapsize * sizeof (malloc_info));
47 if (mdp -> heapinfo == NULL)
51 memset ((void*)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
52 mdp -> heapinfo[0].free.size = 0;
53 mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
55 mdp -> heapbase = (void*) mdp -> heapinfo;
56 mdp -> flags |= MMALLOC_INITIALIZED;
60 /* Get neatly aligned memory, initializing or
61 growing the heap info table as necessary. */
63 static void* morecore (struct mdesc *mdp, size_t size)
66 malloc_info *newinfo, *oldinfo;
69 result = align (mdp, size);
75 /* Check if we need to grow the info table. */
76 if ((size_t) BLOCK ((char*) result + size) > mdp -> heapsize)
78 newsize = mdp -> heapsize;
79 while ((size_t) BLOCK ((char*) result + size) > newsize)
83 newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
86 mdp -> morecore (mdp, -size);
89 memset ((void*) newinfo, 0, newsize * sizeof (malloc_info));
90 memcpy ((void*) newinfo, (void*) mdp -> heapinfo,
91 mdp -> heapsize * sizeof (malloc_info));
92 oldinfo = mdp -> heapinfo;
93 newinfo[BLOCK (oldinfo)].busy.type = 0;
94 newinfo[BLOCK (oldinfo)].busy.info.size
95 = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
96 mdp -> heapinfo = newinfo;
97 __mmalloc_free (mdp, (void*)oldinfo);
98 mdp -> heapsize = newsize;
101 mdp -> heaplimit = BLOCK ((char*) result + size);
105 /* Allocate memory from the heap. */
107 void* mmalloc (void *md, size_t size) {
110 size_t block, blocks, lastblocks, start;
118 mdp = MD_TO_MDP (md);
120 printf("(%s) Mallocing %d bytes on %p (default: %p)...",xbt_thread_self_name(),size,mdp,__mmalloc_default_mdp);fflush(stdout);
123 if (mdp -> mmalloc_hook != NULL) {
124 void * res = ((*mdp -> mmalloc_hook) (md, size));
129 if (!(mdp -> flags & MMALLOC_INITIALIZED)) {
130 if (!initialize (mdp)) {
136 if (size < sizeof (struct list)) {
137 size = sizeof (struct list);
140 /* Determine the allocation policy based on the request size. */
141 if (size <= BLOCKSIZE / 2)
143 /* Small allocation to receive a fragment of a block.
144 Determine the logarithm to base two of the fragment size. */
147 while ((size /= 2) != 0)
152 /* Look in the fragment lists for a
153 free fragment of the desired size. */
154 next = mdp -> fraghead[log].next;
157 /* There are free fragments of this size.
158 Pop a fragment out of the fragment list and return it.
159 Update the block's nfree and first counters. */
160 result = (void*) next;
161 next -> prev -> next = next -> next;
162 if (next -> next != NULL)
164 next -> next -> prev = next -> prev;
166 block = BLOCK (result);
167 if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
169 mdp -> heapinfo[block].busy.info.frag.first =
170 RESIDUAL (next -> next, BLOCKSIZE) >> log;
173 /* Update the statistics. */
174 mdp -> heapstats.chunks_used++;
175 mdp -> heapstats.bytes_used += 1 << log;
176 mdp -> heapstats.chunks_free--;
177 mdp -> heapstats.bytes_free -= 1 << log;
181 /* No free fragments of the desired size, so get a new block
182 and break it into fragments, returning the first. */
184 printf("(%s) No free fragment...",xbt_thread_self_name());
185 result = mmalloc (md, BLOCKSIZE);
186 printf("(%s) Fragment: %p...",xbt_thread_self_name(),result);
194 /* Link all fragments but the first into the free list. */
195 for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
197 next = (struct list *) ((char*) result + (i << log));
198 next -> next = mdp -> fraghead[log].next;
199 next -> prev = &mdp -> fraghead[log];
200 next -> prev -> next = next;
201 if (next -> next != NULL)
203 next -> next -> prev = next;
207 /* Initialize the nfree and first counters for this block. */
208 block = BLOCK (result);
209 mdp -> heapinfo[block].busy.type = log;
210 mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
211 mdp -> heapinfo[block].busy.info.frag.first = i - 1;
213 mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
214 mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
215 mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
220 /* Large allocation to receive one or more blocks.
221 Search the free list in a circle starting at the last place visited.
222 If we loop completely around without finding a large enough
223 space we will have to get more memory from the system. */
224 blocks = BLOCKIFY(size);
225 start = block = MALLOC_SEARCH_START;
226 while (mdp -> heapinfo[block].free.size < blocks)
228 block = mdp -> heapinfo[block].free.next;
231 /* Need to get more from the system. Check to see if
232 the new core will be contiguous with the final free
233 block; if so we don't need to get as much. */
234 block = mdp -> heapinfo[0].free.prev;
235 lastblocks = mdp -> heapinfo[block].free.size;
236 if (mdp -> heaplimit != 0 &&
237 block + lastblocks == mdp -> heaplimit &&
238 mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
239 (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
241 /* Which block we are extending (the `final free
242 block' referred to above) might have changed, if
243 it got combined with a freed info table. */
244 block = mdp -> heapinfo[0].free.prev;
246 mdp -> heapinfo[block].free.size += (blocks - lastblocks);
247 mdp -> heapstats.bytes_free +=
248 (blocks - lastblocks) * BLOCKSIZE;
251 result = morecore(mdp, blocks * BLOCKSIZE);
257 block = BLOCK (result);
258 mdp -> heapinfo[block].busy.type = 0;
259 mdp -> heapinfo[block].busy.info.size = blocks;
260 mdp -> heapstats.chunks_used++;
261 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
267 /* At this point we have found a suitable free list entry.
268 Figure out how to remove what we need from the list. */
269 result = ADDRESS(block);
270 if (mdp -> heapinfo[block].free.size > blocks)
272 /* The block we found has a bit left over,
273 so relink the tail end back into the free list. */
274 mdp -> heapinfo[block + blocks].free.size
275 = mdp -> heapinfo[block].free.size - blocks;
276 mdp -> heapinfo[block + blocks].free.next
277 = mdp -> heapinfo[block].free.next;
278 mdp -> heapinfo[block + blocks].free.prev
279 = mdp -> heapinfo[block].free.prev;
280 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
281 = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
282 = mdp -> heapindex = block + blocks;
286 /* The block exactly matches our requirements,
287 so just remove it from the list. */
288 mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
289 = mdp -> heapinfo[block].free.prev;
290 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
291 = mdp -> heapindex = mdp -> heapinfo[block].free.next;
292 mdp -> heapstats.chunks_free--;
295 mdp -> heapinfo[block].busy.type = 0;
296 mdp -> heapinfo[block].busy.info.size = blocks;
297 mdp -> heapstats.chunks_used++;
298 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
299 mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
301 printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout);