这篇slub算法对具体实现讲得很生动。图画的是真不错，我就偷懒不画这么好看了。大家自行前往参考。

此链接中描述的，我就不再多讲了。我来讲点上面没有的。

slub的运行最关键的两个函数是___slab_alloc()和__slab_free()。如果能看懂这两个，那基本上就是对slub了解了。一下的讲述都基于个人理解，若有偏差，欢迎指正。

你的样子

slab的原意是：厚板，大块。也就是我们从内存中，预先挖下一块，按照我们的要求安放好。等到要用的时候可以拿出来用。在上面给大家指出的这个链接上，作者的比喻更生动。slub像是零售商，从伙伴系统上批发内存，再零售出去。

更有意思的是，零售商有营业厅和仓库。营业厅只保留一个slab，当这个slab用完的时候，才从仓库里取出一个，并把这个营业厅里的下架。

好了，我唠叨了半天估计你也烦了。那我想说的是什么呢？我想说的是，一直在说slab/slub，那它究竟长什么样子呢？也就是我们所说的这一块是什么呢？其实他就是page结构体。

如果说kmem_cache结构体是一个零售商，那page结构体就是真的要上架下架的那个slab。

内核中很巧妙的复用了page结构体来保存slab所需要的信息。

struct page +------------------------------+ |slab_cache | | (struct kmem_cache *) | +------------------------------+ |freelist | first free object (list head) | (viod *) | +------------------------------+ |objects | number of objects in Page |inuse | number of objects used in cpu_slab |frozen | frozen means in cpu_slab | (unsigned ) | +------------------------------+

如果觉得烧脑，我们可以先只看前两个部分: slab_cache, freelist。

slab_cache比较好理解，就是你这商品到底是哪个零售商的。freelist是一个链表头，指向了还剩下可用的内存。

因为每一次上架不止上一个，而是上架一大块。所以我们需要有个链表来指示还剩哪些。那为啥不用数组呢？因为如果是数组，我们就要用bitmap来标示用了哪些，还剩哪些。每次分配也需要搜索，每次归还还需要写回。这个操作是费时的，且容易引入竞争。

而内核的实现非常巧妙的使用了单链表。分配的时候直接取，归还的时候插入链表头部。操作简单，O(1)的复杂度。通过cmpxchg还做到了无锁化。另外，因为是插入链表头部，下次要用还会被优先取到，相对插入别的地方更不容易发生cache miss。

Brilliant Design

货架的样子

我们沿用零售商的比喻。现在便利店已经是满大街了。同样一种商品可以在不同的地区的便利店内买到。甚至我在张江门店买的梦龙和在明光村门店买的梦龙是一模一样的。那这是怎么做到的呢？每个店都上架一套呗。

内核中为了满足每个cpu上的需求，在每个cpu上都上架了一套。你可以理解为在每个cpu上都开了个门店。当进程在这个cpu上运行时，直接向本cpu的门店去拿内存，而不是统一去厂家拿货。这样减少了竞争。

所以我们可以理解为真正上架的是这个cpu_slab，而page结构体则是在“库存”内的。或者把cpu_slab比喻成那个货架，可能更好理解一些。

我们来看看这个上架的过程：

kmem_cache_cpu +------------------------------+ |freelist | first free object (list head) | (void *) | +------------------------------+ |page | | (struct page*) | | +-------------------------+ | |freelist | NULL | |objects | | |inuse | | |frozen | 1 | | (unsigned) | +----+-------------------------+

简单来讲有两个动作：

把链表头给了cpu_slab，而page->freelist则清零frozen置1

第一个动作其实挺形象的。东西上架了嘛，自己这就空了，放到货架上了。

隐含的两条链表

东西上架了，是不是万事大吉了呢？没。

最要命的我们开的不是小卖部，其实更像一个图书馆，或者是租赁中心。东西总有一天是要回来的！如果只是简单的还回来还好说，我们还开启了一个高级功能，异地还！就好像神州租车，从上海租车开到了黄山，太累了，打算坐火车回来了。行，车就还在苏州吧～

在系统中这是一种什么情况呢？比如进程在cpu1上申请了内存，然后跑到cpu2上去了。这个时候要还，就是一个异地还。

那这样问题来了，链表头在percpu变量上，我怎么知道你刚才是在哪里借的？嗯，这时候就是两条链表的作用了。

这两条链表分别是：

cpu_slab->freelistpage->freelist

如果是本地还，则使用第一个链表。如果是异地还，就使用第二个链表。真是聪明。

嗯，完了么？还差一点点。

既然现在有两个链表了，所以每次去营业厅买东西，除了要看货架上有没有货，还要去看看同一批次的货物有没有异地还回来的。如果有，就把这部分上架并借出。这部分在get_freelist()中实现。有兴趣的可以仔细研读代码。

下架时的三种状态

