2012年（7）
分类：
2012-02-05 12:47:04
原文地址：【讨论】简析堆内存 作者：jiangwen127
1. 接口
用户空间示意图如下，堆区从数据段尾端开始生长，动态分配普通大小的内存，超大块内存则直接在共享内存区（文件映射区）映射空间。
图1 进程地址空间示意图
内核记录了进程堆空间的位置，并提供系统调用brk/sbrk给用户，动态伸缩该空间。
图2 堆区生长示意图
用户程序通过malloc与C库交互，后者再通过brk/sbrk与内核交互。用户调用C库函数malloc时，如果没有找到合适的空闲内存块，则调用brk/sbrk扩展堆空间。调用free时，也可能调用brk/sbrk收缩堆空间。
图3 malloc调用示意图
2. 结构
C库把堆空间当做一个数据结构来管理，一般包含空闲表和隐式表，空闲表记录空闲内存块，隐式表将分割的内存块按地址顺序连接起来。
一个比较典型的堆结构示意图如下，具体实现可参考《【例子】“首次匹配法”动态内存分配的实现》。
图4 典型的堆结构示意图
malloc时，在空闲表中查找合适的内存块，如果找到的内存块比申请的大很多，还要切割内存块，将切下来的空闲块加入空闲表和隐式表。
free时，先检查是否可以合并隐式表上的相邻空闲块，然后将合并后的内存块加入空闲表。
图5 free操作示意图
free块1后，库函数将它链入空闲表；free块2后，库函数也将它链入空闲表，由于块2在堆顶，因此内核有可能会回收该空间，此时块2所在空间的映射被断开。
所以，通常free(ptr)后，随着时间推移，ptr指向的地址空间通常有4种状态：
1：在空闲表中（free后，还未被重新分配出去）。
2：在隐式表中，但不在空闲表中（free后，又被重新分配出去）。
3：在隐式表中（部分字节已用作堆结构的控制数据，如隐式表的表头或表尾）。
4：不在隐式表中（free后，被内核回收）。
如果free(ptr)后，过段时间再来访问ptr，针对上述4种状态，将会有以下结果：
1：读写都能成功；读取的是之前保留下来的值，写操作无副作用。
2：读写都能成功；读取的是不可预期的值，写操作会影响其他对象，导致程序错误。
3：读写都能成功；读取的是不可预期的值，写操作会破坏堆结构，导致程序错误。
4：读写都失败，导致进程立刻退出。
一旦用户疏忽造成了上述错误，在测试时，
1—若出现情况4，则跟踪调试即可，因为出错的地方就是案发第一现场。
2—若出现情况3，因为破坏堆结构后，程序不会立刻出错，而要当再次访问堆结构（malloc/free）时才会出错，而且可能每次出错地点不相同。因此找到第一现场有些难度。
3—若出现情况2，与上一条类似，只是程序不一定会出错退出，而会产生错误结果。
4—若测试期间情况2、3、4都未出现，而是如情况1所述，那是最糟糕的，因为问题最终很可能会暴露在客户那里。
3. 碎片
内存碎片是指进程地址空间中的空闲内存，由于种种原因，导致这些内存无法被内核收回，形成内存碎片。
久而久之，当malloc一块大内存时，堆结构空闲表没有合适的空闲块，malloc通过系统调用sbrk扩展堆空间，但此刻空闲物理内存短缺，从而导致OOM Killer错误（暴露在写时拷贝操作，可参考《【基础】关于Linux的malloc的写时拷贝(延迟分配)》），虽然总的空闲内存【空闲物理内存+进程释放但内核未能回收的内存】足够。
内存碎片（这里指片外碎片）的原因主要有：
1．未释放的块妨碍内核回收空闲物理内存；
2．未释放的块妨碍C库合并相邻空闲块。
图6 内存碎片示意图
如图6所示，堆顶的内存块妨碍了内核回收空闲物理内存，2个空闲块间的内存块妨碍了C库合并空闲块。
4. 定制
如果内存碎片不及时处理，那么随着时间推移，情况可能会越来越糟，最终将导致系统瘫痪。这对于那些长时间运转的系统（如工业控制系统）来说，是致命的。因此对于一些专用系统，需要定制合适的内存管理器。
自定义的动态内存管理可以是基于C库的二次管理，也可以直接分配静态内存进行管理，后者就干脆屏蔽了堆内存的使用。
一般我们可以采用前者，即在C库的基础上，再自定义内存管理器，管理算法有很多，其中内存池比较常用（同时还可使用一些简单的垃圾回收机制），主要适用于有小内存块频繁分配和释放的系统。主要思路是：将小内存块集中在堆的底部分配，避免小内存块散落在大内存块之间而造成碎片。具体实现可参考Slab算法。
