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:
10 * void *getMBlock(nat n);
12 * returns the address of an n*MBLOCK_SIZE region of memory, aligned on
13 * an MBLOCK_SIZE boundary. There are no other restrictions on the
14 * addresses of memory returned by getMBlock().
16 * ---------------------------------------------------------------------------*/
18 #include "PosixSource.h"
22 #include "BlockAlloc.h"
28 static void initMBlock(void *mblock);
30 // The free_list is kept sorted by size, smallest first.
31 // In THREADED_RTS mode, the free list is protected by sm_mutex.
33 /* -----------------------------------------------------------------------------
39 - bdescr = block descriptor
40 - bgroup = block group (1 or more adjacent blocks)
42 - mgroup = mega group (1 or more adjacent mblocks)
44 Invariants on block descriptors
45 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
46 bd->start always points to the start of the block.
49 - zero for a non-group-head; bd->link points to the head
50 - (-1) for the head of a free block group
51 - or it points within the block
54 - zero for a non-group-head; bd->link points to the head
55 - number of blocks in this group otherwise
57 bd->link either points to a block descriptor or is NULL
59 The following fields are not used by the allocator:
64 Exceptions: we don't maintain invariants for all the blocks within a
65 group on the free list, because it is expensive to modify every
66 bdescr in a group when coalescing. Just the head and last bdescrs
67 will be correct for a group on the free list.
73 - most allocations are for single blocks
74 - we cannot be dependent on address-space ordering; sometimes the
75 OS gives us new memory backwards in the address space, sometimes
77 - We want to avoid fragmentation in the free list
79 Coalescing trick: when a bgroup is freed (freeGroup()), we can check
80 whether it can be coalesced with othre free bgroups by checking the
81 bdescrs for the blocks on either side of it. This means that:
83 - freeGroup is O(1) if we coalesce with an existing free block
84 group. Otherwise we have to insert in the free list, but since
85 most blocks are small and the free list is sorted by size, this
87 - the free list must be double-linked, so we can insert into the
89 - every free group in the free list must have its head and tail
90 bdescrs initialised, the rest don't matter.
91 - we cannot play this trick with mblocks, because there is no
92 requirement that the bdescrs in the second and subsequent mblock
93 of an mgroup are initialised (the mgroup might be filled with a
94 large array, overwriting the bdescrs for example).
96 So there are two free lists:
98 - free_list contains bgroups smaller than an mblock.
100 - sorted in *size* order: allocation is best-fit
101 - free bgroups are always fully coalesced
102 - we do the coalescing trick in freeGroup()
104 - free_mblock_list contains mgroups only
105 - it is singly-linked (no need to double-link)
106 - sorted in *address* order, so we can coalesce using the list
107 - allocation is best-fit by traversing the whole list: we don't
108 expect this list to be long, avoiding fragmentation is more
111 freeGroup() might end up moving a block from free_list to
112 free_mblock_list, if after coalescing we end up with a full mblock.
114 checkFreeListSanity() checks all the invariants on the free lists.
116 --------------------------------------------------------------------------- */
118 static bdescr *free_list;
119 static bdescr *free_mblock_list;
122 /* -----------------------------------------------------------------------------
124 -------------------------------------------------------------------------- */
126 void initBlockAllocator(void)
129 free_mblock_list = NULL;
132 /* -----------------------------------------------------------------------------
134 -------------------------------------------------------------------------- */
137 initGroup(nat n, bdescr *head)
143 head->free = head->start;
145 for (i=1, bd = head+1; i < n; i++, bd++) {
153 // when a block has been shortened by allocGroup(), we need to push
154 // the remaining chunk backwards in the free list in order to keep the
155 // list sorted by size.
157 free_list_push_backwards (bdescr *bd)
162 while (p != NULL && p->blocks > bd->blocks) {
165 if (p != bd->u.back) {
166 dbl_link_remove(bd, &free_list);
168 dbl_link_insert_after(bd, p);
170 dbl_link_onto(bd, &free_list);
174 // when a block has been coalesced by freeGroup(), we need to push the
175 // remaining chunk forwards in the free list in order to keep the list
178 free_list_push_forwards (bdescr *bd)
183 while (p->link != NULL && p->link->blocks < bd->blocks) {
187 dbl_link_remove(bd, &free_list);
188 dbl_link_insert_after(bd, p);
193 free_list_insert (bdescr *bd)
198 dbl_link_onto(bd, &free_list);
204 while (p != NULL && p->blocks < bd->blocks) {
210 dbl_link_onto(bd, &free_list);
214 dbl_link_insert_after(bd, prev);
219 STATIC_INLINE bdescr *
222 return bd + bd->blocks - 1;
225 // After splitting a group, the last block of each group must have a
226 // tail that points to the head block, to keep our invariants for
229 setup_tail (bdescr *bd)
241 // Take a free block group bd, and split off a group of size n from
242 // it. Adjust the free list as necessary, and return the new group.
244 split_free_block (bdescr *bd, nat n)
246 bdescr *fg; // free group
248 ASSERT(bd->blocks > n);
249 fg = bd + bd->blocks - n; // take n blocks off the end
253 free_list_push_backwards(bd);
258 alloc_mega_group (nat mblocks)
260 bdescr *best, *bd, *prev;
263 n = MBLOCK_GROUP_BLOCKS(mblocks);
267 for (bd = free_mblock_list; bd != NULL; prev = bd, bd = bd->link)
272 prev->link = bd->link;
274 free_mblock_list = bd->link;
279 else if (bd->blocks > n)
281 if (!best || bd->blocks < best->blocks)
290 // we take our chunk off the end here.
291 nat best_mblocks = BLOCKS_TO_MBLOCKS(best->blocks);
292 bd = FIRST_BDESCR(MBLOCK_ROUND_DOWN(best) +
293 (best_mblocks-mblocks)*MBLOCK_SIZE);
295 best->blocks = MBLOCK_GROUP_BLOCKS(best_mblocks - mblocks);
296 initMBlock(MBLOCK_ROUND_DOWN(bd));
300 void *mblock = getMBlocks(mblocks);
301 initMBlock(mblock); // only need to init the 1st one
302 bd = FIRST_BDESCR(mblock);
304 bd->blocks = MBLOCK_GROUP_BLOCKS(mblocks);
313 // Todo: not true in multithreaded GC, where we use allocBlock_sync().
316 if (n == 0) barf("allocGroup: requested zero blocks");
318 if (n >= BLOCKS_PER_MBLOCK)
320 bd = alloc_mega_group(BLOCKS_TO_MBLOCKS(n));
321 // only the bdescrs of the first MB are required to be initialised
322 initGroup(BLOCKS_PER_MBLOCK, bd);
323 IF_DEBUG(sanity, checkFreeListSanity());
327 // The free list is sorted by size, so we get best fit.
328 for (bd = free_list; bd != NULL; bd = bd->link)
330 if (bd->blocks == n) // exactly the right size!
332 dbl_link_remove(bd, &free_list);
333 initGroup(n, bd); // initialise it
334 IF_DEBUG(sanity, checkFreeListSanity());
337 if (bd->blocks > n) // block too big...
339 bd = split_free_block(bd, n);
340 initGroup(n, bd); // initialise the new chunk
341 IF_DEBUG(sanity, checkFreeListSanity());
346 bd = alloc_mega_group(1);
348 initGroup(n,bd); // we know the group will fit
350 rem->blocks = BLOCKS_PER_MBLOCK-n;
351 initGroup(BLOCKS_PER_MBLOCK-n, rem); // init the slop
352 freeGroup(rem); // add the slop on to the free list
353 IF_DEBUG(sanity, checkFreeListSanity());
358 allocGroup_lock(nat n)
370 return allocGroup(1);
374 allocBlock_lock(void)
383 /* -----------------------------------------------------------------------------
385 -------------------------------------------------------------------------- */
387 STATIC_INLINE bdescr *
388 coalesce_mblocks (bdescr *p)
394 MBLOCK_ROUND_DOWN(q) ==
395 MBLOCK_ROUND_DOWN(p) + BLOCKS_TO_MBLOCKS(p->blocks) * MBLOCK_SIZE) {
397 p->blocks = MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(p->blocks) +
398 BLOCKS_TO_MBLOCKS(q->blocks));
406 free_mega_group (bdescr *mg)
410 // Find the right place in the free list. free_mblock_list is
411 // sorted by *address*, not by size as the free_list is.
413 bd = free_mblock_list;
414 while (bd && bd->start < mg->start) {
419 // coalesce backwards
422 mg->link = prev->link;
424 mg = coalesce_mblocks(prev);
428 mg->link = free_mblock_list;
429 free_mblock_list = mg;
432 coalesce_mblocks(mg);
434 IF_DEBUG(sanity, checkFreeListSanity());
441 nat p_on_free_list = 0;
443 // Todo: not true in multithreaded GC
446 ASSERT(p->free != (P_)-1);
448 p->free = (void *)-1; /* indicates that this block is free */
451 /* fill the block group with garbage if sanity checking is on */
452 IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
454 if (p->blocks == 0) barf("freeGroup: block size is zero");
456 if (p->blocks >= BLOCKS_PER_MBLOCK)
458 // If this is an mgroup, make sure it has the right number of blocks
459 ASSERT(p->blocks == MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(p->blocks)));
467 next = p + p->blocks;
468 if (next <= LAST_BDESCR(MBLOCK_ROUND_DOWN(p)) && next->free == (P_)-1)
470 p->blocks += next->blocks;
471 if (p->blocks == BLOCKS_PER_MBLOCK)
473 dbl_link_remove(next, &free_list);
477 dbl_link_replace(p, next, &free_list);
479 free_list_push_forwards(p);
484 // coalesce backwards
485 if (p != FIRST_BDESCR(MBLOCK_ROUND_DOWN(p)))
489 if (prev->blocks == 0) prev = prev->link; // find the head
491 if (prev->free == (P_)-1)
493 prev->blocks += p->blocks;
494 if (prev->blocks >= BLOCKS_PER_MBLOCK)
498 dbl_link_remove(p, &free_list);
500 dbl_link_remove(prev, &free_list);
501 free_mega_group(prev);
504 else if (p_on_free_list)
506 // p was already coalesced forwards
507 dbl_link_remove(p, &free_list);
510 free_list_push_forwards(prev);
522 IF_DEBUG(sanity, checkFreeListSanity());
526 freeGroup_lock(bdescr *p)
534 freeChain(bdescr *bd)
545 freeChain_lock(bdescr *bd)
553 initMBlock(void *mblock)
558 /* the first few Bdescr's in a block are unused, so we don't want to
559 * put them all on the free list.
561 block = FIRST_BLOCK(mblock);
562 bd = FIRST_BDESCR(mblock);
564 /* Initialise the start field of each block descriptor
566 for (; block <= LAST_BLOCK(mblock); bd += 1, block += BLOCK_SIZE) {
571 /* -----------------------------------------------------------------------------
573 -------------------------------------------------------------------------- */
577 check_tail (bdescr *bd)
579 bdescr *tail = tail_of(bd);
583 ASSERT(tail->blocks == 0);
584 ASSERT(tail->free == 0);
585 ASSERT(tail->link == bd);
590 checkFreeListSanity(void)
594 IF_DEBUG(block_alloc, debugBelch("free block list:\n"));
597 for (bd = free_list; bd != NULL; prev = bd, bd = bd->link)
599 IF_DEBUG(block_alloc,
600 debugBelch("group at %p, length %ld blocks\n",
601 bd->start, (long)bd->blocks));
602 ASSERT(bd->blocks > 0 && bd->blocks < BLOCKS_PER_MBLOCK);
603 ASSERT(bd->link != bd); // catch easy loops
608 ASSERT(bd->u.back == prev);
610 ASSERT(bd->u.back == NULL);
612 if (bd->link != NULL)
614 // make sure the list is sorted
615 ASSERT(bd->blocks <= bd->link->blocks);
620 next = bd + bd->blocks;
621 if (next <= LAST_BDESCR(MBLOCK_ROUND_DOWN(bd)))
623 ASSERT(next->free != (P_)-1);
629 for (bd = free_mblock_list; bd != NULL; prev = bd, bd = bd->link)
631 IF_DEBUG(block_alloc,
632 debugBelch("mega group at %p, length %ld blocks\n",
633 bd->start, (long)bd->blocks));
635 ASSERT(bd->link != bd); // catch easy loops
637 if (bd->link != NULL)
639 // make sure the list is sorted
640 ASSERT(bd->start < bd->link->start);
643 ASSERT(bd->blocks >= BLOCKS_PER_MBLOCK);
644 ASSERT(MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(bd->blocks))
647 // make sure we're fully coalesced
648 if (bd->link != NULL)
650 ASSERT (MBLOCK_ROUND_DOWN(bd->link) !=
651 MBLOCK_ROUND_DOWN(bd) +
652 BLOCKS_TO_MBLOCKS(bd->blocks) * MBLOCK_SIZE);
661 lnat total_blocks = 0;
663 for (bd = free_list; bd != NULL; bd = bd->link) {
664 total_blocks += bd->blocks;
666 for (bd = free_mblock_list; bd != NULL; bd = bd->link) {
667 total_blocks += BLOCKS_PER_MBLOCK * BLOCKS_TO_MBLOCKS(bd->blocks);
668 // The caller of this function, memInventory(), expects to match
669 // the total number of blocks in the system against mblocks *
670 // BLOCKS_PER_MBLOCK, so we must subtract the space for the
671 // block descriptors from *every* mblock.