memcached slabs内存分配算法详解

[liexusong原创]

Memcached Slab算法是根据powers of 2来将1MB的内存块划分成多个小内存块, 而这1MB的内存块称为页：

 

Powers of 2是2的n次方的意思，例如：2的0次方是1，2的1次方是2，2的2次方是4，2的3次方是8等等。

而将1MB的内存按2的n次方划分可以划分成20种不同的内存块，因为2的20次方是1MB（1048576）。所以可以说，memcached管理着20种不同的内存块的集合。

而memcached是通过slabclass_t结构体来管理这些小内存块的, slabclass_t的定义如下:

typedef struct {

    unsigned int size;     

    unsigned int perslab;  

 

    void **slots;          

    unsigned int sl_total; 

    unsigned int sl_curr;  

 

    void *end_page_ptr;

    unsigned int end_page_free;

 

    unsigned int slabs;    

 

    void **slab_list;      

    unsigned int list_size;

 

    unsigned int killing; 

} slabclass_t;

 

(1)   slots指针指向的是内存分配器回收的小内存块的数组, sl_total保存了回收器的容量, 当回收器容量不足时, 需要重新分配更大的内存来作为回收器, sl_curr是当前回收器回收到的位置, 下一个回收的内存块就会放到这里:

(2)   end_page_ptr保存的是当前的空闲内存块, end_page_free保存的是当前空闲块的数量, 如果end_page_free等于0表示已经没有空闲内存块了, 需要向系统申请一块新的内存页.

(3)   slab_list保存的是申请的内存页, slabs保存的是已经申请的内存页数量. 

所以综合起来的总体结构图:

slab分配函数(slabs_alloc):

if (! (p->end_page_ptr || p->sl_curr || slabs_newslab(id)))

    return 0;

 

 

 

if (p->sl_curr)

    return p->slots[--p->sl_curr];

 

 

if (p->end_page_ptr) {

    void *ptr = p->end_page_ptr;

    if (--p->end_page_free) {

        p->end_page_ptr += p->size;

    } else {

        p->end_page_ptr = 0;

    }

    return ptr;

}

 

函数中首先判断是否有空闲内存块, 或者回收过的内存块, 如果都没有就调用slabs_newslab()新建一个内存页; 然后优先分配回收过的内存块, 如果没有才去分配空闲的内存块.

 

slabs_newslab()函数是新建一个内存页.

int slabs_newslab(unsigned int id) {

    slabclass_t *p = &slabclass[id];

    int num = p->perslab;

    int len = POWER_BLOCK;

    char *ptr;

 

    if (mem_limit && mem_malloced + len > mem_limit)

        return 0;

 

    if (! grow_slab_list(id)) return 0;

  

    ptr = malloc(len);

    if (ptr == 0) return 0;

 

    memset(ptr, 0, len);

    p->end_page_ptr = ptr;

    p->end_page_free = num;

 

    p->slab_list[p->slabs++] = ptr;

    mem_malloced += len;

    return 1;

}

 

slabs_newslab()每次分配1MB作为内存页. 然后把end_page_ptr指向这个新的内存页.

 

 

slab回收函数(slabs_free):

void slabs_free(void *ptr, unsigned int size) {

    unsigned char id = slabs_clsid(size);

    slabclass_t *p;

 

    if (id < POWER_SMALLEST || id > POWER_LARGEST)

        return;

 

    p = &slabclass[id];

    if (p->sl_curr == p->sl_total) {

        int new_size = p->sl_total ? p->sl_total*2 : 16; 

        void **new_slots = realloc(p->slots, new_size*sizeof(void *));

        if (new_slots == 0)

            return;

        p->slots = new_slots;

        p->sl_total = new_size;

    }

    p->slots[p->sl_curr++] = ptr;

    return;

}

 

回收时, 直接用回收器(slots)的指针指向这个内存块, 这样就完成回收操作. 如果回收器不够大, 就扩充回收器.