6.4.3 堆内存申请

HeapAlloc函数完成堆内存的申请，该函数接受两个参数，目标堆对象和待申请内存的大小。若申请成功，则返回成功申请的内存基地址，否则返回NULL。该函数完成如下动作。

① 首先，做一个堆归属的合法性检查，即判断用户提供的堆对象是不是属于当前线程。若属于当前线程，则继续下一步的动作，否则直接返回NULL。

② 检查空闲链表，以寻找一块大小大于用户请求的空闲内存块。

③ 如果能够找到这样的内存块，则根据内存块的大小，确定是需要进一步拆分，还是直接返回用户。

④ 如果需要拆分，则把找到的内存块拆分成两块，然后把拆分后的两块内存块中的后一块，重新插入空闲链表，把第一块返回用户。若不需要拆分，则把找到的空闲块直接从空闲链表中删除，然后返回用户。

⑤ 如果从空闲链表中无法找到满足要求的空闲块，则调用VirtualAlloc函数，重新分配一个虚拟区域，并把该区域当成一块空闲块进行上述处理。

⑥ 返回用户分配的内存块地址，或者在失败的情况下返回NULL。

代码如下。

static LPVOID HeapAlloc(__HEAP_OBJECT＊ lpHeapObject,DWORD dwSize)
{
    __VIRTUAL_AREA_NODE＊           lpVirtualArea =NULL;
    __FREE_BLOCK_HEADER＊           lpFreeBlock  =NULL;
    __FREE_BLOCK_HEADER＊           lpTmpHeader  =NULL;
    LPVOID                       lpResult     =NULL;
    DWORD                        dwFlags      =0L;
    DWORD                        dwFindSize   =0L;
    if((NULL==lpHeapObject) || (0==dwSize)) //Parameter check.
        return lpResult;
    //__ENTER_CRITICAL_SECTION(NULL,dwFlags);
    if(lpHeapObject->lpKernelThread !=CURRENT_KERNEL_THREAD)
                                            //Check the heap's owner.
    {
        __LEAVE_CRITICAL_SECTION(NULL,dwFlags);
        return lpResult;
    }
    //__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
    if(dwSize < MIN_BLOCK_SIZE)
        dwSize=MIN_BLOCK_SIZE;
    dwFindSize=dwSize+MIN_BLOCK_SIZE+sizeof(__FREE_BLOCK_HEADER);

上述代码完成了堆归属检查，并重新计算了用户所申请的内存块的大小。在当前的实现中，对于堆内存的申请最小尺寸是MIN_BLOCK_SIZE（定义为16字节），若用户请求的内存小于该数值，则调整为该数值。其中，dwFindSize是待查找的目标空闲块的大小。只所以在dwSize的基础上增加MIN_BLOCK_SIZE和控制头的尺寸，是为了确保任何空闲块的可用尺寸都应该大于MIN_BLOCK_SIZE。在找到一块空闲块之后，若该空闲块的大小大于dwFindSize，则需要对该空闲块进行分割，否则无需分割，直接返回给用户。

//
//Now,check the free list,try to find a free block.
//
lpFreeBlock=lpHeapObject->FreeBlockHeader.lpNext;
    while(lpFreeBlock !=&lpHeapObject->FreeBlockHeader)
    {
    if(lpFreeBlock->dwBlockSize >=dwSize)  //Find one.
    {
        if(lpFreeBlock->dwBlockSize >=dwFindSize)  //Should split it
                                            //into two free blocks.
        {
            lpTmpHeader=(__FREE_BLOCK_HEADER＊)((DWORD)lpFreeBlock+
                        dwSize
           +sizeof(__FREE_BLOCK_HEADER));    //Pointing to
                                            //second part.
            lpTmpHeader->dwFlags  =BLOCK_FLAGS_FREE;
            lpTmpHeader->dwBlockSize=lpFreeBlock->dwBlockSize-
                                      dwSize
           -sizeof(__FREE_BLOCK_HEADER);
            //Calculate second part's size.
            //
            //Now,should replace the lpFreeBlock with lpTmpHeader.
            //
            lpTmpHeader->lpNext=lpFreeBlock->lpNext;
            lpTmpHeader->lpPrev=lpFreeBlock->lpPrev;
            lpTmpHeader->lpNext->lpPrev=lpTmpHeader;
            lpTmpHeader->lpPrev->lpNext=lpTmpHeader;
            lpFreeBlock->dwBlockSize=dwSize;
            lpFreeBlock->dwFlags    |=BLOCK_FLAGS_USED;
            lpFreeBlock->dwFlags    &=～BLOCK_FLAGS_FREE;
            //Clear the free flags.
            lpFreeBlock->lpPrev   =NULL;
            lpFreeBlock->lpNext   =NULL;
            lpResult             =(LPVOID)((DWORD)lpFreeBlock
           +sizeof(__FREE_BLOCK_HEADER));
            goto __TERMINAL;
        }
        else  //Now need to split,return the block is OK.
        {
            //
            //Delete the free block from free block list.
            //
            lpFreeBlock->lpNext->lpPrev=lpFreeBlock->lpPrev;
            lpFreeBlock->lpPrev->lpNext=lpFreeBlock->lpNext;
            lpFreeBlock->dwFlags       |=BLOCK_FLAGS_USED;
            lpFreeBlock->dwFlags              &=～BLOCK_FLAGS_FREE;
//Clear free bit.
            lpFreeBlock->lpNext      =NULL;
            lpFreeBlock->lpPrev      =NULL;
            lpResult=(LPVOID)((DWORD)lpFreeBlock+sizeof(__FREE_
BLOCK_HEADER));
            goto __TERMINAL;
        }
    }
    lpFreeBlock=lpFreeBlock->lpNext;  //Check the next block.
}
if(lpResult)   //Have found a block.
    goto __TERMINAL;

上述代码完成空闲块链表的搜索，一旦找到一块满足要求尺寸（dwSize）的空闲块，则进一步判断该空闲块的大小是否大于dwFindSize。若大于，则可以进行进一步拆分，否则直接返回用户找到的内存块。在拆分的情况下，把拆分后的第二块内存重新插入空闲链表。

这时候，就可以很清楚地解释为什么只有在大于dwFindSize的时候才需要拆分了。因为在拆分后，实际上还需要在空闲块的开头预留16字节（空闲控制头的大小）作为空闲块的控制头，这样若找到的空闲块小于dwFindSize，则无法保证拆分后空闲块的大小会大于MIN_BLOCK_SIZE（这是空闲块的最小尺寸）。

如果从空闲链表中无法找到满足的空闲块，则需要扩充堆的内存池了，这时候，需要调用VirtualAlloc函数，从系统空间中重新申请一个虚拟区域，然后把该虚拟区域当作一个空闲块对待，插入堆的空闲链表，这时候，还需要把虚拟区域插入堆的虚拟区域链表。代码如下。

//
//If can not find a statisfying block in above process,we should allocate
//a new virtual area according to dwSize,insert the virtual area into
//free list,then repeat above process.
//
lpVirtualArea=(__VIRTUAL_AREA_NODE＊)GET_ KERNEL_MEMORY(sizeof(__
VIRTUAL_AREA_NODE));
if(NULL==lpVirtualArea)  //Can not allocate kernel memory.
    goto __TERMINAL;
lpVirtualArea->dwAreaSize =((dwSize+sizeof(__FREE_BLOCK_HEADER))
    > DEFAULT_VIRTUAL_AREA_SIZE) ?
    (dwSize+sizeof(__FREE_BLOCK_HEADER)) : DEFAULT_VIRTUAL_ AREA_ SIZE;
    lpVirtualArea->lpStartAddress=GET_VIRTUAL_ AREA(lpVirtualArea->
                                dwAreaSize);
    if(NULL==lpVirtualArea->lpStartAddress)  //Can not get virtual area.
    {
    RELEASE_KERNEL_MEMORY((LPVOID)lpVirtualArea);
    goto __TERMINAL;
    }
    //
    //Insert the virtual area node object into virtual area list
    //of current heap object.
    //
    lpVirtualArea->lpNext    =lpHeapObject->lpVirtualArea;
    lpHeapObject->lpVirtualArea=lpVirtualArea;
    //
    //Now,insert the free block(virtual area) into free list of the
    //heap object.
    //
    lpTmpHeader=(__FREE_BLOCK_HEADER＊)lpVirtualArea->lpStartAddress;
    lpTmpHeader->dwFlags |=BLOCK_FLAGS_FREE;
    lpTmpHeader->dwFlags &=～BLOCK_FLAGS_USED;  //Clear the used flags.
    lpTmpHeader->dwBlockSize=lpVirtualArea->dwAreaSize-sizeof(__FREE_
                          BLOCK_HEADER);
    lpTmpHeader->lpNext=lpHeapObject->FreeBlockHeader.lpNext;
    lpTmpHeader->lpPrev=&lpHeapObject->FreeBlockHeader;
    lpTmpHeader->lpNext->lpPrev=lpTmpHeader;
    lpTmpHeader->lpPrev->lpNext=lpTmpHeader;

若调用VirtualAlloc函数也失败，则HeapAlloc函数只能返回NULL了，否则，在成功调用VirtualAlloc函数的情况下，堆的空闲链表中会增加一块满足要求的内存空闲块（新申请的虚拟区域），这时候，重新调用HeapAlloc函数，肯定是成功的，因此，HeapAlloc函数递归调用自己，然后把返回的结果返回给用户。

    //
    //Now,call HeapAlloc again,this time must successful.
    //
    lpResult=HeapAlloc(lpHeapObject,dwSize);
    __TERMINAL:
    return lpResult;
    }