5.4  案例研究：NTDLL.DLL中的Generic Table API

现在我们就进入我们的第一个逆向工程任务吧！在这个任务中我们将以一组未公开的Windows API函数为例进行分析，直到我们能够在自己的代码中使用这些APIs。实际上，为了证明这一想法是确实可行的，我还特意写了一个使用这些APIs的小程序。当然，我写这一章的目的不是教大家怎样使用这些特定的API，而是向大家生动地演示如何对真实的代码实施逆向工程。

这一章我们选择generic table API函数进行逆向。这组API是Windows本地API（Native API）的一部分。（至于什么是Windows本地API，请参见第3章）。

在系统本地API中有很多冠以不同前缀的API函数组。在本例中，我们选择RTL组中的一个函数集合。这组运行库函数不是用来与操作系统通信的而是作为提供操作系统最常见服务的一个工具包而存在的，这些最常见的服务包括字符串处理、数据管理，等等。

一旦你锁定generic table API，下一步就该通览一下NTDLL.DLL的导出表（generic table API是在NTDLL.DLL中实现的）以便找到所有可能的相关函数。在本例中任何以Rtl开头并涉及generic table的函数都是我们可能感兴趣的。在用DUMPBIN（见第4章关于DUMPBIN一节的内容）转储了NTDLL.DLL的导出表之后，根据上面的要求，我们得到了如下的函数列表：

如果你自己做一下，并观察NTDLL.DLL的导出表，你可能会注意到上面绝大多数API函数还有一个带Avl后缀的版本，所以实际的generic table API函数组比上面列出来的还要大，我们只是为了方便讨论而有意忽略了一些基本重复的函数。

我们根据函数名做一点基本的猜测：显然这是一组用于管理某种通用链表的函数（通用就是意味着链表中的每一个成员可以是任何一种类型的数据）。有一些API是用来进行插入、删除及查找一个链表中的成员的。RtlNumberGenericTableElements API可能是用于返回链表中成员总数的。而RtlGetElementGenericTable则很可能是用来按索引来访问链表中特定成员的。在你开始使用这个通用表单之前，很可能要用RtlInitializeGenericTable来初始化某种根数据结构。

一般来说，逆向工程都是从数据开始的——你必须找到代码管理的关键数据结构。有鉴于此，我们从RtlInitializeGenericTable开始是个不错的主意。我们希望从中找到破译通用表单的数据结构的线索。

就像我已经解释过的，我们下面会仅对代码进行逐行分析，而不是动态调试它。如果你还是想要在一个调试器中分析generic table的代码，你可以使用我自己根据对generic table API的逆向工程结果写的名为GenericTable.EXE的小程序。如果你没有这个小程序，那么你可能只有依靠静态分析来进行分析了，当然你还是可以试着找一找其他使用这组API的代码。我大致搜索了一把，我发现使用这组API的代码只出现在Windows内核模式的代码中，而在用户态运行的代码中我还没有找到类似符合条件的代码。（generic table也是在Windows内核中的一个内核态的实现）GenericTable.EXE可以在本书的网站www.wiley. com/go/eeilam上下载。

下面几节里我们分别深入研究generic table API中的每一个重要的函数，并展示每个函数的内部实现细节。你也许会注意到，我会钻研得比较深，比破解必要的实现细节更深入一些。这主要是为了向大家展示高级的逆向工程技巧的威力，如果这是一个真实的为了使用generic table API而进行的逆向工程，你可能在获得必要的信息后，就会停止有关逆向工程的工作。但这次，为了展示高级逆向工程技巧，我们要搞清楚generic table数据结构的细节。

5.4.1  RtlInitializeGenericTable

就像我们已经说过的，要想破译generic table API最好从其使用的数据结构入手。虽然你不需要知道这组API的所有细节，但是如果知道关于这组API所使用的数据结构的通用思路一定有助于我们破译这组API。让我们从最有可能包含有关信息的函数（仅仅是从文件名来判断）入手开始工作：RtlInitializeGenericTable函数，下面是使用OllyDbg对这个函数进行反汇编得到的结果（见列表5.1）：

列表5.1  RtlInitializeGenericTable的反汇编

在确定函数的功能和实现细节之前，我们先要搞清楚什么是“调用约定”以及主调函数一共向函数传递了多少个参数？“调用约定”是指函数是怎样接收主调函数传来的参数以及一旦函数执行完毕由谁来负责清栈。有好几种调用约定，但在Windows下默认使用的调用约定是stdcall。使用stdcall调用约定的函数在执行完毕时自己负责清栈。并且按照从左往右的顺序接受参数（这就是说主调函数是按照逆序向堆栈中压入参数的）。关于调用约定的详细讨论见附录C。

要确定一个函数到底是使用了哪一种调用约定，你可以看一下该函数的返回指令——RET。在这段代码中，你应该注意到：函数是以一个“RET 14”的指令返回的。这个RET指令带有一个操作数，这个操作数至少向我们提供了两个重要信息：1、通过这个操作数我们知道在函数返回时应该清除的堆栈的大小（除返回值外）。2、既然是由RET指令进行清栈，那么这个函数一定不是使用cdecl调用约定的。因为cdecl调用约定是由主调函数负责清栈的。那么这个函数到底是使用哪种调用约定的呢？

我们继续用这种排除法来确定这个函数的调用约定，而且我们发现这个函数没有通过寄存器从主调函数接收任何参数，因为在函数中所有用到的寄存器都是由函数自己初始化的。这个函数使用的肯定不是_fastcall调用约定的，因为_fastcall函数通过ECX和EDX寄存器来接收参数，而这里却是在函数开始处对这两个寄存器作了初始化。

其他常见的调用约定还有stdcall调用约定和C++成员函数方法调用约定。你知道它用的不是C++成员函数调用约定，因为你是从NTDLL.DLL的导出目录中知道这个函数的名字的（RtlInitializeGenericTable）。而且你知道这个函数名是未加修饰的（undecorated）。C++函数的方法名称总是要它们的类名和它们所接收的每个参数的准确类型来修饰一番。识别修饰过的C++函数名字的方法很简单，因为它们通常都包含大量非字符数字的字符，而且包含多个名字（最少也有类名和方法名两个名字）

通过排除法，你已经确定了这个函数使用的是stdcall调用约定。而且，你也知道RET指令后的数字14告诉你这个函数总共接收几个参数。在这里我们用的是OllyDbg，OllyDbg输出的是十六进制数，所以这里的十六进制数14实际就是十进制的数20。因为你工作在32位环境下所有的参数都是以32位（即4个字节）对齐的，所以你可以假定这个函数总共接收了5个参数。当然也有可能其中有一个参数的长度超过4个字节，这种情况下函数接收的参数就会少于5个，但是参数个数绝对不会多于5个的，因为参数是32位对齐的。

通过观察这个函数的头几条指令，你会发现它使用了标准的EBP堆栈帧（stack frame），EBP的当前值被保存在堆栈上，而EBP中存储的是ESP的值。这样在函数运行过程中不管ESP的值如何变化，都可以用EBP来便捷地访问参数（只要这个函数在调用其他函数时向堆栈中压入参数ESP的值就会改变）。在这种常用的堆栈布局方法中，第一个参数放在[EBP+8]处，第二个参数放在[EBP+C]处，等等。如果你不明白为什么是这个样子的话，请参考附录C，其中很详细地介绍了堆栈帧。

通常，函数还会在堆栈中为局部变量分配存储空间，这时，ESP又会减去存储局部变量所需的字节数，不过还好，这个函数没有这样做，也就是说，这个函数没有在堆栈中存储局部变量。

我们把列表5.1中给出的这个函数代码逐条看一下，弄清楚它到底在干什么。正如我在前面提到过的，你可能想在调试器中使用在线分析方法一步一步的跟踪代码来确定这个函数的“所作所为”，并用GenericTable.EXE观察它在执行中会发生什么。如果你现在看汇编代码已经没有什么障碍的话，你可以直接读列表5.1中的代码而无需借助GenericTable.EXE。

我们开始深入分析一下这个函数吧，看看它到底是怎样工作的以及它做了些什么。

第一行代码把堆栈中[EBP+8]的值装入了EAX寄存器。我们已经知道[EBP+8]是函数的第一个参数。第二行代码堆栈器edx自己和自己进行了XOR（异或）操作，这实际上是将EDX清零。编译器之所以使用XOR是因为指令XOR EDX，EDX的机器码比指令mov EDX,0的机器码要短，虽然后者要更直观一些。这也正好说明了逆向工程师经常要面对这种代码——优化编译器常常为了减小代码的体积和加快代码的运行速度牺牲代码的可读性。

第三行代码，你可能被LEA指令在你第一次见到它的情况下把你搞糊涂。LEA（加载有效地址，load effective address）实际上是一条算术指令——它不执行任何实际的内存访问，但它常被用来计算地址（虽然你还可以用它来完成整型数运算）。别让前缀“DWORD PTR”把你搞懵了，这条指令只是一条纯算术运算。在我们这段代码中，LEA指令就等价于“ECX = EAX + 4”。

到现在为止，你还不知道你所碰到的数据类型是什么，最重要的是你还不确信这个函数接收的第一个参数[EBP+8]的数据类型。我们接着看看下面这段代码，看还能获得些什么信息。

这段代码为我们揭示了一条非常重要的信息：函数中的第一个参数是指向某种数据结构的指针，而且这种数据结构是在这个函数中初始化的。很可能这个数据结构是这个generic table的关键数据或者根结点，因此，搞清楚这个数据结构的布局将是你学会使用这些generic table的关键。

我们现在感兴趣的是访问这种数据结构的方式——用了两个不同的寄存器。实际上，这个函数保留了两个指向这个数据结构的指针，即EAX和ECX。EAX存储的是通过第一个参数传来的原始值，而ECX存储的是地址“EAX+4”。该数据结构中的成员有的是通过EAX访问的，有的是通过ECX来访问的。

这是上面每一条代码所完成的工作：

1．将这个数据结构的第一个成员设置为0（用EDX）。这个结构是通过EAX访问的；

2．将这个数据结构的第三个成员设置为这个数据结构的第二个成员的地址（就是存储在“ECX：EAX+4”中的值）。这次这个数据结构是通过ECX而不是通过EAX访问的；

