Glib内存管理模块之magazine layer

1. 简介：

Glib中使用了slab进行内存管理(代码解释见[1]，cache coloring见[2])，同时引入了magazine cache来进行多级缓存。本文主要介绍magazine cache部分实现，不讨论slab和使用malloc的实现代码。

2. 层级关系：

采用了magazine layer后的glib内存管理，在整体上一共分为四个层级：

1. 线程缓存magazine层，这一层为线程专属，每个线程维护自己的两个空闲链表，内存申请和释放首先与这一级的缓存进行交付。

2. 全局缓存magazine层，这一层为全局的缓存，当某个线程缓存空了需要申请内存，会先向全局缓存进行申请，当某个线程的空闲链表都满了，会将其中一级缓存释放回全局缓存层。

3. slab层。

4. 系统层。

3. 数据结构：

magazine本身数据结构上看起来并不复杂，但是其在实际使用时引入了一些复杂的操作。

// 这里的chunk不一定是以普通单链表存在，也可能在data中存在一条子链
// 当magazine归还到全局缓存时，data还会用于元数据的存储和管理
struct _ChunkLink {
  ChunkLink *next;
  ChunkLink *data;
};
// 用于空闲列表的管理，chunks里面记录的都是空闲chunk。
typedef struct {
  ChunkLink *chunks;
  gsize      count;                     /* approximative chunks list length */
} Magazine;
// 线程缓存，一共设有二级缓存，优先从一级缓存分配，归还到二级缓存。
// 其实是两个数组，在内存排布上ThreadMemory紧跟着就是两个大小的数组。
//  ThreadMemory {
//    Maganize cache 1 [n_magazines]; --------------|
//    Maganize cache 2 [n_magazines]; --------|     |
//  }                                         |     |
//  Maganize [0]  <---------------------------|-----|
//  ....                                      |
//  Maganize [n_magazines - 1]                |
//  Maganize [n_magazines]  <-----------------|
//  ....
//  Maganize [2 * n_maganizes - 1]
typedef struct {
  Magazine   *magazine1;                /* array of MAX_SLAB_INDEX (allocator) */
  Magazine   *magazine2;                /* array of MAX_SLAB_INDEX (allocator) */
} ThreadMemory;

当一个magazine放到线程缓存中，这个magazine中所有的chunk都有可能随时拆分使用，因此这时候的magazine单纯的是一个chunk链表，但是可能是不规则的链表。如下图：

当这个magazine归还给全局magazine的时候，这时候的magazine都处于空闲状态，因此归还时会调整chunk链表的链接形态，用前四个（因此一个magazine最少有4个chunk）chunk来做元数据管理，分别代表上一个magazine，归还时间戳，下一个magazine，magazine中的chunk数。如下图：chunk 1、2、3、4位置改变，成为普通链表的形态，并用他们的data来保存元数据。

线程缓存的magazine是一个一个放置在一组数组中的，因此不需要维护前后关系，如下图：

而全局magazine缓存则类似一个桶，在对应id下会有若干个magazine串成一组链表，而链表之间的关系则由上面说的元数据来维护。如下图：

4. 简要流程：

4.1 申请：

申请的过程是在四层管理层上逐级获取分配的过程，流程图如下：

4.2 释放：

释放的过程类似，不过略有区别的是对全局缓存的管理是以时间来进行管理。

5. 代码分析：

5.1 基础函数：

5.1.1 线程缓存获取函数：

这个函数是单例实现，第一次获取失败的时候会创建一个的数据。这里使用了g_private_get，类似于thread_local关键字的功能。

static inline ThreadMemory*
thread_memory_from_self (void)
{
  ThreadMemory *tmem = g_private_get (&private_thread_memory);
  // 未初始化
  if (G_UNLIKELY (!tmem))
    {
      static GMutex init_mutex;
      guint n_magazines;

      g_mutex_lock (&init_mutex);
      if G_UNLIKELY (sys_page_size == 0)
        g_slice_init_nomessage ();
      g_mutex_unlock (&init_mutex);

      n_magazines = MAX_SLAB_INDEX (allocator);
      // 初始化，类似于c中的柔性数组
      // struct ThreadMemory {
      //   Magazine *magazine1;
      //   Magazine *magazine2;
      //   magazine m1[0];
      //   magazine m2[0];
      // }
      tmem = g_malloc0 (sizeof (ThreadMemory) + sizeof (Magazine) * 2 * n_magazines);
      tmem->magazine1 = (Magazine*) (tmem + 1);
      tmem->magazine2 = &tmem->magazine1[n_magazines];
      g_private_set (&private_thread_memory, tmem);
    }
  return tmem;
}

5.1.2 magazine中弹出一个有效chunk

这个函数将从magazine中弹出一个可用的chunk，并会根据当前chunk来调整整个magazine中的chunk形状。

