前言

这学期有门课需要分析linux内核代码的版本变化，我被分到了内存管理题目。
clone内核仓库下来看了看统计数据，整个内核千万行，memory manage部分十万行，很夸张的规模，单单git clone就把我服务器2G内存撑爆了，设了swap才成功……
原本想看页表和mmzone部分，但因为涉及体系结构，文件太多理不出头绪，最后目标锁定在slab/slob/slub分配器上，都只有一个.c文件，slab四千行、slub六千行，于是我决定去看六百行的slob……
linux是历经检验的项目，单单一个六百行的slob自v2.6.11至今的commit log也有四千多行。本文的分析有些粗略，不重要的变化以及过多涉及系统其他模块的部分将不会叙述，权当抛砖引玉。

slob的引入

小内存分配器的引入是为了解决内核申请小内存的问题，最初版本只有slab分配器，《深入Linux内核架构》一书给出了详细叙述：

内核也必须经常分配内存，但无法借助于标准库的函数。上面描述的伙伴系统支持按页分配内存，但这个单位太大了。……显然的解决方案是将页拆分为更小的单位，可以容纳大量的小对象。
为此必须引入新的管理机制，这会给内核带来更大的开销。为最小化这个额外负担对系统性能的影响，该管理层的实现应该尽可能紧凑，以便不要对处理器的高速缓存和TLB带来显著影响。同时，内核还必须保证内存利用的速度和效率。……
所谓slab分配，证明对许多种类工作负荷都非常高效。它是由Sun公司的一个雇员Jeff Bonwick，在Solaris 2.4中设计并实现的。……
提供小内存块不是slab分配器的唯一任务。由于结构上的特点，它也用作一个缓存，主要针对经常分配并释放的对象。通过建立slab缓存，内核能够储备一些对象，供后续使用……slab分配器将释放的内存块保存在一个内部列表中，并不马上返回给伙伴系统。在请求为该类对象分配一个新实例时，会使用最近释放的内存块。这有两个优点。首先，由于内核不必使用伙伴系统算法，处理时间会变短。其次，由于该内存块仍然是“新”的，因此其仍然驻留在CPU高速缓存的概率较高。

借助slab分配器，内核得以实现kmalloc和kmem_cache_create函数，实现对普通对象和缓存对象的创建。
在2.6版本中linux增加了两个替代分配器：

• slob以简单链表实现，代码量很少，适用于小型系统；
• slub在slab基础上做了优化，在大型系统上有更好的性能表现。

本文将对slob分配器进行分析。

slob初始版本及原理

基本结构

slob是在内核v2.6.16引入的，当时只有四百多行，初始commit中开发者介绍：

SLOB is a traditional K&R/UNIX allocator with a SLAB emulation layer, similar to the original Linux kmalloc allocator that SLAB replaced. It's signicantly smaller code and is more memory efficient. But like all similar allocators, it scales poorly and suffers from fragmentation more than SLAB, so it's only appropriate for small systems.

slob分配内存的最小粒度称为unit，连续的unit被组织为block，内存因此被划分为一系列block，block内部空间是连续的。slob分配器将所有可供分配的block组织为一个单向循环链表，按照首地址由小到大排列。

struct slob_block {
    int units;
    struct slob_block *next;
};
typedef struct slob_block slob_t;

#define SLOB_UNIT sizeof(slob_t)

可以看出slob直接将slob_t结构体的大小作为unit大小，在32位体系结构上为8字节，64位结构上因为结构体对齐是16字节。

在每个block中，第一个unit存储的就是描述这块block的slob_t，因此slob_t和对应block首地址是相同的，units变量代表block大小（包含头部的这个slob_t），next是链表中下一个slob_t的地址（同时也是下一个block的首地址）。按照这样的设计，显然每个block的units数至少为1.

初始化

slob_t组成一个单向循环链表，初始只有一个哑节点：

static slob_t arena = { .next = &arena, .units = 1 };
static slob_t *slobfree = &arena;

因此最初向slob申请内存时没有空闲的block，slob需要向伙伴系统申请一个空闲页面，然后调用slob_free为该页面创建一个slob_t，这个页面因此成为一个大的block：

if (cur == slobfree) {
    // ...
    cur = (slob_t *)__get_free_page(gfp);
    // ...
    slob_free(cur, PAGE_SIZE);
    // ...
}

slob_free(block, size)函数会将block的大小设为size，然后在slob_t链表中找到合适的位置插入block对应的slob_t，如果这个块与前/后块在地址空间上紧邻，还会执行合并。

