FreeRTOS下C语言Buddy分配器实现遇段错误求助

核心问题分析 #

你当前的Buddy分配器实现存在以下几个关键问题，直接导致测试用例触发段错误或逻辑异常：

1. 分配器未初始化：测试用例中直接使用栈上未初始化的buddy_allocator_t结构体，freelist为野指针，访问block->size时触发段错误。
2. 空闲链表维护错误：buddy_alloc未将分配的块从空闲链表中移除，导致链表中混有已分配块，后续遍历会访问非法内存。
3. 块拆分逻辑违规：未遵循Buddy分配器的2的幂拆分规则，直接按请求大小拆分，无法正确合并伙伴块。
4. 伙伴块查找错误：原buddy_free通过block + block_size计算伙伴块，这是错误的，正确方式是通过地址异或块总大小定位伙伴。
5. 边界检查缺失：未处理空指针、size=0等边界场景，导致非法访问。

修复后的完整代码 #

结构体定义 #

#include <stdint.h>
#include <stdbool.h>
#include <stddef.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;// 最小分配单元（必须是2的幂）
} buddy_allocator_t;

分配器初始化函数 #

bool buddy_allocator_init(buddy_allocator_t *allocator, void *mem, size_t total_size, size_t min_block_size) {
    if (!allocator || !mem) return false;
    // 总内存必须是2的幂，且至少能容纳一个块头+最小块大小
    if (total_size < sizeof(buddy_block_t) + min_block_size || (total_size & (total_size - 1)) != 0) {
        return false;
    }
    // 最小块大小必须是2的幂
    if ((min_block_size & (min_block_size - 1)) != 0) {
        return false;
    }

    buddy_block_t *initial_block = (buddy_block_t *)mem;
    initial_block->next = NULL;
    initial_block->size = total_size - sizeof(buddy_block_t);
    initial_block->is_free = true;

    allocator->freelist = initial_block;
    allocator->total_size = total_size;
    allocator->min_block_size = min_block_size;
    return true;
}

修复后的分配函数 #

void *buddy_alloc(buddy_allocator_t *allocator, size_t size) {
    if (!allocator || size == 0) {
        return NULL;
    }

    size_t max_available = allocator->total_size - sizeof(buddy_block_t);
    if (size > max_available) {
        return NULL;
    }

    // 计算需要的最小块大小（向上取2的幂，不小于min_block_size）
    size_t required_size = size;
    if (required_size < allocator->min_block_size) {
        required_size = allocator->min_block_size;
    }
    if ((required_size & (required_size - 1)) != 0) {
        required_size = 1 << (64 - __builtin_clzll(required_size));
    }

    // 首次适配查找空闲块
    buddy_block_t *prev = NULL;
    buddy_block_t *block = allocator->freelist;
    while (block != NULL && (block->size < required_size || !block->is_free)) {
        prev = block;
        block = block->next;
    }

    if (block == NULL) {
        return NULL;
    }

    // 将块从空闲链表中移除
    if (prev == NULL) {
        allocator->freelist = block->next;
    } else {
        prev->next = block->next;
    }

    // 按2的幂拆分块，直到满足需求
    while (block->size > required_size) {
        size_t split_size = block->size / 2;
        buddy_block_t *remainder = (buddy_block_t *)((uint8_t *)block + sizeof(buddy_block_t) + split_size);
        remainder->size = split_size;
        remainder->is_free = true;
        remainder->next = allocator->freelist;
        allocator->freelist = remainder;
        block->size = split_size;
    }

    block->is_free = false;
    return (void *)(block + 1);
}

修复后的释放函数 #

void buddy_free(buddy_allocator_t *allocator, void *ptr) {
    if (!allocator || !ptr) {
        return;
    }

    buddy_block_t *block = (buddy_block_t *)ptr - 1;
    uint8_t *mem_start = (uint8_t *)allocator->freelist;
    uint8_t *mem_end = mem_start + allocator->total_size;

    // 检查块是否在分配器管理范围内
    if ((uint8_t *)block < mem_start || (uint8_t *)block + sizeof(buddy_block_t) + block->size > mem_end) {
        return;
    }
    if (block->is_free) {
        return;
    }

    block->is_free = true;
    size_t block_total_size = sizeof(buddy_block_t) + block->size;

    // 循环尝试合并伙伴块
    while (true) {
        buddy_block_t *buddy = (buddy_block_t *)((uintptr_t)block ^ block_total_size);
        // 检查伙伴块合法性
        if ((uint8_t *)buddy < mem_start || (uint8_t *)buddy + block_total_size > mem_end) {
            break;
        }
        if (!buddy->is_free || buddy->size != block->size) {
            break;
        }

        // 合并块：保留地址较小的块
        if (buddy < block) {
            block = buddy;
        }
        block->size *= 2;
        block_total_size = sizeof(buddy_block_t) + block->size;

        // 将伙伴块从空闲链表中移除
        buddy_block_t *prev = NULL;
        buddy_block_t *curr = allocator->freelist;
        while (curr != NULL && curr != buddy) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != NULL) {
            if (prev == NULL) {
                allocator->freelist = curr->next;
            } else {
                prev->next = curr->next;
            }
        }
    }

    // 将合并后的块插入空闲链表头部
    block->next = allocator->freelist;
    allocator->freelist = block;
}

修复后的测试用例 #

#include <assert.h>

#define TEST_MEM_SIZE (4096)
static uint8_t test_mem[TEST_MEM_SIZE];

void test_buddy_alloc_insufficient_memory() {
    buddy_allocator_t allocator;
    assert(buddy_allocator_init(&allocator, test_mem, TEST_MEM_SIZE, 16));

    size_t max_alloc_size = TEST_MEM_SIZE - sizeof(buddy_block_t);
    void *ptr = buddy_alloc(&allocator, max_alloc_size);
    assert(ptr != NULL);

    ptr = buddy_alloc(&allocator, 1);
    assert(ptr == NULL);
}

void test_buddy_alloc_size_zero() {
    buddy_allocator_t allocator;
    assert(buddy_allocator_init(&allocator, test_mem, TEST_MEM_SIZE, 16));

    void *ptr = buddy_alloc(&allocator, 0);
    assert(ptr == NULL);
}

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