您的位置: 首页 > 技术杂谈 > 正文

DPDK内存碎片优化，性能最高提升30+倍!

2023-05-23 12:00 https://my.oschina.net/u/6150560/blog/8881899 字节跳动SYS Tech 次阅读条评论

原文链接点击 DPDK内存碎片优化，性能最高提升30+倍!

背景

DPDK（Data Plane Development Kit）是一个用于高性能数据包处理的开源项目，常用于构建各类高性能网络应用。基于 DPDK 的设计思想及其提供的线程/内存模型，SPDK(Storage Performance Development Kit)被开发出来，广泛用于构建各类高性能存储应用。

为了提升应用程序的性能，DPDK 基于大页内存实现了一套自己的内存管理接口，这些内存接口被广泛应用于SPDK/DPDK 的各类应用中，而且不少应用会在 IO 路径中进行内存的分配与释放。DPDK 常用的内存接口有：

void *rte_malloc(const char *type, size_t size, unsigned align);
void *rte_realloc(void *ptr, size_t size, unsigned int align);
void rte_free(void *ptr);

在实际使用过程中，我们发现 DPDK 原生的内存分配接口在一些场景下有着较大的性能问题。本文将结合实际遇到的问题，为大家介绍如何优化 DPDK 内存碎片问题。

问题现象

当接到 DPDK 内存碎片化的问题反馈后，经过多方排查，最终将怀疑点锁定到大页内存的分配上，并将实际使用时内存分配的逻辑与参数进行抽象后，编写了如下的测试 case：

uint64_t entry_time, time;
size_t size = 4096;
unsigned align = 4096;
for (int j = 0; j < 10; j++) {
        entry_time = rte_get_timer_cycles();
        for (int i = 0; i < 2000; i++) {
                rte_malloc(NULL, size, align);
        }
        time = (rte_get_timer_cycles()-entry_time) * 1000000 /
                rte_get_timer_hz();
        printf("total open time %lu us, avg time %lu us\n", time, time/2000);
}

单线程执行内存分配，总共分配 1 万个 4k 大小的对象, 每 2000 次分配后计算平均耗时，中间不释放内存，各阶段单次平均耗时如下表：

malloc次数	平均耗时
0-2000	15us
2000-4000	44us
4000-6000	77us
6000-8000	168us
8000-10000	253us

从上表可以看到，随着分配次数的增加，后续每分配 4K内存的耗时在线性增加，按照我们之前的理解，单线程下多次分配内存耗时不会过高，每次分配4K内存的耗时应该差不多，但是当前结果与预期不符，针对该场景我们进行了深入分析。

分析

首先结合代码分析了 DPDK 分配的逻辑，然后结合火焰图对怀疑点加了些调试手段以进一步 debug，最终得到了结论，并对结论进行了的验证。

代码分析

DPDK 通过 heap 管理每个 NUMA 节点上的大页内存，对于一块连续内存，首先转换成一个 struct malloc_elem 对象 elem，再将 elem 插入链表中，并保证链表中每项的地址按大小排序。每个 heap 都维护了 13 个链表，每个链表中的 elem 大小在相同范围内，比如大小 0-256 的 elem 在同一个链表，256-1024 的 elem 在同一个链表，1024-4096 的 elem 在同一个链表...。

DPDK内存分配的主要逻辑如下图所示：

暂时无法在飞书文档外展示此内容

根据参数和当前线程所在 CPU 决定从哪个 heap 上分配内存。
根据要分配的大小，找到对应的链表（对应代码中的 free_head[N]），遍历该链表中所有的 elem，找到合适（满足大小、对齐等要求）的 elem。
将 elelm 从链表上摘除，根据大小进行切分并返回。

抓火焰图

可以看到 find_subitable_element 函数耗时非常高，这个函数的作用就是遍历链表上的 elem，找到满足要求的 elelm。以分配 4K 内存为例，首先遍历第三个链表即 free_head[2] 上的所有 elem，逐个检查是否满足要求，如果找到合适的 elem，就从链表上摘除，根据大小进行切分并返回，如果 free_head[2] 上找不到，会依次在free_head[3]、free_head[4] 上查找，直到找到为止。

