Linked List : list_splice_init

  • In this program, you are going to learn

  • How to join two lists ?

Topics in this section,

  • In this example, we are going to join two lists..

  • 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");

  • LIST_HEAD is used to initialize the list.

struct list_node {
    int data;
    struct list_head list;
};

static LIST_HEAD(my_list);
static LIST_HEAD(new_list);

struct list_node data1, data2, data3,data4,  *entry;

  • 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");

    data1.data = 10;
    data2.data = 20;
    data3.data = 30;
    data4.data = 40;

    INIT_LIST_HEAD(&data1.list);
    INIT_LIST_HEAD(&data2.list);
    INIT_LIST_HEAD(&data3.list);
    INIT_LIST_HEAD(&data4.list);

    list_add(&data1.list, &my_list);
    list_add(&data2.list, &my_list);
    list_add(&data3.list, &my_list);
    list_add(&data4.list, &my_list);

    list_for_each_entry(entry, &my_list, list)
        printk(KERN_INFO "my_list entry 1: %d\n",entry->data);

    INIT_LIST_HEAD(&new_list);

    list_splice_init(&my_list, &new_list);

    list_for_each_entry(entry, &my_list, list)
        printk(KERN_INFO "my_list entry 2: %d\n",entry->data);

    list_for_each_entry(entry, &new_list, list)
                                    printk(KERN_INFO "new_list entry : %d\n",entry->data);

        return 0;
}

  • INIT_LIST_HEAD is used to initialize a list_head structure.

INIT_LIST_HEAD(&data1.list);
INIT_LIST_HEAD(&data2.list);
INIT_LIST_HEAD(&data3.list);
INIT_LIST_HEAD(&data4.list);

  • list_add to insert a new element after the given list head.

list_add(&data1.list, &my_list);
list_add(&data2.list, &my_list);
list_add(&data3.list, &my_list);
list_add(&data4.list, &my_list);

  • list_for_each_entry to iterate over list of given type.

list_for_each_entry(entry, &my_list, list)

  • list_splice_init to join two lists and reinitialise the emptied list.

list_splice_init(&my_list, &new_list);

  • 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);
        }

        list_for_each_entry_safe(ptr, next, &new_list, list) {
                list_del(&ptr->list);
        }
        pr_info("Driver unloaded\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 LIST_HEAD(my_list);
17static LIST_HEAD(new_list);
18
19struct list_node data1, data2, data3,data4,  *entry;
20
21static int __init linkedlist_init(void)
22{
23	pr_info("Driver loaded\n");
24
25	data1.data = 10;
26	data2.data = 20;
27	data3.data = 30;
28	data4.data = 40;
29
30	INIT_LIST_HEAD(&data1.list);
31	INIT_LIST_HEAD(&data2.list);
32	INIT_LIST_HEAD(&data3.list);
33	INIT_LIST_HEAD(&data4.list);
34
35	list_add(&data1.list, &my_list);
36	list_add(&data2.list, &my_list);
37	list_add(&data3.list, &my_list);
38	list_add(&data4.list, &my_list);
39
40	list_for_each_entry(entry, &my_list, list) 
41		printk(KERN_INFO "my_list entry : %d\n",entry->data);
42
43	INIT_LIST_HEAD(&new_list);
44
45	list_splice_init(&my_list, &new_list);
46
47	list_for_each_entry(entry, &my_list, list) 
48		printk(KERN_INFO "new_list entry : %d\n",entry->data);
49
50	list_for_each_entry(entry, &new_list, list) 
51		printk(KERN_INFO "new_list entry : %d\n",entry->data);
52
53	return 0;
54}
55
56static void __exit linkedlist_exit(void)
57{
58	struct list_node *ptr, *next;
59
60	list_for_each_entry_safe(ptr, next, &my_list, list) {
61		list_del(&ptr->list);
62	}
63
64	list_for_each_entry_safe(ptr, next, &new_list, list) {
65		list_del(&ptr->list);
66	}
67	pr_info("Driver unloaded\n");
68}
69
70module_init(linkedlist_init);
71module_exit(linkedlist_exit);

1obj-m += linked_list.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_linked_list modules
make[1]: Entering directory '/usr/src/linux-headers-5.4.0-150-generic'
  CC [M]  $HOME/kernel_linked_list/linked_list.o
  Building modules, stage 2.
  MODPOST 1 modules
  CC [M]  $HOME/kernel_linked_list/linked_list.mod.o
  LD [M]  $HOME/kernel_linked_list/linked_list.ko
make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-150-generic'

  • Run ls to check if linked_list.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 linked_list.c
-rw-rw-r-- 1 test test 5880 Feb 26 13:18 linked_list.ko
-rw-rw-r-- 1 test test   47 Feb 26 13:18 linked_list.mod
-rw-rw-r-- 1 test test  919 Feb 26 13:18 linked_list.mod.c
-rw-rw-r-- 1 test test 3448 Feb 26 13:18 linked_list.mod.o
-rw-rw-r-- 1 test test 3320 Feb 26 13:18 linked_list.o

  • Run insmod to load the module.

$ sudo insmod ./linked_list.ko

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

$ dmesg
[ 1223.691973] Driver loaded
[ 1223.691976] my_list entry : 40
[ 1223.691976] my_list entry : 30
[ 1223.691977] my_list entry : 20
[ 1223.691977] my_list entry : 10
[ 1223.691978] new_list entry : 40
[ 1223.691978] new_list entry : 30
[ 1223.691979] new_list entry : 20
[ 1223.691979] new_list entry : 10

  • Run rmmod to unload the module.

$ sudo rmmod linked_list

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

$ dmesg

[ 1223.691973] Driver loaded
[ 1223.691976] my_list entry : 40
[ 1223.691976] my_list entry : 30
[ 1223.691977] my_list entry : 20
[ 1223.691977] my_list entry : 10
[ 1223.691978] new_list entry : 40
[ 1223.691978] new_list entry : 30
[ 1223.691979] new_list entry : 20
[ 1223.691979] new_list entry : 10
[ 1231.366682] 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_add

To insert a new entry after the specified head

list_splice_init

To join two lists

list_for_each_entry_safe

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

list_del

To delete entry from list
See Also