Intersec内存系列文章–第4部分：Intersec自定义分配器

malloc()并不是一个适用于所有场合的分配器

malloc()因其通用性使用起来非常方便。它不会对分配和释放内存的情境做任何假设。内存的申请/释放可以是连续的，也可以在整个任务执行中分开，既能发生在同一线程中，也可以在不同线程中。分配器的通用性使得每次分配互不相同，这意味着不同生命周期的内存会共享相同的内存池。

因此malloc()的实现很复杂。由于内存可以被多个线程共享，所以内存池也必须共享，并且分配过程中需要加锁。同时现在硬件支持越来越多的物理线程，因此每次内存分配时的加锁会对性能造成极大影响。也正是因为如此，目前的malloc()实现拥有线程本地缓存，只有当缓存过小或过大时才会锁内存池。（译者注：过小时，需要向内存池请求资源，过大时会被垃圾回收机制回收到内存池）它的副作用就是，一些内存在线程本地缓存中，其他线程无法轻易访问。

由于内存块可以在不同的地方（线程本地缓存，全局内存池，或者只是简单地分配给进程），堆会变得碎片化。这将难以把未使用的内存释放回内核，并极有可能导致两次连续的分配，却返回相距甚远的内存，导致对堆的随机访问。在上一篇文章中我们看到，随机访问绝不是内存访问的最佳方案。（译者注：无法利用内存的局部性）

因此，拥有一个能预测其行为的专用分配器在某些情况下确实是必须的。在Intersec，不同的情境下我们使用不同的分配器。在一些特定的使用场合，它能提高几个数量级的性能。

性能测试

为了提供对比数据，我们做了一个小的基准测试。它在两种场景下测试malloc()和free()的性能。第一个场景很简单：我们分配1亿个指针，然后释放它们。通过单线程环境下小块内存的分配，来测试分配器的基本性能。

#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;
}

第二个场景增加了多线程因素：分配完所有的指针后，我们开始在另一个线程中释放它们，与此同时在主线程中分配新一批的指针。这样分配和释放同时在两个不同的线程运行，导致对内存池的竞争。

测试程序运行了三次：分别采用了glibc的ptmalloc 、谷歌的tcmalloc和jemalloc（Linux对FreeBSD实现的移植）。

场景		分配	释放	占用内存	时间
无竞争	PTMALLOC	1512ms(66M/s)	1261ms(79M/s)	2.9GiB	9.98s
	TCMALLOC	1712ms（58M/s)	2229ms(44M/s)	769MiB	12.10s
	JEMALLOC	3312ms(30M/s)	4191ms(23M/s)	784MiB	22.55s
竞争	PTMALLOC	16154ms(6.2M /s)	15309ms(6.3M/s)	2.9GiB	39.18s
	TCMALLOC	2860ms(34M/s)	6707ms(14M/s)	1.7GiB	14.62s
	JEMALLOC	3845ms(26M/s)	11672ms(8.5M/s)	2.3GiB	23.55s

事实上，测试结果极大地依赖malloc()实现。在非竞争场景中，ptmalloc（占用更大的内存）比tcmalloc 性能稍好，不过在多线程场景中tcmalloc表现更好。

每次批量分配100M的8字节指针，这意味着它分配了800MB（762MiB）内存。因此，在单线程场景中，载荷会占762MiB内存。我们可以看到在内存消耗方面tcmalloc是接近最优的。然而，奇怪的是tcmalloc的释放慢于分配：线程释放内存无法像分配时那么快，如果我们增加测试中的线程数量将导致逐渐增长的内存占用。

上述测试过程是在极其特定的使用情景下，模拟进行了小块内存分配性能的压力测试。因此，它不能绝对证明tcmalloc在多线程环境下更快，而ptmalloc在单线程场景下更快。不过测试表明：虽然没有完美的malloc()实现，但结合使用场景，选择合适的实现可能对整体性能有巨大提升。