3．把第二个成员设置为（存储在ECX中）的那个地址；

4．把第四个成员设置为（存储在ECX中）的那个地址。

如果你把这段代码翻译成C语言代码，它可能会是下面这个样子：

初看上去，除了告诉我们第2、3、4个成员（偏移地址分别是+4，+8和+c）都是指针外，我们好像没有得到更多有关这个数据结构的信息。后三个成员的初始化方式有点儿奇怪：它们都被初始化为指向第二个成员的指针了。这可能是什么意思？实际上这告诉你这三个成员中的每一个都是指向一组（三个）指针的指针（因为就是“UnknownStruct -> Member2”所指向的——三个一组的指针）。但是让人感到不解的是这个结构指向的是它自己，而且这很可能只是一个占位符。如果要我猜的话，我觉得这些指针以后都会变成指向其他地方的指针。

我们来看这个函数反汇编代码中接下来的四行：

前两行代码把传给函数的第二个参数的值拷贝写到数据结构中偏移地址+18处（偏移地址+18处是第七个成员）。接下来的两行把第三个参数拷贝到该数据结构中偏移地址+1C处（偏移地址+1C处是第八个成员）。我们把这几句代码翻译成C语言代码，所示如下：

接着我们看RtlInitializeGenericTable的下一部分代码：

这和前面的代码很相似——代码对这个数据结构的其余部分进行了初始化。在这段代码中，偏移地址+20处的成员是用第4个参数初始化的，偏移地址+14和+10被初始化为0，而偏移地址+24处是用第5个参数初始化的。

到这里就结束了RtlInitializeGenericTable函数的数据结构中初始化。不幸的是，如果不在调试器中现场调试看看传给这个函数的真正数据的话，你很难了解传入的参数的或者数据结构成员的数据类型。你现在只知道这个数据结构大约占40个字节，因为最后一个成员的偏移地址是+24，这表明这个数据结构有28个字节长（28是十六进制数），换算成十进制数就是40字节。假定这个数据结构的每个成员都占用4个字节，那么你就可以推断出这个数据结构共有10个成员。这样，就可以为这个数据结构写出一个模糊的定义来，我们在后面再逐渐改进它。

5.4.2  RtlNumberGenericTableElements

接下来我们研究一个感觉比较简单的函数：RtlNumberGenericTableElements。我的想法是如果在根数据结构中有一个记录整个table的中元素个数的成员的话，那么RtlNumber GenericTableElements函数可能会把这个成员暴露出来。如果没有这样一个成员，那么

RtlNumberGenericTableElements函数将会遍历所有的元素。下面是用OllyDbg得到的RtlNumberGenericTableElements函数的反汇编代码。

好，看起来好像问题已经解决了！这个函数只接收了一个指针，和前面一样，我们只能假定这个指针指向同一种数据结构，返回的数据在偏移地址+14处。显然，偏移地址+14中包含的就是generic Table数据结构中的元素个数。我们现在更新一下这个TABLE数据结构的定义。

5.4.3  RtlIsGenericTableEmpty

在generic table API还有另外一个简单的函数（希望如此），或许从这个函数也能得到一些有关这个数据结构的信息，这个函数是：RtlIsGenericTableEmpty。当然，也有可能这个函数用的就是RtlNumberGenericTableElements函数中所使用的NumberOfElements成员。我们来看一下。

正如我们所希望的，RtlIsGenericTableEmpty的确很简单。这个函数将第一个参数的值（它应该是前边所说的根数据结构）加载到ECX寄存器中，并将EAX寄存器清零。这个函数接着比较了该数据结构的第一个成员（在偏移地址+0处）与EAX，如果相等就用SETE指令将AL置1。（有关SETE指令的详细信息见附录A）

实际上这个函数所做的就是检查该数据结构中偏移地址+0处是不是0，如果是0，则函数返回TRUE，如果不是则函数返回零。现在你知道在偏移地址+0处有一个重要的成员，只要table中有元素这个成员就总是非零。我们再向这个数据结构添加一些信息。

5.4.4  RtlGetElementGenericTable

在generic table API中有三个看上去好像是用来查找和检索元素的函数，它们是RtlGetElementGenericTable、RtlEnumerateGenericTable和RtlLookupElementGenericTable。仅根据它们的函数名，我们就可以轻松猜出这三个函数是干什么的了。最容易猜的是RtlEnumerateGenericTable函数，它显然是枚举表中部分或者全部的元素。接下来的问题是：RtlGetElementGenericTable函数和RtlLookupElementGenericTable函数之间有什么区别？不看代码是不可能回答这个问题的，不过如果非要让我猜的话，我会猜RtlGetElement GenericTable函数具有一种直接访问元素的能力（可能是用索引来访问），而RtlLookupElementGenericTable函数可能要在表中搜索正确的元素。

如果我猜得没错的话，在这两个函数中可能RtlGetElementGenericTable函数比较简单。列表5.2给出了RtlGetElementGenericTable函数完整的反汇编代码。在继续读我的分析之前，你不妨试着自己分析一下这些代码。

列表5.2  RtlGetElementGenericTable的反汇编代码（待续）

列表5.2（续）

正如你所看到的，RtlGetElementGenericTable函数比我们前面看到的函数要稍微复杂一些。下面我们分成几个小节详细地一下列表5.2中的反汇编代码。

设置和初始化

和前面分析过的APIs一样，RtlGetElementGenericTable函数代码的开头也是一段堆栈帧设置代码序列。这告诉你这个函数准备用EBP而不是ESP来访问其参数。我们来看一下RtlGetElementGenericTable函数的前几行代码。

这些generic table APIs好像都把根table数据结构作为它们的第一个参数，从这一点来说我们找不到任何证据证明RtlGetElementGeneric有什么不同。在这段代码中，函数将根据table指针加载到ECX寄存器中，然后将存储在偏移地址+14中的值存入EDX寄存器中。回忆一下我们在分析RtlNumberGenericTableElements函数时发现偏移地址+14处是table中元素的总个数。接下来的一条指令将偏移地址+0_C处的第三个指针（三指针组）加载到EAX寄存器中。我们来看下面的代码：

这段代码一开始将EBX和ESI寄存器压入堆栈，目的是保存它们原来的值（我这样说是因为我在这段代码中没有找到函数调用）。其后，代码将根数据结构偏移地址+10处的值装入ESI寄存器，然后将EDI寄存器压入堆栈（为了把它腾出来用于存放其他值），接下来的一条指令将“EBP+C”指向的值装入EDI。

你知道“EBP+8”指向第一个参数，所以“EBP+C”指向的是第二个参数。因此位于ntdll.7C9624F2的指令是把传给该函数的第二个参数的值赋给EDI寄存器。紧接着将EDI与-1相比较，这里你看到的是典型的交错代码的情况。交错代码在为现代IA-32处理器生成的代码中是非常普遍的现象（详见第2章2.5节“执行环境”一节的内容）。交错代码是指令在代码中并不是按照其本来的顺序排列的，而是相互独立的指令交互在一起，这样在运行时CPU在必须执行第二条指令之前就有时间完成第一条指令。在这个例子中，你可以说代码是交错的，因为条件跳转质量没有紧跟着CMP指令。这样做是为了在执行中最大程度地实现并行。

CMP指令后面是另一条把LEA用作纯算术指令的语句。这次，这条LEA指令只是用于执行了“EBX = EDI + 1”。一般情况下编译器会使用“INC EDI”指令，但是这次编译器显然是想既保持EDI中的值不变，又得到EDI加1的结果，所以LEA指令是个不错的选择。这条LEA将EDI加1后结果放在EBX中——EDI中原来的值保持不变。

下面你看到的这句JE就是与ntdll.7C962559处的CMP相关的条件跳转，提醒一下，EDI（传给该函数的第二个函数）前面已与-1进行了比较！如果“EDI == 1”则指令将会跳转到ntdll.7C962559处。如果你回过头来看到列表5.2中ntdll.7C962559处的代码，你很快就会发现这是某种失败或错误条件的处理代码，因为这里把EAX（返回值）置为0，弹出前边压入堆栈的寄存器值并返回。所以，如果你要把前边这个条件语句写成C代码的话，可能会写成下面这个样子：

上面这段代码中的最后两句执行的是同一个参数的另一次检查，只是这次用的是EBX寄存器（你还记得EBX就是“EDI+1”吧？）。这里将EBX与EDX比较，如果EBX大于EDX代码将跳转到ntdll.7C962559。请注意这个跳转目标地址ntdll.7C962559，和前面的条件跳转JE是同一个地址。这显然就是暗示我们这两个跳转在源代码中都属于一个复合条件语句，它们只不过是一个条件判断语句中的两个测试条件而已！

另一个既有趣又能为我们提供丰富提示信息的问题是这个条件跳转指令用的是JA（jump if above，大于则跳转）指令，JA是使用CF标志位来判断的，这表明EDX和EBX中的值都是被当作无符号数处理的！因为如果是有符号数，编译器应该用JG指令才对，JG才是这条指令的有符号数版本。更多有关有符号数和无符号数条件代码信息请参考附录A。

如果你试着把这些信息整合一下，你会发现这个最后的测试条件为我们揭示了一个有关传给这个函数的第二个参数的有趣信息。回想一下，EDX中存放的是该结构中偏移地址+14处的值，也就是存放Table中元素的总数的那个成员。RtlGetElementGeneric的第二个参数是table的一个索引（index）。这最后两条指令只是通过将这个索引与元素的总数比较来确认一下它是不是一个合法索引的。这也在一定程度上说明了为什么要给索引加1：为了正确地比较索引和总数。索引号是从0开始的，而表中元素的总数显然不是（雷同于C语言中的数组）。现在你理解了这两个条件，而且知道他们都是来自同一个条件语句，你可以放心地假设对索引参数的合法性校验在源代码中是用一句话完成的，可能就像下面这种写法：

你怎么能确定“ElementToGet+1”是在if语句中计算的还是先计算出来存到一个变量中的呢？我现在确实不能确定。但是当你观察列表5.2中所有用到EBX的代码，你会发现整个函数中频繁使用了“ElementToGet+1”这个值。这表明这个值被算出来存放到一个局部变量中（因为要反复用这个值，为了提高效率肯定不会多次计算它），在后边要用“ElementToGet+1”的地方就用这个变量。编译器显然用EBX来存储这个局部变量而不会把它放到堆栈上。

