(一) 内容介紹
對 Windows HandleTable 的研究基于微軟的 WRK 項目和《 Windows Internals 》第四版。研究的絕大多數情況适應于 WindowsXP 和 Windows2003 作業系統。技術報告首先總體上介紹了 Windows 下的 Handle 、 Object 、 HandleTable 的作用和互相關系，然後依次介紹了 Handle 的資料結構、 HandleTable 的資料結構，其中着重介紹了 HandleTable 中的 Free Entry List 的管理機制。最後介紹了在研究過程中設計的一個 windows 驅動，該驅動的作用是向應用程式開發系統核心中的 HadleTable 的部分資料結構。
(二) Handle ， Object and Handle Table
Handle 是 Windows API 裡非常重要的概念，比如 CreateFile 的系統調用傳回類型是 Handle 。在應用程式利用 CreateFile 建立或者打開了一個檔案的之後，要讀取這個檔案，需要傳給 ReadFile 系統調用這個檔案對應的 Handle 。
Windows 核心中每個打開的檔案是有一個核心對象來控制的，也就是有一塊記憶體區，而 Handle 相當于這個核心對象的一個索引。應用程式雖然不能直接引用核心态的記憶體區，但是可以通過 Haldle 來标記對應的核心對象。
HandleTalbe 是核心中資料結構，它的主要作用就是記錄 Handle 與核心對象的 Pointer 的對應關系。
(三) Handle
Handle 在記憶體中的資料結構如下：
typedef struct _EXHANDLE {
union {
struct {
ULONG TagBits : 2;
ULONG Index : 30;
};
HANDLE GenericHandleOverlay;
ULONG_PTR Value;
};
} EXHANDLE, *PEXHANDLE;
它總共占據 32bits ，其中低二位 TagBits 位被作業系統完全忽略掉，是以可以被應用程式自由改寫。高 6 位，作為 Tag 來使用，其中最高位等于 1 ，代表是系統 HandleTable 中的 Handle 。中間的 24 位作為 Handle 的有效值。如下：
是以，得出以下兩個結論：
1. 所有的 Handle 的值，都應該是 4 的倍數
2. 一個 HandleTable 中最多有 224 個 Handle 。
另外需要注意，使用者态程式可以通過 Handle 操作核心态對象，核心态代碼也可以通過 Handle 查詢核心對象的指針，即 Handle 并不是專門給使用者态程式準備的。
(四) HandleTable
HandleTable 資料結構的主要字段如下（包含簡單注釋）：
typedef struct _HANDLE_TABLE {
struct _EPROCESS *QuotaProcess; // 所屬程序 PCB 的指針
HANDLE UniqueProcessId; // 這個程序的 ProcessID
LIST_ENTRY HandleTableList; // 所有的 HandleTAble 在核心中形成一個 List ，這是 Entry
LONG HandleCount; // HandleTable 中有多少個有效的 Handle
ULONG_PTR TableCode; // HandleTable 的樹的根指針。
EX_PUSH_LOCK HandleTableLock[4]; // 為管理樹中的 Free Entry 而提供的 4 把鎖
ULONG FirstFree; // 第一個 Free Entry List
ULONG LastFree; // 第二個 Free Entry List
……
} HANDLE_TABLE, *PHANDLE_TABLE;
有兩點需要注意：
首先每個程序是有一個 HandleTable 的，在 HandleTable 的資料結構中已經展現出來。
其次作業系統中有一張系統 HandleTable 。核心态的程式在建立 Handle 的時候，可以把 Handle 放到系統 HandleTable 中，這樣可以保證使用者态程式永遠不可能通路到該 Handle 。
l HandleTable 中的 Tree
Handle Table 儲存了程序能夠通路的所有的指針，這些指針以 Three Level 樹的方式組織，三級的名字依次為 LowLevel 、 MidLevel 、 HighLevel 。其中 LowLevel 總是被建立， MidLeve/HighLevel 按需建立。
一個 LowLevel 節點是一個頁面大小的連續記憶體，相當于一個數組，數組的每個 Entry 占了 8 個 bytes （詳見後面對每個 Entry 資料結構的描述）。如果頁面大小是 212 Bytes ，那麼總共有 212 /8=29 個 Entry 。每個 Entry 所對應的 Handle 的值是其索引的 4 倍，即這種對應關系是固定的。見下圖：
另外有 MidLevel 和 HighLevel 的一些資料：
每個 MidLevel 節點儲存一組指向 LowLevel 的指針，占據一個 Page ，有 210 個 Entry ，能檢索 2**19 個 Handle 。
每個 HighLevel 節點儲存一組指向 MidLevel 的指針，含有 25 個 Entry ，能檢索 224 個 Handle 。這裡的 224 即是一個 HadleTable 能檢索的 Handle 的最大數量。
一棵最完整的樹可能是以下形态：
有兩個問題着重闡述一下：
1. HandleTable 如何記錄 Tree 的級數。
首先保證 TreeNode 配置設定以 4Bytes 對齊 ，是以根指針 TableCode 的低二位就空閑下來，是以就可以利用根指針的低二位标記 TableLevel ，如下：
TableLevel = TableCode & 3
2. 如何根據 Handle 來查找 Entry 。
這個過程跟虛拟位址 - 實體位址的轉換很像，如下：
l LowLevel 中每個 Entry 的資料結構
HighLevel 和 MidLevel 中每個 Entry 結構很簡單，就是指向下一級 Level 的指針（ 4 個 byte ）； Lowlevel 中每個 Entry 的資料結構要複雜一下，定義如下：
typedef struct _HANDLE_TABLE_ENTRY {
union {
PVOID Object;
ULONG ObAttributes;
PHANDLE_TABLE_ENTRY_INFO InfoTable;
ULONG_PTR Value;
};
union {
union {
ACCESS_MASK GrantedAccess;
struct {
USHORT GrantedAccessIndex;
USHORT CreatorBackTraceIndex;
};
};
LONG NextFreeTableEntry;
};
} HANDLE_TABLE_ENTRY, *PHANDLE_TABLE_ENTRY;
這個資料結構占據了 8 個位元組，具有複雜的 Struct-Union 的嵌套結構。它實作了三種功能，相同的字段在不同的功能下有不同的解釋，如下：
1. 用途 1 ： HANDLE_TABLE_ENTRY 包含指向 Kernel Object 的指針，這是這個資料結構的主要用途。
此時， Object 是指針字段。由于 KernelObject 配置設定記憶體的時候保證 8 位元組對齊，指針的低三位空閑作為 tag ， ObjectAttributes 就是用來操作 tag 的。三個 tag 位中，有一位是作為 Handle 是否被加鎖的标記，有一位是作為 Handle 是否可以繼承給子程序的标記。 GrantedAccess 字段是作為 Handle 的安全資訊的标記。
2. 用途 2 ：形成空 Entry 的連結清單。
此時 Object 字段一定要是 0 ， NextFreeTableEntry 儲存了下一個空 Entry 所對應的 Handle 值。
3. 用途 3 ：指向一個 Lowlevel 中所有 Handle 的統計資訊。
LowLevel 節點的第一個 Entry 永遠也不會是有效的 Hanlde 。即數值 n*29 *4 (n=0,1,2,..) 肯定不是有效的 Handle 數值。 HANDLE_TABLE_ENTRY 此時做如下解釋： NextFreeTableEntry 儲存常量 EX_ADDITIONAL_INFO_SIGNATURE （定義為 -2 ）作為标記， Object 指向了統計資訊數組的指針，這個數組總共有 29 個 Entry ，每個 Entry 的内容由統計子產品解釋。
統計資訊并非總是需要的，是以并沒有 Handle_Table_Entry 結構中添加字段，而是在需要的時候，單獨配置設定一個數組，在 LowLevel 的第一個 Entry 中放一個指向這個數組的指針。
l Free Entry List
HandleTable Tree 中 LowLevel 的 Free Entry 是以 List 的方式來管理的，是以在打開新的 Handle 的時候，能夠迅速查到 Free 的 Entry 。 Handle Table 中的維護 Free Entry List 用到了無鎖同步的方法，但是無鎖同步會導緻典型的 A-B-A 問題， HandleTable 中提供了一個解決方案。下面依次描述這三項。
1. 無鎖同步：
如果要修改一個共享記憶體的内容，比如 int * des ，可以用下面的方式進行：
while( 1 ){
oldValue = *dest; // Step1 讀取老值
newValue = oldValule * 100; // Step2 根據老值計算新值
if(InterlockedCompareExchange(&dest, newValue, oldValue)) // Step3 設定新值
break;
}
InterlockedCompareExchange 是一個原子操作，它的功能是判斷 dest 記憶體中目前的内容和 oldValue 是否相等。如果不相等，則認為從 Step1-Step2 之間， dest 記憶體已經被别的程序改寫，是以本次寫入失敗，進入下次 while 循環；如果相等，則為 dest 記憶體沒有被改寫，本次寫入成功，退出 while 循環。
可以看到，對于一個孤立的記憶體位址，上面的代碼是正确的。
2. A-B-A 問題：
要用無鎖操作來實作一個 List ，主要是要用上面的代碼對 push 和 pop 操作中的 list 的 head 進行保護，即要通過上面的 while 循環來改寫 head 位址。這在大部分情況下是成功的，但是在以下情況下會出現錯誤：
上面是一個 list ，下面是操作這個 list 的兩個程序 P1 、 P2 。其中 P1 的 pop 代碼展開了， P2 的 pop 和 push 的代碼沒有展開。注意的是， P1 的執行過程中發生了程序切換， P2 插入後執行了一段代碼。
P2 在執行結束之後， list 變成了
當重新切換到 P1 的時候， P1 堆棧中的 old 變量的值和 head 指針指向的值是相等的，是以 head 指針會指向已經被删除的節點 B ，此時就發生了嚴重錯誤。
錯誤發生的原因是， P2 在 pop 了兩次之後，重新 push 了老的頭節點；而 P1 是通過 head 的指針内容來判斷寫入 head 指針是否成功。即記憶體空間從 A 改成了 B ，又改成了 A ，繞過了 InterlockedCompareExchange 的判斷機制導緻了錯誤，是以這種錯誤通常被稱為 A-B-A 錯誤。
3. HandleTable 中的解決方案：
這個是從 WRK 代碼中整理出來的僞代碼：
#define LOCK_IDX(handle) ((handle) >> 2) % 4)
void push( handle ) {
if(Locks[LOCK_IDX(handle)].IsSharedLock) // 這個 handle 與 FirstFree 使用相同的鎖
push to LastFree List;
else
push to FirstFree List;
}
void pop( ) {
while( 1 ) {
if(FirstFree List is empty)
Move LastFree list to FirstFree list // 這裡有可能發生阻塞
Locks[LOCK_IDX(FirstFree)].lockshared(); // 這裡是不會互相阻塞的，因為是共享鎖
if(InterlockedCompareExchange(&FirstFree, Next,FirstFree))
break;
Locks[LOCK_IDX(FirstFree)].unlockshared();
}
}
需要注意的是，在 HandleTable 的資料結構中有 EX_PUSH_LOCK HandleTableLock[4] 字段，這就是上述僞代碼中操作的鎖。
做兩點解釋：
1. 基本思路是保證在 Pop 的過程中，不會 push 與 Head 相同的 Handle ，這樣就避免了前面描述的 ABA 問題。
2. 這裡配置設定了兩個 List ， push 的時候，按照共享鎖的配置設定情況判斷 push 到哪個 list 中；在 pop 的時候，如果第一個 list 是空的，則把第二個 List 轉移到第一個 List 中。
(五) 利用驅動程式讀取 HandleTable
下面介紹一下寫的一個工具。這個工具包含一個 Windows 驅動程式和一個讀取該驅動程式的應用程式。工具的主要功能是讀取目前運作的 Windows 系統中的所有程序的 HandleTable ，列出有效 handle 的數量和 Tree 的級數。該驅動的功能代碼由研究者完成，驅動的架構借鑒了《 Windows 驅動開發詳解》中的代碼。
下面是運作的截圖：
從結果可以看出，系統中大部分的 Handle 的數量比較少，對應的 HandleTable 的級數是 0 （即一級 LowLevel ）。從 HandleTable 的設計來看，在隻有一級 LowLeve 的時候， HandleTable 的 Tree 就退化成為一個數組，是以在保證所有的情況都可用的條件下，最大程度的提高了大多數情況的運作效率。