8. Kernel Data Structures

  • Kernel gives you linked list and red black tree implementations.
  • You need not code your own linked list for your code.
  • The linked list is extensively used by the kernel.
  • Red Black tree is used in the Completely Fair Schedular.

8.1. Using Kernel’s linked list for your data structure

Let us write a small application.

The application will show the kernel’s linked list in a graphical way. How can we do it.

What we will do

  1. We will implement the kernel linked list.
  2. We will give a proc interface to user. When the user write’s add [int] to the file we will add it to the linked list.
  3. Writing delete [int] will delete the node with the provided value from the linked list.
  4. Writing print will print the whole linked list. The list can be viewed through the dmesg command.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * <PD> Program for linked list manipulation using proc </PD>
 */
#include "ll.h"

struct list_head todo_list;

int todo_add_entry(int number)
{
   struct todo_struct *new_node = kmalloc((size_t) (sizeof(struct todo_struct)), GFP_KERNEL);
   if (!new_node) {
      printk(KERN_INFO
             "Memory allocation failed, this should never fail due to GFP_KERNEL flag\n");
      return 1;
   }
   new_node->priority = number;
   list_add_tail(&(new_node->list), &todo_list);
   return 0;
}

void show_list(void)
{
   struct todo_struct *entry = NULL;

   list_for_each_entry(entry, &todo_list, list) {
      printk(KERN_INFO "Node is %d\n", entry->priority);
   }
}

