(一) 内容介绍
对 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 就退化成为一个数组，因此在保证所有的情况都可用的条件下，最大程度的提高了大多数情况的运行效率。