原文地址：https://techtalk.intersec.com/2013/10/memory-part-4-intersecs-custom-allocators/

# malloc()不是适用所有场景的分配器

malloc()由于其通用性而非常易于使用。它没有对分配和释放的上下文做任何的假设。 这样的分配器可以连续使用，也可以在一整个执行任务前后分开使用。它们可以用在同一个线程，也可以在多个线程。因为它很通用，每一次分配都是不同的，这意味着生存周期长的分配内存和生存周期短的分配内存都在一个内存池里。

这样导致malloc()的实现比较复杂。因为内存可以在多个线程之间共享，内存池也必须是共享的，并且必须要上锁。由于现代硬件有越来越多的物理线程（注，应该是指CPU的多核），每次分配都对内存池上锁会对性能有灾难性的影响。因此，现代的malloc()实现采用线程本地缓存，只有当本地缓存太大或太小的时候才会锁主内存池。这也导致一些内存驻留在线程本地缓存中，不容易被其他线程使用。

既然内存块驻留在不同的位置（线程本地缓存，全局内存池，或进程简单分配），堆会变得碎片化。未使用的内存则很难被释放回内核。并且有很大的可能，两次连续的分配，得到的内存离得很远。导致在堆上做随机访问。正如我们在前面的文章看到的，对内存随机访问的方式离最优方案还差的很远。

因此，有时候，行为可预测的特殊分配器是很有必要的。在Intersec，我们有好几个这样的分配器，分别用在不同场景下。在一些特定的用例中，我们可以提升几个数量级的性能。

# 性能测试

为了提供一些可对比的点，我们跑了一些自己写的性能测试。我们测试了malloc()和free()在两个场景的性能。第一个是简单场景：我们分配100万个指针，然后释放它们。我们使用单线程环境和小块的分配来测试原始的分配器。

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>struct list {struct list *next;
};static int64_t timeval_diffmsec(const struct timeval *tv2,const struct timeval *tv1)
{int64_t delta = tv2->tv_sec - tv1->tv_sec;return delta * 1000 + (tv2->tv_usec - tv1->tv_usec) / 1000;
}int main(int argc, char *argv[])
{for (int k = 0; k < 3; k++) {struct timeval start;struct timeval end;struct list *head = NULL;struct list *tail = NULL;/* Allocation */gettimeofday(&start, NULL);head = tail = malloc(sizeof(struct list));for (int i = 0; i < 100000000; i++) {tail->next = malloc(sizeof(struct list));tail = tail->next;}tail->next = NULL;gettimeofday(&end, NULL);printf("100,000,000 allocations in %ldms (%ld/s)\n",timeval_diffmsec(&end, &start),100000000UL * 1000 / timeval_diffmsec(&end, &start));/* Deallocation */gettimeofday(&start, NULL);while (head) {struct list *cur = head;head = head->next;free(cur);}gettimeofday(&end, NULL);printf("100,000,000 deallocations in %ldms (%ld/s)\n",timeval_diffmsec(&end, &start),100000000UL * 1000 / timeval_diffmsec(&end, &start));}return 0;
}

第二个场景增加了多线程：给我们的指针都分配完内存以后，我们开始在另一个线程释放它们，同时在主线程分配另外一批指针。这样，分配和释放分别在两个线程同时进行，分配池产生了竞争。

性能测试执行了三次：一次用ptmmalloc()（glibc的实现），另一次是用tcmalloc()（Google的实现），最后是用jemalloc()（FreeBSD实现在Linux上的移植版）。

结果的确依赖于malloc()的不同实现。没有竞争的情况下，ptmalloc()比tcmalloc()性能稍微好一点（但是花费了大得多的内存空间）。tcmalloc()在多线程环境表现好得多。

一批8字节指针包含100M个时，意味着要分配800MB（762MiB。注，原文这里用词比较注意，MB应该指以1000为计算单位，MiB则是以1024为计算单位)。因此在单线程的用例里，实际数据就是762MiB大小。我们可以看到tcmalloc在内存占用上优化的更好。不过奇怪的是，tcmalloc释放被分配更慢：释放速度无法和分配速度匹配，导致我们在多线程测试中增加线程数的时候，内存占用一直在增加。

性能测试用例是人为造的，只是用极其特别的用例对小块内存的分配进行压力测试。因此这不能作为一个绝对的证据证明多线程环境tcmalloc更快，而单线程环境ptmalloc更快。但是，测试说明了没有完美的malloc()实现，为你的用例选择正确的实现可能对总体性能有巨大的影响。

最后，但不是最不重要，测试告诉你，每秒只能做一两百万的内存分配/释放。这个数字看起来很大，但是如果你每秒要处理几十万的事件，每个事件要触发1个或多个分配，malloc()将会成为瓶颈。

# 栈分配器