最后，同样重要的是，测试表明每秒可以执行的分配/释放数只有几百万。这看起来可能相当大了，可一旦你想每秒处理成千上万的事件，并且如果每一个事件会触发一个或多个分配，那么malloc()将成为性能瓶颈。

栈分配器

在Intersec，最先使用的（当然也是最常用的）自定义分配器是栈分配器。它是一个LIFO分配器，这意味着内存释放的顺序与它们分配的的顺序相反。（译者注：LIFO: Last In First Out）它模仿程序的栈行为，分配的块被组织为一个个帧，并且帧可以被立即释放。

内部实现

栈分配器是基于arena的分配器。它申请大块的内存，然后分割成小块来使用。

对于每一块，它跟踪记录两个关键信息：

o 栈底

o 帧界限

进行分配时，栈底会以所请求内存大小来增长（要加上对齐的要求，和记录信息的大小）。如果在当前块中找不到适合的请求大小，则会分配一个新块：不会尝试使用前面块的空留部分。

当帧被创建时，记录前一帧起始位置的标记被压到栈底。分配器总能知道当前帧的起始位置。这样一来，删除帧非常快：分配器设置栈底为当前帧的位置，然后重新加载前一帧的位置将它设置为当前帧。此外，分配器将列出删除帧后完全空闲的块，并释放它们。

帧的释放可以在常量时间内完成，它不依赖于帧中内存分配的数量，而是帧中块的数量。块大小会设定得足够大以包含一些典型帧，这意味着大部分时候释放帧并不会释放任何块。

由于分配和释放有严格的顺序，两个连续的分配将返回相邻的内存块（除非新的分配需要一个新的arena）。这有助于改善程序内存访问的局部性。此外，由于分配/释放顺序，在栈分配器中很少有碎片。因此，当实际是这样分配内存时，栈分配器的内存压力就会减小。

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则是安全的。此外，由于没有大小限制（当然不能超过可用的RAM），t_stack可用于一般用途的分配，只要内存的生命周期与帧的分配方案兼容。

在函数中不申明t_scope却分配t_stack内存明显违背了正常栈的行为。对于标准的程序栈，函数在栈上不能有副作用：当退出函数时，它的栈状态恢复为函数执行前。为了减少混乱，我们使用如下编码约定：当函数对t_stack带来副作用时（也就是说，它会在其调用者的一个帧中分配内存），其命名必须带有前缀t_。这样一来，很容易检测漏掉t_scope的情况：如果函数调用t_开头的函数，但不包含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它肯定是除标准库外最好的库之一。

性能测试

我们对栈分配器进行测试：

场景	分配	释放	占用内存	时间
无竞争	833ms(120M/s)	0ms	1.5GiB	2.99s

正如你所看到的，分配器速度很快：它优于ptmalloc和tcmalloc的最佳性能。得益于帧机制，释放完全不依赖于分配数（可以改进测试以测量帧的创建/销毁性能）。

栈分配器的当前实现有一个最小分配对齐__BIGGEST_ALIGNMENT__ ，它是一个依赖于平台的常数，表示CPU规定的的最大对齐要求。在x86_64系统中，该常数设置为16字节，因为一些指令（如SSE指令）操作要求16字节对齐。这也解释了为什么内存占用量是最优的两倍。

FIFO分配器

FIFO问题

另一个经常使用的内存模式是采用FIFO（先入先出）管道：这意味着内存的释放顺序与分配顺序相近。典型的用例是网络协议实现中的请求上下文缓冲区：每个请求与一个上下文相关，上下文在发出请求时分配，在收到答复时释放。大部分时候，请求将按照它们提交的顺序进行处理（虽然并不总是这样，但同这种过程的执行时间相比，再长的处理时间也是短的）。

当FIFO数据直接在堆上分配时，它会放大内存碎片问题，因为下一个被释放的块很可能不是堆的尾部，这将在堆上形成一个洞（因为并不仅仅FIFO在堆上分配，其他的分配将被插入两个FIFO项之间，这使得情况更加糟糕）。

