堆和栈的区别
| 堆内存 | 栈内存 | |
|---|---|---|
| 典型用例 | 动态增长的链表等结构 | 函数局部数组 |
| 申请方式 | 使用函数申请，通过指针使用 | 直接声明 |
| 释放方式 | 使用函数释放 | 系统回收 |
| 管理方式 | 使用者管理 | 系统管理 |
| 所处位置 | 变化范围大 | 相对固定 |
| 增长方向 | 低向高排列 | 高向低增加 |
堆的数据结构与管理策略
堆块
堆块：出于性能的考虑，堆区的内存按不同大小组织成块，以堆块为单位进行标识，而不是传统的按字节标识。一个堆块包括两个部分：块首和块身。块首是一个堆块头部的几个字节， 用来标识这个堆块自身的信息（本块的大小、本块空闲还是占用等信息），块身是紧跟在块首后面的部分，也是最终分配给用户使用的数据区。
堆表并不索引所有的堆块。在Windows系统中：
- 处于占用态的堆块由正在使用它的程序索引
- 处于空闲态的堆块由堆表索引。
空闲的堆块大小不一，而且其使用频率不定。可能较小的堆块的使用频率更高，较大的使用频率较低，这需要对这两种情况进行不同的索引方式以提高效率。该问题主要通过不同类型的堆表进行解决，其中，最重要的堆表有两种：空闲双向链表Freelist和快速单向链表Lookaside。
堆表
堆表一般位于堆区的起始位置，用于索引堆区中所有堆块的重要信息，包括堆块的位置、堆块的大小、空闲还是占用等。堆表里有很多信息：段表索引，虚表索引，空表使用标识，空表索引区
空表
空闲堆块的堆首有一对链表指针，空闲堆块之间组成双向链表--空表：
- 双向链表共有128条
- free[1]开始，每个链表保存的堆块大小依次+8字节
- free[0]保存大于1024字节的堆块（小于512KB）
快表
快表是Windows加速堆块分配采用的堆表：
- 不会出现堆块合并（因为其中的空闲堆块被设置为占用态，不会发生合并，大大提高堆块分配速度）
- 快表只有在精确匹配的时候才会分配（分割或合并后的堆块）
- 有128条，组织结构和空表类似，但是单链表
- 初始化的时候会初始化为空，每条快表有4个节点
- 单链表操作比双链表简单，快表速度快
堆操作
堆操作：
- 堆块分配：
- 快表，找到大小匹配空闲的堆块，修改一下堆块状态，从堆表中取出，返回一个指针给程序使用
- 普通空表，寻找最优的空闲堆块，找不到则找次优的
- 0号空表，从后往前寻找合适的堆块（满足条件的最小堆块）
- 堆块释放：将堆块修改为空闲状态，然后插入相应的链表末尾
- 堆块合并（内存紧缩）：为了减少内存碎片，当两个堆块相邻且空闲时，堆管理系统就会进行堆块合并操作：将两个堆块断链，合并堆块，调整合并后的堆块头信息，将合并后的堆块插入合适的链表
堆根据内存大小不同可以分为三类：小块（size<1kb），大块（1KB<=size<512KB），大大块（512KB<=size）
分配与释放算法
| 分配 | 释放 | |
|---|---|---|
| 小块 | 分配顺序：快表，空表，堆缓存，0号空表，内存紧缩后重试，如果还不行就返回NULL | 优先插入快表（上限4个）如果快表满了就插入空表 |
| 大块 | 堆缓存分配，失败则使用0号空表的大块分配 | 优先插入堆缓存，如果满了则插入0号空表 |
| 巨块 | 虚分配 | 直接释放 |
堆分配函数调用关系
Windows下堆管理结构如下：
Windows中很多堆相关的管理函数的调用关系如图，最终都会到同一个函数RtlAllocHeap()：
参考资料
-
《0Day安全》