Memcached源碼學習

大致浏覽了一下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，定義如下：

2. typedef struct {  
4.     unsigned int size;      /* sizes of items */  
5.     unsigned int perslab;   /* how many items per slab */  
6.   
7.     void **slots;           /* list of item ptrs */  
8.     unsigned int sl_total;  /* size of previous array */  
9.     unsigned int sl_curr;   /* first free slot */  
10.   
11.     void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */  
12.     unsigned int end_page_free; /* number of items remaining at end of last alloced page */  
13.   
14.     unsigned int slabs;     /* how many slabs were allocated for this class */  
15.   
16.     void **slab_list;       /* array of slab pointers */  
17.     unsigned int list_size; /* size of prev array */  
18.   
19.     unsigned int killing;  /* index+1 of dying slab, or zero if none */  
20.     size_t requested; /* The number of requested bytes */  
21. } 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數據結構如下圖所示（圖中實箭頭表示指針，小箭頭表示索引或數量）：

•實現介紹（函數介紹過程中，結合上圖理解起來更容易）

下面將對主要的代碼進行解析：

2. /* 
4.  * Figures out which slab class (chunk size) is required to store an item of 
5.  * a given size. 
6.  * 
7.  * Given object size, return id to use when allocating/freeing memory for object 
8.  * 0 means error: can't store such a large object 
9.  */  
10.   
11. unsigned int slabs_clsid(const size_t size) {  
12.     int res = POWER_SMALLEST;  
13.   
14.     if (size == 0)  
15.         return 0;  
16.     // 從後向前遍歷slabclass數組，找到最適合放入size大小的slabclass_t的索引   
17.     while (size > slabclass[res].size)  
18.         if (res++ == power_largest)     /* won't fit in the biggest slab */  
19.             return 0;  
20.     return res;  
21. }  

1. /** 
2.  * Determines the chunk sizes and initializes the slab class descriptors 
3.  * accordingly. 
4.  */  
5. void slabs_init(const size_t limit, const double factor, const bool prealloc) {  
6.     int i = POWER_SMALLEST - 1;  
7.     unsigned int size = sizeof(item) + settings.chunk_size;    // 初始化trunk大小   
8.   
9.     mem_limit = limit;  
10.   
11.     // 指定為預分配內存，則一次行分配全部內存（limit大小）   
12.     if (prealloc) {  
13.         /* Allocate everything in a big chunk with malloc */  
14.         mem_base = malloc(mem_limit);  
15.         if (mem_base != NULL) {  
16.             mem_current = mem_base;  
17.             mem_avail = mem_limit;  
18.         } else {  
19.             fprintf(stderr, "Warning: Failed to allocate requested memory in"  
20.                     " one large chunk.\nWill allocate in smaller chunks\n");  
21.         }  
22.     }  
23.   
24.     memset(slabclass, 0, sizeof(slabclass));  
25.     // 初始化每個slabclass_t的trunk大小和每個slab中trunk數量   
26.     // slabclass中每個slabclass_t的trunk大小增長為factor倍   
27.     // 注意 i 從索引 1 開始   
28.     while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {  
29.         /* Make sure items are always n-byte aligned */  
30.         if (size % CHUNK_ALIGN_BYTES)                             // 內存8字節對齊   
31.             size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);  
32.   
33.         slabclass[i].size = size;  
34.         slabclass[i].perslab = settings.item_size_max / slabclass[i].size;  
35.         size *= factor;  
36.         if (settings.verbose > 1) {  
37.             fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",  
38.                     i, slabclass[i].size, slabclass[i].perslab);  
39.         }  
40.     }  
41.   
42.     // slabclass中最後一個slabclass_t的trunk大小設置為最大item大小   
43.     power_largest = i;  
44.     slabclass[power_largest].size = settings.item_size_max;  
45.     slabclass[power_largest].perslab = 1;  
46.     if (settings.verbose > 1) {  
47.         fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",  
48.                 i, slabclass[i].size, slabclass[i].perslab);  
49.     }  
50.     ....// 省略   
51. }  

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

1. // 初始化或增大slab_list指針數組   
2. static int grow_slab_list (const unsigned int id) {  
3.     slabclass_t *p = &slabclass[id];  
4.     // slabclass_t中已經分配的slabs數量與slab指針數組的大小相同，表示已滿,如<span >下圖</span>所示   
5.     // 則，重新分配slab指針數組，指針數組增大為以前的2倍或初始化為16   
6.     if (p->slabs == p->list_size) {  
7.         size_t new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;  
8.         void *new_list = realloc(p->slab_list, new_size * sizeof(void *));  
9.         if (new_list == 0) return 0;  
10.         p->list_size = new_size;  
11.         p->slab_list = new_list;  
12.     }  
13.     return 1;  
14. }  

