6、链表操作

1、课程目标

1. 理解内核双向链表结构
2. 掌握LIST_ENTRY的使用方法
3. 学会安全的链表操作
4. 理解链表在内核编程中的应用

---

2、名词解释

术语	解释
LIST_ENTRY	双向链表节点结构
CONTAINING_RECORD	从链表节点获取外层结构的宏
Flink	Forward Link，前向指针
Blink	Backward Link，后向指针
Head	链表头节点

---

3、使用工具

工具	用途
WinDbg	!list命令遍历链表
dt命令	显示结构成员

---

4、技术原理

4.1、LIST_ENTRY结构

┌─────────────────────────────────────────────────────────────┐
│                   双向链表结构                               │
│                                                             │
│       ┌──────────┐    ┌──────────┐    ┌──────────┐        │
│  ┌───→│  Node1   │───→│  Node2   │───→│  Node3   │───┐    │
│  │    │  Flink ──┼───→│  Flink ──┼───→│  Flink ──┼───┤    │
│  │    │  Blink   │←───┼── Blink  │←───┼── Blink  │   │    │
│  │    └──────────┘    └──────────┘    └──────────┘   │    │
│  │          ↑                                   │         │
│  │          │         循环链表                   │         │
│  │          └───────────────────────────────────┘         │
│  │                                                        │
│  └────────────────────────────────────────────────────────┘
│                                                             │
│  typedef struct _LIST_ENTRY {                              │
│      struct _LIST_ENTRY *Flink;  // 指向下一个             │
│      struct _LIST_ENTRY *Blink;  // 指向上一个             │
│  } LIST_ENTRY;                                             │
└─────────────────────────────────────────────────────────────┘

4.2、CONTAINING_RECORD宏原理

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

// 示例：从LIST_ENTRY获取外层结构
typedef struct _MY_DATA {
    ULONG       Id;
    LIST_ENTRY  ListEntry;  // 偏移为4
    CHAR        Name[32];
} MY_DATA;

// 如果pEntry指向ListEntry，获取MY_DATA指针：
// pMyData = CONTAINING_RECORD(pEntry, MY_DATA, ListEntry);
// 实际计算：pMyData = (MY_DATA*)((char*)pEntry - 4)

---

5、代码实现

5.1、示例1：基础链表操作

// ListBasics.c - 基础链表操作
#include <ntddk.h>

// 数据结构
typedef struct _PROCESS_INFO {
    ULONG       ProcessId;
    ULONG       ParentId;
    WCHAR       ProcessName[64];
    LIST_ENTRY  ListEntry;      // 链表节点
} PROCESS_INFO, *PPROCESS_INFO;

// 全局链表头
LIST_ENTRY g_ProcessListHead;
KSPIN_LOCK g_ProcessListLock;

VOID InitializeProcessList() {
    // 初始化链表头
    InitializeListHead(&g_ProcessListHead);
    KeInitializeSpinLock(&g_ProcessListLock);
}

// 添加到链表尾部
VOID AddProcessInfo(PPROCESS_INFO Info) {
    KIRQL oldIrql;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    InsertTailList(&g_ProcessListHead, &Info->ListEntry);
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
}

// 添加到链表头部
VOID AddProcessInfoHead(PPROCESS_INFO Info) {
    KIRQL oldIrql;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    InsertHeadList(&g_ProcessListHead, &Info->ListEntry);
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
}

// 从链表移除
VOID RemoveProcessInfo(PPROCESS_INFO Info) {
    KIRQL oldIrql;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    RemoveEntryList(&Info->ListEntry);
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
}

// 遍历链表
VOID EnumerateProcessList() {
    KIRQL oldIrql;
    PLIST_ENTRY entry;
    PPROCESS_INFO info;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    
    // 遍历链表
    for (entry = g_ProcessListHead.Flink;
         entry != &g_ProcessListHead;
         entry = entry->Flink) {
        
        // 从LIST_ENTRY获取外层结构
        info = CONTAINING_RECORD(entry, PROCESS_INFO, ListEntry);
        
        DbgPrint("[List] PID: %d, Name: %ws\n", 
                 info->ProcessId, info->ProcessName);
    }
    
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
}

