SlabPlus 内存分配算法

原理叙述：

我也来介绍一种内存管理方面的优化算法：怎样才能根除内存碎片？有且只有如下办法：1. 只分配不释放，2. 只分配固定大小内存，3. 不分配内存，虽然，仍不妨碍我们再一次回顾各种常用的分配策略，以发掘一些新的思路：

前提：下面提及的分配技巧并不能说是“最快的”，也不能说是“最小碎片的”，但是可以保证，不管系统运行多长时间，不管分配多大内存，碎片比例趋于恒定，同时分配时间为常数（unit interval）：

最后将讨论一些更进一步的优化技巧（如果愿意大量增加代码行数的话），看看在分配内存方面，哪些我们值得努力，哪些不值得我们努力。

现代的内存分配算法，需要顾及以下几个特性：

1）缓存命中：现今的计算机体系，优秀的缓存策略对一个系统而言异常重要，一些写的不太注意的分配器，容易忽略该特性，前分配一块内存，后分配一块内存，大大增加了缓存的失效。

2）总线平衡：大部分缓存管理都是提供 2^n字节大小的内存机制，并且所分配地址也是以 2^n字节进行对齐，比如我们有一个 packfile对象有400多个字节，将使用 512字节的缓存分配器，并且按照 512字节进行对齐，但是问题在于，大部分时候我们都在访问该对象的头30个字节，因此在(0-30) mod 512的地方，也就是在以512字节为分割的缓存线周围集中了大量的压力，在现今的大部分普通的缓存芯片上将出现总线失衡bus-overbalance。

3）页面归还：何时向系统请求页面，何时归还系统页面，很多分配器只向系统不停的申请页面，却并不考虑提供保证能够正常不断的归还系统页面的机制。

4）多核优化：尽管多核技术现在才逐渐在PC上推广，但我们的服务器很早就已经开始使用双核或者四核的架构，分配器如何尽量避免在不同核间产生的等待，是分配器效率优化的一个前提。

以下几点内容有助于优化我们的分配器：

1）菲波拉契 vs 等比数列：

我们可能习惯于使用 2^n字节的多级缓存管理器来进行内存分配，就是针对 8, 16, 32, 64 … 1k, 2k…大小的缓存提供对应的分配策略，由于按照大小的 2^n字节对齐后再进行分配，因此有 50%的内存白白浪费，其实就统计上来看，使用 2^n增长的多级分配器不如使用菲波拉契方式排列的方式：8, 16, 24, 40 …. 大部分情况，后者能更有效的利用内存。

2）三层页面链表：

通常分配器缓存为空时便向系统请求一个新页面，然后进行分配，那怎么比较有效的保证持续归还系统空闲的页面呢？通常使用三层双向页面链表：A, B, C

链表-A：保存完全没有分配过的页面队列链表-B：保存分配过但是还有空闲块的页面队列链表-C：保存完全分配完了的页面

需要分配内存的时候我们会先查找B中有无还没有分配干净的页面，有就在该页面上进行分配，如果该页面刚好被分配完了，那么就把它从B中转移到C，如果B中为空，那么我们就该向系统请求新的页面了。

当释放的时候判断内存块所处页面的情况，如果之后该页面还有部分内容没释放干净，那么放入B中，如果释放干净了，那么放入A中。B链表使用FIFO策略，等待一个页面上已经分配出去的内存块能够有充分的时间释放回来。

随着内存的释放，当达到一定规模时候，我们将A中存在的页面归还给os

3）地址着色：

在一个页面上的所有待分配对象，最好不要都从偏移为0的地方进行划分，为了避免bus-overbalance，我们可以根据不同的页面，对起始对象地址进行有规律的偏移（coloring），比如一个管理N字节对象的分配器，当请求到新页面的时候，第一次按照 0, N, 2N, …划分，那么第二次按照 8, 8 + N, 8 + 2N, …第三次按照16, 16 + N, 16 + 2N，进行划分，如此类推，以保证我们分配出来的对象不会总卡在某些地址线的固定位置。

