理解 LIST_ENTRY 列表及其在操作系统中的重要性

• 下载源代码 (C++) - 770 B
• 下载源代码 - 3.5 MB

目录

• 引言
• 背景
• 所需软件工具
• 软件工具下载链接
• 快速浏览代码
• LIST_ENTRY内存布局和工作原理
• CONTAINING_RECORD工作原理
• 对LIST_ENTRY的操作
• 使用WinDbg dt命令通过LIST_ENTRY转储MYSTRUCT结构
• 使用WinDbg dt命令转储实时内核中的所有进程
• 使用WinDbg dt命令转储实时内核中进程的所有线程

引言

当我们在操作系统尽可能低的级别编写软件时，我们常常无法奢侈地使用那些花哨、经过充分测试、享誉全球的库，例如 C++ STL、C++ Boost 或类似的库。一个突出的例子是 Windows 内核，其中使用 C++ 本身就被认为不是最高效的做法，而是倾向于使用朴素的 C 来实现纯粹的“裸机”操作，并能完全控制和跟踪编译器生成的每一条指令。这带来了额外的挑战，例如难以维护项目组，而在用户模式下，我们本可以使用 STL 的 vector、map 或 list。

为了应对这种情况，传统上，操作系统开发人员会在操作系统内核中使用简单的数组、列表和树。在这些结构中，我无法过分强调一个典型的双向链表的重要性，它在 Windows 内核中无处不在。在本文中，我将讨论 LIST_ENTRY 数据结构，它在 Windows 内核以及 Windows 用户模式的许多原生部分（特别是 ntdll.dll）中使用，用于维护双向链表。虽然本文展示的示例是针对 Windows 操作系统的，但请注意，在 Linux、BSD 等系统中也使用了完全相同的技术，只是变量名和宏名可能不同。事实上，即使您在阅读本文时，这里讨论的概念也在您的系统上运行，无论您使用的是什么操作系统（Mac、Linux、Windows）或其哪个版本。

可供下载的代码演示了 LIST_ENTRY 和 CONTAINING_RECORD 在一个简单场景中的用法。这段代码用于使用 WinDbg 进行调试，以演示 dt (dump type) 命令转储结构。文章的后半部分将介绍如何使用前半部分介绍的技术进行实时 Windows 内核调试，以转储所有进程的列表，然后转储特定进程中的所有线程。

我建议您先查看代码，并在阅读文章时将其打开，因为我试图通过引用源代码来解释这些概念。此外，本文的读者应了解 C 编程语言。

背景

要理解 LIST_ENTRY 结构和 CONTAINING_RECORD 宏及其用法，对指针和结构有透彻的理解是必不可少的。LIST_ENTRY 和 CONTAINING_RECORD 的文档分别可以在 ListEntry 和 ContainingRecordMacro 找到。对 WinDbg 的初步了解也有助于调试。

本文基于以下 4 个演示文稿，请随时参考它们来巩固您的先备知识。

• https://www.youtube.com/watch?v=xuYKwlV9TR8
• https://www.youtube.com/watch?v=RHVesT9_Kzs
• https://www.youtube.com/watch?v=xzn7qQKHW1I
• https://www.youtube.com/watch?v=yQQLIEM6qp8

所需软件工具

使用的工具是

• WinDbg，最好是最新版本 - 用于调试
• VmPlayer - 用于运行正在调试的目标虚拟机
• 一个操作系统 - 安装在 VmPlayer 中

WinDbg 和 VmPlayer 均可免费下载。我使用了 Windows 7 作为 VmPlayer 的操作系统，但您可以根据需要使用任何高于 Windows 2000 的版本。另外，您不必局限于 vmplayer。您可以选择任何支持 Windows 内核调试的虚拟化基础设施。

软件工具下载链接

• WinDbg - 点击此处
• VmPlayer - 点击此处

请确保下载最新版本的 VMPlayer。

让我们快速看一下代码

如前所述，请在您喜欢的编辑器中打开附件代码。代码包含一个示例结构 MYSTRUCT，其中 LIST_ENTRY 是其一部分。其定义与头文件 wdm.h 中的定义类似。

