C 语言实现自定义内存分配器：从 ptmalloc 原理到高性能 Allocator 设计

引言

内存分配器是 C/C++ 程序性能的关键瓶颈之一。标准库的 malloc/free 虽然通用，但在特定场景下性能堪忧。理解内存分配器的工作原理，并针对特定场景设计自定义分配器，是系统程序员的核心技能之一。

本文将深入剖析 ptmalloc 的设计思想，然后从零实现三种经典的自定义内存分配器，并通过基准测试对比它们的性能差异。

1. 标准 malloc 的工作原理

1.1 内存布局基础

在深入分配器之前，需要理解进程的内存布局。Linux 进程通过 brk/sbrk 系统调用扩展数据段，或通过 mmap 映射匿名内存区域。

// 通过 brk 扩展数据段（小块内存）
void *brk(void *addr);

// 通过 mmap 映射匿名内存（大块内存）
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

// 判断阈值：M_MMAP_THRESHOLD，默认 128KB
// 小于阈值用 brk，大于等于阈值用 mmap

1.2 ptmalloc 的 Chunk 结构

ptmalloc（pthreads malloc）是 glibc 默认的分配器，其核心数据结构是 chunk：

struct malloc_chunk {
    size_t mchunk_prev_size;  /* 前一个空闲 chunk 的大小（如果前一个已空闲） */
    size_t mchunk_size;       /* 当前 chunk 的大小（含元数据，低位为标志位） */
    struct malloc_chunk *fd;  /* 双向链表指针：指向前一个空闲 chunk */
    struct malloc_chunk *bk;  /* 双向链表指针：指向后一个空闲 chunk */
};

/* chunk 大小字段的标志位 */
#define PREV_INUSE 0x1  /* 前一个 chunk 是否正在使用 */
#define IS_MMAPPED 0x2  /* 当前 chunk 是否通过 mmap 分配 */
#define NON_MAIN_ARENA 0x4  /* 是否属于非主分配区 */

关键设计要点：

• 对齐：chunk 大小按 2 * sizeof(size_t) 对齐（64 位系统为 16 字节）
• 边界标记：通过当前 chunk 的大小字段可快速定位下一个 chunk，通过 prev_size 定位前一个
• 空闲链表：按大小分桶（small bins、large bins、unsorted bin）
• 多 arena：支持多线程并发分配，减少锁竞争

1.3 malloc 分配流程

一次 malloc(size) 调用经历以下步骤：

1. 根据请求大小计算所需 chunk 大小（含元数据 + 对齐）
2. 检查对应大小的 fast bin（LIFO 单链表，<= 128 字节常用大小）
3. 检查 small bin（精确匹配的双向链表）
4. 检查 unsorted bin（刚从 free 返回的 chunk，按大小插入 large bin）
5. 遍历 large bin（按大小降序排列的二叉树）
6. 都没有合适的，从 top chunk 切割
7. top chunk 也不够大，扩展堆或 mmap 新区域

2. 自定义分配器实现

2.1 栈式分配器（Stack Allocator / Bump Allocator）

最简单的分配器——一个指针从头用到尾，不支持 free，适合帧内存或短生命周期对象。

#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <sys/mman.h>

typedef struct {
    uint8_t *buffer;
    size_t capacity;
    size_t offset;
    size_t high_water_mark;
} StackAllocator;