另一方面，也有可能是源代码中多次使用了“ElementToGet+1”这个语句，而编译器会在优化代码时自动声明一个临时变量来存储这个值而不是在每次用到的时候计算它。这

是另一种你以前不知道的情况——这个信息在编译过程中丢失了。

我们继续分析下一段代码：

这段代码开始比较了ESI（在前边其值取值table数据结构偏移地址+10处）与EBX寄存器。这为我们揭示了偏移地址+10处也是指向table中的某个索引（因为它与EBX进行了比较，而你知道EBX是table的索引），但是你还不知道它是一个什么索引。如果“ESI == EBX”,代码将跳转到ntdll.7C962554，如果“ESI <= EBX”，代码将跳转到ntdll.7C96252B。现在我们还不太清楚为什么第二个跳转使用指令JBE？因为这里的相等条件使不可能成立的，否则第一个跳转JE就被执行了。

我们还是先来看一下ntdll.7C962554处发生了什么：

这段代码执行“EAX = EAX + 12”，然后无条件跳转到ntdll.7C96255B。如果你回到列表5.2，你会看到ntdll.7C96255B就在该函数的结尾处，所以上面的代码就是给主调函数返回“EAX+12”。回想一下，早些时候EAX是从table数据结构偏移地址+C处加载的值，并且在解读RtlInitializeGenericTable时我们假定偏移地址+4、+8和+C处都是指向同一种三指针数据结构的指针（它们都被初始化为指向偏移地址+4处的指针）。在这里，这些指针中的一个增加了12后返回给主调函数。这为我们理解GenericTable提供了很多线索。我们来逐个分析一下：

^, 你知道根数据结构中从偏移地址+4处开始有三个指针；

^, 你知道这三个指针每一个都是指向另外一个三指针组。在初始化时，它们都是指向它们自己的，但你可以放心地认为在向table填充元素时情况就变了；

^, 你知道函数RtlGetElementGenericTable给主调函数返回的是这些指针中的一个，但是在将其值加上12后返回的。注意12恰好是三个指针加起来的长度；

^, 你已经知道RtlGetElementGenericTable函数接收两个参数，第一个参数是指向table数据结构的指针，第二个参数是table的索引。你可以放心地假定这个函数返回的是这种元素。

综合上述几点你可以推知RtlGetElementGenericTable函数返回指向一个元素的指针，加上12只是为了跳过元素的头部而直接指向元素的数据。这个头部看上去很像是另一个三指针数据结构，就像根数据结构偏移地址+4处那样。另外，这三个中的每一个都应该指向其他带有三指针头部的向才有意义，就像这个。此外，偏移地址+10是缓存元素（cached element——由第三个指针指向的元素（在偏移地址+C处））的索引。不同的是偏移地址+C是指向内存单元的地址，而偏移地址+10是table的索引，等价于一个元素编号。

对我来说，这是一个令人激动的逆向过程——我们一点一点地收集证据，然后把这些证据整合起来，先形成一个带有主观猜测的解释，然后逐渐成为对代码的完整理解。对于这项逆向任务，我们无疑已经在最重要的难题上——generic table数据结构上取得了突破性的进展。

逻辑与结构

我们总是在不经意间忽略掉一个关键问题：这个函数的结构是怎样的？当然，你可以将那些条件跳转语句和无条件跳转语句全部当作goto指令来处理，但用这种方法只能帮助你理解相对简单代码的流程。另一方面，如果一段代码中有太多的跳转语句而使得你很难追踪到所有这些跳转的话，会怎样呢？我想，你现在应该考虑一下代码的“逻辑与结构”的问题了，你可以从试着按照逻辑关系摆放这些条件跳转语句和无条件跳转语句开始。记住了，你正在逆向的汇编语言代码是用编译器生成的，而源代码可能是用C语言写的。极有可能这个逻辑完全是用if-else语句组织的代码生成的，你怎样才能重构出它原来的样子呢？

让我们从代码列表5.2中的第一个有趣的条件跳转语句——跳转到ntdll.7C962554的那条JE语句开始吧（我忽略了前面两个跳转到ntdll.7C962559处的条件跳转语句，因为这两条语句我们前面已经讨论过了）。假设是用高级语言写的话，你会使用什么样的语句实现跳过这么多行代码的条件跳转呢？很简单，汇编语言代码中条件跳转语句的测试条件一定与源代码（即高级语言代码）中if语句中的判断条件刚好相反。这是因为处理器需要知道在

什么情况下要跳过那些代码；高级语言的视角则完全不同，我们需要考虑的是满足什么条件才会执行某个条件块。这么说来，测试是否满足ESI等于EBX的源代码必定是“if (ESI != EBX)”，而且紧接其后的一对花括号（curly braces）中有一大段代码。JE语句跳转的目标地址就是该条件块结束之后的代码地址。

认识到这一点非常重要，按照这一理论，我们可以断定在JE语句和JE语句跳转的目标地址之间的所有代码都属于同一个条件块，因此，在这个条件块中出现的任何其他的条件语句，都可以当作嵌套逻辑（nested logic）来对待。

我们把这个逻辑分析方法再扩展一下。该JE指令之后紧接着是一条条件跳转指令，它仍然是测试ESI和EBX这两个寄存器的值：如果“ESI <= EBX”，则跳转到ntdll.7C96252B处。我们还是假设高级语言中的测试条件必然与汇编语言中测试条件相反（附录A中详细讨论了什么时候刚好相反什么时候不是。）。这就是说源代码中原来的测试条件必定是（ESI > EBX）。如果不满足条件“ESI > EBX”则跳过该条件块。

需要强调的是对于这个特殊的跳转指令——该无条件跳转指令JMP就出现在ntdll.7C96252B之前。这就是说：如果上面的条件块被执行了，ntdll.7C96252B后边这段代码就不能执行。这就意味着在高级语言中只有if条件块被跳过了，才会执行ntdll.7C96252B后面这段代码。为什么会这样？如果你好好想想，就会发现这不就是高级语言中再常见不过的程序设计构造——if-else语句吗？其中else块的起始位置是ntdll.7C96252B，这就是为什么在if块之后有一个无条件跳转语句。我们只能让两个块中的一个执行，而不是两个都执行。

你可以在附录A中找到更多有关编译器生成的逻辑结构的信息。

我们继续分析在研究ntdll.7C96252B处的代码之前所看的代码块。要知道，我们刚比较了ESI（它是偏移地址+10的索引）I和EBX（它显然就是我们想要获得的元素的索引），接着有两个条件转移指令：第一个条件转移指令（我们已经研究过了）在两个操作数相等的情况下发生跳转；第二个条件跳转指令在“ESI <= EBX”的情况下跳转到ntdll.7C96252B。我们等一会再来讨论ntdll.7C96252B处的这段条件代码。你应该意识到这两个条件转移指

令之后面的代码只有满足ESI>EBX时才会执行，因为我们已经测试了“ESI == EBX”和“ESI < EBX”并给出了它们的跳转位置，这才是最重要的。

当上面两个条件转移指令的条件都没有执行时，代码会将ESI中的值拷贝到EDX寄存器中，然后将EDX中的值右移一位。二进制移位操作是实现操作数乘以或除以2的指数次方比较常用的方法。将整数x左移n位可以得到“x_*2ⁿ”；右移n位则得到“x/2ⁿ”。在这种情况下，将EDX右移1意味着EDX/2¹，或EDX/2要获得更多有关怎样辨认算术代码的信息可参考附录B。

接下来是一条将EDX寄存器（这时EDX中的值是ESI/2）和EBX寄存器（EBX中的值是我们要找的元素的索引加1）进行比较的语句，并且如果EBX小于或等于EDX，则跳转到ntdll.7c96251B。如假定的两个操作数EBX和EDX都是无符号数，也就是说表的索引是用无符号整型数来表示的，因此你完全不必担心它的安全问题。我们先跳过这个跳转转移指令，就当这个条件转移根本没有发生过，继续看下面的代码。

接下来的指令将ESI减去EBX，并将结果存放在ESI中。但是再往下的指令可能会让有些人摸不着头脑。你可以看到这条减法指令后面是一句JE指令（如果相等则跳转），因为实际上比较指令和减法指令是一会事儿，都是做了减法运算，只不过比较指令不保存减法运算的结果，只保留了对标志位的影响。因此这一条JE指令执行跳转的条件是：如果减法运算作之前“EBX == ESI”，或者减法运算后“ESI == 0”（这两个条件实际上是一回事儿，只是看上去不同而已）。注意这暴露了代码中的一个冗余操作——你在前边已经比较过EBX和ESI寄存器的值，并在EBX等于ESI的情况了退出此函数（还记得跳转到ntdll.7C962554的代码吗？），所以这里ESI是不可能等于0的。我想，写这段代码的程序员一定有充足的理由应对“紧接着这个检测之后的代码不会在“ESI == EBX”情况下被执行”的两处检测。让我们来看看这到底是怎么回事儿。

搜索循环1

现在，你已经分析完了从ntdll.7C962501开始到ntdll.7c962511结束这一段代码了。接下来的代码看起来好像是某种类型的循环。让我们一起看一下这些代码，并试着分析它的功能。

如同我前边提到的那样，我们首先应该注意到这些指令构成了一个循环：只要“ESI != 0”，这条JNZ指令就会不断地跳转回ntdll.7C962513（循环的开始位置）。那么这个循环在

干什么呢？记住EAX就是根数据结构中那个三指针组中的第三个指针，并且你现在还假定每个元素都是以同样三指针结构开始的。这个循环的确支持这一假定，因为这个循环里，把EAX指向的位置加上偏移量+4当成另一个指针来处理。这虽然不是一个确凿的证据，但是偏移量+4处确实就是generic table中每个元素开头的三指针结构中的第二个。

