CppExplore

作者：CppExplore  http://www.cppblog.com/CppExplore/和http://blog.csdn.net/cppexplore同步发布
一 linux内存管理以及内存碎片产生原因

                    
        最底层使用伙伴算法管理内存页面。系统将所有空闲内存页面分10个组，每个组中的内存块大小依次是1，2，4......512个内存页面，每组中的内存块大小相同，并且以链表结构保存。大小相同，并且内存地址连续的两个内存块称为伙伴。伙伴算法的中心思想就是将成为伙伴的空闲内存合并成一个更大的内存块。
        os中使用get_free_page获取空闲页面，如果找不到合适大小的空闲页面，则从更大的组中找到空闲内存块，分配出去，并将剩余内存分割，插入到合适的组中。当归还内存时，启动伙伴算法合并空闲内存。如果不停的申请内存，并且部分归还，但归还的内存不能成为伙伴，长期运行后，所有内存将被分割成不相邻的小块，当再次申请大块内存时，则可能由于找不到足够大的连续内存块而失败，这种零散的不相邻的小块内存称之为内存碎片。当然这只是理论上的说明，伙伴算法本身就是为了解决内存碎片问题。

二  malloc子系统内存管理（dlmalloc)
        应用层面的开发并不是直接调用sbrk/mmap之类的函数，而是调用malloc/free等malloc子系统提供的函数，linux上安装的大多为DougLea的dlmalloc或者其变形ptmalloc。下面以dlmalloc为例说明malloc工作的原理。
1 dlmalloc下名词解释：
   boundary tag: 边界标记，每个空闲内存块均有头部表识和尾部标识，尾部表识的作为是合并空闲内存块时更快。这部分空间属于无法被应用层面使用浪费的内存空间。
   smallbins: 小内存箱。dlmalloc将8,16,24......512大小的内存分箱，相临箱子中的内存相差8字节。每个箱子中的内存大小均相同，并且以双向链表连接。
   treebins: 树结构箱。大于512字节的内存不再是每8字节1箱，而是一个范围段一箱。比如512~640, 640~896.....每个箱子的范围段依次是128，256，512......。每箱中的结构不再是双向链表，而是树形结构。
   dv chunk:  当申请内存而在对应大小的箱中找不到大小合适的内存，则从更大的箱中找一块内存，划分出需要的内存，剩余的内存称之为dv chunk.
   top chunk: 当dlmalloc中管理的内存都找不到合适的内存时，则调用sbrk从系统申请内存，可以增长内存方向的chunk称为top chunk.
2 内存分配算法
        从合适的箱子中寻找内存块-->从相临的箱子中寻找内存块-->从dv chunk分配内存-->从其他可行的箱子中分配内存-->从top chunk中分配内存-->调用sbrk/mmap申请内存
3 内存释放算法
       临近内存合并-->如属于top chunk，判断top chunk>128k，是则归还系统
                              -->不属于chunk，则归相应的箱子

dlmalloc还有小内存缓存等其他机制。可以看出经过dlmalloc，频繁调用malloc/free并不会产生内存碎片，只要后续还有相同的内存大小的内存被申请，仍旧会使用以前的合适内存，除非大量调用malloc之后少量释放free，并且新的malloc又大于以前free的内存大小，造成dlmalloc不停的从系统申请内存，而free掉的小内存因被使用的内存割断，而使top chunk<128k，不能归还给系统。即便如此，占用的总内存量也小于的确被使用的内存量的2倍（使用的内存和空闲的内存交叉分割，并且空闲的内存总是小于使用的内存大小）。因此可以说，在没有内存泄露的情况，常规频繁调用malloc/free并不会产生内存碎片。

