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);
315 if (n == 0) barf("allocGroup: requested zero blocks");
317 if (n >= BLOCKS_PER_MBLOCK)
319 bd = alloc_mega_group(BLOCKS_TO_MBLOCKS(n));
320 // only the bdescrs of the first MB are required to be initialised
321 initGroup(BLOCKS_PER_MBLOCK, bd);
322 IF_DEBUG(sanity, checkFreeListSanity());
326 // The free list is sorted by size, so we get best fit.
327 for (bd = free_list; bd != NULL; bd = bd->link)
329 if (bd->blocks == n) // exactly the right size!
331 dbl_link_remove(bd, &free_list);
332 initGroup(n, bd); // initialise it
333 IF_DEBUG(sanity, checkFreeListSanity());
336 if (bd->blocks > n) // block too big...
338 bd = split_free_block(bd, n);
339 initGroup(n, bd); // initialise the new chunk
340 IF_DEBUG(sanity, checkFreeListSanity());
345 bd = alloc_mega_group(1);
347 initGroup(n,bd); // we know the group will fit
349 rem->blocks = BLOCKS_PER_MBLOCK-n;
350 initGroup(BLOCKS_PER_MBLOCK-n, rem); // init the slop
351 freeGroup(rem); // add the slop on to the free list
352 IF_DEBUG(sanity, checkFreeListSanity());
357 allocGroup_lock(nat n)
369 return allocGroup(1);
373 allocBlock_lock(void)
382 /* -----------------------------------------------------------------------------
384 -------------------------------------------------------------------------- */
386 STATIC_INLINE bdescr *
387 coalesce_mblocks (bdescr *p)
393 MBLOCK_ROUND_DOWN(q) ==
394 MBLOCK_ROUND_DOWN(p) + BLOCKS_TO_MBLOCKS(p->blocks) * MBLOCK_SIZE) {
396 p->blocks = MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(p->blocks) +
397 BLOCKS_TO_MBLOCKS(q->blocks));
405 free_mega_group (bdescr *mg)
409 // Find the right place in the free list. free_mblock_list is
410 // sorted by *address*, not by size as the free_list is.
412 bd = free_mblock_list;
413 while (bd && bd->start < mg->start) {
418 // coalesce backwards
421 mg->link = prev->link;
423 mg = coalesce_mblocks(prev);
427 mg->link = free_mblock_list;
428 free_mblock_list = mg;
431 coalesce_mblocks(mg);
433 IF_DEBUG(sanity, checkFreeListSanity());
440 nat p_on_free_list = 0;
444 ASSERT(p->free != (P_)-1);
446 p->free = (void *)-1; /* indicates that this block is free */
449 /* fill the block group with garbage if sanity checking is on */
450 IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
452 if (p->blocks == 0) barf("freeGroup: block size is zero");
454 if (p->blocks >= BLOCKS_PER_MBLOCK)
456 // If this is an mgroup, make sure it has the right number of blocks
457 ASSERT(p->blocks == MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(p->blocks)));
465 next = p + p->blocks;
466 if (next <= LAST_BDESCR(MBLOCK_ROUND_DOWN(p)) && next->free == (P_)-1)
468 p->blocks += next->blocks;
469 if (p->blocks == BLOCKS_PER_MBLOCK)
471 dbl_link_remove(next, &free_list);
475 dbl_link_replace(p, next, &free_list);
477 free_list_push_forwards(p);
482 // coalesce backwards
483 if (p != FIRST_BDESCR(MBLOCK_ROUND_DOWN(p)))
487 if (prev->blocks == 0) prev = prev->link; // find the head
489 if (prev->free == (P_)-1)
491 prev->blocks += p->blocks;
492 if (prev->blocks >= BLOCKS_PER_MBLOCK)
496 dbl_link_remove(p, &free_list);
498 dbl_link_remove(prev, &free_list);
499 free_mega_group(prev);
502 else if (p_on_free_list)
504 // p was already coalesced forwards
505 dbl_link_remove(p, &free_list);
508 free_list_push_forwards(prev);
520 IF_DEBUG(sanity, checkFreeListSanity());
524 freeGroup_lock(bdescr *p)
532 freeChain(bdescr *bd)
543 freeChain_lock(bdescr *bd)
551 initMBlock(void *mblock)
556 /* the first few Bdescr's in a block are unused, so we don't want to
557 * put them all on the free list.
559 block = FIRST_BLOCK(mblock);
560 bd = FIRST_BDESCR(mblock);
562 /* Initialise the start field of each block descriptor
564 for (; block <= LAST_BLOCK(mblock); bd += 1, block += BLOCK_SIZE) {
569 /* -----------------------------------------------------------------------------
571 -------------------------------------------------------------------------- */
575 check_tail (bdescr *bd)
577 bdescr *tail = tail_of(bd);
581 ASSERT(tail->blocks == 0);
582 ASSERT(tail->free == 0);
583 ASSERT(tail->link == bd);
588 checkFreeListSanity(void)
592 IF_DEBUG(block_alloc, debugBelch("free block list:\n"));
595 for (bd = free_list; bd != NULL; prev = bd, bd = bd->link)
597 IF_DEBUG(block_alloc,
598 debugBelch("group at %p, length %ld blocks\n",
599 bd->start, (long)bd->blocks));
600 ASSERT(bd->blocks > 0 && bd->blocks < BLOCKS_PER_MBLOCK);
601 ASSERT(bd->link != bd); // catch easy loops
606 ASSERT(bd->u.back == prev);
608 ASSERT(bd->u.back == NULL);
610 if (bd->link != NULL)
612 // make sure the list is sorted
613 ASSERT(bd->blocks <= bd->link->blocks);
618 next = bd + bd->blocks;
619 if (next <= LAST_BDESCR(MBLOCK_ROUND_DOWN(bd)))
621 ASSERT(next->free != (P_)-1);
627 for (bd = free_mblock_list; bd != NULL; prev = bd, bd = bd->link)
629 IF_DEBUG(block_alloc,
630 debugBelch("mega group at %p, length %ld blocks\n",
631 bd->start, (long)bd->blocks));
633 ASSERT(bd->link != bd); // catch easy loops
635 if (bd->link != NULL)
637 // make sure the list is sorted
638 ASSERT(bd->start < bd->link->start);
641 ASSERT(bd->blocks >= BLOCKS_PER_MBLOCK);
642 ASSERT(MBLOCK_GROUP_BLOCKS(BLOCKS_TO_MBLOCKS(bd->blocks))
645 // make sure we're fully coalesced
646 if (bd->link != NULL)
648 ASSERT (MBLOCK_ROUND_DOWN(bd->link) !=
649 MBLOCK_ROUND_DOWN(bd) +
650 BLOCKS_TO_MBLOCKS(bd->blocks) * MBLOCK_SIZE);
659 lnat total_blocks = 0;
661 for (bd = free_list; bd != NULL; bd = bd->link) {
662 total_blocks += bd->blocks;
664 for (bd = free_mblock_list; bd != NULL; bd = bd->link) {
665 total_blocks += BLOCKS_PER_MBLOCK * BLOCKS_TO_MBLOCKS(bd->blocks);
666 // The caller of this function, memInventory(), expects to match
667 // the total number of blocks in the system against mblocks *
668 // BLOCKS_PER_MBLOCK, so we must subtract the space for the
669 // block descriptors from *every* mblock.