Posts Tagged ‘Lists in Linux’

Deep Down Inside the Linux Kernel .. Part 2

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
{
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

For Eg:

typedef struct
{
int data;
struct list_head k_list; //The linux list
}Node;

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 .

#include “linux/kernel.h”
#include “linux/module.h”
#include “linux/init.h”
#include “linux/sched.h”
#include “linux/list.h”
#include “linux/slab.h”
typedef struct
{
int data;
struct list_head list;
}Node;

int abhi_init(void)
{
int i;
Node *node;
struct list_head *head=NULL,*Next=NULL;
for(i=0;idata=i;

INIT_LIST_HEAD(&node->list);

if(head ==NULL)
{
head=&node->list;
Next=head;

}
else
{
list_add(&node->list,Next);
Next=Next->next;

}

}

printk(“\nPrinting data”);
printk(“\nThe value is %d ” , (list_entry(head,Node,list))->data );

list_for_each(Next,head)
{
node=list_entry(Next,Node,list);
printk(“\nThe value is %d “,node->data);

}

return 0;
}

void abhi_exit(void)
{

printk(“\nModule Exiting “);
}

module_init(abhi_init);
module_exit(abhi_exit);
MODULE_LICENSE(“GPL”);

Happy Kernel Hacking!!!!!!!!!!