Linux Slab内存性能初探
2022-08-27 15:12:48 
阿炯
文章用了大量精美的图深入浅出地分析了Linux内核slab性能优化的核心思想，slab是Linux内核小对象内存分配最重要的算法，文章分析了内存分配的各种性能问题(在不同的场景下面)，并给出了这些问题的优化方案，这个对我们实现高性能内存池算法，或以后遇到内存性能问题的时候，有一定的启发，值得我们学习。
Linux内核的slab来自一种很简单的思想，即事先准备好一些会频繁分配，释放的数据结构。然而标准的slab实现太复杂且维护开销巨大，因此便分化出了更加小巧的slub，因此本文讨论的就是slub，后面所有提到slab的地方，指的都是slub。另外又由于本文主要描述内核优化方面的内容，因此想了解slab细节以及代码实现的请查看源码。
单CPU上单纯的slab
下图给出了单CPU上slab在分配和释放对象时的情景序列：
可以看出，非常之简单，而且完全达到了slab设计之初的目标。
扩展到多核心CPU
现在简单的将上面的模型扩展到多核心CPU，同样差不多的分配序列如下图所示：
可以看到，在只有单一slab的时候，如果多个CPU同时分配对象，冲突是不可避免的，解决冲突的几乎是唯一的办法就是加锁排队，然而这将大大增加延迟，申请单一对象的整个时延从T0开始，到T4结束，这太久了。
多CPU无锁化并行化操作的直接思路-复制给每个CPU一套相同的数据结构。不二法门就是增加“每CPU变量”。对于slab而言，可以扩展成下面的样子：
如果以为这么简单就结束了，那这就太没有意义了。
问题
首先来看一个简单的问题，如果单独的某个CPU的slab缓存没有对象可分配了，但是其它CPU的slab缓存仍有大量空闲对象的情况，如下图所示：
这是可能的，因为对单独一种slab的需求是和该CPU上执行的进程/线程紧密相关的，比如如果CPU0只处理网络，那么它就会对skb等数据结构有大量的需求，对于上图最后引出的问题，如果我们选择从伙伴系统中分配一个新的page(或者pages，取决于对象大小以及slab cache的order)，那么久而久之就会造成slab在CPU间分布的不均衡，更可能会因此吃掉大量的物理内存，这都是不希望看到的。
在继续之前，首先要明确的是，我们需要在CPU间均衡slab，并且这些必须靠slab内部的机制自行完成，这个和进程在CPU间负载均衡是完全不同的，对进程而言，拥有一个核心调度机制，比如基于时间片，或者虚拟时钟的步进速率等，但是对于slab，完全取决于使用者自身，只要对象仍然在使用，就不能剥夺使用者继续使用的权利，除非使用者自己释放。因此slab的负载均衡必须设计成合作型的，而不是抢占式的。
好了。现在我们知道，从伙伴系统重新分配一个page(s)并不是一个好主意，它应该是最终的决定，在执行它之前，首先要试一下别的路线。
现在引出第二个问题，如下图所示：
谁也不能保证分配slab对象的CPU和释放slab对象的CPU是同一个CPU，谁也不能保证一个CPU在一个slab对象的生命周期内没有分配新的page(s)，这期间的复杂操作谁也没有规定。这些问题该怎么解决呢？事实上，理解了这些问题是怎么解决的，一个slab框架就彻底理解了。
问题的解决-分层slab cache
无级变速总是让人向往。如果一个CPU的slab缓存满了，直接去抢同级别的别的CPU的slab缓存被认为是一种鲁莽且不道义的做法。那么为何不设置另外一个slab缓存，获取它里面的对象不像直接获取CPU的slab缓存那么简单且直接，但是难度却又不大，只是稍微增加一点消耗，这不是很好吗？
事实上， CPU的L1，L2，L3 cache不就是这个方案设计的吗？这事实上已经成为cache设计的不二法门。这个 设计思想同样作用于slab，就是Linux内核的slub实现， 现在可以给出概念和解释了。
Linux kernel slab cache：一个分为3层的对象cache模型。
Level 1 slab cache：一个空闲对象链表，每个CPU一个的独享cache，分配释放对象无需加锁。
Level 2 slab cache：一个空闲对象链表，每个CPU一个的共享page(s) cache，分配释放对象时仅需要锁住该page(s)，与Level 1 slab cache互斥，不互相包容。
Level 3 slab cache：一个page(s)链表，每个NUMA NODE的所有CPU共享的cache，单位为page(s)，获取后被提升到对应CPU的Level 1 slab cache，同时该page(s)作为Level 2的共享page(s)存在。
共享page(s)：该page(s)被一个或者多个CPU占有，每一个CPU在该page(s)上都可以拥有互相不充图的空闲对象链表，该page(s)拥有一个唯一的Level 2 slab cache空闲链表，该链表与上述一个或多个Level 1 slab cache空闲链表亦不冲突，多个CPU获取该Level 2 slab cache时必须争抢，获取后可以将该链表提升成自己的Level 1 slab cache。
该 slab cache的图示如下：
其行为如下图所示：
2个场景
对于常规的对象分配过程，下图展示了其细节：
事实上，对于多个CPU共享一个page(s)的情况，还可以有另一种玩法，如下图所示：
伙伴系统
前面简短的体会了Linux内核的slab设计，不宜过长，太长了不易理解；但是最后，如果Level 3也没有获取page(s)，那么最终会落到终极的伙伴系统，伙伴系统是为了防内存分配碎片化的，所以它尽可能地做两件事：
1.尽量分配尽可能大的内存
2.尽量合并连续的小块内存成一块大内存
可以通过下面的图解来理解上面的原则：
注意，本文是关于优化的，不是伙伴系统的科普，所以我假设大家已经理解了伙伴系统。
鉴于slab缓存对象大多数都是不超过1个页面的小结构(不仅仅slab系统，超过1个页面的内存需求相比1个页面的内存需求，很少)，因此会有大量的针对1个页面的内存分配需求。
从伙伴系统的分配原理可知，如果持续大量分配单一页面，会有大量的order大于0的页面分裂成单一页面，在单核心CPU上，这不是问题，但是在多核心CPU上，由于每一个CPU都会进行此类分配，而伙伴系统的分裂，合并操作会涉及大量的链表操作，这个锁开销是巨大的，因此需要优化！
Linux内核对伙伴系统针对单一页面的分配需求采取的批量分配“每CPU单一页面缓存”的方式！每一个CPU拥有一个单一页面缓存池，需要单一页面的时候，可以无需加锁从当前CPU对应的页面池中获取页面。而当池中页面不足时，系统会批量从伙伴系统中拉取一堆页面到池中，反过来，在单一页面释放的时候，会择优将其释放到每CPU的单一页面缓存中。
为了维持“每CPU单一页面缓存”中页面的数量不会太多或太少(太多会影响伙伴系统，太少会影响CPU的需求)，系统保持了两个值，当缓存页面数量低于low值的时候，便从伙伴系统中批量获取页面到池中，而当缓存页面数量大于high的时候，便会释放一些页面到伙伴系统中。
小结
多CPU操作系统内核中，关键的开销就是锁的开销。我认为这是一开始的设计导致的，因为一开始，多核CPU并没有出现，单核CPU上的共享保护几乎都是可以用“禁中断”，“禁抢占”来简单实现的，到了多核时代，操作系统同样简单平移到了新的平台，因此同步操作是在单核的基础上后来添加的。
简单来讲，目前的主流操作系统都是在单核年代创造出来的，因此它们都是顺应单核环境的，对于多核环境，可能它们一开始的设计就有问题。
不管怎么说，优化操作的不二法门就是禁止或者尽量减少锁的操作。随之而来的思路就是为共享的关键数据结构创建" 每CPU的缓存“，而这类缓存分为两种类型：
1. 数据通路缓存
比如路由表之类的数据结构，你可以用RCU锁来保护，当然如果为每一个CPU都创建一个本地路由表缓存，也是不错的，现在的问题是何时更新它们，因为所有的缓存都是平级的，因此一种批量同步的机制是必须的。
2. 管理机制缓存
比如slab对象缓存这类，其生命周期完全取决于使用者，因此不存在同步问题，然而却存在管理问题。采用分级cache的思想是好的，这个非常类似于CPU的L1/L2/L3缓存，采用这种平滑的开销逐渐增大，容量逐渐增大的机制，并配合以设计良好的换入/换出等算法，效果是非常明显的。
slab 作为 Linux 操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内碎片，而且处理速度也太慢。而 slab 分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)，每当要申请这样一个对象，slab 分配器就从一个slab 列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。slab 分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
每个 slab 处于三种状态之一：
满的：slab 中的所有对象被标记为使用。
空的：slab 中的所有对象被标记为空闲。
部分：slab 中的对象有的被标记为使用，有的被标记为空闲。
slab 层把不同的对象划分为所谓高速缓存组,其中每个高速缓存组都存放不同类型的对象。每种对象类型对应一个高速缓存。例如,一个高速缓存用于存放进程描述符(struct task 结构的一个空闲链表)，而另一个高速缓存存放索引节点对象(struct inode)。有趣的是, kmalloc() 接口建立在 slab 层之上，使用了一组通用高速缓存。然后，这些高速缓存又被划分为 slab (这也是这个子系统名字的来由)。slab 由一个或多个物理上连续的页组成(一般是一页)。每个高速缓存可以由多个slab组成。每个slab都包含一些对象成员,这里的对象指的是被缓存的数据结构。当内核的某一部分需要一个新的对象时,先从部分满的 slab 中进行分配。如果没有部分满的 slab,就从空的 slab 中进行分配；如果没有空的 slab，就要创建一个 slab 了。这种策略能减少碎片。
与传统的内存管理模式相比， slab 缓存分配器提供了很多优点：
1.内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。
2.slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。
3.slab 分配器还支持通用对象的初始化，从而避免了为同一目的而对一个对象重复进行初始化。
4.slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
有了伙伴系统buddy，就可以以页为单位获取连续的物理内存了，即4K为单位的获取，但如果需要频繁的获取/释放并不大的连续物理内存怎么办，如几十字节几百字节的获取/释放，这样的话用buddy就不太合适了，这就引出了slab。
比如需要一个100字节的连续物理内存，那么内核slab分配器会提供一个相应大小的连续物理内存单元，为128字节大小(不会是整好100字节，而是这个档的一个对齐值，如100字节对应128字节，30字节对应32字节，60字节对应64字节)，这个物理内存实际上还是从伙伴系统获取的物理页；当不再需要这个内存时应该释放它，释放它并非把它归还给伙伴系统，而是归还给slab分配器，这样等再需要获取时无需再从伙伴系统申请，这也就是为什么slab分配器往往会把最近释放的内存(即所谓“热”)分配给申请者，这样效率是比较高的。
slab管理对象的存储方式分为内置和外置，简单的说，内置就是说slab管理部分的内容和实际供使用的内存都在申请到的内存区域中，外置slab管理部分的内容自己再单独申请一个内存区域，和实际申请的内存区域分开，所谓slab管理部分，包括slab结构体、对象描述符，后面会细致描述，这里的if的意思是，当slab初始化完成后，如果创建的“规则”的内存长度大于(PAGE_SIZE >> 3)即512字节时，就使用外置方式，否则使用内置方式，初始化完成之前均使用内置方式。Slab真正有效的部分一个是它提供了分配小段内存的机制，另外它申请的物理内存不是返回给伙伴系统而是驻留在slab内部，这对代码执行高效的使用硬件cache是非常有效的，这是它很关键的一个特征。
伙伴系统
Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型，对于32位系统来说，两级页表足够用了，而在x86_64系统中，用到了四级页表。四级页表分别为：
页全局目录(Page Global Directory)
页上级目录(Page Upper Directory)
页中间目录(Page Middle Directory)
页表(Page Table)
页全局目录包含若干页上级目录的地址，页上级目录又依次包含若干页中间目录的地址，而页中间目录又包含若干页表的地址，每一个页表项指向一个页框。Linux中采用4KB大小的页框作为标准的内存分配单元。
在实际应用中，经常需要分配一组连续的页框，而频繁地申请和释放不同大小的连续页框，必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样，即使这些页框是空闲的，其他需要分配连续页框的应用也很难得到满足。
为了避免出现这种情况，Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。
假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。
页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。
Buddy算法的优缺点：
1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色，但是该算法中，一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并。
2)算法中有一定的浪费现象，伙伴算法是按2的幂次方大小进行分配内存块，当然这样做是有原因的，即为了避免把大的内存块拆的太碎，更重要的是使分配和释放过程迅速。但是他也带来了不利的一面，如果所需内存大小不是2的幂次方，就会有部分页面浪费。有时还很严重。比如原来是1024个块，申请了16个块，再申请600个块就申请不到了，因为已经被分割了。
3)另外拆分和合并涉及到 较多的链表和位图操作，开销还是比较大的。
Buddy(伙伴的定义)：
这里给出伙伴的概念，满足以下三个条件的称为伙伴：
1)两个块大小相同；
2)两个块地址连续；
3)两个块必须是同一个大块中分离出来的；
Buddy算法的分配原理：
假如系统需要4(2*2)个页面大小的内存块，该算法就到free_area[2]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16(2*2*2*2)个页面等分成两份，前一半挂如free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]的链表中，后一半分配出去。假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。
Buddy算法的释放原理：
内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。
slab机制
作为一种内存分配机制，其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内碎片，而且处理速度也太慢。而slab分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)，每当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
Linux 的slab可有三种状态(上文也有述)：
满的：slab 中的所有对象被标记为使用。
空的：slab 中的所有对象被标记为空闲。
部分：slab 中的对象有的被标记为使用，有的被标记为空闲。
slab 分配器首先从部分空闲的slab 进行分配。如没有，则从空的slab 进行分配。如没有，则从物理连续页上分配新的slab，并把它赋给一个cache ，然后再从新slab 分配空间。与传统的内存管理模式相比， slab 缓存分配器提供了很多优点：
1.内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。
2.slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。
3.slab 分配器还支持通用对象的初始化，从而避免了为同一目的而对一个对象重复进行初始化。
4.slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
本文总结自互联网，感谢原作者。
Linux内核的slab来自一种很简单的思想，即事先准备好一些会频繁分配，释放的数据结构。然而标准的slab实现太复杂且维护开销巨大，因此便分化出了更加小巧的slub，因此本文讨论的就是slub，后面所有提到slab的地方，指的都是slub。另外又由于本文主要描述内核优化方面的内容，因此想了解slab细节以及代码实现的请查看源码。
单CPU上单纯的slab
下图给出了单CPU上slab在分配和释放对象时的情景序列：
可以看出，非常之简单，而且完全达到了slab设计之初的目标。
扩展到多核心CPU
现在简单的将上面的模型扩展到多核心CPU，同样差不多的分配序列如下图所示：
可以看到，在只有单一slab的时候，如果多个CPU同时分配对象，冲突是不可避免的，解决冲突的几乎是唯一的办法就是加锁排队，然而这将大大增加延迟，申请单一对象的整个时延从T0开始，到T4结束，这太久了。
多CPU无锁化并行化操作的直接思路-复制给每个CPU一套相同的数据结构。不二法门就是增加“每CPU变量”。对于slab而言，可以扩展成下面的样子：
如果以为这么简单就结束了，那这就太没有意义了。
问题
首先来看一个简单的问题，如果单独的某个CPU的slab缓存没有对象可分配了，但是其它CPU的slab缓存仍有大量空闲对象的情况，如下图所示：
这是可能的，因为对单独一种slab的需求是和该CPU上执行的进程/线程紧密相关的，比如如果CPU0只处理网络，那么它就会对skb等数据结构有大量的需求，对于上图最后引出的问题，如果我们选择从伙伴系统中分配一个新的page(或者pages，取决于对象大小以及slab cache的order)，那么久而久之就会造成slab在CPU间分布的不均衡，更可能会因此吃掉大量的物理内存，这都是不希望看到的。
在继续之前，首先要明确的是，我们需要在CPU间均衡slab，并且这些必须靠slab内部的机制自行完成，这个和进程在CPU间负载均衡是完全不同的，对进程而言，拥有一个核心调度机制，比如基于时间片，或者虚拟时钟的步进速率等，但是对于slab，完全取决于使用者自身，只要对象仍然在使用，就不能剥夺使用者继续使用的权利，除非使用者自己释放。因此slab的负载均衡必须设计成合作型的，而不是抢占式的。
好了。现在我们知道，从伙伴系统重新分配一个page(s)并不是一个好主意，它应该是最终的决定，在执行它之前，首先要试一下别的路线。
现在引出第二个问题，如下图所示：
谁也不能保证分配slab对象的CPU和释放slab对象的CPU是同一个CPU，谁也不能保证一个CPU在一个slab对象的生命周期内没有分配新的page(s)，这期间的复杂操作谁也没有规定。这些问题该怎么解决呢？事实上，理解了这些问题是怎么解决的，一个slab框架就彻底理解了。
问题的解决-分层slab cache
无级变速总是让人向往。如果一个CPU的slab缓存满了，直接去抢同级别的别的CPU的slab缓存被认为是一种鲁莽且不道义的做法。那么为何不设置另外一个slab缓存，获取它里面的对象不像直接获取CPU的slab缓存那么简单且直接，但是难度却又不大，只是稍微增加一点消耗，这不是很好吗？
事实上， CPU的L1，L2，L3 cache不就是这个方案设计的吗？这事实上已经成为cache设计的不二法门。这个 设计思想同样作用于slab，就是Linux内核的slub实现， 现在可以给出概念和解释了。
Linux kernel slab cache：一个分为3层的对象cache模型。
Level 1 slab cache：一个空闲对象链表，每个CPU一个的独享cache，分配释放对象无需加锁。
Level 2 slab cache：一个空闲对象链表，每个CPU一个的共享page(s) cache，分配释放对象时仅需要锁住该page(s)，与Level 1 slab cache互斥，不互相包容。
Level 3 slab cache：一个page(s)链表，每个NUMA NODE的所有CPU共享的cache，单位为page(s)，获取后被提升到对应CPU的Level 1 slab cache，同时该page(s)作为Level 2的共享page(s)存在。
共享page(s)：该page(s)被一个或者多个CPU占有，每一个CPU在该page(s)上都可以拥有互相不充图的空闲对象链表，该page(s)拥有一个唯一的Level 2 slab cache空闲链表，该链表与上述一个或多个Level 1 slab cache空闲链表亦不冲突，多个CPU获取该Level 2 slab cache时必须争抢，获取后可以将该链表提升成自己的Level 1 slab cache。
该 slab cache的图示如下：
其行为如下图所示：
2个场景
对于常规的对象分配过程，下图展示了其细节：
事实上，对于多个CPU共享一个page(s)的情况，还可以有另一种玩法，如下图所示：
伙伴系统
前面简短的体会了Linux内核的slab设计，不宜过长，太长了不易理解；但是最后，如果Level 3也没有获取page(s)，那么最终会落到终极的伙伴系统，伙伴系统是为了防内存分配碎片化的，所以它尽可能地做两件事：
1.尽量分配尽可能大的内存
2.尽量合并连续的小块内存成一块大内存
可以通过下面的图解来理解上面的原则：
注意，本文是关于优化的，不是伙伴系统的科普，所以我假设大家已经理解了伙伴系统。
鉴于slab缓存对象大多数都是不超过1个页面的小结构(不仅仅slab系统，超过1个页面的内存需求相比1个页面的内存需求，很少)，因此会有大量的针对1个页面的内存分配需求。
从伙伴系统的分配原理可知，如果持续大量分配单一页面，会有大量的order大于0的页面分裂成单一页面，在单核心CPU上，这不是问题，但是在多核心CPU上，由于每一个CPU都会进行此类分配，而伙伴系统的分裂，合并操作会涉及大量的链表操作，这个锁开销是巨大的，因此需要优化！
Linux内核对伙伴系统针对单一页面的分配需求采取的批量分配“每CPU单一页面缓存”的方式！每一个CPU拥有一个单一页面缓存池，需要单一页面的时候，可以无需加锁从当前CPU对应的页面池中获取页面。而当池中页面不足时，系统会批量从伙伴系统中拉取一堆页面到池中，反过来，在单一页面释放的时候，会择优将其释放到每CPU的单一页面缓存中。
为了维持“每CPU单一页面缓存”中页面的数量不会太多或太少(太多会影响伙伴系统，太少会影响CPU的需求)，系统保持了两个值，当缓存页面数量低于low值的时候，便从伙伴系统中批量获取页面到池中，而当缓存页面数量大于high的时候，便会释放一些页面到伙伴系统中。
小结
多CPU操作系统内核中，关键的开销就是锁的开销。我认为这是一开始的设计导致的，因为一开始，多核CPU并没有出现，单核CPU上的共享保护几乎都是可以用“禁中断”，“禁抢占”来简单实现的，到了多核时代，操作系统同样简单平移到了新的平台，因此同步操作是在单核的基础上后来添加的。
简单来讲，目前的主流操作系统都是在单核年代创造出来的，因此它们都是顺应单核环境的，对于多核环境，可能它们一开始的设计就有问题。
不管怎么说，优化操作的不二法门就是禁止或者尽量减少锁的操作。随之而来的思路就是为共享的关键数据结构创建" 每CPU的缓存“，而这类缓存分为两种类型：
1. 数据通路缓存
比如路由表之类的数据结构，你可以用RCU锁来保护，当然如果为每一个CPU都创建一个本地路由表缓存，也是不错的，现在的问题是何时更新它们，因为所有的缓存都是平级的，因此一种批量同步的机制是必须的。
2. 管理机制缓存
比如slab对象缓存这类，其生命周期完全取决于使用者，因此不存在同步问题，然而却存在管理问题。采用分级cache的思想是好的，这个非常类似于CPU的L1/L2/L3缓存，采用这种平滑的开销逐渐增大，容量逐渐增大的机制，并配合以设计良好的换入/换出等算法，效果是非常明显的。
slab 作为 Linux 操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内碎片，而且处理速度也太慢。而 slab 分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)，每当要申请这样一个对象，slab 分配器就从一个slab 列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。slab 分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
每个 slab 处于三种状态之一：
满的：slab 中的所有对象被标记为使用。
空的：slab 中的所有对象被标记为空闲。
部分：slab 中的对象有的被标记为使用，有的被标记为空闲。
slab 层把不同的对象划分为所谓高速缓存组,其中每个高速缓存组都存放不同类型的对象。每种对象类型对应一个高速缓存。例如,一个高速缓存用于存放进程描述符(struct task 结构的一个空闲链表)，而另一个高速缓存存放索引节点对象(struct inode)。有趣的是, kmalloc() 接口建立在 slab 层之上，使用了一组通用高速缓存。然后，这些高速缓存又被划分为 slab (这也是这个子系统名字的来由)。slab 由一个或多个物理上连续的页组成(一般是一页)。每个高速缓存可以由多个slab组成。每个slab都包含一些对象成员,这里的对象指的是被缓存的数据结构。当内核的某一部分需要一个新的对象时,先从部分满的 slab 中进行分配。如果没有部分满的 slab,就从空的 slab 中进行分配；如果没有空的 slab，就要创建一个 slab 了。这种策略能减少碎片。
与传统的内存管理模式相比， slab 缓存分配器提供了很多优点：
1.内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。
2.slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。
3.slab 分配器还支持通用对象的初始化，从而避免了为同一目的而对一个对象重复进行初始化。
4.slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
有了伙伴系统buddy，就可以以页为单位获取连续的物理内存了，即4K为单位的获取，但如果需要频繁的获取/释放并不大的连续物理内存怎么办，如几十字节几百字节的获取/释放，这样的话用buddy就不太合适了，这就引出了slab。
比如需要一个100字节的连续物理内存，那么内核slab分配器会提供一个相应大小的连续物理内存单元，为128字节大小(不会是整好100字节，而是这个档的一个对齐值，如100字节对应128字节，30字节对应32字节，60字节对应64字节)，这个物理内存实际上还是从伙伴系统获取的物理页；当不再需要这个内存时应该释放它，释放它并非把它归还给伙伴系统，而是归还给slab分配器，这样等再需要获取时无需再从伙伴系统申请，这也就是为什么slab分配器往往会把最近释放的内存(即所谓“热”)分配给申请者，这样效率是比较高的。
slab管理对象的存储方式分为内置和外置，简单的说，内置就是说slab管理部分的内容和实际供使用的内存都在申请到的内存区域中，外置slab管理部分的内容自己再单独申请一个内存区域，和实际申请的内存区域分开，所谓slab管理部分，包括slab结构体、对象描述符，后面会细致描述，这里的if的意思是，当slab初始化完成后，如果创建的“规则”的内存长度大于(PAGE_SIZE >> 3)即512字节时，就使用外置方式，否则使用内置方式，初始化完成之前均使用内置方式。Slab真正有效的部分一个是它提供了分配小段内存的机制，另外它申请的物理内存不是返回给伙伴系统而是驻留在slab内部，这对代码执行高效的使用硬件cache是非常有效的，这是它很关键的一个特征。
伙伴系统
Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型，对于32位系统来说，两级页表足够用了，而在x86_64系统中，用到了四级页表。四级页表分别为：
页全局目录(Page Global Directory)
页上级目录(Page Upper Directory)
页中间目录(Page Middle Directory)
页表(Page Table)
页全局目录包含若干页上级目录的地址，页上级目录又依次包含若干页中间目录的地址，而页中间目录又包含若干页表的地址，每一个页表项指向一个页框。Linux中采用4KB大小的页框作为标准的内存分配单元。
在实际应用中，经常需要分配一组连续的页框，而频繁地申请和释放不同大小的连续页框，必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样，即使这些页框是空闲的，其他需要分配连续页框的应用也很难得到满足。
为了避免出现这种情况，Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。
假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。
页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。
Buddy算法的优缺点：
1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色，但是该算法中，一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并。
2)算法中有一定的浪费现象，伙伴算法是按2的幂次方大小进行分配内存块，当然这样做是有原因的，即为了避免把大的内存块拆的太碎，更重要的是使分配和释放过程迅速。但是他也带来了不利的一面，如果所需内存大小不是2的幂次方，就会有部分页面浪费。有时还很严重。比如原来是1024个块，申请了16个块，再申请600个块就申请不到了，因为已经被分割了。
3)另外拆分和合并涉及到 较多的链表和位图操作，开销还是比较大的。
Buddy(伙伴的定义)：
这里给出伙伴的概念，满足以下三个条件的称为伙伴：
1)两个块大小相同；
2)两个块地址连续；
3)两个块必须是同一个大块中分离出来的；
Buddy算法的分配原理：
假如系统需要4(2*2)个页面大小的内存块，该算法就到free_area[2]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16(2*2*2*2)个页面等分成两份，前一半挂如free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]的链表中，后一半分配出去。假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。
Buddy算法的释放原理：
内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。
slab机制
作为一种内存分配机制，其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内碎片，而且处理速度也太慢。而slab分配器是基于对象进行管理的，相同类型的对象归为一类(如进程描述符就是一类)，每当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
Linux 的slab可有三种状态(上文也有述)：
满的：slab 中的所有对象被标记为使用。
空的：slab 中的所有对象被标记为空闲。
部分：slab 中的对象有的被标记为使用，有的被标记为空闲。
slab 分配器首先从部分空闲的slab 进行分配。如没有，则从空的slab 进行分配。如没有，则从物理连续页上分配新的slab，并把它赋给一个cache ，然后再从新slab 分配空间。与传统的内存管理模式相比， slab 缓存分配器提供了很多优点：
1.内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。
2.slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。
3.slab 分配器还支持通用对象的初始化，从而避免了为同一目的而对一个对象重复进行初始化。
4.slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
本文总结自互联网，感谢原作者。