Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of how to realize the two-way linked list in the Linux kernel, the content is detailed and easy to understand, the operation is simple and fast, and it has a certain reference value. I believe you will gain something after reading this article on how to realize the two-way linked list in the Linux kernel. Let's take a look.

First, let's take a look at the main structure in include/linux/types.h:

Struct list_head {struct list_head * next, * prev;}

You may notice that this is different from the implementation of two-way linked lists you have seen before.

For example, this is done in the glib library:

Struct GList {gpointer data;GList * next;GList * prev;}

Generally speaking, a linked list structure contains a pointer to an item.

But the linked list implementation in the Linux kernel does not do so. So the question arises: where do linked lists store data? In fact, linked lists implemented in the kernel are intrusive linked lists (Intrusive list). An intrusive linked list does not store data within a node-its node contains only pointers to the front and rear nodes, and pointers to the data portion of the linked list nodes-this is how the data is attached to the linked list. This makes the data structure generic and does not need to consider the type of node data to use.

For example:

Struct nmi_desc {spinlock_t lock;struct list_head head;}

Let's look at a few examples to understand how list_head is used in the kernel.

As mentioned above, linked lists are used in many different places in the kernel. Let's take a look at an example of the use of miscellaneous character drivers. The miscellaneous character driver API in drivers/char/misc.c is used to write small drivers that deal with small hardware or virtual devices. These drivers share the same major number:

# define MISC_MAJOR 10

But they all have different secondary numbers.

For example:

Ls-l / dev | grep 10crw1 root root 10,235 Mar 21 12:01 autofsdrwxr-xr-x 10 root root 200 Mar 21 12:01 cpucrw- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latencycrw- 1 root root 10,203 Mar 21 12:01 cusedrwxr-xr-x 2 root root 100 Mar 21 12:01 dricrw-rw-rw- 1 root root 10,229 Mar 21 12:01 fusecrw- 1 root root 10 228 Mar 21 12:01 hpetcrw- 1 root root 10, 183 Mar 21 12:01 hwrngcrw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvmcrw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-controlcrw- 1 root root 10, 227 Mar 21 12:01 mcelogcrw- 1 root root 10, 59 Mar 21 12:01 memory_bandwidthcrw- 1 root root 10 61 Mar 21 12:01 network_latencycrw- 1 root root 10, 60 Mar 21 12:01 network_throughputcrw-r- 1 root kmem 10, 144 Mar 21 12:01 nvrambrw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10crw- 1 root root 10 63 Mar 21 12:01 vga_arbitercrw- 1 root root 10, 137 Mar 21 12:01 vhci

Now let's see how it uses linked lists. First take a look at the structure miscdevice:

Struct miscdevice {int minor;const char * name;const struct file_operations * fops;struct list_head list;struct device * parent;struct device * this_device;const char * nodename;mode_t mode;}

You can see that the fourth variable list of the structure miscdevice is a linked list of all registered devices.

You can see the definition of this linked list at the beginning of the source code file:

Static LIST_HEAD (misc_list)

It is actually an extension of a variable defined with the list_head type.

# define LIST_HEAD (name)\ struct list_head name = LIST_HEAD_INIT (name)

Then initialize it using the macro LIST_HEAD_INIT

This populates the two variables of the prev and next structures with the address of the variable name.

# define LIST_HEAD_INIT (name) {& (name), & (name)}

Now let's look at the function misc_register that registers miscellaneous devices.

It initializes miscdevice- > list from the beginning with the function INIT_LIST_HEAD.

INIT_LIST_HEAD (& misc- > list)

It works the same as the macro list _ HEAD_INIT.

Static inline void INIT_LIST_HEAD (struct list_head * list) {list- > next = list;list- > prev = list;}

Next, after the function device_create creates the device

Let's add the device to the device list with the following statement:

List_add (& misc- > list, & misc_list)

The kernel file list.h provides an API interface to add new items to the linked list.

Let's take a look at its implementation:

Static inline void list_add (struct list_head * new, struct list_head * head) {_ list_add (new, head, head- > next);}

In fact, the internal function _ _ list_add is called with three specified parameters:

New-New item. The new head- item will be inserted after the head head- > next-the item after the head before the insert. The implementation of _ _ list_add is very simple:

Static inline void _ list_add (struct list_head * new,struct list_head * prev,struct list_head * next) {next- > prev = new;new- > next = next;new- > prev = prev;prev- > next = new;}

Here, we add a new item between prev and next.

So the misc linked list we defined at the beginning with the macro list _ HEAD_INIT will contain forward and backward pointers to miscdevice- > list. Here's another question: how do you get the contents of the list? Here is a special macro:

# define list_entry (ptr, type, member)\ container_of (ptr, type, member)

Three parameters are used:

Ptr-pointer to the structure list_head; type-structure type; member-the name of a variable of type list_head in the structure body

For example:

Const struct miscdevice * p = list_entry (v, struct miscdevice, list)

Then we can use p-> minor or p-> name to access the miscdevice. Let's look at the implementation of list_entry:

# define list_entry (ptr, type, member)\ container_of (ptr, type, member)

As we can see, it simply calls the macro container _ of with the same parameters. At first glance, this macro is very strange:

# define container_of (ptr, type,member) ({\ const typeof (type *) 0)-> member) * _ mptr = (ptr);\ (type *) ((char *) _ mptr-offsetof (type,member));})

First of all, you can notice that the curly braces contain two expressions.

The compiler executes all the statements in curly braces and then returns the value of the final expression.

For example:

# include int main () {int I = 0bot printf ("I =% d\ n", ({+ + I; + + I;})); return 0;}

Will eventually print out 2.

The next point is typeof, which is also very simple.

As you can understand from the name, it simply returns the type of a given variable. When I first saw the implementation of the macro container _ of, the strangest thing I found was the 0 in the expression ((type *) 0). In fact, this pointer cleverly calculates the offset from a specific variable of the structure, where the zero happens to be the zero offset in the bit width.

For example:

# include struct s {int field1;char field2;char field3;}; int main () {printf ("% p\ n", & (struct s*) 0)-> field3); return 0;}

The results show 0x5.

The next macro offsetof calculates the offset from the starting address of the structure to a given structure field.

Its implementation is similar to the above: # define offsetof (TYPE, MEMBER) ((size_t) & ((TYPE *) 0)-> MEMBER) now let's summarize the macro container _ of. Given the address and name of the list_head type field in the structure, and the type of the structure container, it can return the starting address of the structure. In the first line of the macro definition, a pointer mptr to the structure member variable ptr is declared and the address of ptr is assigned to it. Now ptr and mptr point to the same address. Technically we don't need this line, but it makes it easy to do type checking. The first line ensures that the specific structure (parameter type) contains the member variable member. The second line of code uses the macro offsetof to calculate the offset of the member variable from the starting address of the structure, and then subtracts the offset from the address of the structure, resulting in the structure.

Of course, list_add and list_entry are not.

The only function provided. The implementation of the two-way linked list also provides the following API:

List_addlist_add_taillist_dellist_replacelist_movelist_is_lastlist_emptylist_cut_positionlist_splicelist_for_eachlist_for_each_entry

Wait, a lot of other API.

This is the end of the article on "how to implement a two-way linked list in the Linux kernel". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to realize the two-way linked list in the Linux kernel". If you still want to learn more knowledge, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.