Linked List : Delete Front

  • In this program, you are going to learn

  • How to Delete the elments to the front end of the linked list ?

Topics in this section,

  • In this example, we are going to delete the elements in the front end.

  • Add the list of header files to refer the APIs used in this program.

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/slab.h>

  • Add the modules macro which lists the information about the license, author and description.

MODULE_LICENSE("GPL");
MODULE_AUTHOR("linux_usr");
MODULE_DESCRIPTION("Linked List");

  • In this example, we are going to delete the elements in the rear end.

  • list_head is used to initialize the list.

static struct list_head my_list;

  • INIT_LIST_HEAD is used to initialize a list_head structure.

INIT_LIST_HEAD(&my_list);

INIT_LIST_HEAD(&new_node->list);

  • Add the module init function to execute the function once when the module is loaded to the linux kernel.

static int __init linkedlist_init(void)
{
    pr_info("Driver loaded\n");

    INIT_LIST_HEAD(&my_list);

    insert_rear(0);
    insert_rear(1);
    insert_rear(2);
    insert_rear(3);
    insert_rear(4);

    pr_info("Linked list after insertion : \n");
    display();

    delete_front();

    pr_info("Linked list after deletion : \n");
    display();

    return 0;
}

  • Add module exit function which is executed once the module is unloaded from the kernel.

static void __exit linkedlist_exit(void)
{
        struct list_node *ptr, *next;

        list_for_each_entry_safe(ptr, next, &my_list, list) {
                list_del(&ptr->list);
                kfree(ptr);
        }

        pr_info("Driver unloaded\n");
}

  • insert_rear function inserts a new node at the end with the given value into the linked list.

void insert_rear(int value)
{
    struct list_node * new_node;

    new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);

    if (!new_node) {
            pr_err("Memory allocation failed\n");

            return;
    }

    new_node->data = value;
    INIT_LIST_HEAD(&new_node->list);
    list_add_tail(&new_node->list, &my_list);
}

  • delete_front function deletes the first node from the linked list.

void delete_front(void)
{
    struct list_node * front;

    if (list_empty(&my_list)) {
            pr_err("List is empty, cannot delete rear");

            return;
    }

    front = list_entry(my_list.next, struct list_node, list);
    list_del(&front->list);
    kfree(front);
}

  • display function iterates through the linked list using list_for_each_entry. It prints the data in each node to the kernel log.

void display(void)
{
    struct list_node * ptr;

    pr_info("Linked list: ");
    list_for_each_entry(ptr, &my_list, list) {
            printk(KERN_CONT "%d -> ", ptr->data);
    }

    printk(KERN_CONT "NULL\n");
}

  • Add the module init and exit which is called when the module is loaded and unloaded.

module_init(linkedlist_init);
module_exit(linkedlist_exit);

 1#include <linux/init.h>
 2#include <linux/module.h>
 3#include <linux/kernel.h>
 4#include <linux/list.h>
 5#include <linux/slab.h>
 6
 7MODULE_LICENSE("GPL");
 8MODULE_AUTHOR("linux_usr");
 9MODULE_DESCRIPTION("Linked List");