当我们要下架一个商品的时候，比如说一盒子的巧克力，我们会遇到三种情况。

满的空的部分的

满的说明这货不好卖，或者前一次上架太多了，实际上没有想象的好卖。空的说明卖断档了，得赶紧补充。部分的则说明还行。

按照这个思路，slub也有对应的三种状态。不过含义上稍有不同。

空的，没人在用，可以释放满的，全用完了部分的

可以看出，表达上略有不同。不过概念是类似的。

好了，那这个在哪里可以看出来判断呢？ 在函数deactivate_slab()中。对了，这就是那个下架slub的函数了。

那怎么判断呢？还记得上面提到的链表么？对啊，就是判断page上的链表状态。

表头是空：全都分配出去了表头非空：现在还有空闲的

空闲的状态可以分为两种，部分空闲和全部空闲。这个仅仅判断链表是不行了。所以内核在page结构体中有inuse字段表示卖出（借出）了多少。

inuse == 0， 一个也没卖出（借出）其他，卖出（借出）了部分

好了，slub的三种状态看完了，不知道你能说清楚么？

主动下架和被动下架

出来混总是要还的。

东西卖得好自然上架，东西卖的不好自然就要下架。你说是不是。同样是下架，也分两种：主动下架和被动下架。这是我自己发明出来的词儿，也不知道对不对。先来解释一下：

主动下架：卖太好了，卖空了，把那盒子给我下下来被动下架：卖得不好，或者得换个地儿，哥们儿挪个地儿

对应slub

主动下架：用完了，得换一个slub被动下架：这个不合适，得换一个slub

对应具体函数：

主动下架：get_freelist()被动下架：deactivate_slab()

slub的另一种状态

刚才我们说了slub下架时的三种状态，现在我们要讲讲slub的另一个状态指示 – 是否上架。

刚才我们讲了上架下架，也讲了page的两条链表。那怎么表示这种状态，告诉管理者这个商品到底有没有上架呢？内核中巧妙的在page结构体中增加了一位frozen来表示。

frozen == 1，上架了frozen == 0，下架了

你看，是不是很清楚。

那些神游的slub

有些事渐渐远去无法记得 有些人渐渐模糊无法记清 有些slub分配出去后就烟消云散各奔东西

有意思的调试信息

在学习slub的过程中，我添加了不少的调试信息来验证我的理解是不是正确。在这里也分享给大家，这样可以看看自己的理解是不是符合实际情况哦。

diff --git a/mm/slub.c b/mm/slub.c index d677853..77e578b 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -1578,6 +1580,8 @@ static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node) kmemcheck_mark_unallocated_pages(page, pages); } + if ((page->lru.prev != LIST_POISON2) || (page->lru.next != LIST_POISON1)) + printk_once(KERN_ERR "ywtest: %s just allocated page still on list\n", __func__); page->objects = oo_objects(oo); order = compound_order(page); @@ -2068,9 +2072,11 @@ static void deactivate_slab(struct kmem_cache *s, struct page *page, new.frozen = 0; - if (!new.inuse && n->nr_partial >= s->min_partial) + if (!new.inuse && n->nr_partial >= s->min_partial) { + if (!new.freelist) + printk_once(KERN_ERR "ywtest: %s slab free with NULL freelist\n", __func__); m = M_FREE; - else if (new.freelist) { + } else if (new.freelist) { m = M_PARTIAL; if (!lock) { lock = 1; @@ -2093,6 +2099,8 @@ static void deactivate_slab(struct kmem_cache *s, struct page *page, spin_lock(&n->list_lock); } } + if (m == M_NONE) + printk_once(KERN_ERR "ywtest: %s slab in NON state\n", __func__); if (l != m) { @@ -2529,6 +2537,8 @@ static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node, struct page *page; page = c->page; + if (!page && c->freelist) + printk_once(KERN_ERR "ywtest: c->page is NULL while c->freelist not\n"); if (!page) goto new_slab; redo: @@ -2590,6 +2600,8 @@ static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node, page = c->page = slub_percpu_partial(c); slub_set_percpu_partial(c, page); stat(s, CPU_PARTIAL_ALLOC); + if (c->freelist) + printk_once(KERN_ERR "ywtest: NON-NULL freelist\n"); goto redo; } @@ -2839,6 +2851,9 @@ static void __slab_free(struct kmem_cache *s, struct page *page, * We can defer the list move and instead * freeze it. */ + if (new.objects != (new.inuse + 1)) + printk_once(KERN_ERR "ywtest: %s not a full slab\n", __func__); + new.frozen = 1; } else { /* Needs to be taken off a list */ @@ -2881,6 +2896,9 @@ static void __slab_free(struct kmem_cache *s, struct page *page, return; } + if (was_frozen) + printk_once(KERN_ERR "ywtest: %s still has was_frozen\n", __func__); + if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) goto slab_empty;