這篇文章會詳細解說mysql中使用非常廣泛的mem_root的結構體，同時省去debug部分的信息，僅分析正常情況下，mysql中使用mem_root來做內存分配的部分。
在具體分析之前我們先例舉在該結構體使用過程中用到的一些宏:
#define?MALLOC_OVERHEAD?8?//分配過程中，需要保留一部分額外的空間 #define?ALLOC_MAX_BLOCK_TO_DROP?4096?//后續會繼續分析該宏的用途 #define?ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP?10?//后續會繼續分析該宏的用途 #define?ALIGN_SIZE(A)?MY_ALIGN((A),sizeof(double)) #define?MY_ALIGN(A,L)?(((A)?+?(L)?-?1)?&?~((L)?-?1)) #define?ALLOC_ROOT_MIN_BLOCK_SIZE?(MALLOC_OVERHEAD?+?sizeof(USED_MEM)?+?8) /*?Define?some?useful?general?macros?(should?be?done?after?all?headers).?*/ /*作者：www.manongjc.com??*/ #define?MY_MAX(a,?b)?((a)?>?(b)???(a)?:?(b))?//求兩個數值之間的最大值 #define?MY_MIN(a,?b)?((a)?<p>下面再來看看MEM_ROOT結構體相關的信息:</p><pre class="brush:php;toolbar:false">typedef?struct?st_mem_root { ????USED_MEM????*free;??????????????????/*?free?block?link?list的鏈表頭指針?*/ ????USED_MEM????*used;??????????????????/*?used?block?link?list的鏈表頭指針?*/ ????USED_MEM????*pre_alloc;?????????????/*?預先分配的block?*/ ????size_t????????min_malloc;?????????????/*?如果block剩下的可用空間小于該值，將會從free?list移動到used?list?*/ ????size_t????????block_size;?????????????/*?每次初始化的空間大小?*/ ????unsigned?int????block_num;??????????????/*?記錄實際的block數量,初始化為4?*/ ????unsigned?int????first_block_usage;??????/*?free?list中的第一個block?測試不滿足分配空間大小的次數?*/ ????void?(*error_handler)(?void?);??????????/*?分配失敗的錯誤處理函數?*/ }?MEM_ROOT;
以下是分配具體的block信息.
typedef?struct?st_used_mem {? ????struct?st_used_mem?*next;?//指向下一個分配的block ????unsigned?int?left;?//該block剩余的空間大小 ????unsigned?int?size;?//該block的總大小 }?USED_MEM;
其實MEM_ROOT在分配過程中，是通過雙向鏈表來管理used和free的block:
MEM_ROOT的初始化過程如下:
void?init_alloc_root(?MEM_ROOT?*mem_root,?size_t?block_size,?size_t?pre_alloc_size?__attribute__(?(unused)?)?) { ????mem_root->free????????????=?mem_root->used?=?mem_root->pre_alloc?=?0; ????mem_root->min_malloc????????=?32; ????mem_root->block_size????????=?block_size?-?ALLOC_ROOT_MIN_BLOCK_SIZE; ????mem_root->error_handler????????=?0; ????mem_root->block_num????????=?4;?/*?We?shift?this?with?>>2?*/ ????mem_root->first_block_usage????=?0; }
初始化過程中，block_size空間為block_size-ALLOC_ROOT_MIN_BLOCK_SIZE。因為在內存不夠，需要擴容時，是通過mem_root->block_num >>2 *?block_size 來擴容的，所以mem_root->block_num >>2 至少為1，因此在初始化的過程中mem_root->block_num=4(注:4>>2=1)。
下面來看看具體分配內存的步驟:
void?*alloc_root(?MEM_ROOT?*mem_root,?size_t?length?) { ????size_t????????get_size,?block_size; ????uchar????????*?point; ????reg1?USED_MEM????*next?=?0; ????reg2?USED_MEM????**prev; ????length?=?ALIGN_SIZE(?length?); ????if?(?(*(prev?=?&mem_root->free)?)?!=?NULL?) ????{ ????????if?(?(*prev)->left?first_block_usage++?>=?ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP?&& ?????????????(*prev)->left?next;?/*?Remove?block?from?list?*/ ????????????next->next????????????=?mem_root->used; ????????????mem_root->used????????????=?next; ????????????mem_root->first_block_usage????=?0; ????????} ????????for?(?next?=?*prev;?next?&&?next->left?next?) ????????????prev?=?&next->next; ????} ????if?(?!next?) ????{???????/*?Time?to?alloc?new?block?*/ ????????block_size????=?mem_root->block_size?*?(mem_root->block_num?>>?2); ????????get_size????=?length?+?ALIGN_SIZE(?sizeof(USED_MEM)?); ????????get_size????=?MY_MAX(?get_size,?block_size?); ????????if?(?!(next?=?(USED_MEM?*)?my_malloc(?get_size,?MYF(?MY_WME?|?ME_FATALERROR?)?)?)?) ????????{ ????????????if?(?mem_root->error_handler?) ????????????????(*mem_root->error_handler)(); ????????????DBUG_RETURN(?(void?*)?0?);??????????????????????????????/*?purecov:?inspected?*/ ????????} ????????mem_root->block_num++; ????????next->next????=?*prev; ????????next->size????=?get_size; ????????next->left????=?get_size?-?ALIGN_SIZE(?sizeof(USED_MEM)?);????/*?bug:如果該block是通過mem_root->block_size?*?(mem_root->block_num?>>?2)計算出來的，則已經去掉了ALIGN_SIZE(sizeof(USED_MEM)，這里重復了。?*/ ????????*prev????????=?next; ????} ????point?=?(uchar?*)?(?(char?*)?next?+?(next->size?-?next->left)?); /*TODO:?next?part?may?be?unneded?due?to?mem_root->first_block_usage?counter*/ /*?作者：www.manongjc.com?*/ ????if?(?(next->left?-=?length)?min_malloc?) ????{???????????????????????????????????????????????????????????????????????/*?Full?block?*/ ????????*prev????????????????=?next->next;???????????????????/*?Remove?block?from?list?*/ ????????next->next????????????=?mem_root->used; ????????mem_root->used????????????=?next; ????????mem_root->first_block_usage????=?0; ????} }
上述代碼的具體邏輯如下:
1.查看free鏈表，尋找滿足空間的block。如果找到了合適的block,則：
1.1 直接返回該block從size-left處的初始地址即可。當然，在free list遍歷的過程中，會去判斷free?list
中第一個block中left的空間不滿足需要分配的空間，且該block中已經查找過了10次
(ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP)都不滿足分配長度，且該block剩余空間小于
4k(ALLOC_MAX_BLOCK_TO_DROP),則將該block 移動到used鏈表中。
2.如果free鏈表中，沒有合適的block，則：
2.1 分配 mem_root->block_size * (mem_root->block_num >> 2)和length+ALIGN_SIZE(sizeof(USED_MEM))
中比較大的作為新的block內存空間。
2.2?根據該block的使用情況，將該block掛在used或者free鏈表上。
這里需要注意的是二級指針的使用:
for?(next=?*prev?;?next?&&?next->left?next) prev=?&next->next; }
prev指向的是最后一個block的next指向的地址的地址：
所以將prev的地址替換為new?block的地址，即將該new block加到了free list的結尾:*prev=next;
總結：
MEM_ROOT的內存分配采用的是啟發式分配算法，隨著后續block的數量越多，單個block的內存也會越大:block_size= mem_root->block_size * (mem_root->block_num >> 2)?.