显然前面那句用ESI中减去EBX的指令的执行结果实际上就是从EAX开始到你要找的元素之前应该遍历的元素个数（记住，你已经知道ESI就是EAX所指元素的索引号）。现在的问题是，相对于EAX我们的遍历是朝方向进行的？是按索引号由大到小遍历元素，还是按索引号由小到大遍历元素？答案很简单，因为在前面你已经比较了ESI和EBX，并且在“ESI<=EBX”的时候跳出循环。所以执行遍历的条件就是“ESI > EBX”。这就告诉你是按索引号由大到小遍历元素的（通过每个单元偏移地址+4处的指针实现）。

还记得我在前面提到过“程序员要两次检查“ESI < EBX”肯定是有原因的”这个问题吗？这个循环可以为我们澄清这个事实。如果你在“ESI <= EBX”的情况下进入了循环，ESI可能很快就变成了一个负数，因为在循环一开始对ESI进行了减1操作。这会使循环不停地进行下去，直到碰到一个无效指针导致程序崩溃或者ESI再次减到零（如果这是一个循环链表的话）。在32位的计算机中，再次减到零需要进行4,294,967,296次迭代操作，这个数字看起来好像很大，但是现代的高速处理器中能够在极短的时间里就完成这么多次迭代，如果这种情况偶尔发生一次的话，程序员可能都察觉不到这个错误。这就是为什么对程序员来说，宁愿让一个程序出错而停止运行也不愿让它出了错还继续运行。

在循环结束的时候程序将跳转到ntdll.7C96254E处。我们来看一下ntdll.7C96254E处的代码都做了些什么。

好，这确实很有趣。在这里你可以清楚地看到根数据结构中偏移地址+C和+10中所包含的内容。这好像是为了实现快速搜索和遍历表而做的某种优化。偏移地址+C处得到的是指向你要找到的元素的指针，而偏移地址+10处得到的是这个元素的索引号。这样的原因是为了尽可能减少迭代的次数，从而减少对这个函数（也可能是遍历这个链表的其他函数）

的频繁调用。其后，代码跳转到ntdll.7C962554，ntdll.7C962554处的代码通过加12跳过了该元素的头部，然后将那个指针返回给主调函数（ntdll.7C962554处的代码我们在前边看过）。

现在你具备了运行这个函数所需的基本知识了，并且了解了generic table布局结构的内容。我们继续讨论前面跳过去的其他主要情况。

我们从满足“ESI < EBX”条件的情况开始（实际上代码检查的是“ESI <= EBX”，但是如果“ESI == EBX”的话就执行不到这里）。下面是满足这个条件时将执行的代码：

这段代码执行了“EBX = (Table->TotalElements - ElementToGet + 1) + 1”和“EDI = ElementToGet+1-LastIndexFound”。简单地说，EDX寄存器中存放的就是你要找的元素到链表中最后一个元素之间的距离（距离的单位是元素的个数），而EDI寄存器中存储的就是你要找的元素到之前找到的元素之间的距离。

搜索循环2

在计算完上面两个距离后，你现在到了一个重要的连接处，在这里你要进入两个搜索循环中的一个。我们先来考察一下如果“EDI > EDX”时就跳转，跳转到ntdll.7C962541的条件转移语句。

这段代码先测试是不是满足“EDX != 0”。满足的话，则从根table数据结构偏移地址+4处所指向的元素开始对各个元素进行循环。和前边你看到过的循环类似，这个循环也使用每个元素中偏移地址+4来遍历整个结构，只不过这个循环的开始指针不同。你前面所看到的循环是从数据结构中偏移+C处的那个成员开始的，也就是指向最后找到的元素的指

针。而这个循环是从偏移地址+4处开始的。那么偏移地址+4处的指针指向哪里呢？我们有一个线索可寻。

我们来看这个循环中将要遍历多少个元素，以及你怎样知道要遍历多少个元素。这个循环迭代的次数存储在EDX寄存器中，你可以通过计算表中最后一个元素到你要找的元素之间的距离来得到这个次数。这个循环带你走过了从表中最后一个元素到你要找的元素这样一段距离，这就是说，据结构中偏移地址4指向链表的最后一个元素！通过对每个元素偏移地址+4处的指针循环，这个循环从链表的后面向链表的头部进行遍历。我们之所以这样说，是因为在前一个循环中（在ntdll.7C962513处），你已经知道了取每个元素偏移地址+4处的指针使得你在链表中“后退”，即按索引号由大到小在链表中遍历元素。而这个循环也在做同样的事情，只是它从链表的最末端开始遍历。因此，RtlGetElementGenericTable函数的功能就是通过尽可能少的迭代次数找到链表表中指定的元素。

当EDX寄存器中的值变为0时，你就找到了指定的元素。然后代码将转向ntdll.7C96254E处执行，此处的代码我们前面已经分析过了。这段代码将我们找到的元素缓存到根数据结构中偏移地址+C和+10处，然后转向函数的返回代码部分，将指向我们的元素数据的指针返回给主调函数。

当“EDI == 0”时，代码将跳转到ntdll.7C96254E处，会有什么事情发生呢？代码将直接跳过循环，缓存找到的元素，接着将它返回给主调函数。在这种情况下，函数只是返回前面找到的元素，这个元素指针缓存在根数据结构偏移地址+C处）。

搜索循环3

如果前面两个循环的运行条件都不满足的话，你就可以肯定是“EDI < EDX”的情况了（因为你已经测试了其他所有的条件了）。在这种情况下，你知道必须在表中按索引号由小到大遍历链表中的元素，以便从缓存元素的偏移地址+C处“顺藤摸瓜”找到你想要找的元素。下面是这个正向搜索循环的代码。

对于这个循环你需要注意的最重要的事情是它使用了元素头部中一个不同的指针。我们前面碰到的反向搜索循环都是使用元素头部偏移地址+4处的那个指针，而这个循环却使用了偏移地址+0处的那个指针。这很好解释——这显然是某种链表结构，偏移地址+0处存储的是“NextElement”指针，而偏移地址+4处存储的则是“PrevElement”指针。另外，

这个循环使用EDI寄存器作为计数器，EDI寄存器中存储的是缓存的元素到你要找的元素之间的距离。

搜索循环4

还有一个重要的搜索循环我们没有讲。你还记得在我们进入第一个反向循环之前是怎样测试索引值小于“LastIndexFound / 2”这种情况的吗？我们来看一下在那里函数做了些什么？

这段代码从根数据结构偏移地址+4的指针所指向的元素开始，我们在前边已经将这个指针定义为指向链表中最后一个元素的指针。然后，这个循环开始用每个元素头部偏移地址+0对链表中的元素进行遍历。偏移地址+0已被建立为元素的NextElement指针，那么接下去是什么呢？我们怎么能够从链表的最后一个元素开始正向遍历链表呢？看来，我们得对根数据结构偏移地址+4处的指针的定义做一个小小的修正。它并非指向链表中的最后一个元素，而是指向一个环形链表（circular linked list）的头，这里所说的“环形”的意思是指链表中最后一个元素的“NextElement”指针指回到链表的第一个元素，而第一元素的“PrevElement”指针指向了最后一个元素。

因为如果索引号小于“LastIndexFound / 2”的话，从链表最后一个元素反向遍历的效率肯定是很低的。相反，我们从链表的第一个元素开始从前到后遍历链表，直到找到要找的元素。

重构源代码

到这里，我们就结束了对RtlGetElementGenericTable函数的细节分析。RtlGetElementGenericTable不是一个简单的函数，它包含了整个比较复杂的控制流结构和一些数据结构的操作。仅仅是为了展示逆向工程的威力以及逆向分析所能达到的精细度，我尝试着重构出这个函数的源代码，以及TABLE数据结构中必定会有的成员的临时声明。列表5.3展示了当前我们所知道的TABLE数据结构。列表5.4给出了我为RtlGetElement GenericTable重构出的源代码：

列表5.3  根据目前为止我们所知道的TABLE数据结构的内容

列表5.4  RtlGetElementGenericTable的源码级重构

列表5.4（续）

想想这真是不可思议：就凭着一些巧妙的推断和扎实的汇编语言功底的准确把握，你就可以把那近两页长的汇编语言代码还转换成了列表5.4中给出的函数，而且，这个函数的允许顺序和反汇编代码完全一样，实现的逻辑也一摸一样。

如果你想知道我重构出来的源代码与Microsoft真正的源代码到底有多相似的话，你可以考虑一下这种情况：如果你使用正确的编译器版本和正确的编译器选项设置来编译我重构出来的源代码，就会生成与前边NTDLL.DLL反汇编代码完全一致的汇编代码，一个字节都不差。我们所说的正确的编译器指的是Microsoft Visual C++ .NET 2003软件中的Microsoft 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86。

如果你想自己亲自做一下的话，请记住，Windows不是用编译器的默认设置编译出来的。下面列出的是我编译出与NTDLL.DLL中的代码完全一样代码时使用的优化选项和代码生成选项设置。我使用的四个优化选项是：/Ox——打开最大优化；/Og——打开全局优化；/Os——生成长度最短的代码，会牺牲代码的运行速度）；/Oy——确保使用帧指针。我还打开了/GA选项，该选项专门针对Windows应用程序进行代码优化。

标准的逆向工程实战，很少会需要重构如此精确的源代码。一般来说，找出基本的数据结构以及函数总体的逻辑结构，对于大多数逆向的目的来说就已经足够满足了。为了编译出与原来完全一致的二进制代码而确定正确的版本编译优化参数是一个很好的练习，不过对大多数逆向工程来说是没有什么价值的。

哈哈！在你已经完成了你的第一次逆向尝试——还是一个相当复杂和棘手的函数。如果你之前没有做过任何逆向尝试，即使对上面的讨论看不太懂也别着急——一旦你完全理解了有关的数据结构，再回头来看这个函数的话，你会发现它变得简单了多了。我认为，面对这样一个大的逆向任务，如果你基本了解了代码所完成的任务以及数据的组织，再来解读这个函数可能你的收获会更大。

5.4.5  RtlInsertElementGenericTable

我们继续往下看，通过观察RtlInsertElementGenericTable来学习怎样给表添加一个元素。列表5.5列出了RtlInsertElementGenericTable的反汇编代码。

列表5.5  用OllyDbg生成的RtlInsertElementGenericTable反汇编代码

我们已经讨论过前两条指令了——它们的作用是创建堆栈帧。接下来的这条指令将EDI寄存器的内容压入堆栈。一般来说，在一个函数中使用PUSH指令不外乎以下三种情况：

