memcached源碼分析-----slab內(nèi)存分配器
來源：程序員人生 發(fā)布時(shí)間：2015-03-01 00:51:48 閱讀次數(shù)：3184次
溫馨提示：本文用到了1些可以在啟動(dòng)memcached設(shè)置的全局變量。關(guān)于這些全局變量的含義可以參考《memcached啟動(dòng)參數(shù)詳解》。對(duì)這些全局變量，處理方式就像《如何瀏覽memcached源代碼》所說的那樣直接取其默許值。
slab內(nèi)存池分配器：
slab簡(jiǎn)介：
memcached使用了1個(gè)叫slab的內(nèi)存分配方法，有關(guān)slab的介紹可以參考鏈接1和鏈接2。可以簡(jiǎn)單地把它看做內(nèi)存池。memcached內(nèi)存池分配的內(nèi)存塊大小是固定的。雖然是固定大小，但memcached的能分配的內(nèi)存大小(尺寸)也是有很多種規(guī)格的。1般來講，是滿足需求的。
memcached聲明了1個(gè)slabclass_t結(jié)構(gòu)體類型，并且定義了1個(gè)slabclass_t類型數(shù)組slabclass(是1個(gè)全局變量)。可以把數(shù)組的每個(gè)元素稱為1個(gè)slab分配器。1個(gè)slab分配器能分配的內(nèi)存大小是固定的，不同的slab分配的內(nèi)存大小是不同的。下面借1幅經(jīng)典的圖來講明：
從每一個(gè)slab class(slab分配器)分配出去的內(nèi)存塊都會(huì)用指針連接起來的(連起來才不會(huì)丟失啊)。以下圖所示：
上圖是1個(gè)邏輯圖。每個(gè)item都不大，從幾B到1M。如果每個(gè)item都是地動(dòng)態(tài)調(diào)用malloc申請(qǐng)的，必將會(huì)造成很多內(nèi)存碎片。所以memcached的做法是，先申請(qǐng)1個(gè)比較大的1塊內(nèi)存，然后把這塊內(nèi)存劃分成1個(gè)個(gè)的item，并用兩個(gè)指針(prev和next)把這些item連接起來。所以實(shí)際的物理圖以下所示：
上圖中，每個(gè)slabclass_t都有1個(gè)slab數(shù)組。同1個(gè)slabclass_t的多個(gè)slab分配的內(nèi)存大小是相同的，不同的slabclass_t分配的內(nèi)存大小是不同的。由于每個(gè)slab分配器能分配出去的總內(nèi)存都是有1個(gè)上限的，所以對(duì)1個(gè)slabclass_t來講，要想分配很多內(nèi)存就必須有多個(gè)slab分配器。
肯定slab分配器的分配規(guī)格：
看完了圖，現(xiàn)在來看1下memcached是怎樣肯定slab分配器的分配規(guī)格的。由于memcached使用了全局變量，先來看1下全局變量。
//slabs.c文件 typedef struct { unsigned int size;//slab分配器分配的item的大小 unsigned int perslab; //每個(gè)slab分配器能分配多少個(gè)item void *slots; //指向空閑item鏈表 unsigned int sl_curr; //空閑item的個(gè)數(shù) //這個(gè)是已分配了內(nèi)存的slabs個(gè)數(shù)。list_size是這個(gè)slabs數(shù)組(slab_list)的大小 unsigned int slabs; //本slabclass_t可用的slab分配器個(gè)數(shù) //slab數(shù)組，數(shù)組的每個(gè)元素就是1個(gè)slab分配器，這些分配器都分配相同尺寸的內(nèi)存 void **slab_list; unsigned int list_size; //slab數(shù)組的大小, list_size >= slabs //用于reassign，指明slabclass_t中的哪一個(gè)塊內(nèi)存要被其他slabclass_t使用 unsigned int killing; size_t requested; //本slabclass_t分配出去的字節(jié)數(shù) } slabclass_t; #define POWER_SMALLEST 1 #define POWER_LARGEST 200 #define CHUNK_ALIGN_BYTES 8 #define MAX_NUMBER_OF_SLAB_CLASSES (POWER_LARGEST + 1) //數(shù)組元素雖然有MAX_NUMBER_OF_SLAB_CLASSES個(gè)，但實(shí)際上其實(shí)不是全部都使用的。 //實(shí)際使用的元素個(gè)數(shù)由power_largest指明 static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];//201 static int power_largest;//slabclass數(shù)組中,已使用了的元素個(gè)數(shù).
可以看到，上面的代碼定義了1個(gè)全局slabclass數(shù)組。這個(gè)數(shù)組就是前面那些圖的slabclass_t數(shù)組。雖然slabclass數(shù)組有201個(gè)元素，但可能其實(shí)不會(huì)所有元素都使用的。由全局變量power_largest指明使用了多少個(gè)元素.下面看1下slabs_init函數(shù)，該函數(shù)對(duì)這個(gè)數(shù)組進(jìn)行1些初始化操作。該函數(shù)會(huì)在main函數(shù)中被調(diào)用。
//slabs.c文件 static size_t mem_limit = 0;//用戶設(shè)置的內(nèi)存最大限制 static size_t mem_malloced = 0; //如果程序要求預(yù)先分配內(nèi)存，而不是到了需要的時(shí)候才分配內(nèi)存，那末 //mem_base就指向那塊預(yù)先分配的內(nèi)存. //mem_current指向還可使用的內(nèi)存的開始位置 //mem_avail指明還有多少內(nèi)存是可使用的 static void *mem_base = NULL; static void *mem_current = NULL; static size_t mem_avail = 0; //參數(shù)factor是擴(kuò)容因子，默許值是1.25 void slabs_init(const size_t limit, const double factor, const bool prealloc) { int i = POWER_SMALLEST - 1; //settings.chunk_size默許值為48，可以在啟動(dòng)memcached的時(shí)候通過-n選項(xiàng)設(shè)置 //size由兩部份組成: item結(jié)構(gòu)體本身 和 這個(gè)item對(duì)應(yīng)的數(shù)據(jù) //這里的數(shù)據(jù)也就是set、add命令中的那個(gè)數(shù)據(jù).后面的循環(huán)可以看到這個(gè)size變量會(huì) //根據(jù)擴(kuò)容因子factor漸漸擴(kuò)大，所以能存儲(chǔ)的數(shù)據(jù)長度也會(huì)變大的 unsigned int size = sizeof(item) + settings.chunk_size; mem_limit = limit;//用戶設(shè)置或默許的內(nèi)存最大限制 //用戶要求預(yù)分配1大塊的內(nèi)存，以后需要內(nèi)存，就向這塊內(nèi)存申請(qǐng)。 if (prealloc) {//默許值為false 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. Will allocate in smaller chunks "); } } //初始化數(shù)組，這個(gè)操作很重要，數(shù)組中所有元素的成員變量值都為0了 memset(slabclass, 0, sizeof(slabclass)); //slabclass數(shù)組中的第1個(gè)元素其實(shí)不使用 //settings.item_size_max是memcached支持的最大item尺寸，默許為1M(也就是網(wǎng)上 //所說的memcached存儲(chǔ)的數(shù)據(jù)最大為1MB)。 while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) { /* Make sure items are always n-byte aligned */ if (size % CHUNK_ALIGN_BYTES)//8字節(jié)對(duì)齊 size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES); //這個(gè)slabclass的slab分配器能分配的item大小 slabclass[i].size = size; //這個(gè)slabclass的slab分配器最多能分配多少個(gè)item(也決定了最多分配多少內(nèi)存) slabclass[i].perslab = settings.item_size_max / slabclass[i].size; size *= factor;//擴(kuò)容 } //最大的item power_largest = i; slabclass[power_largest].size = settings.item_size_max; slabclass[power_largest].perslab = 1; ... if (prealloc) {//預(yù)分配內(nèi)存 slabs_preallocate(power_largest); } }
上面代碼中出現(xiàn)的item是用來存儲(chǔ)我們放在memcached的數(shù)據(jù)。代碼中的循環(huán)決定了slabclass數(shù)組中的每個(gè)slabclass_t能分配的item大小，也就是slab分配器能分配的item大小，同時(shí)也肯定了slab分配器能分配的item個(gè)數(shù)。
上面的代碼還可以看到，可以通過增大settings.item_size_max而使得memcached可以存儲(chǔ)更大的1條數(shù)據(jù)信息。固然是有限制的，最大也只能為128MB。巧的是，slab分配器能分配的最大內(nèi)存也是受這個(gè)settings.item_size_max所限制。由于每個(gè)slab分配器能分配的最大內(nèi)存有上限，所以slabclass數(shù)組中的每個(gè)slabclass_t都有多個(gè)slab分配器，其用1個(gè)數(shù)組管理這些slab分配器。而這個(gè)數(shù)組大小是不受限制的，所以對(duì)某個(gè)特定的尺寸的item是可以有很多很多的。固然全部memcached能分配的總內(nèi)存大小也是有限制的，可以在啟動(dòng)memcached的時(shí)候通過-m選項(xiàng)設(shè)置，默許值為64MB。slabs_init函數(shù)中的limit參數(shù)就是memcached能分配的總內(nèi)存。
預(yù)分配內(nèi)存：
現(xiàn)在就假定用戶需要預(yù)先分配1些內(nèi)存，而不是等到客戶端發(fā)送存儲(chǔ)數(shù)據(jù)命令的時(shí)候才分配內(nèi)存。slabs_preallocate函數(shù)是為slabclass數(shù)組中每個(gè)slabclass_t元素預(yù)先分配1些空閑的item。由于item可能比較小(上面的代碼也能夠看到這1點(diǎn))，所以不能以item為單位申請(qǐng)內(nèi)存（這樣很容易造成內(nèi)存碎片）。因而在申請(qǐng)的使用就申請(qǐng)1個(gè)比較大的1塊內(nèi)存，然后把這塊內(nèi)存劃分成1個(gè)個(gè)的item，這樣就等于申請(qǐng)了多個(gè)item。本文將申請(qǐng)得到的這塊內(nèi)存稱為內(nèi)存頁，也就是申請(qǐng)了1個(gè)頁。如果全局變量settings.slab_reassign為真，那末頁的大小為settings.item_size_max，否則等于slabclass_t.size * slabclass_t.perslab。settings.slab_reassign主要用于平衡各個(gè)slabclass_t的。后文將統(tǒng)1使用內(nèi)存頁、頁大小。
現(xiàn)在就假定用戶需要預(yù)先分配內(nèi)存，看1下slabs_preallocate函數(shù)。該函數(shù)的參數(shù)值為使用到的slabclass數(shù)組元素個(gè)數(shù)。slabs_preallocate函數(shù)的調(diào)用是分配slab內(nèi)存塊和和設(shè)置item的。
//參數(shù)值為使用到的slabclass數(shù)組元素個(gè)數(shù) //為slabclass數(shù)組的每個(gè)元素(使用到的元素)分配內(nèi)存 static void slabs_preallocate (const unsigned int maxslabs) { int i; unsigned int prealloc = 0; //遍歷slabclass數(shù)組 for (i = POWER_SMALLEST; i <= POWER_LARGEST; i++) { if (++prealloc > maxslabs)//固然是只遍歷使用了的數(shù)組元素 return; if (do_slabs_newslab(i) == 0) {//為每個(gè)slabclass_t分配1個(gè)內(nèi)存頁 //如果分配失敗，將退出程序.由于這個(gè)預(yù)分配的內(nèi)存是后面程序運(yùn)行的基礎(chǔ) //如果這里分配失敗了，后面的代碼無從履行。所以就直接退出程序。 exit(1); } } } //slabclass_t中slab的數(shù)目是漸漸增多的。該函數(shù)的作用就是為slabclass_t申請(qǐng)多1個(gè)slab //參數(shù)id指明是slabclass數(shù)組中的那個(gè)slabclass_t static int do_slabs_newslab(const unsigned int id) { slabclass_t *p = &slabclass[id]; //settings.slab_reassign的默許值為false，這里就采取false。 int len = settings.slab_reassign ? settings.item_size_max : p->size * p->perslab;//其積 <= settings.item_size_max char *ptr; //mem_malloced的值通過環(huán)境變量設(shè)置，默許為0 if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) || (grow_slab_list(id) == 0) ||//增長slab_list(失敗返回0)。1般都會(huì)成功,除非沒法分配內(nèi)存 ((ptr = memory_allocate((size_t)len)) == 0)) {//分配len字節(jié)內(nèi)存(也就是1個(gè)頁) return 0; } memset(ptr, 0, (size_t)len);//清零內(nèi)存塊是必須的 //將這塊內(nèi)存切成1個(gè)個(gè)的item，固然item的大小有id所控制 split_slab_page_into_freelist(ptr, id); //將分配得到的內(nèi)存頁交由slab_list掌管 p->slab_list[p->slabs++] = ptr; mem_malloced += len; return 1; }
上面的do_slabs_newslab函數(shù)內(nèi)部調(diào)用了3個(gè)函數(shù)。函數(shù)grow_slab_list的作用是增大slab數(shù)組的大小(以下圖所示的slab數(shù)組)。memory_allocate函數(shù)則是負(fù)責(zé)申請(qǐng)大小為len字節(jié)的內(nèi)存。而函數(shù)split_slab_page_into_freelist則負(fù)責(zé)把申請(qǐng)到的內(nèi)存切分成多個(gè)item，并且把這些item用指向連起來，構(gòu)成雙向鏈表。以下圖所示：前面已見過這圖了，看完代碼再來看1下吧。
下面看1下那3個(gè)函數(shù)的具體實(shí)現(xiàn)。
//增加slab_list成員指向的內(nèi)存，也就是增大slab_list數(shù)組。使得可以有更多的slab分配器 //除非內(nèi)存分配失敗，否則都是返回1,不管是不是真正增大了 static int grow_slab_list (const unsigned int id) { slabclass_t *p = &slabclass[id]; if (p->slabs == p->list_size) {//用完了之前申請(qǐng)到的slab_list數(shù)組的所有元素 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; } //申請(qǐng)分配內(nèi)存，如果程序是有預(yù)分配內(nèi)存塊的，就向預(yù)分配內(nèi)存塊申請(qǐng)內(nèi)存 //否則調(diào)用malloc分配內(nèi)存 static void *memory_allocate(size_t size) { void *ret; //如果程序要求預(yù)先分配內(nèi)存，而不是到了需要的時(shí)候才分配內(nèi)存，那末 //mem_base就指向那塊預(yù)先分配的內(nèi)存. //mem_current指向還可使用的內(nèi)存的開始位置 //mem_avail指明還有多少內(nèi)存是可使用的 if (mem_base == NULL) {//不是預(yù)分配內(nèi)存 /* We are not using a preallocated large memory chunk */ ret = malloc(size); } else { ret = mem_current; //在字節(jié)對(duì)齊中，最后幾個(gè)用于對(duì)齊的字節(jié)本身就是沒成心義的(沒有被使用起來) //所以這里是先計(jì)算size是不是比可用的內(nèi)存大，然后才計(jì)算對(duì)齊 if (size > mem_avail) {//沒有足夠的可用內(nèi)存 return NULL; } //現(xiàn)在斟酌對(duì)齊問題，如果對(duì)齊后size 比mem_avail大也是無所謂的 //由于最后幾個(gè)用于對(duì)齊的字節(jié)不會(huì)真正使用 /* mem_current pointer _must_ be aligned!!! */ if (size % CHUNK_ALIGN_BYTES) {//字節(jié)對(duì)齊.保證size是CHUNK_ALIGN_BYTES (8)的倍數(shù) size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES); } mem_current = ((char*)mem_current) + size; if (size < mem_avail) { mem_avail -= size; } else {//此時(shí)，size比mem_avail大也無所謂 mem_avail = 0; } } return ret; } //將ptr指向的內(nèi)存頁劃分成1個(gè)個(gè)的item static void split_slab_page_into_freelist(char *ptr, const unsigned int id) { slabclass_t *p = &slabclass[id]; int x; for (x = 0; x < p->perslab; x++) { //將ptr指向的內(nèi)存劃分成1個(gè)個(gè)的item.1共劃成perslab個(gè) //并將這些item前后連起來。 //do_slabs_free函數(shù)本來是worker線程向內(nèi)存池歸還內(nèi)存時(shí)調(diào)用的。但在這里 //新申請(qǐng)的內(nèi)存也能夠當(dāng)作是向內(nèi)存池歸還內(nèi)存。把內(nèi)存注入內(nèi)存池中 do_slabs_free(ptr, 0, id); ptr += p->size;//size是item的大小 } } static void do_slabs_free(void *ptr, const size_t size, unsigned int id) { slabclass_t *p; item *it; assert(((item *)ptr)->slabs_clsid == 0); assert(id >= POWER_SMALLEST && id <= power_largest); if (id < POWER_SMALLEST || id > power_largest) return; p = &slabclass[id]; it = (item *)ptr; //為item的it_flags添加ITEM_SLABBED屬性，標(biāo)明這個(gè)item是在slab中沒有被分配出去 it->it_flags |= ITEM_SLABBED; //由split_slab_page_into_freelist調(diào)用時(shí)，下面4行的作用是 //讓這些item的prev和next相互指向，把這些item連起來. //當(dāng)本函數(shù)是在worker線程向內(nèi)存池歸還內(nèi)存時(shí)調(diào)用，那末下面4行的作用是, //使用鏈表頭插法把該item插入到空閑item鏈表中。 it->prev = 0; it->next = p->slots; if (it->next) it->next->prev = it; p->slots = it;//slot變量指向第1個(gè)空閑可使用的item p->sl_curr++;//空閑可使用的item數(shù)量 p->requested -= size;//減少這個(gè)slabclass_t分配出去的字節(jié)數(shù) return; }
在do_slabs_free函數(shù)的注釋說到，在worker線程向內(nèi)存池歸還內(nèi)存時(shí)，該函數(shù)也是會(huì)被調(diào)用的。由于同1slab內(nèi)存塊中的各個(gè)item歸還時(shí)間不同，所以memcached運(yùn)行1段時(shí)間后，item鏈表就會(huì)變得很混亂，不會(huì)像上面那個(gè)圖那樣。有可能以下圖那樣：
雖然混亂，但肯定還是會(huì)有前面那張邏輯圖那樣的清晰鏈表圖，其中slots變量指向第1個(gè)空閑的item。
向內(nèi)存池申請(qǐng)內(nèi)存：
與do_slabs_free函數(shù)對(duì)應(yīng)的是do_slabs_alloc函數(shù)。當(dāng)worker線程向內(nèi)存池申請(qǐng)內(nèi)存時(shí)就會(huì)調(diào)用該函數(shù)。在調(diào)用之前就要根據(jù)所申請(qǐng)的內(nèi)存大小，肯定好要向slabclass數(shù)組的哪一個(gè)元素申請(qǐng)內(nèi)存了。函數(shù)slabs_clsid就是完成這個(gè)任務(wù)。
unsigned int slabs_clsid(const size_t size) {//返回slabclass索引下標(biāo)值 int res = POWER_SMALLEST;//res的初始值為1 //返回0表示查找失敗，由于slabclass數(shù)組中，第1個(gè)元素是沒有使用的 if (size == 0) return 0; //由于slabclass數(shù)組中各個(gè)元素能分配的item大小是升序的 //所以從小到大直接判斷便可在數(shù)組找到最小但又能滿足的元素 while (size > slabclass[res].size) if (res++ == power_largest) /* won't fit in the biggest slab */ return 0; return res; }
在do_slabs_alloc函數(shù)中如果對(duì)應(yīng)的slabclass_t有空閑的item，那末就直接將之分配出去。否則就需要擴(kuò)充slab得到1些空閑的item然后分配出去。代碼以下面所示：
//向slabclass申請(qǐng)1個(gè)item。在調(diào)用該函數(shù)之前，已調(diào)用slabs_clsid函數(shù)肯定 //本次申請(qǐng)是向哪一個(gè)slabclass_t申請(qǐng)item了，參數(shù)id就是指明是向哪一個(gè)slabclass_t //申請(qǐng)item。如果該slabclass_t是有空閑item，那末就從空閑的item隊(duì)列中分配1個(gè) //如果沒有空閑item，那末就申請(qǐng)1個(gè)內(nèi)存頁。再重新申請(qǐng)的頁中分配1個(gè)item //返回值為得到的item，如果沒有內(nèi)存了，返回NULL static void *do_slabs_alloc(const size_t size, unsigned int id) { slabclass_t *p; void *ret = NULL; item *it = NULL; if (id < POWER_SMALLEST || id > power_largest) {//下標(biāo)越界 MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0); return NULL; } p = &slabclass[id]; assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0); //如果p->sl_curr等于0，就說明該slabclass_t沒有空閑的item了。 //此時(shí)需要調(diào)用do_slabs_newslab申請(qǐng)1個(gè)內(nèi)存頁 if (! (p->sl_curr != 0 || do_slabs_newslab(id) != 0)) { //當(dāng)p->sl_curr等于0并且do_slabs_newslab的返回值等于0時(shí)，進(jìn)入這里 /* We don't have more memory available */ ret = NULL; } else if (p->sl_curr != 0) { //除非do_slabs_newslab調(diào)用失敗，否則都會(huì)來到這里.不管1開始sl_curr是不是為0。 //p->slots指向第1個(gè)空閑的item，此時(shí)要把第1個(gè)空閑的item分配出去 /* return off our freelist */ it = (item *)p->slots; p->slots = it->next;//slots指向下1個(gè)空閑的item if (it->next) it->next->prev = 0; p->sl_curr--;//空閑數(shù)目減1 ret = (void *)it; } if (ret) { p->requested += size;//增加本slabclass分配出去的字節(jié)數(shù) } return ret; }
可以看到在do_slabs_alloc函數(shù)的內(nèi)部也是通過調(diào)用do_slabs_newslab增加item的。
在本文前面的代碼中，都沒有看到鎖的。作為memcached這個(gè)用鎖大戶，有點(diǎn)不正常。其實(shí)前面的代碼中，有1些是要加鎖才能訪問的，比如do_slabs_alloc函數(shù)。之所以上面的代碼中沒有看到，是由于memcached使用了包裹函數(shù)(這個(gè)概念對(duì)應(yīng)看過《UNIX網(wǎng)絡(luò)編程》的讀者來講很熟習(xí)吧)。memcached在包裹函數(shù)中加鎖后，才訪問上面的那些函數(shù)的。下面就是兩個(gè)包裹函數(shù)。
static pthread_mutex_t slabs_lock = PTHREAD_MUTEX_INITIALIZER; void *slabs_alloc(size_t size, unsigned int id) { void *ret; pthread_mutex_lock(&slabs_lock); ret = do_slabs_alloc(size, id); pthread_mutex_unlock(&slabs_lock); return ret; } 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); }
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
