C++基础：SGI STL二级空间配置器内存池

2024/12/14-2024/12/ ：
这篇稍微写一下阅读SGI STL内存池的收获。
reference:
[1] 深度剖析SGI STL二级空间配置器内存池源码
[2] C++内存管理：new / delete 和 cookie
[3] 侯捷 内存管理

一、写在前面

SGI STL由Silicon Graphics Computer Systems公司参照HP STL实现，主要设计者仍然是STL之父Alexandar Stepanov，被Linux的C++编译器GCC所采用。

在重构SGI STL的源码时，我看到了社区中许多很完善的源码解析，之前有篇写了一半的，实在没别人完善所以直接删掉了，因为既然做的没别人好，也给不了读者什么参考价值。但是，最近开始对重构项目进行复盘，好像也看到了写一篇复盘文章的必要性——有时候就算做的没有别人好，自己的理解似乎也有存在的必要。因此按照侯捷的内存管理课程重新做了一下复盘。

让我有些意外的是，在回头复盘这个项目的时候，看见了之前背过八股和别的项目一些相似细节的影子，这也许就是在学习中有所收获的印证。

二、二级空间配置器解读

2.1 从 malloc 和 free 开始

在SGI STL中若申请一块较大的内存（界限为128b）则采用一级空间配置器，而一级空间配置器直接调用 malloc 和 free 实现内存块的分配，二级空间配置器也使用了 malloc 和 free（不如说这两个函数是一个内存池无法避开的必要操作），但是二级空间配置器使用这两个函数的频率并没有一级空间配置器这么频繁。

对于如何优化内存分配的效率，一般有两个方面的考量：

• 内存分配层面：
  在这个层面，我们希望达到一次申请，多次分配的效果。也就是说一次申请一大块的内存，后面需要分配直接在这一大块内存里面用指针的方式直接拿。
• cookie开销层面：
  在malloc中，分配内存带有cookie，即一部分存储当前分配内存空间大小等信息的额外空间，如果能减少这一部分的开销，对内存空间的利用一定更充分。

众所周知，new的操作步骤一共两步，即内存分配和对象构造，前者调用::operator new，而在普通的内存分配方式（一级空间配置器）中，::operator new直接调用malloc来实现内存的分配。因此，如果需要实现内存池，我们就需要对对象的operator new进行重载操作（同理，需要重载::operator delete实现内存的回收）。

ps. 本文用的单位都是byte，按照侯捷讲的来。实际上根据代码来应该是B（字节），但是这也并不影响理解。

2.2 SGI STL 内存池结构

SGI STL 内存池的结构如下，内存池维护了一个 free_list 指针数组，每个指针指向一串内存块链表，如 #0 指向的内存块为8b，#1 指向一串由16b内存块构成的内存块链表…以此类推。可知 #15 指向的内存块链表中每一块内存的大小为128b。

那么大于128b的内存块该怎么办？这就不需要使用二级空间配置器了，直接使用一级空间配置器的mallco即可，这样的设计可以理解——cookie可以看作内存块的浪费率，内存块越大，cookie的大小不变，而浪费率自然就更小，我们可以接受这样的浪费。

2.3 内存分配操作

另一个层面思考，过大的内存块意味着更大的连续内存，我们看到下面可以知道，如果池中有足够内存，内存块链表会一次申请一大块连续内存（roundup(size)*20）来扩充自己的大小（池中内存连一个内存块都不够则继续用malloc申请内存），如果 free_list 支持更大的256b乃至512b的内存块链表，这么一大块的连续内存可能并不存在，这就很容易给我们的内存分配带来麻烦，所以不如直接交给malloc来申请离散的内存块。

至于roundup函数的作用，是为了将申请的内存向上对齐至8b(1B)单位（比如申请31b，则对齐至4B(32b)，申请9b，则对齐至2B(16b)），因为我们维护的free_list 里面的内存块链表都是以8b为单位增长的，如果不加上一个对齐的操作，可能会在内存分配的时候产生内部碎片。

