Linux的一个核心就是内存的分配管理，在现代的linux中，综合了不同的算法来针对不同的对象（如不同大小）来进行分配内存。其中针对小对象使用了slab算法。
对于这个算法，网上大多数博客都针对Linux内核实现和工程化进行了些阐述，本文只针对94年发表的原始版算法进行一些剖析。
（因为看Fatcache顺路看的，后来才发现没啥关联……
SLAB
在内存分配的过程中，总是伴随一些常量（如mutex）的初始化。正常的一个对象的生命周期为：
- 分配内存空间（allocation）
- 初始化常量（construction）
- 当引用为0，把所有内存reclaim，返还给系统
而slab期待的是，增加一个central allocator，来管理一个额外的cache，减少反复的construct，deconstruct，只有当系统需要内存的时候，才真正做deconstruct，从cache里拿内存。Slab也提出了一套新的数据结构来实现这个效果。
central allocator有以下优越性：
- debug方便
- 减少同问题类似管理的资源开销
- 进程来管理的话没办法知道system的情况
Slab的优点：
- 轻量的GC引擎：使用引用计数来代替复杂的位图等方法
- 高效地分配内存：只从一个freelist中取出放回，更新计数。
- 防止严重的外部碎片问题：对象都以同样的类型进行存储，所以有一样的lifetime distribution，从而避免某一个长时间allocation占用了整个page。~~？~~
- 内部碎片问题的影响很小：Slab的机制决定，单个slab里n个buffer只有最后一个会有未使用的空间，即最坏$\frac{1}{n}$的内部碎片。越大的Slab的内部碎片越小，但增大了外部碎片，成了一个trade off。
Slab制定了一些接口规范，主要是简化client的操作，增加central allocator获取的信息，不表。
Slab是Slab allocator操作的基础单位，申请和释放的基本单位。一个slab内部有多个page。
逻辑结构
slab allocator的基础数据结构如下图。最上层是一个由kmem_slab组成的双向循环链表。每个kmem_slab和多个kmem_bufctl双向链接，每个kmem_bufctl存储对应buffer的相关元数据（buffer address, freelist linkage?）。
对于大对象来说，在内存的结构就像是这样的逻辑结构
For Small Objects
对于小于$\frac{1}{8}$page的object们，会采用简化的方法来存储。把kmem_slab的元数据存在一个page的末尾，前面等分作buffer。这里的buf也做bufctl的功能，防止bufctl在这种场景下占用和实际buf相同大小的空间了。
Freelist
cache的freelist是部分排序的：满的slab->半满slab->空slab，cache的freelist指针指向第一个半满slab。cache内部的freelist管理也是类似的。这样的两级freelist可以简化释放内存的操作。
Reclaim
在free对象的时候，为了实现cache，并不会把引用计数到0的直接返还给系统，而是把这个slab移动到freelist的末尾。
直到系统请求内存，slab allocator才会返还15s外free的内存，以此防止抖动。
Hardware Cache Effects
本文提出了一个在之前没有被注意到的硬件上的因素对于cache的影响，即buffer的地址分布，同时其也会影响总线上的负载均衡。
Slab Coloring
Slab提出了一个非常简单的策略，通过多余（因为align等）的存储空间来对slabs进行“偏移”，即着色coloring操作：对slab在空间上做偏移X，下一个slab做偏移2X……让不同slab中的对象从不同的位置开始，当然空间上会造成一些额外使用
偏移的意义在于充分利用硬件高速缓存行，把原来密集在某一个区域的数据，偏移分散到整个空间上，一个slab里的不同对象不会互相flush硬件缓存。
另外，在cache footprint上，slab这样的segregated-storage allocator相对sequential-fit allocator和buddy methods不需要做太多search的操作，而是by computation or table lookup，TLB miss和cache miss都可以降低。在小对象的情况下，单page内也足够放下一个slab相关的绝大部分信息。
相关
碎片问题
内存管理中一个常见的讨论点就是碎片问题:
- 内部碎片
指的是在进程内部中无法被使用的内存空间。e.g. 7M的进程拿到了8M的空间 - 外部碎片
指的是在未分配的内存空间中，由于size过小，无法分配给申请进程。e.g. 某空间中有一个1M的空间，但所有新进程所需的内存都大于1M。
slab Calcification
使用slab的好处是减轻allocation的开销，一个隐患是钙化问题（Calcification）。就是当可用空间告急要做回收，原始策略是只在本地相同slab上做，但本slab上没有空余空间，而某一些slab上有可剔除，就会出现明显浪费。这是个老问题，解决的策略关注在怎么跨slab做balance & remove。
Buddy memory allocation 伙伴算法
这个算法的思想被用在linux kernel的大对象内存分配上。
Buddy memory allocation是一个power of two algorithm，即内存每块为$2^n$的空间。通过搭配伙伴，来指定两两的同等大小内存块为一组伙伴。如下图所示，相同大小的块组成一个链，按照大小归到数组里管理。
当free mem的时候，寻找一组伙伴（即连续的另一半）都free时，可以拼凑组成2倍的上一级大小的free内存块，没有则直接入链首。
当需要allocation的时候，从大小匹配的链里寻找，如果找不到，就去大一级大小的链找找一个，切为两半，当做小的用。
SLUB
SLUB是基于Slab的一个改进思路……
Refer
Slab Allocator – linux kernel org
Kernel Memory Allocation – Mike Murphy on Youtube
Chapter 8. Slab Allocator – Understanding the Linux Virtual Memory Manager