細說MySQL 之MEM_ROOT

細說MySQL 之MEM_ROOT

這篇文章會詳細解說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). */
#define MY_MAX(a, b) ((a) > (b) ? (a) : (b)) //求兩個數值之間的最大值
#define MY_MIN(a, b) ((a) < (b) ? (a) : (b)) //求兩個數值之間的最小值

下面再來看看MEM_ROOT結構體相關的信息:

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 < length &&
mem_root->first_block_usage++ >= ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP &&
(*prev)->left < ALLOC_MAX_BLOCK_TO_DROP)
{
next= *prev;
*prev= next->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 < length ; next= next->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*/
if ((next->left-= length) < mem_root->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遍歷的過程中，會去判斷freelist 中第一個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 < length ; next= next->next)
 
prev= &next->next;
} 

prev指向的是最後一個block的next指向的地址的地址：

所以將prev的地址替換為newblock的地址，即將該new block加到了free list的結尾:*prev=next;


總結：MEM_ROOT的內存分配采用的是啟發式分配算法，隨著後續block的數量越多，單個block的內存也會越大:block_size= mem_root->block_size * (mem_root->block_num >> 2).