解决方法

由于上述原因，我们决定将这类使用模式与其它分配隔离。我们使用自定义的分配器来取代堆分配。

这个分配器与栈分配器的工作原理基本相同：它包含一个由线性内存的巨块组成的arena（只有在当前块中无法满足分配时，新块才会被分配）。FIFO分配器采用由每块来记录大小的机制而不是基于帧的模型。每个块维护它所分配的内存大小。当块中所有的数据被释放时，块本身才会被释放。块使用mmap分配以确保他们不会干涉堆（因而不会导致碎片）。

由于FIFO堆分配器与栈分配器采用相同的分配模式（释放模式不同），它们具有一些共性。其中之一是连续分配的内存是相邻的。不过，由FIFO分配器的使用模式带来的局部性改善并不太重要：大部分时候，它是用来分配那些极少被一起使用的独立元素。

FIFO分配器被设计用于单线程环境中，因而不存在竞争问题。

性能测试

我们用FIFO分配器进行无竞争场景的测试，来与malloc()的性能做对比：

场景	分配	释放	占用	时间
无竞争	1100ms(90M/s)	638ms(156M/s)	1.5GiB	5.30s

同栈分配器一样，FIFO分配器优于malloc()实现。然而，它比栈分配器慢一点，因为它要跟踪记录每一个独立的分配，可能没有像栈分配器那样的最优化。

环形分配器

环形分配器在某种程度上是栈分配器和FIFO分配器的混合。它用帧来对分配进行分类，在主要采用FIFO模式的同时又保证了在常量时间内完成大量内存的释放。环形分配器中的帧并不会影响前面的帧，每个帧都是独立的、自包含的。

为了在环形分配器中分配内存，第一步是创建一个新的帧。这需要前一帧已被封住。一旦帧在分配器中打开，分配就可以进行并自动成为活跃帧的一部分。当所有的分配已经完成，帧必须被封住。被封住的帧仍然可用，这意味着它所包含的分配仍可以被访问，但不能接受新的分配。当帧不再被需要时，它必须被释放。

环形分配器释放内存是线程安全的。这使得分配器非常适合于构建传递给工作线程的消息。在这种情况下，它可以作为多线程环境下对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);
    });
}

在这种使用场合，帧大多按照FIFO的顺序进行释放。

我们使用该分配器再次进行测试。由于环形分配器是线程安全的，测试覆盖竞争和无竞争两种情形：

场景	分配	释放	占用内存	时间
无竞争	861ms(116M/s)	0ms	764MiB	2.82s
无竞争	862ms(116M/s)	0ms	764MiB	2.83s

其它自定义分配器

本文介绍了Intersec中使用的三个自定义分配器。 这三个分配器并不用作通用目的：它们被优化以用于特定的使用模式。值得庆幸的是，大部分时候这三个分配器的组合足以避免使用malloc()时遇到的大多数问题，如缺乏局部性，在分配过程中的锁竞争和堆碎片。

然而，有时也并非如此，我们别无选择，只能自定义实现一个通用分配器以满足我们的性能要求。因为这个原因，我们也有一个基于（两级隔离适应）的分配器。TLSF是一个分配算法，被设计用于实时处理，它能保证分配和释放在常量时间内完成。

另外透露下，我们也有一些页分配器和持久分配器。后一个可能会在后续文章中讲到。

下一章：调试工具

在本系列的最后一篇文章中，我们将介绍处理内存问题的工具。

---

1. 在引入t_scope宏之前，开发者得显示调用t_push()和t_pop()分配帧，但这太危险，并且由于缺少t_pop()（大多在错误处理的情况下）导致了一些bug，它们自身会导致内存泄漏。引进t_scope后，即使不是纯C环境，它提供了更安全的代码，因为开发人员不必关心错误情况，并且t_scope还可以自动检查push/pop平衡。

---

来源声明：本文来自Intersec的博文《Memory – Part 4: Intersec’s custom allocators》，由IDF实验室童进翻译。

（全文完）