在Intersec，第一个（当然也是用得最多的）自定义分配器是栈分配器。这是一个后进先出（LIFO）分配器，意思是分配和释放的顺序相反。它模仿了程序栈的行为，因为分配总是以帧为一组，释放也都是一次一帧。

## 内部实现

栈分配器是大舞台式的分配器。它分配非常巨大的块（block），然后分割为小的块（chunk）。

对于每一块（block），它追踪两个关键信息：

• 栈底
• 帧的分割

当一个分配被执行时，栈底增加请求的大小（加上对齐和溢出校验值canaries）。如果当前block不能分配请求的大小，那么就会分配另外一个block：分配器不会尝试去填充前一个block的空隙。

当一个帧被创建，前一个帧的开始位置被压入栈底。分配器总是知道当前帧的开始位置。这样，帧的移除非常快：分配器设置栈底为当前帧的开始位置，然后重新加载前一个帧的位置，并置为当前帧。另外，分配器会列出所有完全空闲的block，并释放它们。

释放一个帧是分期返还的常量时间，它不依赖于帧上分配的chunk数量，但是依赖于帧包含的block数量。一般block的大小可以放下好几个典型的帧，这样在大部分情况下，释放一个帧不需要释放任何block。

通常分配和释放是一个严格的顺序，两次连续的分配会返回连续的内存chunk（除非新的分配请求需要一个新的区块）。这会提升程序内存的局部性访问。更进一步，多亏了顺序分配，栈分配器里几乎没有碎片。因此，当实际分配的内存都这样做时，栈分配器的压力会下降。

## t_stack

我们的确有一个特殊的栈分配器：t_stack。这是一个线程本地单实例的栈分配器。它被用作普通程序栈的补充。t_stack的主要优势是可以动态高效的分配临时内存。物理什么时候，我们想在函数内分配内存，在函数结束时释放它们，我们都使用基于t_stack的分配。

t_stack上帧的创建和释放是绑定在函数范围的。一个特别的宏定义t_scope用在词法范围的开头。这个宏利用GNU的cleanup属性在C中模拟C++的RAII行为：它创建了某个帧，并且并且增加一个清除句柄，这样无论什么时候退出其定义所在的词法范围，该帧都护被销毁。

static inline void t_scope_cleanup(const void **frame_ptr)
{if (unlikely(*unused != mem_stack_pop(&t_pool_g))) {e_panic("unbalanced t_stack");}
}#define t_scope__(n)  \const void *t_scope_##n __attribute__((unused,cleanup(t_scope_cleanup))) \= mem_stack_push(&t_pool_g)#define t_scope_(n)  t_scope__(n)
#define t_scope      t_scope_(__LINE__)

既然帧的分配和释放是开发者控制的，t_stack比普通的栈更灵活。有些行为在栈上是危险的，或者也做不到。比如在一个循环内做分配，或者返回一个t_stack分配的内存。但是用t_stack就很安全。另外，由于没有大小限制（除了实际可用物理内存大小），t_stack可以用于一般性的分配目的，只要内存的生存周期和帧的分配计划相一致。

用t_stack分配内存而不带t_scope声明很明显是跟普通程序栈的行为相悖的。对普通程序栈来说，函数不能给栈带来副作用：当函数退出时，它要把栈恢复到函数开始调用的时候。为了减小混乱，我们使用一个编码约定：当一个函数会对t_stack有副作用时（也就是它可以在它的调用者创建的帧上进行分配），它的名称必须带一个“t_”前缀。这样就比较容易的检测到缺失的t_scope：如果一个函数使用了t_stack提供的函数，但是没有包含t_scope，那么要么它的名称有“t_”前缀，要么就是疏忽了声明t_scope。

t_stack另外一个优点是，跟堆分配器相比，它经常（但不总是）让错误管理更简单。由于释放是在t_scope的结尾处自动进行的，在出错的时候也不需要加额外的处理。

/* Error handling with heap-allocated memory.*/
int process_data_heap(int len)
{/* We need a variable to remember the result. */int ret;/* We will need to deallocate memory, so we have to keep the* pointer in a variable.*/byte *data = (byte *)malloc(len * sizeof(byte));ret = do_something(data, len);free(data);return ret;
}/* Error handling with t_stack-allocated memory.*/
int process_data_t_stack(int len)
{/* Associate the function scope to a t_stack frame.* That way all `t_stack`-allocated memory within the* function will be released at exit*/t_scope;return do_something(t_new(byte, len), len);
}

t_stack的另一个作用是，很多堆上的短期分配可以在t_stack上分配了。这减少了堆的碎片。而且t_stack是线程本地的，不需要处理竞争。

t_stack依赖于一些非标准的C扩展，对于Intersec的一些新人来说有些不可思议。但是在Intersec它的确是对语言提供的标准库之外一个很好的补充。

## 性能测试

我们对栈分配器做了性能测试：

正如你看到的，这个分配器很快：它比ptmalloc和tcmalloc的最优情况更好。多亏帧机制，释放完全不依赖于分配（测试代码可以改善一下，测算帧的创建和销毁性能）。

