Buddy allocator block free index can be optimized

[sourencho]

We have a static array that holds a bit indicating whether or not a block is free or not (alloc_block_size) to avoid spending the time looping over its level's free list to see if it's there.

The size of this array could be halved using this strategy:

For each pair of buddies A and B we store the single bit is_A_free XOR is_B_free. We can easily maintain the state of that bit by flipping it each time one of the buddies is freed or allocated.
When we consider making a merge we know that one of buddies is free, because it is only when a block has just been freed that we consider a merge. This means we can find out the state of the other block from the XORed bit. If it is 0, then both blocks are free. If it is 1 then it is just our block that is free.
So we can get by with just one bit for every pair of blocks, that's half a bit per block, or an overhead of just 1 / 16 / leaf_size.

Details can be found in this blog post: http://bitsquid.blogspot.com/2015/08/allocation-adventures-3-buddy-allocator.html