前言
说到内存管理,就得提到内存池,gc垃圾回收以及malloc底层实现。本篇主要剖析内存池,通过分析经典的memcached的内存池设计来了解了解内存池的内部实现和优劣点。
memcached概述
memcached是一种分布式高速缓存中间件,相比较redis是更早期的缓存中间件。它的内存池使用的是slab机制。这里使用的是1.6.16版本,源码文件是slab.c。
在讲slab机制前先来说说几个概念,以及后面的源码精简了下只保留和本主题有关的内容。
item
- item 是memcached存储的最小单元
- item 存储memcached里的key和value
- HashTable 和 LRU链表结构都依赖item来进行的
总之item就是我们使用memcached最基础的数据单元
代码如下:
typedef struct _stritem {
/* Protected by LRU locks */
struct _stritem *next;
struct _stritem *prev;
...
uint8_t slabs_clsid;/* which slab class we're in */
uint8_t nkey; /* key length, w/terminating null and padding */
/* this odd type prevents type-punning issues when we do
* the little shuffle to save space when not using CAS. */
union {
uint64_t cas;
char end;
} data[];
/* if it_flags & ITEM_CAS we have 8 bytes CAS */
/* then null-terminated key */
/* then " flags length\r\n" (no terminating null) */
/* then data with terminating \r\n (no terminating null; it's binary!) */
} item;
省略了和本主题无关的字段, 剩下的字段 next, prev 这个事链表的前后指针,slabs_clsid 是 slab class的 id表达该item在哪个slab class里面
slabclass 内存分配的数据结构
代码如下:
typedef struct {
//当下可以存储的最大的item的大小
unsigned int size; /* sizes of items */
//当下可以存的item的数量
unsigned int perslab; /* how many items per slab */
//空闲的未使用的item链表
void *slots; /* list of item ptrs */
//总共的空闲链表的item数量
unsigned int sl_curr; /* total free items in list */
//已经分配了多少个item
unsigned int slabs; /* how many slabs were allocated for this class */
//这个字段实际上可以理解成item指针的数组,每个数组元素的item指针都是指向一个item链表。记录之前分配给该slab的一个完整page(大小1Mb)
void **slab_list; /* array of slab pointers */
//上面这个数组的大小
unsigned int list_size; /* size of prev array */
} slabclass_t;
//总共64个slabclass
static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];
- memcached会初始化64个slabclass_t结构。下标为0的特别说明一下这个是给-e参数指定文件。然后内存会按照page为单位预先分配到0的 slabclass_t里面,这里只是提一下,默认机制里不使用这玩意。
- 这里有个chunk的概念的,每个slabclass_t是存储一系列大小相同的chunk,然后每一个chunk里面存实际的item
- slabclass_t数组从1开始指定存储的chunk大小是96Byte,然后到下标63(如果能到chunk有最大值控制默认512KB),依次乘以1.25(setting.factor 通过-f来修改),这里最后一个64下标直接存默认512KB(settings.slab_chunk_size_max)
- 每个slabclass只存小于等于它chunk的item,比如slabclass[1]是96Byte slabclass[2]是120Byte,那么100Byte的item就会分配在slabclass[2]里面。当然这里有内存浪费
- 每次分配给slabclass内存的时候是按照page(默认1mb)为单位整体分配给它的
接下来在画slabclass内存图之前,先来说明一下经典的内存池技术嵌入式指针。
图中要说明的是这个小的内存块,分配出去后就完全可以当做一个新的结构体使用,可以无视原来的指针字段。
最重要的字段就是slots用于挂载空闲链表。当有需要就从这里分配给应用。
源码分析
slabclass的初始化slabs_init
这里删减了一些大页预分配内存以及memcache设定内存文件用于热启动的一些机制代码,只保留最核心的内存池代码
/**
* Determines the chunk sizes and initializes the slab class descriptors
* accordingly.
*/
void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes, void *mem_base_external, bool reuse_mem) {
int i = POWER_SMALLEST - 1;
unsigned int size = sizeof(item) + settings.chunk_size;
...
memset(slabclass, 0, sizeof(slabclass));
while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {
if (slab_sizes != NULL) {
if (slab_sizes[i-1] == 0)
break;
size = slab_sizes[i-1];
} else if (size >= settings.slab_chunk_size_max / factor) {
break;
}
//这里进行内存对齐
/* Make sure items are always n-byte aligned */
if (size % CHUNK_ALIGN_BYTES)
size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
//每个slabclass存储最大的item大小
slabclass[i].size = size;
//每个slabclass可以一页有多少个item
slabclass[i].perslab = settings.slab_page_size / slabclass[i].size;
if (slab_sizes == NULL)
size *= factor;
if (settings.verbose > 1) {
fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
i, slabclass[i].size, slabclass[i].perslab);
}
}
//处理最大的这个slabclass,size取最大size配置,默认是512KB,perslab为2
power_largest = i;
slabclass[power_largest].size = settings.slab_chunk_size_max;
slabclass[power_largest].perslab = settings.slab_page_size / settings.slab_chunk_size_max;
if (settings.verbose > 1) {
fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
i, slabclass[i].size, slabclass[i].perslab);
}
...
}
这里就是slab的初始化过程,从slabclass[1]一直遍历到最大power_largest,对每一个slabclass指定size和perslab,这里可以看到是可以外部自己指定slabclass大小(就是代码里slab_sizes参数), 最大的size不能超过settings.slab_chunk_size_max,默认是512KB。
do_slabs_alloc 分配item
//分配一个slab
void *slabs_alloc(size_t size, unsigned int id,
unsigned int flags) {
void *ret;
pthread_mutex_lock(&slabs_lock);
//需要分配的size和 哪个slabclass id 就是slabclass数组下标,这两个值是对应的
ret = do_slabs_alloc(size, id, flags);
pthread_mutex_unlock(&slabs_lock);
return ret;
}
static void *do_slabs_alloc(const size_t size, unsigned int id,
unsigned int flags) {
slabclass_t *p;
void *ret = NULL;
item *it = NULL;
...
//获取指定的slabclass
p = &slabclass[id];
assert(p->sl_curr == 0 || (((item *)p->slots)->it_flags & ITEM_SLABBED));
assert(size <= p->size);
/* fail unless we have space at the end of a recently allocated page,
we have something on our freelist, or we could allocate a new page */
//sl_curr就是当前slabclass还有多少剩余chunk可以分配,后面flag判定是rebalance机制使用可以这里无视它。然后do_slabs_newslab进行分配
if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) {
do_slabs_newslab(id);
}
//从空余的slots链表上取下一个节点分配给应用
if (p->sl_curr != 0) {
/* return off our freelist */
it = (item *)p->slots;
p->slots = it->next;
if (it->next) it->next->prev = 0;
/* Kill flag and initialize refcount here for lock safety in slab
* mover's freeness detection. */
it->it_flags &= ~ITEM_SLABBED;
it->refcount = 1;
p->sl_curr--;
ret = (void *)it;
} else {
ret = NULL;
}
...
return ret;
}
这个代码还是很清晰的。Memcached分配一个item会进行调用slabs_alloc。实现里会先检查对应的slabclass的空闲列表有没有chunk,有就进行分配,如果没有的话,会先进行调用do_slabs_newslab进行该slab分配。
do_slabs_newslab分配,先看代码
static int do_slabs_newslab(const unsigned int id) {
slabclass_t *p = &slabclass[id];
slabclass_t *g = &slabclass[SLAB_GLOBAL_PAGE_POOL];
//这里默认是使用pagesize (1MB), 另外一种选项可以节省点内存,简单提一下,一个是内存进行Rebalance机制(这个主要是进行slabclass可以把分配给自己不用的页置换给别人)另一个是允许chunk(这个是让一个item可以突破单个chunk大小限制)下不允许这样,
int len = (settings.slab_reassign || settings.slab_chunk_size_max != settings.slab_page_size)
? settings.slab_page_size
: p->size * p->perslab;
char *ptr;
...
//grow_slab_list 是扩充slabclass里面的slab_list
//get_page_from_global_pool是从 slabclass[0]里取page
//memory_allocate通常行为就是调用系统的malloc申请一页的内存,当然开启其他机制的时候有变化这里就不细说了
if ((grow_slab_list(id) == 0) ||
(((ptr = get_page_from_global_pool()) == NULL) &&
((ptr = memory_allocate((size_t)len)) == 0))) {
...
return 0;
}
// Always wipe the memory at this stage: in restart mode the mmap memory
// could be unused, yet still full of data. Better for usability if we're
// wiping memory as it's being pulled out of the global pool instead of
// blocking startup all at once.
memset(ptr, 0, (size_t)len);
//把申请到的该页,改造成内存链表挂载到该slabclass的slot空闲链表上面
split_slab_page_into_freelist(ptr, id);
//用slab_list记录下,目前的主要的slab机制里用不到这个东西,它主要是用于rebalance。
p->slab_list[p->slabs++] = ptr;
...
return 1;
}
static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
slabclass_t *p = &slabclass[id];
int x;
//遍历该slabclass一个page所有的chunk,把它们全部挂载到slot上面
for (x = 0; x < p->perslab; x++) {
do_slabs_free(ptr, 0, id);
ptr += p->size;
}
}
static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
slabclass_t *p;
item *it;
...
p = &slabclass[id];
it = (item *)ptr;
if ((it->it_flags & ITEM_CHUNKED) == 0) {
it->it_flags = ITEM_SLABBED;
it->slabs_clsid = id;
it->prev = 0;
it->next = p->slots;
if (it->next) it->next->prev = it;
p->slots = it;
p->sl_curr++;
} else {
...
}
return;
}
do_slabs_newslab所做事情
- 申请1个page的内存
- 重置内存值
- 把申请到的page进行嵌入式链表化处理,然后挂载到该slabclass slots上面
- 修改相应的值 slab_list
slabs_free释放一个item
//传入item指针ptr, size和slabclass的id 进行chunk释放
void slabs_free(void *ptr, size_t size, unsigned int id) {
pthread_mutex_lock(&slabs_lock);
do_slabs_free(ptr, size, id);
pthread_mutex_unlock(&slabs_lock);
}
static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
slabclass_t *p;
item *it;
...
//找到对应的slabclass
p = &slabclass[id];
it = (item *)ptr;
if ((it->it_flags & ITEM_CHUNKED) == 0) {
//回收到slots链表
it->it_flags = ITEM_SLABBED;
it->slabs_clsid = id;
it->prev = 0;
it->next = p->slots;
if (it->next) it->next->prev = it;
p->slots = it;
p->sl_curr++;
} else {
...
}
return;
}
释放item,主要做的事情
- 找到slabclass
- 该item插入到该slabclass的slots链表上
- 进行slabclass相应值sl_cur修改
slabclass在回收内存的时候只是回收到自己的slab机制里,并不会调用free把它还给操作系统。考虑这样一个场景比如我一直使用slabclass[1]的内存。然后用满了然后全部删除,这时候内存全部还给slabclass[1],但是我想放入一个大的item就会没法分配(因为slabclass大的想要申请page没有了)
这里memcached提供了内存页重分配机制处理。memcached是把不怎么使用的slabclass i 里的页重分配给 slabclass j,然后一页整体划过去,上面的已经存在的数据需要进行处理。内部也有机制判别啥时候i划给j。这里只是提一下,有兴趣可以看看slab.c 里面的slab_rebalance_thread
总结
memcached的内存机制
优点:
- 速度极快,我们可以看到分配时候直接取slot上面的chunk即可。基本不需要经过系统级malloc调用。尤其是开启预分配large page时候,抢占式开始就申请完整的内存。后面无需任何malloc
- 效率高,避免了内存碎片产生,这套算法避免了在整块内存里进行不规则切割,会把连续的内存切的稀碎导致申请要去寻找合适的位置。这里分配好就固定下来了就直接使用,回收后不会在进行复杂的重新调整避免了碎片
缺点:
- 浪费内存, 这里是以chunk为单位的。并不会以item的size就行恰好的分配。会有内存的浪费
- 使用了就抢占了,不能把内存还给操作系统给其他应用使用。
写在最后,欢迎有任何建议和想法或者指出哪里写的不足的地方的童鞋联系我~~~