- 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.
+ whether it can be coalesced with other free bgroups by checking the
+ bdescrs for the blocks on either side of it. This means that we can
+ coalesce in O(1) time. Every free bgroup must have its head and tail
+ bdescrs initialised, the rest don't matter.
+
+ We keep the free list in buckets, using a heap-sort strategy.
+ Bucket N contains blocks with sizes 2^N - 2^(N+1)-1. The list of
+ blocks in each bucket is doubly-linked, so that if a block is
+ coalesced we can easily remove it from its current free list.
+
+ To allocate a new block of size S, grab a block from bucket
+ log2ceiling(S) (i.e. log2() rounded up), in which all blocks are at
+ least as big as S, and split it if necessary. If there are no
+ blocks in that bucket, look at bigger buckets until a block is found
+ Allocation is therefore O(logN) time.
+
+ To free a block:
+ - coalesce it with neighbours.
+ - remove coalesced neighbour(s) from free list(s)
+ - add the new (coalesced) block to the front of the appropriate
+ bucket, given by log2(S) where S is the size of the block.
+
+ Free is O(1).
+
+ We cannot play this coalescing 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 is a separate free list for megablocks, sorted in *address*
+ order, so that we can coalesce. Allocation in this list is best-fit
+ by traversing the whole list: we don't expect this list to be long,
+ and allocation/freeing of large blocks is rare; avoiding
+ fragmentation is more important than performance here.