memcached源码学习-内存管理机制slab allocator

stage

　　    前端时间大致浏览了一下memcached的源码，但是并没有对相关的知识点进行总结和记录，所以很快就忘了，这次打算将memcached的源码再学习一遍，并进行总结归纳。
　　    memcached模块化设计比较好，每个模块除了对外接口定义在头文件外，其它函数定义及实现都在源文件中，且定义为static类型，这样很好的降低了模块之间的耦合性。下面，浏览源码将按照功能模块进行划分，逐步学习总结。
　　    memcached主要包括以下模块（不完全归纳）：
　　        内存管理机制(slab)，hash，多线程及libevent事件处理机制，...
　　    本文主要对memcached的内存管理机制进行总结，并画出相应的结构图，便于理解。
　　    众所周知，简单的使用malloc和free，这样将产生大量的内存碎片，从而加重操作系统内存管理器的负担。memcached的内存管理机制采用了slab allocator内存分配和管理机制，以解决内存碎片问题。slab allocator基本原理是按照预先定义的大小，将内存分割为多种特定长度的trunk块，并将长度相同的trunk块归成slab组，每次请求内存时，采用最佳适应算法查询并获得一个trunk，用于保存item。
　　    memcached中slab内存分配管理相关函数定义及实现源码全部集中在slabs.h和slabs.c中，slabs.h定义了外部模块内存操作的接口，包括的函数如下（其中最后2个函数与slab内存管理机制关联不大，后续不予讨论）：
　　        // slabs_init：初始化slab内存管理，主要完成slabclass数组中每个slabclass_t中trunk大小(内存以CHUNK_ALIGN_BYTES=8字节对齐)及每个slab中trunk数量的初始化
　　        // 参数 limit：运行时指定的memcached可用内存大小，0表示不限制大小
　　        // 参数 factor：增长因子
　　        // 参数 prealloc：表示是否预分配limit内存，true：则在函数内使用malloc预分配limit大小的内存


　　        void slabs_init(const size_t limit, const double factor, const bool prealloc) ;


　　


　　        // slabs_clsid：返回size大小对应的slabclass索引clsid，即size大小的trunk将放入slabclass[clsid]中，0表示对象太大
　　        unsigned int slabs_clsid(const size_t size) ;
　　


　　        // slabs_alloc：从slabclass[id]中分配一个size大小的trunk，错误时返回NULL(0)

        void *slabs_alloc(const size_t size, unsigned int id) ;
　　


　　        // slabs_free：将ptr指向的大小为size的内存区域加入slabclass[id]的空闲内存块数组（freelist）中

        void slabs_free(void *ptr, size_t size, unsigned int id) ;


　　        // 调整slabclass[id]的requested值：requested = requested - old + ntotal

        void slabs_adjust_mem_requested(unsigned int id, size_t old, size_t ntotal) ;



         // 返回状态信息（）

         bool get_stats(const char *stat_type, int nkey, ADD_STAT add_stats, void *c) ;


　　


　　    slabs.c中定义了memcached中slab allocator实现代码，下面首先介绍使用的数据结构，然后介绍相关的实现。

• 数据结构
  

　　        memcached定义slabclass数组用来管理内存：
　　             slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];  


　　        memcached的slab内存管理机制最主要的数据结构为struct slabclass_t，定义如下：

typedef struct {
unsigned int size;      /* sizes of items */
unsigned int perslab;   /* how many items per slab */
void **slots;           /* list of item ptrs */
unsigned int sl_total;  /* size of previous array */
unsigned int sl_curr;   /* first free slot */
void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */
unsigned int end_page_free; /* number of items remaining at end of last alloced page */
unsigned int slabs;     /* how many slabs were allocated for this class */
void **slab_list;       /* array of slab pointers */
unsigned int list_size; /* size of prev array */
unsigned int killing;  /* index+1 of dying slab, or zero if none */
size_t requested; /* The number of requested bytes */
} slabclass_t;