// 查找进程
PPROCESS_INFO FindProcessById(ULONG ProcessId) {
    KIRQL oldIrql;
    PLIST_ENTRY entry;
    PPROCESS_INFO info;
    PPROCESS_INFO result = NULL;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    
    for (entry = g_ProcessListHead.Flink;
         entry != &g_ProcessListHead;
         entry = entry->Flink) {
        
        info = CONTAINING_RECORD(entry, PROCESS_INFO, ListEntry);
        
        if (info->ProcessId == ProcessId) {
            result = info;
            break;
        }
    }
    
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
    
    return result;
}

// 检查链表是否为空
BOOLEAN IsProcessListEmpty() {
    return IsListEmpty(&g_ProcessListHead);
}

// 清空链表
VOID ClearProcessList() {
    KIRQL oldIrql;
    PLIST_ENTRY entry;
    PPROCESS_INFO info;
    
    KeAcquireSpinLock(&g_ProcessListLock, &oldIrql);
    
    while (!IsListEmpty(&g_ProcessListHead)) {
        entry = RemoveHeadList(&g_ProcessListHead);
        info = CONTAINING_RECORD(entry, PROCESS_INFO, ListEntry);
        ExFreePoolWithTag(info, 'corP');
    }
    
    KeReleaseSpinLock(&g_ProcessListLock, oldIrql);
}

5.2、示例2：安全遍历（边遍历边删除）

// SafeIteration.c - 安全遍历链表
#include <ntddk.h>

typedef struct _CONNECTION_INFO {
    ULONG       ConnectionId;
    ULONG       ClientIp;
    USHORT      ClientPort;
    BOOLEAN     Active;
    LIST_ENTRY  ListEntry;
} CONNECTION_INFO, *PCONNECTION_INFO;

LIST_ENTRY g_ConnectionList;
KSPIN_LOCK g_ConnectionLock;

// 安全删除：使用临时指针保存下一个节点
VOID RemoveInactiveConnections() {
    KIRQL oldIrql;
    PLIST_ENTRY entry;
    PLIST_ENTRY nextEntry;
    PCONNECTION_INFO conn;
    
    KeAcquireSpinLock(&g_ConnectionLock, &oldIrql);
    
    entry = g_ConnectionList.Flink;
    
    while (entry != &g_ConnectionList) {
        // 先保存下一个节点（因为删除后entry->Flink可能无效）
        nextEntry = entry->Flink;
        
        conn = CONTAINING_RECORD(entry, CONNECTION_INFO, ListEntry);
        
        if (!conn->Active) {
            // 从链表移除
            RemoveEntryList(entry);
            
            // 释放内存
            ExFreePoolWithTag(conn, 'nnoC');
            
            DbgPrint("[SafeRemove] Removed inactive connection\n");
        }
        
        // 移动到下一个
        entry = nextEntry;
    }
    
    KeReleaseSpinLock(&g_ConnectionLock, oldIrql);
}

// 使用for循环的安全遍历删除
VOID RemoveConnectionById(ULONG ConnectionId) {
    KIRQL oldIrql;
    PLIST_ENTRY entry, next;
    PCONNECTION_INFO conn;
    
    KeAcquireSpinLock(&g_ConnectionLock, &oldIrql);
    
    for (entry = g_ConnectionList.Flink, next = entry->Flink;
         entry != &g_ConnectionList;
         entry = next, next = entry->Flink) {
        
        conn = CONTAINING_RECORD(entry, CONNECTION_INFO, ListEntry);
        
        if (conn->ConnectionId == ConnectionId) {
            RemoveEntryList(entry);
            ExFreePoolWithTag(conn, 'nnoC');
            break;
        }
    }
    
    KeReleaseSpinLock(&g_ConnectionLock, oldIrql);
}

5.3、示例3：InterlockedXxx无锁链表操作

// LockFreeList.c - 无锁链表操作
#include <ntddk.h>

// 单向链表（无锁）
SLIST_HEADER g_SListHead;

typedef struct _SLIST_ITEM {
    SLIST_ENTRY SListEntry;
    ULONG       Data;
} SLIST_ITEM, *PSLIST_ITEM;

