设计一个简单的内存分配器

题目

设计一个简单的内存分配器

信息

• 类型：问答
• 难度：⭐⭐

考点

内存分配算法,碎片管理,指针操作

快速回答

实现一个基于隐式空闲链表的内存分配器需要：

1. 定义块头部结构（存储块大小和分配状态）
2. 实现初始化函数建立初始空闲块
3. 实现分配函数（首次适应算法）
4. 实现释放函数（合并相邻空闲块）
5. 处理对齐要求（通常8字节对齐）

关键挑战：碎片优化和边界合并

解析

1. 核心原理

隐式空闲链表通过在每个内存块头部存储元数据（大小+分配标志），将所有块串联成隐式链表：

typedef struct header {
    size_t size;          // 块大小（包含头部）
    unsigned is_free : 1; // 最低位标记分配状态
} Header;

内存布局：
[Header|数据区] → [Header|数据区] → ...

2. 关键实现

初始化内存池

void init_allocator() {
    void *heap = sbrk(INIT_SIZE); // 申请堆空间
    Header *header = (Header*)heap;
    header->size = INIT_SIZE;
    header->is_free = 1;
}

内存分配（首次适应）

void* my_malloc(size_t size) {
    // 1. 计算对齐后所需大小（包含头部）
    size_t total_size = ALIGN(size + sizeof(Header));

    // 2. 遍历链表查找空闲块
    Header *curr = (Header*)heap_start;
    while (curr < heap_end) {
        if (curr->is_free && curr->size >= total_size) {
            // 3. 分割块（剩余空间足够时）
            if (curr->size > total_size + sizeof(Header)) {
                split_block(curr, total_size);
            }
            curr->is_free = 0;
            return (void*)(curr + 1); // 返回数据区指针
        }
        curr = NEXT_BLOCK(curr); // 移动到下一个块
    }
    return NULL; // 分配失败
}

内存释放与合并

void my_free(void *ptr) {
    if (!ptr) return;

    Header *header = (Header*)ptr - 1;
    header->is_free = 1;

    // 向后合并（检查下一块是否空闲）
    Header *next = NEXT_BLOCK(header);
    if (next < heap_end && next->is_free) {
        header->size += next->size;
    }

    // 向前合并（需记录前一块位置）
    // 实现略（可通过边界标记优化）
}

3. 最佳实践

• 对齐处理：使用 #define ALIGN(size) (((size) + 7) & ~7)
• 分割阈值：剩余空间至少保留 sizeof(Header)+8 才分割
• 合并优化：采用边界标记（在块尾部复制头部信息）实现O(1)前向合并
• 扩展堆：空间不足时调用 sbrk() 扩展堆大小

4. 常见错误

• 🚫 未处理对齐：导致非法内存访问（如SSE指令要求16字节对齐）
• 🚫 头部覆盖：返回数据区指针时误用 header 而非 header+1
• 🚫 合并失效：未正确处理相邻空闲块，导致碎片
• 🚫 大小计算错误：未包含头部大小或对齐填充

5. 扩展知识

• 显式空闲链表：在空闲块中添加 prev/next 指针，加速搜索
• 分离适配：按大小分类的空闲链表（如dlmalloc实现）
• 伙伴系统：固定大小分块，快速合并但易产生内碎片
• 性能指标：吞吐量（ops/sec）和内存利用率（有效数据/总分配）