static inline ChunkLink*
magazine_chain_pop_head (ChunkLink **magazine_chunks)
{
  /* magazine chains are linked via ChunkLink->next.
   * each ChunkLink->data of the toplevel chain may point to a subchain,
   * linked via ChunkLink->next. ChunkLink->data of the subchains just
   * contains uninitialized junk.
   */
  // 首先获取第一个chunk的data，看是否有子链，优先从子链中选取，如果不是，则选择第一个节点。
  // 场景1: 
  //   1  -->  2  -->  3
  //   |
  //   4
  // 取走第一个节点1后，变成：
  //   4  -->  2  -->  3
  // 场景2：
  //   1  -->  2  -->  3
  //           |
  //           4
  // 取走第一个节点1后，变成:
  //   2  -->  3
  //   |
  //   4
  ChunkLink *chunk = (*magazine_chunks)->data;
  if (G_UNLIKELY (chunk))
    {
      /* allocating from freed list */
      // 取到子链，这时候把该链头节点取走，并将子链上提
      (*magazine_chunks)->data = chunk->next;
    }
  else
    {
      // 子链没有数据，这时候会取走头节点，并将next往前移
      chunk = *magazine_chunks;
      *magazine_chunks = chunk->next;
    }
  return chunk;
}

5.2 申请：

用户调用的接口为g_slice_alloc和g_slice_alloc0，后者增加将内存块置零的操作，类似于calloc。

首先会根据需要分配的大小选择对应的magazine缓存块，再去线程缓存对应块中申请一个chunk。申请时优先从缓存1中申请，如果缓存1空，则会交换缓存1和2，再尝试从当前的缓存1申请，如果都空了，则需要去全局magazine缓存中申请一个magazine。

// 根据大小查找索引
guint ix = SLAB_INDEX (allocator, chunk_size);
// 当1为空，交换12，再空就需要去全局缓存中重新申请一个magazine。
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);
  }
// 从空闲列表中弹出一个chunk。
mem = thread_memory_magazine1_alloc (tmem, ix);

thread_memory_magazine1_reload中我们主要看函数magazine_cache_pop_magazine，这里是向全局缓存申请一个magazine的过程，主要是从全局magazine缓存中取出一个节点，如果全局缓存中也没有对应的magazine缓存，则需要向slab进行申请，slab分配过程这里不讨论。

static ChunkLink*
magazine_cache_pop_magazine (guint  ix,
                             gsize *countp)
{
  g_mutex_lock_a (&allocator->magazine_mutex, &allocator->contention_counters[ix]);
  if (!allocator->magazines[ix])
    {
      // 当前缓存为空，向slab申请一个新的magazine，大小根据配置计算，但是不小于MIN_MAGAZINE_SIZE
	  // MIN_MAGAZINE_SIZE为magazine在缓存时的元数据信息大小，这里为四个链表节点。
	  // 第一个申请时候直接返回给了线程缓存magazine层，因此不用设置元数据。
      guint magazine_threshold = allocator_get_magazine_threshold (allocator, ix);
      gsize i, chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
      ChunkLink *chunk, *head;
      g_mutex_unlock (&allocator->magazine_mutex);
      g_mutex_lock (&allocator->slab_mutex);
      head = slab_allocator_alloc_chunk (chunk_size);
      head->data = NULL;
      chunk = head;
      for (i = 1; i < magazine_threshold; i++)
        {
          chunk->next = slab_allocator_alloc_chunk (chunk_size);
          chunk = chunk->next;
          chunk->data = NULL;
        }
      chunk->next = NULL;
      g_mutex_unlock (&allocator->slab_mutex);
      *countp = i;
      return head;
    }
  else
    {
      // 当前缓存中有内容，会从当前缓存中弹出一个magazine，
      // 需要维护前后两个magazine缓存的链表之间元数据信息，
      // 同时需要清空弹出的magazine的元数据信息。
      ChunkLink *current = allocator->magazines[ix];
      ChunkLink *prev = magazine_chain_prev (current);
      ChunkLink *next = magazine_chain_next (current);
      /* unlink */
      magazine_chain_next (prev) = next;
      magazine_chain_prev (next) = prev;
      allocator->magazines[ix] = next == current ? NULL : next;
      g_mutex_unlock (&allocator->magazine_mutex);
      /* clear special fields and hand out */
      *countp = (gsize) magazine_chain_count (current);
      magazine_chain_prev (current) = NULL;
      magazine_chain_next (current) = NULL;
      magazine_chain_count (current) = NULL;
      magazine_chain_stamp (current) = NULL;
      return current;
    }
}

5.3 释放：

用户调用函数g_slice_free1，注意这里和普通的free函数不同，需要额外带上结构体大小，因为需要这个大小去计算对应的magazine索引。释放过程和申请过程相反。会优先将chunk释放到缓存2中，如果缓存2满了，则交换缓存1和2，再次释放到缓存2中，如果两个缓存都满了，则会将缓存归还给全局缓存。

