SGI-STL配置器allocator篇

SGI版本的STL其精髓之一就是空间配置器的实现，其余还有算法、适配器、容器。空间配置器根据申请内存大小的不同选择使用一级空间配置器（__malloc_alloc_template<inst>）还是二级空间配置器（__default_alloc_template<threads, inst>）。在SGI版本的STL实现中，判断阈值threshold为128字节——若一次申请的内存超过128字节，则使用一级空间配置器，否则使用二级空间配置器。

一级空间配置器：

一级空间配置器定义了用于空间分配的allocate函数、用于释放内存的deallocate函数、用于重新分配内存的reallocate函数、用于分别处理上述函数执行发生空间不足状况（out of memory, oom）的oom_malloc函数和oom_realloc函数、一个指向可由用户自定义处理oom的函数的指针__malloc_alloc_oom_handler、以及重定向函数指针的set_malloc_handler函数。以上函数和函数指针均使用了static修饰。接下来讲述各函数的实现原理，旨在欣赏该版本设计上的“美”。

（ 函数声明）static void* allocate(size_t)，该函数内部调用的还是C语言的malloc(size_t)函数。如果分配内存不成功，即返回的指针为空，那么就需要调用oom_malloc函数。oom_malloc函数内部会判断成员函数指针__malloc_alloc_oom_handler是否为空，若不为空则执行该指针指向的函数，否则抛出“out of memory”异常。经过*__malloc_alloc_oom_handler处理之后再次执行malloc函数重新申请空间。上述过程是一个循环事件，一直到抛出异常或成功开辟空间并返回新空间首地址才会退出。个人认为自定义函数的设计目标之一可能是类似于操作系统对于内存的管理，将某些分片区域进行紧凑合并，从而腾出更多的连续空间（底下有勘误）。除了alloocate函数外，（函数声明）static void* reallocate(void*, size_t, size_t)操作与上述的操作如出一辙，不同点就是调用oom_realloc函数和C语言的realloc(void*, size_t)函数，所以处理oom的还是__malloc_alloc_oom_handler指向的函数。

（函数声明）static void (* set_malloc_handler(void (*f)()))()，由此可以看出成员中的函数指针应指向什么样的函数了。这个函数也没什么好讲的了。deallocate函数也没什么好讲的，不说了！接下来开始最精彩的二级空间配置器对于内存的管理机制。

二级空间配置器：

当一次申请内存空间小于128字节时，启用二级空间配置器。在具体实现中，调用一级配置器的入口其实还是设计在了二级空间配置器内部——当容器端使用二级空间配置器申请内存大于128字节时，会进行memory_threshold判断，然后进入调用一级空间配置器allocate函数分支。

二级空间配置器的实现主要是基于一块用于管理“碎片内存”的“内存链”和一整块连续的“内存池”。内存链（free_list）其实是一个长度为16的数组，存储类型为SGI自定义的obj类型。该类型是一个union联合体，内部包含obj*和char[]。当该obj未被分配时，内部存储的是obj*，用于连接下一个obj从而保证链的连续；当该obj被返回给用户时，内部存储的是char[]，用于用户写入数据。该数组从低索引到高索引，每块负责管理的内存大小比前一个索引负责管理的内存大小要多8字节，最低管理内存大小为8字节，最高为128字节。内存池其实是一块连续的内存空间，使用start_free和end_free分别指向开始地址和结束地址。有了内存池的存在，可以减缓二级配置器因内存链耗尽而频繁调用malloc收到的影响。

下面开始介绍二级空间配置是如何allocate的。该函数接收参数是size_t类型的变量n，表示申请内存大小。如前所述，当n大于128字节调用一级空间配置器的allocate，否则继续下面操作。逻辑先判断n具体落在内存链的哪一个索引处，从而去对应位置取出内存片返回给用户，具体方法是将n丢入一个叫FREELIST_INDEX(size_t bytes)的函数即可返回对应的索引位置。该函数运算一遍(bytes + 7) / 8 - 1，得出的结果就是其索引index。然后查找free_list[index]，如果发现“诶，有obj耶”，咱们就可以 拿着这块obj返回给用户了，后续再经典“上尾连下头”维护一下free_list就完成这次操作了。但是如果发现索引下空空如也，那就必须要自己动手去开辟链条了。下面会调用refill(size_t n)函数，该函数的作用是用单位大小为n bytes的内存片一一填满这空空的索引，注意咱们调用refill函数时，要保证传入的n大小满足是8（即一个最小内存大小）的倍数。再来看看refill函数中有什么？首先会默认待创建的内存片有20个（不出意外待会有19个内存片要填满free_list[FREELIST_INDEX(n)]，因为还有一个用户说要），接下来调用chunk_alloc(size_t n, int& nobjs)函数，让它替咱们申请空间，如果内存充足，咱们可以拿到所有申请的内存片，然后分一片给用户，其余全部进free_list对应管理区；如果情况还不算太糟糕，咱们还可以得到一部分内存片，这就是为什么形参nobjs采用引用的方式，继续返回一片给用户（就算只申请到一片）；如果太糟糕，咱们啥也拿不到，得跟用户“say sorry”了。

