Buddy Allocator

buddy.cpp

#include <iostream>
#include <cstdint>
#include <cassert>
#include <vector>

// Definitions in powers of two
constexpr std::size_t MemBlockExp = 6;

// A single memory block to try the algorithm
struct Block
{
    Block* next;
};

// Provide storage and the block pointers
Block storage[1 << MemBlockExp];
Block* nextFreeBlocks[MemBlockExp+1];

// Function to initialize the allocator
void initAllocator()
{
    // Allocate the first block and set the other orders to zero
    nextFreeBlocks[MemBlockExp] = storage;
    storage[0] = { nullptr };

    for (std::size_t i = 0; i < MemBlockExp-1; i++)
        nextFreeBlocks[i] = nullptr;
}

// Function to print the allocator's statod
void printStatus()
{
    std::cout << "Current status of the buddy allocator:" << std::endl;
    for (std::size_t i = MemBlockExp; i <= MemBlockExp; i--)
    {
        std::cout << "order " << i << ':';
        for (auto block = nextFreeBlocks[i]; block; block = block->next)
        {
            std::size_t id = block-storage;
            std::cout << " [" << id << ',' << (id+(1<<i)-1) << "]";
        }
        std::cout << std::endl;
    }
}

// Split a block in two, returning the first block
Block* splitBlock(Block* block, std::size_t order)
{
    // We cannot really split an atom block
    if (order == 0) return block;

    // Downsize the order of the block and insert a new block in the free list
    order--;

    // Prepare the next block
    block[1 << order].next = nextFreeBlocks[order];

    // Point the new block and insert it in the free store
    nextFreeBlocks[order] = block+(1 << order);

    // And finally return the block
    return block;
}

// Function to get a block of memory of a specific order
// (order is the expoent of the size of the block requested)
Block* allocMem(std::size_t order)
{
    if (order > MemBlockExp) return nullptr;

    // Pick a block of that order
    if (nextFreeBlocks[order])
    {
        auto block = nextFreeBlocks[order];
        nextFreeBlocks[order] = block->next;
        return block;
    }

    // Pick a superior block and split it as many times as necessary
    Block* block = nullptr;
    std::size_t foundOrder;
    for (foundOrder = order+1; foundOrder <= MemBlockExp; foundOrder++)
    {
        block = nextFreeBlocks[foundOrder];
        if (block)
        {
            // Take the block from the free list
            nextFreeBlocks[foundOrder] = block->next;
            break;
        }
    }

    // Bail out if no block is there
    if (!block) return nullptr;

    // Split the block as many times as necessary
    while (foundOrder > order)
    {
        block = splitBlock(block, foundOrder);
        foundOrder--;
    }
    return block;
}

// Function to free a block given a specific order (this is important)
void freeMem(Block* block, std::size_t order)
{
    // First, join recursively the buddy blocks
    for (; order < MemBlockExp; order++)
    {
        std::size_t id = block - storage;
        auto buddy = storage + (id ^ (1 << order));

        // Find it in the free list
        Block* buddyBlock;
        Block* prevBlock = nullptr;
        for (buddyBlock = nextFreeBlocks[order]; buddyBlock; buddyBlock = block->next)
        {
            if (buddyBlock == buddy) break;
            prevBlock = buddyBlock;
        }

        // And join it if it exists
        if (buddyBlock)
        {
            // Take it from the free list
            if (prevBlock) prevBlock->next = buddyBlock->next;
            else nextFreeBlocks[order] = buddyBlock->next;

            // Make the bigger block as the storage
            block = storage+(id &~ (1<<order));
        }
        else break;
    }

    // Put it back in the free list
    block->next = nextFreeBlocks[order];
    nextFreeBlocks[order] = block;
}

int main()
{
    initAllocator();

    std::vector<std::pair<Block*,int>> blocks;

    while (true)
    {
        printStatus();
        std::cout << "Allocated blocks:";
        std::size_t i = 0;
        for (auto [block, order] : blocks)
        {
            std::size_t id = block - storage;
            std::cout << ' ' << i << ":[" << id << ',' << (id+(1<<order)-1) << "]";
            i++;
        }
        std::cout << std::endl << std::endl;

        std::cout << "Type a command: ";
        std::string cmd;
        std::cin >> cmd;

        if (cmd == "alloc")
        {
            std::size_t order;
            std::cin >> order;

            auto block = allocMem(order);
            if (block) blocks.emplace_back(block, order);
        }
        else if (cmd == "free")
        {
            std::size_t id;
            std::cin >> id;

            if (id >= blocks.size())
                std::cout << "Id invalid! Try another id!" << std::endl;
            else
            {
                auto it = blocks.begin() + id;
                freeMem(it->first, it->second);
                blocks.erase(it);
            }
        }
        else std::cout << "Invalid command! Type another command!" << std::endl;
    }
}