久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標題: Glib中slab內存管理算法實現 [打印本頁]

作者: liuda 時間: 2015-1-23 19:24
標題: Glib中slab內存管理算法實現
摘要：在嵌入式系統中，內存碎片是一個很棘手的問題。slab內存管理算法具有分配和釋放內存速度迅速、內外部碎片非常小等優點。本文通過分析glib中slab內存管理算法，闡明了其管理內存的實現機制。
關鍵詞：glib slab 內存碎片

一個不斷產生內存碎片的嵌入式系統，不管內存多大，總會有用完的一刻，這種現象在高性能的嵌入式系統中，這簡直是致命的問題。碎片的內存描述一個系統中所有不可用的空閑內存。這些資源之所以仍然未被使用，是因為負責分配內存的分配器使這些內存無法使用。這一問題通常都會發生，產生的原因有很多，具體到代碼主要表現在使用malloc()動態分配內存函數，以及數據結構沒有字對齊造成的。因此內存分配器在保證空閑資源可用性方面扮演著重要的角色。
Glib所使用的slab分配器的基礎是 Jeff Bonwick 為 SunOS 操作系統首次引入的一種算法。Jeff 的分配器是圍繞對象緩存進行的。在內核中，會為有限的對象集（例如文件描述符和其他常見結構）分配大量內存。Jeff 發現對內核中普通對象進行初始化所需的時間超過了對其進行分配和釋放所需的時間。因此他的結論是不應該將內存釋放回一個全局的內存池，而是將內存保持為針對特定目而初始化的狀態。例如，如果內存被分配給了一個互斥鎖，那么只需在為互斥鎖首次分配內存時執行一次互斥鎖初始化函數（mutex_init）即可。后續的內存分配不需要執行這個初始化函數，因為從上次釋放和調用析構之后，它已經處于所需的狀態中了。
Glib中的slab分配器使用了這種思想和其它思想來實現對內存的分配和管理。
Glib源碼中實現slab算法代碼主要體現在gslice.c中。本文以glib-2.18.4中的glice.c為研究對象，Gslic.c中實現了三種內存分配機制：slab，magazine以及純粹的malloc。本文中主要講解slab的實現工程。
Slab分配器allocator總體結構：

