原文发表于百度空间，2009-04-04
==========================================================================
分析了Windows句柄表的分配算法之后,综合WRK1.2中的代码以及Window XP下的实践,继续分析句柄的分配算法~~
为了便于描述,先定义几个概念:FreeHandle即尚未被使用的Handle,FreeHandleList是由FreeHandle依靠HandleTableEntry->NextFreeTableEntry组成的一个链表
在分析句柄表的分配算法时,已经注意到系统对每个一级句柄表进行填充,把所有可用句柄串联起来形成一个链表,称之为FreeHandleList,该链表也可以看成是一个FreeHandle队列.而HANDLE_TABLE结构中的FirstFree则始终指向该队列头部.
看下面这个图来回顾一下:
首先分析句柄的创建,对应的函数是ExCreateHandle
NTKERNELAPI
HANDLE //返回值,即创建好的句柄
ExCreateHandle ( __inout PHANDLE_TABLE HandleTable, //句柄表 __in PHANDLE_TABLE_ENTRY HandleTableEntry //HANDLE_TABLE_ENTRY,里面包含了对象信息 );
而ExCreateHandle的主要功能是调用ExpAllocateHandleTableEntry实现的,然后把传进来的对象及属性放入申请到的HANDLE_TABLE_ENTRY里.这很容易理解,创建句柄的过程其实就是把传进来的对象放入目标句柄表中,然后计算出它在句柄表中的索引作为句柄返回就可以了.要放置对象,就必须要有一个有效的HANDLE_TABLE_ENTRY,而申请工作就是由ExpAllocateHandleTableEntry完成的.
PHANDLE_TABLE_ENTRY ExpAllocateHandleTableEntry ( IN PHANDLE_TABLE HandleTable, OUT PEXHANDLE pHandle ) /*++ Routine Description: This routine does a fast allocate of a free handle. It's lock free if possible. Only the rare case of handle table expansion is covered by the handle table lock. Arguments: HandleTable - Supplies the handle table being allocated from. pHandle - Handle returned Return Value: PHANDLE_TABLE_ENTRY - The allocated handle table entry pointer or NULL on failure. --*/ { PKTHREAD CurrentThread; ULONG OldValue, NewValue, NewValue1; PHANDLE_TABLE_ENTRY Entry; EXHANDLE Handle; BOOLEAN RetVal; ULONG Idx; CurrentThread = KeGetCurrentThread (); while (1) {//这是一个循环过程 OldValue = HandleTable->FirstFree; //取当前FirstFree的值,这是FreeHandleList的队列头 while (OldValue == 0) { //判断是否为0.若为0则表示FreeHandleList已经用完了,需要进行一些处理 // // Lock the handle table for exclusive access as we will be // allocating a new table level. // ExpLockHandleTableExclusive (HandleTable, CurrentThread); //锁定句柄表 // // If we have multiple threads trying to expand the table at // the same time then by just acquiring the table lock we // force those threads to complete their allocations and // populate the free list. We must check the free list here // so we don't expand the list twice without needing to. // OldValue = HandleTable->FirstFree; //再取FirstFree的值,这里考虑到多个线程访问同一个句柄表的情况,可能我们这次得到的值不为0.因为在这期间可能已经有线程触发了扩充句柄表的操作 if (OldValue != 0) { //这时如果FirstFree不为0,说明句柄表已经扩充,有FreeHandle了,那就解锁退出循环 ExpUnlockHandleTableExclusive (HandleTable, CurrentThread); break; } //如果仍然没有可用句柄,继续下面的操作 // // See if we have any handles on the alternate free list // These handles need some locking to move them over. // OldValue = ExpMoveFreeHandles (HandleTable);//对句柄表进行整理,至于如何整理稍后分析. if (OldValue != 0) {//若不为0,表明整理之后又有了可用句柄,解锁退出循环,进行真正处理 ExpUnlockHandleTableExclusive (HandleTable, CurrentThread); break; } // // This must be the first thread attempting expansion or all the // free handles allocated by another thread got used up in the gap. // //确实没有可用句柄(句柄表已满)时的处理 RetVal = ExpAllocateHandleTableEntrySlow (HandleTable, TRUE);//扩充句柄表,细节在分析句柄表分配算法时已分析 ExpUnlockHandleTableExclusive (HandleTable, CurrentThread); OldValue = HandleTable->FirstFree;//再取此时的FirstFree的值,如果上面的扩充是成功的,此时应该有可用句柄 // // If ExpAllocateHandleTableEntrySlow had a failed allocation // then we want to fail the call. We check for free entries // before we exit just in case they got allocated or freed by // somebody else in the gap. // if (!RetVal) { //若此if成立则说明ExpAllocateHandleTableEntrySlow在扩充句柄表时操作失败,那就直接返回失败 if (OldValue == 0) { pHandle->GenericHandleOverlay = NULL; return NULL; } } } //OldValue的值来自HandleTable->FirstFree Handle.Value = (OldValue & FREE_HANDLE_MASK); //给新句柄赋值 Entry = ExpLookupHandleTableEntry (HandleTable, Handle); //查找新句柄对应的HANDLE_TABLE_ENTRY,用来放置对象,至此我们有了一个可用的HANDLE_TABLE_ENTRY Idx = ((OldValue & FREE_HANDLE_MASK)>>2) % HANDLE_TABLE_LOCKS; ExpLockHandleTableShared (HandleTable, CurrentThread, Idx); //锁定句柄表 if (OldValue != *(volatile ULONG *) &HandleTable->FirstFree) { //再比较一下,若两者不相等,则可能又有线程在此期间进行了句柄申请或释放操作,为避免出错,下一次循环再试 ExpUnlockHandleTableShared (HandleTable, CurrentThread, Idx); continue; } KeMemoryBarrier (); NewValue = *(volatile ULONG *) &Entry->NextFreeTableEntry; //取新申请到的HANDLE_TABLE_ENTRY中的NextFreeTableEntry.也就是当前申请到的Handle所指向的下一个FreeHandle NewValue1 = InterlockedCompareExchange ((PLONG)&HandleTable->FirstFree, NewValue, OldValue);//修改HandleTable->FirstFree的值为下一个FreeHandle,由前面的操作可知,相当于从FirstFree所指向的FreeHandleList队列头部取走了一个FreeHandle,并且把FirstFree指向新的头部 ExpUnlockHandleTableShared (HandleTable, CurrentThread, Idx); //解锁 if (NewValue1 == OldValue) {//NewValue存放的是原来的FirstFree EXASSERT ((NewValue & FREE_HANDLE_MASK) < HandleTable->NextHandleNeedingPool); break; } else { // // We should have eliminated the A-B-A problem so if only the sequence number has // changed we are broken. // EXASSERT ((NewValue1 & FREE_HANDLE_MASK) != (OldValue & FREE_HANDLE_MASK)); } } InterlockedIncrement (&HandleTable->HandleCount); //当前句柄表的计数增加一 *pHandle = Handle; //把当前新句柄返回 return Entry; }
现在对句柄的分配应该有了一个大致的了解.每次分配句柄时总是从FreeHandleList队列头取走第一个FreeHandle,依次类推
再来看句柄销毁的过程:
句柄的销毁由ExDestroyHandle来完成.
NTKERNELAPI
BOOLEAN
ExDestroyHandle (
__inout PHANDLE_TABLE HandleTable,
__in HANDLE Handle,
__inout_opt PHANDLE_TABLE_ENTRY HandleTableEntry
);
该函数的内部关键操作如下:
HandleTableEntry = ExpLookupHandleTableEntry( HandleTable, LocalHandle ); //根据传入句柄找到对应的HANDLE_TABLE_ENTRY Object = InterlockedExchangePointer (&HandleTableEntry->Object, NULL);//把Object清零 ExpFreeHandleTableEntry( HandleTable, LocalHandle, HandleTableEntry ); //在指定的句柄表中释放指定的Handle对应的HANDLE_TABLE_ENTRY 这里的释放并不是释放空间的意思,而是使该HANDLE_TABLE_ENTRY重新变得可用,下面重点分析ExpFreeHandleTableEntry. VOID ExpFreeHandleTableEntry ( IN PHANDLE_TABLE HandleTable, IN EXHANDLE Handle, IN PHANDLE_TABLE_ENTRY HandleTableEntry ) /*++ Routine Description: This worker routine returns the specified handle table entry to the free list for the handle table. Note: The caller must have already locked the handle table Arguments: HandleTable - Supplies the parent handle table being modified Handle - Supplies the handle of the entry being freed HandleTableEntry - Supplies the table entry being freed Return Value: None. --*/ { PHANDLE_TABLE_ENTRY_INFO EntryInfo; ULONG OldFree, NewFree, *Free; PKTHREAD CurrentThread; ULONG Idx; ULONG SeqInc; PAGED_CODE(); //一些断言和检测 EXASSERT (HandleTableEntry->Object == NULL); EXASSERT (HandleTableEntry == ExpLookupHandleTableEntry (HandleTable, Handle)); // // Clear the AuditMask flags if these are present into the table // EntryInfo = ExGetHandleInfo(HandleTable, Handle.GenericHandleOverlay, TRUE); if (EntryInfo) { EntryInfo->AuditMask = 0; } // // A free is simply a push onto the free table entry stack, or in the // debug case we'll sometimes just float the entry to catch apps who // reuse a recycled handle value. // InterlockedDecrement (&HandleTable->HandleCount); //释放时,句柄表中句柄计数减一 CurrentThread = KeGetCurrentThread (); NewFree = (ULONG) Handle.Value & ~(HANDLE_VALUE_INC - 1); //计算要销毁的句柄的值(掩去了低两位) #if DBG if (ExReuseHandles) { #endif //DBG if (!HandleTable->StrictFIFO) { //判断StrictFIFO标记,该标记直接影响到句柄的分配算法 // // We are pushing potentially old entries onto the free list. // Prevent the A-B-A problem by shifting to an alternate list // read this element has the list head out of the loop. // //这里是StrictFIFO=0的处理方法,普通进程的句柄表的StrictFIFO是等于0的 Idx = (NewFree>>2) % HANDLE_TABLE_LOCKS; if (ExTryAcquireReleasePushLockExclusive (&HandleTable->HandleTableLock[Idx])) { //锁定 SeqInc = GetNextSeq(); Free = &HandleTable->FirstFree; //Free指向了FirstFree } else { SeqInc = 0; Free = &HandleTable->LastFree; //若锁定失败,则Free指向LastFree.实际上,上面的操作通常是成功的 } } else {//这里是StrictFIFO=1的处理方法,PspCidTable设置了此标志 SeqInc = 0; //增量为0 Free = &HandleTable->LastFree; //Free指向LastFree } while (1) {//这是一个循环尝试操作 OldFree = ReadForWriteAccess (Free); //读取Free所指向的值,即当前FreeHandleList的队列头 HandleTableEntry->NextFreeTableEntry = OldFree; //把目标HANDLE_TABLE_ENTRY的NextFreeTableEntry指向原来的队列头 if ((ULONG)InterlockedCompareExchange ((PLONG)Free, NewFree + SeqInc, OldFree) == OldFree) {//Free指向队列头,设置新的队列头为刚释放的句柄.这个操作相当于在FreeHandleList队列头部插入了一个新元素 EXASSERT ((OldFree & FREE_HANDLE_MASK) < HandleTable->NextHandleNeedingPool); break; } } #if DBG } else { HandleTableEntry->NextFreeTableEntry = 0; } #endif //DBG return; }