堆对于开发者一般来说是熟悉又陌生的，熟悉是因为我们常常使用new/delete或者malloc/free使用堆，陌生是因为我们基本没有去了解堆的结构。堆在什么地方？怎么申请？怎么释放？系统又是怎么管理堆的呢？
带着疑问，这两天看了<软件漏洞分析技术>与<漏洞战争>中关于堆的说明，终于对于堆有一点点的了解了。这里记录一下在学习和调试中的一点笔记。
二、关于堆的基本知识
1).首先了解空闲双向链表和快速单向链表的概念
1.空闲双向链表(空表)
空闲堆块的块首中包含一对重要的指针，这对指针用于将空闲堆块组织成双向链表。按照堆块的大小不同，空表总共被分为128条。
堆区一开始的堆表区中有一个128项的指针数组，被称作空表索引(Freelist array)。该数组的每一项包括两个指针，用于标识一条空表。
如图所示，空表索引的第二项(free[1])标识了堆中所有大小为8字节的空闲堆块。之后每个索引项指示的空闲堆块递增8字节。例如free[2]为16字节的空闲堆块，free[3]为24字节的空闲堆块，free[127]为1016字节的空闲堆块。
空闲堆块的大小 = 索引项(ID) x 8(字节)
把空闲堆块按照大小的不同链入不同的空表，可以方便堆管理系统高效检索指定大小的空闲堆块。需要注意的是，空表索引的第一项(free[0])所标识的空表相对比较特殊。这条双向链表链入了所有大于等于1024字节的堆块（小于512KB），升序排列。
2.快速单项链表(快表)
快表是Windows用来加速堆块分配而采用的一种堆表。这里之所以叫做"快表"是因为这类单项链表中从来不会发生堆块合并(其中的空闲块块首被设置为占用态，用来防止堆块合并)
快表也有128条，组织结构与空表类似，只是其中的堆块按照单项链表组织。
快表总是被初始化为空，而且每条快表最多只有4个结点，故很快就会被填满。
2）堆块的结构
堆块分为块首和块身，实际上，我们使用函数申请得到的地址指针都会越过8字节(32位系统)的块首，直接指向数据区(块身)。堆块的大小包括块首在内的，如果申请32字节，实际会分配40字节，8字节的块首+32字节的块身。同时堆块的单位是8字节，不足8字节按8字节分配。堆块分为占用态和空闲态。
其中空闲态结构为：
占用态结构为
空闲态将块首后8个字节用于存放空表指针了。
在64位系统，块首大小为16字节，按16字节对齐。
3）堆块的分配和释放
1.堆块分配
堆块分配可以分为三类：快表分配、普通空表分配和零号空表（free[0]分配）。
从快表中分配堆块比较简单，包括寻找到大小匹配的空闲堆块、将其状态修改为占用态、把它从堆表中"卸下"、最后返回一个指向堆块快身的指针给程序使用。
普通空表分配时首先寻找最优的空闲块分配，若失败，则寻找次优的空闲块分配，即最小的能满足要求的空闲块。
零号空表中按照大小升序链着大小不同的空闲块，故在分配时先从free[0]反向查找最后一个块(即最大块)，看能否满足要求，如果满足要求，再正向搜索最小能满足要求的空闲堆块进行分配。
当空表中无法找到匹配的"最优"堆块时，一个稍大些的块会被用于分配，这种次优分配发生时，会先从大块中按请求的大小精确地"割"出一块进行分配，然后给剩下的部分重新标注块首，链入空表。
由于快表只有在精确匹配才会分配，所以不存在上述现象。
2.堆块的释放
释放堆块的操作包括将堆块状态改为空闲，链入相应的堆表。所有的释放块都链入堆表的末尾，分配的时候也先从堆表末尾拿。
另外需要强调，快表最多只有4项。
3.堆块的分配和释放
在具体进行堆块分配和释放时，根据操作内存大小不同，Windows采取的策略也会有所不同。可以把内存按照大小分为三类：
小块：Size < 1KB
大块：1KB < Size < 512KB
巨块：Size >= 512KB
小块