圖一 allocator總體結構Slab基本思想：利用內核對內存是以頁為單位進行管理的思想，slab對頁劃分成（n-1）*8 Byte的chunks，也就是說一個slab控制一個頁，所以圖一中的Slab_info總共大小為一頁【這一點很重要】，這樣軟件可以從宏觀的角度控制內存的分配；如果要分配大小為Length字節的內存，只需要把與Length相近的chunk分配給它即可。
接下來通過代碼具體分析下slab的實現過程：
1. 首先了解幾個宏定義。
#define LARGEALIGNMENT (256)
#define P2ALIGNMENT  (2 * sizeof (gsize)) /* fits 2 pointers (assumed to be 2 * GLIB_SIZEOF_SIZE_T below) */chunk采用8字節對齊
#define ALIGN(size, base)  ((base) * (gsize) (((size) + (base) - 1) / (base)))
#define NATIVE_MALLOC_PADDING P2ALIGNMENT/* per-page padding left for native malloc(3) see [1] */
#define SLAB_INFO_SIZE  P2ALIGN(sizeof (SlabInfo) + NATIVE_MALLOC_PADDING)
…//省略
#define MAX_SLAB_CHUNK_SIZE(al) (((al)->max_page_size - SLAB_INFO_SIZE) / 8)/* we want at last 8 chunks per page, see [4] */每一頁至少要包含8個chunk
#define MAX_SLAB_INDEX(al) (SLAB_INDEX (al, MAX_SLAB_CHUNK_SIZE (al)) + 1)//slab的最大個數
#define SLAB_INDEX(al, asize) ((asize) / P2ALIGNMENT - 1)                   /* asize must be P2ALIGNMENT aligned */根據asize的大小查找對應slab的索引
#define SLAB_CHUNK_SIZE(al, ix) (((ix) + 1) * P2ALIGNMENT)//slab[ix]中chunk的大小
#define SLAB_BPAGE_SIZE(al,csz) (8 * (csz) + SLAB_INFO_SIZE)
2. slab所涉及的幾個結構體：
/* --- structures --- */
typedef struct _ChunkLink    ChunkLink;
typedef struct _SlabInfo    SlabInfo;
typedef struct _CachedMagazine CachedMagazine;
struct _ChunkLink {
  ChunkLink *next;
  ChunkLink *data;
};
struct _SlabInfo {
  ChunkLink *chunks;
  guint n_allocated;//記錄有當前slab結構中多少chunk被使用
  SlabInfo *next, *prev;
};
…//省略
typedef struct {
  gboolean always_malloc;
  gboolean bypass_magazines;
  gboolean debug_blocks;
  gsize working_set_msecs;
  guint color_increment;
} SliceConfig;
typedef struct {
  /* const after initialization */
  gsize       min_page_size, max_page_size;
  SliceConfig config;
  gsize       max_slab_chunk_size_for_magazine_cache;
  /* magazine cache */
  GMutex    *magazine_mutex;
  ChunkLink **magazines; /* array of MAX_SLAB_INDEX (allocator) */
  guint       *contention_counters; /* array of MAX_SLAB_INDEX (allocator) */
  gint       mutex_counter;
  guint       stamp_counter;
  guint       last_stamp;
  /* slab allocator */
  GMutex    *slab_mutex;
  SlabInfo **slab_stack; /* array of MAX_SLAB_INDEX (allocator) */SlabInfo最大數組數為MAX_SLAB_INDEX (allocator)
  guint       color_accu;
} Allocator;
…//省略
static gsize    sys_page_size = 0; //這個變量如果是0說明allocator還未被初始化，如果是大于0的數說明allocator已被初始化，并且它的值就是系統頁面值的大小
static Allocator allocator[1] = { { 0, }, }; // 內存分配器
static SliceConfig slice_config = {
  FALSE,       /* always_malloc */
  FALSE,       /* bypass_magazines */ 把這個值設為TRUE,才真正使用slab
  FALSE,       /* debug_blocks */
  15 * 1000,    /* working_set_msecs */
  1,          /* color increment, alt: 0x7fffffff */
};//在變量slice_config中配置選取用那種分配機制，由以下值可知默認情況是使用magazine分配機制
以上各結構體之間的關系可以用圖一表示。圖一中可以看出allocator中成員slab_stack指向一個SlabInfo類型的數組，數組成員指向一個雙向循環鏈表，鏈表中每個成員所包含的chunk的大小都是一樣的，我們通過g_slice_alloc獲取的空間就是從chunk中拿來的。

3. API函數
現在來創建slab、向allocator增加內存頁、回收內存頁的應用程序接口【API接口】以及slab對對象的進行分配和銷毀的操作
3.1創建并初始化slab分配器allocator:
static inline guint
allocator_categorize (gsize aligned_chunk_size)
{
  /* speed up the likely path */
  if (G_LIKELY (aligned_chunk_size && aligned_chunk_size <= allocator->max_slab_chunk_size_for_magazine_cache))
return 1;          /* use magazine cache */會發現宏G_LIKELY其實是利用了__builtin_expect的屬性，具體作用可以看我先前寫的

  /* the above will fail (max_slab_chunk_size_for_magazine_cache == 0) if the
* allocator is still uninitialized, or if we are not configured to use the
* magazine cache.
*/
  if (!sys_page_size)
g_slice_init_nomessage ();//先是通過slice_config_init初始化slice_config，而后初始化allocator
  if (!allocator->config.always_malloc &&
   aligned_chunk_size &&
   aligned_chunk_size <= MAX_SLAB_CHUNK_SIZE (allocator))//注意這三個條件
{
   if (allocator->config.bypass_magazines)
      return 2;    /* use slab allocator, see [2] */使用slab分配內存
   return 1;       /* use magazine cache */
}
  return 0;          /* use malloc() */
}
從以上的代碼可知，這一過程極其的簡單！它主要做了三樣事情：一是獲得系統頁面大小sys_page_size；二是初始化config，以此決定了allocator分配器使用的分配機制；三是建立了SlabInfo指針數組。