代码中的用户定义结构如下

//
// MYSTRUCT - structure
//
typedef struct newstruct
{
    int num1;
    int num2;
    char alpha;
    LIST_ENTRY list_entry;
    float exp;

}MYSTRUCT,*PMYSTRUCT;
...

LIST_ENTRY 的结构如下（稍后解释）

//
// LIST_ENTRY structure 
//
typedef struct _LIST_ENTRY
{
    struct _LIST_ENTRY *Flink;
    struct _LIST_ENTRY *Blink;

}LIST_ENTRY,*PLIST_ENTRY;
... 

CONTAINING_RECORD 宏在代码开头定义如下（稍后解释）

//
// CONTAINING_RECORD macro
//Gets the value of structure member (field),given the type(MYSTRUCT, in this code) and the List_Entry head(temp, in this code)
//
#define CONTAINING_RECORD(address, type, field) (\
    (type *)((char*)(address) -(unsigned long)(&((type *)0)->field)))
    
...

我们刚刚了解了游戏中的所有重要参与者。现在，代码中只定义了两个操作，即 InsertHeadList 和 InitializeListHead，它们的定义与 wdm.h 中的定义类似。在 main 函数中，我向列表中添加了两个条目。然后，通过遍历 LIST_ENTRY 并使用 CONTAINING_RECORD 计算 MYSTRUCT 的起始地址来访问结构成员（num1）。因此，代码就像将 2 个节点添加到双向链表中然后读取它们一样简单。

LIST_ENTRY 内存布局和工作原理（相对于源代码）

现在，让我们尝试理解列表的内存布局及其工作原理。 LIST_ENTRY 通常出现在结构体的中间。它包含一个 Flink 和 Blink 指针，分别指向另一个结构体的成员（在源代码中是 MYSTRUCT）的下一个和上一个 LIST_ENTRY 结构体。

在上图中，您可以看到 list_entry（参考上一节中的 MYSTRUCT 声明）的类型是“LIST_ENTRY”，并且它出现在 MYSTRUCT 结构体的中间。另外，请注意每个结构体对象是如何链接的。它不是使用指向 MYSTRUCT 的指针，而是通过指向 LIST_ENTRY 的指针。现在，这也意味着您无法直接访问结构体的成员，因为您的对象指向 LIST_ENTRY 结构体的开头，而不是 MYSTRUCT。因此，您必须从 list_entry 的地址（您当前拥有的地址）计算 MYSTRUCT 的起始地址。为此，使用了宏 CONTAINING_RECORD。

例如，如果您想访问 MYSTRUCT 的 num1，您不能直接访问它，而是需要先计算偏移量，获取 MYSTRUCT 的起始地址，然后访问该元素。这正是源代码所做的。

CONTAINING_RECORD 工作原理（相对于源代码）

现在让我们看一下 CONTAINING_RECORD。CONTAINING_RECORD 的声明乍一看可能很复杂。然而，它的工作原理非常简单。让我们看一下它接受的参数。

1. address：这只是指向 Type（在此示例中为 MYSTRUCT）结构体实例中的一个 *字段*（在此示例中为 list_entry）的指针。
2. type：结构体的类型名称（在源代码中是 MYSTRUCT，需要返回其基地址，通过该基地址可以实现对结构体成员的直接访问）。
3. field：由 address（宏的第一个参数）指向的 field（在此源代码中是 list_entry）的名称，并且该字段包含在 Type（MYSTRUCT）类型的结构体中。

仍然很复杂？让我们深入探讨一下。让我们再次看一下定义。

//
// CONTAINING_RECORD macro
//Gets the value of structure member (field - num1),given the type(MYSTRUCT, in this code) and the List_Entry head(temp, in this code)
//
#define CONTAINING_RECORD(address, type, field) (\
    (type *)((char*)(address) -(unsigned long)(&((type *)0)->field)))
    
...

让我们仔细看看宏定义中的这一部分

(&((type *)0)->field)  

