概述

Linux内核使用了大量精心设计的数据结构来管理复杂的系统资源。这些数据结构经过高度优化，能够在各种场景下提供优异的性能。本专题深入剖析内核中最常用的数据结构。

一、链表（list_head）

1.1 基本结构

// include/linux/list.h
structlist_head {
structlist_head *next, *prev;
};

1.2 链表操作实现

// list_demo.c - 内核链表使用示例
#include<linux/init.h>
#include<linux/module.h>
#include<linux/kernel.h>
#include<linux/slab.h>
#include<linux/list.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Kernel Linked List Demo");

// 定义数据结构
structstudent {
int id;
char name[32];
int score;
structlist_headlist;// 链表节点
};

// 定义链表头
staticLIST_HEAD(student_list);

// 添加学生
staticvoidadd_student(int id, constchar *name, int score)
{
structstudent *stu;

    stu = kmalloc(sizeof(*stu), GFP_KERNEL);
if (!stu)
return;

    stu->id = id;
strncpy(stu->name, name, sizeof(stu->name) - 1);
    stu->score = score;

// 初始化链表节点
    INIT_LIST_HEAD(&stu->list);

// 添加到链表
    list_add_tail(&stu->list, &student_list);

    printk(KERN_INFO "Added student: %d - %s\n", id, name);
}

// 遍历链表
staticvoidshow_students(void)
{
structstudent *stu;

    printk(KERN_INFO "=== Student List ===\n");

// 正向遍历
    list_for_each_entry(stu, &student_list, list) {
        printk(KERN_INFO "ID: %d, Name: %s, Score: %d\n",
               stu->id, stu->name, stu->score);
    }

// 反向遍历
    printk(KERN_INFO "=== Reverse Order ===\n");
    list_for_each_entry_reverse(stu, &student_list, list) {
        printk(KERN_INFO "ID: %d, Name: %s\n", stu->id, stu->name);
    }
}

// 查找学生
staticstruct student *find_student(int id)
{
structstudent *stu;

    list_for_each_entry(stu, &student_list, list) {
if (stu->id == id)
return stu;
    }

returnNULL;
}

// 删除学生
staticvoiddelete_student(int id)
{
structstudent *stu = find_student(id);

if (stu) {
        list_del(&stu->list);
        printk(KERN_INFO "Deleted student: %d\n", id);
        kfree(stu);
    }
}

// 安全遍历并删除
staticvoiddelete_all_students(void)
{
structstudent *stu, *tmp;

// 安全遍历（允许删除）
    list_for_each_entry_safe(stu, tmp, &student_list, list) {
        list_del(&stu->list);
        kfree(stu);
    }
}

staticint __init list_demo_init(void)
{
    printk(KERN_INFO "List Demo Module Loaded\n");

// 添加测试数据
    add_student(1001, "Alice", 95);
    add_student(1002, "Bob", 88);
    add_student(1003, "Charlie", 92);

// 显示所有学生
    show_students();

// 查找测试
structstudent *found = find_student(1002);
if (found)
        printk(KERN_INFO "Found: %s\n", found->name);

return0;
}

staticvoid __exit list_demo_exit(void)
{
    delete_all_students();
    printk(KERN_INFO "List Demo Module Unloaded\n");
}

module_init(list_demo_init);
module_exit(list_demo_exit);

1.3 高级链表操作

// list_advanced.c - 链表高级操作
#include<linux/list.h>

// 链表合并
staticvoidlist_demo_splice(void)
{
    LIST_HEAD(list1);
    LIST_HEAD(list2);

// ... 添加元素到 list1 和 list2 ...

// 将list2合并到list1
    list_splice(&list2, &list1);

// 合并并重新初始化list2
    list_splice_init(&list2, &list1);
}

// 链表替换
staticvoidlist_demo_replace(void)
{
structlist_head *old_entry, *new_entry;

// 替换链表中的节点
    list_replace(old_entry, new_entry);

// 替换并重新初始化old
    list_replace_init(old_entry, new_entry);
}

// 移动节点
staticvoidlist_demo_move(void)
{
structlist_head *entry, *head;

// 移动到头部
    list_move(entry, head);

// 移动到尾部
    list_move_tail(entry, head);
}

