Free List Allocator with Red Black Tree

user_5672025 0
Viewed 1112

I'm trying to implement a free list allocator using Red Black Tree for optimize O(LogN) best fit search.

My strategy is that when a block is allocated, it's allocated with a Header where

struct Header {
  std::size_t m_Size;
};

thus sizeof(Header) == sizeof(std::size_t) This is done, so when deallocating I could know how much bytes were allocated to give it back as a free node.

Now there's a problem with this solution, because now I have to align the Header itself + the allocated block to the requested alignment, so padding in between the Header and the allocated block start, and padding between the end of the allocated block and a start of a new Header (so next block Header will be already aligned) are needed.

So to illustrate the problem better here's a Red Black Tree with nodes indicating free block sizes minus sizeof(Header) enter image description here

Now let's assume a user allocate a block of size 16 with alignment of 16:

allocate(16, 16);

Now best fit will yield us node 17.
But we can't count on it, let's assume node 17 is at address 0x8 and we're on x32 so sizeof(Header) = 4.
Header's address will be from 0x8-0xC, now we would need to add a padding so our block will be aligned to 16 as requested, this padding is equal to 4 bytes so our allocated block will start at 0x10 which is aligned to 16. Now no padding is needed at the end of the block since 0x10 + 16d will be aligned to next block Header.
The padding between the end of the allocated block to the start of the new block is easy to calculate before-hand like so:

std::size_t headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;

So it's not dependent on the address of the free node.
But the padding between the end of the Header and the start of the allocated block IS dependent on the address of the free node like I've demonstrated.
And for our example the total needed size in the case of this specific node will be 4 (padding between Header and allocated block) + 16 (allocated block size) + 0 (padding needed for next free block header alignment) = 20.
Obviously node 17 doesn't match.

Now my strategy to fix this is as follows:
- Find best fit - See if best fit matches the size requirements as described - If yes we're done - If not get its successor and check if it matches the size requirements as described - If yes we're done - If not start over from successor parent until we reach a node that satisfy size requirements or we reach the original best fit again

Here's a code describing the process:

void FreeTreeAllocator::Find(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node*& curr)
{
    headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;

    RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
    RBTree::Node* origin = best;

    std::vector<std::size_t> visited;

    while (visited[visited.size() - 1] != (std::size_t)origin && !IsNodeBigEnough(size, alignment, sizePadding, headerPadding, best))
    {
        RBTree::Node* successor = m_Tree.Successor(best);
        if (IsNodeBigEnough(size, alignment, sizePadding, headerPadding, successor))
        {
            best = successor;
            break;
        }
        else
        {
            std::vector<std::size_t>::iterator it;
            do {
                best = successor->m_Parent;
                it = std::find(visited.begin(), visited.end(), (std::size_t)best);
            } while (it != visited.end());
        }
        visited.push_back((std::size_t)best);
    }
}

bool FreeTreeAllocator::IsNodeBigEnough(const std::size_t size, const std::size_t alignment, std::size_t& sizePadding, std::size_t& headerPadding, RBTree::Node* curr)
{
    if (curr == m_Tree.m_Nil)
        return false;
    void* currentAddress = reinterpret_cast<char*>(curr) + sizeof(Header);
    std::size_t space = curr->m_Value;
    std::align(alignment, size, currentAddress, space);
    sizePadding = reinterpret_cast<char*>(currentAddress) - reinterpret_cast<char*>(curr) - sizeof(Header);
    return sizePadding + size + headerPadding <= curr->m_Value;
}

Now for the given allocation request:

allocate(16, 16);

and the given example tree from the picture the following the algorithm described, the search path will be:

17 -> 21 -> 22 -> 23 -> 25 -> 27

At worst case this is O(LogN + M) where M is the size of the right sub-tree of the original best fit node.

Now one way this could be solved if I make sizeof(Header) = sizeof(std::max_align_t), this way the padding between the Header and the start of the allocated block will always be 0, so we won't need this padding anymore because every request will be aligned without this padding, so we could really just do:

