HeapAllocate（）
wine-1.0 + ReactOS-3.8
这里是对堆函数进行一些分析，阅读代码时最好参考wine源码阅读，可以在www.winehq.org 下载到wine的源码。
ReactOS的源码在www.reactos.org下载。
1 检查
HeapAllocate -> RtlAllocateHeap
HeapAllocate函数是调用RtlAllocateHeap函数。所以我们直接看RtlAllocateHeap函数好啦。
这个函数在dlls/ntdll/heap.c中。
我们先看看这个函数的代码：
HEAP *heapPtr = HEAP_GetPtr( heap );
flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
flags |= heapPtr->flags;
rounded_size = ROUND_SIZE(size);
函数进来，首先通过HEAP_GetPtr()把heap的handle转换成pointer，其实就是一个简单的强制转换：
336 /***********************************************************************
337 * HEAP_GetPtr
338 * RETURNS
339 * Pointer to the heap
340 * NULL: Failure
341 */
342 static HEAP *HEAP_GetPtr(
343 HANDLE heap /* [in] Handle to the heap */
344 ) {
345 HEAP *heapPtr = (HEAP *)heap;
。。。
。。。。
357 return heapPtr;
358 }
得到了指向这个堆的指针后，检查一下flags，关于这个flags的值及其代表的意思，可以参考《Windows核心编程》（参考资料一）。
检查完flags后用宏ROUND_SIZE()来进行一下8字节对齐。
然
后检查一下申请的空间的大小有没有溢出，若是溢出了，并设HEAP_GENERATE_EXCEPTIONS标志位，则转去
RtlRaiseStatus（）函数执行。否则返回NULL。（这里检查溢出的方式我并不是很理解，在ReactOS3.7中这个溢出检查已经去掉了，
不过3.8又加了回来）很明显，这里rtlRaiseStatus( )过去就是一个软中断，引发一个异常。
if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
若没有设置HEAP_NO_SERIALIZE标志，分配的是连续的空间，则进入临界区。为了防止连续空间还没有分配好的时候被截断了。相应的，若进入了临界区在下面这个函数结束前，会退出临界区。
if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
这里RtlEnterCriticalSection和RtlLeaveCriticalSection是一对函数，简单的理解的话把RtlEnterCriticalSection当做上锁，当做RtlLeaveCriticalSection解锁就好了。
2 找一块合适大小的空闲空间 HEAP_FindFreeBlock()
2.1 从空闲队列找块合适的空间
HeapAllocate -> RtlAllocateHeap -> Heap_FindFreeBlock
/* Find a suitable free list, and in it find a block large enough */
继续往下：
if (!(pArena = HEAP_FindFreeBlock( heapPtr, rounded_size, &subheap )))
HEAP_FindFreeBlock():
FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( size + sizeof(ARENA_INUSE) );
首
先在FREE_LIST_ENTRY队列中，找到一个大小不小于申请大小的堆。函数get_freelist_index()把
size+sizeof(ARENA_INUSE)-sizeof（ARENA_FREE）去和HEAP_freeListSizes[]数组比较，看看
应该选择哪个粒度的堆队列，把这个粒度的堆队列的编号 i 返回来，这样pEntry就指向了这个粒度的堆空闲队列。
2.1.1 找到合适的ARENA_FREE和subheap
HeapAllocate -> RtlAllocateHeap -> Heap_FindFreeBlock ->HEAP_FindSubHeap
ptr = &pEntry->arena.entry;
ptr是指向这个队列的连接器（entry成员)的地址的指针
ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
在ARENA_FREE
队列中，每个元素是一个ARENA_FREE结构，每个ARENA_FREE结构都含有同一个成员──struct list entry
把他们串起来，ptr则指向第 N
个ARENA_FREE结构的entry成员，由LIST_ENTRY(ptr，ARENA_FREE，entry)宏得到 pArena 则指向第
N 个ARENA_FREE结构 。
while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
遍
历ARENA_FREE结构链表，若找到某个ARENA_FREE结构的size大于申请的size,则转到HEAP_findSubHeap(
heap, pArena )找出pArena所指向的ARENA_FREE结构被包含在哪个堆里头，找到后返回指向这个子堆的指针subheap。
2.1.2 HEAP_Commit()
Heap Allocate -> R tlAllocateHeap -> Heap_FindFreeBlock ->HEAP_Commit
Windows系统内存需要commit以后才能使用
void *ptr = (char *)(pArena + 1) + data_size + sizeof(ARENA_FREE);
把data_size+sizeof(ARENA_FREE)的大小转化为
[data_size+sizeof(ARENA_FREE)-sizeof(ARENA_INUSE)]+sizeof(ARENA_INUSE)大小。方括号括起来的是新的INUSE的size值。
SIZE_T size = (char *)ptr - (char *)subheap->base;
新的堆的大小
if (size > subheap->size) size = subheap->size;
这个情况因该是不会出现的，前面有检查，这里可能是为了防止某种意外带来的破坏。
如果size的大小小于subheap中已经commit了的内存大小，那么commit新区域成功。不然调用NtAllocateVirualMemory()来commit多出来的内存，完成commit操作。
2.2 若是找不到合适的block，试着把堆增长一下
Heap Allocate -> R tlAllocateHeap -> Heap_FindFreeBlock ->HEAP_CreateSubHeap
/* If no block was found, attempt to grow the heap */
调
用HEAP_CreateSubHeap（）创建一个新的subheap。首先把尺寸大小对齐，base为NULL，所以调用
NtAllocateVirtualMemory（...，MEM_RESERVE，...）分配一块内存，用来创建子堆。注意MEM_RESERVE标
志。后面还需要进行Commit操作。
然后调用HEAP_InitSubHeap（）来对新的subheap进行初始化，成功的话返回新的subheap的地址。
2.2.1 HEAP_InitSubHeap
Heap Allocate -> R tlAllocateHeap -> Heap_FindFreeBlock ->HEAP_CreateSubHeap -> HEAP_InitSubHeap
这
个函数把创建的堆初始化，在这里把前面MEM_RESERVE的内存变为MEM_COMMIT，使内存可用。若创建堆不是第一个subheap，把它初始
化为subheap并挂入subheap_list;若是第一个subheap,将它初始化为一个heap,包括初始化字段，构建空闲队列，初始化临界区
等。
接着调用HEAP_CreateFreeBlock（）创建这个子堆的第一块空闲块。
2.2.2 HEAP_CreateFreeBlock
HeapAllocate
-> RtlAllocateHeap -> Heap_FindFreeBlock ->HEAP_CreateSubHeap
-> HEAP_InitSubHeap -> HEAP_CreateFreeBlock
这里调试信息相关的我忽略掉了，特别有兴趣的可以详细阅读一下。
在这里创建一个ARENA_FREE结构，并且把内容初始化
if (pEnd > (char *)(pFree + 1)) mark_block_free( pFree + 1, pEnd - (char *)(pFree + 1) );
这个语句做的就是这个事情。
接下来检查大小是否达到要求（正常情况下已经得到了申请的大小空间），若是先前的ARENA_FREE不够大，再继续把freeList队列中的下一个ARENA_FREE也划到空闲块里面来，并且把那个（下一个ARENA_FREE）结构移出空闲队列。
然后调用HEAP_InserFreeBlock函数把空闲块放到新的subheap的空闲队列中。
最后调整堆和空闲队列的大小，返回新的空闲队列的地址。
3 HEAP_ShrinkBlock
list_remove( &pArena->entry );
把新申请到的block（pArena）从空闲队列移出，并且调整由ARENA_FREE变为ARENA_INUSE的空间差额。
3.1 HEAP_ShrinkBlock()收缩
HeapAllocate -> RtlAllocateHeap -> Heap_FindFreeBlock -> HEAP_ShrinkBlock
前
面的HEAP_ShrinkBlock函数划了一个或两个ARENA_FREE过来，若划过来的空间不够大，则调用
HEAP_CreateFreeBlock增大申请的空间。然后/* Turn off PREV_FREE flag in next block
*/。
返回到RtlAllocateHeap函数中，记录未使用的空间大小到 pInUse->unused_bytes字段中。然后返回申请到的InUse的起始地址给调用者。
Renference:
《Windows核心编程》第18章
《Heap相关数据结构简介》
viewtopic.php?f=6&t=297&st=0&sk=t&sd=a&start=0
《Windows堆管理》
PS：自己的blog并没有dead，主要龙井是项目开个论坛后，很大的业余精力都往那里放了，所以很少有时间来写东西