从代码分析单次判断 elem 是否满足要求耗时应该很短，所以怀疑是链表上元素过多，导致整个遍历耗时过久。

那么我们可以尝试添加些 log，看看各个链表上 elem 的个数是否有变化

添加调试手段

经分析 DPDK 有些内存 dump 的 rpc，其中用到的 malloc_heap_get_stats 函数会遍历 heap 上所有链表上的 elem，我们可以简单修改，查看每个链表上的 elem 个数。

系统刚启动完成时，可以看到 elem 个数不多，大小也比较集中。

分配 2000 个 4K 内存后，看到 free_head[2] 上 elem 数量明显增加：

分配 4000 个 4K 内存后：

可以看到 free_head[2] 上 elem 个数随着分配次数的增加线性增加，这会导致每次分配 4K 所需遍历的 elem 个数也会增加，那么为什么会这样呢？

原因分析

添加 log 发现，free_head[2] 上所有 elem 的大小都小于 4096 字节:

为什么会出现这么多小的 elem 呢？经分析我们发现是在分配时切分 elem 而生成，切分 elem 示意图如下：

暂时无法在飞书文档外展示此内容

以上图为例：

当调用 find_suitable_element 函数后，找到了一个满足要求的 elem，该 elem 大小一般远大于 4096 字节，所以在 malloc_elem_alloc 中会切分。
malloc_elem_alloc 中会从 elem 末尾开始，根据大小和对齐算出 new_elem 的地址，由于分配内存要求 4K 对齐，所以 end-start 很可能大于 4096 ，而我们只要 4096，那么 new_elem 后面的 tailer 这段空间为避免浪费，是可以被重新利用的，由于其大小是 2432，也会被插入 free_head[2] 中。这也就导致了 free_head[2] 上 elem 个数在线性增加。

验证

根据上述分析，如果 align 为 64 字节，elem 的尾部空间应该小于 64，不会再插入链表，就不会有这个问题，将测试代码中的 align 参数改为 64 后，测试结果如下:

平均耗时 0.7us ~ 0.8us，不再有线性增加的现象。

那么是不是所有的 align 都有这个问题？我们又测了分配 64K 大小，align 为 64K 的情况，也出现了相同的情况。

结论

DPDK在管理内存时会将相邻大小的 elem 放在一个链表，分配时根据大小 4K 找到对应的链表 free_head[2]，遍历该链表上的 elem 来查找满足要求的 elem，当分配时指定 align 过大，会使找到的 elem 尾部空间较大，为避免空间浪费会将尾部空间重新插入 free_head[2] 链表中，导致 free_head[2] 链表中 elem 数量增多，下次分配时又需要先遍历 free_head[2]，使每次分配耗时呈线性增加。

解决方案

方案一：

struct malloc_heap {
        rte_spinlock_t lock;
        LIST_HEAD(, malloc_elem) free_head[RTE_HEAP_NUM_FREELISTS];
        size_t free_head_max_size[RTE_HEAP_NUM_FREELISTS];
        .....
}

在 heap 中新增 free_head_max_size 数组，记录每个 freelist 中 elem 的最大 size，遍历时如果要求的 size 大于该 freelist 上最大的size，可以直接跳过，但缺点是每次分配/释放时都要维护该数组。

可以看到单次分配耗时没有再呈线性增加，平均耗时稳定在0.5us左右，对比之前性能提升30 倍+：

方案二：

在原有的逻辑中，大小为 4K 的 elem 在 free_head[2] 上，4K 刚好处于边界，如果修改链表选择的规则，改到在 free_head[3] 进行查找，也可以解决问题。以分配 4K 为例，在 4K-16K 的链表上更容易找到对应的 elem，16K 也是在 16K-64K 的链表上能查找的概率更高。

也即每个链表上包含的元素大小范围如下：

