kmem库中的slab分配算法

slab 最初是用于 Linux 内核的一种内存分配机制，主要用于优化小对象的频繁分配和释放操作。

数据结构

slab 的数据结构定义如下：

struct IMEMSLAB
{
    struct IQUEUEHEAD queue;
    size_t coloroff;
    void*membase;
    ilong memsize;
    ilong inuse;
    void*bufctl;
    void*extra;
};

typedef struct IMEMSLAB imemslab_t;

#define IMEMSLAB_ISFULL(s) ((s)->bufctl == 0)
#define IMEMSLAB_ISEMPTY(s) ((s)->inuse == 0)

关键成员说明如下：

membase slab 缓存的起始地址
bufctl 当前 slab 缓存的分配入口

slab 缓存分配算法就是将一段连续的内存块等分成指定大小的多个段，之后，基于 slab 的缓存分配即是从这些段中取出一个空闲的。

slab 缓存在分配和释放的过程中，我们怎么标记它们的状态呢？为解决此问题，实际上，slab 缓存被等分成的段并不会孤立存在， slab 缓存中的每个段的前面都会预留 sizeof(void*) 个字节，用于保存该段之后下一个可用段的指针。于是，slab 缓存各可用内存段相当于构成了一个单链表，bufctl 为单链表入口。

slab 缓存的结构模型如下图所示：

实现

slab 缓存的初始化函数实现如下：

/* init slab structure with given memory block and coloroff */
static ilong imslab_init(imemslab_t *slab, void *membase,
    size_t memsize, ilong obj_size, size_t coloroff)
{
    char *start = ((char*)membase) + coloroff;
    char *endup = ((char*)membase) + memsize - obj_size;
    ilong retval = 0;
    char *tail;

    assert(slab && membase);
    assert((size_t)obj_size >= sizeof(void*));

    iqueue_init(&slab->queue);
    slab->membase = membase;
    slab->memsize = memsize;
    slab->coloroff = coloroff;
    slab->inuse = 0;
    slab->extra = NULL;
    slab->bufctl = NULL;

    for (tail = NULL; start <= endup; start += obj_size) {
        IMEM_NEXT_PTR(start) = NULL;
        if (tail == NULL) slab->bufctl = start;
        else IMEM_NEXT_PTR(tail) = start;
        tail = start;
        retval++;
    }

    return retval;
}

在 imslab_init 函数中，((char*)membase) + coloroff 至 ((char*)membase) + memsize 的内存块被均分成 obj_size 大小的多个段。并且构造了以 bufctl 为入口的一个单链表。IMEM_NEXT_PTR 的定义为：#define IMEM_NEXT_PTR(p) (((void**)(p))[0])。

在 slab 缓存区初始化之后，我们就可以在该缓存区上分配和释放内存了。

基于 slab 缓存的分配函数实现如下：

/* alloc data from slab */
static void *imslab_alloc(imemslab_t *slab)
{
    void *ptr;

    if (slab->bufctl == 0) return 0;
    ptr = slab->bufctl;
    slab->bufctl = IMEM_NEXT_PTR(slab->bufctl);
    slab->inuse++;

    return ptr;
}

可以看到，基于 slab 缓存的分配操作即是从单链表中取出一个节点。

释放函数实现如下：

/* free data into slab */
static void imslab_free(imemslab_t *slab, void *ptr)
{
    char *start = ((char*)slab->membase) + slab->coloroff;
    char *endup = ((char*)slab->membase) + slab->memsize;
    char *p = (char*)ptr;

    assert(slab->inuse > 0);
    assert(p >= start && p < endup);

    if (p >= start && p < endup) {
        IMEM_NEXT_PTR(p) = slab->bufctl;
        slab->bufctl = p;
    }

    slab->inuse--;
}

基于 slab 缓存的释放操作即是将被释放的内存块重新放入单链表。

本文作者ruleless, 欢迎评论、交流。
转载请务必标注出处: kmem库中的slab分配算法