• Windows 驱动开发2 链表的数据结构
  • 一丶链表
    • 1.1 简介
    • 1.2 WDK中的链表结构
    • 1.2.1 链表的使用
    • 1.3 链表API 之初始化节点

Windows 驱动开发2 链表的数据结构

一丶链表

1.1 简介

​ 链表在windows内核开发中是最最最常见的数据结构了。 主要分为单向链表和双向链表。 单向链表的链表节点只有一个链表节点指针。 双向则是两个。 分别是指向前链表节点和后链表节点。

双向链表指向了前后两个节点。所以链表在插入移除上面的操作比单向链表更为方便。

1.2 WDK中的链表结构

typedef struct _LIST_ENTRY {
   struct _LIST_ENTRY *Flink;
   struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;

在内核中链表就是一个结构体定义的数据结构。 而链表的使用就是将其放到 其它结构中。并且通过某种方法来进行链接起来。

1.2.1 链表的使用

首先我们先定义一个链表，作为Node节点。

然后我们定义一个我们自己的结构

如下：

typedef struct _MY_TEST_STRUCT {
	ULONG m_ulDataA;
	ULONG m_ulDataB;
	ULONG m_ulDataC;
	ULONG m_ulDataD;
}MY_TEST_STRUCT,*PMY_TEST_STRUCT;

结构定义好了我们如何使用链表哪？ 我们可以在结构中定义一个Node节点。

如下：

typedef struct _MY_TEST_STRUCT {
	ULONG m_ulDataA;
	ULONG m_ulDataB;
	LIST_ENTRY m_listentry;
	ULONG m_ulDataC;
	ULONG m_ulDataD;
}MY_TEST_STRUCT,*PMY_TEST_STRUCT;

我们定义了一个链表节点 名字为 m_listentry 但是其实我们可以将这个成员定义在任何地方。

我们看下在内存的布局吧。

而如果我们多定义几个结构，并且让他们互相链接起来。那么在内存中表现形式就如下：

我们可以看到 节点A中的 Fink指向节点B中的Fink位置 好好品味我这句话 它并不是指向节点B的首地址， 也就是并不是指向m_ulDataA位置

而Bink则是指向前节点位置的Fink位置。

这里操作系统设计的很巧妙。 通过在任意结构中定义 Node节点 那么这个结构就是一个双向链表的节点。

那么可能有人问了。如果给我一个节点A。 那么我要遍历双向链表的时候要怎么遍历。 因为节点位置不固定，且Flink指向的位置并不是结构体的开头。

其实这个问题很简单。 我们算一下结构体的偏移。

假设 m_listentry节点在任意结构体位置处定义，那么我们只需要计算出 m_listentry结构距离 结构体首地址的偏移即可。

如下：

typedef struct _MY_TEST_STRUCT {
	ULONG m_ulDataA;						//设在内存中的地址为0位置
	ULONG m_ulDataB;						//+4
	LIST_ENTRY m_listentry;                 //+8
	ULONG m_ulDataC;                        
	ULONG m_ulDataD;
}MY_TEST_STRUCT,*PMY_TEST_STRUCT;

通过上面结构体可以看到 +8位置是m_listentry地址。 而我们通过遍历链表所得出的地址也是+8的位置。 那么我们只需要把的出来的地址-8即可得到结构体首地址

例如下：

PMY_TEST_STRUCT BNode = xxx.m_listentry -8 

而如果计算出-8这个偏移。 其实我们可以利用指针原理 来获取偏移量。

如下：

(&(MY_TEST_STRUCT*)0).m_listentry

这里利用了个小技巧，设0地址为结构体首地址。 并且强转为我们自己的结构体。然后再去访问成员变量m_listentry。 但是有人说了0地址直接访问变量肯定是错的。直接会蓝屏。因为0地址根本就不是我们自己的结构。 所以这里还有个设计的小技巧。 我们取的是0的地址。 这样一来我们并没有访问变量了。

所以上面的公式变成了

PMY_TEST_STRUCT BNode = xxx.m_listentry -((&(MY_TEST_STRUCT*)0).m_listentry)

是不是挺恶心的。不过别怕，操作系统给我们定义了一个宏。如下：

#define CONTAINING_RECORD(address, type, field) ((type *)( \
                                                  (PCHAR)(address) - \
                                                  (ULONG_PTR)(&((type *)0)->field)))

这里的宏就是我们上面所说的意思。

看下如何使用吧。

伪代码：

MY_TEST_STRUCT testA;
MY_TEST_STRUCT testB;
PMY_TEST_STRUCT testB = CONTAINING_RECORD(&testB.m_listentry, MY_TEST_STRUCT, m_listentry);

参数一就是我们双向链表得出的地址。 比如 节点A的双向链表位置是+8位置。 那么参数1就是+8地址。

参数二就是结构体类型

参数三就是结构体成员。

看如下图应该更能明白。

1.3 链表API 之初始化节点

链表的头节点是不携带任何内容的，只是表示链表的头部，对链表的所有操作都是从头部开始的。

如果链表只有一个头节点，那么这个链表就是一个空的链表。 头节点的Flink Blink都是指向自身额