看起来，我们试图从一个 null 指针访问一个字段。也就是说，上述语句本身就会引起问题。事实上，整个表达式并不完全符合 C 标准，尽管它在几乎所有已知的编译器上都能工作。让我们尝试在逻辑上理解正在发生的事情。现在，如您所见，null 指针被类型转换为指向类型（在此例中为 MYSTRUCT）的指针。尝试引用一个字段不会产生任何访问冲突错误，事实上，它前面的“&”起到了关键作用，因为我们并没有真正访问那个内存位置，只是获取了它的地址。因此，它将返回我们引用的字段（在源代码中是 list_entry）的 *偏移量*。换句话说，它在 type 的对象地址为 null 时，给出 field 元素在 type 中的地址。现在我们知道了 LIST_ENTRY 结构体在 MYSTRUCT 中的偏移量，我们只需要从 address（CONTAINING_RECORD 的第一个参数）中减去这个偏移量，就可以得到 **包含结构体**（在源代码中，包含结构体是 MYSTRUCT）的起始地址。

因此，源代码中的 CONTAINING_RECORD(temp,MYSTRUCT,list_entry)->num1 将引用 MYSTRUCT 结构体的 num1。

对源代码中使用了 CONTAINING_RECORD 的 while 循环的解释

//
//
PLIST_ENTRY temp=0;
temp=MyListHead;
while(MyListHead!=temp->Flink)
  {
    temp=temp->Flink;
    int num1=CONTAINING_RECORD(temp,MYSTRUCT,list_entry)->num1;
    printf("num1=%d\n",num1);
  }

上述循环在源代码中的功能是打印结构体 MYSTRUCT 中成员 num1 的每个值。列表的遍历是通过 MYSTRUCT 的 list_entry 完成的。temp 是一个 LIST_ENTRY 类型的元素，它被初始化为 MyListHead（它指向 MYSTRUCT 类型元素的列表中，MYSTRUCT 结构体内的第一个 list_entry）。循环中的条件检查是否已到达列表末尾。temp=temp->Flink 用于遍历到列表中的下一个元素。然而，请注意 Flink 将指向 MYSTRUCT 内部的 list_entry，而不是结构体的开头。但是我们必须显示 num1 的值。为此，使用了源代码中的下一行（int num1=CONTAINING_RECORD(temp,MYSTRUCT,list_entry)->num1;）。COTNAINING_RECORD 的工作原理前面已经解释过。请参考前面部分以了解宏的工作原理。

LIST_ENTRY 操作

虽然 LIST_ENTRY 有很多操作，但源代码只涵盖了两个函数，其余函数可在 wdm.h 中找到供您参考。在本节中，让我们尝试理解 LIST_ENTRY 操作的工作原理及其多态性意义。

• 初始化列表头 ( InitializeListHead(PLIST_ENTRY Listhead))

  InitializeListHead(PLIST_ENTRY Listhead) 的定义如下

  //
  //
  void InitializeListHead( PLIST_ENTRY ListHead)
   {
     ListHead->Flink = ListHead->Blink = ListHead;
   }
      

  在上面的函数中，由于这是一个双向链表，我们初始化了 Flink 和 Blink。并且 Flink 和 Blink 都指向 ListHead。也就是说，这是一个*循环双向链表*。

• 插入新节点 ( InsertHeadList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry))

  InsertHeadList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry) 的定义如下

  //
  //
  void InsertHeadList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry)
  {
      PLIST_ENTRY Flink;
  
      Flink = ListHead->Flink;
      Entry->Flink = Flink;
      Entry->Blink = ListHead;
      Flink->Blink = Entry;
      ListHead->Flink = Entry;
  }

  该函数接受两个参数，其中一个是 listhead（在源代码中是 MyListhead），另一个是 list_entry（它是 MYSTRUCT 结构体的成员）。该函数将新元素添加到头部列表的前面，将现有元素推到后面，否则代码是不言自明的。

LIST_ENTRY 及其相关函数的多态性质

