首页 > *nix安全 > Intersec内存系列文章–第4部分:Intersec自定义分配器

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

2014年3月17日 发表评论 阅读评论 7,601次浏览    

原文:http://techtalk.intersec.com/2013/10/memory-part-4-intersecs-custom-allocators/

翻译:童进

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

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

malloc-benchmark

测试程序运行了三次:分别采用了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 帧界限

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

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

mem-stack

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

由于分配和释放有严格的顺序,两个连续的分配将返回相邻的内存块(除非新的分配需要一个新的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(两级隔离适应)的分配器。TLSF是一个分配算法,被设计用于实时处理,它能保证分配和释放在常量时间内完成。

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

下一章:调试工具

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


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

(全文完)

版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0
分类: *nix安全 标签: ,
  1. 本文目前尚无任何评论.