程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> 細說MySQL 之MEM_ROOT

細說MySQL 之MEM_ROOT

編輯:關於PHP編程

細說MySQL 之MEM_ROOT


這篇文章會詳細解說MySQL中使用非常廣泛的MEM_ROOT的結構體,同時省去debug部分的信息,僅分析正常情況下,mysql中使用MEM_ROOT來做內存分配的部分。

在具體分析之前我們先例舉在該結構體使用過程中用到的一些宏:
  1. #define MALLOC_OVERHEAD 8 //分配過程中,需要保留一部分額外的空間
  2. #define ALLOC_MAX_BLOCK_TO_DROP 4096 //後續會繼續分析該宏的用途
  3. #define ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP 10 //後續會繼續分析該宏的用途

  4. #define ALIGN_SIZE(A) MY_ALIGN((A),sizeof(double))
  5. #define MY_ALIGN(A,L) (((A) + (L) - 1) & ~((L) - 1))

  6. #define ALLOC_ROOT_MIN_BLOCK_SIZE (MALLOC_OVERHEAD + sizeof(USED_MEM) + 8)
  7. /* Define some useful general macros (should be done after all headers). */
  8. #define MY_MAX(a, b) ((a) > (b) ? (a) : (b)) //求兩個數值之間的最大值
  9. #define MY_MIN(a, b) ((a) < (b) ? (a) : (b)) //求兩個數值之間的最小值

下面再來看看MEM_ROOT結構體相關的信息:
  1. typedef struct st_mem_root
  2. {
  3. USED_MEM *free; //free block link list的鏈表頭指針
  4. USED_MEM *used;//used block link list的鏈表頭指針
  5. USED_MEM *pre_alloc; //預先分配的block
  6. size_t min_malloc; //如果block剩下的可用空間小於該值,將會從free list移動到used list
  7. size_t block_size; //每次初始化的空間大小
  8. unsigned int block_num; //記錄實際的block數量,初始化為4
  9. unsigned int first_block_usage; //free list中的第一個block 測試不滿足分配空間大小的次數
  10. void (*error_handler)(void);//分配失敗的錯誤處理函數
  11. } MEM_ROOT;

以下是分配具體的block信息.
  1. typedef struct st_used_mem
  2. {
  3. struct st_used_mem *next; //指向下一個分配的block
  4. unsigned int left; //該block剩余的空間大小
  5. unsigned int size; //該block的總大小
  6. } USED_MEM;
其實MEM_ROOT在分配過程中,是通過雙向鏈表來管理used和free的block:


MEM_ROOT的初始化過程如下:
  1. void init_alloc_root(MEM_ROOT *mem_root, size_t block_size,size_t pre_alloc_size __attribute__((unused)))
  2. {
  3. mem_root->free= mem_root->used= mem_root->pre_alloc= 0;
  4. mem_root->min_malloc= 32;
  5. mem_root->block_size= block_size - ALLOC_ROOT_MIN_BLOCK_SIZE;
  6. mem_root->error_handler= 0;
  7. mem_root->block_num= 4; /* We shift this with >>2 */
  8. mem_root->first_block_usage= 0;
  9. }

初始化過程中,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)。

下面來看看具體分配內存的步驟:
  1. void *alloc_root(MEM_ROOT *mem_root, size_t length)
  2. {
  3. size_t get_size, block_size;
  4. uchar* point;
  5. reg1 USED_MEM *next= 0;
  6. reg2 USED_MEM **prev;

  7. length= ALIGN_SIZE(length);
  8. if ((*(prev= &mem_root->free)) != NULL)
  9. {
  10. if ((*prev)->left < length &&
  11. mem_root->first_block_usage++ >= ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP &&
  12. (*prev)->left < ALLOC_MAX_BLOCK_TO_DROP)
  13. {
  14. next= *prev;
  15. *prev= next->next; /* Remove block from list */
  16. next->next= mem_root->used;
  17. mem_root->used= next;
  18. mem_root->first_block_usage= 0;
  19. }
  20. for (next= *prev ; next && next->left < length ; next= next->next)
  21. prev= &next->next;
  22. }
  23. if (! next)
  24. { /* Time to alloc new block */
  25. block_size= mem_root->block_size * (mem_root->block_num >> 2);
  26. get_size= length+ALIGN_SIZE(sizeof(USED_MEM));
  27. get_size= MY_MAX(get_size, block_size);

  28. if (!(next = (USED_MEM*) my_malloc(get_size,MYF(MY_WME | ME_FATALERROR))))
  29. {
  30. if (mem_root->error_handler)
  31. (*mem_root->error_handler)();
  32. DBUG_RETURN((void*) 0); /* purecov: inspected */
  33. }
  34. mem_root->block_num++;
  35. next->next= *prev;
  36. next->size= get_size;
  37. 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),這裡重復了。
  38. *prev=next;
  39. }

  40. point= (uchar*) ((char*) next+ (next->size-next->left));
  41. /*TODO: next part may be unneded due to mem_root->first_block_usage counter*/
  42. if ((next->left-= length) < mem_root->min_malloc)
  43. { /* Full block */
  44. *prev= next->next; /* Remove block from list */
  45. next->next= mem_root->used;
  46. mem_root->used= next;
  47. mem_root->first_block_usage= 0;
  48. }
  49. }

上述代碼的具體邏輯如下: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鏈表上。
這裡需要注意的是二級指針的使用:
  1. for (next= *prev ; next && next->left < length ; next= next->next)
  2. prev= &next->next;
  3. }
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).

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved