歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux基礎 >> 關於Linux

slab內存管理源代碼分析

學習計算機原理,最好是實踐或看高手寫的源代碼,在一定程度上就不再會感到原理的抽象。關於slab一些原理資料,可以在這裡下載或到網站有更多的信息和資料。Slab內存管理機制已被廣泛使用,要找到使用slab管理內存的開源代碼也不難,如一些OS內核中的內存管理。既然要分析理解slab,最好還是選擇復雜度和代碼量都不要太大的,在這裡我選取了glib-2.12.9的gslice.c實現的slab機制相關代碼作為分析對象。注意Glib庫是針對用戶級的而非OS內核級別的。

gslice.c中實現了三種內存分配機制:一是slab;二是比slab更適合於多CPU/多線程的magazine;三是只使用純粹的malloc。本文章只針對slab相關的源代碼進行分析。

在分析代碼時主要從以下幾個方面入手:先從分配器總體數據結構的關系進行描述;二是看分配器allocator是如何初始化的;接下來是分析分配器如何分配和回收內存(chunk)。

Allocator分配器總體結構:

下面先來看一些重要的數據結構和變量:

  …………. //點代表省略的代碼
  130 typedef struct _ChunkLink   ChunkLink;
  131 typedef struct _SlabInfo    SlabInfo;
  132 typedef struct _CachedMagazine CachedMagazine;
  // 這個結構也表明了一個Chunk的最小值是兩個指針大小
  133 struct _ChunkLink {
  134  ChunkLink *next;
  135  ChunkLink *data; //這字段在slab中未被使用
  136 };
  137 struct _SlabInfo {
  138  ChunkLink *chunks;
  139  guint n_allocated;
  140  SlabInfo *next, *prev;
  141 };
  ………….
  150 typedef struct {
  151  gboolean always_malloc; // 為TRUE表示使用純粹的malloc
  152  gboolean bypass_magazines; // 為TRUE表示使用slab
  153  gsize  working_set_msecs;
  154  guint  color_increment;
  155 } SliceConfig;
  156 typedef struct {
  157  /* const after initialization */
  158  gsize     min_page_size, max_page_size;
  159  SliceConfig  config;
  ……………
  168  /* slab allocator */
  169  GMutex    *slab_mutex;
  // SlabInfo指針數組,最大值為MAX_SLAB_INDEX (allocator)
  170  SlabInfo  **slab_stack; /* array of MAX_SLAB_INDEX (allocator) */
  171  guint    color_accu;
  172 } Allocator;
  ………….
  // 這個變量如果是0說明allocator還未被初始化,如果是大於0的數說明allocator
  // 已被初始化,並且它的值就是系統頁面值的大小
  189 static gsize    sys_page_size = 0;
  190 static Allocator  allocator[1] = { { 0, }, }; // 內存分配器
   // 在變量slice_config中配置選取用那種分配機制,由以下值可知默認情況
  // 是使用magazine分配機制
  191 static SliceConfig slice_config = {
  192  FALSE,   /* always_malloc */
  193  FALSE,   /* bypass_magazines */ // 把這個值設為TRUE,才真正使用slab
  194  15 * 1000,  /* working_set_msecs */
  195  1,      /* color increment, alt: 0x7fffffff */
  196 };
  ………….

根據以上的數據結構和程序的邏輯實現,可以把它們的關系用如下的圖表示:

Allocator有個SlabInfo指針數組slab_stack成員,stab_stack的每個成員或者是空指針或是一個指向SlabInfo雙向循環鏈表。雙向循環鏈表中的每個成員有個指針指向chunk鏈表的表頭。而chunk鏈表中的每個成員就是調用接口g_slice_alloc時被分配的空間。

當調用接口g_slice_alloc申請空間時,根據申請的空間大小通過宏SLAB_INDEX找到對應指針數組slab_stack的正確下標,找到對應的slab_stack數組下標就要以找到相應的SlabInfo雙向循環鏈表,也就可以找到Chunk鏈表並從Chunk鏈表取出一個節點作為被申請的空間返回。即實際分配內存要先找到SlabInfo雙向循環鏈表,然後再通過它分配內存。

要注意,在下面的分析中會經常用到上圖中的幾個名詞。這些名詞有SlabInfo指針數組(allocator->slab_stack)、SlabInfo雙向循環鏈表、每個SlabInfo管理的Chunk鏈表。還有在下面分析時會把allocator->slab_stack[ix]叫當前的SlabInfo。

allocator分配器初始化:

初始化的調用關系是:g_slice_alloc--->allocator_categorize--->g_slice_init_nomessage---> slice_config_init。

  // 以下相關代碼是初始化190行定義的allocator變量
  751 g_slice_alloc (gsize mem_size)
  752 {
  ……………// 點代表省略的代碼
  755  guint acat;
  ……………
  757  acat = allocator_categorize (chunk_size);
  ……………
  779 }
  // 這個函數的作用是獲取allocator分配器的分配機制。
  // 返回值:0表示使用純粹的malloc;1表示使用magazine;2表示使用slab
  335 static inline guint
  336 allocator_categorize (gsize aligned_chunk_size)
  337 {
  ……………
  346  if (!sys_page_size)
  347   g_slice_init_nomessage ();
  ……………
  357 }
  281 g_slice_init_nomessage (void)
  282 {
  ……………
  // 獲取系統頁面大小,並把值賦給sys_page_size變量
  287 #ifdef G_OS_WIN32
  288  {
  289   SYSTEM_INFO system_info;
  290   GetSystemInfo (&system_info);
  291   sys_page_size = system_info.dwPageSize;
  292  }
  293 #else
  294  sys_page_size = sysconf (_SC_PAGESIZE); /* = sysconf (_SC_PAGE_SIZE); = getpagesize(); */
  295 #endif
  ……………
  298  slice_config_init (&allocator->config);
  299  allocator->min_page_size = sys_page_size;
  ……………
  // 建立SlabInfo指針數組(allocator->slab_stack),
  // 數組裡每個指針值都初始化成NULL值
  323  allocator->slab_stack = g_new0 (SlabInfo*, MAX_SLAB_INDEX (allocator));
  ……………
  <!--[if !supportLists]-->333    }<!--[endif]-->
  264 slice_config_init (SliceConfig *config)

  265 {
  ……………
  // 通過使用191行代碼(代碼在總攬中已給出)定義的slice_config初始化
  // allocator中的config,以此決定了使用哪種分配機制。
  273  *config = slice_config;
  ……………
  278 }

從以上的代碼可知,如果只看初始化相關的代碼,這一過程極其的簡單!它主要做了三樣事情:一是獲得系統頁面大小sys_page_size;二是初始化config,以此決定了allocator分配器使用的分配機制;三是建立了SlabInfo指針數組。

allocator分配器分配內存chunk:

在分析主要代碼之前有必要先了解操作chunk_size字節對齊和求SlabInfo指針數組(allocator->slab_stack)下標的幾個宏定義。

chunk_size的字節對齊是通過宏P2ALIGN來實現,P2ALIGN是以P2ALIGNMENT字節對齊的。

  // gsize和下文的GLIB_SIZEOF_SIZE_T是同等意義的,它等於一個指針的字節數。可見
  // P2ALIGNMENT為兩個指針字節數,也即在總攬給出的代碼133行中聲明的Chunk的最
  //小字節數。我們一般假設在32位機器中,一個指針的字節數為4,
  // 那麼P2ALIGNMENT的值為8。
  // 在下面的分析中,如果有假設數據字節數,就認為P2ALIGNMENT的值為8
  103 #define P2ALIGNMENT  (2 * sizeof (gsize)) /* fits 2 pointers (assumed to be 2 * GLIB_SIZEOF_SIZE_T below) */
  // ALIGN功能是求size以base字節對齊的數據。這是一種常用的方法,如果看不明白
  // 可以假設一些真實的數據進去運算,當然假設數據時base值最好是2的n次方。
  104 #define ALIGN(size, base)  ((base) * (gsize) (((size) + (base) - 1) / (base)))
  // 下面的P2ALIGN也是以一定的字節數對齊的操作,它用的了一些二進制的技巧
  // 可以參考本人寫的另外一篇文章講二進制技巧那部分或有關這方面知識的其它資料。
  116 /* optimized version of ALIGN (size, P2ALIGNMENT) */
  117 #if   GLIB_SIZEOF_SIZE_T * 2 == 8 /* P2ALIGNMENT */
  118 #define P2ALIGN(size)  (((size) + 0x7) & ~(gsize) 0x7) // 以8字節對齊
  119 #elif  GLIB_SIZEOF_SIZE_T * 2 == 16 /* P2ALIGNMENT */
  120 #define P2ALIGN(size)  (((size) + 0xf) & ~(gsize) 0xf) // 以16字節對齊
  121 #else
  122 #define P2ALIGN(size)  ALIGN (size, P2ALIGNMENT)
  123 #endif

