Linked List : list_cut_position

  • In this program, you are going to learn

  • How to cut a list into two ?

Topics in this section,

  • In this example, we are going to cut a list into two.

  • 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_cut_position(&new_list, &my_list, my_list.next);

    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_cut_position All entries from list up to and including entry are moved to new, which should be an empty list. Entry may be equal to list, in which case no entries are moved.

list_cut_position(&new_list, &my_list, my_list.next);

  • 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 1: %d\n",entry->data);
42
43
44	INIT_LIST_HEAD(&new_list);
45
46	list_cut_position(&new_list, &my_list, my_list.next);
47//	list_cut_position(&new_list, &my_list, my_list.prev);
48
49	list_for_each_entry(entry, &my_list, list) 
50		printk(KERN_INFO "my_list entry 2: %d\n",entry->data);
51
52
53	list_for_each_entry(entry, &new_list, list) 
54		printk(KERN_INFO "new_list entry : %d\n",entry->data);
55
56	return 0;
57}
58
59static void __exit linkedlist_exit(void)
60{
61	struct list_node *ptr, *next;
62
63	list_for_each_entry_safe(ptr, next, &my_list, list) {
64		list_del(&ptr->list);
65	}
66
67	list_for_each_entry_safe(ptr, next, &new_list, list) {
68		list_del(&ptr->list);
69	}
70	pr_info("Driver unloaded\n");
71}
72
73module_init(linkedlist_init);
74module_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
[15274.105659] Driver loaded
[15274.105664] my_list entry 1: 40
[15274.105664] my_list entry 1: 30
[15274.105665] my_list entry 1: 20
[15274.105665] my_list entry 1: 10
[15274.105665] my_list entry 2: 30
[15274.105666] my_list entry 2: 20
[15274.105666] my_list entry 2: 10
[15274.105666] new_list entry : 40

  • Run rmmod to unload the module.

$ sudo rmmod linked_list

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

$ dmesg
[15274.105659] Driver loaded
[15274.105664] my_list entry 1: 40
[15274.105664] my_list entry 1: 30
[15274.105665] my_list entry 1: 20
[15274.105665] my_list entry 1: 10
[15274.105665] my_list entry 2: 30
[15274.105666] my_list entry 2: 20
[15274.105666] my_list entry 2: 10
[15274.105666] new_list entry : 40
[15279.094026] 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_cut_position

To cut a list into two

list_for_each_entry_safe

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

list_add

To insert a new entry after the specified head

list_del

To delete entry from list
See Also