heap->free_head[ 0 ] - ( 0 , 2 ^ 8 ) 0 < x < 256  heap->free_head[ 1 ] - [ 2 ^ 8 , 2 ^ 10 ) 256 <= x < 1024  heap->free_head[ 2 ] - [ 2 ^ 10 , 2 ^ 12 ) 1024 <= x < 4096  heap->free_head[ 3 ] - [ 2 ^ 12 , 2 ^ 14 ) 4 k <= x < 16 k
heap->free_head[ 4 ] - [ 2 ^ 14 , 2 ^ 16 ) 16 k <= x < 64 k ...

对比测试效果与方案一无明显差异，优点是对 16K/64K 等处于边界点的分配效率也有提升，缺点是可能会对极端情况有影响，需要更多测试。

测试验证

单线程

bulk：连续分配 1000 个对象，memset 后，1000 个对象一起释放，统计单次平均分配/释放耗时

no-bulk：分配 1 个对象，memset, delay 5us, 释放，重复 1 万次，统计平均分配和释放的总耗时

realloc：分配 1 个对象，memset, realloc 成原本 2 倍大小，memset, realloc 成原本 4 倍大小，memset，释放，重复 1000 次，统计平均总耗时

单次分配大小	测试项	修改前align=64	修改后align=64	修改前align=4096	修改后align=4096
64	bulk	0.309/0.083	0.287/0.079	/	/
no-bluk	5.275	5.273	/	/
realloc	0.538	0.512	/	/
128	bulk	0.410/0.074	0.399/0.085	/	/
no-bluk	5.270	5.264	/	/
realloc	0.584	0.616	/	/
512	bulk	0.380/0.115	0.382/0.086	/	/
no-bluk	5.291	5.292	/	/
realloc	1.033	0.963	/	/
1024	bulk	0.636/0.117	0.36/0.146	/	/
no-bluk	5.291	5.289	/	/
realloc	1.56	1.31us	/	/
3072	bulk	0.801/0.386	0.812/0.343	0.875/0.217	0.883/0.225
no-bluk	5.32	5.26	5.77	5.81
realloc	2.15	2.09	2.774	2.769
4096	bulk	1.099/0.486	0.771/0.474	0.90/0.324	0.762/0.362
no-bluk	5.62	5.329	5.65	5.394
realloc	2.89	2.59	3.36	2.81
8192	bulk	0.967/0.563	1.011/0.589	0.886/0.516	0.883/0.476
no-bluk	5.37	5.37	5.43	5.43
realloc	4.68	4.65	4.87	4.75
16384	bulk	1.33/0.87	1.21/0.881	1.379/0.938	1.33/0.95
no-bluk	5.49	5.465	5.57	5.525
realloc	9.59	9.528	9.76	9.705
32768	bulk	2.22/2.01	2.276/2.06	2.41/2.06	2.44/2.068
no-bluk	5.65	5.646	5.72	5.71us
realloc	20.5	20.49	20.8	20.74
131072	bulk	10.432/10.526	10.397/10.531	10.68/10.79	10.676/10.818
no-bluk	9.87	9.866	9.9	9.9
realloc	82.0	82.15	82.8	82.56
524288	bulk	42.8/42.59	43.058/42.689	43.6/43.2	43.609/43.357
no-bluk	23.72	23.74	23.8	23.8us
realloc	406	406	407	408.75
1048576	bulk	125.2/125.7	124.9/125	88.2/86.8	87.3/86.9
no-bluk	42.38	42.25	42.46	42.46
realloc	869	873	890	888

多线程

bulk：连续分配 1000 个对象，memset 后，1000 个对象一起释放，统计单次平均分配/释放耗时

no-bulk：分配 1 个对象，memset, delay 5us, 释放，重复 1 万次，统计平均分配和释放的总耗时

realloc：分配 1 个对象，memset, realloc 成原本 2 倍大小，memset, realloc 成原本 4 倍大小，memset，释放，重复 1000 次，统计平均总耗时

