1. 简介：
Glib中使用了slab进行内存管理(代码解释见[1]，cache coloring见[2])，同时引入了magazine cache来进行多级缓存。本文主要介绍magazine cache部分实现，不讨论slab和使用malloc的实现代码。
2. 层级关系：
采用了magazine layer后的glib内存管理，在整体上一共分为四个层级：
1. 线程缓存magazine层，这一层为线程专属，每个线程维护自己的两个空闲链表，内存申请和释放首先与这一级的缓存进行交付。
（按：ThreadMemory: 包含两个Magazine串，magazine1, magazine2。）
2. 全局缓存magazine层，这一层为全局的缓存，当某个线程缓存空了需要申请内存，会先向全局缓存进行申请，当某个线程的空闲链表都满了，会将其中一级缓存释放回全局缓存层。
（按：
以下是Allocator结构体的部分成员，其中magzines，就是全局缓存magazine，当某个线程缓存空了以后，就需要从这里申请缓存，同时也会将缓存还到这里。
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) */ guint color_accu; } Allocator
）
3. slab层。（按: 个人感觉，上面结构中的slab_stack 就是slab层，其结构如下示：
struct _SlabInfo { ChunkLink *chunks; guint n_allocated; SlabInfo *next, *prev; };
）
4. 系统层。
3. 数据结构：
magazine本身数据结构上看起来并不复杂，但是其在实际使用时引入了一些复杂的操作。
[cpp] view plain copy // 这里的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关键字的功能。
[cpp] view plain copy 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形状。
[cpp] view plain copy 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。
[cpp] view plain copy // 根据大小查找索引 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分配过程这里不讨论。
[cpp] view plain copy 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中，如果两个缓存都满了，则会将缓存归还给全局缓存。
[cpp] view plain copy // 获取当前线程缓存，并根据内存大小计算索引。 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是带有子链的，则会规整为前四个元数据节点为普通链表的形式，均无子链的形状，具体见上面的图。
[cpp] view plain copy 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层。
[cpp] view plain copy 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
原文出处：http://blog.csdn.net/mercy_pm/article/details/53398802
