Buddy allocator, blocks of memory and FreeRTOS

Question

I am trying to implement buddy allocator in C for FreeRTOS.

I made a function buddy_free for memory management. I am using struct _buddy_block and function for allocation and memory management, but things don't go well and I need your help. Here's my sources and problems below:

typedef struct _buddy_block {
    struct _buddy_block *next;
    size_t size;
    bool is_free;
} buddy_block_t;

typedef struct {
    buddy_block_t *freelist;
    size_t total_size;
    size_t min_block_size;
} buddy_allocator_t;

Allocation:

void *buddy_alloc(buddy_allocator_t *allocator, size_t size) {
    // Find the first free block that is large enough to satisfy the request
    buddy_block_t *block = allocator->freelist;
    while (block != NULL && (block->size < size || !block->is_free)) {
        block = block->next;
    }

    // If no suitable block was found, return NULL
    if (block == NULL) {
        return NULL;
    }

    // Split the block into two blocks if the block is larger than needed
    if (block->size > size) {
        // Create a new block for the remainder
        buddy_block_t *remainder = (buddy_block_t *) ((uint8_t *) block + size);

        remainder->size = block->size - size;
        remainder->is_free = true;
        remainder->next = block->next;

        // Update the current block
        block->size = size;
        block->next = remainder;
    }

    // Mark the block as allocated and return a pointer to the memory
    block->is_free = false;
    return (void *) (block + 1);
}

void buddy_free(buddy_allocator_t *allocator, void *ptr) {
    // Get a pointer to the block header
    buddy_block_t *block = (buddy_block_t *) ptr - 1;

    if (block->is_free) {
        return;
    }


    // Mark the block as free
    block->is_free = true;

    // Try to merge the block with its buddy (if it has one and the buddy is free)
    size_t block_size = block->size;
    buddy_block_t *buddy = (buddy_block_t *) ((uint8_t *) block + block_size);

    // Check if the buddy block is within the memory region managed by the allocator
    if (block < allocator->freelist ||
        block > (buddy_block_t *) ((uint8_t *) allocator->freelist + allocator->total_size) ||
        buddy < allocator->freelist ||
        buddy > (buddy_block_t *) ((uint8_t *) allocator->freelist + allocator->total_size)) {
    // One of the blocks is outside of the memory region managed by the allocator, so they cannot be merged
        return;
    }

    // Check if the buddy block is free and has the same size as the current block
    if (buddy->is_free && buddy->size == block_size) {
        // The buddy is free and has the same size as the current block, so they can be merged
        if (buddy < block) {
            // The buddy comes before the current block in memory, so it should be the new block
            buddy->size *= 2;
            buddy->next = block->next;
            block = buddy;
        } else {
        // The current block comes before the buddy in memory, so it should be the new block
            block->size *= 2;
            block->next = buddy->next;
        }
    }

// Insert the merged block back into the free list
    buddy_block_t *prev = NULL;
    buddy_block_t *curr = allocator->freelist;
    while (curr != NULL && curr < block) {
        prev = curr;
        curr = curr->next;
    }
    block->next = curr;
    if (prev == NULL) {
        allocator->freelist = block;
    } else {
        prev->next = block;
    }
}

First problem is that in the line:

while (block != NULL && (block->size < size || !block->is_free))

I get Segmentation fault with test_buddy_alloc_insufficient_memory test:

// Test the behavior of the buddy_alloc function when it is unable to fulfill an allocation request due to insufficient free memory
void test_buddy_alloc_insufficient_memory() {
    // Allocate all of the available memory
    buddy_allocator_t allocator;
    void *ptr = buddy_alloc(&allocator, allocator.total_size);
    assert(ptr != NULL);

    // Attempt to allocate more memory
    ptr = buddy_alloc(&allocator, 1);
    assert(ptr == NULL);
}

// Test the behavior of the buddy_alloc function when it is called with a size of 0
void test_buddy_alloc_size_zero() {
    buddy_allocator_t allocator;
    // Attempt to allocate a block of size 0
    void *ptr = buddy_alloc(&allocator, 0);
    assert(ptr == NULL);
}

Can someone help me to fix or improve my code?

Answer 1

You have UB (undefined behavior).

In your test_* functions, you have:

buddy_allocator_t allocator;

This is on the stack and is uninitialized.

You need:

buddy_allocator_t allocator = { 0 };

With -Wall, the compiler flags:

orig.c: In function ‘test_buddy_alloc_insufficient_memory’:
orig.c:114:14: warning: ‘allocator.total_size’ is used uninitialized in this function [-Wuninitialized]
  void *ptr = buddy_alloc(&allocator, allocator.total_size);
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Also, in buddy_alloc, the first thing it does is:

buddy_block_t *block = allocator->freelist;

while (block != NULL && (block->size < size || !block->is_free))

The block != NULL is insufficient. It does not guard against dereferencing a non-null but random/invalid pointer value.