1. // 初始化或重新分配一個slabclass[id]中的slab（每個slab包含perslab個trunk，每個trunk大小為size），<span >見下圖</span>！   
2. static int do_slabs_newslab(const unsigned int id) {  
3.     slabclass_t *p = &slabclass[id];  
4.     int len = p->size * p->perslab; // 每個trunk的size * 每個slab中trunk數量   
5.     char *ptr;  
6.   
7.     // 第一次未分配時，p->slabs==0, mem_malloced==0   
8.     // 如果已經分配過，mem_malloced + len > mem_limit表示超過定義的內存   
9.     if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||  
10.         (grow_slab_list(id) == 0) ||  // 如果slabs指針數組滿了或未初始化，   
11.                                       // 則增大slabs指針數組的大小(2倍或初始化為16)   
12.         ((ptr = memory_allocate((size_t)len)) == 0)) {  // 調用malloc分配len大小內存或調整當前指針(預分配時)   
13.   
14.         MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);  
15.         return 0;  
16.     }  
17.   
18.     memset(ptr, 0, (size_t)len);  
19.     p->end_page_ptr = ptr;              // 當前slab可用trunk起始地址   
20.     p->end_page_free = p->perslab;      // 當前slab可用的trunk數量   
21.   
22.     p->slab_list[p->slabs++] = ptr;     // 將分配的slab(trunk列表)，放到slabs數組中   
23.     mem_malloced += len;  
24.     MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);  
25.   
26.     return 1;  
27. }      

1. /* 分配一個trunk數據結構，過程見<span >下圖</span> */  
2. static void *do_slabs_alloc(const size_t size, unsigned int id) {  
3.     slabclass_t *p;  
4.     void *ret = NULL;  
5.   
6.     // 索引非法   
7.     if (id < POWER_SMALLEST || id > power_largest) {  
8.         MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);  
9.         return NULL;  
10.     }  
11.   
12.     p = &slabclass[id];  
13.     assert(p->sl_curr == 0 || ((item *)p->slots[p->sl_curr - 1])->slabs_clsid == 0);  
14.   
15. #ifdef USE_SYSTEM_MALLOC   
16.     if (mem_limit && mem_malloced + size > mem_limit) {  
17.         MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);  
18.         return 0;  
19.     }  
20.     mem_malloced += size;  
21.     ret = malloc(size);  
22.     MEMCACHED_SLABS_ALLOCATE(size, id, 0, ret);  
23.     return ret;  
24. #endif   
25.   
26.     /* fail unless we have space at the end of a recently allocated page, 
27.        we have something on our freelist, or we could allocate a new page */  
28.     if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||  
29.            do_slabs_newslab(id) != 0)) {  
30.         /* We don't have more memory available */  
31.         ret = NULL;  
32.     } else if (p->sl_curr != 0) {       // freelist非空，優先從freelist分配   
33.         /* return off our freelist */  
34.         ret = p->slots[--p->sl_curr];  
35.     } else {                            // 剛分配的   
36.         /* if we recently allocated a whole page, return from that */  
37.         assert(p->end_page_ptr != NULL);  
38.         ret = p->end_page_ptr;  
39.         if (--p->end_page_free != 0) {  
40.             p->end_page_ptr = ((caddr_t)p->end_page_ptr) + p->size;  
41.         } else {  
42.             p->end_page_ptr = 0;  
43.         }  
44.     }  
45.   
46.     if (ret) {  
47.         p->requested += size;  
48.         MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);  
49.     } else {  
50.         MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);  
51.     }  
52.   
53.     return ret;  
54. }  

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的過程圖：

1. // 釋放trunk結構(將其放入freelist指針數組)，結合“數據結構”部分圖<span >可以更好的了解這個過程   
2. static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {  
3.     slabclass_t *p;  
4.   
5.     assert(((item *)ptr)->slabs_clsid == 0);  
6.     assert(id >= POWER_SMALLEST && id <= power_largest);  
7.     if (id < POWER_SMALLEST || id > power_largest)  
8.         return;  
9.   
10.     MEMCACHED_SLABS_FREE(size, id, ptr);  
11.     p = &slabclass[id];  
12.   
13. #ifdef USE_SYSTEM_MALLOC   
14.     mem_malloced -= size;  
15.     free(ptr);  
16.     return;  
17. #endif   
18.   
19.     // 增加freelist指針數組大小為2倍或初始化為16   
20.     if (p->sl_curr == p->sl_total) { /* need more space on the free list */  
21.         int new_size = (p->sl_total != 0) ? p->sl_total * 2 : 16;  /* 16 is arbitrary */  
22.         void **new_slots = realloc(p->slots, new_size * sizeof(void *));  
23.         if (new_slots == 0)  
24.             return;  
25.         p->slots = new_slots;  
26.         p->sl_total = new_size;  
27.     }  
28.     p->slots[p->sl_curr++] = ptr;   // 將ptr指向的trunk放入freelist指針數組   
29.     p->requested -= size;  
30.     return;  
31. } 

對於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部分介紹完畢，有什麼高見敬請指教。