为FreeRTOS实现的Buddy内存分配器测试段错误排查

问题背景 #

为FreeRTOS实现Buddy内存分配器，编写初始化、分配、释放逻辑及测试用例后，运行测试出现段错误，进程退出码为-1073741819（0xC0000005），需排查是Windows环境问题还是代码错误。

核心代码与测试用例 #

结构体定义 #

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;

核心实现代码 #

#include <stdint.h>
#include <cstring>
#include "buddy_alloc.h"

#define BUDDY_MIN_BLOCK_SIZE 32
#define NULL 0


void buddy_init(buddy_allocator_t *allocator, void *memory, size_t *size) {
    // Initialize the allocator structure
    allocator->total_size = *size;
    allocator->min_block_size = BUDDY_MIN_BLOCK_SIZE;
    allocator->freelist = (buddy_block_t *) memory;
    allocator->freelist->next = NULL;
    allocator->freelist->size = *size;
    allocator->freelist->is_free = true;
}

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;

    // 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 (buddy < allocator->freelist ||
        buddy > (buddy_block_t *) ((uint8_t *) allocator->freelist + allocator->total_size)) {
        // The buddy is outside of the memory region managed by the allocator, so it 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;
    }
}

测试用例代码 #

// Test 1: Test with a single block in the free list
void test_buddy_init_1() {
    // Initialize the allocator
    buddy_allocator_t allocator;
    size_t size = 128;
    buddy_init(&allocator, NULL, &size);

    // Check the total size of the memory region
    assert(allocator.total_size == 16);

    // Check the size of the first block in the free list
    assert(allocator.freelist->size == 16);

    // Check the "is_free" flag of the first block
    assert(allocator.freelist->is_free == true);

    // Check the "next" pointer of the first block
    assert(allocator.freelist->next == NULL);
}

// Test 2: Test with a larger memory region
void test_buddy_init_2() {
    // Initialize the allocator
    buddy_allocator_t allocator;
    size_t size = 128;
    buddy_init(&allocator, NULL, &size);

    // Check the total size of the memory region
    assert(allocator.total_size == 128);

    // Check the size of the first block in the free list
    assert(allocator.freelist->size == 128);

    // Check the "is_free" flag of the first block
    assert(allocator.freelist->is_free == true);

    // Check the "next" pointer of the first block
    assert(allocator.freelist->next == NULL);
}

错误原因分析 #

段错误（0xC0000005）是Windows系统下的访问违规错误，直接原因是代码中的空指针解引用：

1. 测试用例中调用buddy_init(&allocator, NULL, &size)时，传入的memory参数为NULL，而buddy_init函数中直接对allocator->freelist（即NULL）进行成员赋值：

   allocator->freelist->next = NULL;
   allocator->freelist->size = *size;
   allocator->freelist->is_free = true;
   

   访问NULL指针的成员会触发内存访问违规，直接导致崩溃。

2. 测试用例test_buddy_init_1中存在逻辑错误：初始化时传入size=128，却断言allocator.total_size == 16，这会导致断言失败，但由于空指针解引用先发生，程序在执行到断言前就已经崩溃。

3. 额外问题：当前实现不符合Buddy算法的核心逻辑（Buddy算法要求块大小为2的幂次，拆分时需将块拆分为两个相等的2的幂次子块），但这是功能逻辑错误，不是当前崩溃的直接原因。

修复建议 #

1. 修复空指针问题：测试时需传入有效的内存块给buddy_init，比如用栈内存或动态分配的内存：

   // 修改test_buddy_init_2为例
   void test_buddy_init_2() {
       buddy_allocator_t allocator;
       size_t size = 128;
       // 分配一块足够的内存作为分配器的管理区域
       uint8_t memory[128];
       buddy_init(&allocator, memory, &size);
   
       assert(allocator.total_size == 128);
       assert(allocator.freelist->size == 128);
       assert(allocator.freelist->is_free == true);
       assert(allocator.freelist->next == NULL);
   }
   

2. 修正测试用例的断言逻辑：test_buddy_init_1中size=128，断言值应与传入的size一致，或调整传入的size为16。

3. 修正Buddy算法实现：

   • 分配时需将请求大小向上取整为最小的2的幂次（不小于BUDDY_MIN_BLOCK_SIZE）
   • 拆分块时需拆分为两个相等的2的幂次子块，而非按请求大小拆分
   • 查找Buddy块的方式需改为通过地址异或块大小（仅当块大小为2的幂时有效），而非直接累加块大小

内容的提问来源于stack exchange，提问作者worrum