// 获取当前线程缓存，并根据内存大小计算索引。
ThreadMemory *tmem = thread_memory_from_self();
guint ix = SLAB_INDEX (allocator, chunk_size);
// 优先归还至缓存2，如果缓存2满，则交换12，并在此归还给2,
// 如果都满，则会释放回全局缓存中。
if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
  {
    thread_memory_swap_magazines (tmem, ix);
    if (G_UNLIKELY (thread_memory_magazine2_is_full (tmem, ix)))
      thread_memory_magazine2_unload (tmem, ix);
  }
if (G_UNLIKELY (g_mem_gc_friendly))
  memset (mem_block, 0, chunk_size);
thread_memory_magazine2_free (tmem, ix, mem_block);

unload函数中我们直接看主要的处理函数magazine_cache_push_magazine。这里将归还的magazine打上元数据信息，并归还至全局magazine，并触发全局magazine的清理操作，清理时间超过一定限制的缓存块，归还其至slab。注意，这里第一句的时候在规整这个magazine，如果这个magazine的第一个chunk是带有子链的，则会规整为前四个元数据节点为普通链表的形式，均无子链的形状，具体见上面的图。

static void
magazine_cache_push_magazine (guint      ix,
                              ChunkLink *magazine_chunks,
                              gsize      count) /* must be >= MIN_MAGAZINE_SIZE */
{
  // 重整这个magazine，保证其元数据是以一维链表的形式存在，而非带有子链的形式。
  ChunkLink *current = magazine_chain_prepare_fields (magazine_chunks);
  ChunkLink *next, *prev;
  g_mutex_lock (&allocator->magazine_mutex);
  /* add magazine at head */
  // 将缓存添加到全局缓存，并维护相应的元数据信息
  // 上下链表节点，chunk数，和当前归还至全局缓存的时间戳。
  next = allocator->magazines[ix];
  if (next)
    prev = magazine_chain_prev (next);
  else
    next = prev = current;
  magazine_chain_next (prev) = current;
  magazine_chain_prev (next) = current;
  magazine_chain_prev (current) = prev;
  magazine_chain_next (current) = next;
  magazine_chain_count (current) = (gpointer) count;
  /* stamp magazine */
  magazine_cache_update_stamp();
  magazine_chain_stamp (current) = GUINT_TO_POINTER (allocator->last_stamp);
  allocator->magazines[ix] = current;
  /* free old magazines beyond a certain threshold */
  // 清理存放超过一定时间的magazine，将其归还至slab中。
  magazine_cache_trim (allocator, ix, allocator->last_stamp);
  /* g_mutex_unlock (allocator->mutex); was done by magazine_cache_trim() */
}

magazine_cache_trim会根据当前时间和每个magazine被归还的时间进行比较，如果超时则会将magazine归还至slab层。

static void
magazine_cache_trim (Allocator *allocator,
                     guint      ix,
                     guint      stamp)
{
  /* g_mutex_lock (allocator->mutex); done by caller */
  /* trim magazine cache from tail */
  // 环形链表，从尾部向前遍历所有magazine。
  // 由于进出都是从头部开始处理，因此其在链表顺序上时间也是顺序的，尾部时间戳越小，空闲时间越大。
  ChunkLink *current = magazine_chain_prev (allocator->magazines[ix]);
  ChunkLink *trash = NULL;
  while (ABS (stamp - magazine_chain_uint_stamp (current)) >= allocator->config.working_set_msecs)
    {
      /* unlink */
	  // 当一个magazine超时后，会将其从全局magazine缓存中摘除，并添加到一个临时的trash链表中。
      ChunkLink *prev = magazine_chain_prev (current);
      ChunkLink *next = magazine_chain_next (current);
      magazine_chain_next (prev) = next;
      magazine_chain_prev (next) = prev;
      /* clear special fields, put on trash stack */
      magazine_chain_next (current) = NULL;
      magazine_chain_count (current) = NULL;
      magazine_chain_stamp (current) = NULL;
      magazine_chain_prev (current) = trash;
      trash = current;
      /* fixup list head if required */
      if (current == allocator->magazines[ix])
        {
          // 遍历了一圈。
          allocator->magazines[ix] = NULL;
          break;
        }
      current = prev;
    }
  g_mutex_unlock (&allocator->magazine_mutex);
  /* free trash */
  // 将所有删除的magazine归还至slab。
  if (trash)
    {
      const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);
      g_mutex_lock (&allocator->slab_mutex);
      while (trash)
        {
          current = trash;
          trash = magazine_chain_prev (current);
          magazine_chain_prev (current) = NULL; /* clear special field */
          while (current)
            {
              ChunkLink *chunk = magazine_chain_pop_head (¤t);
              slab_allocator_free_chunk (chunk_size, chunk);
            }
        }
      g_mutex_unlock (&allocator->slab_mutex);
    }
}

参考文档：

[1] glib的slab算法学习

[2] 缓存染色技术

[3] cache associativity

[4] magazine layer

原文链接：https://blog.csdn.net/MeRcy_PM/article/details/53398802