栈分配器的当前实现用__BIGGEST_ALIGNMENT__来做最小分配对齐。这是一个平台相关的常量，表示CPU的最大对齐要求。在x86_64上，这个常量是16字节，因为一些操作16字节数组的指令（例如SSE指令）要求按16字节对齐。这解释了为什么内存占用是最优情况的两倍。

# 先进先出分配器（FIFO）

## 先进先出问题

另一个经常用到的内存用法是先进先出（FIFO）管道：内存的释放顺序跟分配顺序（近似的）一致。一个典型的用例是在网络协议的实现中缓冲请求的上下文：当一个请求被发出并释放，以及收到响应时，每一个请求都要关联到一个已分配的上下文。大部分情况下，请求被以发出的顺序处理（这不总是正确的，但是即使有个别处理时间很长的请求，对于这类处理来说，也只是很短的时间）。

当先进先出数据在堆上直接分配时，它会放大碎片问题，因为下一个释放的chunk很可能不在堆的末端，这样就会产生一个空洞（并且由于堆上不仅有先进先出数据，还有其他分配可能夹杂在两个先进先出的分配之间，情况会变得更糟）。

## 解决方案

因为这些原因，我们觉得把这种使用模式跟其他的分配方式独立开来。我们使用自定义的分配器来取代堆分配器。

这个分配器基本上跟栈分配器工作方式相同：它内部存放被线性使用的巨大的block（新的block只有在当前block无法满足下一次分配时才会被创建）。没有使用帧的模型，先进先出分配器使用计算每个block大小的机制。每一个block维护它内部分配的内存。当block内所有的数据都被释放时，它自己也被释放。block使用mmap来分配，以免干扰到堆（因此也不会产生碎片）。

因为先进先出分配器使用跟栈分配器一样的分配模式（但不是一样的释放模式），它也有一些一样的属性。其中之一是，连续的分配得到的地址也是连续的。但是由于先进先出分配器的使用模式，这里局部性带来的好处并不重要：大部分时间，它被用来分配独立的元素，这些元素几乎不会一起使用。

先进先出分配器被设计为在单线程环境中使用，因此不需要处理竞争的问题。

## 性能测试

我们使用先进先出分配器来运行我们的无竞争版性能测试，这样可以和malloc来比较性能：

跟栈分配器一样，先进先出分配器的性能比malloc实现更好。但是比栈分配器慢一点点，这是因为它要单独追踪每个分配的信息，因此没有想栈分配器一样优化。

## 循环分配器

循环分配器是栈分配器和先进先出分配器的混合。它使用帧来给内存分配分组，可以在常量时间释放一大批的分配，尽管它大部分是先进先出的使用模式。循环分配器中的帧不是堆叠的，每个堆是独立且自包含的。

为了在循环分配器上分配内存，首先要创建一个新的帧。这要求之前的帧已经封闭。当一个帧在分配器中被打开，就可以进行分配，并且自动成为活动帧的一部分。当所有的分配都完成，帧必须被封起来。一个封闭的帧仍然是活跃的，这意味着它包含的分配仍然是可以访问的，只是帧不能再进行新的分配。当帧不再被需要时，必须被释放。

在帧分配器中释放内存是线程安全的。这使得这个分配器在工作线程中构造用于传输的消息非常有用。在那个上下文中，它几乎可以在那些需要处理多线程的代码中直接替换t_stack来工作。

/* Single threaded version, use t_stack.*/
void do_job(void)
{t_scope;job_ctx_t *ctx = t_new(job_ctx_t, 1);run_job(ctx);
}/* Multi-threaded version, using ring allocation.* Note that it uses Apple's block extension.*/
void do_job(void)
{const void *frame = r_newframe();job_ctx_t *ctx = r_new(job_ctx_t, 1);r_seal();thr_schedule(^{run_job(ctx);r_release(frame);});
}

这个用例里，帧基本上是按照先进先出的方式使用。

我们使用这个分配器再次运行基准测试。由于环形分配器是线程安全的，基准测试覆盖了有竞争和无竞争的用例：

## 其他自定义分配器

本文介绍了Intersec使用的三种自定义分配器。这三个分配器不适用于一般的用途：它们是为了特别的使用模式而优化的。幸运的是，在大部分情况下，这三个分配器的组合使用足够让我们避开我们碰到的跟malloc有关的问题，比如缺乏局部性，分配时的锁竞争和堆碎片。

然而，有些时候没有办法，我们没有其他选择，必须实现一个自定义通用内存分配器来满足我们的性能要求。因此，我们也有一个基于TLSF (Two Level Segregate Fit)的分配器。TLSF是被设计来做实时处理的分配算法，它保证操作是常数时间（分配和释放都是）。

还有更多有趣的，我们也有页分配器和持久化分配器。最后一个我们可能会在以后的文章讲到。