　　        其中，size为slabclass_t中每个trunk的大小，perslab为每个slab包含的trunk数；
　　         slots为memcached中空闲trunk块指针数组（或列表，以下使用数组），sl_total为已分配的slots数组大小，sl_curr为当前可用的slots数组索引；
　　         slab_list为此slabclass_t中的slab指针数组，list_size为slab_list指针数组已分配的大小，slabs为当前已使用的slab_list指针数组数量，end_page_ptr和end_page_free分别为当前的slab中trunk的起始位置和trunk可用数量；
　　        killing不确定，requested为已使用的内存大小。
　　        memcached的slab数据结构如下图所示（图中实箭头表示指针，小箭头表示索引或数量）：



　　

• 实现介绍（函数介绍过程中，结合上图理解起来更容易）
  

　　         下面将对主要的代码进行解析：

/*
* Figures out which slab class (chunk size) is required to store an item of
* a given size.
*
* Given object size, return id to use when allocating/freeing memory for object
* 0 means error: can't store such a large object
*/
unsigned int slabs_clsid(const size_t size) {
int res = POWER_SMALLEST;
if (size == 0)
return 0;
// 遍历slabclass数组，找到最适合放入size大小的slabclass_t的索引
while (size > slabclass[res].size)
if (res++ == power_largest)     /* won't fit in the biggest slab */
return 0;
return res;
}

/**
* Determines the chunk sizes and initializes the slab class descriptors
* accordingly.
*/
void slabs_init(const size_t limit, const double factor, const bool prealloc) {
int i = POWER_SMALLEST - 1;
unsigned int size = sizeof(item) + settings.chunk_size;    // 初始化trunk大小
mem_limit = limit;
// 指定为预分配内存，则一次行分配全部内存（limit大小）
if (prealloc) {
/* Allocate everything in a big chunk with malloc */
mem_base = malloc(mem_limit);
if (mem_base != NULL) {
mem_current = mem_base;
mem_avail = mem_limit;
} else {
fprintf(stderr, "Warning: Failed to allocate requested memory in"
" one large chunk.\nWill allocate in smaller chunks\n");
}
}
memset(slabclass, 0, sizeof(slabclass));
// 初始化每个slabclass_t的trunk大小和每个slab中trunk数量
// slabclass中每个slabclass_t的trunk大小增长为factor倍
// 注意 i 从索引 1 开始
while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
/* Make sure items are always n-byte aligned */
if (size % CHUNK_ALIGN_BYTES)                             // 内存8字节对齐
size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
slabclass.size = size;
slabclass.perslab = settings.item_size_max / slabclass.size;
size *= factor;
if (settings.verbose > 1) {
fprintf(stderr, &quot;slab class %3d: chunk size %9u perslab %7u\n&quot;,
i, slabclass.size, slabclass.perslab);
}
}
// slabclass中最后一个slabclass_t的trunk大小设置为最大item大小
power_largest = i;
slabclass[power_largest].size = settings.item_size_max;
slabclass[power_largest].perslab = 1;
if (settings.verbose > 1) {
fprintf(stderr, &quot;slab class %3d: chunk size %9u perslab %7u\n&quot;,
i, slabclass.size, slabclass.perslab);
}
....// 省略
}

　　下面是我抓取的系统初始化trunk列表（CentOS6.0-64bit，memcached版本为1.4.7，factor默认为1.25）：



　　

// 初始化或增大slab_list指针数组
static int grow_slab_list (const unsigned int id) {
slabclass_t *p = &slabclass[id];
// slabclass_t中已经分配的slabs数量与slab指针数组的大小相同，表示已满,如下图所示
// 则，重新分配slab指针数组，指针数组增大为以前的2倍或初始化为16
if (p->slabs == p->list_size) {
size_t new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;
void *new_list = realloc(p->slab_list, new_size * sizeof(void *));
if (new_list == 0) return 0;
p->list_size = new_size;
p->slab_list = new_list;
}
return 1;
}

// 初始化或重新分配一个slabclass[id]中的slab（每个slab包含perslab个trunk，每个trunk大小为size），见下图！
static int do_slabs_newslab(const unsigned int id) {
slabclass_t *p = &slabclass[id];
int len = p->size * p->perslab; // 每个trunk的size * 每个slab中trunk数量
char *ptr;
// 第一次未分配时，p->slabs==0, mem_malloced==0
// 如果已经分配过，mem_malloced + len > mem_limit表示超过定义的内存
if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
(grow_slab_list(id) == 0) ||  // 如果slabs指针数组满了或未初始化，
// 则增大slabs指针数组的大小(2倍或初始化为16)
((ptr = memory_allocate((size_t)len)) == 0)) {  // 调用malloc分配len大小内存或调整当前指针(预分配时)
MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
return 0;
}
memset(ptr, 0, (size_t)len);
p->end_page_ptr = ptr;              // 当前slab可用trunk起始地址
p->end_page_free = p->perslab;      // 当前slab可用的trunk数量
p->slab_list[p->slabs++] = ptr;     // 将分配的slab(trunk列表)，放到slabs数组中
mem_malloced += len;
MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
return 1;
}            

