概述
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
数据结构选择指南
实践检查清单
下一步
学习完内核数据结构后，可以：
10个月宝宝每天需要喝多少奶粉？