^, 保存一个寄存器的值到堆栈中，用作函数的局部变量。在这个函数的结尾处会将这个值弹出堆栈。如果是这种情况的话其代码很容易辨认，因为在压入堆栈的时候是哪个寄存器的值必须在弹出的时候还交给这个寄存器（即要反序出栈）；

^, 在进行函数调用之前要把参数压入堆栈；

^, 在拷贝数值的时候，有时会在PUSH指令后面紧跟一条POP指令，用于将这个值加载到其他的寄存器中。这样的指令序列比较少见，但是某些编译器时常会产生这种代码。

在这个函数中，我们必须试着弄清楚：EDI是被作为ntdll.7C92147B（后边紧接着的就是对ntdll.7C92147B的调用）的最后一个参数压入堆栈的，还是为了保护现场而将它的值压入堆栈保存。因为你可以看到在EDI的值被压入堆栈之后立刻就有一个新的值写入了EDI，你还可以看到在函数的最后又将值从堆栈弹出并返还给了EDI，你知道这是编译器把EDI寄存器腾出来用于在函数中存储局部变量。

这个函数中接下来的两条指令比较有趣：

第一条指令把传给这个函数的第一个参数的值（我们早已知道[EBP+8]是指传给函数的第一个参数的地址）写入EDI寄存器（用作局部变量）。第二条指令把指向的第一个参数的指针存入EAX寄存器。注意这里的MOV指令和LEA指令之间的区别！MOV指令实际上是把内存地址[ebp+8]处的值取出来，而LEA指令只是计算出“EBP+8”的结果，并把结果写入EAX寄存器。

马上又出来一个问题：EAX是不是像EDI一样是另一个局部变量呢？为了回答这个问题，我们先来看一下接下来的代码：

你可以看到压入堆栈的第一个参数是EAX的值，这给我们的第一感觉就是EAX并非用作一个局部变量，而是编译器把它用作一个临时存储单元，这是因为要把第一个参数的指针压入堆栈需要用两条指令来完成。这在汇编语言中是一种很常见的限制条件：大多数指令都不像LEA和MOV指令那样能够接收比较复杂的参数。因此，编译器就只能使用MOV或LEA指令，并将MOV或LEA指令的输出存储到一个寄存器中，之后接下来的指令就可以使用该寄存器了。

我们再回到代码中，很快你就可以在ntdll.7C92147B处看到一个的函数，这个函数共接收两个参数。记住，在stdcall调用约定（stdcall调用约定是大多数Windows代码使用的调用约定）中，参数是逆序压入堆栈的，所以第一个PUSH指令（将EAX压入堆栈那一条）实际上压入的是第二个参数。ntdll.7C92147B函数接收的第一个参数是[ebp+C]，它实际上是传给RtlInsertElementGenericTable函数的第二个参数。

RtlLocateNodeGenericTable

现在我们顺着RtlInsertElementGenericTable函数中对ntdll.7C92147B处的函数的调用往下看，分析分析那个函数，我们暂且称它RtlLocateNodeGenericTable。完整的RtlLocateNodeGenericTable函数反汇编代码如列表5.6所示。

列表5.6  ntdll.7C92147B处的内部非导出（nonexported）函数的反汇编代码

在开始对这个函数进行逆向工程之前，必须先考虑一下列表5.6中开头的几行代码，这些代码有几处稍微有点儿奇怪。我们先看第一行：“MOV EDI，EDI”，这句代码什么也没做！它实际上只是被编译器当作占位符（placeholder）放在这里的一条空代码（dead code），以防有人想捕获（trap）这个函数。这里所说的“捕获”是指：某些外部组件增加一条JMP指令，只要被捕获函数被调用就将这条JMP指令用作通知信号。通过在每个函数的开头位置放一条这样的占位指令，Microsoft公司实际上是为NTDLL中所有的捕获函数设置一个统一的记号。需要指出的是，这种占位符只有在比较新的Windows版本中（Windows XP的Service Pack 2中）才开始使用，所以不一定能在你的计算机系统上找到这些占位符。

下面几行代码也比较奇怪。在建立了常规的堆栈帧之后，这个函数会从EDI寄存器中读取数据，尽管在这个函数中EDI到目前为止还没有被访问过。是不是这时EDI寄存器的值是随机的呢？

如果你再看一下RtlInsertElementGenericTable的代码（见列表5.5），你会发现：好像在调用列表5.6的函数之前已经将传给RtlInsertElementGenericTable函数的第一个参数的值（这个值可能是根TABLE数据结构的地址，root TABLE data structure）加载到EDI寄存器了。这暗示了编译器使用EDI寄存器是为了直接向RtlLocateNodeGenericTable函数传递那个指针，但问题是，哪种调用约定使用EDI传递参数呢？答案是没有一种标准的调用约定这样做，但是编译器却选择了这种方式。这说明编译器控制了这个函数的所有的入口点（points of entry）。

总的来说，当在对象文件中定义了一个函数之后，编译器是无法知道这个函数将来会用在什么地方。这个函数可能会被链接器（linker）导出，并被其他模块调用，也有可能在同一个模块中被其他的对象文件调用。但无论是哪种情况，编译器必须遵照指定的调用约定，只有这样才能保证与那些未知的调用程序（callers）相兼容。除非你使用static关键字显式地把函数定义为当前对象文件的内部函数，这样就告知编译器只有当前源文件内的函数可以调用这个函数，编译器会将这种静态函数按照效率更高的非标准接口进行编译。

在这个特别的例子中，编译器充分利用了这个函数的static（静态）关键字——将一些参数放在寄存器中传递给函数，从而尽最大的可能减少对堆栈的使用。这是完全可行的，因为无论是在主调函数（caller）中还是在被调函数（callee）中，编译器都可以完全控制所有寄存器的分配。

从传送到堆栈上的字节数（从那句RET指令可以看出是8个字节），在加上EDI寄存器在未经初始化的情况下就被用来传递参数了这一事实，我们可以保险地认为这个函数共接收三个参数。因为EDI寄存器这个参数的存在，我们还不知道这些参数的次序，但是根据前面一个函数的情况，我们可以大胆地猜测根数据结构总是作为第一个参数传递进来的。正如我所说，RtlInsertElementGenericTable函数将传递给它的第一个参数的值写入了EDI寄存器，所以我们基本上可以肯定地说EDI中包含了我们的根数据结构。

我们现在接着看实际函数体开头的几行代码。

在这几行代码中，你可以很快看出EDI被当作一个指向某个地方的指针来用，这也支持EDI中的内容是根数据结构这一假设。在这里，代码测试了第一个成员（地址是offset+0）是不是0（要牢记你是在逆向条件代码），如果是0的话函数就跳转到ntdll .7C924E8C。

你可能已注意到了一个有趣的现象：ntdll.7C924E8C这个地址离我们当前正在看的代码的距离很远！实际上，ntdll.7C924E8C都不在列表5.6中——这个地址位于可执行文件中的一个完全独立的区域中。这是怎么回事呢——为什么一个函数会像这样被拆分开后分散到整个可执行文件的不同位置呢？实际上，这样做与一些Windows内存管理问题有关。

还记得我们在第3章中讨论过的工作集（working sets）吗？在创建可执行模块的时候，其中最重要的一个问题就是要以一种使模块装入内存时占用尽可能少的物理内存的方式来组织模块。因为Windows只将当前正使用的区域装入物理内存，这个模块（指NTDLL.DLL，其他Windows组件也基本上一样）使用一种特殊的组织方式——把最常用的代码部分放在模块的开头位置，而把其他极少执行的代码放在模块的结尾部分。这个组织过程称为“工作区间调整（working-set tuning）”，我们将在附录A中详细讨论。

现在，你试着想想，从这个条件块被重定位到更高的内存地址（而且距离很远）这一事实你能推断出些什么信息来？这极可能意味着这个条件块很少被执行！一般情况下，使得某个条件块极少被执行的原因有好几种，但可能90%的情况是因为：该条件块实现的是某种出错处理代码。出错处理代码是一种典型的条件语句块，它们被执行的几率非常小。

我们现在转到ntdll.7C924E8C处，看看它到底是不是一段出错处理代码。

如我们所预期的，这段代码所做的就是将EAX清零后跳转到函数结尾处。虽然还不是很肯定，但是所有的证据都表明这确实是一段出错处理代码。

到这里，你可以接着读一读ntdll.7C92148B那个条件语句后面的代码，那里的代码很显然就是函数体。

回调

RtlLocateNodeGenericTable函数的函数体的中有一个有些不同寻常的函数调用，这个调用看上去好像是整个函数的焦点。让我们来看一下这段代码。

这段代码所完成的工作很特别，我们之前都没有遇到过。显然前面的五条指令是用来调用同一个函数的部分，但是请注意一下所调用的“地址”。这个地址不是我们常常见到的那种硬编码地址，而是由“EDI+18”这个偏移地址处的值给出的。这就揭示了在根table数据结构中偏移地址+18处存放着另一个成员——大概是一个回调函数。如果你回顾一下RtlInitializeGenericTable函数，你会看到偏移地址+18处加载的是传递给RtlInitialize GenericTable函数的第二个参数，这就是说，偏移地址+18处包含的是某种类型的用户定义的回调函数。

这个在“EDI+18”处的函数好像有三个参数：第一个是table数据结构，第二个是传给当前函数（即RtlLocateNodeGenericTable函数）的第二个参数，第三个是“ESI+18”。记住，ESI寄存器中在前边已经加载了根数据结构在偏移地址+0处的值，这表明偏移地址+0处包含了某种其他类型的数据结构，而且回调函数获得的是指向该数据结构中偏移地址+18处的指针。在这里，你还不知道这是个什么样的数据结构。

当这个回调函数返回之后，你可以测试它的返回值，如果返回值为零的话，代码将跳转到ntdll.7C924F14。同样，ntdll.7C924F14也是一个在RtlLocateNodeGenericTable函数体之外的地址，难道这里也是一段错误处理代码？我们一起来弄个清楚。下面是在ntdll.7C924F14处的这段代码。