// 判断链表状态
staticvoidlist_demo_check(void)
{
structlist_head *head, *entry;

// 检查链表是否为空
if (list_empty(head))
        printk("List is empty\n");

// 检查是否是最后一个元素
if (list_is_last(entry, head))
        printk("This is the last entry\n");

// 检查是否只有一个元素
if (list_is_singular(head))
        printk("List has only one entry\n");
}

二、哈希链表（hlist）

2.1 基本结构

// include/linux/list.h
structhlist_head {
structhlist_node *first;
};

structhlist_node {
structhlist_node *next, **pprev;
};

2.2 哈希表实现

// hash_table.c - 哈希表实现
#include<linux/init.h>
#include<linux/module.h>
#include<linux/hashtable.h>
#include<linux/slab.h>

MODULE_LICENSE("GPL");

// 定义哈希表大小（2的幂）
#define HASH_BITS 8
DECLARE_HASHTABLE(my_hash_table, HASH_BITS);

// 数据结构
structhash_entry {
int key;
char data[64];
structhlist_nodenode;
};

// 初始化哈希表
staticvoidinit_hash_table(void)
{
    hash_init(my_hash_table);
}

// 添加元素
staticvoidhash_add_entry(int key, constchar *data)
{
structhash_entry *entry;

    entry = kmalloc(sizeof(*entry), GFP_KERNEL);
if (!entry)
return;

    entry->key = key;
strncpy(entry->data, data, sizeof(entry->data) - 1);

// 添加到哈希表
    hash_add(my_hash_table, &entry->node, key);

    printk(KERN_INFO "Added: key=%d, data=%s\n", key, data);
}

// 查找元素
staticstruct hash_entry *hash_find_entry(int key)
{
structhash_entry *entry;

    hash_for_each_possible(my_hash_table, entry, node, key) {
if (entry->key == key)
return entry;
    }

returnNULL;
}

// 删除元素
staticvoidhash_del_entry(int key)
{
structhash_entry *entry = hash_find_entry(key);

if (entry) {
        hash_del(&entry->node);
        kfree(entry);
        printk(KERN_INFO "Deleted: key=%d\n", key);
    }
}

// 遍历哈希表
staticvoidhash_traverse(void)
{
structhash_entry *entry;
structhlist_node *tmp;
int bkt;

    printk(KERN_INFO "=== Hash Table Contents ===\n");

    hash_for_each_safe(my_hash_table, bkt, tmp, entry, node) {
        printk(KERN_INFO "Bucket[%d]: key=%d, data=%s\n",
               bkt, entry->key, entry->data);
    }
}

// 清空哈希表
staticvoidhash_cleanup(void)
{
structhash_entry *entry;
structhlist_node *tmp;
int bkt;

    hash_for_each_safe(my_hash_table, bkt, tmp, entry, node) {
        hash_del(&entry->node);
        kfree(entry);
    }
}

staticint __init hash_demo_init(void)
{
    printk(KERN_INFO "Hash Table Demo Loaded\n");

    init_hash_table();

// 添加测试数据
    hash_add_entry(100, "Data for key 100");
    hash_add_entry(200, "Data for key 200");
    hash_add_entry(150, "Data for key 150");

// 遍历显示
    hash_traverse();

// 查找测试
structhash_entry *found = hash_find_entry(200);
if (found)
        printk(KERN_INFO "Found: %s\n", found->data);

return0;
}

staticvoid __exit hash_demo_exit(void)
{
    hash_cleanup();
    printk(KERN_INFO "Hash Table Demo Unloaded\n");
}

module_init(hash_demo_init);
module_exit(hash_demo_exit);

三、红黑树（rbtree）

3.1 基本结构

// include/linux/rbtree.h
structrb_node {
unsignedlong  __rb_parent_color;
structrb_node *rb_right;
structrb_node *rb_left;
};

structrb_root {
structrb_node *rb_node;
};

3.2 红黑树实现

// rbtree_demo.c - 红黑树使用示例
#include<linux/init.h>
#include<linux/module.h>
#include<linux/rbtree.h>
#include<linux/slab.h>

MODULE_LICENSE("GPL");

// 数据节点
structrb_object {
int key;
char data[64];
structrb_nodenode;
};

// 红黑树根
staticstructrb_rootmy_tree = RB_ROOT;