4）前端LRU：

分配器前端可以挂接长度为2N的LRU队列，初始的时候，我们分配 N个对象给 LRU队列，外部请求新对象的时候，直接从 LRU中取出，释放就直接放回 LRU，如果 N个新对象都用完了，那么再次向队列中填充 N个新分配出来的对象，如果不停的释放，导致长度 2N的LRU都填充满了，那么一次性归还一半（N个）对象到分配器。

5）多核优化：

出于对多核情况下减少锁定带来的开销，我们可以为不同的 CPU提供多个 LRU，比如我们如果为分配器前端提供N个LRU的话，那么可以用 n = CPUID mod N来确定，当代吗运行于编号为 i的cpu上，我们选择用编号为 n的 LRU队列，如此，互斥锁的开销将会大大降低，同时根据 LRU“一次性分配/释放N个对象”的情况，我们的内存分配器也可以进行一些优化，将N次批量请求的互斥锁开销进一步降低。

上面所提及的5种方法，各种操作系统内核分配策略，近些年也在不断创新，上面这些经验策略在各种操作系统的实践中都取得了很好的效果。但是我们应用层开发却有别于系统层的开发，因为内核程序可以方便的将一个个离散的页面隐射在连续的地址空间上，但是应用层开发在不做页面隐射的条件下，当我们需要分配大小接近或者超过一个页面的时候就会出现问题。

应用层问题：

比如我们在4K页面上分配1100字节的对象，那么最多一个页面只能分配三个对象，利用率仅有：3300/4096=80%，有 4096 – 3300 = 796个字节被浪费掉了，而如果我们每次只分配8个字节的对象，那么一个页面最多有 4096 / 8 = 512个对象供分配，问题在于一个页面上分布的待分配对象越多，那么该页面归还系统的几率就越小，因为我们起码要等到这512个对象都归还回这个页面了，才能将这一整页归还给系统。比起在4K页面上分配 64字节大小对象的情况，后者一个页面有更多几率是前者的 p ^ 8倍。

但是，虽然我们在应用层不做页面-地址映射，但是我们还是能够使用一些新的页面管理技术，解决应用层分配器的页面限制，以下的解决方案我不知道有没有人用过，原自之前对服务器内存管理优化时得出的一种方案：

GFP-Tree

之前2004年底开发服务器代码时，通过强制内存使用最频繁的部分只分配三种固定大小的内存，使用了3个分配器两个用于分配结构体，一个用来分配大小为4K的页面，当缓存要求大于4K时都使用4K进行链表串接，并专门为这种基于4k页面的缓存提供了常用读写访问接口，其上实现了各种“缓存”，“流”变长字符串的操作接口。用限制应用层逻辑的代价，实现单位时间分配与零碎片。

要冲破这个限制就需要对我们的页面管理器 — GFP（Get Free Pages）在应用层作进一步的改进，传统的内存分配器与 GFP的关系如下：

GFP(4K或者8K,16K等) +– 8字节分配器 +– 16字节分配器 +– 32字节分配器 …… +– 2 ^ n 字节分配器

所有的分配器都向唯一的 GFP请求页面，这其实又回到前面提到的困扰上，将使我们对选择页面的大小犹豫不决：小了，大对象无法分配，大了，小对象分配却又难回收，浪费大。

其实问题的本源在于我们默认了系统的页面只能是固定的 4K或者其他，如果抛开计算机硬件页面固定大小对我们暗示的限制，转而思考，如果提供不同大小页面的GFP，情况将会如何？

