C语言的内存管理一直是开发者绕不过去的坎，像memcached这种接收大量请求的框架来说，频繁的内存调用和内存泄露是名副其实的性能杀手。malloc/free有三大缺点：1.容易造成内存泄露；2.频繁调用会造成大量内存碎片无法回收重新利用，降低内存利用率；3.作为系统调用，其系统开销远远大于一般函数调用。现在最常用的内存管理方案是使用内存池替代malloc/free调用，内存池方案的基本思想是预先分配一大块内存，此后的内存申请与释放都只操作这块内存。至于具体的实现细节嘛，不同的系统会根据实际需求制定详细的方案。
slabs内存管理系统
memcached使用slabs系统分配内存，slabs系统只为存储外部数据而设计，也就是说所有的key-value数据都存储在slabs系统里，而memcached的其它内存请求则通过普通的malloc/free来申请，因为这些请求的数量和频率决定了它们不会对整个系统的性能造成影响。
slabs系统也是一种内存池方案，首先会将整个预先分配的内存空间分为若干个slab class来接收不同size的内存请求，slab class的信息保存在数组slabclass[]中。每个slab class由多个slab/page组成，同一个slab class的slab地址也不一定是连续的，一个slab是向slabclass内存池申请内存的最小单位，当slabclass内存不足时就向内存池申请一个slab的空间。每个slab/page又被划分为多个chunk，一个chunk负责装载一个item（包含key，value的数据结构）。这些slab
class的chunk的大小从最小值开始以factor为乘法系统递增，直到chunk的大小达到page的最大限制，默认情况下factor为1.25，page的大小限制等于item的大小限制item_size_max是1MB。
例如假设id为1的slab class中chunk大小设置为96B，那么id为2的slab class中chunk大小是96*1.25=120B，id为3的slab class中chunk大小本应是120B*1.25=150B，然而memcached要求chunk大小以8字节对齐，所以实际为152B…以此类推直至chunk大小超过1MB。这么做的目的是根据内存请求大小快速定位slab class 的id，例如新申请的大小为128B的内存空间来自在id为3的slab class中。
slabcalss_t是描述slab class 的数据结构
typedef struct {
unsigned int size; /* sizes of items */
unsigned int perslab; /* how many items per slab */
void **slots; /* slot地址数组 */
unsigned int sl_total; /* slots数组长度 */
unsigned int sl_curr; /* slots数组中可用空槽的数量 */
void *end_page_ptr; /* 最近分配页中第一个空闲chunk的地址 */
unsigned int end_page_free; /* 最近分配页中剩余chunk数量 */
unsigned int slabs; /* 这个class里slabs数量 */
void **slab_list; /* slab地址数组 */
unsigned int list_size; /* slab_list数组长度 */
unsigned int killing; /* index+1 of dying slab, or zero if none */
size_t requested; /* The number of requested bytes */
} slabclass_t;slab系统中的空闲空间分为两类，一类是曾经被使用过的chunk释放后形成的空槽，在结构slabclass_t中用指针数组slots存放，sl_curr表示现有可用空槽数量；另一类是之前从未使用过的空间，它们位于最新分配的一个page里，在结构slabclass_t中end_page_ptr指向第一个这样的chunk地址，而end_page_free表示最后一个page中还剩余的这种空闲空间的数量。
相关函数
slabs_init
初始化slabclass[]数组
do_slabs_alloc
do_slabs_alloc负责分配slabs系统中的空闲空间。首先优先使用slots里存放的“空槽”，如果不存在则使用end_page_ptr指向的空间。但是如果不存在空槽且最后一个page也没有空余空间，则使用do_slabs_newslab(id)从slabs内存池里再申请一个slab/page的空间.
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);
/* 如果空槽和最近分配页均已分配光且向内存池申请新的slab也失败的话，返回NULL */
if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||
do_slabs_newslab(id) != 0)) {
/* 没有可用的内存 */
ret = NULL;
} else if (p->sl_curr != 0) {
/* 返回一个空槽的地址 */
ret = p->slots[--p->sl_curr];
} else {
/* 返回p->end_page_ptr */
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_free
处理chunk空间释放的函数。只是将被释放的chunk地址存放进slots数组，并维护slots数组的长度。
do_slabs_newslab
处理page空间申请的函数。首先判断整个slabs系统的地址空间是否申请，如果没有则使用malloc申请。再从slabs系统的地址空间里申请一个page的空间，将地址存放进slab_list数组，并修改end_page_ptr和end_page_free。
Item
item结构相当于了储存在memcached中的一条条数据，item实例即是也是slabs系统服务的对象，一个item实例享用一个chunk的空间。每个slab class存储的item实例都会单独组成一个双向链表，item结构中的prev和next指针分别表示它在链表中的前驱后继节点，而h_next指针用于hashtable中的冲突处理。
typedef struct _stritem {
struct _stritem *next;
struct _stritem *prev;
struct _stritem *h_next; /* hash chain next */
rel_time_t time; /* least recent access */
rel_time_t exptime; /* expire time */
int nbytes; /* size of data */
unsigned short refcount;
uint8_t nsuffix; /* length of flags-and-length string */
uint8_t it_flags; /* ITEM_* above */
uint8_t slabs_clsid;/* which slab class we're in */
uint8_t nkey; /* key length, w/terminating null and padding */
union {
uint64_t cas;
char end;
} data[];
} item;下面是item中data的格式，只有当it_flags为ITEM_CAS时，data的首部分才是CAS id，CAS id的长度是固定为8字节。item结构中的nkey表示key部分的长度，nsuffix表示flags和length部分的长度之和，使用这两个值可以快速得到value的地址。
CAS id
key
flags
length
value
memcached定义了几个宏以获取data的各个部分，例如：
#define ITEM_key(item) (((char*)&((item)->data)) \
+ (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))
这个宏得到一个item实例中data的key，如果it_flags不是ITEM_CAS，key的地址就是(item)->data的地址；否则，key的地址是(item)->data的地址加上64比特，因为要跳过8字节的CAS id部分。
item相关函数
do_item_alloc()
负责为item实例分配存储空间，memcached不会直接调用slabs函数为item分配内存空间，而是会先从链表里寻找可替换的item，使用它占用的空间，然后才会考虑请slabs系统处理。
如下面的代码，先从其所在slabs class的item链表最后一个item （tails[id]）开始向前遍历，直到找到发现一个引用数为0且过期的item，新的item将使用这个过期item的内存空间。如果没有找到这样的item则调用slabs_alloc为item分配新空间。
for (search = tails[id];
tries > 0 && search != NULL;
tries--, search=search->prev) {
if (search->refcount == 0 &&
((search->time < oldest_live) || // dead by flush
(search->exptime != 0 && search->exptime < current_time))) {
it = search;
…
/* 一些统计工作 */
…
it->refcount = 1;
/* 调整这个slabs calss的使用总空间 */
slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
do_item_unlink(it);
/* Initialize the item block: */
it->slabs_clsid = 0;
it->refcount = 0;
break;
}
}
但是如果此时slabs内存空间已耗尽，slabs_alloc会返回NULL，此时需要使用LRU算法将某一个item强行替换出去。Memcached的LRU算法也是从tails[id]开始向前遍历，直到发现一个引用数为0的item，调用do_item_unlink移除旧item，再调用slabs_alloc为新item分配空间。注意这里的遍历不会搜索某个slabs class的所有item，而只会搜索尾部50个item。
Hashtable
memcached的hash算法细节不是这里需要研究的重点，但hashtable的设计倒是值得一看。hashtable的作用是通过数据的key快速找到存储这块数据的地址，也就是相应的item结构的指针。
memcached的hashtable用指针数组primary_hashtable表示，数组的每一项就是一个hashtable的bucket，内容即是散列到这个bucket的item指针。hashtable采用链表法处理冲突，前面已经介绍过item数据结构中的h_next指针。memcached的bucket不是固定不变的，当hashtable的item总数量超过bucket数量的1.5倍时，hashtable会将bucket数量扩充为原先的两倍。
memcached会创建一个线程专门维护hashtable的扩展，这段代码在main.c的start_assoc_maintenance_thread函数里。一般情况下这个线程被pthread_cond_wait阻塞，当主线程发现需要扩展时用pthread_cond_signal唤醒这个线程。
为了hashtable的扩展和复制过程不能影响hashtable的查询请求，hashtable使用变量expand_bucket表示复制进程进行到了哪一个bucket。查询hashtable代码如下：
assoc_find
#define hashmask(n) (hashsize(n)-1)
// 哈希表的bucket数是2的hashpower次方，所以
// (hash_value & hashmask(hashpower))即是hash_value对应的bucket
item *assoc_find(const char *key, const size_t nkey) {
uint32_t hv = hash(key, nkey, 0);
item *it;
unsigned int oldbucket;
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
// 如果哈希表正在扩展且复制进程还没有超过key对应的bucket时，
// 应该去old_hashtable中查找
it = old_hashtable[oldbucket];
} else {
it = primary_hashtable[hv & hashmask(hashpower)];
}
// 查找冲突链表
item *ret = NULL;
int depth = 0;
while (it) {
if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
ret = it;
break;
}
it = it->h_next;
++depth;
}
MEMCACHED_ASSOC_FIND(key, nkey, depth);
return ret;
}
assoc_insert
将item插入哈希表，并判断是否调用assoc_expand扩展哈希表。
assoc_expand
保存old_hashtable并初始化primary_hashtable，最后使用pthread_cond_signal唤醒维护哈希表的线程开始复制工作。
引自http://www.cozyshu.com/memcached-slabs/
do_slabs_newslab 解析
Q:
split_slab_page_into_freelist是要把slab插入freelist中，
为什么里面调用了do_slabs_free：释放slabs？
A：split_slab_page_into_freelist是把新分配的slab页里所有的item放入回收槽slot中
(item插入slot头部，并it->it_flags |= ITEM_SLABBED)，
再将slablist指向最新分配的slab页：p->slab_list[p->slabs++] = ptr；