int stack_init(StackAllocator *a, size_t capacity) {
    a->buffer = mmap(NULL, capacity, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (a->buffer == MAP_FAILED) return -1;
    a->capacity = capacity;
    a->offset = 0;
    a->high_water_mark = 0;
    return 0;
}

void *stack_alloc(StackAllocator *a, size_t size, size_t alignment) {
    size_t aligned = (a->offset + alignment - 1) & ~(alignment - 1);
    if (aligned + size > a->capacity) return NULL;
    void *ptr = a->buffer + aligned;
    a->offset = aligned + size;
    if (a->offset > a->high_water_mark)
        a->high_water_mark = a->offset;
    return ptr;
}

void stack_free(StackAllocator *a, void *ptr) {
    (void)a; (void)ptr;
}

void stack_reset(StackAllocator *a) {
    a->offset = 0;
}

void stack_pop(StackAllocator *a, void *Marker) {
    size_t marker_offset = (uint8_t *)marker - a->buffer;
    if (marker_offset <= a->capacity) {
        a->offset = marker_offset;
    }
}

void stack_destroy(StackAllocator *a) {
    munmap(a->buffer, a->capacity);
}

性能分析：stack_alloc 只需一次对齐计算和指针递增，单 alloc 1-3 个 CPU 指令，是理论上最快的分配器。缺点是不能单独释放对象。

2.2 池式分配器（Pool Allocator / Fixed-size Allocator）

固定大小对象的专用分配器，广泛用于游戏引擎、网络服务器中的消息包、连接对象等。

#include <stdint.h>
#include <assert.h>

typedef union FreeNode {
    union FreeNode *next;
    char data[1];
} FreeNode;

typedef struct {
    uint8_t *buffer;
    FreeNode *free_list;
    size_t slot_size;
    size_t capacity;
    size_t used;
} PoolAllocator;

int pool_init(PoolAllocator *p, size_t slot_size, size_t count) {
    if (slot_size < sizeof(FreeNode *))
        slot_size = sizeof(FreeNode *);
    slot_size = (slot_size + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
    p->slot_size = slot_size;
    p->capacity = count;
    p->used = 0;
    p->buffer = mmap(NULL, slot_size * count, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (p->buffer == MAP_FAILED) return -1;
    p->free_list = NULL;
    for (size_t i = 0; i < count; i++) {
        FreeNode *node = (FreeNode *)(p->buffer + i * slot_size);
        node->next = p->free_list;
        p->free_list = node;
    }
    return 0;
}

void *pool_alloc(PoolAllocator *p) {
    if (!p->free_list) return NULL;
    FreeNode *node = p->free_list;
    p->free_list = node->next;
    p->used++;
    memset(node, 0, p->slot_size);
    return node->data;
}

void pool_free(PoolAllocator *p, void *ptr) {
    uint8_t *raw = (uint8_t *)ptr;
    FreeNode *node = (FreeNode *)raw;
    node->next = p->free_list;
    p->free_list = node;
    p->used--;
}

void pool_destroy(PoolAllocator *p) {
    munmap(p->buffer, p->slot_size * p->capacity);
}

性能分析：alloc/free 都是 O(1)，无碎片、无锁、无系统调用。相比 malloc 每次可能需要 200-500 个 CPU 周期，池分配器只需 5-15 个周期。

2.3 伙伴系统分配器（Buddy Allocator）

伙伴系统是操作系统内核中管理物理页的经典算法，通过递归二分实现高效分配与合并，完美契合 mmap/munmap 的页级管理。

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

#define MIN_ORDER 4
#define MAX_ORDER 20
#define MAX_ORDERS (MAX_ORDER - MIN_ORDER + 1)

typedef struct FreeList {
    struct FreeList *next;
    struct FreeList *prev;
} FreeList;

typedef struct {
    FreeList orders[MAX_ORDERS];
    uint8_t *buffer;
    size_t total_size;
} BuddyAllocator;

void buddy_init(BuddyAllocator *b, void *buffer, size_t size) {
    b->buffer = (uint8_t *)buffer;
    b->total_size = size;
    for (int i = 0; i < MAX_ORDERS; i++) {
        b->orders[i].next = &b->orders[i];
        b->orders[i].prev = &b->orders[i];
    }
    int order = MAX_ORDER;
    while ((1UL << order) > size && order > MIN_ORDER)
        order--;
    FreeList *block = (FreeList *)b->buffer;
    block->next = &b->orders[order - MIN_ORDER];
    block->prev = &b->orders[order - MIN_ORDER];
    b->orders[order - MIN_ORDER].next = block;
    b->orders[order - MIN_ORDER].prev = block;
}

static void list_remove(FreeList *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

static void list_push(FreeList *head, FreeList *node) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

static inline uintptr_t buddy_address(uintptr_t addr, int order) {
    return addr ^ (1UL << order);
}

void *buddy_alloc(BuddyAllocator *b, size_t size) {
    int order = MIN_ORDER;
    while ((1UL << order) < size + sizeof(FreeList))
        order++;
    if (order > MAX_ORDER) return NULL;
    int found = -1;
    for (int i = order - MIN_ORDER; i < MAX_ORDERS; i++) {
        if (b->orders[i].next != &b->orders[i]) {
            found = i;
            break;
        }
    }
    if (found == -1) return NULL;
    while (found > order - MIN_ORDER) {
        FreeList *block = b->orders[found].next;
        list_remove(block);
        uintptr_t addr = (uintptr_t)block;
        uintptr_t buddy = buddy_address(addr, found + MIN_ORDER - 1);
        list_push(&b->orders[found - 1], block);
        list_push(&b->orders[found - 1], (FreeList *)buddy);
        found--;
    }
    FreeList *result = b->orders[found].next;
    list_remove(result);
    return result;
}

伙伴系统的核心优势是合并：释放块时自动与伙伴（相邻对齐的等大小块）合并成更大的块，减少了外部碎片。缺点是内部碎片较大（最多浪费 50%），适合页级管理。

3. 实战应用场景与性能对比

3.1 性能基准测试

分配 100 万个 64 字节对象并全部释放的性能对比（Release 模式，Intel i7-10700）：

结果非常直观：栈分配器 227 倍快于标准 malloc，池分配器约 22 倍。这些差异在高频小对象分配场景（游戏帧、网络包、粒子系统）中会产生巨大的累积效应。

3.2 游戏引擎帧分配器

游戏引擎中经典的双缓冲帧分配器——每帧开始时重置，所有临时对象从栈分配器分配：

typedef struct {
    StackAllocator alloc;
    void *frame_marker;
} GameFrameAllocator;

void game_frame_begin(GameFrameAllocator *gfa) {
    stack_reset(&gfa->alloc);
}

void *game_frame_alloc(GameFrameAllocator *gfa, size_t size) {
    return stack_alloc(&gfa->alloc, size, 16);
}

3.3 网络服务器连接池

高并发服务器（如 Redis、Nginx）中，连接对象的大小固定且可预测，完美的池分配器场景：

PoolAllocator conn_pool;

void server_init(void) {
    pool_init(&conn_pool, sizeof(Connection), 10000);
}

Connection *accept_connection(void) {
    Connection *c = pool_alloc(&conn_pool);
    if (!c) return NULL;
    c->fd = accept(server_fd, NULL, NULL);
    c->state = CONN_READING_HEADER;
    return c;
}

void close_connection(Connection *c) {
    close(c->fd);
    pool_free(&conn_pool, c);
}

3.4 伙伴系统用于页级缓存

自己实现的内存数据库或文件缓存系统，可以用伙伴系统管理内存块：

BuddyAllocator page_cache;

void db_cache_init(void) {
    void *mem = mmap(NULL, 1024 * 1024 * 1024, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    buddy_init(&page_cache, mem, 1024 * 1024 * 1024);
}

void *db_fetch_results(DB *db, Query *q) {
    void *page = buddy_alloc(&page_cache, 64 * 1024);
    if (!page) {
        page = evict_and_alloc(&page_cache, 64 * 1024);
    }
    execute_query_into(q, page);
    return page;
}

4. 调试与检测工具

4.1 使用 mprotect 检测 use-after-free

释放后将内存页设为不可访问，触发 SIGSEGV 即可捕获野指针：

#include <signal.h>
#include <ucontext.h>

#define PAGE_SIZE 4096

void guarded_free(void *ptr, size_t size) {
    uintptr_t start = (uintptr_t)ptr & ~(PAGE_SIZE - 1);
    size_t pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
    for (size_t i = 0; i < pages; i++) {
        mprotect((void *)(start + i * PAGE_SIZE), PAGE_SIZE, PROT_READ);
    }
}

void sigsegv_handler(int sig, siginfo_t *info, void *context) {
    fprintf(stderr, "[GUARD] Segfault at %p (use-after-free detected)\n", info->si_addr);
    print_stacktrace();
    abort();
}

4.2 统计碎片率

typedef struct {
    size_t total_allocated;
    size_t total_requested;
    size_t alloc_count;
    size_t free_count;
    size_t max_contiguous;
} AllocatorStats;

double fragmentation_ratio(AllocatorStats *stats) {
    if (stats->total_allocated == 0) return 0.0;
    return 1.0 - (double)stats->total_requested / stats->total_allocated;
}

5. 总结

内存分配器的选择遵循相同的工程原则：先测量，再优化。在绝大多数场景下，glibc malloc 或 jemalloc 已经足够好。但当你面临每秒数百万次小对象分配、硬实时要求或嵌入式环境时，自定义分配器就是不可或缺的武器。理解它们的原理，让我们在最需要的时候能做出正确的选择。