Creating linked list in liinux Kernel using the list

Linked lists are a very frequently used data structure in the linux kernel and to make the programming easier the linux kernel provides an easy of creating the linked lists. Using the inbuilt method available in the kernel we can create circular doubly linked lists easily and use them in which ever required in the code.

To be able to use this feature available in the kernel we need to add the header file linux/list.h. The structure that is used for creation of the list"list_head" defined in types.h

struct list_head { struct list_head *next, *prev; };

To use this structure for creation of a linked list we need to include the structure as a member of the main structure of which we want to create the list. For example to create a linked list called k_list in which we will create a list of numbers we will have to create the structure as

struct k_list { struct list_head test_list; int temp; };

In the above structure "temp" is the real data that we want to store and test_list, which is a structure of the kind "list_head" will be used for the creation of the link list.

Then we will need to create a head for the linked list which will be used start the creation of the list. To create a head we can make use of th macro INIT_LIST_HEAD, which will declared and initialize the list at runtime, or we can use the function LIST_HEAD to initialize the list at compile time.

Once list has been created we can add nodes to the linked list using the function

list_add(struct list_head *new, struct list_head *head);

Let us say we want to add create a linked list of three nodes of the kind k_list structure shown above. let us first create three structures and populate it with data that we want to store in it.

struct k_list *one,*two,*three,*entry; one=kmalloc(sizeof(struct k_list *),GFP_KERNEL); two=kmalloc(sizeof(struct k_list *),GFP_KERNEL); three=kmalloc(sizeof(struct k_list *),GFP_KERNEL); one->temp=10; two->temp=20; three->temp=30;

Thus we have created three structures "one","two" and "three" of kind k_list in which we have stored data "10","20", and "30" respectively.

Now to form a linked list of these three structures using lines_add

list_add(&one->test_list,&test_head); list_add(&two->test_list,&test_head); list_add(&three->test_list,&test_head);

The first argument to list_add is the pointed to the structure of kind list_head which is a member of k_list and the second argument is a pointer to the head node initialized using INIT_LIST_HEAD.

To traverse through the linked list we can make use of another function available in the kernel

list_for_each(struct list_head *cursor, struct list_head *list) *cursor: Is the pointer to the current location in the list *list: Pointer to the head of the list.

In our example we can use this function as

list_for_each(ptr,&test_head){

Where ptr is

struct list_head *ptr;

Now as we traverse through the list we need to be able to access the data that we have stored in the structure k_list. To be able to ge a pointer to the k_list structures through the pointer to the nodes we can make use of the function

list_entry(struct list_head *ptr, type_of_struct, field_name); ptr: Pointer to the current node of the linked list type_of_struct: The type of the parent structure of which the pointer is to be returned field_name: Name of field in "type_of_struct" of the kind ptr.

Note: This structure works similar to the function "container_of"

Thus in the example above to get a pointer of kind k_list using the pointer "ptr" we need to use the function as

entry=list_entry(ptr,struct k_list,test_list);

Where entry is

struct k_list *entry;

Putting all the above pieces of code into one module we can test the functions related to the creation of linked list in kernel.

create_list.c

#include<linux/kernel.h> #include<linux/module.h> #include<linux/list.h> #include<linux/slab.h> struct k_list { struct list_head test_list; int temp; }; int create_list_init() { struct k_list *one,*two,*three,*entry; struct list_head test_head; struct list_head *ptr; one=kmalloc(sizeof(struct k_list *),GFP_KERNEL); two=kmalloc(sizeof(struct k_list *),GFP_KERNEL); three=kmalloc(sizeof(struct k_list *),GFP_KERNEL); one->temp=10; two->temp=20; three->temp=30; INIT_LIST_HEAD(&test_head); list_add(&one->test_list,&test_head); list_add(&two->test_list,&test_head); list_add(&three->test_list,&test_head); list_for_each(ptr,&test_head){ entry=list_entry(ptr,struct k_list,test_list); printk(KERN_INFO "\n Hello %d \n ", entry->temp); return 0; } int create_list_exit() { return 0 ; } module_init(create_list_init); module_exit(create_list_exit);

Makefile required to compile the module

ifneq ($(KERNELRELEASE),) obj-m := create_list.o else KERNELDIR ?= /lib/modules/$(shell uname -r)/build PWD := $(shell pwd) default: $(MAKE) -C $(KERNELDIR) M=$(PWD) modules endif

To see the output first compile the module using

$ make

Insert it into the kernel

$ insmod create_list.ko

To see the output

$ dmesg [ 7822.769538] Hello 30 [ 7822.769538] [ 7822.769547] [ 7822.769547] Hello 20 [ 7822.769547] [ 7822.769550] [ 7822.769550] Hello 10 [ 7822.769550]

We can see in the output of dmesg that we have been able to traverse the list using list_for_each successfully.