单次分配大小	测试项	修改前align=64	修改后align=64	修改前align=4096	修改后align=4096
64	bulk	15.0/6.5	15.1/6.5	/	/
no-bluk	22.6	22.6	/	/
realloc	73.5	73.8	/	/
128	bulk	17.4/6.7	17.2/6.7	/	/
no-bluk	23.5	23.5	/	/
realloc	73.9	73.3	/	/
512	bulk	16.8/6.2	16.4/6.2	/	/
no-bluk	22.3	22.4	/	/
realloc	82.1	79.5	/	/
1024	bulk	18.5/6.8	15.9/6.7	/	/
no-bluk	25.1	24.0	/	/
realloc	92.1	84.7	/	/
3072	bulk	18.2/7.8	18.2/7.9	29.1/6.7	29.3/6.5
no-bluk	23.9	25	36.8	36.3
realloc	91.8	91.3	117.7	116.2
4096	bulk	21.3/8.5	16.7/8.4	30.3/14.2	23.0/7.5
no-bluk	28.9	24.6	39.2	30.0
realloc	101.8	95.1	125.6	108
8192	bulk	18.4/12.0	18.4/12	25.0/9.8	24.1/11.5
no-bluk	26.0	25.9	31.2	30.9
realloc	110.7	108.4	122.8	121
16384	bulk	22.9/19.4	19.4/19.0	28.5/16.5	27.2/15.6
no-bluk	27.8	26.5	33.5	31.5
realloc	125.6	122.5	140.9	136.2
32768	bulk	27.4/33.2	27.4/33.2	32.8/30.3	34.1/27.5
no-bluk	28.9	28.8	34	34
realloc	171	168.2	184.5	180.8
131072	bulk	44.8/170	44.6/171	44.7/169.4	44.6/167
no-bluk	58.5	58.1	63.2	62.9
realloc	463.6	458.3	472.7	470
524288	bulk	160/655	160/660	160.8/653.7	160.1/652.5
no-bluk	162.8	163	168.8	168.7
realloc	1812	1826	1824	1820

16 个线程，每个线程单独绑核后做如下测试：

连续分配 N 个 4K 大小对象，4K 对齐，每次分配之间 delay 5us, 统计耗时，然后连续释放 N 个 4K 对象，不delay，统计单次耗时

单线程分配次数	优化前	优化后
64	109us	16us
128	214us	17.8us
256	408us	17.5us
512	962us	18.2us
1024	3.1ms	15.3us
2048	8.6ms	17.6us
4096	20.5ms	17.4us

DPDK malloc perf test

malloc 测试，修改前：

malloc 测试，修改后，可以看到没有性能衰退，4K/64K/1M 等大小分配有 15%-50% 的性能提升：

memzone 测试，修改前：

memzone测试，修改后没有性能衰退，64K/1M 大小的分配分别有 7% 和 52% 的性能提升：

总结

通过以上分析，确定了 DPDK 内存碎片化的诱因是在分配时要求对齐的大小比较大，导致 elem 切分时产生了很多碎片，并影响了后续内存分配的效率。经过完整的测试，最终选用了方案二，改动简单，效果也更好，不仅解决碎片场景下的问题，使得性能提升 30+ 倍，也在非碎片情况下，使得 4K/64K/1M 等大小的内存分配性能提升 15-50% ，同时也能缓解多进程并发分配时竞争锁的压力。目前字节跳动 STE 团队已将该补丁提交至 DPDK 社区，并于 2023 年 2 月合入 DPDK 主线，链接如下：https://inbox.dpdk.org/dev/CAJFAV8x5k55jH0A_BHN9jxA1m-3o08tKr7RbCesvVL7o4MKgGQ@mail.gmail.com/

DPDK/SPDK 作为开源项目，凭借其出色的性能表现赢得了众多开发者的青睐，我们也希望在使用开源项目获得收益的同时，能为项目与社区带来更多想法，做出更多贡献，与开发者们一起推进社区的建设。

展开阅读全文