堆（heap）是一种内存管理器，程序可以通过堆来动态地分配和释放内存。通常，需要使用堆的情况包括，当无法预先知道所需的内存大小或者所需内存过大而无法在栈中进行分配。操作系统提供一套API把复杂的堆管理机制屏蔽掉。下面是一些与堆相关的API
Function Description
GetProcessHeap Obtains a handle to the heap of the calling process.
GetProcessHeaps Obtains handles to all of the heaps that are valid for the calling process. HeapAlloc Allocates a block of memory from a heap.
HeapCompact Coalesces adjacent free blocks of memory on a heap.
HeapCreate Creates a heap object.
HeapDestroy Destroys the specified heap object.
HeapFree Frees a memory block allocated from a heap.
HeapLock Attempts to acquire the lock associated with a specified heap. HeapQueryInformation Retrieves information about the specified heap.
HeapReAlloc Reallocates a block of memory from a heap.
HeapSetInformation Sets heap information for the specified heap.
HeapSize Retrieves the size of a memory block allocated from a heap. HeapUnlock Releas ownership of the lock associated with a specified heap. HeapValidate Attempts to validate a specified heap.
HeapWalk Enumerates the memory blocks in a specified heap.
Windows堆的数据结构
1.前端分配器（Front End Allocator）
是对的一个抽象优化层。在程序中可以选择不同类型的前端分配器来满足不同的内存需求。例如，如果在程序中存在一些密集的内存分配操作，那么就可以使用低碎片的前端分配器来避免产生内存碎片。在windows中有两种前端分配器：
·（Look Aside List, LAL）前端分配器
·（Low Fragmentation, LF）前端分配器
除windows vista外，所有版本的windows在默认情况下都使用LAL前端分配器，windows vista默认情况下使用LF前端分配器。
旁视列表是一张表，包含128项，每一项对应于一个单向链表。每个单向链表都包含了一组固定大小的空闲，堆块的大小从16字节开始随索引递增依次增加8个字节。最后一个索引（127）包含了大小为1024字节的空闲堆块。每个堆块包含了8个字节的用于管理这个堆块。返回给调用者的最小堆块是16字节。这样，旁视列表前端分配器没有使用索引为0的项，因为这个项对应于大小为8个字节的空闲堆块。
2.后端分配器（Back End Allocator）
如果前端分配器无法满足分配请求，那么这个请求将会被转发到后端分配器。后端分配器是一张（Free Lists），表中的每一项是一个双向的表头。空闲列表记录了堆中的所有空闲堆块。空闲列表包含128个空闲链表，每个链表中包含了固定大小的空闲堆块。空闲列表[1]没有被使用。空闲列表[2]中的堆块大小是16字节，空闲列表[3]中的堆块大小是24字节，等等。每个空闲链表中的堆块都比前一个空闲链表中的堆块多8个字节。空闲列表[127]中的堆块大小是1016字节。如果空闲堆块的大小大于1016字节，那么将会被放入到索引为0个空闲链表中。在空闲列表[0]中的堆块将大于等于1024字节而小于512K字节(虚拟分配的限值)，并且按照堆块的大小来排序（升序）以获得最大的效率。
为了将查找空闲堆块的效率最大化，将维持一个。位图中包含了128位，每一位表示空闲列表中的一个索引的状态。如果某一位被设置了，那么表示在空闲列表这个索引的空闲链表中包含了空闲的堆块，否则，该空闲链表为空。
3.堆段（Heap Segment）
sole是堆管理器从请求分配的内存块。首先，堆管理器通过虚拟内存管理器来分配堆段，然后，堆段被分为不同大小的块以满足程序的内存分配请求。在堆段最初被创建时，堆段中的大部分虚拟内存都是被保留的（Rerve），只有一小部分被提交（Commit）。当堆管理器耗尽了已提交的空间时，堆段将进一步提交更多的内存，而堆管理器接着对新提交的空间进行分割。
当一个堆段耗尽了所有的空间后，堆管理器将创建另一个新的堆段，并且新堆段的大小将是之前堆段大小的两倍。如果由于内存不足而无法创建这个新堆段，那么堆管理器将把这个大小减半。如果再次失败，那么将继续减半，直到堆段大小的最小阈值——在这种情况下，堆管理器将返回一个错误给用户。在堆中最多可以同时存在64个堆段。在新的堆段被创建后，堆管理器将把它添加到一个数组中，在此数组中将记录堆使用的所有堆段。
堆管理器是否会释放某个堆段中的内存？答案是堆管理器将根据需要取消内存提交（Decommit），但从来不释放它，也就是说，内存将始终被保留。
4.虚拟分配链表（Virtual Allocation List）
所以大于等于512K字节的内存分配请求都会转发到。堆管理器将向虚拟内存管理器发出请求，并将相应的内存分配信息保存到虚拟分配链表中。
5.windows堆的具体数据结构（windows xp sp3）
调用CreateHeap返回的堆句柄实际就是堆的基地址。堆的开始部分是_HEAP结构。
0:000> dt _heap
ntdll!_HEAP
+0x000 Entry : _HEAP_ENTRY
翻译繁体字+0x008 Signature : Uint4B
+0x00c Flags : Uint4B
+0x010 ForceFlags : Uint4B
+0x014 VirtualMemoryThreshold : Uint4B
+0x018 SegmentRerve : Uint4B
+0x01c SegmentCommit : Uint4B
+0x020 DeCommitFreeBlockThreshold : Uint4B
+0x024 DeCommitTotalFreeThreshold : Uint4B
+0x028 TotalFreeSize : Uint4B
+0x02c MaximumAllocationSize : Uint4B
+0x030 ProcessHeapsListIndex : Uint2B
+0x032 HeaderValidateLength : Uint2B
+0x034 HeaderValidateCopy : Ptr32 V oid
+0x038 NextAvailableTagIndex : Uint2B
thegraduate
+0x03a MaximumTagIndex : Uint2B
+0x03c TagEntries : Ptr32 _HEAP_TAG_ENTRY
+0x040 UCRSegments : Ptr32 _HEAP_UCR_SEGMENT
+0x044 UnudUnCommittedRanges : Ptr32 _HEAP_UNCOMMMTTED_RANGE
+0x048 AlignRound : Uint4B
+0x04c AlignMask : Uint4B
+0x050 VirtualAllocdBlocks : _LIST_ENTRY // 虚拟分配链表
+0x058 Segments : [64] Ptr32 _HEAP_SEGMENT // 堆段指针数组
+0x158 u : __unnamed // 空闲列表位图（128 bit）+0x168 u2 : __unnamedleisuretime
+0x16a AllocatorBackTraceIndex : Uint2B
+0x16c NonDedicatedListLength : Uint4B
+0x170 LargeBlocksIndex : Ptr32 V oid
hsort
+0x174 PudoTagEntries : Ptr32 _HEAP_PSEUDO_TAG_ENTRY
+0x178 FreeLists : [128] _LIST_ENTRY // 空闲列表
+0x578 LockVariable : Ptr32 _HEAP_LOCK
+0x57c CommitRoutine : Ptr32 long
+0x580 FrontEndHeap : Ptr32 Void // 指向前端分配器的指针
+0x584 FrontHeapLockCount : Uint2B
+0x586 FrontEndHeapType : UChar
+0x587 LastSegmentIndex : UChar
堆块的块首是_HEAP_ENTRY结构。
0:000> dt _HEAP_ENTRY
itouch游戏
ntdll!_HEAP_ENTRY
+0x000 Size : Uint2B // 堆块的大小（以堆粒度为单位，含块首）+0x002 PreviousSize : Uint2B // 前一堆块的大小（以堆粒度为单位，含块首） +0x000 SubSegmentCode : Ptr32 V oid
+0x004 SmallTagIndex : UChar
+0x005 Flags : UChar // 表示堆块的状态
+0x006 UnudBytes : UChar // 堆块中未被用户使用的字节数（含块首）
+0x007 SegmentIndex : UChar // 堆块所在堆段的索引
Flages所代表的堆块状态
0x01 堆块正在被程序或者堆管理器使用
0x04 堆块使用了填充模式（File Pattern）
0x08 堆块是直接从虚拟内存管理器中分配而来的
0x10 堆块是未提交范围之前的最后一个堆块
0:000> dt nt!_HEAP_SEGMENT
ntdll!_HEAP_SEGMENT
+0x000 Entry : _HEAP_ENTRY
+0x008 Signature : Uint4B
+0x00c Flags : Uint4B
+0x010 Heap : Ptr32 _HEAP
+0x014 LargestUnCommittedRange : Uint4B
+0x018 BaAddress : Ptr32 V oid
+0x01c NumberOfPages : Uint4B
+0x020 FirstEntry : Ptr32 _HEAP_ENTRY // 指向堆段中的第一个堆块
+0x024 LastValidEntry : Ptr32 _HEAP_ENTRY
+0x028 NumberOfUnCommittedPages : Uint4B
+0x02c NumberOfUnCommittedRanges : Uint4B
+0x030 UnCommittedRanges : Ptr32 _HEAP_UNCOMMMTTED_RANGE
+0x034 AllocatorBackTraceIndex : Uint2B
+0x036 Rerved : Uint2B
+0x038 LastEntryInSegment : Ptr32 _HEAP_ENTRY // 指向堆段中的最后一个堆块6.使用结构_HEAP_SEGMENT遍历堆段
数据结构_HEAP_SEGMENT包含了大量的信息，堆管理器根据这些信息管理堆中所有活跃的堆块。偏移 0x20处的FirstEntry域指向堆段中的第一个堆块。找到堆块一后，根据堆块一的Size域，可以找到堆块二，即堆块一的地址 + 堆块一的字节数 = 堆块二的地址。重复这个过程，那么就可以遍历整个堆段，并且可以进一步分析每一个堆块的正确性。偏移0x38处的LastEntryInSegment域指向堆段中的最后一个堆块。
Windows堆的管理策略
1.堆块分割（Block Splitting）
堆管理器将程序请求分配的字节数向上调整到（Heap Granularity），然后加上8个字节，并且除以8。例如，对于分配4个字节的请求，堆管理器计算出空闲列表位图索引为2。查看空闲列表位图中的第2比特位。如果该比特位被设置，堆管理器将从这个链表中移出一个空闲堆块，并返回给调用者。如果在移出了一个空闲堆块后，空闲链表为空，那么堆管理器将清除空闲列表位图中相应的比特位。如果该比特位没有被设置，那么堆管理器将使用快分割技术。即找到一个比请求大小更大的空闲堆块，然后将其分割以满足分配请求。
清单1 演示堆块分割
#include <windows.h>
int main()
taurus>魅力女性课程{
HLOCAL h1, h2, h3, h4, h5, h6, h7;足球2
hp;
HANDLE
hp = HeapCreate(0, 0x1000, 0x100000);
_asm int 3; //程序出错后调用 just-in-time-debugger
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 48-8);
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16-8);
h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 48-8);
h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16-8);
h5 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 40-8);
h6 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16-8);
HeapFree(hp, 0, h1);
HeapFree(hp, 0, h3);
HeapFree(hp, 0, h5);
h7 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 24-8); //观察这次分配前后堆的变化
HeapFree(hp, 0, h2);
HeapFree(hp, 0, h4);
HeapFree(hp, 0, h6);
HeapFree(hp, 0, h7);
现象用英语怎么说
0;
return
}
请求分配16字节，实际需要分配24字节。而大小为24字节的空闲堆块不存在。于是堆管理器选择一个比请求大小更大的空闲堆块进行分割——将40字节的空闲堆块从空闲链表中移除，分割为24字节的堆块和16字节的堆块。其中，24字节的堆块返回给程序使用（程序获得的指针指向堆块块身），同时将该堆块标志为设置为占用；另外16字节的堆块添加到相应的空闲链表中，同时将该堆块标记为空闲。之后，更新空闲列表位图，以反映在执行块分割操作之后的变化。