int delete_node(int number)
{
   struct todo_struct *entry = NULL;

   list_for_each_entry(entry, &todo_list, list) {
      if (entry->priority == number) {
         printk(KERN_INFO "Found the element %d\n",
                entry->priority);
         list_del(&(entry->list));
         kfree(entry);
         return 0;
      }
   }
   printk(KERN_INFO "Could not find the element %d\n", number);
   return 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/proc_fs.h>
#include <linux/uaccess.h>
#include <linux/slab.h>

#ifndef LL_H
#define LL_H
#define NODE "driver/mmmod"
/*
 * Linked List Node
 */
struct todo_struct {
		struct list_head list;
		int priority;
};

/*
 * Linked list related functions
 */
void show_list(void);
int todo_add_entry(int);

/*
 * Proc Interface related function
 */

void proc_cleanup(void);
int ll_proc_init (void);
int configure_proc_entry(void);


ssize_t my_proc_read (struct file *filp,char *buf,size_t count,loff_t *offp ); 
ssize_t my_proc_write(struct file *filp, const char __user * buffer, size_t count, loff_t *pos);

int configure_proc_entry(void);
int delete_node (int);
void destroy(void); 
#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * Module to show how to use the kernel linked list for managing data
 * 1. Add node to linked list
 * 2. Print the list
 * 3. Delete nodes from the list
 * The modules exposes a /proc interface on which if you cat 
 * 1. add 5 -- it adds five
 * 2. print -- it prints the linked list
 * 3. delete 5 -- it deletes the node in the linked list
 * 4. destroy -- destroys the whole linked list
 */

#include "ll.h"
extern struct proc_dir_entry *proc;
extern struct list_head todo_list;
static int __init my_init(void)
{

   printk(KERN_INFO "Hello from Linked List Module");

   if (ll_proc_init()) {
      printk(KERN_INFO "Falied to create the proc interface");
      return -EFAULT;
   }

   INIT_LIST_HEAD(&todo_list);
   return 0;
}

static void __exit my_exit(void)
{
   if (proc) {
      proc_cleanup();
      pr_info("Removed the entry");
   }
   printk(KERN_INFO "Bye from Hello Module");
}

module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("abr");

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// Module to make a read entry in the proc file system.
// Module to write a command line calculator

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include <linux/sched.h>
#include <linux/mm.h>
#include <linux/slab.h>
#include <asm/uaccess.h>
#include <asm/types.h>


#include "ll.h"
struct proc_dir_entry *proc;
int len,temp;
char *msg;

#define PROC_NAME "linked_list"

ssize_t my_proc_write(struct file *filp, const char __user * buffer, size_t count, loff_t *pos)
{
   char *str;
   char command[20];
   int val = 0;

   printk("Calling Proc Write");
   str = kmalloc((size_t) count, GFP_KERNEL);
   if (copy_from_user(str, buffer, count)) {
      kfree(str);
      return -EFAULT;
   }

   sscanf(str, "%s %d", command, &val);
   printk("First Arguement %s\n", command);
   printk("Second Argument %d\n", val);

   if (!strcmp(command, "add")) {
      /* Add node */
      printk(KERN_INFO "Adding data to linked list %d\n", val);
      todo_add_entry(val);
   }

   if (!strcmp(command, "delete")) {
      /* Delete Node */
      printk(KERN_INFO "Deleting node from linked list %d\n", val);
      if (delete_node(val)) {
         printk(KERN_INFO "Delete failed \n");
      }
   }

   if (!strcmp(command, "print")) {
      /* Print the linked list */
      printk(KERN_INFO "Printing the linked list\n");
      show_list();
   }

   kfree(str);
   return count;
}

ssize_t my_proc_read (struct file *filp,char *buf,size_t count,loff_t *offp ) 
{
        char *data;
        int err;
        data=PDE_DATA(file_inode(filp));
        if(!(data)){
                printk(KERN_INFO "Null data");
                return 0;
        }

        if(count>temp) {
                count=temp;
        }

        temp=temp-count;

        err = copy_to_user(buf,data, count);
        if (err) {      
                printk(KERN_INFO "Error in copying data.");
        }

        if(count==0) {
                temp=len;
        }

        return count;
}

struct file_operations proc_fops = {
    .read = my_proc_read,
    .write = my_proc_write,
};

int create_new_proc_entry(void) {
        msg="Hello World";
        proc=proc_create_data(PROC_NAME, 0666, NULL, &proc_fops, msg);
        len=strlen(msg);
        temp=len;
        if (proc) {
            return 0;
        } else {
            return -1;
        }
}

int ll_proc_init (void) {
        create_new_proc_entry();
        return 0;
}

void proc_cleanup(void) {
        remove_proc_entry("hello", NULL);
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

obj-m +=  ll_module.o
obj-m +=  ll_proc.o
obj-m +=  ll.o
obj-m += ll_driver.o
ll_driver-objs := ll_module.o ll_proc.o ll.o

export KROOT=/lib/modules/$(shell uname -r)/build
#export KROOT=/lib/modules/$(uname)3.2.0-23-generic/build

allofit:  modules

modules: clean

	@$(MAKE) -C $(KROOT) M=$(PWD) modules

modules_install:
	@$(MAKE) -C $(KROOT) M=$(PWD) modules_install

kernel_clean:
	@$(MAKE) -C $(KROOT) M=$(PWD) clean

clean: kernel_clean
	rm -rf   Module.symvers modules.order

insert: modules 
	sudo dmesg -c
	sudo insmod ll_driver.ko

remove: clean
	sudo rmmod ll_driver.ko

8.2. Examples

  • Lets just print the empty list.
echo "print" > /proc/linked_list
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# dmesg
[  578.782533] ll_driver: module verification failed: signature and/or required key missing - tainting kernel
[  578.783117] Hello from Linked List Module
[  630.344370] Calling Proc Write
[  630.344376] First Arguement print
[  630.344378] Second Argument 0
[  630.344380] Printing the linked list
  • Now let us add some nodes.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "add 10" > /proc/linked_list
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "add 20" > /proc/linked_list
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "add 30" > /proc/linked_list
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# dmesg
[  578.782533] ll_driver: module verification failed: signature and/or required key missing - tainting kernel
[  578.783117] Hello from Linked List Module
[  630.344370] Calling Proc Write
[  630.344376] First Arguement print
[  630.344378] Second Argument 0
[  630.344380] Printing the linked list
[  642.095630] Calling Proc WriteFirst Arguement add
[  642.095638] Second Argument 10
[  642.095640] Adding data to linked list 10
[  645.399251] Calling Proc WriteFirst Arguement add
[  645.399256] Second Argument 20
[  645.399257] Adding data to linked list 20
[  647.542762] Calling Proc WriteFirst Arguement add
[  647.542767] Second Argument 30
[  647.542768] Adding data to linked list 30
  • Let us print again.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "print" > /proc/linked_list
  • Let us delete some nodes.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "delete 30" > /proc/linked_list
  • Let us delete a non existent node.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "delete 0" > /proc/linked_list
  • Delete more node.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "delete 10" > /proc/linked_list
  • Print.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# echo "print" > /proc/linked_list
  • Check the dmesg commands output.
root@lkw:~/doc_linux_kernel_workbook/doc/code/07_data_structures/01_ll# dmesg
[  578.782533] ll_driver: module verification failed: signature and/or required key missing - tainting kernel
[  578.783117] Hello from Linked List Module
[  630.344370] Calling Proc Write
[  630.344376] First Arguement print
[  630.344378] Second Argument 0
[  630.344380] Printing the linked list
[  642.095630] Calling Proc WriteFirst Arguement add
[  642.095638] Second Argument 10
[  642.095640] Adding data to linked list 10
[  645.399251] Calling Proc WriteFirst Arguement add
[  645.399256] Second Argument 20
[  645.399257] Adding data to linked list 20
[  647.542762] Calling Proc WriteFirst Arguement add
[  647.542767] Second Argument 30
[  647.542768] Adding data to linked list 30
[  653.222910] Calling Proc WriteFirst Arguement print
[  653.222916] Second Argument 0
[  653.222918] Printing the linked list
[  653.222919] Node is 10
[  653.222920] Node is 20
[  653.222921] Node is 30
[  659.727435] Calling Proc WriteFirst Arguement delete
[  659.727440] Second Argument 30
[  659.727442] Deleting node from linked list 30
[  659.727443] Found the element 30
[  665.175263] Calling Proc WriteFirst Arguement delete
[  665.175274] Second Argument 0
[  665.175277] Deleting node from linked list 0
[  665.175281] Could not find the element 0
[  665.175282] Delete failed
[  667.134783] Calling Proc WriteFirst Arguement delete
[  667.134789] Second Argument 10
[  667.134791] Deleting node from linked list 10
[  667.134792] Found the element 10
[  668.942912] Calling Proc WriteFirst Arguement print
[  668.942917] Second Argument 0
[  668.942919] Printing the linked list
[  668.942920] Node is 20