void FreeTreeAllocator::Find(const std::size_t size, std::size_t& headerPadding, RBTree::Node*& curr)
{
    headerPadding = size % sizeof(Header) != 0 ? sizeof(Header) - size % sizeof(Header) : 0;

    RBTree::Node* best = m_Tree.SearchBest(m_Tree.m_Root, size + headerPadding);
    return best;

But that will waste alot of memory compared to my proposed idea where I settle on O(LogN + M) best fit search.

Now why do I ask it?
Because I see the use of Red Black Tree as optimization for free list allocator to reduce best fit search to O(LogN) while I can't seem to make it really O(LogN), the flaw with my design I guess is that there need to be a Header for book-keeping on how much bytes to give back to a free block when deallocating, and I don't see a way to do it without this, if I was able to not have a Header at all, or make it so I don't have issues with it's alignment to find padding specific for a node in the list (by making sizeof(Header) = sizeof(std::max_align_t), or even sizeof(Header) = 1) then this could be solved with simple O(LogN) search.

I'm looking for ideas on how to solve this issue, how other implementations are doing this in O(LogN) while keeping inner fragmentation as low as possible?

UPDATE:
I ended up having the node addresses aligned to alignof(std::max_align_t) - sizeof(Header) so that makes Header always aligned no matter if you're on x32/x64 (remember that Header is composed of sizeof(std::size_t)), and no matter if alignof(std::max_align_t) is 8 or 16.
That makes the allocated payload to start at address that is aligned to alignof(std::max_align_t) just like malloc, so no matter what is allocated it will always be aligned to the max alignment and no padding is required between Header and payload. The only padding required is after payload to match the next address that is aligned to alignof(std::max_align_t) - sizeof(Header) + any padding required to make it so the allocated block is at least sizeof(RBTree::Node) bytes big (including sizeof(Header) inside the equation) so when deallocation we could safely store an RBTree::Node without overriding other data.
Without the padding between Header and the payload, and with the padding needed to align next block to alignof(std::max_align_t) - sizeof(Header) we can easily use the default RBTree::Search of O(LogN) since the padding can be calculated beforehand depending on the size of the block and removing from the equation the start address of a particular node.

The only remaining problem I have with optimizing this free list allocator to O(LogN) is the deallocation part, more precisely the coalescence part.
What I can't solve now is how to do O(1) coalescence. I rearranged the RBTree::Node struct such as that m_Parent is first and so its LSB is always set 1 (for every function relying on m_Parent I have a getter function for fixing it) and then I can check if next block of current deallocated block (we can get to next block with size from Header) if the first sizeof(std::size_t) bytes & 0x1 is true and if so it's a free node, if not it's a busy block with Header (since Header's m_Size LSB will always be 0 because we add padding for alignment with std::max_align_t).
The remaining problem is how to get to the previous memory block and know if it's free or busy, that I cannot figure yet and would love to hear suggestions.

red-black-tree memory-management algorithm c++
3 Answers

For the padding issue:

Make sure the size of your free list nodes is a power of 2 -- either 16 or 32 bytes -- and make sure the addresses of your free list nodes are all aligned at node_size * x - sizeof(Header) bytes.

Now all of your allocations will automatically be aligned at multiples of the node size, with no padding required.

Allocations requiring larger alignments will be rare, so it might be reasonable just to find the left-most block of appropriate size, and walk forward in the tree until you find a block that works.

If you need to optimize large-alignment allocations, though, then you can sort the blocks first by size, and then break ties by sorting on the number of zeros at the right of each nodes's allocation address (node address + sizeof(Header)).

Then, a single search in the tree will either find an exactly-fitting block that works, or a larger block. There is a good chance you'll be able to split the larger block in a way that satisfies the alignment requirement, but if not, then you can again skip ahead in the tree to find a block of that size that works, or an even larger block, etc.

The resulting search is faster, but still not guaranteed O(log N). To fix that, you can just give up after a limited number of skips forward, and revert to finding a block of requested_size + requested_alignment. If you find one of those, then it is guaranteed that you'll be able to split it up to satisfy your alignment constraint.

user_54835260

there need to be a Header for book-keeping on how much bytes to give back to a free block when deallocating

On a 64-bit platform, one way to eliminate the header is to make your allocator manage arenas of power-of-2 object sizes. Each arena is for one object size and all arenas are of the same size. Then map (reserve only) one large chunk of virtual memory in such a way, that it is aligned by its own size (which is also a power of 2). That way, your pointers to objects are structured: the lower order bits are the offset to the object within the arena, the next bits are the arena number. For each arena it needs to maintain the free list and allocated object count, but the free lists must initially include only one page or 1 object (whichever is bigger), so that it doesn't commit page frames to the entire reserved virtual memory, which would run out of memory immediately.

For example, if you have 8GiB arenas for objects of power-2-sizes from 8 to 65536 bytes, then the lower [0:32] bits are the object offset within the arena, bits [33:36] are the arena number and log2 of object size (arenas [0, 2] are unused because they are not big enough for free list next pointer).

user_4120800

The complete answer is my OP update and this answer.
I found a solution for coalescence in O(1).
My OP update describe how we can achieve coalescence with next block in O(1) but not how to achieve coalescence in O(1) with previous block.
To do this I store an additional std::size_t m_PrevSize in both busy block Header struct and RBTree::Node struct as the first member. When a block is allocated and becomes busy (either by simple allocation or by block splitting) I simply move to the next block using the Header's m_Size property and the first std::size_t bytes to 0. This will set the next memory block either busy or free that the previous is busy and there's no need to merge with.
When a block is deallocated and I convert it to free block, I do the same thing but set the first std::size_t bytes to RBTree::Node's m_Value property which is basically how much bytes this free block have, and the when deallocating I can check own m_PrevSize property and if it's not 0 go backward m_PrevSize bytes and do the merge.

user_56720250
Related