目录

Linux 内存分配算法

Linux 内存分配算法用于管理和分配系统中的内存资源，具有下列 3 个方面的关键目标。

1. 最大化利用内存资源
2. 避免内存碎片
3. 提高内存分配效率

Kernel 为此实现了 2 大类型的内存分配算法：

1. 面向 Main Memory 的 Buddy 分配算法
2. 面向 CPU Cache 的 Slab/Slub 分配算法

值的注意的是，glibc 提供的 malloc() 等虚拟地址空间内存分配接口所使用到的内存分配算法由 glibc 具体实现，并不直接由 Kernel 提供，不属于本文讨论的范畴。

Buddy 分配算法

Buddy（Buddy system，伙伴系统）分配算法，是一种尽量避免内存碎片的分配算法，用于管理 Main Memory 物理内存页面的分配和释放。

针对 Linux 页式内存管理方式，Buddy 实现了 11 张链表，每张链表的节点分别为 2^n * PageSize 大小的页面空间，称为 “伙伴块“。其中 n 为 0-10，即：1，2，4，8，16，32，64，128，256，512 和 1024。

如果当前系统的 PageSize 为 4K（默认），那么这 11 张链表的伙伴块大小分别为 4K、8K、16K、…、2M、4M。

当需要分配一块大小为 size 的内存时，Buddy 就会这些链表中寻找满足一个 >= size 的伙伴块。并执行以下算法：

1. 如果存在 = size 的伙伴块，那么 Buddy 直接分配。
2. 如果存在 > size 的伙伴块，那么 Buddy 会将大伙伴块切分，并将剩余的一部分存储到小链表中。
3. 如果不存在 >= size 的伙伴块，那么 Buddy 会将多个小的伙伴块组成一个 >= size 的伙伴块。且如果合并后 > 时，还会切分，并将剩余的一部分存储到小链表中。

当释放一块内存时，Buddy 则会检查释放的这几个页的前后页是否空闲，是否能组成一个大的伙伴块，如果可以则合并，并存储到大链表中。

在 Linux 操作系统中可以通过命令查看 Buddy 的分配情况。

$ cat /proc/buddyinfo

Node 0, zone      DMA      1      0      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32    189    209    119     80     38     17     11      1      1      2    627
Node 0, zone   Normal   1298   1768   1859    661    743    461    275    133     68     61   2752

Slab 分配算法

Slab 分配算法是一种基于 Object Cache（对象缓存）的内存分配算法，被用于分配和释放内核对象的缓存。kmalloc() 和 kfree() SCI 底层使用了 Slab 分配算法。

Kernel 中存在大量的 Small objects（小对象），例如：文件描述符号对象、进程描述结构对象等等。这些 objects 不适合应用 Buddy 分配算法，因为 objects 的 Size 很可能远小于一个页（4K），会造成空间浪费。而且这些 objects 数量庞大，可能会引起 Buddy 频繁的执行页的拆分、合并、分配和释放，从而降低系统性能。

所以 Slab 分配算法就是针对这些 objects 而设计的，它的核心思想是将这些 objects 存储到 CPU Cache 中，并且由 Kernel 维持其始终可用的状态。

具体地说，Slab 实现了一个由 “2 级链表 + 1 级页表“ 组成的结构：

1. Slab 分配器首先创建了一个 cache_chain 链表，链表的节点为若干个 kmem_cache（高速缓存空间），它们具有不同的 Sizes（32B、128B、32KB etc…）。
2. 每个 kmem_cache 又包含了 3 种类型的 slabs 链表，这些链表的节点是若干个 slabs。这些 slab 是 Slab 分配器的最小存储/管理单位，本质是最终分配给 objects 的内存空间。
   • slabs_full：完全分配的 slabs 链表。
   • slabs_partial：部分分配的 slabs 链表。
   • slabs_empty/free：没有分配的 slabs 链表。
3. 每个 slab 的空间可以分配给多个 objects 使用，slab 和 objects 之间通过 PageTable 来建立映射关系。

slab 会在 3 个不同的 slabs 链表之间流动，例如：一个 slabs_partial 链表中的 slab 的空间被完全分配给了 objects 后，那么该 slab 就会被移动到 slabs_full 链表中，表示现在无法继续分配给其他 objects 了。

下图展示了 Slab 分配器为 objects 分配空间的流程：

1. 如果 slabs_partial 链表还有未分配的空间，那么分配给 objects，若分配完了，移动 slab 到 slabs_full 链表。
2. 如果 slabs_partial 链表没有未分配的空间，进入下一步。
3. 如果 slabs_empty 链表还有未分配的空间，那么分配给 objects，同时移动 slab 进入 slabs_partial 链表。
4. 如果 slabs_empty 为空，那么请求 Buddy 分一个页，创建一个新的空闲 slab 加入到 slabs_empty，然后再按步骤 3 分配对象。

在 Linux 上查看 Slab 内存分配的信息：

$ cat /proc/slabinfo

slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
isofs_inode_cache     50     50    640   25    4 : tunables    0    0    0 : slabdata      2      2      0
kvm_async_pf           0      0    136   30    1 : tunables    0    0    0 : slabdata      0      0      0
kvm_vcpu               0      0  14976    2    8 : tunables    0    0    0 : slabdata      0      0      0
xfs_dqtrx              0      0    528   31    4 : tunables    0    0    0 : slabdata      0      0      0
xfs_dquot              0      0    488   33    4 : tunables    0    0    0 : slabdata      0      0      0
xfs_ili            40296  40296    168   24    1 : tunables    0    0    0 : slabdata   1679   1679      0
xfs_inode          41591  41616    960   34    8 : tunables    0    0    0 : slabdata   1224   1224      0
xfs_efd_item        1053   1053    416   39    4 : tunables    0    0    0 : slabdata     27     27      0
6
7
8
9
10
11
12

Slub 分配算法

随着 NUMA 等多核平台的广泛应用，Slab 分配算法也暴露出了以下问题：

1. 复杂的多级链表管理开销较大。
2. 长时间运行会导致 slab_partial 链表变得非常长。
3. 对 NUMA 支持非常复杂。

为了解决问题，Kernel 基于 Slab 实现了替代的 Slub 分配算法，同样用于分配和释放内核对象的缓存。kmalloc() 和 kfree() SCI 底层使用了 Slub 分配算法。

下图中清晰的展示了 Slub 在 Slab 的基础上，为每个 CPU core 都创建了一个本地的 kmem_cache_cpu。

还重新设计了 3 个 slabs 链表，去除了最后 1 级 PageTable。