Create a double linked list using hlist

To create a double linked list with a seperate head node ,in the linux kernel, we can use the pre existing functions and structures defined in the file types.h. The doubly linked list is formed of two nodes, one is the head node

struct hlist_head { struct hlist_node *first; };

The second one are the nodes used to form the linked list.

struct hlist_node { struct hlist_node *next, **pprev; };

The functions and macros needed to create and use the nodes are defined in the file list.h. To initialize the the list we use the macro

INIT_HLIST_HEAD(ptr)

Where ptr should be of the type hlist_head. This points to the head of the double linked list. As we can see this structure has only one pointer of the type hlist_node, thus the head node will point to the first node of double linked list that we want to create.

To add a node to the list we can use the function

hlist_add_head(struct hlist_node *n, struct hlist_head *h)

The function has been implemented in the file list.h

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; if (first) first->pprev = &n->next; WRITE_ONCE(h->first, n); n->pprev = &h->first; }

The function adds the node "n" at the head of the double linked list pointed to by the head node h. It does this by

Allocate the first node of the list to a temporary node : *first = h->first Make the temporary node as the next node of the new node: n->next = first; if the list was not an empty list first will not be null: if(first) allocate the pprev pointer to the address of the node itself: first->pprev = &n->next; Update the value of head node pointer to n : WRITE_ONCE(h->first, n);

We can iterate over the list using the function

hlist_for_each_entry_safe(pos, n, head, member) pos: the type * to use as a loop cursor. n: another &struct hlist_node to use as temporary storage head: the head for your list. member: the name of the hlist_node within the struct.

To test these functions we will create a structure

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

In the init function we create the required pointers.

struct k_list *one,*two,*three,*entry,*four,*five; struct hlist_head test_head; struct hlist_head *ptr; struct hlist_node*tmp

Allocate memory for the k_list structures.

one=kmalloc(sizeof(struct k_list *),GFP_KERNEL); two=kmalloc(sizeof(struct k_list *),GFP_KERNEL); three=kmalloc(sizeof(struct k_list *),GFP_KERNEL;

Assign values to the integer in the structure. one->temp=10; two->temp=20; three->temp=30;

Initialize the hlist_head

INIT_HLIST_HEAD(&test_head);

Add the nodes at the head, so every new node gets added at the head with the other nodes moving away from the head.

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

The list has been formed, so now we can iterate through the list

hlist_for_each_entry_safe(entry,tmp,&test_head,test_list){ i=i+1; printk(KERN_INFO " Entry %d %d \n \n ", i,entry->temp); }

In the code we have created and displayed the double linked list in the init funtion, thus to test the code we just need to insert the code into the kernel.

This the full code



Save the file as double_linked_list.c, and use the following makefile to compile the code.

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

Make and Insert the code using

$ make $ sudo insmod double_linked_list.ko To see the output execute the message dmesg , we should see the following output.

[ 4642.380108] Entry 1 30 [ 4642.380109] Entry 2 20 [ 4642.380111] Entry 3 10

Thus we can see each node got inserted at the head so the last node inserted which was "30" is the head node.