【旧文章搬运】Windows句柄分配算法(二)

原文发表于百度空间，2009-04-04
==========================================================================

在创建句柄时,操作过程并不受StrictFIFO标志的影响.而在销毁句柄时,StrictFIFO标志则决定了如何放置刚释放的这个FreeHandle.
对于普通进程的句柄表而言,StrictFIFO为0,那么销毁该句柄时,Free指针所指向的队列头是HandleTable->FirstFree.此时这个新的FreeHandle被插在了队列的最前面,FirstFree始终是指向该FreeHandleList的头部,而LastFree并没有被使用,它的值从申请句柄表时初始化为0的就再也没有用过.
写段小代码做个实验:

HANDLE hProc;
for (int i=0;i<5;i++)
{
   hProc=OpenProcess(PROCESS_QUERY_INFORMATION,FALSE,4);
   printf("[%d]hProc=0x%X
",i,hProc);
   CloseHandle(hProc);
}

你会发现每次得到的句柄值都是一样的.这和前面的分析结果是一致的,每次我们取走了FreeHandleList队列的第一个FreeHandle,把它放回去时由于StrictFIFO=0,这个FreeHandle又被放在了队列的最前面.所以就导致每次得到的句柄都是它,跟你的对象类型什么的没有任何关系.来看一下该进程的句柄表:

可以看到FirstFree的值为0x7e8,而它的NextFreeTableEntry为0x7F4.
然后把CloseHandle的位置换一换,这样写:

HANDLE hProc2,hProc;
printf("Press Enter to Continue...
");
getchar();
hProc=OpenProcess(PROCESS_QUERY_INFORMATION,FALSE,4);
printf("hProc=0x%X
",hProc);
hProc2=OpenProcess(PROCESS_QUERY_INFORMATION,FALSE,4);
printf("hProc=0x%X
",hProc2);
CloseHandle(hProc);
CloseHandle(hProc2);

可以看到,连续打开两个句柄,系统就从FirstFree队列中连续取了两个FreeHandle~~
系统中唯一一个StrictFIFO=1的句柄表是PspCidTable.设置该标志的影响就是刚释放的FreeHandle没有插入FirstFree这个FreeHandleList,而到插入到以LastFree为队列头的FreeHandleList中去了.这样,在任一确定时刻,PspCidTable必定满足以下条件:
(FirstFree中的FreeHandle个数)+(LastFree中的FreeHandle个数)+(当前句柄表的句柄计数)=当前句柄表的最大句柄数
这个可以实践证明之,后面再细说.
根据这个情况我们也大概知道了,FirstFree队列中存放的是从未使用过的句柄,而LastFree队形中存放的是已经用过但是又释放了的句柄.两个队形中的句柄都是FreeHandle,都可以使用,但是前面我们已经看到申请句柄时只从FirstFree队列中取FreeHandle,那么LastFree队列中的FreeHandle都哪儿去了呢?这就是我们接下来要分析的ExpMoveFreeHandles所完成的工作了.

ULONG
ExpMoveFreeHandles (
     IN PHANDLE_TABLE HandleTable
     )
{
    ULONG OldValue, NewValue;
    ULONG Index, OldIndex, NewIndex, FreeSize;
     PHANDLE_TABLE_ENTRY Entry, FirstEntry;
     EXHANDLE Handle;
    ULONG Idx;
    BOOLEAN StrictFIFO;
    //
    // First remove all the handles from the free list so we can add them to the
    // list we use for allocates.
    //
     OldValue = InterlockedExchange ((PLONG)&HandleTable->LastFree, //先取出LastFree的值,并将其清0
                                     0);
     Index = OldValue;//赋给Index
    if (Index == 0) {//若LastFree=0,说明这是一个非StrictFIFO的句柄表,所有的FreeHandle都在FirstFree队列中,不需要进行操作
        //
        // There are no free handles.   Nothing to do.
        //
        return OldValue;
     }
    //OldValue不为0,说明LastFree队形不为空  
    //
    // We are pushing old entries onto the free list.
    // We have the A-B-A problem here as these items may have been moved here because
    // another thread was using them in the pop code.
    //
    for (Idx = 1; Idx < HANDLE_TABLE_LOCKS; Idx++) {
         ExAcquireReleasePushLockExclusive (&HandleTable->HandleTableLock[Idx]); //完全锁定
     }
     StrictFIFO = HandleTable->StrictFIFO; //取StrictFIFO标志
    //
    // If we are strict FIFO then reverse the list to make handle reuse rare.
    //
    if (!StrictFIFO) {//若StrictFIFO=0
        //
        // We have a complete chain here. If there is no existing chain we
        // can just push this one without any hassles. If we can't then
        // we can just fall into the reversing code anyway as we need
        // to find the end of the chain to continue it.
        //
        //
        // This is a push so create a new sequence number
        //
  //那就直接把FirstFree指向原来LastFree所指向的队列,这样又可以从FirstFree取FreeHandle了
        if (InterlockedCompareExchange ((PLONG)&HandleTable->FirstFree,
                                         OldValue + GetNextSeq(),
                                         0) == 0) {
            return OldValue;//无须更多操作,返回!
         }
     }
    //
    // Loop over all the entries and reverse the chain.
    //
     FreeSize = OldIndex = 0;
     FirstEntry = NULL;
    while (1) {
         FreeSize++; //LastFree队形中的FreeHandle计数
         Handle.Value = Index;
         Entry = ExpLookupHandleTableEntry (HandleTable, Handle);
         EXASSERT (Entry->Object == NULL);
         NewIndex = Entry->NextFreeTableEntry;
         Entry->NextFreeTableEntry = OldIndex;
        if (OldIndex == 0) {OldIndex=0时是第一次循环,把此时的Entry赋给FirstEntry
             FirstEntry = Entry;
         }
         OldIndex = Index;
        if (NewIndex == 0) {
            break;
         }
         Index = NewIndex;
     }//前面已经说过,LastFree指向的也是一个FreeHandleList,也是一个队列.而上面这个循环则把这个队列给反向了,相当于来了一个"向后转".这样,原来的队列尾就变成了队列头.而循环结束时,OldIndex则等于逆转前的队列尾,如今的队列头,一些数据结构知识而已
     NewValue = ExpInterlockedExchange (&HandleTable->FirstFree,
                                        OldIndex,
                                        FirstEntry);//把新的队列头赋值给Handle->FirstFree,新的FreeHandleList就建立起来了
    //
    // If we haven't got a pool of a few handles then force
    // table expansion to keep the free handle size high
    //
    if (FreeSize < 100 && StrictFIFO) {//若在设置了StrictFIFO时FreeHandle过少,那就返回0强制句柄表进行扩容操作
         OldValue = 0;
     }
    return OldValue;
}

这个函数涉及到一些数据结构知识了,总结如下:ExpMoveFreeHandles先检查HandleTable->LastFree是否为0,不为0则进行整理.若没有设置StrictFIFO,就直接设置FirstFree指向队形头,若设置了StrictFIFO,就将队形逆序后再设置FirstFree指向队列头.

综合前面普通进程的句柄表的操作,简单画个示意图:

同一颜色字体的FirstFree和LastFree是相对应的.
StrictFIFO=0(普通进程)的句柄表申请释放均不涉及LastFree,所有操作都在FirstFree队列头部进行,申请句柄时从队列头取走一个,释放时仍放回队列头,LastFree始终是一个空队列.
而StrictFIFO=1的PspCidTable则申请一个句柄就从FirstFree队形头移除一个,每释放一个句柄就在LastFree队列头插入一个.但是当FirstFree队列用完时,ExpMoveFreeHandles则把队列逆向之后又赋给FirstFree,相当于把LastFree队列反向接在了FirstFree队列之后.虽然这个队列的形式和我们通常见到的队列有点不一样,但是它仍然具有队列的特征(FIFO,First In First Out,这可是队列的基本特征),FirstFree指向队列头,LastFree指向队列尾(当然是在设置了StrictFIFO并把队列反转之后),这不是队列是啥?Windows的句柄分配算法是彻底清楚了,那么我们可以写个程序来预测一下:下一个进程的PID(或TID,两者在句柄表级别没有区别)会是多少?
我写个了简单程序,把PspCidTable从FirstFree开始遍历一次,再从LastFree开始遍历一次.然后运行我们的RunIt程序,可以看到,RunIt输出的线程TID(在句柄表这一级,TID和PID是没有区别的)和我们遍历FirstFree输出的结果是多么的一致!
当TID=2040(FirstFree的最后一个FreeHandle)时,此时HandleTable->FirstFree的值为0

根据前面的分析,若要进行申请下一个TID的操作,必定会调用ExpMoveFreeHandles把LastFree队列反转,所以下一个TID就是之前遍历LastFree时的最后一个FreeHandle,值为2036.继续创建线程,继续看(注意两个箭头的方向):

与预期完全一致!而且输出的FirstFreeCnt,LastFreeCnt,HandleCnt,TotalHandle确实满足如下关系:
FirstFreeCnt+LastFreeCnt+HandleCnt=TotalHandle //注意每个句柄表开头有一个无效HANDLE_TABLE_ENTRY占位
Windows句柄分配算法的分析到此结束~~