求SlabInfo指針數組(allocator->slab_stack)下標的宏是代碼112行的SLAB_INDEX(al, asize),從代碼981行可知宏SLAB_INDEX裡的asize就是chunk_size。代碼981行的chunk_size是從代碼756行調用P2ALIGN獲得的,可見傳給宏SLAB_INDEX的asize已是P2ALIGNMENT字節對齊的了。下圖更直接明了地說明了chunk_size和SlabInfo指針數組(allocator->slab_stack)下標的關系。可見SlabInfo指針數組(allocator->slab_stack)下標從小到大的成員所指向的SlabInfo雙向循環鏈表(此鏈表見總攬圖)的chunk_size是從小到大的P2ALIGNMENT整數倍數。

  // 通過asize求SlabInfo指針數組(allocator->slab_stack)的下標,
  // asize以P2ALIGNMENT字節對齊
  112 #define SLAB_INDEX(al, asize) ((asize) / P2ALIGNMENT - 1)           /* asize must be P2ALIGNMENT aligned */
  750 gpointer
  751 g_slice_alloc (gsize mem_size)
  752 {
  753  gsize chunk_size;
  754  gpointer mem;
  755  guint acat;
  // 對要分配的內存大小通過宏P2ALIGN變為以P2ALIGNMENT字節對齊的大小
  // 並把它賦給chunk_size
  756  chunk_size = P2ALIGN (mem_size);
  ……………
  772    g_mutex_lock (allocator->slab_mutex);
  773    mem = slab_allocator_alloc_chunk (chunk_size);
  774    g_mutex_unlock (allocator->slab_mutex);
  ……………
  778  return mem;
  779 }
  977 static gpointer
  978 slab_allocator_alloc_chunk (gsize chunk_size)
  979 {
  980  ChunkLink *chunk;
   // 求SlabInfo指針數組(allocator->slab_stack)下標,
  // 也即找到chunk_size對應的SlabInfo雙向循環鏈表
  981  guint ix = SLAB_INDEX (allocator, chunk_size);
  982  /* ensure non-empty slab */
   // 判斷chunk_size對應的SlabInfo雙向循環鏈表的循環是否還未建立或是
  // 當前的SlabInfo中的chunk是否已被分配完。
  // 如果兩者的任何一個成立,那麼就重新建立一個新的SlabInfo,並把
  // 當前SlabInfo指針allocator->slab_stack[ix]指向新建的SlabInfo,新建
  // 的SlabInfo包含了新分配的chunk鏈表,這功能在allocator_add_slab函數完成。
  983  if (!allocator->slab_stack[ix] || !allocator->slab_stack[ix]->chunks)
  984   allocator_add_slab (allocator, ix, chunk_size);
  985  /* allocate chunk */
  986  chunk = allocator->slab_stack[ix]->chunks;
   // 讓被分配的chunk脫離chunk鏈表
  987  allocator->slab_stack[ix]->chunks = chunk->next;
  988  allocator->slab_stack[ix]->n_allocated++;
  989  /* rotate empty slabs */
  // 如果當前的SlabInfo的chunk已分配完,就讓當前的SlabInfo指針指
  // 向下一個SlabInfo。
  990  if (!allocator->slab_stack[ix]->chunks)
  991   allocator->slab_stack[ix] = allocator->slab_stack[ix]->next;
  992  return chunk;
  993 }
  // 這函數的代碼分析也可以直接看下面圖A解釋或是兩者結合起來理解。
  926 static void
  927 allocator_add_slab (Allocator *allocator,
  928           guint   ix,
  929           gsize   chunk_size)
  930 {
  931  ChunkLink *chunk;
  932  SlabInfo *sinfo;
  933  gsize addr, padding, n_chunks, color = 0;
  934 gsize page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));
  935  /* allocate 1 page for the chunks and the slab */
   /* 分配一頁內存給slab和chunk鏈表 */
  936  gpointer aligned_memory = allocator_memalign (page_size, page_size - NATIVE_MALLOC_PADDING);
  937  guint8 *mem = aligned_memory;
  938  guint i;
  ……………
  952  /* basic slab info setup */
   // 把SlabInfo結構信息放在剛分配的一頁內存的高地址處
  953  sinfo = (SlabInfo*) (mem + page_size - SLAB_INFO_SIZE);
  954  sinfo->n_allocated = 0;
  955  sinfo->chunks = NULL;
  956  /* figure cache colorization */
   // 計算這一頁內存能夠劃分成多少(n_chunks)個chunk。
  957  n_chunks = ((guint8*) sinfo - mem) / chunk_size;
   // 再判斷是否還有剩余的空間padding,如果有另作他用。
  958  padding = ((guint8*) sinfo - mem) - n_chunks * chunk_size;
  959  if (padding)
  960   {
  961    color = (allocator->color_accu * P2ALIGNMENT) % padding;
  962    allocator->color_accu += allocator->config.color_increment;
  963   }
  964  /* add chunks to free list */
  // 找出chunk鏈表的表頭
  965  chunk = (ChunkLink*) (mem + color);
  966  sinfo->chunks = chunk;
   // 循環構建chunk鏈表:把地址相鄰的chunk鏈接起來
  967  for (i = 0; i < n_chunks - 1; i++)
  968   {
   // 當前chunk指向下一個chunk,
   // (chunk + chunk_size)是下一個chunk的起始地址。
  969    chunk->next = (ChunkLink*) ((guint8*) chunk + chunk_size);
  970    chunk = chunk->next;
  971   }
   // 最後一個chunk指向NULL
  972  chunk->next = NULL;  /* last chunk */
  973  /* add slab to slab ring */
  974  allocator_slab_stack_push (allocator, ix, sinfo);
  975 }
  // 函數功能是根據SlabInfo指針數組(allocator->slab_stack)下標ix
  // 把新建的SlabInfo鏈入對應的SlabInfo雙向循環鏈表,並把當前SlabInfo指針
  // allocator->slab_stack[ix]指向新建的SlabInfo。
  896 allocator_slab_stack_push (Allocator *allocator,
  897               guint   ix,
  898               SlabInfo *sinfo)
  899 {
  900  /* insert slab at slab ring head */
  901  if (!allocator->slab_stack[ix])
  902   {
  903    sinfo->next = sinfo;
  904    sinfo->prev = sinfo;
  905   }
  906  else
  907   {
  908    SlabInfo *next = allocator->slab_stack[ix], *prev = next->prev;
  909    next->prev = sinfo;
  910    prev->next = sinfo;
  911    sinfo->next = next;
  912    sinfo->prev = prev;
  913   }
  914  allocator->slab_stack[ix] = sinfo;
  915 }

對於以上的代碼,重點對allocator_add_slab函數進行更為詳細的分析,它的功能主要是申請一頁內存,用這一內存新建立一個SlabInfo,並把它鏈入對應的SlabInfo雙向循環鏈表。對於新建立的SlabInfo,幾乎所有跟它相關的內部信息都在申請的那頁內存上:

現在結合上圖展開說明。代碼936、937行申請一頁內存,並把起始地址給mem變量。代碼953行把頁面的高地址分給了SlabInfo結構。如果有padding的話,代碼958到963是把padding另作它用。而上圖color的大小和空白的大小相加就是padding的值了,這點細節也可以不用太多關注它。chunk鏈表的起始地址,即鏈表表頭在代碼的965行確定的,而上圖SlabInfo有個指向chunk鏈表頭的指針是在代碼966行實現的。圖中chunk鏈表的建立是在代碼967到972實現的。

allocator分配器回收內存chunk:

分配器對內存的分配和回收就很簡單了,通過函數g_slice_free1調用了函數slab_allocator_free_chunk,下面僅對slab_allocator_free_chunk函數分析:

  // 參數中的mem就是要釋放回收的內存chunk
  996 slab_allocator_free_chunk (gsize  chunk_size,
  997               gpointer mem)
  998 {
  999  ChunkLink *chunk;
  1000  gboolean was_empty;
  1001  guint ix = SLAB_INDEX (allocator, chunk_size);
  1002  gsize page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));
  // 這是求mem所在的頁面的起始地址。因地址在程序邏輯中是扁平線性的,
  // 所以(mem / page_size)就是mem所屬的是第幾個頁面,那麼它乘上page_size就是
  // mem所在的頁面的起始地址。
  1003  gsize addr = ((gsize) mem / page_size) * page_size;
  1004  /* mask page adress */
  1005  guint8 *page = (guint8*) addr;
  // 獲取管理mem的SlabInfo的指針。在上面已提到過SlabInfo是放在一個頁面
  // 的高地址處。
  1006  SlabInfo *sinfo = (SlabInfo*) (page + page_size - SLAB_INFO_SIZE);
  1007  /* assert valid chunk count */
  1008  mem_assert (sinfo->n_allocated > 0);
  1009  /* add chunk to free list */
  1010  was_empty = sinfo->chunks == NULL;
  1011  chunk = (ChunkLink*) mem;
  // 把要回收的chunk鏈入SlabInfo管理的chunk鏈表的表頭
  1012  chunk->next = sinfo->chunks;
  1013  sinfo->chunks = chunk;
  1014  sinfo->n_allocated--;
  1015  /* keep slab ring partially sorted, empty slabs at end */
  // was_empty為TRUE,表明管理要回收的chunk的SlabInfo所在的SlabInfo雙向循環鏈表
  // 中的每一個SlabInfo都可能已把它自己的chunk分配完,即它們都沒有空間可分配了。
  // 那麼就應該把當前的SlabInfo改為這次回收了內存chunk的SlabInfo,以備下次分配用。
  1016  if (was_empty)
  1017   {
  1018    /* unlink slab */
  1019    SlabInfo *next = sinfo->next, *prev = sinfo->prev;
  1020    next->prev = prev;
  1021    prev->next = next;
  1022    if (allocator->slab_stack[ix] == sinfo)
  1023     allocator->slab_stack[ix] = next == sinfo ? NULL : next;
  1024    /* insert slab at head */
  // 重新把SlabInfo鏈入SlabInfo雙向循環鏈表,為的是把當
  // 前SlabInfo(allocator->slab_stack[ix])改為這次回收了內存chunk的SlabInfo
  1025    allocator_slab_stack_push (allocator, ix, sinfo);
  1026   }
  1027  /* eagerly free complete unused slabs */
  1028  if (!sinfo->n_allocated)
  1029   {
  1030    /* unlink slab */
  1031    SlabInfo *next = sinfo->next, *prev = sinfo->prev;
  1032    next->prev = prev;
  1033    prev->next = next;
  1034    if (allocator->slab_stack[ix] == sinfo)
  1035     allocator->slab_stack[ix] = next == sinfo ? NULL : next;
  1036    /* free slab */
   // allocator_memfree函數功能是系統回收內存空間
  1037    allocator_memfree (page_size, page);
  1038   }
  1039 }

到此已把slab相關的代碼已分析完,比slab更適合於多CPU/多線程的magazine內存管理機制比slab更復雜但也更有用更有意思,我將在下一篇給出。

從以上的代碼可知,如果只看初始化相關的代碼,這一過程極其的簡單!它主要做了三樣事情:一是獲得系統頁面大小sys_page_size;二是初始化config,以此決定了allocator分配器使用的分配機制;三是建立了SlabInfo指針數組。

Copyright © Linux教程網 All Rights Reserved