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;
115 /* Work even if the user was stupid enough to ask a 0-byte block, ie return a valid block that can be realloced or freed
116 * glibc malloc does not use this trick but return a constant pointer, but my hack is quicker to implement ;)
121 mdp = MD_TO_MDP (md);
123 // printf("(%s) Mallocing %d bytes on %p (default: %p)...",xbt_thread_self_name(),size,mdp,__mmalloc_default_mdp);fflush(stdout);
126 if (mdp -> mmalloc_hook != NULL) {
127 void * res = ((*mdp -> mmalloc_hook) (md, size));
132 if (!(mdp -> flags & MMALLOC_INITIALIZED)) {
133 if (!initialize (mdp)) {
139 if (size < sizeof (struct list)) {
140 size = sizeof (struct list);
143 /* Determine the allocation policy based on the request size. */
144 if (size <= BLOCKSIZE / 2)
146 /* Small allocation to receive a fragment of a block.
147 Determine the logarithm to base two of the fragment size. */
150 while ((size /= 2) != 0)
155 /* Look in the fragment lists for a
156 free fragment of the desired size. */
157 next = mdp -> fraghead[log].next;
160 /* There are free fragments of this size.
161 Pop a fragment out of the fragment list and return it.
162 Update the block's nfree and first counters. */
163 result = (void*) next;
164 next -> prev -> next = next -> next;
165 if (next -> next != NULL)
167 next -> next -> prev = next -> prev;
169 block = BLOCK (result);
170 if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
172 mdp -> heapinfo[block].busy.info.frag.first =
173 RESIDUAL (next -> next, BLOCKSIZE) >> log;
176 /* Update the statistics. */
177 mdp -> heapstats.chunks_used++;
178 mdp -> heapstats.bytes_used += 1 << log;
179 mdp -> heapstats.chunks_free--;
180 mdp -> heapstats.bytes_free -= 1 << log;
184 /* No free fragments of the desired size, so get a new block
185 and break it into fragments, returning the first. */
187 //printf("(%s) No free fragment...",xbt_thread_self_name());
188 result = mmalloc (md, BLOCKSIZE);
189 //printf("(%s) Fragment: %p...",xbt_thread_self_name(),result);
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);
260 block = BLOCK (result);
261 mdp -> heapinfo[block].busy.type = 0;
262 mdp -> heapinfo[block].busy.info.size = blocks;
263 mdp -> heapstats.chunks_used++;
264 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
270 /* At this point we have found a suitable free list entry.
271 Figure out how to remove what we need from the list. */
272 result = ADDRESS(block);
273 if (mdp -> heapinfo[block].free.size > blocks)
275 /* The block we found has a bit left over,
276 so relink the tail end back into the free list. */
277 mdp -> heapinfo[block + blocks].free.size
278 = mdp -> heapinfo[block].free.size - blocks;
279 mdp -> heapinfo[block + blocks].free.next
280 = mdp -> heapinfo[block].free.next;
281 mdp -> heapinfo[block + blocks].free.prev
282 = mdp -> heapinfo[block].free.prev;
283 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
284 = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
285 = mdp -> heapindex = block + blocks;
289 /* The block exactly matches our requirements,
290 so just remove it from the list. */
291 mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
292 = mdp -> heapinfo[block].free.prev;
293 mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
294 = mdp -> heapindex = mdp -> heapinfo[block].free.next;
295 mdp -> heapstats.chunks_free--;
298 mdp -> heapinfo[block].busy.type = 0;
299 mdp -> heapinfo[block].busy.info.size = blocks;
300 mdp -> heapstats.chunks_used++;
301 mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
302 mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
304 //printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout);