This article is a continuation of the Series on Linux Device Drivers and carries the discussion on Linux device drivers and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. This is the Linked List in Linux Kernel tutorial part 1 – Linux Device Driver Tutorial Part 17.
You can also read Sysfs, Procfs, Workqueue, Completion, Softirq, and threaded IRQ in the Linux device driver.
Linked List in Linux Kernel
Introduction to Linked List
A linked list is a data structure that consists of a sequence of nodes. Each node is composed of two fields: the data field and the reference field which is a pointer that points to the next node in the sequence.
Each node in the list is also called an element. A head pointer is used to track the first element in the linked list, therefore, it always points to the first element.
The elements do not necessarily occupy contiguous regions in memory and thus need to be linked together (each element in the list contains a pointer to the next element).
Advantages of Linked Lists
- They are dynamic in nature and allocate memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed.
- Linked List reduces the access time.
Disadvantages of Linked Lists
- The memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially.
- Reverse Traversing is difficult in the linked list.
Applications of Linked Lists
- Linked lists are used to implement stacks, queues, graphs, etc.
- Unlike an array, In Linked Lists, we don’t need to know the size in advance.
Types of Linked Lists
There are three types of linked lists.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
I guess you all are familiar with Linked list types already. So, I’m not going to discuss its types. Let’s get into the Linked List in the Linux kernel.
Linked List in Linux Kernel
The linked list is a very important data structure that allows a large number of storage with efficient manipulation of data. Most of the kernel code has been written with the help of this data structure. So in the Linux kernel, no need to implement our own Linked List or no need to use 3rd party library. It has a built-in Linked List which is the Doubly Linked List. It is defined in defined in /lib/modules/$(uname -r)/build/include/linux/list.h.
Normally we used to declare a linked list as like the below snippet.
struct my_list{
int data,
struct my_list *prev;
struct my_list *next;
};
But if want to Implement it in Linux, then you could write like the below snippet.
struct my_list{
struct list_head list; //linux kernel list implementation
int data;
};
Where struct list_head is declared in list.h.
struct list_head {
struct list_head *next;
struct list_head *prev;
};
Initialize Linked List Head
Before creating any node in the linked list, we should create a linked list’s head node first. So below macro is used to create a head node.
|
This macro will create the head node structure in the name of “ For example, I’m going to create the head node in the name of “
Let’s see how internally it handles this. The macro is defined like below in #define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
struct list_head {
struct list_head *next;
struct list_head *prev;
};
So it will create like below. struct list_head etx_linked_list = { &etx_linked_list , &etx_linked_list};
While creating the head node, it initializes the prev and next pointer to its own address. This means that |
Create Node in Linked List
|
You have to create your linked list node dynamically or statically. Your linked list node should have the member defined in
For Example, My node is like this. struct my_list{
struct list_head list; //linux kernel list implementation
int data;
};
struct my_list new_node;
So we have to initialize the list_head variable using INIT_LIST_HEAD(&new_node.list); new_node.data = 10; |
Add Node to Linked List
Add after Head Node
|
After creating that node, we need to add that node to the linked list. So we can use this inline function to do that.
Insert a new entry after the specified head. This is good for implementing stacks. Where,
For Example, list_add(&new_node.list, &etx_linked_list); |
Add before Head Node
|
Insert a new entry before the specified head. This is useful for implementing queues.
Where,
For Example, list_add_tail(&new_node.list, &etx_linked_list); |
Delete Node from Linked List
list_del
| It will delete the entry node from the list. This function removes the entry node from the linked list by disconnecting prev and next pointers from the list, but it doesn’t free any memory space allocated for the entry node.
Where,
|
list_del_init
| It will delete the entry node from the list and reinitialize it. This function removes the entry node from the linked list by disconnecting prev and next pointers from the list, but it doesn’t free any memory space allocated for the entry node.
Where,
|
Replace Node in Linked List
list_replace
|
This function is used to replace the old node with the new node.
Where,
If |
list_replace_init
|
This function is used to replace the old node with the new node and reinitialize the old entry.
Where,
If |
Moving Node in Linked List
list_move
| This will delete one list from the linked list and again adds to it after the head node.
Where,
|
list_move_tail
|
This will delete one list from the linked list and again adds it before the head node.
Where,
|
Rotate Node in Linked List
| This will rotate the list to the left.
Where,
|
Test the Linked List Entry
list_is_last
This tests whether list is the last entry in the list head.
Where,
It returns 1 if it is the last entry otherwise 0. |
list_empty
| It tests whether a list is empty or not.
Where,
It returns 1 if it is empty otherwise 0. |
list_is_singular
| This will test whether a list has just one entry.
Where,
It returns 1 if it has only one entry otherwise 0. |
Split Linked List into two parts
| This cut a list into two.
This helper moves the initial part of
Where,
|
Join Two Linked Lists
| This will join two lists, this is designed for stacks.
Where,
|
Traverse Linked List
list_entry
| This macro is used to get the struct for this entry.
|
list_for_each
| This macro is used to iterate over a list.
|
So using those above two macros, we can traverse the linked list. We will see the example in the next tutorial. We can also use the below methods also.
list_for_each_entry
| This is used to iterate over a list of the given type.
|
list_for_each_entry_safe
| This will iterate over the list of given type-safe against the removal of list entry.
Where,
|
We can also traverse the linked list on the reverse side also using the below macros.
list_for_each_prev
| This will be used to iterate over a list backward.
|
list_for_each_entry_reverse
| This macro is used to iterate backward over the list of the given type.
|
So, We have gone through all the functions. Please go through the next tutorial (Part 2) for the Linked List sample program.
Please find the other Linux device driver tutorials here.
You can also read the below tutorials.
Embedded Software | Firmware | Linux Devic Deriver | RTOS
Hi, I’m SLR. I am a tech blogger and an Embedded Engineer. I am always eager to learn and explore tech-related concepts. And also, I wanted to share my knowledge with everyone in a more straightforward way with easy practical examples. I strongly believe that learning by doing is more powerful than just learning by reading. I love to do experiments. If you want to help or support me on my journey, consider sharing my articles, or Buy me a Coffee! Thank you for reading my blog! Happy learning!