看看我们chunk_alloc(size_t size, int& nobjs)函数干了些什么。还记得我们前面提到的内存池，接下来就需要它来大显身手了。我们需要先判断内存池空间bytes_left(= end_free - start_free)够不够申请的空间total_bytes(= size * nobjs)，如果发现内存池“海量”，直接大手一挥分配给咱们total_bytes，start_free += total_bytes更新一下，任务完成，可以return；如果内存池还不至于捉襟见肘，那咱们有啥拿啥——可以分成几片内存就拿几片。拿完后更新nobjs=拿到的数量，更新total_bytes = size * nobjs，更新start_free += total_bytes，此时原本富足的内存池被我们洗劫一空，仅剩空间end_free - start_free < size，但是别怕，后备隐藏能源会得到补充，内存池终将得到救赎；现在的内存池已经一穷二白了，供不上一片内存了。没事！我chunk_alloc继续操作，滴水之恩当涌泉相报——现在为内存池申请高达bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4)的内存空间，ROUND_UP作用是返回距heap_size >> 4最近且较大的8的倍数，heap_size记录的是本二级容器配置器成功使用malloc分配到的空间总和，注意一级空间配置器不算。为什么不增加heap_size，而是除了一个16？因为不能给太多了，以免这个容器用不了那么多，让内存池拿着不是浪费了吗？这次我们终于需要用malloc获取新的内存空间了。在给内存池补充之前，需要先把他“余量”再给拿过来挂在内存链free_list对应的位置上（如果有的话）。现在的内存池是真的啥都没有了(start_free = end_free)。但是我们知道malloc也不一定能成功，如果malloc返回值start_free != 0！“内存池好兄弟，我chunk_alloc终不负你，我带着涌泉凯旋而归了，用涌泉填满你！”，end_free = start_free + bytes_to_get，更新heap_size += bytes_to_get以当作内存池好好服从的下一次奖池，然后继续调用chunk_alloc(size, nobjs)完成这次的分配任务；如果malloc返回失败了，“抱歉好兄弟，我chunk_alloc老弟无能为力，看看free_list那边怎么说”。虽然malloc失败了，内存池啥也没得到，但是chunk_alloc会继续去遍历内存链free_list从满足size的最小索引到最大索引。如果发现有满足的内存片，即刻取出该片放入内存池，此时内存池又有了一点微弱资金，然后继续调用chunk_alloc继续剥夺内存池，完成分配任务。若是free_list老弟也挤不出来大块了，那么chunk_alloc也尽力了，内存池啥都没了，进入一级空间配置器创造奇迹吧。

下面来看一看deallocate(void* p, size_t n)函数是如何回收内存的。首先判断n与128的大小关系，大于则直接使用一级空间配置器的deallocate；小于则需要二级空间配置器自己处理。处理过程可简述为找到n对应的索引index，将该片内存重新挂载在free_list[FREELIST_INDEX(n)]。

至此，已经讲述了一级空间配置器的allocate、reallocate、oom_malloc、oom_realloc、deallocate、__malloc_alloc_oom_handler和二级空间配置器的allocate、refill、chunk_alloc、dealllocate、内存链、内存池，还有reallocate没有讲述，因为书上没说。

个人设计reallocate函数逻辑：判断新要求的内存大小决定用一级空间配置器还是二级空间配置器。若是二级空间配置器，先使用allocate分配内存空间，如果失败则返回失败结果，成功则将就空间的元素使用memcpy使用较底层手段迁移数据，然后回收旧空间。

勘误：

据Chatgpt所说，__malloc_alloc_oom_handler指向的自定义函数更大可能是由用户自己选择释放掉一些内存空间，不至于触及到内核层操作，因为用户毕竟只是用户，不是root。

“内存链”为个人异想天开式叫法，“自由链表数组”更能表现实现形式。

二级空间配置器的reallocate函数补充：若申请的内存空间与旧内存空间实际是对应free_list同索引处，那么直接返回传入的原指针。因为旧内存空间本来就很大——“你本来就很美”。