Doubly linked list
Doubly linked list
Linux kernel provides its own implementation of doubly linked list, which you can find in the include/linux/list.h. We will start Data Structures in the Linux kernel
from the doubly linked list data structure. Why? Because it is very popular in the kernel, just try to search
First of all, let's look on the main structure in the include/linux/types.h:
You can note that it is different from many implementations of doubly linked list which you have seen. For example, this doubly linked list structure from the glib library looks like :
Usually a linked list structure contains a pointer to the item. The implementation of linked list in Linux kernel does not. So the main question is - where does the list store the data?
. The actual implementation of linked list in the kernel is - Intrusive list
. An intrusive linked list does not contain data in its nodes - A node just contains pointers to the next and previous node and list nodes part of the data that are added to the list. This makes the data structure generic, so it does not care about entry data type anymore.
For example:
Let's look at some examples to understand how list_head
is used in the kernel. As I already wrote about, there are many, really many different places where lists are used in the kernel. Let's look for an example in miscellaneous character drivers. Misc character drivers API from the drivers/char/misc.c is used for writing small drivers for handling simple hardware or virtual devices. Those drivers share same major number:
but have their own minor number. For example you can see it with:
Now let's have a close look at how lists are used in the misc device drivers. First of all, let's look on miscdevice
structure:
We can see the fourth field in the miscdevice
structure - list
which is a list of registered devices. In the beginning of the source code file we can see the definition of misc_list:
which expands to the definition of variables with list_head
type:
and initializes it with the LIST_HEAD_INIT
macro, which sets previous and next entries with the address of variable - name:
Now let's look on the misc_register
function which registers a miscellaneous device. At the start it initializes miscdevice->list
with the INIT_LIST_HEAD
function:
which does the same as the LIST_HEAD_INIT
macro:
In the next step after a device is created by the device_create
function, we add it to the miscellaneous devices list with:
Kernel list.h
provides this API for the addition of a new entry to the list. Let's look at its implementation:
It just calls internal function __list_add
with the 3 given parameters:
new - new entry.
head - list head after which the new item will be inserted.
head->next - next item after list head.
Implementation of the __list_add
is pretty simple:
Here we add a new item between prev
and next
. So misc
list which we defined at the start with the LIST_HEAD_INIT
macro will contain previous and next pointers to the miscdevice->list
.
There is still one question: how to get list's entry. There is a special macro:
which gets three parameters:
ptr - the structure list_head pointer;
type - structure type;
member - the name of the list_head within the structure;
For example:
After this we can access to any miscdevice
field with p->minor
or p->name
and etc... Let's look on the list_entry
implementation:
As we can see it just calls container_of
macro with the same arguments. At first sight, the container_of
looks strange:
First of all you can note that it consists of two expressions in curly brackets. The compiler will evaluate the whole block in the curly braces and use the value of the last expression.
For example:
will print 2
.
The next point is typeof
, it's simple. As you can understand from its name, it just returns the type of the given variable. When I first saw the implementation of the container_of
macro, the strangest thing I found was the zero in the ((type *)0)
expression. Actually this pointer magic calculates the offset of the given field from the address of the structure, but as we have 0
here, it will be just a zero offset along with the field width. Let's look at a simple example:
will print 0x5
.
The next offsetof
macro calculates offset from the beginning of the structure to the given structure's field. Its implementation is very similar to the previous code:
Let's summarize all about container_of
macro. The container_of
macro returns the address of the structure by the given address of the structure's field with list_head
type, the name of the structure field with list_head
type and type of the container structure. At the first line this macro declares the __mptr
pointer which points to the field of the structure that ptr
points to and assigns ptr
to it. Now ptr
and __mptr
point to the same address. Technically we don't need this line but it's useful for type checking. The first line ensures that the given structure (type
parameter) has a member called member
. In the second line it calculates offset of the field from the structure with the offsetof
macro and subtracts it from the structure address. That's all.
Of course list_add
and list_entry
is not the only functions which <linux/list.h>
provides. Implementation of the doubly linked list provides the following API:
list_add
list_add_tail
list_del
list_replace
list_move
list_is_last
list_empty
list_cut_position
list_splice
list_for_each
list_for_each_entry
and many more.
Last updated