所谓的 GFP-Tree就是让所有分配器都具备 GFP的功能，也就是说，除去最原始的固定大小的GFP，我们所有建立在该GFP之上的内存分配器除了向该 GFP请求释放内存外，他同时提供GFP功能，比如建立在4KGFP上的1K分配器，除了提供 1K大小对象的分配功能外，本身也可以作为 GFP提供 1k大小的页面管理，供下一级分配器进行页面请求。由此从最初的GFP开始，一级级创接分配器，新的分配器又提供对应的 GFP接口供更小内存的分配器使用，从而形成了一个树形结构，称之为 GFP-Tree，见下图示例:

GFP(4M)
  |
  +----+
2M     1M
       |
  +----+------+------+
 512K  256K  128K   64K
                     |
  +----+------+------+
 32K  16K     8K    4K
                     |
  +----+------+------+------+--------+
  2K   1K    512    256    128       64
       |
  +----+----+
  32   16   8

分配策略：

上面的图中表述出在固定页面 4MB的GFP下面，逐级挂接的不同大小分配器的组织方式，当我们创建一个分配器的接口中，都必须增加 GFP的指针，指明页面提供者，这样生成了这个多级 GFP-Tree，当我们请求8字节大小的内存时，8字节分配器发现没有页面了，它就会请求它的GFP(1K分配器)，而上一级1K的分配器如果没有页面了，又会请求4k,4k请求64K，64K请求1MB，而1MB请求最终的 4MB GFP。

回收策略：

参考前面提到的“三层页面链表”方式，将页面分为“干净的，部分的，用完的”三个队列，并使用FIFO策略使得“部分的”页面链表中的页面有足够的时间等到对象释放回来，变成“干净的”页面，而“干净”的页面超过一定阀值时将会被释放给 GFP，那么当我们释放了 8字节内存的时候如果该内存所处页面刚好变成空页面那么如果 8字节分配器中空页面的数量超过阀值，将会有一半1K字节的页面释放给他们的上级GFP–1K分配器。

评估策略：

一个页面的最佳使用情况是，只分配该页面大小1/32 – 1/8之间的对象，这样页面利用率是最好效果，当我们创建一个新的分配器（比如大小不是 n ^ 2的），我们就需在“分配器池”中为他寻找最佳的 GFP，方式是不但需要考虑是否在 ¹⁄₃₂ – 1/8之间，还需要考虑空间浪费情况，这个空间浪费将会按照递归的方式一直计算到根节点GFP，再求和，最后寻找出最优的 GFP作为该分配器的父节点。

变动策略：

加入新分配器节点时，首先在现有的GFP-Tree中寻找出最佳父节点后，作为子节点插入 GFP-Tree，然后更新用于查找分配器的sizemap（多级数组，分别用来查询0-1K, 1K-64K, 64K-1M, 1M-64M的各个大小分配应该由哪个分配器完成）

删除新分配器时并不能马上删除，只是记录而已，直到该分配器没有子节点，引用计数为零的时候才执行，如果确实删除了一个节点，那么将减少其父节点的引用计数，递归向上，最后更新sizemap。

优化方式可以设置一个开关，在申请增加一个大小为N的分配器时，可以浏览 GFP-Tree，找到一个大小和它差不多的给他，前提是那个分配器比N大，但是误差在10%以内即可，这样大大提高了整棵 GFP-Tree的利用率。

观点总结

上面图中的 GFP-Tree节点还是按照 2^n大小的，这是为了方便阅读和说明问题，实际我在应用中使用的是2^n与菲波拉契大小的若干分配器，因为三层页面链表保证了持续的向上级归还空闲页面，所以我们的初始 GFP页面大小可以选择稍微大些的，比如 64K, 1MB, 4MB或者更大，整个 GFP-Tree的上下协调机制提供了初始GFP页面大小以内的所有内存分配机制，使用前面所提及的所有技巧，解决了应用层页面管理问题，整个分配工作没有任何一个循环，没有任何一次搜索，都能以单位时间完成分配/释放。

不敢说时间就是很快，但是至少可以保证不管系统运行多长时间，不论多大面积的分配操作，其开销是 unitinterval，多次试验中，冗余内存基本徘徊在 30%-65%之间。