【导读】

   一直想总结一下关于内存池方面自己的理解和使用, 临近春节(写完不知已是何时), 终于陆陆续续有些时间能写点东西, 网上关于此方面的文章数不胜数, 但仍旧想通过自己之手写(敲)出点文字, 一是自己也能够通过这种方式温故而知新；二是希望能从自己对这方面的理解带给大家一些不同的东西.

    关于内存池的概念, 优点, 缺点什么的, 真不想说太多, 简单总结以下, 其他大家google吧, 嘿嘿.

    所谓池, 其实就是一种资源的集中, 那么内存池, 自然就是预先将内存集中在一块.

内存池帮助我们解决的问题:

Hello_desired_world乱聊内存池(一) - boost内存池原理与介绍

   首先我还是从boost内存池大概原理, 以及组件分类开始, 由外向内地剖析boost内存池的实现, 毕竟我觉得比起晦涩难懂的代码来说, 通俗的文字表述和图形总能更让人快速接受.

从使用者的角度来讲的话, boost内存池分为如下几个组件模块: pool, object_pool, singleton_pool, pool_alloc(pool_allocator, fast_pool_allocator). 这些都是定长内存池, 所以, boost目前的版本(hello_desired_world使用的是1.44)没有提供不定长内存池.

pool: 与object_pool最大的区别就是其不提供自动调用对象构造和析构函数, 而只负责分配指定大小的内存.

object_pool: 基于pool实现, 提供对象内存池, 根据使用者给予的模板类型, 可以构造出自定义的类型, 并且在object_pool本身析构时, 会自动调用所有使用者忘记释还给内存池的对象的析构函数.

singleton_pool: 提供线程安全, 并且可以通过静态方法访问的内存池, 基于pool实现.

pool_alloc: 用于替换stl标准库中allocator的默认实现, 所以该组件完全符合stl allocator的接口设计.pool_alloc提供了两种stl allocator, 一个是pool_allocator, 另一个则是fast_pool_allocator. 两者都是基于singleton_pool实现, 前者擅长分配多个并且连续内存的数据, 后者擅长每次只分配单个数据.

简单介绍了以上几个组件之后, 我们这就开始进行深入分析吧. 虽然说boost提供了这些用于不同场景的定长内存池, 但他们底层都基于同一种数据结构, boost将这种数据结构实现为 class simple_segregated_storage(以下简称sss).

    simple_segregated_storage:

    sss维护着当前内存池中所有可用的内存块, 并用链表的方式将每个内存块给串联起来, 并可以通过sss中任意一块可用内存块, “导向”到下一块可用内存块, 一般我们称这种结构为空闲内存块链表 - free_list(以下均简称为free_list). 这里提到了链表, 可能有人会想, 我们平时编写数据链表时, 通常需要另外维护一个指针来指向链表的下一个元素, 而指针本身又是一种空间开销, 这种方法很明显与我们编写内存池用来减少消耗(空间和时间)的目的背道而驰了. 当然, 我们不可能那么做, 还记得sss主要是维护当前内存池中所有可用的内存块, 也就是没有被分配给使用者的内存, 那么这些内存的“内容”就可以任意被我们充分利用了, 我们完全可以将一块可用内存块的 “内容”写为下一块可用内存块的地址.如图1-1:

                                   图1-1

    内存块A的内容为B的地址, 内存块B的内容为C的地址, 如果是最后一块可用内存块(这里是C) ,那么值就为0. 这边读者肯定还会产生一些疑惑:

    对于Q1, 可以说, 是的, boost内存池不管使用者最初给予的 “定长” 是多大, 最终总会对齐到某个最适当的大小(起码能够容纳下本机的最大地址值), 例如:

    void* ptr = pool(3).malloc();

    这里我们初始化了一个匿名的可以分配3个字节的定长内存池pool, 然后调用malloc分配出我们需要的内存, 但是ptr指向的可用内存不仅仅只有3bytes, boost内部会按 4bytes/8bytes(视环境而定) 进行对齐, 那么ptr指向的这块内存到底有多大? 4bytes还是8bytes? 之后在分析代码时我们便知, 但是有一点需要提醒, 就是不要因为贪图小便宜而去使用后面的空余内存, 虽然可能在本机上合法, 但是这样的程序没有可移植性甚至在其他环境下可能会导致内存崩溃的问题.

    好了, 现在我们来看Q2. 这个问题牵涉到boost内存池的预分配策略, 乍一听使用链表会造成很多碎片, 但事实上这里是在一大块连续的内存内部实现的链表指向, 假设使用者初始化了定长为6bytes的内存池, 那么boost对齐到8bytes, 然后我们看图1-2, 其展示了较为真实的内存布局情况.