VOID InitializeSList() {
    // 初始化单向链表头（16字节对齐）
    InitializeSListHead(&g_SListHead);
}

VOID PushItem(ULONG data) {
    PSLIST_ITEM item;
    
    // 分配必须对齐
    item = (PSLIST_ITEM)ExAllocatePoolWithTag(
        NonPagedPool, sizeof(SLIST_ITEM), 'tslS');
    
    if (item) {
        item->Data = data;
        
        // 原子入栈
        InterlockedPushEntrySList(&g_SListHead, &item->SListEntry);
    }
}

PSLIST_ITEM PopItem() {
    PSLIST_ENTRY entry;
    
    // 原子出栈
    entry = InterlockedPopEntrySList(&g_SListHead);
    
    if (entry) {
        return CONTAINING_RECORD(entry, SLIST_ITEM, SListEntry);
    }
    
    return NULL;
}

USHORT GetSListDepth() {
    return ExQueryDepthSList(&g_SListHead);
}

VOID FlushSList() {
    PSLIST_ENTRY entry;
    PSLIST_ITEM item;
    
    // 清空链表，返回所有项
    entry = InterlockedFlushSList(&g_SListHead);
    
    while (entry) {
        item = CONTAINING_RECORD(entry, SLIST_ITEM, SListEntry);
        entry = entry->Next;
        
        ExFreePoolWithTag(item, 'tslS');
    }
}

5.4、示例4：内核链表实战 - 遍历进程链表

// ProcessListWalk.c - 遍历系统进程链表
#include <ntddk.h>

// EPROCESS结构偏移（Windows版本相关）
// 需要使用WinDbg或逆向确定
#define EPROCESS_ACTIVEPROCESSLINKS_OFFSET  0x448  // Win10 x64示例
#define EPROCESS_IMAGEFILENAME_OFFSET       0x5A8
#define EPROCESS_UNIQUEPROCESSID_OFFSET     0x440

VOID WalkActiveProcessList() {
    PEPROCESS currentProcess;
    PLIST_ENTRY processListHead;
    PLIST_ENTRY processEntry;
    PEPROCESS process;
    ULONG pid;
    PUCHAR imageName;
    
    // 获取当前进程
    currentProcess = PsGetCurrentProcess();
    
    // 获取ActiveProcessLinks（链表节点）
    processListHead = (PLIST_ENTRY)((PUCHAR)currentProcess + 
                                    EPROCESS_ACTIVEPROCESSLINKS_OFFSET);
    
    // 遍历链表
    processEntry = processListHead->Flink;
    
    DbgPrint("[ProcessWalk] ===== Active Process List =====\n");
    
    while (processEntry != processListHead) {
        // 从LIST_ENTRY获取EPROCESS
        process = (PEPROCESS)((PUCHAR)processEntry - 
                              EPROCESS_ACTIVEPROCESSLINKS_OFFSET);
        
        // 获取进程ID
        pid = *(PULONG)((PUCHAR)process + EPROCESS_UNIQUEPROCESSID_OFFSET);
        
        // 获取进程名（15字节ANSI）
        imageName = (PUCHAR)process + EPROCESS_IMAGEFILENAME_OFFSET;
        
        DbgPrint("[ProcessWalk] PID: %5d  Name: %s\n", pid, imageName);
        
        processEntry = processEntry->Flink;
        
        // 安全检查，防止无限循环
        if (processEntry == processListHead->Flink) {
            break;
        }
    }
    
    DbgPrint("[ProcessWalk] ===== End of List =====\n");
}

// 使用官方API遍历进程（更安全）
VOID EnumerateProcessesSafe() {
    NTSTATUS status;
    PEPROCESS process = NULL;
    ULONG pid = 0;
    
    // 遍历所有进程ID
    for (pid = 4; pid < 65536; pid += 4) {
        status = PsLookupProcessByProcessId((HANDLE)(ULONG_PTR)pid, &process);
        
        if (NT_SUCCESS(status)) {
            DbgPrint("[Enumerate] PID: %d, Name: %s\n", 
                     pid, PsGetProcessImageFileName(process));
            
            // 必须解引用
            ObDereferenceObject(process);
        }
    }
}

