Hotdry.
归档
systems-engineering

C语言轻量级内存分配器：空闲链表管理与块拆分合并

面向嵌入式系统的无依赖内存分配器，详解空闲链表、块拆分与释放合并的核心实现、参数阈值及碎片监控要点。

在嵌入式系统和资源受限环境中，标准 malloc/free 往往依赖系统调用，引入不可预测的延迟和内存开销。为此，自实现轻量级、无依赖的内存分配器成为常见优化策略。本文聚焦 C 语言下最小化内存分配器，强调空闲链表（freelist）管理、分配时的块拆分（splitting）和释放时的合并（coalescing），提供可落地工程参数和监控清单。

为什么需要自定义内存分配器？

标准 libc malloc（如 ptmalloc 或 jemalloc）虽高效，但针对通用场景：多线程支持、bins 分级、大页优化等。在裸机 / RTOS 嵌入式中，这些特性反成负担：

  • 系统调用开销：brk/mmap 引入上下文切换。
  • 元数据膨胀：每个块 8-16 字节头部，碎片化严重。
  • 非确定性：垃圾回收或并发锁导致抖动。

自定义分配器使用固定 arena（预分配内存池），实现 O (1)~O (n) 分配，零 syscall，适用于实时系统。典型场景：传感器数据缓冲、RTOS 任务栈、网络包处理。

事实支撑：嵌入式项目中，自定义分配器可将分配延迟从 us 级降至 ns 级，内存利用率提升 20-50%（基于 freelist 基准测试）。

核心数据结构：带元数据的双向空闲链表

分配器以固定 arena 起始（如 uint8_t arena [1<<20];），每个块前置元数据：

typedef struct Block {
    size_t size;      // 当前块大小（含头部，8字节对齐）
    struct Block* prev; // 前块指针（双向链表）
    struct Block* next; // 后块指针
    bool used;        // 占用标志（最低位嵌入size可节省空间）
} Block;
  • arena 首块：Block* head = (Block*) arena;
  • 空闲块串成双向链表，便于 O (1) 合并。
  • 对齐：size 向上取 8 字节倍数，宏ALIGN8(size)实现。

初始：整个 arena 为一个空闲块，head->size = ARENA_SIZE; head->used=0; head->prev=next=NULL。

参数建议：

参数 值 说明
ALIGN_BYTES 8 x86/ARM 常见，减碎片
HEADER_SIZE sizeof(Block) 24 字节（64 位）
ARENA_SIZE 1MB~64MB 嵌入式上限
MIN_BLOCK 32 小于丢弃，避免碎片

分配（malloc）：查找 + 拆分

流程：

  1. 从 head 遍历 freelist，first-fit/best-fit 选块。
  2. 若块 size >= req + HEADER_SIZE + MIN_BLOCK，拆分：后块变空闲，新块 used=1，返回 user_ptr = block+1。
  3. 无合适：返回 NULL 或 panic。

伪码：

void* my_malloc(size_t req) {
    req = ALIGN8(req + HEADER_SIZE);
    Block* b = head;
    Block* best = NULL; size_t best_size = SIZE_MAX;
    while (b) {  // first-fit: 第一个合适即取；best-fit: 最小合适
        if (!b->used && b->size >= req) {
            if (first_fit) return split(b, req);
            if (b->size < best_size) best = b;
        }
        b = b->next;
    }
    return best ? split(best, req) : NULL;
}

Block* split(Block* b, size_t req) {
    Block* newb = (Block*)((uint8_t*)b + req);
    newb->size = b->size - req;
    newb->used = 0;
    newb->prev = b; newb->next = b->next;
    if (b->next) b->next->prev = newb;
    b->next = newb;
    b->size = req; b->used = 1;
    return (void*)(b + 1);
}
  • 策略选择：first-fit 快（平均遍历少），best-fit 抗碎片但慢。嵌入式首选 first-fit。
  • 阈值：若 req <16B，用栈 / 静态；>ARENA/2，直接 panic。

落地清单：

  • 预热：启动时预分配 100 小块，避冷启动抖动。
  • 批量 alloc：对象池模式，预切固定大小块。

释放（free）：合并前后空闲块

关键抗碎片：coalescing。

void my_free(void* ptr) {
    if (!ptr) return;
    Block* b = (Block*)ptr - 1;
    b->used = 0;
    // 合并后块
    if (b->next && !b->next->used) {
        coalesce(b, b->next);
    }
    // 合并前块
    if (b->prev && !b->prev->used) {
        coalesce(b->prev, b);
    }
}

void coalesce(Block* a, Block* b) {
    a->size += b->size;
    a->next = b->next;
    if (a->next) a->next->prev = a;
    // b回收，无需free
}
  • 时机：lazy coalescing（仅 free 时），或周期 scan。
  • 风险：外部碎片（空闲块散布），内部碎片（块 > req）。

监控与优化参数

嵌入式需可观测：

size_t stats[3]; // used, free, peak_frag
void print_stats() {
    size_t used=0, free=0, max_free=0;
    Block* b = head;
    while (b) {
        if (b->used) used += b->size;
        else { free += b->size; max_free = max(max_free, b->size); }
        b = b->next;
    }
    float util = 100.0 * used / ARENA_SIZE;
    float frag = 100.0 * (free ? max_free / free : 0); // 最大空闲/总空闲
    // 日志：util>90%? 扩arena; frag>50%? 切换best-fit
}

监控阈值：

指标 阈值 动作
利用率 <70% 泄漏检查
碎片率 >30% 加 bins（size-class）
分配延迟 >1us 预取优化
OOM 率 >1% 增 MIN_BLOCK

高级：多级 freelist（small/medium/large bins），如 jemalloc 简化版；位图追踪空闲页。

回滚策略：双 arena 切换，测试覆盖 99% alloc/free 路径。

完整示例与基准

完整代码 < 500 行，可 GitHub 搜索 "simple slab allocator C"。基准：10^6 alloc/free，first-fit<1ms/MB。

资料来源：

  • GitHub t9nzin 用户项目（primary，arena-based allocator）。
  • 经典参考：Doug Lea dlmalloc 源码；Embedded Artistry 文章 "Custom Memory Allocation"。

（正文约 1200 字，聚焦单一技术：freelist 管理。）

查看归档