如何找到合适的插入位置呢？前面提到链表按照block首地址由小到大排列，又因为是循环链表，如果将首地址最大的block定义为队尾，则对它来说有cur >= cur->next，而对其他block均有cur <= cur->next。于是注意到以下几点：

• 从循环链表的任意节点进入，遍历一周必然能找到b的唯一合适插入位置，记这个位置是在节点cur之后，即应设cur->next = b
• 如果cur不是队尾，则一定满足b > cur && b < cur->next
• 如果cur是队尾，则一定满足cur >= cur->next && (b > cur || b < cur->next)，前半部分是队尾的性质，后半部分表明b应在“队尾之后”或“队头之前”

从而可以写出循环：

for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next)
    if (cur >= cur->next && (b > cur || b < cur->next))
        break;

循环只有在找到合适的cur后才会结束，之后分别判断b是否需要与cur、cur->next合并，即为完整的slob_free函数：

static void slob_free(void *block, int size)
{
    slob_t *cur, *b = (slob_t *)block;
    unsigned long flags;

    if (!block)
        return;

    if (size)
        b->units = SLOB_UNITS(size);

    /* Find reinsertion point */
    spin_lock_irqsave(&slob_lock, flags);
    for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next)
        if (cur >= cur->next && (b > cur || b < cur->next))
            break;

    if (b + b->units == cur->next) {
        b->units += cur->next->units;
        b->next = cur->next->next;
    } else
        b->next = cur->next;

    if (cur + cur->units == b) {
        cur->units += b->units;
        cur->next = b->next;
    } else
        cur->next = b;

    slobfree = cur;

    spin_unlock_irqrestore(&slob_lock, flags);
}

函数的最后将slobfree，即循环的入口点设为了cur，注释没有说明原因，猜测可能是因为相邻内存的释放行为大概率也相邻，入口设为cur可以加快与b相邻内存被释放时的查找速度。v2.6.23有一段类似代码解释说：

Improve fragment distribution and reduce our average search time by starting our next search here. (see Knuth vol 1, sec 2.5, pg 449)

感兴趣的读者可以自行查阅。

内存分配——kmalloc

我们知道malloc实际分配的空间比申请者可见的要大，因为头部存储了这块空间的大小等信息，这也是free时不需要指定大小的原因。kmalloc也是如此，前面提到block头部有一个unit用来存储slob_t，当申请分配x个unit时，实际会占用一个units数为(x+1)的block，然后返回后x个unit。

kmalloc根据申请空间的大小决定是采用常规分配方法还是被称为bigblock的分配方法，因为bigblock在后续版本中被废弃，这里不再展示：

void *kmalloc(size_t size, gfp_t gfp)
{
    slob_t *m;
    bigblock_t *bb;
    unsigned long flags;

    if (size < PAGE_SIZE - SLOB_UNIT) {
        m = slob_alloc(size + SLOB_UNIT, gfp, 0);
        return m ? (void *)(m + 1) : 0;
    }

    // big block part ...
}

可以看出kmalloc多申请了一个unit的空间，并有1个unit的返回偏移。下面看核心逻辑slob_alloc：

slob_alloc从slobfree开始，以first fit方式寻找满足分配需求的block并返回。如果block大小恰好等于需求，则将该block从空闲链表中删去；否则分配后剩余的空间将形成一个新block。如果所有block都不满足要求，则需要从伙伴系统申请新的内存页，如初始化一节所述。

slob_alloc还有一些对齐方面的工作，完整代码如下：

static void *slob_alloc(size_t size, gfp_t gfp, int align)
{
    slob_t *prev, *cur, *aligned = 0;
    int delta = 0, units = SLOB_UNITS(size);
    unsigned long flags;

    spin_lock_irqsave(&slob_lock, flags);
    prev = slobfree;
    for (cur = prev->next; ; prev = cur, cur = cur->next) {
        if (align) {
            aligned = (slob_t *)ALIGN((unsigned long)cur, align);
            delta = aligned - cur;
        }
        if (cur->units >= units + delta) { /* room enough? */
            if (delta) { /* need to fragment head to align? */
                aligned->units = cur->units - delta;
                aligned->next = cur->next;
                cur->next = aligned;
                cur->units = delta;
                prev = cur;
                cur = aligned;
            }

            if (cur->units == units) /* exact fit? */
                prev->next = cur->next; /* unlink */
            else { /* fragment */
                prev->next = cur + units;
                prev->next->units = cur->units - units;
                prev->next->next = cur->next;
                cur->units = units;
            }

            slobfree = prev;
            spin_unlock_irqrestore(&slob_lock, flags);
            return cur;
        }
        if (cur == slobfree) {
            spin_unlock_irqrestore(&slob_lock, flags);

            if (size == PAGE_SIZE) /* trying to shrink arena? */
                return 0;

            cur = (slob_t *)__get_free_page(gfp);
            if (!cur)
                return 0;

            slob_free(cur, PAGE_SIZE);
            spin_lock_irqsave(&slob_lock, flags);
            cur = slobfree;
        }
    }
}