值得注意的是，上述函数接受 LIST_ENTRY 类型指针作为参数，而不是 MYSTRUCT 的指针。这意味着这些函数与它所使用的结构体的类型无关，因为定义与该结构体类型（在源代码中是 MYSTRUCT）无关。这些构造的多态性质允许我们将其与任何 TYPE 一起使用，而无需担心运行时布局。从编程角度来看，这与 C++ 模板一样好，甚至更好，而且没有 C++ 模板的重复代码。

使用 WinDbg dt 命令通过 LIST_ENTRY 转储 MYSTRUCT 结构

现在让我们看一下调试器，并用代码进行一些练习。正如您在下面看到的，调试器命令能够处理 LIST_ENTRY。请按照以下说明进行此练习。这对于本文的下一部分是必需的。

在 WinDbg 中打开给定的源文件（Convert.cpp）。同时在项目文件夹中打开可执行文件（Convert.exe）。在源代码第 89 行，或 while 循环开始处设置一个断点。现在您可以使用以下命令转储结构

1. 在调试器中键入命令 x Convert!MyListHead。
2. MyListHead 的地址将显示在左侧。
3. 在调试器中键入命令 dc address (any d* of your choice should work) （来自步骤 2 的地址）。再执行一次 dc address （来自上一个 dc 输出左侧的第一个地址）。
4. 第一个地址是 MYSTRUCT 中 LIST_ENTRY 结构的地址。
5. 必须从上一步的地址中减去 MYSTRUCT 中 LIST_ENTRY 结构（list_entry 字段）的偏移量，才能获得 MYSTRUCT 的起始地址。
6. 可以使用命令 dt Convert!MYSTRUCT 转储 MYSTRUCT 来获取偏移量。
7. 使用命令 ?addr-offset 将 list_entry 的偏移量从步骤 4 中的地址减去。
8. 现在使用获得的地址，使用以下命令递归地列出 MYSTRUCT 的条目
   • 语法：dt type -l field.Flink address
   • 命令： dt Convert!MYSTRUCT -l list_entry.Flink addr from previous step

如果您在步骤中遇到困难，请参考下图。这是附加演示项目可执行文件的 WinDbg 的命令序列和等效输出。

现在我们准备研究 LIST_ENTRY 在实际生产操作系统场景中的使用。

使用 WinDbg dt 命令转储实时内核中的所有进程（类似于 !process 输出）

请按照以下步骤创建命名管道，并使用它将虚拟机连接到调试器，以便对虚拟机内的操作系统进行实时内核调试。

1. 下载并安装 VmPlayer（参见“软件工具下载链接”以获取下载链接）
2. 在 VMPlayer 中安装目标操作系统。我安装了 Windows 7。
3. 在 VM Player 中添加虚拟串行端口。
   • 打开 VmPlayer
   • 在左侧窗格中选择已安装的操作系统。其属性显示在右侧窗格中。
   • 点击 Edit virtual machine settings
   • 在打开的对话框中，在“*硬件*”选项卡下，点击“添加”
   • 选择硬件类型为“串行端口”并点击下一步
   • 在下一个窗口中选择“输出到命名管道”，然后点击下一步
   • 输入管道名称。（我给了“\\.\pipe\NamedPipe”作为名称。）请务必将其复制到某处。您需要记住它。点击完成。
   • 在“硬件”窗格下选择“串行端口”。其属性显示在右侧窗格中。
   • 启用 使用命名管道 单选按钮。输入您之前输入的名称。点击确定。
4. 现在启动您的虚拟操作系统。（点击“Play Virtual Machine”。）
5. 打开“运行”命令提示符。键入 msconfig
6. “系统配置”对话框打开。
7. 在“*引导*”选项卡下，点击“*高级选项*”，然后勾选 **调试** 复选框。点击确定。
8. 在您的主机上打开 WinDbg。
9. 选择 文件->内核调试
10. 在打开的“内核调试”窗口的“COM”选项卡下，勾选 Pipe 和 Reconnect 复选框。输入您在虚拟机中创建的管道名称（对我来说是 \\.\pipe\NamedPipe）。点击确定。
11. 现在内核调试器等待管道重新连接。重新启动您的虚拟机。然后目标操作系统（虚拟机内的那个，被调试者）将连接到调试器。
12. 连接后，当您在命令窗口看到“KDTARGET : Refreshing KD connection ”消息时，按中断键，然后就可以执行命令了。

