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都是指向自身额