下图展示了当用户申请32b时内存池中进行的操作。顺便可以注意到，返回给用户的第一个内存块（绿色）上面是一个小的蓝色内存块，这个指的是这次malloc附带的cookie。

除此之外，内存池做了一个记录累计申请量的操作，同时，也更新了池中start_free指针和end_free指针的指向，来指向池中剩下的可用内存块。

下图中，申请的内存块为64b，虽然池中的余量不足 roundup(size)*20，但是仍有 roundup(size)*9 即9块符合要求的内存块，数量在1-20之间。这里将第一块给用户，剩下的构成 #7 下的内存块链表。此时池中内存分配完，start_free 和 end_free 重合，因为没有用malloc继续申请内存，所以没有多出新的小块cookie内存。

问题来了，如果剩下的内存块不足一个，因为我们内存对齐的操作，这块内存的大小一定在8-128b之间，且以8B为单位对齐（无论是将池中的内存分配给内存块链表还是用malloc扩展内存池，我们的操作是始终对齐8b的）。处理这块内存碎片的方法很简单，将其接入适合其大小的内存块链表即可。

接下来申请96b的内存，可是池中剩余内存为0，则继续使用malloc增加池中内存再分配给用户以及内存块链表。申请的内存大小为roundup(96b)202 + roundup(累计申请量/16)，然后给用户一块roundup(96b)，剩下roundup(96b)*19即19块内存接到对应的内存块链表上。因为是第二次malloc，所以上面带了一个小块红色cookie。

可以看到，累计申请量是会越来越大的，所以池在每次扩张时额外申请的内存也会越来越大，这比较符合平时的设计经验。

接下来其实就是以此类推了：

下图则展示了申请size大小的内存块时，roundup(size)对应位置的内存块链表上面还有内存块的情况：

这里展示的其实就是继续从池中分配内存的操作了：

在这里我们可以看到，当池中剩下不足一块时，对待内存碎片的处理方法和我们之前讲过的一样。可以看到，#9 下面的内存块链表多出了一块：

接下来的操作之前都做过了：

2.4 内存切分操作

该操作在系统内存不够，malloc申请失败时进行。此时虽然余下内存不够分配，但是内存块链表中还有许多白色的内存块未被分配。下图中就申请了一个72b的内存块，但是malloc失败，这时候，找比72b更大的8b单位内存块，80b、88b等等都是可用的。算法会取一个最接近的80b，将其切分为两部分，即72b和8b。将这两个内存挂到对应的#8以及#0下，然后将72b的部分交给用户。

下图又申请了一个72b内存块，此时malloc失败且#8（72b）、#9（80b）都没有内存了。这时拿一个#9（88b）下的内存块，同样做一次切分，切成72b以及16b然后挂在对应的内存块链表下，再将72b那块分配给用户。

2.3 纰漏

但是如果我们申请一个稍大的120b内存块，这时malloc失败，剩下的内存链表中也找不到比它大的内存块了。如下图：

对于这种情况，我们仍然有两种补救措施：

• 利用池中更小的内存块组成所需的大内存块：
  这可能是我们第一时间的想法，这种方法可以看作是切分的逆操作，但是用代码实现的难度会高很多。
• 改变malloc的策略：
  malloc申请失败并不意味着堆上真的没空间了，只能说明malloc申请量大于该空间大小。上面也说过，malloc的内存申请大小是受到当前申请的内存块大小以及内存池累计申请大小的影响，不如对计算申请量的公式略作修改，少申请一点内存便能很容易解决这个问题。

在代码中给出的解决方案是直接使用malloc来分配对应大小的内存，不多不少。

还有一点，在内存池的deallocate中并没有调用free，这就是说整个内存池的大小是只会增加不会减少的。在一些情况下，我们是不希望内存池这么做的。deallocate实际上做了一个将分配给对象的内存块重新挂到对应的内存块链表上的操作。