3.2.5 SLAB/SLUB/SLOB

上一节我们讨论了使用Buddy System进行连续内存页面的分配，但对于使用内存的程序而言，Buddy System 还存在如下问题：

  • 粒度太大：Buddy System一次最少也要分配一页内存，通常情况下是4KB, 这对于程序而言还是太大了，我们需要一种更加细致的方式来对内存进行分配与释放。

  • 缺乏语义：程序在使用内存时考虑的通常也不会是“物理内存页”这种底层概念，而是程序中定义的各种具备业务意义的数据结构与对象；不仅如此，对象的初始化与释放的逻辑有时比内存分配更加耗时。

  • 效率偏低：Buddy System在分配与释放内存时会对Buddy进行拆分与合并，在频繁的内存申请与释放的场景下这将非常影响性能。

为了解决这些问题，内核基于Buddy System构建了一个“对象分配系统”，该系统叫着SLAB Allocator, SLAB以对象为基本单位进行分配与释放，并且为对象提供了缓存机制，从而一举解决了上述的各种问题。

SLAB详细思路可以参考论文：The Slab Allocator: An Object-Caching Kernel Memory Allotor

SLUB是SLAB的改进版本，本节后续内容我们将基于SLUB的代码来讨论具体实现，但依然使用SLAB来描述对应的算法和概念。

SLOB是用于嵌入式等内存容量不大的场景下的对象分配算法，这里我们不做介绍。

3.2.5.1 对象（Object）

对象（Object）一词常用于面向对象编程语言之中，从技术上讲，一个对象是一组数据（属性）与行为（方法）的封装；从业务上讲，对象用来对业务概念进行建模，以便更好地通过模块化地方式构建系统。但这里我们所说的对象确不是这个概念，此处的对象指满足内核内存申请时的任意大小的一块连续内存。

SLAB通过两个维度来区分对象：

  • 用途，例如表示对象是用于通用的目的（例如用于内核的各种数据结构），还是用于特定目的（例如用于DMA）；

  • 大小，从内存的视角上来看，所谓对象就是固定大小的一块连续内存，SLAB将对象通过大小进行区分，并将相同大小的对象组织在一起进行管理；

从逻辑上讲，一个SLAB Allocator管理的就是一个 <用途，大小> 形成的对象集合，Linux中所有的SLAB信息记录在 /proc/slabinfo 文件中，我们可以看一下其中的内容：

❯ sudo 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>
kmalloc-8k           204    208   8192    4    8 : tunables    0    0    0 : slabdata     52     52      0
kmalloc-4k           709    752   4096    8    8 : tunables    0    0    0 : slabdata     94     94      0
kmalloc-2k          1266   1312   2048   16    8 : tunables    0    0    0 : slabdata     82     82      0
kmalloc-1k          2827   3008   1024   32    8 : tunables    0    0    0 : slabdata     94     94      0
kmalloc-512        54469  57856    512   32    4 : tunables    0    0    0 : slabdata   1808   1808      0
kmalloc-256        21418  21536    256   32    2 : tunables    0    0    0 : slabdata    673    673      0
kmalloc-192        43876  48867    192   21    1 : tunables    0    0    0 : slabdata   2327   2327      0
kmalloc-128         2157   2240    128   32    1 : tunables    0    0    0 : slabdata     70     70      0
kmalloc-96          2745   2772     96   42    1 : tunables    0    0    0 : slabdata     66     66      0
kmalloc-64         14032  14720     64   64    1 : tunables    0    0    0 : slabdata    230    230      0
kmalloc-32         22733  23040     32  128    1 : tunables    0    0    0 : slabdata    180    180      0
kmalloc-16         14485  14848     16  256    1 : tunables    0    0    0 : slabdata     58     58      0
kmalloc-8          10691  10752      8  512    1 : tunables    0    0    0 : slabdata     21     21      0
kmem_cache_node      576    576     64   64    1 : tunables    0    0    0 : slabdata      9      9      0
kmem_cache           352    352    256   32    2 : tunables    0    0    0 : slabdata     11     11      0

这里展示了系统中部分的 slab 信息，其中 kmalloc 是内核运行时申请内存的通用slab, 内核可能申请任意大小的内存，为了满足各种应用场景，内核预备了各种大小的 kmalloc slab, 从最小的8Byte一直到最大的8KB, 大小呈几何级数分布，并且各个 slab 的大小都满足 2n。内核申请内存时需要指定内存大小，然后系统找到满足要求的最小的 kmalloc slab 来进行分配。