内存释放——kfree

忽略对bigblock的处理后，kfree就是对slob_free的简单调用。申请者通过kmalloc获取的、以及之后传递给kfree的，都是偏移一个unit之后的地址，kfree需要计算出偏移前的地址作为slob_free的block参数，size参数设为0，表示要求slob_free通过第一个unit中的信息自行判断大小：

void kfree(const void *block)
{
    // big block part ...
    slob_free((slob_t *)block - 1, 0);
    return;
}

其他内容

作为轻量级分配器，slob只是模拟了slab的kmem_cache系列接口，并没有实际实现缓存对象机制，而是直接调用slob_alloc、slob_free。

slob还提供了__alloc_percpu、free_percpu，这部分和核心逻辑关系不大，不再叙述。

block和page结构的变动——v2.6.23

如何查看版本变化

v2.6.16-v2.6.23期间slob进行了很多优化，这里先介绍一些查看版本变化的方法：

• git tag查看所有版本号，git show v2.6.23查看指定版本信息
• git log --stat mm/slob.c查看指定文件commit log，--stat表示额外显示增删行的统计信息
• git diff v2.6.16 v2.6.23 mm/slob.c两个版本中对比指定文件在，推荐把git的difftool设为vscode，然后改用git difftool v2.6.16 v2.6.23 mm/slob.c，显示更友好

改变slob_t结构

block描述方法产生了变化：

// -----v2.6.16-----
struct slob_block {
    int units;
    struct slob_block *next;
};
// ---end v2.6.16---

// -----v2.6.23-----
#if PAGE_SIZE <= (32767 * 2)
typedef s16 slobidx_t;
#else
typedef s32 slobidx_t;
#endif

struct slob_block {
    slobidx_t units;
};
// ---end v2.6.23---

typedef struct slob_block slob_t;
#define SLOB_UNIT sizeof(slob_t)

units字段使用了更小的数据类型，使用了一种新的方法来表示next。

• 在新的结构中，规定每个内存页拥有一个独立的block链表
• 如果block的units数大于1，将使用两个unit存储信息：第一个unit存储units数，第二个unit存储下一block在页中的偏移units数
• 如果block的units数为1，只使用一个unit，存储下一block偏移units的相反数

即：

// set block
static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
{
    slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
    slobidx_t offset = next - base;

    if (size > 1) {
        s[0].units = size;
        s[1].units = offset;
    } else
        s[0].units = -offset;
}

// get block size
static slobidx_t slob_units(slob_t *s)
{
    if (s->units > 0)
        return s->units;
    return 1;
}

// get next block
static slob_t *slob_next(slob_t *s)
{
    slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
    slobidx_t next;

    if (s[0].units < 0)
        next = -s[0].units;
    else
        next = s[1].units;
    return base+next;
}

当PAGE\_SIZE\lt 2^{15}*2时，slobidx_t被设为16位整数，unit大小为2字节，一页包含的unit数量小于2^{15}，从而block的units数和偏移量都在16位整数的表示范围[-2^{15},2^{15}-1]内。而当改用32位整数时，通过类似计算得，slob可支持小于8G的页面.

利用page结构

slob_t的改动减少了粒度和空间占用，偏移量的设计使得每个页面拥有自己的独立空闲块链表。slob通过union机制，重用了include/linux/mm_types.h中page结构，用空闲位来存储链表，从而不增加任何空间占用。

/*
 * We use struct page fields to manage some slob allocation aspects,
 * however to avoid the horrible mess in include/linux/mm_types.h, we'll
 * just define our own struct page type variant here.
 */
struct slob_page {
    union {
        struct {
            unsigned long flags;    /* mandatory */
            atomic_t _count;    /* mandatory */
            slobidx_t units;    /* free units left in page */
            unsigned long pad[2];
            slob_t *free;       /* first free slob_t in page */
            struct list_head list;  /* linked list of free pages */
        };
        struct page page;
    };
};