图1-2

    现在, 让我们用抽象的思维将物理内存想象成图1-2, 这是boost内存池向系统预申请(通过malloc或new)的一块连续内存, 大小是 8bytes(对齐后的单个数据空间大小) * 32 = 256bytes, 每个数据空间都占8bytes, 而每个数据空间的前4个字节, 都记录着下一块可用内存的地址(最后一个数据空间的前四个字节为0), 但是后四个字节的内容未知, 因为标准函数malloc不负责将申请的内存赋为零. 我相信大家都已经看到那个高高在上的叫做first的东东了, first是sss维护的一个指针, 指向free_list的第一块可用内存, 每当使用者需要内存来存放数据时, boost内存池就会通过sss的first指针找到可用内存, 返回给使用者. 好, 现在我们来模拟一下图1-2的场景在分配给使用者一块数据块之后的情况, 看图1-3.

            图 1-3

哈哈, 现在[0xaabbcc00,0xaabbcc08)这块内存区域已经脱离了我们可用内存块的大家庭, 寻找自己的幸福去了, 而且它也可能已经被使用者写入了用户数据, 覆盖了原来的地址值.

    好了, 分配暂时说到这里, 我们现在来说说boost内存池(都由sss提供接口)的内存释放策略了. 首先要明确的是, 所有释放给boost的内存池的内存, 都只是将其重新加入到free_list的管理中去, 永远都不会还给系统. 我们接着用上面的场景, 假设这时候使用者调用boost内存池提供的释放接口将[0xaabbcc00,0xaabbcc08)的内存还给boost内存池, 会如何? 非常easy, 图1-3将会变回原来图1-2的情况, first指针重新指向[0xaabbcc00,0xaabbcc08), [0xaabbcc00,0xaabbcc08)和[0xaabbcc08,0xaabbcc10)重新建立起节点指向的关系. 但这只是释放时的一种最简单的场景, 考虑如下情况: 使用者连续向boost内存池申请了两次内存, 那么根据sss的first指针, 使用者首先得到[0xaabbcc00,0xaabbcc08), 然后会拿到[0xaabbcc08,0xaabbcc10), 好了, 现在使用者可以肆意蹂躏这两块内存了(虽然是连续的, 也可以说是一块, 但使用者可以不知道), 在一番玩弄之后, 使用者厌烦了, 决定抛弃它们, 于是就调用了boost内存池的释放接口依次释放[0xaabbcc00,0xaabbcc08)和[0xaabbcc08,0xaabbcc10), 我们来看看第一次释放之后的情景, 图1-4.

            图1-4

接着, 我们马上来看第二块内存[0xaabbcc08,0xaabbcc10)如何加入到free_list中, 也许聪明的读者早就想到, 这还不简单, 直接将[0xaabbcc08,0xaabbcc10)加入到链表头, first -> [0xaabbcc08,0xaabbcc10) -> [0xaabbcc00,0xaabbcc08) 如此不就行了, 只不过和图1-2的指向不太一样罢了, 但并不影响下一次的分配啊. 没错, 确实如此, sss的普通释放free(void*)函数就是这么做的, 但还有另外一种释放方式, 由ordered_free(void*)函数实现, 见名知意, 我们可以称之为 “有序释放”, 也就是说, 不管使用者先释放哪一块内存, 该释放函数都会保证由低地址内存块指向高地址内存块的顺序, 说得再直白一点, 就是你甭管先释放哪个, 就必须给我还原成最原始的内存块指向顺序(图1-2)就行了, 而不是哪块后释放, 哪块就是链表头, 辈份还是要按照最初的来. 由此, 我们可以得出两种第二次释放内存后的情景, 第一种情况是调用了普通的sss::free(void*). 如图1-5.

                图1-5

第二种情况就是调用了sss::ordered_free(void*). 还原成了图1-2, ordered_free函数会将使用者传入的要释放的内存依次和现有管理中的可用内存块地址进行比较, 直到找到最适他的那个链表位置(由小到大排序), 然后才修改指向. 读者一定会想, 为什么要有ordered_free的存在, 顺序就那么重要吗, 无序内存块链表应该也能满足基本需求啊. 没错, 是这样的, 但是ordered_free的存在一定有它的意义, 只是目前我们还不需要知道, 之后的内容中我们会讲到它的用处, 这边就暂时卖个关子啦.

我们现在继续关注分配时的一个问题, 上面的场景都是在一块固定大小的连续内存中进行操作的, 既然是固定的, 就一定会有山穷水尽的时候, 那boost是如何让它柳暗花明的呢? 依然是灰常easy, 这块内存不够用了, 那就再申请呗, 只不过boost会成倍增长对系统申请的内存大小, 例如我们上面的例子, boost会预分配32个数据空间, 当这32个数据空间都用完了, boost会再预分配64个数据空间进来, 如果之后还不够, 就会再预分配128个, 以此类推, 估计大家都嫌我罗嗦了, 我们还是先看一下当第一块连续内存块用尽时的图吧. 如图1-6.

               图1-6

