Lists in Linux kernel
This tutorial will give you a small working code of creating a list which is supposed to be quite difficult coz the kernel is not documented . So even understanding code which used lists and creating your own list becomes quite tedious . So decided to dedicate an article on this one .
The linux kernel has some very efficient implementation of list . It can perform insertion , deletion in O(1) . It’s pretty easy to guess that it’s a double linked list . It is a circularly double linked list . The most brilliant thing about this is it does have a header node . Kernel hackers are proud about this implementation . The reason is that the can traverse the list starting at any node in the list untill the node is reached again . This removes the special code to take care of the corner cases . If you want to write some kernel code which need a list , you should only use the list provided by linux otherwise your code will never be accepted into the mainstream kernel , otherwise you are sure to get strange reaction from the kernel community . I can say the same reaction that you would get if use vmalloc() in kernel code or even worse . So better dnt dare .
The linux implementation of list is in #include “linux/list.h”
You can create a structure using struct list_head structure Eg : struct list_head sample_list;
Internally list_head is implemented as follows
struct list_head *next;
struct list_head *prev;
This list itself is of no use . You have to embed this structure inside your own structure
struct list_head k_list; //The linux list
Next is allocating space and initialisation
Node *node=(Node *)kmalloc(sizeof(Node) , GFP_KERNEL ) ; //Note that this function would sleep . So use it in interupt handlers only when you want to crash your system 🙂
INIT_HEAD_LIST(&node->k_list) ; //To initialse the list
A number of functions are available to manipulate list .But aim is to tell you how to create , initialise list and how to use it which are supposed to be quite non intutive .
To Add a item to the list use
list_add(struct list_head *node , struct list_head *list ) which adds “node” to the right of the “list” .
To iterate through the list use
list_for_each(struct list_head *temp , struct_list_head *list) which is expanded to
for(temp=list->next ; temp !=list ; temp=temp->next ) //Hope you understand this . Kernel provides a macro function to achieve this
The most important take away point is as follows . Take for example our structure Node . The kernel list(k_list) inside our structure points to the next node in the kernel list . It does not point to the next Node . We need to find the address of Node structure to access its variables . We use list_entry() to achieve this
list_entry(temp,Node,k_list ) where temp is the address of the list item in the Node structure . Node is the type of the structure .k_list is the name of the list inside our structure .
I wrote a sample code to create a list which i though would be handy for others .
struct list_head list;
struct list_head *head=NULL,*Next=NULL;
printk(“\nThe value is %d ” , (list_entry(head,Node,list))->data );
printk(“\nThe value is %d “,node->data);
printk(“\nModule Exiting “);
Happy Kernel Hacking!!!!!!!!!!