---

UPDATE:

From the discussion and further review, I didn't see any code to set up the allocator struct with a valid block. So, the allocator started without any memory.

Normally, we'd call brk/sbrk to get more memory from the system, but, for testing, we can use a static/persistent fixed array.

Here is the restructured code:

#include <stddef.h>
#include <stdint.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

typedef struct _buddy_block {
    struct _buddy_block *next;
    size_t size;
    bool is_free;
} buddy_block_t;

typedef struct {
    buddy_block_t *freelist;
    size_t total_size;
    size_t min_block_size;
} buddy_allocator_t;

void *
buddy_alloc(buddy_allocator_t * allocator, size_t size)
{
    // Find the first free block that is large enough to satisfy the request
    buddy_block_t *block = allocator->freelist;

    while (block != NULL && (block->size < size || !block->is_free)) {
        block = block->next;
    }

    // If no suitable block was found, return NULL
    if (block == NULL) {
        return NULL;
    }

    // Split the block into two blocks if the block is larger than needed
    if (block->size > size) {
        // Create a new block for the remainder
        buddy_block_t *remainder = (buddy_block_t *) ((uint8_t *) block + size);

        remainder->size = block->size - size;
        remainder->is_free = true;
        remainder->next = block->next;

        // Update the current block
        block->size = size;
        block->next = remainder;
    }

    // Mark the block as allocated and return a pointer to the memory
    block->is_free = false;
    return (void *) (block + 1);
}

void
buddy_free(buddy_allocator_t * allocator, void *ptr)
{
    // Get a pointer to the block header
    buddy_block_t *block = (buddy_block_t *) ptr - 1;

    if (block->is_free) {
        return;
    }

    // Mark the block as free
    block->is_free = true;

    // Try to merge the block with its buddy (if it has one and the buddy is free)
    size_t block_size = block->size;
    buddy_block_t *buddy = (buddy_block_t *) ((uint8_t *) block + block_size);

    // Check if the buddy block is within the memory region managed by the allocator
    if (block < allocator->freelist || block > (buddy_block_t *) ((uint8_t *) allocator->freelist + allocator->total_size) || buddy < allocator->freelist || buddy > (buddy_block_t *) ((uint8_t *) allocator->freelist + allocator->total_size)) {
        // One of the blocks is outside of the memory region managed by the allocator, so they cannot be merged
        return;
    }

    // Check if the buddy block is free and has the same size as the current block
    if (buddy->is_free && buddy->size == block_size) {
        // The buddy is free and has the same size as the current block, so they can be merged
        if (buddy < block) {
            // The buddy comes before the current block in memory, so it should be the new block
            buddy->size *= 2;
            buddy->next = block->next;
            block = buddy;
        }
        else {
            // The current block comes before the buddy in memory, so it should be the new block
            block->size *= 2;
            block->next = buddy->next;
        }
    }

// Insert the merged block back into the free list
    buddy_block_t *prev = NULL;
    buddy_block_t *curr = allocator->freelist;

    while (curr != NULL && curr < block) {
        prev = curr;
        curr = curr->next;
    }
    block->next = curr;
    if (prev == NULL) {
        allocator->freelist = block;
    }
    else {
        prev->next = block;
    }
}

void
initme(buddy_allocator_t *ctl)
{
#if 0
    static buddy_block_t block;
    static char mem[1024 * 1024];

    memset(&block,0,sizeof(block));
    block.size = sizeof(mem);
    block.is_free = 1;

    ctl->total_size = block.size;
    ctl->freelist = &block;
    ctl->min_block_size = 128;
#else
    static char mem[1024 * 1024];
    buddy_block_t *block = (void *) mem;

    memset(block,0,sizeof(*block));
    block->size = sizeof(mem) - sizeof(*block);
    block->is_free = 1;

    ctl->total_size = block->size;
    ctl->freelist = block;
    ctl->min_block_size = 128;
#endif
}

// Test the behavior of the buddy_alloc function when it is unable to fulfill an allocation request due to insufficient free memory
void
test_buddy_alloc_insufficient_memory()
{
    // Allocate all of the available memory
    buddy_allocator_t allocator = { 0 };
    initme(&allocator);

    void *ptr = buddy_alloc(&allocator, allocator.total_size);
    assert(ptr != NULL);

    // Attempt to allocate more memory
    ptr = buddy_alloc(&allocator, 1);
    assert(ptr == NULL);
}

// Test the behavior of the buddy_alloc function when it is called with a size of 0
void
test_buddy_alloc_size_zero()
{
    buddy_allocator_t allocator = { 0 };
    initme(&allocator);

    // Attempt to allocate a block of size 0
    void *ptr = buddy_alloc(&allocator, 0);

    assert(ptr == NULL);
}

int
main(void)
{

    test_buddy_alloc_insufficient_memory();
    test_buddy_alloc_size_zero();

    return 0;
}