对page的必要位进行填充，其他位存储空闲units数、空闲block链表等。
注意struct list_head list变量，对于自己申请的所有页，slob采用循环双向链表形式管理，链表相关函数定义在include/linux/list.h中，数据结构定义在include/linux/types.h中，链表节点除了前驱后继指针以外没有任何其他内容：

// types.h
struct list_head {
    struct list_head *next, *prev;
};
// list.h
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

与block节点的增删类似，当一个页面的空间被完全分配出去后，slob将其list节点从链表中删去（clear_slob_page_free）；被归还和新申请的页面则会被插入链表中的合适位置（set_slob_page_free）。

相应的流程变化

空闲block按页面组织后，显然在遍历block链表寻找空闲block之前，还需先找到一个能满足分配要求的页面，页面的寻找仍然是first fit方式。注意由于碎片问题，页面空闲units数大于需求不一定代表就能分配成功，如果失败则继续尝试其他页面。

此外还有：

• 更改了大内存分配方式，不再使用bigblock，这部分仍然不再赘述
• 增加了对NUMA的支持，因此分配内存时多了一个node参数
• 分配时强制进行align，align宽度与体系结构相关
• 增加了对RCU的支持，这部分不是很懂

分配部分核心代码：

• kmalloc调用slob_alloc分配多一个align大小的内存，在头部写入大小信息，返回偏移后的地址
• slob_alloc找到符合要求的page，调用slob_page_alloc在页内分配，没有合适的页面则会申请新页面
• slob_page_alloc是经典的block分配

// top API
void *__kmalloc_node(size_t size, gfp_t gfp, int node)
{
    unsigned int *m;
    int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);

    if (size < PAGE_SIZE - align) {
        if (!size)
            return ZERO_SIZE_PTR;

        m = slob_alloc(size + align, gfp, align, node);
        if (m)
            *m = size;
        return (void *)m + align;
    } else {
        // big block part
    }
}

static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
{
    struct slob_page *sp;
    struct list_head *prev;
    slob_t *b = NULL;
    unsigned long flags;

    spin_lock_irqsave(&slob_lock, flags);
    /* Iterate through each partially free page, try to find room */
    list_for_each_entry(sp, &free_slob_pages, list) {
#ifdef CONFIG_NUMA
        /*
         * If there's a node specification, search for a partial
         * page with a matching node id in the freelist.
         */
        if (node != -1 && page_to_nid(&sp->page) != node)
            continue;
#endif
        /* Enough room on this page? */
        if (sp->units < SLOB_UNITS(size))
            continue;

        /* Attempt to alloc */
        prev = sp->list.prev;
        b = slob_page_alloc(sp, size, align);
        if (!b)
            continue;

        /* Improve fragment distribution and reduce our average
         * search time by starting our next search here. (see
         * Knuth vol 1, sec 2.5, pg 449) */
        if (free_slob_pages.next != prev->next)
            list_move_tail(&free_slob_pages, prev->next);
        break;
    }
    spin_unlock_irqrestore(&slob_lock, flags);

    /* Not enough space: must allocate a new page */
    if (!b) {
        b = slob_new_page(gfp, 0, node);
        if (!b)
            return 0;
        sp = (struct slob_page *)virt_to_page(b);
        set_slob_page(sp);

        spin_lock_irqsave(&slob_lock, flags);
        sp->units = SLOB_UNITS(PAGE_SIZE);
        sp->free = b;
        INIT_LIST_HEAD(&sp->list);
        set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
        set_slob_page_free(sp);
        b = slob_page_alloc(sp, size, align);
        BUG_ON(!b);
        spin_unlock_irqrestore(&slob_lock, flags);
    }
    if (unlikely((gfp & __GFP_ZERO) && b))
        memset(b, 0, size);
    return b;
}

static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
{
    slob_t *prev, *cur, *aligned = 0;
    int delta = 0, units = SLOB_UNITS(size);

    for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
        slobidx_t avail = slob_units(cur);

        if (align) {
            aligned = (slob_t *)ALIGN((unsigned long)cur, align);
            delta = aligned - cur;
        }
        if (avail >= units + delta) { /* room enough? */
            slob_t *next;

            if (delta) { /* need to fragment head to align? */
                next = slob_next(cur);
                set_slob(aligned, avail - delta, next);
                set_slob(cur, delta, aligned);
                prev = cur;
                cur = aligned;
                avail = slob_units(cur);
            }

            next = slob_next(cur);
            if (avail == units) { /* exact fit? unlink. */
                if (prev)
                    set_slob(prev, slob_units(prev), next);
                else
                    sp->free = next;
            } else { /* fragment */
                if (prev)
                    set_slob(prev, slob_units(prev), cur + units);
                else
                    sp->free = cur + units;
                set_slob(cur + units, avail - units, next);
            }

            sp->units -= units;
            if (!sp->units)
                clear_slob_page_free(sp);
            return cur;
        }
        if (slob_last(cur))
            return NULL;
    }
}

