标题: 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://www.51hei.com/bbs/)

Powered by Discuz! X3.1