6.4 堆的详细实现

下面我们对当前版本Hello China的堆的详细实现进行描述。在当前的实现中，对于堆的管理是通过一个堆管理器（Heap Manager）进行的，堆管理器提供五个接口函数：创建堆函数（CreateHeap）、销毁堆函数（DestroyHeap）、销毁所有堆函数（DestroyAllHeap）、堆内存分配函数（HeapAlloc）和堆内存释放函数（HeapFree）。

6.4.1 堆的创建

堆的创建过程比较简单，主要过程如下

① 分配一块虚拟区域，虚拟区域的大小根据用户提供的参数dwInitSize来决定，如果dwInitSize大于预定义的DEFAULT_VIRTUAL_AREA_SIZE（当前定义为16KB），则按照dwInitSize申请内存，否则按照DEFAULT_VIRTUAL_AREA_SIZE来申请内存；

② 创建一个虚拟区域头节点，来管理刚刚申请的虚拟区域对象；

③ 申请核心内存（KMemAlloc），创建一个堆对象；

④ 把虚拟区域节点插入堆的虚拟区域链表；

⑤ 把申请的虚拟区域，作为第一块空闲内存块，插入空闲链表；

⑥ 然后把上述初始化完成的堆对象插入当前线程的堆对象链表；

⑦ 如果上述所有操作成功，则返回堆的起始地址，否则返回NULL，指示失败。

代码如下所示，为了方便，我们分段解释。

static __HEAP_OBJECT＊ CreateHeap(DWORD dwInitSize)
{
    __HEAP_OBJECT＊            lpHeapObject =NULL;
    __HEAP_OBJECT＊            lpHeapRoot  =NULL;
    __VIRTUAL_AREA_NODE＊       lpVirtualArea=NULL;
    __FREE_BLOCK_HEADER＊       lpFreeHeader =NULL;
    LPVOID                   lpVirtualAddr=NULL;
    BOOL                     bResult     =FALSE;
    DWORD                    dwFlags     =0;
    if(dwInitSize > MAX_VIRTUAL_AREA_SIZE)  //Requested size too big.
        return NULL;
    if(dwInitSize < DEFAULT_VIRTUAL_AREA_SIZE)
        dwInitSize=DEFAULT_VIRTUAL_AREA_SIZE;
    //
    //Now,allocate the virtual area.
    //
    lpVirtualAddr=GET_VIRTUAL_AREA(dwInitSize);
    if(NULL==lpVirtualAddr)   //Can not get virtual area.
        goto __TERMINAL;
    lpFreeHeader=(__FREE_BLOCK_HEADER＊)lpVirtualAddr;
    lpFreeHeader->dwFlags  =BLOCK_FLAGS_FREE;
    lpFreeHeader->dwBlockSize=dwInitSize-sizeof(__FREE_BLOCK_
HEADER); //Caution!!!

上述代码调用VirtualAllo（c GET_VIRTUAL_AREA实际上是VirtualAlloc的宏定义），申请一块虚拟区域，该虚拟区域的大小是dwInitSize和DEFAULT_VIRTUAL_AREA_SIZE中最大者，然后把申请的虚拟区域看做是一块空闲内存块，并初始化其头部。需要注意的是，这块空闲块的大小是虚拟区域的大小减去空闲块控制头的大小（16字节），因为要考虑空闲块控制头所占用的大小。

//
//Now,create a virtual area node object,to manage virtual area.
//
lpVirtualArea=(__VIRTUAL_AREA_NODE＊)GET_KERNEL_MEMORY(
    sizeof(__VIRTUAL_AREA_NODE));
if(NULL==lpVirtualArea)  //Can not get memory.
    goto __TERMINAL;
lpVirtualArea->lpStartAddress=lpVirtualAddr;
lpVirtualArea->dwAreaSize  =dwInitSize;
lpVirtualArea->lpNext      =NULL;

上述代码创建了一个虚拟区域节点对象，这个节点对象的唯一用途就是把虚拟区域连接到堆的虚拟区域链表中。

lpHeapObject=(__HEAP_OBJECT＊)GET_KERNEL_MEMORY(sizeof(__HEAP_OBJECT));
if(NULL==lpHeapObject)  //Can not allocate memory.
    goto __TERMINAL;
lpHeapObject->lpVirtualArea           =lpVirtualArea;
                                      //Virtual area node list.
lpHeapObject->FreeBlockHeader.dwFlags    |=BLOCK_FLAGS_FREE;
lpHeapObject->FreeBlockHeader.dwFlags    &=～BLOCK_FLAGS_USED;
lpHeapObject->FreeBlockHeader.dwBlockSize=0;
lpHeapObject->lpPrev                     =lpHeapObject;
                                          //Pointing to itself.
lpHeapObject->lpNext                      =lpHeapObject;
                                          //Pointing to itself.
//__ENTER_CRITICAL_SECTION(NULL,dwFlags);  //Critical section here.
lpHeapObject->lpKernelThread     =CURRENT_KERNEL_THREAD;
lpHeapRoot=(__HEAP_OBJECT＊)CURRENT_KERNEL_THREAD->lpHeapObject;
if(NULL==lpHeapRoot)  //Has not any heap yet.
{
    CURRENT_KERNEL_THREAD->lpHeapObject=(LPVOID)lpHeapObject;
}
else  //Has at least one heap object,so insert it into the list.
{
    lpHeapObject->lpPrev=lpHeapRoot->lpPrev;
    lpHeapObject->lpNext=lpHeapRoot;
    lpHeapObject->lpNext->lpPrev=lpHeapObject;
    lpHeapObject->lpPrev->lpNext=lpHeapObject;
}
//__LEAVE_CRITICAL_SECTION(NULL,dwFlags);

上述代码创建了一个堆对象（__HEAP_OBJECT），并把该堆对象初始化。其中，FreeBlockHeader是空闲链表的头节点，这个头节点仅仅是用来完成空闲块的连接，不代表任何空闲块，因此其尺寸设置为0。完成堆对象的创建并初始化后，把创建的堆对象插入当前线程的堆链表。需要注意的是，由于堆是基于线程创建的，不存在与其他线程竞争资源的情况，而且当前线程对象的堆链表也不会被中断处理程序修改，因此上述代码无须保护。

下面的代码把申请的虚拟区域加入了当前堆的虚拟区域列表，然后返回创建的堆的基地址。当然，如果上述处理中发生错误，则会导致该函数失败，在这种情况下，函数返回前，需要撤销已经申请的资源。这种采用事务式的处理方式在Hello China的实现中非常常见。

//
//Now,add the virtual area into the heap object's free list.
//
lpFreeHeader->lpPrev=&(lpHeapObject->FreeBlockHeader);
lpFreeHeader->lpNext=&(lpHeapObject->FreeBlockHeader);
lpHeapObject->FreeBlockHeader.lpPrev   =lpFreeHeader;
lpHeapObject->FreeBlockHeader.lpNext   =lpFreeHeader;
bResult=TRUE;   //The whole operation is successful.
__TERMINAL:
if(!bResult)   //Failed.
{
    if(lpVirtualAddr)  //Should release it.
        RELEASE_VIRTUAL_AREA(lpVirtualAddr);
    if(lpHeapObject)
        RELEASE_KERNEL_MEMORY((LPVOID)lpHeapObject);
    if(lpVirtualArea)
        RELEASE_KERNEL_MEMORY((LPVOID)lpVirtualArea);
    lpHeapObject=NULL;  //Should return a NULL flags.
}
return lpHeapObject;
}