推荐系列-DPDK内存碎片优化，性能最高��升30+倍-

&emsp;&emsp;链接点击 DPDK内存碎片优化，性能最高提升30+倍! 背景 DPDK（Data Plane Development Kit）是一个用于高性能数据包处理的开源项目，常用于构建各类高性能网络应用。基于 DPDK 的设计思想…

背景

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

多线程

单次分配大小
测试项
修改前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 作为开源项目，凭借其出色的性能表现赢得了众多开发者的青睐，我们也希望在使用开源项目获得收益的同时，能为项目与社区带来更多想法，做出更多贡献，与开发者们一起推进社区的建设。

本文标题：推荐系列-DPDK内存碎片优化，性能最高��升30+倍-

本文作者： OSChina

发布时间： 2023年05月24日 09:23

最后更新： 2023年06月29日 07:10

原始链接： https://haoxiang.eu.org/ed9d85f2/

赏

狂欢马克思

专注Web开发