C 语言中的 Arena 分配器
一个 C 语言里的小型 arena 分配器全解：从它解决的生命周期问题，到可运行实现的结构体、内存对齐和 realloc 路径。
中文
复制
众所周知，C 是一门非常底层的语言。它允许你（某种程度上也是强迫你）自己管理所使用的内存。这大概也是很多人日常编程时转向其他语言的原因之一。本文将介绍一种内存管理范式，它不仅性能极高，而且极其灵活。它让内存管理这件事轻松不少，也大幅降低了内存泄漏的概率。
你也许已经听说过它，也许没有，无论如何：我说的就是 arena 分配器。
接下来我会讲实现，但在此之前，先简要介绍一下 arena 分配器的概念。
什么是 Arena 分配器？
人们通常管理内存的方式是：每次需要内存时，就用 malloc 从堆上分配一小块——只分配需要的量。如果后来发现需要的内存比最初计划的多，就用 realloc 扩大已分配内存的大小。
用完之后，调用 free 告诉操作系统这块内存不再需要，可以挪作他用。
这很好，但有几个问题：
1.
程序员必须记得在用完内存后释放它。如果分配发生在循环里——比如游戏中——这就尤其危险，因为这种情况下操作系统会不断分配越来越多的内存，而这些内存永远不会被释放。
内存作为一种资源并非无限。到了某个时刻，你的计算机会耗尽内存，程序会被操作系统终止（也就是崩溃）。
2.
分配和释放大量小块内存很慢。
3.
如果你有这样一个函数：
i32 *create_array(usize len) {
i32 *elements = (i32 *)malloc(sizeof(int));
return elements;
}
那么请告诉我：调用这个函数的程序员怎么知道它内部做了内存分配？在这个例子里，或许可以靠函数名去猜它可能在做什么，但事情并不总是这么简单。
记住，这一点很重要，因为程序员需要知道什么时候该释放内存。
必须让程序员意识到：释放内存是他自己的责任。
可能还有更多我没考虑到的问题，但以上是我当场能想到的一些主要问题。
解决方案。
登场吧，arena allocator。
大多数生命周期（也就是某块内存在被释放之前会被使用多久）都可以归入少数几类：
- 内存的生命周期与整个程序相同
- 内存的生命周期持续到某些任务完成（比如游戏中的一帧，或一次 HTTP 请求的处理）
- 内存的生命周期仅限于某个函数的作用域
这样的分组通常够用了，但取决于你如何划分，可能还会有更多类别。无论如何，我们都可以直接分配一大块内存，用来处理生命周期相近的东西（也就是可以一起释放的东西）。
这样我们就拥有了一大块可用的内存。每当我们用掉其中一部分来做某件事，就推进一个指针，记住内存已经用到了哪里、空闲内存从哪里开始。
看到实现之后，这一点会更清楚。
当我们不再需要那块大内存中的任何数据时，可以直接一次性全部释放（或者——如果我们想复用这块内存——就把 memory arena 重新初始化到初始状态，从头开始分配）。
这省去了一次次单独的内存分配（记住，这些操作很慢），也让我们不必太操心内存管理，因为只需要关注几块不同的内存“块”，而不是为各个数组使用的一堆小块内存。
实现
说明
在开始之前，我用 C 的时候几乎总会在代码顶部包含这个文件。
它只是给一些内置类型 typedef，并提供了一些常用、实用的工具。我会直接包含 .c 文件，因为我用 unity build 来加快编译速度。
你完全可以自己写头文件，如果你更倾向那样做的话。
// types.c
#ifndef TYPES_C
#define TYPES_C
#include <stddef.h>
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef float f32;
typedef double f64;
typedef size_t usize;
#define KiB(x) x * 1024
#define MiB(x) KiB(x) * 1024
#define GiB(x) MiB(x) * 1024
#define MIN(a, b) a < b ? a : b
#define MAX(a, b) a > b ? a : b
#endif // TYPES_C
arena.c
下面是 arena 的实际实现。
开头是 include guard（同样是因为 unity build），再引入几个要用到的 libc 头文件：
#ifndef ARENA_C
#define ARENA_C
#include "types.c"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
// code goes here
#endif // ARENA_C
这是 arena 结构体的定义：
struct arena {
void *data;
usize size;
usize used;
};
它记录了已用掉多少内存。也可以用另一个办法达到同样目的：用一个指针指向内存中尚未使用区域的起点。
size 字段的作用是判断分配时是否会超出 arena 的容量（内存用多了，这种情况很容易发生）。
data 则直接指向 arena 的起始位置。
到这里一切顺利，但接下来需要一个创建新 arena 的方法。如下：
struct arena_create_out {
struct arena arena;
bool success;
};
[[nodiscard]]
struct arena_create_out arena_create(usize size) {
struct arena_create_out out = {0};
out.arena.data = malloc(size);
if (out.arena.data == NULL)
return out;
out.arena.size = size;
out.arena.used = 0;
out.success = true;
return out;
}
返回多个值时，我不喜欢用输出参数——我觉得那样很绕，API 也不直观——更愿意直接返回结构体。
接着需要一个在 arena 里分配内存的方法。在此之前，先定义这个宏（我把它放在文件顶部，但到这里才真正用得上，所以现在才介绍）：
#define ARENA_ALIGN 8
它用来对齐数据。不知为何，我们的计算机处理按 8 字节对齐的数据要高效得多。也就是说，每次新分配的起始位置必须是 8 的倍数。
malloc 会替我们处理这件事，但现在我们不是用 malloc 来分配，而只是在一块已经分配好的内存里划出一部分空间，所以必须自己对齐数据，以加快访问速度。
下面是分配函数：
struct arena_alloc_out {
void *ptr;
bool success;
};
[[nodiscard]]
struct arena_alloc_out arena_alloc(struct arena *arena, usize size) {
struct arena_alloc_out out = {0};
usize alignment = (ARENA_ALIGN - (arena->used % ARENA_ALIGN)) % ARENA_ALIGN;
out.ptr = arena->data + arena->used + alignment;
if (out.ptr + size > arena->data + arena->size)
return out;
arena->used += size + alignment;
out.success = true;
return out;
}
这里我们要算出需要在分配末尾补上多少“填充”（即 alignment 变量），才能让下一次分配对齐到 8 字节。
我习惯在函数返回类型里放一个 success 字段，出错时直接提前返回（因为它被 = {0} 初始化为全零，所以 success 会是 false）。
如果你不喜欢这种做法，把 API 改成别的约定应该不难。
大部分工作已经完成。我写了一个简单的包装函数来改变分配的大小：在 arena 末尾按新大小分配一块内存，再把数据复制过去。旧数据原样保留，等 arena 释放时一并释放（记住，我们无法单独释放某次分配，要么释放整个 arena，要么什么都不释放）。
你其实不需要它，但我发现它让我的代码更干净，所以放上来：
struct arena_realloc_out {
void *ptr;
bool success;
};
[[nodiscard]]
struct arena_realloc_out arena_realloc(struct arena *arena, usize new_size, void *src, usize old_size) {
struct arena_realloc_out out = {0};
struct arena_alloc_out alloc_out = arena_alloc(arena, new_size);
if (!alloc_out.success)
return out;
out.ptr = memcpy(alloc_out.ptr, src, MIN(old_size, new_size));
out.success = true;
return out;
}
如果新大小比旧大小更小，末尾那部分数据会被截掉。另外，realloc 内部知道每个指针所对应的分配大小，所以你不必传旧大小，只传新大小即可。
由于我们的 arena 实现完全不记录分配的大小，我们只能把旧大小单独传给这个函数。arena 的使用者应当自己清楚每次分配的大小。
这一点也可以实现，但我想保持简单。
接下来两个函数是小型包装，只是为了方便，并非必需：
void arena_clear(struct arena *arena) { arena->used = 0; }
void arena_free(struct arena *arena) { free(arena->data); }
我的实现就到这里。
用法示例
我有一个简单的字符串库，是为自己的使用场景写的。它有两个概念：string view 和 owned string。
owned string 以 NUL 结尾，并且 owns 它的数据（也就是说，必须分配和释放）。这也意味着可以直接修改 owned string。
string view 只是查看数据，因此不能直接修改它——同一份数据可能存在多个 string view，修改它会导致其他字符串发生意料之外的变化。反过来，任何一块数据区域都只应存在一个 owned string。
关键在于，我需要一种把 string view 转换成 owned string 的方法。为此，我们必须新建一个 owned string（也就是为它分配内存），再把数据复制过去。这同样是为了确保对这个 owned string 的修改不会影响到其他可能正在查看它的 string view。
我们还会在自有字符串末尾加上 NUL 终止符（以兼容其他遗留 C API）。
为此，我们向函数传入一个 arena 分配器，并从该 arena 分配内存：
struct str_view {
const u8 *data;
usize len;
};
struct str_owned {
u8 *data;
usize len;
};
struct str_view_to_str_owned_out {
struct str_owned str;
bool success;
};
[[nodiscard]]
struct str_view_to_str_owned_out str_view_to_str_owned(
struct arena *arena,
struct str_view s
) {
struct str_view_to_str_owned_out out = {0};
struct arena_alloc_out alloc_out = arena_alloc(arena, s.len + 1);
if (!alloc_out.success)
return out;
out.str.data = alloc_out.ptr;
memcpy(out.str.data, s.data, s.len);
out.str.len = s.len;
out.str.data[out.str.len] = 0;
out.success = true;
return out;
}
这带来两个好处：
- 调用方立刻就能知道这个函数会分配内存（因为它的第一个参数就是 arena 指针）
- 调用方可以决定在哪里分配内存（也就是以什么生命周期分配）。
关于第 2 点，既然调用方通过传入相应的 arena 来决定生命周期，就不必操心直接释放内存——生命周期结束、arena 被丢弃（或清空）时，内存自然就释放了。这个时机可以是程序结束时（这种情况下释放内存根本没必要，操作系统会替我们处理），也可以是函数结束时，或者调用方确信不再需要这块内存的任何时候。
结语
我最近开始把 arena 纳入自己的编程习惯，不得不说效果让我非常满意。我已经把自己的字符串库迁移到 arena 上，我觉得你用 arena 也能获益不少。
开发者体验的提升有时大有时小，但可以说，作为程序员，把这一工具收入囊中绝对是净收益。
我并不自称专家，这个实现也只是我自己为个人使用而写的。它未必完美，但作为入门介绍应该够用了。
一如既往，有任何问题、反馈或想法，都可以通过邮件联系我：