[ Windows DDP ] Windows 記憶體管理 : 在驅動中使用鏈表

前言 : 
在驅動程式開發中, 經常使用這種資料結構. DDK 為使用者提供兩種鏈表的資料結構, 簡化了對鏈表的操作. 鏈表中可以記錄將整型, 浮點, 字元型或者程式員自訂的資料結構. 鏈表透過指標將這些資料結構組成一條"鏈", 鏈中的每個元素對應著記錄的資料. 對於單向鏈表, 每個元素有一個 Next 指標指向下一個元素. 對於雙向鏈表, 每個元素有兩個指標 : BLINK 指標指向前一個元素 ; FLINK 指向下一個元素. 這裡介紹主要以使用雙向鏈表為主, 單向鏈表操做類似. 

鏈表結構 : 
DDK 提供了標準的雙向鏈表, 雙向鏈表可以將鏈表形成一個環. BLINK 指標指向前一個元素, FLINK 指標指向下一個元素 : 
 
以下是 DDK 提供的雙向鏈表的資料結構 : 

view plaincopy to clipboardprint?

1. typedef struct _LIST_ENTRY {  
2.     struct  _LIST_ENTRY *Flink;  
3.     struct  _LIST_ENTRY *Blink;  
4. } LIST_ENTRY, *PLIST_ENTRY;  

- 鏈表初始化 
每個雙向鏈表都是以一個鏈表頭做為鏈表的第一個元素. 初次使用鏈表頭需要進行初始化. 主要將鏈表頭的 Flink 和 Blink 兩個指標都指向自己. 這意味著鏈表頭所代表的鏈是空鏈. 而初始化鏈表頭用 InitializeListHead 巨集實做. 
如何判斷鏈表是否為空, 可以透過上面定義來判斷鏈表頭的 Flink 和 Blink 是否指向自己. DDK 為程式設計師提供了一個巨集簡化這種檢查, 這就是 IsListEmpty. 
程式設計師需要自己定義鏈表中每個元素的資料類型, 並將 LIST_ENTRY 結構做為自訂結構的一個子域. LIST_ENTRY 的作用是將自訂的資料結構串成一個鏈表. 

- 從首部插入鏈表 
對鏈表的插入有兩種方式, 一種是在鏈表的頭部插入, 一種是在尾部插入. 在頭部插入鏈表使用語句 InsertHeadList, 用法如下 : 
InsertHeadList(&head, &mydata->ListEntry); 

其中 head 是 LIST_ENTRY 結構的鏈表頭, mydata 是使用者定義的資料結構, 而它的子Field:ListEntry 就是 LIST_ENTRY 的資料結構. 假設鏈表中已經有一個元素 Entry1, 如下圖. 現在將另一個元素 Entry2 插入鏈表, 使用 InsertHeadList 插入, 則可得到下面第二個圖 : 
 

- 從尾部插入鏈表 
另一種插入方法是在鏈表的尾部進行插入. 在尾部插入鏈表使用語句 InsertTailList, 用法如下 : 
InsertTailList(&head, &mydata->ListEntry); 

其中 head 是 LIST_ENTRY 結構的鏈表頭, mydata 是使用者定義的資料結構, 而它的 Field:ListEntry 是 LIST_ENTRY 資料結構. 假設鏈表中已經有一個元素 Entry1, 如下圖一所示, 現在將另一個 Entry2 使用 InsertTailList 插入鏈表, 則可得下圖二 : 
 

- 從鏈表刪除 
和插入鏈表一樣, 刪除也有兩種對應方式. 一種是從鏈表頭刪除, 一種是從鏈表尾刪除. 分別對應 RemoveHeadList 和 RemoveTailList 函式. 其原型如下 : 

- RemoveTailList 函式 :

view plaincopy to clipboardprint?

1. PLIST_ENTRY RemoveTailList(  
2.   __inout  PLIST_ENTRY ListHead  
3. );  

- RemoveHeadList 函式 :

view plaincopy to clipboardprint?

1. PLIST_ENTRY RemoveHeadList(  
2.   __inout  PLIST_ENTRY ListHead  
3. );  

而使用方法如下 : 
PLIST_ENTRY pEntry = RemoveHeadList(&head); 
及 
PLIST_ENTRY pEntry = RemoveTailList(&head); 

