Linux鏈表操作方式

更新時間：2025年06月10日 16:18:36 作者：隱身模式

這篇文章主要介紹了Linux鏈表操作方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

一、鏈表基礎(chǔ)概念與內(nèi)核鏈表優(yōu)勢
二、內(nèi)核鏈表結(jié)構(gòu)與宏解析
三、內(nèi)核鏈表的優(yōu)點
四、用戶態(tài)鏈表示例
五、雙向循環(huán)鏈表在內(nèi)核中的實現(xiàn)優(yōu)勢
六、典型應(yīng)用場景
七、調(diào)試技巧與常見陷阱
八、實戰(zhàn)案例：Linux 內(nèi)核模塊中的鏈表使用
總結(jié)：開發(fā)建議

本文系統(tǒng)講解 Linux 下 C 語言鏈表的使用原理、最佳實踐及內(nèi)核模塊中的實戰(zhàn)示例，適合嵌入式開發(fā)者、驅(qū)動工程師和系統(tǒng)軟件開發(fā)者。

一、鏈表基礎(chǔ)概念與內(nèi)核鏈表優(yōu)勢

1.1 為什么使用鏈表？

動態(tài)插入/刪除效率高（相比數(shù)組不需要整體移動元素）
內(nèi)存利用率高（按需分配）
常用于隊列、任務(wù)調(diào)度、資源池、驅(qū)動設(shè)備列表等場景

1.2 Linux 內(nèi)核鏈表與用戶態(tài)鏈表的區(qū)別

項目	用戶態(tài)實現(xiàn)	內(nèi)核態(tài)實現(xiàn)
指針結(jié)構(gòu)	自定義指針結(jié)構(gòu)	使用 struct list_head
安全性	程序員自行維護	提供安全宏/內(nèi)聯(lián)函數(shù)
插入/刪除API	手動實現(xiàn)	提供統(tǒng)一接口如 list_add
迭代方式	手動循環(huán)	宏如 list_for_each_entry

二、內(nèi)核鏈表結(jié)構(gòu)與宏解析

struct list_head {
    struct list_head *next, *prev;
};

常用宏/函數(shù)：

INIT_LIST_HEAD(ptr)
list_add(new, head)：頭插法
list_add_tail(new, head)：尾插法
list_del(entry)
list_empty(head)
list_for_each_entry(pos, head, member)
list_for_each_entry_safe(pos, n, head, member)

三、內(nèi)核鏈表的優(yōu)點

雙向循環(huán)結(jié)構(gòu)：從任意節(jié)點出發(fā)都能遍歷完整鏈表
插入刪除不涉及內(nèi)容拷貝：僅修改指針
接口統(tǒng)一、安全可靠：可結(jié)合 container_of 獲取真實結(jié)構(gòu)體指針

四、用戶態(tài)鏈表示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct student {
    int id;
    char name[20];
    struct student *next;
} student_t;

void add_student(student_t **head, int id, const char *name) {
    student_t *new_node = malloc(sizeof(student_t));
    new_node->id = id;
    strncpy(new_node->name, name, sizeof(new_node->name));
    new_node->next = *head;
    *head = new_node;
}

void print_students(student_t *head) {
    while (head) {
        printf("ID: %d, Name: %s\n", head->id, head->name);
        head = head->next;
    }
}

五、雙向循環(huán)鏈表在內(nèi)核中的實現(xiàn)優(yōu)勢

5.1 插入效率

在頭部插入只需兩次指針操作：

list_add(&new_node->list, &head);

5.2 安全遍歷刪除

list_for_each_entry_safe(ptr, tmp, &head, list) {
    list_del(&ptr->list);
    kfree(ptr);
}

六、典型應(yīng)用場景

場景	描述
設(shè)備驅(qū)動管理	管理設(shè)備結(jié)構(gòu)體（如 net_device）
定時器鏈表	內(nèi)核定時器統(tǒng)一調(diào)度
slab 分配器鏈表	管理對象緩存池
進程調(diào)度/等待隊列	管理 PCB / wait queue
協(xié)議棧管理	TCP/UDP 的 socket 鏈表

七、調(diào)試技巧與常見陷阱

7.1 打印鏈表內(nèi)容

#define print_list(head) \
    list_for_each_entry(ptr, head, list) \
        printk(KERN_INFO "Node: %s\n", ptr->name);

7.2 常見錯誤

忘記初始化 INIT_LIST_HEAD
使用已釋放節(jié)點（UAF）
非安全刪除遍歷（未使用 list_for_each_entry_safe）

八、實戰(zhàn)案例：Linux 內(nèi)核模塊中的鏈表使用

8.1 模塊源碼

// mylist_module.c
#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/list.h>

MODULE_LICENSE("GPL");

struct student {
    int id;
    char name[20];
    struct list_head list;
};

static LIST_HEAD(student_list);

static int __init mylist_init(void)
{
    int i;
    struct student *stu;

    printk(KERN_INFO "Loading student list module...\n");

    for (i = 1; i <= 5; ++i) {
        stu = kmalloc(sizeof(*stu), GFP_KERNEL);
        stu->id = i;
        snprintf(stu->name, sizeof(stu->name), "Student%d", i);
        INIT_LIST_HEAD(&stu->list);
        list_add_tail(&stu->list, &student_list);
    }

    return 0;
}

static void __exit mylist_exit(void)
{
    struct student *stu, *tmp;

    printk(KERN_INFO "Unloading student list module...\n");

    list_for_each_entry_safe(stu, tmp, &student_list, list) {
        list_del(&stu->list);
        kfree(stu);
    }
}

module_init(mylist_init);
module_exit(mylist_exit);

8.2 Makefile 編譯模塊

obj-m += mylist_module.o

all:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

8.3 插入與卸載模塊

$ make
$ sudo insmod mylist_module.ko
$ dmesg | tail -n 10
$ sudo rmmod mylist_module
$ dmesg | tail -n 10

總結(jié)：開發(fā)建議

建議項	內(nèi)容
一定初始化鏈表頭	使用 INIT_LIST_HEAD 初始化
刪除節(jié)點用安全宏	list_for_each_entry_safe 防止遍歷時刪除崩潰
內(nèi)存管理責任明確	kmalloc/kfree 成對使用
多線程環(huán)境加鎖	必要時配合 spinlock 或 mutex
定位 bug 用 printk	輸出 prev, next, 數(shù)據(jù)字段調(diào)試鏈表結(jié)構(gòu)

本文涵蓋了從用戶態(tài)鏈表構(gòu)造到 Linux 內(nèi)核模塊鏈表的實戰(zhàn)應(yīng)用，幫助你在驅(qū)動開發(fā)和內(nèi)核開發(fā)中熟練掌握鏈表的構(gòu)造與使用。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: