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)的指针指向这个内存块,?这样就完成回收操作.?如果回收器不够大,?就扩充回收器.