/* 分配一个trunk数据结构，过程见下图 */
static void *do_slabs_alloc(const size_t size, unsigned int id) {
slabclass_t *p;
void *ret = NULL;
// 索引非法
if (id < POWER_SMALLEST || id > power_largest) {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
return NULL;
}
p = &slabclass[id];
assert(p->sl_curr == 0 || ((item *)p->slots[p->sl_curr - 1])->slabs_clsid == 0);
#ifdef USE_SYSTEM_MALLOC
if (mem_limit && mem_malloced + size > mem_limit) {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
return 0;
}
mem_malloced += size;
ret = malloc(size);
MEMCACHED_SLABS_ALLOCATE(size, id, 0, ret);
return ret;
#endif
/* 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 */
if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||
do_slabs_newslab(id) != 0)) {
/* We don't have more memory available */
ret = NULL;
} else if (p->sl_curr != 0) {       // freelist非空，优先从freelist分配
/* return off our freelist */
ret = p->slots[--p->sl_curr];
} else {                            // 刚分配的
/* if we recently allocated a whole page, return from that */
assert(p->end_page_ptr != NULL);
ret = p->end_page_ptr;
if (--p->end_page_free != 0) {
p->end_page_ptr = ((caddr_t)p->end_page_ptr) + p->size;
} else {
p->end_page_ptr = 0;
}
}
if (ret) {
p->requested += size;
MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
} else {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
}
return ret;
}

　　  do_slabs_newslab函数初始化时，end_page_ptr指向slab的起始位置，end_page_free等于perslab；
　　        do_slabs_alloc函数每次分配一个trunk(假设此时freelist为空)，则end_page_ptr指向下一位置，end_page_free减1，直到分配完毕；后续申请，则新建一个slab（do_slabs_newslab函数的ptr = memory_allocate((size_t)len)）。
　　         初始化一个slab和分配trunk的过程图：

// 释放trunk结构(将其放入freelist指针数组)，结合“数据结构”部分图可以更好的了解这个过程
static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
slabclass_t *p;
assert(((item *)ptr)->slabs_clsid == 0);
assert(id >= POWER_SMALLEST && id <= power_largest);
if (id < POWER_SMALLEST || id > power_largest)
return;
MEMCACHED_SLABS_FREE(size, id, ptr);
p = &slabclass[id];
#ifdef USE_SYSTEM_MALLOC
mem_malloced -= size;
free(ptr);
return;
#endif
// 增加freelist指针数组大小为2倍或初始化为16
if (p->sl_curr == p->sl_total) { /* need more space on the free list */
int new_size = (p->sl_total != 0) ? p->sl_total * 2 : 16;  /* 16 is arbitrary */
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;   // 将ptr指向的trunk放入freelist指针数组
p->requested -= size;
return;
}

　　        对于slabs_alloc和slabs_free只是使用slabs_lock互斥锁，控制多线程对临界区资源的访问，分别调用了上述的do_slabs_alloc和do_slabs_free函数，这里不做过多解释。
　　        内存管理模块对其它模块的接口主要有：slabs_init、slabs_alloc、slabs_free和slabs_clsid。
　　         slabs_init在main函数中初始化部分调用，slabs_clsid和slabs_alloc在do_item_alloc函数中，每次存入一个item申请内存时调用slabs_clsid获得item对应大小的slabclass_t的索引clsid，然后通过clsid调用slabs_alloc函数分配一个trunk（一个item保存在一个trunk中），slabs_free在item_free函数中，释放item时调用，将item所在的trunk放入slabclass[clsid]的空闲trunk块指针数组（slots）中。
　　        到此，slab部分介绍完毕，有什么高见敬请指教。
　　



版权声明：本文为博主原创文章，未经博主允许不得转载。