Search

Creating linked list in liinux Kernel using the list

Linked lists are a very frequently used data structure in the linux kernel and to make the programming easier the linux kernel provides an easy of creating the linked lists. Using the inbuilt method available in the kernel we can create circular doubly linked lists easily and use them in which ever required in the code.

To be able to use this feature available in the kernel we need to add the header file linux/list.h. The structure that is used for creation of the list"list_head" defined in types.h



To use this structure for creation of a linked list we need to include the structure as a member of the main structure of which we want to create the list. For example to create a linked list called k_list in which we will create a list of numbers we will have to create the structure as



In the above structure "temp" is the real data that we want to store and test_list, which is a structure of the kind "list_head" will be used for the creation of the link list.

Then we will need to create a head for the linked list which will be used start the creation of the list. To create a head we can make use of th macro INIT_LIST_HEAD, which will declared and initialize the list at runtime, or we can use the function LIST_HEAD to initialize the list at compile time.

Once list has been created we can add nodes to the linked list using the function



Let us say we want to add create a linked list of three nodes of the kind k_list structure shown above. let us first create three structures and populate it with data that we want to store in it.



Thus we have created three structures "one","two" and "three" of kind k_list in which we have stored data "10","20", and "30" respectively.

Now to form a linked list of these three structures using lines_add



The first argument to list_add is the pointed to the structure of kind list_head which is a member of k_list and the second argument is a pointer to the head node initialized using INIT_LIST_HEAD.

To traverse through the linked list we can make use of another function available in the kernel



In our example we can use this function as



Where ptr is



Now as we traverse through the list we need to be able to access the data that we have stored in the structure k_list. To be able to ge a pointer to the k_list structures through the pointer to the nodes we can make use of the function



Note: This structure works similar to the function "container_of"

Thus in the example above to get a pointer of kind k_list using the pointer "ptr" we need to use the function as



Where entry is



Putting all the above pieces of code into one module we can test the functions related to the creation of linked list in kernel.

create_list.c



Makefile required to compile the module



To see the output first compile the module using



Insert it into the kernel



To see the output



We can see in the output of dmesg that we have been able to traverse the list using list_for_each successfully.


10 comments:

  1. Hello. Do you have any idea how to implement a list inside of a list? For example:

    struct my_first_struct {
    struct list_head children;
    int a;
    }

    struct my_second_list {
    struct list_head children;
    struct my_first_list *list1;
    }

    LIST_HEAD(for_my_first_list);
    LIST_HEAD(for_my_second_list);

    How do I iterate through my first list from my second list?

    Thank you!

    ReplyDelete
  2. entry = kmalloc(sizeof(struct k_list *),GFP_KERNEL);

    ReplyDelete
  3. How check if the list is empty?

    ReplyDelete
  4. How to free the resource for items in list?

    ReplyDelete
  5. to free resources you have to iterate through each individual element and free them one by one , it is similar as in c , if i am not mistaken

    ReplyDelete
  6. as for how to check if the list is empty, thats easy, there is a built in function that does the work for you: list_empty(plist) where plist is a pointer to the list_head structure

    ReplyDelete
  7. i recieved this message:
    Makefile:10: *** missing separator. Stop.

    ReplyDelete
  8. getting two error and a warning
    please find the details below.


    home/einfochips/Desktop/kernel_queue/create_list.c:12:5: error: function declaration isn’t a prototype [-Werror=strict-prototypes]
    int create_list_init(){
    ^
    /home/einfochips/Desktop/kernel_queue/create_list.c:40:5: error: function declaration isn’t a prototype [-Werror=strict-prototypes]
    int create_list_exit() {
    ^
    In file included from /home/einfochips/Desktop/kernel_queue/create_list.c:2:0:
    /home/einfochips/Desktop/kernel_queue/create_list.c: In function ‘__exittest’:
    /home/einfochips/Desktop/kernel_queue/create_list.c:45:13: warning: return from incompatible pointer type [-Wincompatible-pointer-types]
    module_exit(create_list_exit);

    ReplyDelete
    Replies
    1. Two fixes:
      1) remove extra } lien 37
      2) Add void in the functions int create_list_init(void)

      Delete