其中 head 是鏈表頭, pEntry 是從鏈表刪除下來的元素中的 ListEntry. 這裡有一個問題就是如何從 pEntry 得到使用者自定資料結構的指標. 這裡有兩種情況 : 
(1) 自定義資料結構的第一個欄位是 LIST_ENTRY 時, 如 : 

view plaincopy to clipboardprint?

1. typedef struct _MYDATASTRUCT {  
2.     LIST_ENTRY  ListEntry;  
3.     ULONG  x;  
4.     ULONG  y;  
5. } MYDATASTRUCTURE, *PMYDATASTRUCTURE;  

此時, RemoveHeadList 返回的指標可以當作用戶自訂的指標, 即 : 

view plaincopy to clipboardprint?

1. PLIST_ENTRY pEntry = RemoveHeadList(&head);  
2. PMYDATASTRUCTURE pMyData = (PMYDATASTRUCTURE) pEntry;  

(2) 當自訂的資料結構的第一個欄位不是 LIST_ENTRY 時, 如 : 

view plaincopy to clipboardprint?

1. typedef struct _MYDATASTRUCT2 {  
2.     ULONG  x;  
3.     ULONG  y;  
4.     LIST_ENTRY  ListEntry;  
5. } MYDATASTRUCTURE2, *PMYDATASTRUCTURE2;  

此時, RemoveHeadList 返回指標不可以當作用戶自訂的指標, 即 : 

view plaincopy to clipboardprint?

1. PLIST_ENTRY pEntry = RemoveHeadList(&head);  
2. PMYDATASTRUCTURE2 pMyData = (PMYDATASTRUCTURE2) pEntry;  // 發生錯誤  

此時需要透過 pEntry 的位址逆向算出自定資料結構的指標. 一般透過 pEntry 在自訂資料中的偏移量, 用 pEntry 減去這個偏移量, 就會得到使用者自定義結構的指標位址. 為了簡化這個操作, DDK 位程式設計師提供了巨集 CONTAINING_RECORD, 其用法如下 : 

view plaincopy to clipboardprint?

1. PLIST_ENTRY pEntry = RemoveHeadList(&head);  
2. PIRP pIrp = CONTAINING_RECORD(pEntry, MYDATASTRUCTURE2, ListEntry);  

而其返回結果就是使用者自定義結構的指標. DDK 建議無論自定義結構的第一個欄位是否為 ListEntry, 最好都使用 CONTAINING_RECORD 巨集取得自定義資料結構的指標. 

實驗 : 
在介紹完記易體分配和鏈表操作後, 下面進行實驗. 實驗目的在於熟悉驅動程式中, 初始化鏈表, 自定義鏈表資料結構. 而該結構包含一個整型數位, 這個實驗演示了鏈表進行插入, 刪除等操作, 主要代碼如下 : 

- Driver.cpp (LinkedList 測試代碼) :

view plaincopy to clipboardprint?

1. typedef struct _MYDATASTRUCT   
2. {  
3.     ULONG number;  
4.     LIST_ENTRY ListEntry;  
5. } MYDATASTRUCT, *PMYDATASTRUCT;  
6.   
7. #pragma INITCODE  
8. VOID LinkListTest()   
9. {  
10.     LIST_ENTRY linkListHead;  
11.     //初始化鏈表  
12.     InitializeListHead(&linkListHead);  
13.   
14.     PMYDATASTRUCT pData;  
15.     ULONG i = 0;  
16.     //在鏈表中插入10個元素  
17.     KdPrint(("Begin insert to link list"));  
18.     for (i=0 ; i<10 ; i++)  
19.     {  
20.         pData = (PMYDATASTRUCT)  
21.             ExAllocatePool(PagedPool,sizeof(MYDATASTRUCT));  
22.         pData->number = i;  
23.         InsertHeadList(&linkListHead,&pData->ListEntry);  
24.     }  
25.   
26.     //從鏈表中取出，並顯示  
27.     KdPrint(("Begin remove from link list\n"));  
28.     while(!IsListEmpty(&linkListHead))  
29.     {  
30.         PLIST_ENTRY pEntry = RemoveTailList(&linkListHead);  
31.         pData = CONTAINING_RECORD(pEntry,  
32.                               MYDATASTRUCT,  
33.                               ListEntry);  
34.         KdPrint(("%d\n",pData->number));  
35.         ExFreePool(pData);  
36.     }  
37.   
38. }  

請將上述程式碼放到 HelloDDK 中的 DriverEntry 中. 驅動載入後可以看對應 log 資訊如下圖 :