windows程序员进阶系列：《软件调试》之堆 （二）
win32堆及内部结构
Windows在创建一个新的进程时会为该进程创建第一个堆，被称为进程的默认堆。默认堆的句柄会被保存在进程环境块_PEB的ProcessHeap字段中。
要获得_PEB的地址，可以通过$peb伪寄存器来获得,dt _PEB @$peb。也可以通过.process获得。
如上图ProcessHeap字段即为进程默认堆。其上的HeapSegmentReserve是进程堆的预订（默认为1MB）大小。HeapSegmentCommit是进程堆的初始提交大小。默认值为2个内存页大小（x86内存页为4KB）。
可以通过GetProcessHeap函数来取得当前进程的默认堆句柄：
HANDLE GetProcessHeap(void);
该函数仅仅是找到_PEB结构然后取出PEB结构中的ProcessHeaps字段的值。获得进程默认堆的句柄后就可以调用HeapAlloc从默认堆上分配空间了 。
除了进程的默认堆以外，应用程序也可以调用HeapCreate函数创建自己的堆，这样创建的堆被称为私有堆。
HANDLE HeapCreate( DWORD flOptions, SIZE_T dwInitialSize, SIZE_T dwMaximumSize);
具体使用方法请参考MSDN。
进程的默认堆与私有堆没有本质的区别。两者都是通过调用RtlHeapCreate创建的。只是用途不同。
除了默认堆，进程的_PEB中还记录了当前进程的所有堆句柄。NumberOfHeaps字段用来介绍堆的总数。ProcessHeaps是一个数组，用来记录每个堆的句柄。
使用windbg加载calc.exe。并查看_PEB结构。
可以看到calc.exe共有13各堆，堆数组首地址位0x7c99ffe0。
打印出此地址的内容：
使用！heap –h命令可以打印出所有的堆
可以看到共有13个堆。每个堆的首地址与前面堆数组中显示的内容相同。
调用HeapAlloc函数可以从win32堆中分配空间。
LPVOID HeapAlloc( HANDLE hHeap, DWORD dwFlags, SIZE_T dwBytes);
具体使用方法，请参考MSDN。
如果分配成功该函数返回所分配空间的指针。还可以使用HeapReAlloc来改变从堆中分配内存的大小。
LPVOID HeapReAlloc( HANDLE hHeap, DWORD dwFlags, LPVOID lpMem, SIZE_T dwBytes);
当不再需要使用堆中的空间时可以调用HeapFree释放。
BOOL HeapFree( HANDLE hHeap, DWORD dwFlags, LPVOID lpMem);
调用HeapFree并不意味者对管理器会将这块内存交还给内存管理器。这是因为应用程序还有可能会继续申请空间，为了减少与对管理器交互的次数，堆管理器只有在下面两个条件同时满足时才会将其交还给内存管理器，这个过程被称为解除提交。
第一个条件：本次释放的堆块大小超过了_PEB中的HeapDeCommitFreeBlockThreshold字段的值。
第二个条件：空闲空间的总大小超过了_PEB中的eapDeCommitTotalFreeThreshold字段的值。
可以看到当要释放的堆块大小超过4KB，并且堆上的空闲空间的总大小大于64KB时，堆管理器才会将空闲空间交还给内存管理器，即执行解除提交操作。
堆内部结构
接下来将介绍对内部结构，也是深入理解堆的重中之重。
从前面的_PEB中的堆数组我们可以知道，进程中可以存在多个堆。在每个堆内部又可以分为多个堆段。堆管理器在创建堆时创建的第一个段，我们将其称为0号段。如果堆是可增长的，当一个段不能满足要求时，堆管理器会继续创建其他段。但最多可以有64个段。段内部又由堆块构成。
每个堆使用_HEAP结构来描述。
_HEAP结构记录该堆的属性和资产情况。因此该结构也被称为是堆的头结构。调用HeapCreate函数返回的句柄便是此结构的地址。
VirtualMemoryThreshold为虚拟内存分配阈值，表示可以在段中分配的堆块的最大有效（即应用程序可以实际使用的）值，该值为508kB。当应用程序从堆中分配的堆块的最大大小大于该值的申请，堆管理器会直接从内存管理器中分配，并不会从从空闲链表申请。同时将此空间添加到VirtualAllocdBlocks结构所指向的链表中。
VirtualAllocdBlocks是一个链表的头指针，该链表维护着所有大于VirtualMemoryThreshold直接从内存管理器申请的空间。
Segments是一个数组，它记录着堆拥有的所有段。每个元素类型为_HEAP_SEGMENT结构。
LastSegmentIndex表示堆中最后一个段的序号，加1便是总段数。
FreeLists是一个双向链表的头指针，该链表记录着所有空闲堆块的地址。链表元素为FREE_LIST结构，
该链表为双向链表，每个链表中都保存着一些空闲堆块。各个链表项都指向_HEAP_FREE_ENTRY结构中的FreeList字段。
当应用程序申请新的空间时，堆管理器会首先遍历这个链表，如果找到满足需要的堆块就分配出去。否则便要考虑建立新的堆块或从内存管理器申请空间。在释放时，当不满足解除提交条件时，大多数情况下也是将要释放的堆块加入到该空闲链表中。
FrontEndHeap该字段为指针指向前端分配器。在本文的最后部分我专门介绍前端分配器。
堆段
每个段使用_HEAP_SEGMENT结构描述。
Entry字段是一个数组，存储着该段所有的堆块。由于每个堆块使用_HEAP_ENTRY结构描述，因此该数组元素类型为_HEAP_ENTRY。
Heap字段维护该块块所属的堆的_HEAP结构的首地址。
BaseAddress字段维护该段的基地址。
FirstEntry表示该段中第一个堆块的地址。
堆块
段内部又可以分为多个堆块。堆块使用 _HEAP_ENTYR结构来描述，该结构占8 Byte。_HEAP_ENTRY结构之后就是供应用程序使用的区域。调用HeapAlloc函数将返回HEAP_ENTRY之后的地址。此地址减去8Byte便可以得到_HEAP_ENTRY结构。
_HEAP_ENTRY的前两个字节Size字段表示该堆块的大小。其单位为8byte。表示每个堆块的最大大小为2^16 *8 byte = 512KB。由于每个堆块都需要8字节的_HEAP_ENTRY结构，因此每个堆块能提供给应用程序的最大大小为512KB-8B = 0x7ffdefff。该值等于_HEAP结构的MaximumAllocationSize字段的值。
PreviousSize表示前一个堆块的大小。
Flags字段代表堆块的状态。
可以通过！heap –a获得。
UnusedBytes表示多分配的字节数。比如应用程序申请1020个字节，但堆管理器为了内存对齐分配了1024个字节。这4个字节就是多分配的值，此时Unused字段就为4。
SegmentIndex表示该堆块所在的段在HEAP结构Segments数组的序号。若为0则表示该堆块是从堆中0号段中分配的。
堆分配和释放实例
使用以下代码构建HeapTest.exe程序。
int main(int argc, _TCHAR* argv[]){ HANDLE hHeap = HeapCreate(HEAP_NO_SERIALIZE, 0, 1024*1024); void * p = HeapAlloc(hHeap, HEAP_NO_SERIALIZE, 1012); bool bRetVal = HeapFree(hHeap, HEAP_NO_SERIALIZE, p); return 0;}
在HeapTest.exe中创建了一个私有堆，该堆大小为1MB。然后从该私有堆中分配1012Byte的空间，最后进行释放。非常的简单，仅仅是为了演示堆的创建、分配空间和释放空间的过程。
由于进程在退出时会清理默认堆和所有其他堆，因此上面的代码中并没有销毁堆的操作。读者只要明白最后操作系统会执行所有的堆的清理工作即可。
在HANDLE hHeap = HeapCreate(HEAP_NO_SERIALIZE, 0, 1024*1024)处设置断点。在windbg中载入HeapTest.exe。开始调试，程序停在该处。
观察hHeap 的值为0x00420000。该值即为该私有堆_HEAP结构的地址。
dt _HEAP 0x00420000
SegmentReserve字段的值为0x100000 = 1MB。表示我们请求创建的堆的最大大小。SegmentCommit为0x2000，表示仅仅提交两个页面为8KB。LastSegmentIndex为0，表示该堆中只有1个段。
单步执行，代码执行到void * p = HeapAlloc(hHeap, HEAP_NO_SERIALIZE, 1012);该语句表示从私有堆中分配1012Byte。
观察p的值为0x00420650。该值表示返回给应用程序的有效用户区地址。该地址减去8byte，得到_HEAP_ENTRY结构的首地址。
Size 为0x82，由于块大小粒度为8byte，可以得到0x82 *8byte = 1040Byte 。UnusedBytes 为28byte。 1040 - 28得到段块的用户有效长度为1012byte。SegmentIndex等于0，表示该断块处于第0号段。
Flags等于7，表示该堆块处于占用状态，且块尾有额外的描述，且进行过填充（使用baadf00d填充）。
观察0x00420650处得内存，发现的确进行过填充。
继续单步执行到bool bRetVal = HeapFree(hHeap, HEAP_NO_SERIALIZE, p);该语句表示从堆中释放p表示的空间。
执行此语句后观察p处得内存：
发现除开头的8个字节外，其余字节已经使用feee（类似free）填充过。这是堆对已经释放的内存的填充。
继续观察该堆块
大小从刚才的0x82变为0x137，即0x137 *8 = 2488Byte。为什么释放后该堆块的大小范围变大了呢？这是因为堆管理器将刚才释放的堆块与其后的空闲区域合并成了一个大的堆块。这样可以防止堆碎片的发生。堆块标志变为0x14，表示该堆块为空闲，进行过填充且是这个段中的最后一个块。
对于已经释放的堆块，堆管理器定义了_HEAP_ FREE_ENTRY结构来描述。该结构的前八个字节与_HEAP_ENTRY结构完全相同。但增加了8个字节来存储空闲链表的头节点。
使用上面的地址观察_HEAP_FREE_ENTRY结构。
_HEAP_FREE_ENTRY字段比_HEAP_ENTRY结构多了一个FreeList字段，用来存储空闲链表的一个链表项。多个链表项构成一个空闲链表。
由于空闲了链表为双向链表，Flink和Blink字段分别指向前一个和后一个空闲的堆块（指向_HEAP_FREE_ENTRY的_FreeList字段）。
由于该链表仅仅只有一个空闲堆块，因此上述_LIST_ENTRY的Flink和Blink 字段均指向空闲链表的头结点。
在前面介绍的_HEAP结构中包含了一个Free_list数组，该数组有128个元素，用来存储各个空闲链表的表头。空闲链表的元素即为_HEAP_FREE_LIST类型。
不知大家注意到没有，上面在观察释放后的堆空间时，前8个字节并不是feeefeee，而是有具体的数值。这8个字节就是_HEAP_FREE_ENTRY的FreeList字段的内容。
偏移16Byte后便可观察到释放后的实际数据。
上面的分析过程很繁琐，其实使用windbg的一个命令就可以详细显示堆的各种信息。
该命为!heap addr –hf
下面将上面HeapCreate返回的私有堆的句柄作为!heap的参数。
可以发现上面的很多字段与前面的分析是相同的。
前端分配器
现在是可以介绍前端分配器的时候了。
前面在介绍_HEAP结构的时候时候遇到一个FrontEndHeap字段，该字段指向前端分配器。与前端分配器对应的是后端分配器。
前端分配器维护固定大小的自由列表。当从堆中分配内存时，堆管理器会首先从前端分配器中查找符合条件的堆块。如果失败则会从后端分配器分配。
可以将前端分配器比作一个”快表”，它的存在就是为了加快分配速度。
Windows有两种类型的前端分配器：
旁视列表（LAL）前端分配器和低碎片(LF)前端分配器。它们分别对应两种不同的堆块分配和回收策略。
可以调用HeapQueryInformation来查询堆支持何种前端分配器
BOOL HeapQueryInformation( HANDLE HeapHandle, HEAP_INFORMATION_CLASS HeapInformationClass, PVOID HeapInformation, SIZE_T HeapInformationLength, PSIZE_T ReturnLength);
接下来我们使用下面的语句分别测试下heapTest.exe的私有堆和默认堆是支持何种前端分配器。
int HeapInfo;int err;size_t len = 0;bRetVal = HeapQueryInformation(hHeap, HeapCompatibilityInformation, &HeapInfo, sizeof(HeapInfo),NULL);if(bRetVal){ std::cout<<"HeapInfo = "<<HeapInfo<<std::endl;}bRetVal = HeapQueryInformation(GetProcessHeap(), HeapCompatibilityInformation, &HeapInfo,sizeof(HeapInfo), NULL);if(bRetVal){ std::cout<<"HeapInfo = "<<HeapInfo<<std::endl;}
在XP下运行得到：
在win7下运行得到：
查询msdn可以知道：
私有堆默认为标准堆，不支持旁视列表。
默认进程堆在xp下默认开启旁视列表前端分配器，在win7下默认开启低碎片前端分配器。
HeapSetInformation用于设置堆的属性
BOOL HeapSetInformation( HANDLE HeapHandle, HEAP_INFORMATION_CLASS HeapInformationClass, PVOID HeapInformation, SIZE_T HeapInformationLength);
通过该函数我们可以设置指定堆支持何种前端分配器。
旁视列表前端分配器和低碎片前端分配器
旁视列表是一张表，包含128个项，每一项对应一个单项链表。每个单向链表中都包含一组固定大小的空闲堆块。从16Byte开始递增。由于每个堆块都有_HEAP_ENTRY结构描述，为8Byte。如果应用程序请求24字节的空间，前端分配器将查找大小为32字节的空闲堆块。由于每个链表的空闲块从16字节开始递增，每个堆块需要8字节的管理结构，因此最小可以返回给应用程序的空间为16 – 8 = 8Byte。
旁视列表没有使用索引为0的项，堆块大小为16的链表的索引为1。每个索引表示一组空闲的堆块，堆块的大小是前一个索引中堆块的大小加8字节。最后一个索引为127，包含大于1024字节的空闲堆块。
当程序释放一块内存时堆管理器会将该块内存标记为空闲，根据该块的大小并放入到相应索引指向的链表中旁视列表中。当下一个请求内存空间时，堆管理器会先从前端分配器检查是否存在满足条件的堆块，如果存在则将此堆块返回给应用程序。否则将请求转发到后端分配器。
低碎片前端分配器
顾名思义，低碎片前端分配器在使用过程中不会产生大量的堆碎片。它将可用空间分为128个桶位，编号1-128。每个桶位大小依次递增：第一个桶位大小8byte，128号桶位16384byte。当需要从低碎片前端分配器上分配器空间时，堆管理器会将满足要求的最小的桶分配出去。
如果应用请求7个字节，则将第一号桶分配出去。如果1号桶已经被分配出去则分配2号桶，依次递推。低碎片前端分配器为不同区域设置了不同的分配粒度。如1-32号桶的分配粒度为8byte，这意味着这些桶的分配粒度为8，不足8byte的分配也会被分配给8byte。
下图列出了各个桶的分配粒度。
后端分配器
后端分配器包含一个空闲列表数组。数组中的每一项是一个空闲链表。该数组共有128项，也就说包含128个空闲链表。与旁视列表类似，每个项也都包含了固定大小的堆块。每个空闲链表中的堆块大小都比前一个空闲链表的堆块长度多8个字节。每个空闲链表的元素类型为_HEAP_FREE_ENTRY结构，该结构为16字节。索引为1的数组项没有使用。因为堆块的最小值为16字节。索引为0 的空闲链表包含的空闲块的大小最小为1016，一直到0x7fff0字节。
对于大于0x7fff0的内存分配请求将转发到虚拟分配链表中。如果虚拟分配链表中存在则分配，否则直接从内存管理器中分配，并添加到虚拟分配链表中。
为了提高搜索效率，每个链表中的项是按堆块大小升序排列。
如果堆管理器无法找到一个堆块满足请求的大小，堆管理器将进行块分割。首先堆管理器会找大一块比请求空间更大的块，然后将其对半分割成两个相同大小的堆块以满足分配请求。如果对半分割后满足分配请求，堆管理器会将其中一块标记为占用状态并返回给应用程序。将另一个堆块放入到与该堆块大小相等的空闲链表中。
在释放时堆管理器会判断这个堆块的左右是否有相邻的堆块也是空闲的。如果有则将它们合并成为一个更大的堆块，从当前空闲链表将它们移除并加入到长度等于新堆块长度的空闲链表中。堆块合并的开销是很大的，但是它能够避免所谓的堆碎片。堆合并将小的空闲的堆块合并成大的堆块，避免由于堆中大量存在小的堆块，而无法分配更大的堆块的情况。
内存分配步骤：
1：堆管理器查看前端分配器是否存在满足条件的堆块。如果存在将返回给调用者。否则进入步骤2。
2：堆管理器继续查看后端分配器。
a：如果找到刚好合适的堆块，将此堆块标记为占用状态从空闲链表移除并返还给调用者。
b：如果没有找到，堆管理器将会将更大的堆块分割为两个更小的堆块。将其中一块标记为占用状态并从空闲链表移除。另一块则添加到新的空闲链表中。最初的大堆块将从空闲链表中移除。
3：如果空闲列表不能满足要求，堆管理器将会提交更多的内存，并将该块内存返回给调用者。
内存释放过程
1：首先检查前端分配器能否处理该空闲块。如果前端分配器没有处理，则交由后端分配器。
2：堆管理器判断该空闲块的左右是否存在空闲堆块，如存在会将这些空闲堆块合并成更大的堆块，合并步骤如下：
a：将相邻的空闲块从空闲链表移除。
b：将新的大堆快添加到空闲列表。
c：将新的大堆快设置为空闲。
3：如果不能进行合并操作，该空闲块将被移入空闲列表。
虽然某些堆块没有被应用程序使用，但是在后端分配器看来这些堆块仍然是占用状态。这是因为所有在前端分配器中的堆块，在后端分配器的眼里均为占用状态。
到此对win32堆的内部结构讨论完毕。
如有纰漏，请指正！谢谢！
2013.10.13于浙江杭州