实时调试以列出所有进程

现在目标操作系统已连接到调试器，我们可以使用 dt 命令转储目标操作系统（虚拟机内的）中所有当前正在运行的进程。步骤与之前转储 MYSTRUCT 类似。我们将使用 nt!PsActiveProcessHead 而不是 Convert!MyListHead。PsActiveProcessHead 是指向内核 _EPROCESS 结构列表开头的指针。_EPROCESS 结构有一个名为 ActiveProcessLinks 的成员，其类型为 LIST_ENTRY。使用此成员（ActiveProcessLinks），我们可以使用 dt 命令转储内核中所有活动进程的列表。

1. 在调试器中键入命令 x nt!PsActiveProcessHead。
2. ActiveProcessHead 的地址将显示在左侧。
3. 在调试器中键入命令 dc address （来自步骤 2 的地址）以查看 ActiveProcessHead 的内容。第一个地址指向一个类型为 _EPROCESS 的结构。
4. 必须从上一步的地址中减去 _EPROCESS 中 ActiveProcessLinks 的偏移量，才能获得 _EPROCESS 的起始地址。
5. 可以使用命令 dt nt!_EPROCESS 转储 _EPROCESS 来获取偏移量。
6. 使用命令 ?addr-offset 将步骤 3 中的地址与 ActiveProcessLinks 的偏移量相减。
7. 现在使用获得的地址，使用以下命令递归地列出 _EPROCESS 的条目
   • 语法：dt type -l field.Flink address
   • 命令：dt nt!_EPROCESS -l ActiveProcessLinks.Flink addr from previous step
8. 要转储 _EPROCESS 结构中的特定字段，例如以“Thread”开头的字段，请使用此命令.. dt nt!_EPROCESS -l ActiveProcessLinks.Flink -y Thread addr 。

以下快照将使理解更加容易。

现在我们已经获取了 Windows 操作系统上运行的所有进程。现在让我们尝试转储这些进程中的一个进程的所有线程。

使用 WinDbg dt 命令转储实时内核中进程的所有线程

转储特定进程中的线程非常直接，并且与转储所有活动进程类似。_EPROCESS 有一个名为 ThreadListHead 的成员，它将指向一个名为 _ETHREAD 的结构列表。ThreadListHead 的类型为 LIST_ENTRY，其 Flink 指向 _ETHREAD 结构内的 ThreadListEntry。一旦理解了上述思路，这个过程应该会很容易。

1. 出于演示目的，假设您已复制了活动进程（句柄计数 > 0）的地址之一。
2. 使用 dt 命令转储该地址处的 _EPROCESS 结构，以查找 ThreadListHead 的偏移量。
3. 复制转储结构中 ThreadListHead 条目括号内的第一个地址。这将指向 _ETHREAD。
4. 必须从上一步的地址中减去 _ETHREAD 中 ThreadListEntry 的偏移量，才能获得 _ETHREAD 的起始地址。
5. 可以使用命令 dt nt!_ETHREAD 转储 _ETHREAD 来获取偏移量。
6. 使用命令 ?addr-offset 将步骤 3 中的地址与 ThreadListEntry 的偏移量相减。
7. 现在使用获得的地址，使用以下命令递归地转储所有活动线程
   • 语法 : dt type -l field.Flink address
   • 命令 : dt nt!_ETHREAD -l ThreadListEntry.Flink addr from previous step

以下快照将使理解更加容易。

要点

有几个有趣的注意事项需要注意，因为如果不正确理解，它们肯定会导致问题。

• CONTAINING_RECORD 接受结构成员的地址并返回结构体的起始地址。
• dt 命令接受结构体的起始地址来转储其内容，而不是像 CONTAINING_RECORD 那样接受结构成员的地址。
• 可以使用 !process 命令转储进程，使用 !thread 命令转储线程。这两个命令内部都使用了我们刚刚讨论过的相同技术。您可以使用这些命令来验证您的输出。