三  应用层内存池
即便没有内存碎片问题，应用层仍然需要内存池，原因如下：
1 使用的内存固定可控  稳定性角度
2 减少与内核态交互的可能  性能角度
3 减少互斥操作  性能角度，各个线程直接调用malloc，极有可能有线程进入竞态条件，陷入内核态。
其中稳定性只能是聊以自慰的说法，os本身都不可信，哪里还来得稳定性的说法。最重要的出发点，是应用层控制内存，提高应用层性能。那么如何创建使用内存池，才能充分提高内存使用的性能呢？我们先从著名的内存池看起。

四  常见内存池
变长内存池：
1 apr pool : 针对业务处理，将整个业务场景分段，不同阶段使用不同类型内存池，内存归还池后并不能被再次使用，而是池本身可以被重复使用，特浪费内存。
2 obstack: gcc自带变长内存池

定长内存池：
1 SGI STL:  针对小内存做池，字节长度为8,16......128共16个池，每个池中内存大小相同，使用链表连接，小内存采取永不归还malloc子系统策略，大于128直接调用malloc。SGI STL为gcc携带的stl实现。vc以及bc携带的stl，虽然也有allocator对象，但并没有真正的池，而是直接调用malloc。

2 boost/loki
两种内存池采用类似的底层算法，以loki为例子，首次申请一块定长内存，loki会一次性申请255个，之后再次申请从该池中直接获取，从池中申请释放内存算法示例如下：


（1）首次申请内存后，对空闲内存编号，并且前一个内存保存下一块内存的编号，一变量NextBlock保存下次可以申请出的内存块，首次NextBlock=0
（2）当申请出3块内存后，NextBlock=3
（3）当第二块内存归还时，根据内存基址找到所属的内存chunk，对比chunk基址以及该持中内存块长度，找到该块编号，尾部编号保存NextBlock，NextBlock=1
（4）再次归还第三块，第三块尾部保存上次的NextBlock，NextBlock=2
（5）再次申请内存，根据NextBlock指定分配出的内存，NextBlock等于该块内存尾部指向的值1.
以上模拟stack的压栈出栈行为.
loki和boost对内存的处理上有稍许差别，包括内存的组织层次上，这些差别我个人看都是loki相对于boost的缺点。
loki/boost代表了当前内存池的最高水准，该池无任何冗余头部（free的内存才保存冗余信息），更节省内存；另外分配释放内存快速，只有固定极少的常数步骤计算。
以上算法只是给内存池的后续使用打下坚实基础，并没有给出内存池的使用方式。

五 内存池使用方式分类
      loki给出了内存池使用的策略，分以下3种：
1 全局内存池  所有相同长度的内存申请，使用同一个内存池，不同长度内存申请使用不同内存池。对池中的内存进行申请释放操作时，对池执行加锁操作。
2 对象内存池 每个对象一个内存池。内存申请释放执行加锁操作。
3 线程内存池 相同长度的内存并且在同一个内存中的内存申请释放使用线程内存池，内存申请释放不执行加锁操作。

     对比第三部分，应用层使用内存池的原因。显然全局内存池并没有解决性能问题，各线程并发申请内存，仍然存在类似直接调用malloc的互斥问题。
而对象内存池将这种互斥进一步降低，仅仅跨线程对同一对象申请释放内存才会遇到互斥问题。
而线程内存池无疑是最高效的，没有锁开销。
      可见最佳的内存池使用方式为，对存在跨线程操作的对象，使用对象内存池，对于只在同一线程内操作的对象使用线程内存池。对象可以通过重载对象的operator new, operator delete等实现。
      boost库极其适合进一步封装，供对象内存池和线程内存池（结合thread-specific storage）使用。

六 Linux下内存池终结者
       tcmalloc，可以通过cache等机制智能判断应该使用对象内存池还是线程内存池，编码不需要任何额外策略，直接使用new/delete，只要最后连接上libtcmalloc之类的库即可。可惜仅仅支持linux。
      已有明确的测试数据支持，链接tcmalloc后，原cpu居高不下，突高的服务器程序，大大减少了直接调用malloc的互斥竞态条件出现，cpu趋于平稳。典型的就是linux下链接tcmalloc后重编译的mysql。