大致浏覽了一下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[i].size = size;
- slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
- 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中最後一個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, "slab class %3d: chunk size %9u perslab %7u\n",
- i, slabclass[i].size, slabclass[i].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指針數組的大小相同,表示已滿,如<span >下圖</span>所示
- // 則,重新分配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),<span >見下圖</span>!
- 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數據結構,過程見<span >下圖</span> */
- 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指針數組),結合“數據結構”部分圖<span >可以更好的了解這個過程
- 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部分介紹完畢,有什麼高見敬請指教。