10
11struct list_node {
12	int data;
13	struct list_head list;
14};
15
16static struct list_head my_list;
17
18void insert_rear(int value)
19{
20	struct list_node *new_node;
21
22	new_node = kmalloc(sizeof(struct list_node), GFP_KERNEL);
23	
24	if (!new_node) {
25		pr_err("Memory allocation failed\n");
26		return;
27	}
28
29	new_node->data = value;
30	INIT_LIST_HEAD(&new_node->list);
31	list_add_tail(&new_node->list, &my_list);
32}
33
34void delete_front(void)
35{
36	struct list_node *front;
37
38	if (list_empty(&my_list)) {
39		pr_err("List is empty, cannot delete rear");
40		return;
41	}
42
43	front = list_entry(my_list.next, struct list_node, list);
44	list_del(&front->list);
45	kfree(front);
46}
47
48void display(void)
49{
50	struct list_node *ptr;
51
52	pr_info("Linked list: ");
53	list_for_each_entry(ptr, &my_list, list) {
54		printk(KERN_CONT "%d -> ", ptr->data);
55	}
56
57	printk(KERN_CONT "NULL\n");
58}
59
60static int __init linkedlist_init(void)
61{
62	pr_info("Driver loaded\n");
63
64	INIT_LIST_HEAD(&my_list);
65
66	insert_rear(0);
67	insert_rear(1);
68	insert_rear(2);
69	insert_rear(3);
70	insert_rear(4);
71	
72	pr_info("Linked list after insertion : \n");
73	display();
74
75	delete_front();
76
77	pr_info("Linked list after deletion : \n");
78	display();
79
80	return 0;
81}
82
83static void __exit linkedlist_exit(void)
84{
85	struct list_node *ptr, *next;
86
87	list_for_each_entry_safe(ptr, next, &my_list, list) {
88		list_del(&ptr->list);
89		kfree(ptr);
90	}
91
92	pr_info("Driver unloaded\n");
93}
94
95module_init(linkedlist_init);
96module_exit(linkedlist_exit);

1obj-m += delete.o
2all:
3	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
4clean:
5	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

  • Run Make to compile the module.

$make
make -C /lib/modules/5.4.0-150-generic/build M=$HOME/kernel_delete modules
make[1]: Entering directory '/usr/src/linux-headers-5.4.0-150-generic'
  CC [M]  $HOME/kernel_delete/delete.o
  Building modules, stage 2.
  MODPOST 1 modules
  CC [M]  $HOME/kernel_delete/delete.mod.o
  LD [M]  $HOME/kernel_delete/delete.ko
make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-150-generic'

  • Run ls to check if delete.ko is generated or not.

$ ls -l
total 36
-rw-rw-r-- 1 test test  154 Feb 26 13:18 Makefile
-rw-rw-r-- 1 test test   47 Feb 26 13:18 modules.order
-rw-rw-r-- 1 test test    0 Feb 26 13:18 Module.symvers
-rw-rw-r-- 1 test test  820 Feb 26 13:18 delete.c
-rw-rw-r-- 1 test test 5880 Feb 26 13:18 delete.ko
-rw-rw-r-- 1 test test   47 Feb 26 13:18 delete.mod
-rw-rw-r-- 1 test test  919 Feb 26 13:18 delete.mod.c
-rw-rw-r-- 1 test test 3448 Feb 26 13:18 delete.mod.o
-rw-rw-r-- 1 test test 3320 Feb 26 13:18 delete.o

  • Run insmod to load the module.

$ sudo insmod ./delete.ko

  • Check the kernel messages to see if the kernel module is loaded or not.

$ dmesg
[12045.072071] Driver loaded
[12045.072073] Linked list after insertion :
[12045.072073] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> NULL
[12045.072076] Linked list after deletion :
[12045.072076] Linked list: 1 -> 2 -> 3 -> 4 -> NULL

  • Run rmmod to unload the module.

$ sudo rmmod delete

  • Check dmesg to see if the module is unloaded from kernel.

$ dmesg
[12045.072071] Driver loaded
[12045.072073] Linked list after insertion :
[12045.072073] Linked list: 0 -> 1 -> 2 -> 3 -> 4 -> NULL
[12045.072076] Linked list after deletion :
[12045.072076] Linked list: 1 -> 2 -> 3 -> 4 -> NULL
[12050.629679] Driver unloaded

API

Learning

INIT_LIST_HEAD

To initialize a list_head structure

list_head

To initialize the list

list_for_each_entry

To iterate over list of given type

list_for_each_entry_safe

To iterate over list of given type safe against removal of list entry

list_add_tail

To insert a new entry before the specified head

list_del

To delete entry from list

list_empty

To test whether a list is empty

list_entry

To get the struct for this entry
See Also