这段代码将这个未知的数据结构中偏移地址为+4处的值加载到了ESI寄存器，然后测试它是不是零。如果不是零，代码将跳转到ntdll.7C924F22，在ntdll.7C924F22只执行了一条指令后就又跳转到了ntdll.7C92148B（跳转到ntdll.7C92148B也就回到了我们的RtlLocateNodeGenericTable函数的函数体了），但是这个跳转是在把这个未知的数据结构（当前它存储在EAX寄存器中）中偏移地址+4处的值加载到ESI寄存器之后执行的。如果这个未知的数据结构中偏移地址+4处的值是零，代码则往堆栈中压入数字2，然后执行短跳转到ntdll.7C9214B0，ntdll.7C9214B0是RtlLocateNodeGenericTable函数的函数体中的一个地址。

讲到这里，你应该搞清楚目前我们在这些代码中遇到的各种分支结构，这是很重要。当然这要比我们预想的要复杂得多，因为函数RtlLocateNodeGenericTable实际上是被分散地放置在整个模块中了。实际上，对这个未知的数据结构中偏移地址为+4处的值作测试的

结果只有两种：如果它的值是零，则函数就返回主调函数RtlInsertElementGenericTable（ntdll.7C9214B0就在这个函数的结尾部分）；如果它的值不是零，函数将把它的值装入ESI寄存器，然后跳转回ntdll.7C92148B，这就又回到刚才我们分析过的回调调用代码了。

这段代码看上去好像是一个循环，它不断地调用回调函数和遍历（traverse）某种类型的链表（该链表从根数据结构偏移地址+0处开始）。该链表中每个元素的大小好像至少有0x1C个字节，因为在该数据结构的偏移地址+18处是这个回调函数的最后一个参数。

我们来看看如果回调函数返回一个非零值会怎么样。

首先，好像回调函数返回的是某种类型的数而不是一个指针，也有可能返回的是一个Boolean值，但你还无法确认。第一个检查测试了“ReturnValue != 1”，并在条件不满足的情况下将偏移地址+8处的值加载到EAX寄存器中。然后测试赋给EAX的这个值是不是等于零，如果等于零，代码就将EAX的值置为3（使用我们前面讨论过的PUSH-POP方法），其后执行的显然就是函数返回前做收尾代码了。到这里，我们就可以清楚地知道为什么要将值3赋给EAX寄存器了——因为这个函数要把3返回给主调函数。注意是怎样把第二个参数当作指针来处理的，这个指针接收的是当前ESI的值，也就是我们刚才讨论的那个未知数据结构。知道这一点很重要，因为好像这个函数遍历的是一个我们之前未曾遇到过的链表。显然会有一种以根table数据结构的偏移地址为+0处开始的链表。

至此，你已经看到了当回调函数返回0或者返回1时代码的执行情况了。而当回调函数返回一个其他值的时候，代码就会通过你前面看到的条件跳转语句跳转到ntdll.7C9214BB继续执行。下面就是ntdll.7C9214BB处的代码。

这段代码把EAX置为1，然后跳转回ntdll.7C9214B1，ntdll.7C9214B1这里的代码我们前面已经分析过了。回想一下，ntdll.7C9214B1处的代码不会影响EAX寄存器，所以这实际上就是向主调函数返回1。

如果你回到紧接着那个回调函数调用之后的代码，你可以看到：如果检查到[ESI+8]处是个非零值的话，代码就跳转到ntdll.7C924F22，ntdll.7C924F22处的代码我们在前面已经分析过了——它的作用是把EAX寄存器的值赋给ESI寄存器，然后跳回到循环的开始处。

到这里，你已经收集到了足够多的信息，可以对RtlLocateNodeGenericTable这个函数做出一些有根据的推测了。这个函数循环执行一段调用一个回调函数的代码，每次循环过程中都根据接收到的返回值执行不同的操作。这个回调函数接收的参数很像是某种链表的元素，而且该链表的第一个元素是通过根数据结构的偏移地址+0访问的。

循环的连续执行以及转向哪里执行都由回调函数的返回值决定。

1．如果回调函数返回0，则循环到由当前项偏移地址+4处的值给出的下一个项上。如果当前项偏移地址+4处的值是0，则函数返回2；

2．如果回调函数返回1，函数通过当前项偏移地址+8处的值加载下一项。如果当前项偏移地址+8处的值是0，则函数返回3。如果当前项偏移地址+8处的值为非空（non-NULL），函数将根据当前项偏移地址+4处的值转向下一项继续循环。

3．如果回调函数返回了一个其他的值，循环即结束，并将当前项返回给主调函数。这时函数的返回值为1。

高级理论

我们从这些比特、字节以及分支结构等底层的细节问题中走出来，以大局观的视角来看看这些代码，我想这会有助于我们理解程序。我们究竟看到了些什么？这个函数到底是在干什么？当然现在我们还无法给出正确的答案，但是，对回调函数的反复调用、以及根据回调函数的返回值改变遍历的方向，我们可能会想到这个回调函数很可能是用来确定链表中某个元素的相对位置的。它可能被定义为一个元素比较回调函数，它接收到两个元素然后对它们进行比较，而函数的三种返回值可能就分别代表小于、大于或是等于。

现在要弄清楚每个返回值的具体含义还很难。但是如果我们利用前边有关指向上一个元素的指针和指向下一个元素的指针的布置所得到的结论的话，我们就明白了指向下一个元素的指针在前，之后才是指向上一个元素的指针。基于这一点，我们就可以做出如下猜测：

^, 回调函数返回0就表示新元素的值比当前元素的值大，因此我们需要在链表中向前移动；

^, 回调函数返回1则说明新元素的值比当前元素的值小，所以我们需要在链表中向后移动；

^, 返回0或1之外的其他值说明新元素的值与链表中某个元素的值是相同的，所以不能把它添加到链表中。

我们已经向前迈进了一大步了，但是好像还有几小块我们没有搞清楚。比如说，假定未知数据结构中偏移地址+4和+8处的成员确实是指向链表的指针，那为什么对偏移地址+4处的成员（假定它是next指针）进行循环呢？而且当我们找到一个比要找元素值小的元素的时候要根据偏移地址+8处的指针（假定它是prev指针）取一个元素，然后继续对偏移地址+4处的指针进行循环，这是为什么呢？如果这真的是一个链表的话，这就意味着：当你找到一个比要找元素值小的元素的时候，你会返回到前一个元素，然后继续向前搜索。我们不清楚这样的代码会有什么用，反过来想这好像又说明这并非一个链表。更有可能的是，这是一个树结构或者类似的数据类型。偏移地址+4处的指针指向树的一个分支（我们假定这是存放较大元素值的那一个分支），偏移地址+8处的指针指向树的另一个分支。

这个树结构的机理完美地解释了为什么循环会从偏移地址+8处的指针取一个元素然后继续对偏移地址+4处的指针进行循环。假定偏移地址+4处的指针确实指向右结点，而偏移地址+8处的指针指向左结点，这合情合理。这个函数不断地向着值大的元素循环（通过不断地移向右结点），直到找到一个中间元素（middle element）比你要找的元素大的结点（这就表明要找元素应该放在左结点中）。只要运行到这里，这个函数就移向左结点，然后从此处出发继续不断移向右结点，直到找到要找的元素。这就是典型的二叉树搜索算法（binary search algorithm），你可以在Donald E. Knuth所著的《The Art of Computer Programming - Volume 3: Sorting and Searching (Second Edition), Addison Wesley [Knuth3]》中找到它的定义。当然，这个函数可能不是在树中找到某个元素的位置，而可能是为新元素寻找一个合适的插入位置。

回调函数的参数

我们再来看一下传递给这个回调函数的参数，并试着猜猜这些参数的含义。我们已经知道了第一个参数——它是从EDI寄存器读入的，是根数据结构。我们也知道第三个参数是二叉树搜索（我们认为这个二叉树搜索还不能完全肯定）中的当前结点，但是为什么回调函数取这个数据结构中偏移地址+18处的成员呢？很可能+18并不表示数据结构中的偏移地址，更可能是元素头部的总长度，通过对这个元素指针加+18，该函数就简单地跳过了这些头部而直接访问到元素的数据部分，当然这是一个与实现有关的细节。

回调函数的第二个参数就是传递给RtlLocateNodeGenericTable的第一个参数。这怎么可能呢？既然我们已经认定这个函数是一个用来比较元素大小的回调函数，我们就可以放心地假设传给回调函数的第二个参数是指向那个新元素的指针。必定如此，否则这个实现比较的回调函数怎么比？这就说明回调函数接收一个TABLE指针、一个指向要添加的元素

数据的指针和一个指向当前元素数据的指针。这个回调函数就是比较新元素和当前遍历到的元素的大小。我们试着给出这个回调函数的原型定义：

总结发现

我们试着总结一下我们对RtlLocateNodeGenericTable函数的学习成果。因为我们已经掌握了分析传入RtlLocateNodeGenericTable函数的各个参数的方法，就让我们重新看一遍RtlInsertElementGenericTable函数中调用RtlLocateNodeGenericTable函数的代码，试着使用这一方法来学习一下RtlInsertElementGenericTable接收的参数。接下来的是RtlInsertElement GenericTable函数中调用RtlLocateNodeGenericTable函数的代码。

好像传给RtlInsertElementGeneric函数的第二个参数（在[EBP+C]）就是当前要插入的新元素。因为你现在已经知道ntdll.7C92147B处的函数（RtlLocateNodeGenericTable）就是用来定位generic table中的结点的，你现在可以为RtlLocateNodeGenericTable给出一个大致的函数原型。

实际上仍然有许多有关generic table的数据组织的问题我们还没解决。举例来说，我们在RtlGetElementGenericTable函数中碰到的链表是怎样的？它与我们找到的二叉树结构有什么联系？

RtlRealInsertElementWorker

在ntdll.7C92147B处的函数（RtlLocateNodeGenericTable）返回后，RtlInsertElement GenericTable又会调用位于ntdll.7C924DF0的另一个函数，该函数的代码在列表5.7中给出。

你不必多想就能知道这个函数的用途：因为前面的函数只是找到插入新元素的正确结点，所以可以肯定这个函数必然是用来完成真正的插入动作的。

