SGI版本的STL其精髓之一就是空间配置器的实现其余还有算法、适配器、容器。空间配置器根据申请内存大小的不同选择使用一级空间配置器__malloc_alloc_templateinst还是二级空间配置器__default_alloc_templatethreads, 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_bytesstart_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同索引处那么直接返回传入的原指针。因为旧内存空间本来就很大——“你本来就很美”。