The second part of this project involves modifying the kernel module so that it uses the kernel linked-list data structure. In Section 1.10, we covered various data structures that are common in operating systems (At the bottom of this document).The Linux kernel provides several of these structures.Here, we explore using the circular, doubly linked list that is available to kernel developers. Much of what we discuss is available in the Linux source code in this instance, the include le and we recommend that you examine this le as you proceed through the following steps. Initially, you must dene a struct containing the elements that are to be inserted in the linked list.The following C struct denes birthdays:

struct birthday {

int day;

int month;

int year;

struct list_head list;

}

Notice the member struct list head list. The list head structure is dened in the include le . Its intention is to embed the linked lis twithin the nodesthat comprise the list.This list head structure is quite simpleit merely holds two members, next and prev,that point to the next and previous entries in the list. By embedding the linked list within the structure,Linux makes it possible to manage the data structure with a series of macro functions.

Inserting Elements into the Linked List We can declare a list head object,which we use as a reference to the head of the list by using the LIST_HEAD() macro static LIST_HEAD(birthday list); This macro denes and initializes the variable birthday list,which is of type struct list head. We create and initialize instances of struct birthday as follows: struct birthday *person; person = kmalloc(sizeof(*person), GFP KERNEL);

person->day = 2;

person->month= 8;

person->year = 1995;

INIT LIST_HEAD(&person->list); The kmalloc() function is the kernel equivalent of the user-level malloc() function for allocating memory,except that kernel memory is being allocated. (TheGFP KERNELag indicates routine kernel memory allocation.)The macro INIT LIST HEAD() initializes the list member in struct birthday.Wecan then add this instance to the end of the linked list using the list add tail() macro: list_add_tail(&person->list, &birthday list); Traversing the LinkedList Traversing the list involves using the list_for_each_entry() Macro, which accepts three parameters:

A pointer to the structure being iterated over

A pointer to the head of the list being iterated over

The name of the variable containing the list head structure Thefollowingcode illustrates this macro: struct birthday *ptr;

list_for_each_entry(ptr, &birthday list, list) {

/* on each iteration ptr points */

/* to the next birthday struct */

}

Removing Elements from the Linked List Removing elements from the list involves using the list_del() macro,which is passed a pointer to struct list_head list_del(struct list_head *element) This removes element from the list while maintaining the structure of the remainder of the list. Perhaps the simplest approach for removing all elements from a linked list is to remove each element as you traverse the list. The macro list for each entry safe() behaves much like list for each entry() except that it is passed an additional argument that maintains the value of the next pointer of the item being deleted. (This is necessary for preserving the structure of the list.)

The following code example illustrates this macro: struct birthday *ptr, *next

list_for_each_entry_safe(ptr,next,&birthday list,list) {

/* on each iteration ptr points */

/* to the next birthday struct */

list del(&ptr->list);

kfree(ptr);

}

Notice that after deleting each element,were turn memory that was previously allocated with kmalloc() back to the kernel with the call to kfree(). Careful memory managementwhich includes releasing memory to prevent memory leaksis crucial when developing kernel-level code.

Part II Assignment In the module entry point,create a linked list containing ve struct birthday elements.Traverse the linked list and output its contents to the kernel log buffer. Invoke the dmesg command to ensure the list is properly constructed once the kernel module has been loaded. In the module exit point,delete the elements from the linked list and return the free memory back to the kernel.Again, invoke the dmesg command to check that the list has been removed once the kernel module has been unloaded.

Kernel module simple.c

#include

#include

#include

/* This function is called when the module is loaded. */

int simple init(void) {

printk(KERN INFO "Loading Module ");

return 0;

}

/* This function is called when the module is removed. */

void simple exit(void) {

printk(KERN INFO "Removing Module ");

}

/* Macros for registering module entry and exit points. */

module init(simple init);

module exit(simple exit);

MODULE_LICENSE("GPL");

MODULE_DESCRIPTION("Simple Module");

MODULE_AUTHOR("SGG")