3.2 從allocator獲取chunk_size大小內存塊的起始地址
函數 g_slice_alloc是提供給外部的API函數，它擔當起初始化并返回所需內存空間的大小的其實地址
gpointer
g_slice_alloc (gsize mem_size)
{
  gsize chunk_size;
  gpointer mem;
  guint acat;
  chunk_size = P2ALIGN (mem_size);//對mem_size進行8自己對齊
  acat = allocator_categorize (chunk_size); //創建并初始化allocator，上面有講解
  if (G_LIKELY (acat == 1))    /* allocate through magazine layer */
{
   ThreadMemory *tmem = thread_memory_from_self();
   guint ix = SLAB_INDEX (allocator, chunk_size);
   if (G_UNLIKELY (thread_memory_magazine1_is_empty (tmem, ix)))
      {
      thread_memory_swap_magazines (tmem, ix);
      if (G_UNLIKELY (thread_memory_magazine1_is_empty (tmem, ix)))
         thread_memory_magazine1_reload (tmem, ix);
      }
   mem = thread_memory_magazine1_alloc (tmem, ix);
}
  else if (acat == 2)          /* allocate through slab allocator */采用slab分配方式
{
   g_mutex_lock (allocator->slab_mutex);
   mem = slab_allocator_alloc_chunk (chunk_size);//slab分配的主要函數
   g_mutex_unlock (allocator->slab_mutex);
}
  else                         /* delegate to system malloc */
mem = g_malloc (mem_size);
  if (G_UNLIKELY (allocator->config.debug_blocks))
smc_notify_alloc (mem, mem_size);
  return mem;
}

到了這，我們都知道SlabInfo指針數組已經創建好，但是這個SlabInfo指針數組有一個特性在這里要先提一下，它能方便大家更快的了解slab。前面已經提到SlabInfo指針數組每個元素都是指向一個雙向鏈表，雙向鏈表中每個chunk的大小都以相同的。那么這個大小該如何獲知呢，這正是slab的精華所在，雙向鏈表所在數組的下標跟該雙向鏈表中的chunk的大小是一一對應關系，比如下標為n-1；那么chunk的大小為(n-1)* P2ALIGNMENT，而P2ALIGNMENT為兩個pointer的大小，即8。既然如此，已知要分配的chunk_size的大小，可以通過(n-1)* P2ALIGNMENT算出n的值，即下標。
static gpointer
slab_allocator_alloc_chunk (gsize chunk_size)
{
  ChunkLink *chunk;
  guint ix = SLAB_INDEX (allocator, chunk_size);//計算下標
  /* ensure non-empty slab */
  if (!allocator->slab_stack[ix] || !allocator->slab_stack[ix]->chunks)//判斷是否存在下標為ix的slab雙向鏈表或者當前鏈表所指向的slab是否分配完
allocator_add_slab (allocator, ix, chunk_size); //創建slab雙鏈表或添加slab
   /* allocate chunk */
  chunk = allocator->slab_stack[ix]->chunks;//獲取空chunk的起始地址
  allocator->slab_stack[ix]->chunks = chunk->next;
  allocator->slab_stack[ix]->n_allocated++;
  /* rotate empty slabs */
  if (!allocator->slab_stack[ix]->chunks)
allocator->slab_stack[ix] = allocator->slab_stack[ix]->next;
  return chunk;
}

static void
allocator_add_slab (Allocator *allocator,
                  guint    ix,
                  gsize    chunk_size)
{
  ChunkLink *chunk;
  SlabInfo *sinfo;
  gsize addr, padding, n_chunks, color = 0;
  gsize page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));//通過chunk_size計算要分配給slab的頁大小，一般是chunk_size的8倍