在看这个函数的实现之前，我们先返回去看看在RtlInsertElementGenericTable中是怎样调用这个函数的。既然你现在已经知道了一些RtlInsertElementGenericTable函数中处理的数据，我想在正式反汇编这个函数之前你应该能够猜测出一些有关这个函数的信息。下面就是在RtlInsertElementGenericTable函数中调用这个函数的代码。

看上去好像这个位于ntdll.7C924DF0的函数接收了六个参数。我们逐个分析一下这些参数，看看能不能弄清楚这些参数所包含的内容。

^, 参数6：这段代码紧接在定位新元素的插入位置的调用之后，因此第六个参数实际上就是ntdll.7C92147B处的函数的返回值，它可能是1、2或者3；

^, 参数5：它实际上是传给RtlInsertElementGenericTable函数的第一个参数的地址。不过，这个地址中的内容不再是主调函数传给RtlInsertElementGenericTable函数的值了，它已经被用于从那个搜索程序接收指向二叉树上的结点的指针。这个参数实际上就是指向新元素将要添加到的结点的指针；

^, 参数4：这个参数实际上是传给RtlInsertElementGenericTable的第四个参数。我们还不清楚这个参数中的内容是什么；

^, 参数3：这个参数实际上是传给RtlInsertElementGenericTable的第三个参数。我们还不清楚这个参数中的内容是什么；

^, 参数2：基于我们前面的分析，我们知道传给RtlInsertElementGenericTable的第二个参数实际上就是我们要添加的新元素；

^, 参数1：EDI寄存器中的内容是根table数据结构。

我们试着根据这些信息写出这个函数的一个临时的原型。

现在你已经对RtlRealInsertElementWorker函数有了基本的了解。至此，我想你已经准备好看这个函数的完整代码列表并试着分析它的工作方式了。RtlRealInsertElementWorker函数的完整的反汇编代码见列表5.7。

列表5.7  位于ntdll.7C924DF0处的函数的反汇编代码

列表5.7（续）

和列表5.6中给出的函数一样，这个函数也是以一个什么都不干的“MOV EDI，EDI”指令开始。但是，与前一个函数不同的是，这个函数好像并没有通过寄存器来接收参数，这说明可能在定义这个函数的时候没有使用static关键字。这个函数首先检查它接收到的参数SearchResult的值（就是它接收的最后一个参数），如果“SearchResult == 1”将会跳转到远离这个函数的位置（即ntdll.7C935D5D）。我们稍后再处理这种情况。

下面是当“SearchResult == 1”这个条件不满足的情况下将会执行的代码。

看起来这个TABLE数据结构中包含有另一个回调指针。在偏移地址+1C处好像是另一个可接收两个参数的回调函数。我们来分析一下这两个参数，看看这个回调函数是干什么的。第一个参数的值来自ESI寄存器，很明显是TABLE的指针。那么第二个参数是什么呢？

实际上它是传给RtlRealInsertElementWorker函数的第三个参数的值再加上0x18个字节（十六进制）。当你在早些时候查看RtlRealInsertElementWorker函数接收的参数时，你的大脑会是一片空白，但是，0x18这个数怎么这么耳熟。还记得为何RtlLocateNodeGenericTable函数在把当前结点的指针传给TABLE_COMPARE_ELEMENTS回调函数之前要给它加上0x18（就是十进制的24）吗？我猜想“加24个字节”是一种跳过元素的头部而到达真正的元素数据的方法。这就证实了我们的假设——好像generic table中的每个元素都有一个24个字节大小的头部，头部后面才是元素的数据。

现在我们深入地分析一下这个函数，试着搞清楚这个函数是如何工作的以及那个回调函数是上干什么的。下面列出的是当回调函数返回后执行的代码。

这段代码测试了回调函数的返回值。如果返回值是0的话，函数就跳转到远处的一个代码块（在ntdll.7C94D4BE）。我们来看一下这个代码块。

这看起来好像是一段失败模式的代码，它实际上给主调函数返回的是0（译注：因为是通过远跳转执行到这里的，这表明这段代码很少会被执行到）。注意一下这段代码是怎样

检查位于[EBP+14]的第四个参数是不是“非零”的。如果是“非零”的话该函数就把它当作一个指针对待，并向该指针所指的内存单元中写入一个值为零的字节（因为我们知道EBX在此处要变成0）。好像第四个参数是一个指向某个布尔值的指针，用这个布尔值来告知主调函数这个函数是成功了还是失败了。

我们继续来看当回调函数返回一个非空值（non-NULL value，即指非空的指针）会出现什么情况。不难看出这段代码把回调函数的返回值作为地址，初始化了新分配的元素的头部。在试着弄清楚这段初始化过程的细节之前，我们还是暂停一下，试着琢磨一下这段代码告诉了我们哪些有关这个我们刚考察过的回调函数的信息。好像这个回调函数是用来为新创建的元素分配内存的。我们这样推断是因为EBX寄存器现在存放的是这个回调函数的返回值，它肯定是用作当前正在初始化的新元素的指针。知道这些后，我们试着定义出这个回调函数。

我是怎样知道第二个参数就是元素的大小呢？这很简单，因为这个参数的值是从RtlInsertElementGenericTable的主调函数传递给RtlRealInsertElementWorker函数，并增加了24，最后送给了TABLE_ALLOCATE_ELEMENT。显然，调用RtlInsertElementGenericTable函数的应用程序会向该函数提供元素的大小，而在函数中加24是因为还要加上元素的头部这24个字节。因此，我们现在还知道传给RtlInsertElementGenericTable函数的第三个参数也是用户提供的元素长度。另外，我们之前已经知道第四个参数是一个指向这个函数输出的布尔量的可选指针。那就让我们一起更正前边给出的RtlInsertElementGenericTable函数的原型吧。

你可能已经注意到了，我们已经收集到了大量有关RtlInsertElementGenericTable函数所接收的参数的信息。现在我们可以开始看RtlInsertElementGenericTable函数的原型了。

到此为止，你已经获得了大量有关这个API函数及与其相关的数据结构的知识。可能确实没有必要试着弄清楚结点的头部中的每个成员的含义，不过，我们还是看看这段代码，试着弄明白新元素是怎样链接到现有数据结构中的。

链接元素

首先，你可以看到这个函数是通过EBX来访问元素的头部的，然后这个函数又把[EBX+C]的内容赋给EAX，然后通过EAX来访问成员。这就说明在元素头部偏移地址+C处有一个数据结构。编译器通过另外一个寄存器（即EAX）访问这些成员是出于什么考虑？为什么不直接通过EBX寄存器访问所有这些成员呢？

另外，你现在可以明显地看出generic table同时维护一个链表和一个树结构。EAX中存放的是链表头部的起始地址（LIST_ENTRY *），而EBX则是用来访问二叉树成员的。这个函数在将树结点连接到树上之前要检查SearchResult参数：如果SearchResult为零，代码将跳转到ntdll.7C924E88，这个地址恰好在这个函数的函数体末尾之后。下面是ntdll.7C924E88处的代码。

在这种情况下，将结点添加到二叉树的根部。如果SearchResult为非零，代码将继续往下执行——当“SearchResult != 2”成立，执行到的代码显然是一个if-else代码块。如果进入了这个条件块（当“SearchResult != 2”时），代码就取得pNode参数（在RtlLocateNodeGenericTable函数中找到的结点），并将新创建的元素作为当前结点（即pNode）的左子结点（偏移地址为+8）添加到二叉树上。如果“SearchResult == 2”，代码将跳转到下面的指令执行。

这里，新创建的元素是作为pNode的右子结点（偏移地址为+4）添加到二叉树中的。显然，搜索结果（即指SearchResult的值）为我们提供了新元素的值大于pNode的值还是小于pNode的值的信息。就在这个“if-else”语句块之后，指向pNode的指针被存放在新

元素中偏移地址+0处。这表明结点头部中偏移地址+0处存储的是指向其父结点的指针。你现在可以正确地写出结点头部的数据结构了。

拷贝元素

在为新元素分配内存空间并把它添加到pNode之后，你就会看到一段有趣的代码，其实这段代码相当常见，相信你在反汇编IA-32汇编语言代码时会经常遇到类似的代码。我们来看看这段代码。

这段代码将ElementData载入ESI，新结点头部结尾处的指针载入EDI，ElementData / 4载入ECX（译注：指令“SHR ECX, 2”应为将ECX中的值除以4，相关信息可参考附录B，原文误为“ElementSize * 4”），然后开始拷贝元素数据，一次拷贝4个字节。注意这里有两条拷贝指令：其中，第一条拷贝指令用于一次次地拷贝4个字节的数据，而第二条拷贝指令用于检查是否还有剩余的数据没有拷贝，如果有的话就继续拷贝（注意第一条MOVS指令用的参数是DWORD PRT而第二条MOVS指令用的是BYTE PTR操作数）。

我之所以说这是一段很常见的代码是因为这是一个经典的memcpy函数实现。实际上，很可能源代码中包含了对memcpy函数的一次调用，并且编译器把它作为一个内部函数来处理的（内部函数在第7章中有一个简单的讨论）。

展开Table

我们来看下一段的代码。你要注意的是有两条不同的代码执行路径可以带我们跳转到这里。其中第一条就是我们刚才讲述的路径：调用回调函数、初始化数据结构；第二条是在RtlRealInsertElementWorker函数开头的第一个分支语句（在ntdll.7C924DFC处）处当满

足“SearchResult == 1”时所执行的路径。需要指出的是，第二条路径的分支语句并不是直接跳转到这里，而是通过ntdll.7C935D5D处的重定位块跳转过来的。不管我们是通过哪条路径执行到这里的，我们现在还是看看这里的代码做了些什么吧。

这段代码调用了RtlSplay函数（这个名字你见过的，因为我们导出了这个函数——记住，我可没有用Windows debug symbol文件啊！）。RtlSplay函数接收一个参数：如果“SearchResult == 1”的话，这个参数就是传给RtlRealInsertElementWorker的pNode参数；如果是其他情况的话，RtlSplay就把我们刚刚插入的新元素的指针作为参数。之后，RtlSplay函数把pTable的树根结点指针作为返回值返回，这说明RtlSplay函数返回了一个树的结点，但是你现在还不知道这个结点是什么呢！