// 插入节点
staticintrb_insert(struct rb_root *root, struct rb_object *obj)
{
structrb_node **new = &(root->rb_node), *parent = NULL;

// 找到插入位置
while (*new) {
structrb_object *this = container_of(*new, struct rb_object, node);
int result = obj->key - this->key;

        parent = *new;
if (result < 0)
            new = &((*new)->rb_left);
elseif (result > 0)
            new = &((*new)->rb_right);
else
return-1;  // 键已存在
    }

// 链接节点并重新平衡
    rb_link_node(&obj->node, parent, new);
    rb_insert_color(&obj->node, root);

return0;
}

// 查找节点
staticstruct rb_object *rb_search(struct rb_root *root, int key)
{
structrb_node *node = root->rb_node;

while (node) {
structrb_object *obj = container_of(node, struct rb_object, node);
int result = key - obj->key;

if (result < 0)
            node = node->rb_left;
elseif (result > 0)
            node = node->rb_right;
else
return obj;
    }

returnNULL;
}

// 删除节点
staticvoidrb_delete(struct rb_root *root, int key)
{
structrb_object *obj = rb_search(root, key);

if (obj) {
        rb_erase(&obj->node, root);
        kfree(obj);
        printk(KERN_INFO "Deleted node with key: %d\n", key);
    }
}

// 中序遍历
staticvoidrb_inorder_walk(struct rb_node *node)
{
if (node) {
        rb_inorder_walk(node->rb_left);

structrb_object *obj = container_of(node, struct rb_object, node);
        printk(KERN_INFO "Key: %d, Data: %s\n", obj->key, obj->data);

        rb_inorder_walk(node->rb_right);
    }
}

// 使用rb_first/rb_next遍历
staticvoidrb_iterate(void)
{
structrb_node *node;

    printk(KERN_INFO "=== RB Tree Iterator ===\n");

for (node = rb_first(&my_tree); node; node = rb_next(node)) {
structrb_object *obj = container_of(node, struct rb_object, node);
        printk(KERN_INFO "Key: %d\n", obj->key);
    }
}

// 清理红黑树
staticvoidrb_cleanup(void)
{
structrb_node *node;

while ((node = rb_first(&my_tree))) {
structrb_object *obj = container_of(node, struct rb_object, node);
        rb_erase(node, &my_tree);
        kfree(obj);
    }
}

staticint __init rbtree_demo_init(void)
{
    printk(KERN_INFO "RB Tree Demo Loaded\n");

// 添加测试数据
int keys[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35};
int i;

for (i = 0; i < ARRAY_SIZE(keys); i++) {
structrb_object *obj = kmalloc(sizeof(*obj), GFP_KERNEL);
if (obj) {
            obj->key = keys[i];
snprintf(obj->data, sizeof(obj->data), "Data_%d", keys[i]);

if (rb_insert(&my_tree, obj) == 0) {
                printk(KERN_INFO "Inserted: %d\n", keys[i]);
            } else {
                kfree(obj);
            }
        }
    }

    printk(KERN_INFO "=== In-order Traversal ===\n");
    rb_inorder_walk(my_tree.rb_node);

    rb_iterate();

return0;
}

staticvoid __exit rbtree_demo_exit(void)
{
    rb_cleanup();
    printk(KERN_INFO "RB Tree Demo Unloaded\n");
}

module_init(rbtree_demo_init);
module_exit(rbtree_demo_exit);

编译和测试

Makefile

# 内核源码路径
KDIR ?= /lib/modules/$(shell uname -r)/build

# 模块列表
obj-m += list_demo.o
obj-m += hash_table.o
obj-m += rbtree_demo.o

all:
$(MAKE) -C $(KDIR) M=$(PWD) modules

clean:
$(MAKE) -C $(KDIR) M=$(PWD) clean

test:
	sudo insmod list_demo.ko
	dmesg | tail -20
	sudo rmmod list_demo

	sudo insmod hash_table.ko
	dmesg | tail -20
	sudo rmmod hash_table

	sudo insmod rbtree_demo.ko
	dmesg | tail -20
	sudo rmmod rbtree_demo

数据结构选择指南

实践检查清单

• [ ] 理解内核链表的侵入式设计
• [ ] 掌握container_of宏的使用
• [ ] 实现自定义哈希表
• [ ] 理解红黑树的平衡机制
• [ ] 使用XArray管理稀疏数据
• [ ] 实现无锁数据结构

下一步

学习完内核数据结构后，可以：

• 研究RCU机制和无锁编程
• 学习内核内存管理
• 分析实际内核代码中的数据结构使用