/* allocate 1 page for the chunks and the slab */
  gpointer aligned_memory = allocator_memalign (page_size, page_size - NATIVE_MALLOC_PADDING);//分配一頁的大小給slab
  guint8 *mem = aligned_memory;
  guint i;
  if (!mem)
{
   const gchar *syserr = "unknown error";
#if HAVE_STRERROR
   syserr = strerror (errno);
#endif
   mem_error ("failed to allocate %u bytes (alignment: %u): %s\n",
               (guint) (page_size - NATIVE_MALLOC_PADDING), (guint) page_size, syserr);
}
  /* mask page adress */
  addr = ((gsize) mem / page_size) * page_size;
  /* assert alignment */
  mem_assert (aligned_memory == (gpointer) addr); //與上一句一起判斷地址是否頁對齊
  /* basic slab info setup */
  sinfo = (SlabInfo*) (mem + page_size - SLAB_INFO_SIZE);
  sinfo->n_allocated = 0;
  sinfo->chunks = NULL;
  /* figure cache colorization */
  n_chunks = ((guint8*) sinfo - mem) / chunk_size;
  padding = ((guint8*) sinfo - mem) - n_chunks * chunk_size;
  if (padding)
{
   color = (allocator->color_accu * P2ALIGNMENT) % padding;
   allocator->color_accu += allocator->config.color_increment;
}
  /* add chunks to free list */
  chunk = (ChunkLink*) (mem + color);
  sinfo->chunks = chunk;
  for (i = 0; i < n_chunks - 1; i++)
{
   chunk->next = (ChunkLink*) ((guint8*) chunk + chunk_size);
   chunk = chunk->next;
}
  chunk->next = NULL; /* last chunk */
  /* add slab to slab ring */
  allocator_slab_stack_push (allocator, ix, sinfo);//這個函數要注意咯，它的作用是把分配好的slab插入雙鏈表頭部；有兩種情況，一種是沒有slab雙鏈表，一種是slab雙鏈表已經沒有chunk可以分配。反正都需要新增一個slab插入雙鏈表的頭部
}

該函數對slab的創建和初始化過程可以用下圖二表示：

圖二 slab結構圖
至此，已經完成對allocator的創建，初始化，以及所需內存塊大小為chunk_size起始地址的獲取的代碼分析。
3.2 從allocator回收chunk_size大小內存塊
它的核心部分主要體現在函數slab_allocator_free_chunk，該函數的思路不是按照我們平時處理單鏈表的思路去回收其中的節點，本科階段在上數據結構時，我們對單鏈表的不管怎么處理，它最后始終是一個單鏈表，可是在這里就不同了，當你回收一個chunk節點時，只要sinfo->n_allocated這個值仍不為0，那么經過回收操作后的chunk鏈表就不一定是單鏈表。
static void
slab_allocator_free_chunk (gsize chunk_size,
                        gpointer mem)
{
  ChunkLink *chunk;
  gboolean was_empty;
  guint ix = SLAB_INDEX (allocator, chunk_size);//計算下標
  gsize page_size = allocator_aligned_page_size (allocator, SLAB_BPAGE_SIZE (allocator, chunk_size));
  gsize addr = ((gsize) mem / page_size) * page_size;
  /* mask page adress */
  guint8 *page = (guint8*) addr;
  SlabInfo *sinfo = (SlabInfo*) (page + page_size - SLAB_INFO_SIZE);
  /* assert valid chunk count */
  mem_assert (sinfo->n_allocated > 0);
  /* add chunk to free list */
  was_empty = sinfo->chunks == NULL;
  chunk = (ChunkLink*) mem;
  chunk->next = sinfo->chunks;
  sinfo->chunks = chunk;//這三行語句把要回收的chunk插入空chunk的頭部，正因為如此，原來是單鏈表的chunk鏈表因為這樣變得不是一個單鏈表，但是它不影響用戶繼續申請chunk和回收chunk。看到這我不得不佩服作者的思維
  sinfo->n_allocated--;
  /* keep slab ring partially sorted, empty slabs at end */
  if (was_empty)
{
   /* unlink slab */
   SlabInfo *next = sinfo->next, *prev = sinfo->prev;
   next->prev = prev;
   prev->next = next;
   if (allocator->slab_stack[ix] == sinfo)
      allocator->slab_stack[ix] = next == sinfo ? NULL : next;
   /* insert slab at head */
   allocator_slab_stack_push (allocator, ix, sinfo);
}
  /* eagerly free complete unused slabs */
  if (!sinfo->n_allocated)// 該slab中才chunk全部回收完，就要把該slab的頁空間釋放掉
{
   /* unlink slab */
   SlabInfo *next = sinfo->next, *prev = sinfo->prev;
   next->prev = prev;
   prev->next = next;
   if (allocator->slab_stack[ix] == sinfo)
      allocator->slab_stack[ix] = next == sinfo ? NULL : next;
   /* free slab */
   allocator_memfree (page_size, page);
}
}
至此，已經完成對回收chunk的代碼分析。
4. 結束語
Slab內存管理算法不僅僅在glib中使用，在linux內核中也有它的身影，如果想更好的了解slab，建議從源碼開始。

歡迎光臨 (http://m.zg4o1577.cn/bbs/)