接下来的代码检查那个可选的布尔指针，如果该指针存在且“SearchResult == 1”，则将该指针所指的值置为TRUE。然后，函数将返回值加载到EAX寄存器中。原来，RtlRealInsertElementWorker函数只是返回指向新分配的元素的数据的指针。下面是更正了的RtlRealInsertElementWorker函数原型。

另外，因为RtlInsertElementGenericTable函数返回的是RtlRealInsertElementWorker函数的返回值，你还可以进一步完善RtlInsertElementGenericTable函数的原型。

伸展树

至此，还有一件事情你不不太确信，那就是RtlSplay函数。我在这里不想讲这个RtlSplay函数，因为它的代码又长又难理解，而且考虑到这个RtlSplay函数的实现代码好像分散在整个模块之中，这使得更难读懂了。事实上，即使你理解RtlSplay函数，你也可以顺顺利利地开始使用generic table函数。话说回来，即使是为了确保你能全面地理解generic table的数据结构，你还是应该大致了解一下RtlSplay函数的功能。

RtlSplay函数中实现的算法相当的复杂，不过，大致查看一下这个函数，你会发现它完成的功能与树结构的恢复平衡（rebalancing）有关。在二叉树中，恢复平衡指的是对树的结构进行重构、使得所有的子结点尽可能平均地分布在父结点两侧。通常，恢复平衡就意味着要去检查树的根结点是不是树中所有结点值的中间值。因为在generic table中的各个元素都是用户定义的，所以RtlSplay就必须得通过调用用户代码中的回调函数来比较元素的大小，而在这个函数中没找到这样的回调函数。

再仔细地考察一下RtlSplay函数，你会发现它的主要工作是选取一个特定的结点并提升它在树中的位置（你可能想在调试器中运行RtlSplay函数，以便对这一过程有一个更清晰的认识）。最后，这个函数返回的是最初出发的那个结点的指针，不过，现在这个结点已经成为整个树结构的根结点了，而且树中所有其他的元素都平均分布在这个元素的左子树和右子树上了。

当我意识到RtlSplay函数的“所作所为”后，整个generic table就豁然开朗了。其实，generic table是用伸展树（splay tree。译注：之所以叫“伸展树”，是因为这种树的左半部分中大部分结点都分布左子结点上，而右半部分中大部分结点都分布右子结点上，外形通常像个“八”字）实现的（参见文献[Tarjan] Robert Endre Tarjan, Daniel Dominic Sleator. Self-adjusting binary search trees. Journal of the ACM (JACM). Volume 32 , Issue 3, July 1985.），它实际上就是一种经过特殊组织规划的二叉树。有关如何恰当地组织二叉树这个问题已经有大量的研究报导了，相应的组织二叉树的技术方法也有不少（如果你是个有耐心的人的话，Knuth为我们深入地讨论了组织二叉树各种技术方法，你可以参考文献[Knuth3] Donald E. Knuth. The Art of Computer Programming—Volume 3: Sorting and Searching (Second Edition). Addison Wesley.）。当然，所有这些技术方法的终极目标是使得我们能够使用尽可能少的迭代次数找到要找的元素。

伸展树（也称为自调整二叉搜索树，self-adjusting binary search tree）是其中一种组织二叉树的方案。在伸展树中，无论是哪个结点，只要涉及它（在任何操作中），它就会立即上升到树的顶端。这种方案使得二叉树像某种缓存器，最近用过的元素往往垂手可得，而最少用到的元素被塞到了树的最底层。按照定义，伸展树总是将最近使用过的元素轮换到二叉树的顶部，这就解释了为什么在添加了一个新元素后就要立即调用RtlSplay函数（新

添加的元素成了二叉树的根结点）。另外，你在删除或者搜索一个元素的代码后面也会看到对RtlSplay函数的调用。

图5.1到图5.5展示了RtlSplay函数是怎样将一个新添加的元素逐级上移、直到该元素成为树结构的根结点。

5.4.6  RtlLookupElementGenericTable

你还记得在开始深入研究generic table之前我提到过的两个看上去好像是负责检索元素的函数（RtlGetElementGenericTable和RtlLookupElementGenericTable）吗？因为你已经知道RtlGetElementGenericTable函数是通过元素的索引号来查找元素的，那么，RtlLookupElementGenericTable函数必定是用于为generic table提供某种搜索能力的。我们来看一看RtlLookupElementGenericTable（见列表5.8）。

图5.1  加入新元素之后的二叉树。新元素被加到了树中最合适的位置，但是其他元素都没动

图5.2  展开操作的第一步之后的二叉树。新元素朝着树的根结点向上移

                     动了一级，刚才是新元素的父结点现在变成了新元素的子结点了

图5.3  展开操作的第二步之后的二叉树。新元素又向上移动了一级

图5.4  展开操作的第三步之后的二叉树。新元素又向上移动了一级

列表5.8  RtlLookupElementGenericTable的反汇编代码

图5.5  展开操作完成之后的二叉树。新元素现在是树的根

         结点了，而且所有其他元素都以它为中间值排在两边

从RtlLookupElementGenericTable这个名字，你就可以猜出这个函数是用来对generic table执行二叉树搜索的，并且它很可能需要两个参数——TABLE结构和一个指向其参数的元素数据的指针。好像这个函数的真正实际是在ntdll.7C9215DA处，所以我们来看一下这个函数。注意一下调用ntdll.7C9215DA这个函数时对堆栈的灵活运用。前两个参数和传给RtlLookupElementGenericTable函数的参数完全相同。而后两个参数显然是指向ntdll.7C9215DA函数返回时某种输出数据的指针，显然根本就没用这两个参数，但是为了避免为输出数据分配局部变量，编译器就使用了用来向这个函数传递参数的堆栈空间。这两个堆栈位置在读出并被传递给ntdll.7C9215DA函数之后就不再需要了。列表5.9给出了ntdll.7C9215DA函数的反汇编代码。

列表5.9  ntdll.7C9215DA函数的反汇编代码，我们暂时将它命名为RtlLookupElementGenericTableWorker

至此，你已经对generic table很熟悉了，基本上不再需要研究这个函数（即指RtlLookupElementGenericTable）了——我们已经讨论过这个API（还是RtlLookupElement GenericTable）使用的两个核心函数了：RtlLocateNodeGenericTable（ntdll.7C92147B）和RtlSplay。RtlLocateNodeGenericTable函数用来定位要找的元素的位置，和在RtlInsert ElementGenericTable函数中该函数的用途一样。在RtlLocateNodeGenericTable函数返回之后，就该调用RtlSplay了，因为伸展树在添加、删除或者查找一个元素之后就要重新展开一次。当然，只有RtlLocateNodeGenericTable找到要找的元素才会调用RtlSplay函数。

根据传递给RtlLocateNodeGenericTable函数的参数，你应该可以马上看出RtlLookupElementGenericTable函数接收的两个参数是TABLE指针和Element的指针。至于返回值，“ADD EAX，18”指令告诉我们：这个函数在获得找到的结点后，跳过这个结

点的头部从而取得了它要返回的值。正如你所想的那样，这个函数返回的是指向找到元素的数据的指针。

5.4.7  RtlDeleteElementGenericTable

到这里我们已经讲述了generic table用法的基本情况，包括在generic table中添加、检索和搜索元素。现在还剩下一种情况我们没有讲，即删除元素。在generic table中是怎样删除元素的？我们来简要地看一下RtlDeleteElementGenericTable的反汇编代码，如列表5.10所示。

列表5.10  RtlDeleteElementGenericTable的反汇编代码

RtlDeleteElementGenericTable函数由三个主要的步骤组成。首先它使用了我们熟悉的RtlLocateNodeGenericTable函数（ntdll.7C92147B）来定位要删除的元素。然后它调用（导出的）RtlDelete函数完成实际的删除工作。我就不深入讨论RtlDelete函数实现从一个二叉树中删除元素的具体算法了，但有一点需要强调的是：在执行完真正的删除动作之后，它还要调用RtlSplay函数来重新整理这个树结构。

RtlDeleteElementGenericTable函数调用的最后一个函数很有趣。这个函数好像是调用用户代码的回调函数，这个回调函数的指针存放TABLE数据结构中偏移地址+20处。我们可以很容易地猜出这是一个用于释放早些时候在TABLE_ALLOCATE_ELEMENT回调函数中分配的内存空间的元素释放（element-free）回调函数，它对应于之前的TABLE_ALLOCATE_ELEMENT回调函数，其功能是把TABLE_ALLOCATE_ELEMENT为指定元素分配的空间释放掉。下面是TABLE_FREE_ELEMENT回调函数的原型：

这里有两点需要注意。第一点，很明显TABLE_FREE_ELEMENT函数没有返回值，即使有也肯定是RtlDeleteElementGenericTable函数忽略了这个返回值（看看代码中是如何TABLE_FREE_ELEMENT这个回调函数返回之后紧接着将AL寄存器置为1的）。第二点，正如你在前面总是看到的那样，Element指针将会指向NODE数据结构的起始位置，而不是元素数据部分的起始位置，这一点你一定要牢记。这是因为主调函数为元素分配了一整块内存，这里头包括了为头部分配的内存，所以这里就要由主调函数来把整块内存释放掉了。

RtlDeleteElementGenericTable函数返回的是一个布尔值：如果RtlLocateNodeGeneric Table函数找到了要删除的元素，这个布尔值就是TRUE；如果RtlLocateNodeGenericTable返回NULL的话，这个布尔值就是FALSE。

5.4.8  思路整理

在完成类似这个逆向工程这么大的逆向任务之后，我建议你把所找到的信息整理一下，弄一个小文档。这是总结你在逆向过程中所获得的信息的非常好的方法，不用说，在站起来喝一杯咖啡或者一杯巧克力奶（我个人的最爱）之后大部分人会忘记自己刚才的逆向“战利品”。

你可以把下面的列表中给出的generic table API函数定义看作是它们的正式定义，这些都是建立在我们在逆向工作中所推断出来的结论的基础上完成的。列表5.11给出了内部数据结构的定义，列表5.12给出了回调函数的原型，列表5.13给出了这些API的函数原型。

列表5.11  本章中发现的内部generic table数据结构的定义

列表5.12  必须由主调函数（caller）实现的generic table回调函数原型

列表5.13  基本的generic table APIs函数原型