为何 kmalloc slab 的大小呈几何级数增长呢？原因是这样的设定能够尽可能地减少内存的内部碎片（Internal Fragmentation），因为不管 slab 使用了多少个物理内存页，都能够被 slab 的对象大小所整除；另外由于相邻 slab 的大小相差两倍，所以任何分配出去的对象的使用率都会超过50%。例如一个内核的结构体刚好是17字节，满足该大小的最小的 slab 是 kmalloc-32, 这样分配出去的对象最终使用了17 字节，浪费了15字节，浪费率低于50%.

3.2.5.2 Slab

一个Slab包含一个或多个连续的物理页面，然后将这些页面均分成固定的大小的各等份，每一等份就是一个对象，各对象通过链表串起来。有关slab 的信息封装在 page 中，对应的字段如下：

如果页面被分配用于 slab, 那么这些字段就会被设置。其中 kmem_cache 与注释中提到的 kmem_cache_cpu 等结构会在下一节介绍。内核创建一个slab的逻辑也很直观：首先向Buddy System申请一定数量的连续页面，然后初始化对象并构建好对象列表。代码如下：

在前文中我们提到过slab中的对象就是一个固定大小的连续内存块，通过对象列表的构建逻辑我们可以对此有更深刻的理解，内核并没有单独定义一个结构体来封装对象信息，在构建对象列表时，指向下一个空闲对象的指针也是直接存放在该对象的内存地址内部，因为对象还没有被分配出去时内存是不会被使用的，而被分配之后也不需要该指针了，这是一个比较精巧的设计。一个初始化完毕的 slab 的示意图如下所示：

freelist 总是指向slab 中第一个空闲对象，也是 slab 分配与释放对象的入口点，这在后续章节会详细介绍。

3.2.5.3 缓存（Cache）

前面讨论了 slab 如何组织管理对象，但我们还面临如下问题：

  • 性能问题：多核系统中，如果多个CPU都使用共享的slab, 那么在分配与释放对象时会面临强烈的竞争问题，从而极大影响系统性能；

  • 如何管理多个slab: 上一节只讲到了内核如何初始化一个slab, slab 从Buddy System中分配的内存页面是固定的，当slab中的对象耗尽之后内核需要重新创建新的slab, 如何管理这些相同类型的 slab 也是一个问题；

内核引入了缓存的概念来解决这些问题。一个缓存使用一个 kmem_cache 来表示，该结构体的定义如下：

我们在前文讨论 slab 初始化时已经见过该结构体，并且已经使用过其中的某些字段，例如用来确定 slab 页面数量与对象数量的字段 struct kmem_cache_order_objects oo;

内核使用 kmem_cache 来管理同一类对象的所有 slab, 其中最重要的两个字段是 struct kmem_cache_cpu __percpu * cpu_slab 与 struct kmem_cache_node * node[MAX_NUMNODES]. 为了避免分配对象时的竞争问题， kmem_cache 为每个CPU都单独维护了一个slab 缓存，变量 cpu_slab 的修饰符 __percpu 就是告诉编译器，该字段是 per cpu 的。该结构体定义如下：

内核申请对象时，CPU都会首先尝试从自己的缓存对象 kmem_cache_cpu 中进行分配，这是效率最高的分配通道。

既然CPU使用的是自己独占的缓存对象了，那么为什么还需要字段 tid 来做同步呢？因为虽然CPU不用与其它CPU竞争资源，但在对象分配过程中调度器可能切入触发任务切换，当前任务在下次被调度时可能就跑到了其它CPU上去执行了；或者当前CPU可能发生中断，而中断处理程序可能会从同一个Slab缓存中申请对象，因此我们需要一种机制来保证对象分配发生在同一个CPU上，并且分配过程中不会被干扰，slab 通过 tid 来实现这一点。tid 是一个全局递增的数字，slab 在每次开始分配对象前会读取到当前的tid数值，完成分配后将 tid 递增，然后通过原子操作CAS(Compare And Set) 来同时更新 freelist 与 tid 两个值，这样如果中途有其它的分配操作乱入的话，CAS 操作就会失败，slab 就会重头开始重新进行分配，直到成功为止。该段逻辑在函数 slab_alloc_node 中，这里我们在不深入具体分配逻辑的情况下看一下同步策略：