我们可以看到, 当仅剩最后一块可用内存块时, 使用者调用分配函数后, first指针依旧按照原来的逻辑指向链表中的下一块内存, 但是[0xaabbccf8,0xaabbccfc)中的值为0, 没事, 我们就让first这家伙暂时与0为伍吧. 等到下一次分配给使用者内存时, 我们就将展开新的世界的分配工作, 新世界! 我们来啦! 继续上面的场景, 当使用者继续调用分配函数时, 如图1-7.

                图1-7

    我们可以清楚地看到, boost内存池重新申请了一块大小为512bytes的连续内存B,  是原来内存块的两倍, 现在boost内存池根据first的指向, 就能从内存块B中拿到需要的内存, 不知道读者注意到没有, 在图1-7中, 内存块A好像(全部分配给了使用者)已经完全不受我们的掌控了, 那如果使用者永远不将内存块A中的数据块还给boost, boost内存池就无法安全地释放或者析构A中的数据了吗, 答案当然是否定的, 我们现在所看的图中确实已经没有任何指向或者说管理着被分配出去的内存的部分, 但是位于数据结构sss上层的组件 - pool, 它有能力管理着这一切, 我准备把这个内容放到之后几篇中讲解, 现在就不多加熬述了.

    让我们回到图1-7中, 可以看到内存块B的地址要比内存块A的高, 这里要注意的是, 不一定后申请(指向系统申请)的内存就比之前申请的内存地址要高, 完全有可能是相反的, 我特意提到地址高低的原因是这关系到sss的ordered_free策略, 还记得上面提到两种释放策略吗:

1. free(void*)

2. ordered_free(void*)

我们已经见识过在同一块连续内存中释放内存的简单情景, 那么现在已经有了两块连续内存, 如果这时候内存块A中的内存被释放, 会怎样? 其实, 对于sss来说, 它本身不知道内存是否连续, 在它看来, 逻辑很简单, 如果是free, 那它就将被使用者释放的内存块直接加入到free_list的头(被first指向), 如果是ordered_free, 那它就将释放的内存块依次和free_list中的内存块进行地址比较, 直到找到前一块内存的地址小于等于它, 而后一块内存的地址大于它的位置, 然后插入到链表的这个位置, 就大功告成. 读者是不是已经厌烦我枯燥无味的文字了? 明眼人一看就知道是从小到大排序的链表嘛, 说那么绕干嘛, 骗字数啊? 哈哈… 是的…=.=!(砖头飞来), 好了, 我继续用图来呈现这个情景, 看图1-8.

                图1-8

    可以看到, 不管使用者调用free还是ordered_free, 将内存块A中的数据块释放给boost内存池时, 在free_list中的顺序都是一样的, 因为内存块A的地址比内存块B的地址要低, 所以当内存块A中的数据块释放回来的时候, ordered_free函数将被释放的内存块在和free_list的第一块内存块进行地址比较的时候, 就能找到其对应的位置并插入(链表头), 所以这里的情况调用free和调用ordered_free的结果是一样的. 我们接着想象, 假设欲求不满的使用者并疯狂地向boost内存池请求内存, 最后正好使内存块A和内存块B使用殆尽(中间没有任何释放过程), 图1-9.

                     图1-9

    然后他开始将手头上从boost内存池中得到的内存开始按照得到的顺序依次归还给boost内存池, 如果是free释放策略, 那么最后[0xaabbdef8,0xaabbdefc)将成为free_list的头结点(因为是最后被使用者传入free函数的), 逆序指向地址低的内存块. 而如果是ordered_free策略, 会以地址最低的内存块为头结点(从小到大排序), 顺序指向地址高的内存块. 如图1-10.

                图1-10

    可以看到, 两种释放策略造成了两种相反的链表指向结果. 那他们的执行过程呢? 我们知道free策略是直接将被释放的块作为头结点, 无需寻找链表位置, 所以复杂度为O(1), 而ordered_free需要从头结点一直遍历直到寻找到合适的位置, 这个场景中, 使用者每释放一块内存块, sss都需要从first开始, 对整个free_list进行一次全遍历, 才能找到合适的位置(free_list尾部), 所以这个场景展现了ordered_free最坏情况下的时间复杂度, 为O(N), 这也是网上诸多对boost内存池诟病的一个重要原因.

    Boost内存池的基本原理就先讲到这里, 在下篇中, 我将会对boost内存池组件pool进行分析.

【编者加注】

    感谢 @hello_desired_world 投递的技术文章，若是有不理解或争论的地方，请大家直接新浪微博或站内留言与其交流，后续作者会继续抽时间完成后续的篇章，分别为：《Hello_desired_world乱聊内存池(二) - boost pool》、《Hello_desired_world乱聊内存池(三) - boost object_pool, singleton_pool, pool_alloc》、《Hello_desired_world乱聊内存池(四) - SGI-STL内存池》、《Hello_desired_world乱聊内存池(五) - Web服务常用内存池》、《Hello_desired_world乱聊内存池(六) - 系统级内存分配算法dlmalloc》，敬请大家关注！

建议继续学习：

1. Nginx源码分析-内存池    (阅读：4227)