In the world of the Linux kernel, data structures are like the foundation of a building, supporting the efficient operation of the entire system. Linked lists, as a flexible and commonly used data structure, play a crucial role in the kernel. Today, we will delve into the implementation of linked lists in the Linux kernel—list.h—and unveil its mysteries.
1. Why Do We Need Kernel Linked Lists?
Traditional implementations of linked lists often tightly couple data and node structures, resulting in poor code reusability. The Linux kernel linked list adopts a unique design philosophy: embedding linked list nodes within data structures, thereby decoupling them from data types. This design allows kernel linked lists to be flexibly applied in various scenarios, significantly enhancing code reusability.
2. Core Data Structures in list.h
The core data structure in list.h is a doubly circular linked list node:
struct list_head { struct list_head *next, *prev;};This structure is very simple, containing only two pointers to the previous and next nodes. Note that it does not include any data fields, which is the brilliance of the kernel linked list—it does not care what the data is, only managing the connections between nodes.
3. Initialization and Basic Operations of the Linked List
1. Initializing the Linked List
There are two ways to initialize a linked list: static initialization and dynamic initialization.
// Static initializationLIST_HEAD(my_list);// Dynamic initializationstruct list_head my_list;INIT_LIST_HEAD(&my_list);2. Adding Nodes
There are two main functions for adding nodes: list_add and list_add_tail.
// Insert new node at the headlist_add(struct list_head *new, struct list_head *head);// Insert new node at the taillist_add_tail(struct list_head *new, struct list_head *head);3. Deleting Nodes
To delete a node, use the list_del function:
// Remove specified node from the linked listlist_del(struct list_head *entry);4. The Magic Macros for Traversing the Linked List
In the kernel linked list, traversing the list is accomplished through several powerful macros. These macros utilize the offsetof and container_of core macros, allowing us to easily find the containing data structure from the linked list node.
1. The offsetof Macro
The offsetof macro is used to calculate the offset of a structure member relative to the start address of the structure:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)2. The container_of Macro
The container_of macro is one of the most powerful macros in the kernel, calculating the address of the structure from the member’s address, structure type, and member name:
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})3. Linked List Traversal Macros
The most commonly used linked list traversal macros are list_for_each and list_for_each_entry:
// Traverse linked list nodeslist_for_each(pos, head) // Process node// Directly traverse the data structure containing the linked list nodelist_for_each_entry(pos, head, member) // Process data structureAmong them, list_for_each_entry is the most commonly used traversal macro, directly returning a pointer to the data structure containing the linked list node, allowing easy access to the data.
5. Practical Example: Managing Student Information with Kernel Linked Lists
Below, we will demonstrate how to use kernel linked lists through a practical example. Suppose we want to manage student information for a class, where each student has a name, age, and score.
#include <linux/init.h>#include <linux/module.h>#include <linux/list.h>#include <linux/slab.h>// Define student information structurestruct student { char name[20]; int age; float score; struct list_head list; // Embedded linked list node};// Define class linked list headstatic LIST_HEAD(class_list);static int __init student_init(void){ struct student *stu; // Create the first student node stu = kmalloc(sizeof(*stu), GFP_KERNEL); strcpy(stu->name, "Zhang San"); stu->age = 20; stu->score = 90.5; list_add_tail(&stu->list, &class_list); // Add to the tail of the linked list // Create the second student node stu = kmalloc(sizeof(*stu), GFP_KERNEL); strcpy(stu->name, "Li Si"); stu->age = 21; stu->score = 88.0; list_add_tail(&stu->list, &class_list); // Add to the tail of the linked list // Traverse the linked list and print student information printk(KERN_INFO "Class Student Information:\n"); list_for_each_entry(stu, &class_list, list) { printk(KERN_INFO "Name: %s, Age: %d, Score: %.1f\n", stu->name, stu->age, stu->score); } return 0;}static void __exit student_exit(void){ struct student *stu, *next; // Traverse and delete all nodes list_for_each_entry_safe(stu, next, &class_list, list) { list_del(&stu->list); kfree(stu); } printk(KERN_INFO "Module unloaded successfully\n");}module_init(student_init);module_exit(student_exit);MODULE_LICENSE("GPL");In this example, we first define a structure containing student information, which embeds a list_head type member. We then create two student nodes and add them to the linked list, followed by using the list_for_each_entry macro to traverse the list and print student information. Upon module unloading, we safely traverse and delete all nodes using the list_for_each_entry_safe macro.
6. Conclusion
The design philosophy of the Linux kernel linked list is very clever. By embedding linked list nodes within data structures, it achieves decoupling from data types, greatly enhancing code reusability. Additionally, with powerful macro definitions, the kernel linked list provides a simple and efficient operational interface, allowing us to easily manage various data. Mastering the use of kernel linked lists is crucial for a deeper understanding of the Linux kernel and for writing high-quality kernel modules.
We hope that through this article, you have gained a deeper understanding of Linux kernel linked lists. In your future kernel development, consider trying this flexible data structure, and we believe it will bring you many surprises.