如果CPU的本地缓存没有空闲对象，那么就需要从其它地方拿一个可用的slab过来，这个地方就是 kmem_cache_node, 这相当于 kmem_cache 的一个中心化仓库，用来管理暂时没有被 kmem_cache_cpu 使用到的slab. 前文介绍NUMA架构时提到过内存会根据CPU的拓扑结果划分成不同的Node, 为了区分从不同Node 分配过来的 slab, kmemcache 也根据Node对 kmem_cache_node 进行了区分，该字段是一个与Node数量相等的数组。

kmem_cache_node 的定义如下：

这里我们只留下了与 SLUB 算法相关的部分，一个 kmem_cache_node 实际上就包含了两个列表，一个是partial slab列表，一个是full slab列表。示意图如下：

综合起来看，一个缓存 kmem_cache 管理着一个特定类型的所有slab, kmem_cache_cpu 中包含着当前CPU正在使用的slab, 任何对象分配的请求都直接从该slab中进行分配；而 kmem_cache_node 用来充当 kmem_cache_cpu 与Buddy System之间的缓冲区，当 kmem_cache_cpu 中的空闲对象分配完了之后，会将 slab 放入 kmem_cache_node 的full 列表，并从 partial 列表获取新的 slab 来使用，而当 kmem_cache_node 也没有多余的 slab 时，便会从Buddy System 中分配新的 slab 进行补充。同时，如果系统对该类对象的使用量下降，导致 kmem_cache_node 有很多完全空闲的 slab 时，系统也会酌情返回一些 slab 给Buddy System, 以缓解系统的总体内存压力。

所有的 kmem_cache 保留在全局变量 kmalloc_caches 中，代码如下：

总结起来，系统所有 kmemcache 的示意图如下：

3.2.5.4 分配（Allocation) 与释放（Free）

通过前文对几个核心概念的分析，我们可以总结出关于SLAB的一些关键设计思想：

  • 懒加载（Lazy Loading）：缓存 kmem_cache 初始化时只会创建出 kmem_cache_cpu 与 kmem_cache_node, 但对slab的初始化会推迟到对象分配时才会发生，这可以降低系统总体的内存压力，因为除了SLAB 系统，整个内核在很多其它地方还需要使用内存；

  • 本地化（Locality）：为了减少竞争，每个CPU都持有一个自己的 slab, 做到独立运作不冲突；

本节我们将继续深入，探讨SLAB系统分配对象的详细流程，以及如何与Buddy System进行交互的。内核申请内存的入口函数是 kmalloc:

函数简单地调用 __kmalloc 并最终调用到 __do_kmalloc, 该函数通过内存大小与 flags 中的内存种类找到对应的 kmem_cache, 然后从该缓存中分配对象：

从缓存中分配对象有两条路径：

  • 快路径（fastpath）：直接从 kmem_cache_cpu 中的slab 中分配到对象

  • 慢路径（slowpath）：无法直接从 kmem_cache_cpu 中分配到对象，需要先从 kmem_cache_node 的 partial 列表拿一个slab，甚至需要从Buddy System 中分配一个全新的 slab 来进行补充

快路径的逻辑在函数 slab_alloc_node 中，前文讨论 kmem_cache_cpu 的并发控制时已经探索过该函数，这里再着重看一下有关对象分配的逻辑：

慢路径的逻辑在函数 ___slab_alloc 中，其主要思想是先尝试着从 kmem_cache_node 的partial 列表获取一个slab, 不行的话就从Buddy System 申请一个全新的slab 来使用。主要代码如下：

从Buddy System 分配与初始化slab 的函数在前面已经介绍过，这里不再讨论。

向缓存中释放对象时逻辑很简单，就是将该对象放入对应slab 的freelist 列表即可。但在如下几种情况下会调整slab 的位置：

  • slab 在 kmemcachenode 的full 列表中时，需要将该slab 放入 partial 列表中

  • slab 变成完全空闲状态时，即没有对象被使用，那么如果此时 kmemcachenode 有太多 slab 的话，需要将整个 slab 释放，将内存还给Buddy System

Previous3.2.4 Buddy System(伙伴系统)

Last updated

Was this helpful?