free基本类似，这里就不再叙述了。

后续变化

后续版本的变化没那么大，就挑几个大版本对比一下。

分类管理页面——v3.0

v3.0中最大的变化是页面链表从增加为3个，分别负责负责分配256B、256B~1024B、1024B以上的空间，这样分工有利于减少内存碎片。

/*
 * All partially free slob pages go on these lists.
 */
#define SLOB_BREAK1 256
#define SLOB_BREAK2 1024
static LIST_HEAD(free_slob_small);
static LIST_HEAD(free_slob_medium);
static LIST_HEAD(free_slob_large);

/*
 * slob_alloc: entry point into the slob allocator.
 */
static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
{
    // ...
    if (size < SLOB_BREAK1)
        slob_list = &free_slob_small;
    else if (size < SLOB_BREAK2)
        slob_list = &free_slob_medium;
    else
        slob_list = &free_slob_large;
    // ...
}

还增加了对kmem_leak的支持，不再叙述。

sl[aou]b统一管理——v4.0

v4.0中不再使用struct slob_page，而是直接在include/linux/mm_types.h的struct page中，为sl[aou]b这三种分配算法设计统一的数据结构，代码比较长就不放了。这样设计可以免去很多格式转换。

slob: Define page struct fields used in mm_types.h

Define the fields used by slob in mm_types.h and use struct page instead of struct slob_page in slob. This cleans up numerous of typecasts in slob.c and makes readers aware of slob's use of page struct fields.

此外在v4.0中：

• kemem_cache部分的流程做了重新设计
• slob不再负责管理超过一页内存的内存申请，直接交给伙伴系统负责

sl[aou]b统一管理优化——当今版本

为了sl[aou]b更改mm_types中的数据结构，可能会对其他引用mm_types的模块产生影响。因此后续版本中这部分实现被移至mm/slab.h中，并重命名为struct slab。

mm/slob: Convert SLOB to use struct slab and struct folio

Use struct slab throughout the slob allocator. Where non-slab page can appear use struct folio instead of struct page.

struct slab通过分配器版本相关的宏选项（CONFIG_SL[AOU]B），来对真正实现进行编译期控制：

struct slab {
    unsigned long __page_flags;

#if defined(CONFIG_SLAB)

    union {
        struct list_head slab_list;
        struct rcu_head rcu_head;
    };
    struct kmem_cache *slab_cache;
    void *freelist; /* array of free object indexes */
    void *s_mem;    /* first object */
    unsigned int active;

#elif defined(CONFIG_SLUB)

    union {
        struct list_head slab_list;
        struct rcu_head rcu_head;
#ifdef CONFIG_SLUB_CPU_PARTIAL
        struct {
            struct slab *next;
            int slabs;  /* Nr of slabs left */
        };
#endif
    };
    struct kmem_cache *slab_cache;
    /* Double-word boundary */
    void *freelist;     /* first free object */
    union {
        unsigned long counters;
        struct {
            unsigned inuse:16;
            unsigned objects:15;
            unsigned frozen:1;
        };
    };
    unsigned int __unused;

#elif defined(CONFIG_SLOB)

    struct list_head slab_list;
    void *__unused_1;
    void *freelist;     /* first free block */
    long units;
    unsigned int __unused_2;

#else
#error "Unexpected slab allocator configured"
#endif

    atomic_t __page_refcount;
#ifdef CONFIG_MEMCG
    unsigned long memcg_data;
#endif
};

后记

slob作为只有几百行代码量、原理简单的轻量级分配器，阅读起来却并不容易。甚至在写作这篇文章的时候我才发现之前的很多理解是错误的，源于自己对内存机制理解的不透彻。

阅读的过程中感叹linux代码之优秀，短短六百行代码竟经历如此之多的迭代改进。

收获的另一个经验是：大型系统中的小功能实现不可避免会涉及与系统其他部分的交互，在分析时对于确定与感兴趣功能无关的部分可以忽略，但涉及原理和内部具体实现的部分绝不能含糊。