1 /* -----------------------------------------------------------------------------
3 * (c) The GHC Team 1998-2006
5 * The block allocator and free list manager.
7 * This is the architecture independent part of the block allocator.
8 * It requires only the following support from the operating system:
12 * returns the address of an MBLOCK_SIZE region of memory, aligned on
13 * an MBLOCK_SIZE boundary. There is no requirement for successive
14 * calls to getMBlock to return strictly increasing addresses.
16 * ---------------------------------------------------------------------------*/
18 #include "PosixSource.h"
22 #include "BlockAlloc.h"
28 static void initMBlock(void *mblock);
29 static bdescr *allocMegaGroup(nat mblocks);
30 static void freeMegaGroup(bdescr *bd);
32 // In THREADED_RTS mode, the free list is protected by sm_mutex.
33 static bdescr *free_list = NULL;
35 /* -----------------------------------------------------------------------------
37 -------------------------------------------------------------------------- */
39 void initBlockAllocator(void)
41 // The free list starts off NULL
44 /* -----------------------------------------------------------------------------
46 -------------------------------------------------------------------------- */
49 initGroup(nat n, bdescr *head)
56 head->free = head->start;
58 for (i=1, bd = head+1; i < n; i++, bd++) {
75 if (n > BLOCKS_PER_MBLOCK) {
76 return allocMegaGroup(BLOCKS_TO_MBLOCKS(n));
80 for (bd = free_list; bd != NULL; bd = bd->link) {
81 if (bd->blocks == n) { /* exactly the right size! */
83 initGroup(n, bd); /* initialise it */
86 if (bd->blocks > n) { /* block too big... */
87 bd->blocks -= n; /* take a chunk off the *end* */
89 initGroup(n, bd); /* initialise it */
95 mblock = getMBlock(); /* get a new megablock */
96 initMBlock(mblock); /* initialise the start fields */
97 bd = FIRST_BDESCR(mblock);
98 initGroup(n,bd); /* we know the group will fit */
99 if (n < BLOCKS_PER_MBLOCK) {
100 initGroup(BLOCKS_PER_MBLOCK-n, bd+n);
101 freeGroup(bd+n); /* add the rest on to the free list */
107 allocGroup_lock(nat n)
119 return allocGroup(1);
123 allocBlock_lock(void)
132 /* -----------------------------------------------------------------------------
133 Any request larger than BLOCKS_PER_MBLOCK needs a megablock group.
134 First, search the free list for enough contiguous megablocks to
135 fulfill the request - if we don't have enough, we need to
136 allocate some new ones.
138 A megablock group looks just like a normal block group, except that
139 the blocks field in the head will be larger than BLOCKS_PER_MBLOCK.
141 Note that any objects placed in this group must start in the first
142 megablock, since the other blocks don't have block descriptors.
143 -------------------------------------------------------------------------- */
146 allocMegaGroup(nat n)
149 bdescr *bd, *last, *grp_start, *grp_prev;
155 for (bd = free_list; bd != NULL; bd = bd->link) {
157 if (bd->blocks == BLOCKS_PER_MBLOCK) { /* whole megablock found */
159 /* is it the first one we've found or a non-contiguous megablock? */
160 if (grp_start == NULL ||
161 bd->start != last->start + MBLOCK_SIZE/sizeof(W_)) {
169 if (mbs_found == n) { /* found enough contig megablocks? */
174 else { /* only a partial megablock, start again */
181 /* found all the megablocks we need on the free list
183 if (mbs_found == n) {
184 /* remove the megablocks from the free list */
185 if (grp_prev == NULL) { /* bd now points to the last mblock */
186 free_list = bd->link;
188 grp_prev->link = bd->link;
192 /* the free list wasn't sufficient, allocate all new mblocks.
195 void *mblock = getMBlocks(n);
196 initMBlock(mblock); /* only need to init the 1st one */
197 grp_start = FIRST_BDESCR(mblock);
200 /* set up the megablock group */
201 initGroup(BLOCKS_PER_MBLOCK, grp_start);
202 grp_start->blocks = MBLOCK_GROUP_BLOCKS(n);
206 /* -----------------------------------------------------------------------------
208 -------------------------------------------------------------------------- */
210 /* coalesce the group p with p->link if possible.
212 * Returns p->link if no coalescing was done, otherwise returns a
213 * pointer to the newly enlarged group p.
216 STATIC_INLINE bdescr *
222 if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
224 p->blocks += q->blocks;
231 // not strictly necessary to do this, but helpful if we have a
232 // random ptr and want to figure out what block it belongs to.
233 // Also required for sanity checking (see checkFreeListSanity()).
234 for (i = 0, bd = q; i < blocks; bd++, i++) {
253 /* are we dealing with a megablock group? */
254 if (p->blocks > BLOCKS_PER_MBLOCK) {
260 p->free = (void *)-1; /* indicates that this block is free */
263 /* fill the block group with garbage if sanity checking is on */
264 IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
266 /* find correct place in free list to place new group */
268 for (bd = free_list; bd != NULL && bd->start < p->start;
273 /* now, last = previous group (or NULL) */
278 /* coalesce with previous group if possible */
279 p->link = last->link;
284 /* coalesce with next group if possible */
286 IF_DEBUG(sanity, checkFreeListSanity());
290 freeGroup_lock(bdescr *p)
298 freeMegaGroup(bdescr *p)
303 n = ((bdescr *)q)->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
304 for (; n > 0; q += MBLOCK_SIZE, n--) {
305 initMBlock(MBLOCK_ROUND_DOWN(q));
306 initGroup(BLOCKS_PER_MBLOCK, (bdescr *)q);
307 freeGroup((bdescr *)q);
312 freeChain(bdescr *bd)
323 freeChain_lock(bdescr *bd)
331 initMBlock(void *mblock)
336 /* the first few Bdescr's in a block are unused, so we don't want to
337 * put them all on the free list.
339 block = FIRST_BLOCK(mblock);
340 bd = FIRST_BDESCR(mblock);
342 /* Initialise the start field of each block descriptor
344 for (; block <= LAST_BLOCK(mblock); bd += 1, block += BLOCK_SIZE) {
349 /* -----------------------------------------------------------------------------
351 -------------------------------------------------------------------------- */
355 checkWellFormedGroup( bdescr *bd )
359 for (i = 1; i < bd->blocks; i++) {
360 ASSERT(bd[i].blocks == 0);
361 ASSERT(bd[i].free == 0);
362 ASSERT(bd[i].link == bd);
367 checkFreeListSanity(void)
371 for (bd = free_list; bd != NULL; bd = bd->link) {
372 IF_DEBUG(block_alloc,
373 debugBelch("group at 0x%p, length %ld blocks\n",
374 bd->start, (long)bd->blocks));
375 ASSERT(bd->blocks > 0);
376 checkWellFormedGroup(bd);
377 if (bd->link != NULL) {
378 /* make sure we're fully coalesced */
379 ASSERT(bd->start + bd->blocks * BLOCK_SIZE_W != bd->link->start);
380 ASSERT(bd->start < bd->link->start);
389 lnat total_blocks = 0;
391 for (bd = free_list; bd != NULL; bd = bd->link) {
392 total_blocks += bd->blocks;