5.5、示例5：泛型链表封装

// GenericList.c - 泛型链表封装
#include <ntddk.h>

typedef struct _GENERIC_LIST {
    LIST_ENTRY  Head;
    KSPIN_LOCK  Lock;
    ULONG       Count;
    ULONG       Tag;
} GENERIC_LIST, *PGENERIC_LIST;

typedef struct _GENERIC_LIST_ITEM {
    LIST_ENTRY  ListEntry;
    ULONG       DataSize;
    UCHAR       Data[1];  // 可变大小数据
} GENERIC_LIST_ITEM, *PGENERIC_LIST_ITEM;

// 初始化链表
VOID GenericList_Init(PGENERIC_LIST List, ULONG Tag) {
    InitializeListHead(&List->Head);
    KeInitializeSpinLock(&List->Lock);
    List->Count = 0;
    List->Tag = Tag;
}

// 添加数据
NTSTATUS GenericList_Add(PGENERIC_LIST List, PVOID Data, ULONG Size) {
    PGENERIC_LIST_ITEM item;
    KIRQL oldIrql;
    
    item = (PGENERIC_LIST_ITEM)ExAllocatePoolWithTag(
        NonPagedPool,
        sizeof(GENERIC_LIST_ITEM) - 1 + Size,
        List->Tag
    );
    
    if (!item) {
        return STATUS_INSUFFICIENT_RESOURCES;
    }
    
    item->DataSize = Size;
    RtlCopyMemory(item->Data, Data, Size);
    
    KeAcquireSpinLock(&List->Lock, &oldIrql);
    InsertTailList(&List->Head, &item->ListEntry);
    List->Count++;
    KeReleaseSpinLock(&List->Lock, oldIrql);
    
    return STATUS_SUCCESS;
}

// 获取并移除头部数据
NTSTATUS GenericList_Pop(PGENERIC_LIST List, PVOID Buffer, PULONG Size) {
    PLIST_ENTRY entry;
    PGENERIC_LIST_ITEM item;
    KIRQL oldIrql;
    NTSTATUS status = STATUS_NO_MORE_ENTRIES;
    
    KeAcquireSpinLock(&List->Lock, &oldIrql);
    
    if (!IsListEmpty(&List->Head)) {
        entry = RemoveHeadList(&List->Head);
        item = CONTAINING_RECORD(entry, GENERIC_LIST_ITEM, ListEntry);
        List->Count--;
        
        if (*Size >= item->DataSize) {
            RtlCopyMemory(Buffer, item->Data, item->DataSize);
            *Size = item->DataSize;
            status = STATUS_SUCCESS;
        } else {
            // 缓冲区太小，放回链表
            InsertHeadList(&List->Head, entry);
            List->Count++;
            *Size = item->DataSize;
            status = STATUS_BUFFER_TOO_SMALL;
        }
        
        if (NT_SUCCESS(status)) {
            ExFreePoolWithTag(item, List->Tag);
        }
    }
    
    KeReleaseSpinLock(&List->Lock, oldIrql);
    
    return status;
}

// 清空链表
VOID GenericList_Clear(PGENERIC_LIST List) {
    PLIST_ENTRY entry;
    PGENERIC_LIST_ITEM item;
    KIRQL oldIrql;
    
    KeAcquireSpinLock(&List->Lock, &oldIrql);
    
    while (!IsListEmpty(&List->Head)) {
        entry = RemoveHeadList(&List->Head);
        item = CONTAINING_RECORD(entry, GENERIC_LIST_ITEM, ListEntry);
        ExFreePoolWithTag(item, List->Tag);
    }
    
    List->Count = 0;
    
    KeReleaseSpinLock(&List->Lock, oldIrql);
}

// 获取计数
ULONG GenericList_GetCount(PGENERIC_LIST List) {
    return List->Count;
}

---

6、课后作业

1. 实现一个LRU缓存，使用双向链表
2. 编写线程安全的优先级队列
3. 实现链表排序功能
4. 使用WinDbg的!list命令遍历内核链表

---

7、扩展阅读

• Windows内核链表实现
• SLIST性能分析
• 无锁数据结构设计