+
+/* -----------------------------------------------------------------------------
+
+ Implementation notes
+ ~~~~~~~~~~~~~~~~~~~~
+
+ Terminology:
+ - bdescr = block descriptor
+ - bgroup = block group (1 or more adjacent blocks)
+ - mblock = mega block
+ - mgroup = mega group (1 or more adjacent mblocks)
+
+ Invariants on block descriptors
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ bd->start always points to the start of the block.
+
+ bd->free is either:
+ - zero for a non-group-head; bd->link points to the head
+ - (-1) for the head of a free block group
+ - or it points within the block
+
+ bd->blocks is either:
+ - zero for a non-group-head; bd->link points to the head
+ - number of blocks in this group otherwise
+
+ bd->link either points to a block descriptor or is NULL
+
+ The following fields are not used by the allocator:
+ bd->flags
+ bd->gen_no
+ bd->step
+
+ Exceptions: we don't maintain invariants for all the blocks within a
+ group on the free list, because it is expensive to modify every
+ bdescr in a group when coalescing. Just the head and last bdescrs
+ will be correct for a group on the free list.
+
+
+ Free lists
+ ~~~~~~~~~~
+ Preliminaries:
+ - most allocations are for single blocks
+ - we cannot be dependent on address-space ordering; sometimes the
+ OS gives us new memory backwards in the address space, sometimes
+ forwards
+ - We want to avoid fragmentation in the free list
+
+ Coalescing trick: when a bgroup is freed (freeGroup()), we can check
+ whether it can be coalesced with othre free bgroups by checking the
+ bdescrs for the blocks on either side of it. This means that:
+
+ - freeGroup is O(1) if we coalesce with an existing free block
+ group. Otherwise we have to insert in the free list, but since
+ most blocks are small and the free list is sorted by size, this
+ is usually quick.
+ - the free list must be double-linked, so we can insert into the
+ middle.
+ - every free group in the free list must have its head and tail
+ bdescrs initialised, the rest don't matter.
+ - we cannot play this trick with mblocks, because there is no
+ requirement that the bdescrs in the second and subsequent mblock
+ of an mgroup are initialised (the mgroup might be filled with a
+ large array, overwriting the bdescrs for example).
+
+ So there are two free lists:
+
+ - free_list contains bgroups smaller than an mblock.
+ - it is doubly-linked
+ - sorted in *size* order: allocation is best-fit
+ - free bgroups are always fully coalesced
+ - we do the coalescing trick in freeGroup()
+
+ - free_mblock_list contains mgroups only
+ - it is singly-linked (no need to double-link)
+ - sorted in *address* order, so we can coalesce using the list
+ - allocation is best-fit by traversing the whole list: we don't
+ expect this list to be long, avoiding fragmentation is more
+ important.
+
+ freeGroup() might end up moving a block from free_list to
+ free_mblock_list, if after coalescing we end up with a full mblock.
+
+ checkFreeListSanity() checks all the invariants on the free lists.
+
+ --------------------------------------------------------------------------- */
+
+static bdescr *free_list;
+static bdescr *free_mblock_list;
+