When comparing the advantages and disadvantages of linked lists against arrays, we can mention a few points. However, in cases of random storage, we would choose linked lists for processing. When using a doubly linked list, we often define it in the following manner:
struct list_node { TYPE data; struct list_node *prev,*next;};The corresponding linked list structure is as follows:
For this data structure definition, there is a limitation: the entire structure can only have one doubly circular linked list, and multiple lists cannot exist. Moreover, operations on the linked list can only be performed on this data structure, making it non-generic. In the Linux Kernel (taking version 3.0.8 as an example), the linked list is separated from the data domain, implementing a generic linked list structure and operations. Its definition is found in the include/linux/types.h file, structured as follows:
struct list_head { struct list_head *next, *prev;};The above is the structure of a generic linked list. Using this definition, we can define our commonly used doubly linked list as follows:
struct list_node { TYPE data; struct list_head list;};The corresponding linked list structure is as follows:
From the diagram, we can see that the linked list is connected solely through the list_head structure. Does this mean we can only operate on the linked list structure? How then can we manipulate the data? This is where the Linux generic linked list technique comes into play, separating the linked list from its data, allowing for unified operations on the linked list. Let’s continue analyzing to appreciate the beauty of Linux algorithms.
In the Linux kernel source code, the include/linux/list.h file contains the operations for linked lists. First, let’s see how to find the base address of the structure element containing the address of list_head. In the list.h file, there is the following macro:
#define list_entry(ptr, type, member) \ container_of(ptr, type, member)In the include/linux/kernel.h file, the following definition exists:
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})In the include/linux/stddef.h file, the following definition exists:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)Here, size_t is defined as unsigned int on i386.
Upon seeing these three macros, it can be a bit dizzying. Let’s convert it into a single macro:
#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned int)(&(type *)0)->member) )Where, (unsigned int)(&(type *)0)->member) converts the address 0 to a pointer of type type, then retrieves the pointer to the member of type type in the structure, and converts it to an unsigned int value, thus obtaining the offset of the member relative to the type type.
Then, by subtracting this Offset value from the ptr pointer, we obtain the starting position of the corresponding structure.
In the above, ptr, type, member are explained as follows:
ptr is a pointer to the member of type list_head in the structure;
type is a structure type that contains a member of type list_head;
member is the name of the member of type list_head in the structure.
We can understand the above transformation through the following diagram:
As shown in the diagram, we subtract the address value pointed to by member from the address value 0, thus obtaining the offset of member relative to the entire structure. Consequently, we obtain the address value of the structure corresponding to our ptr, allowing us to access the structure containing the list_head member, which is equivalent to:
The absolute address of the structure containing the list_head member = ptr absolute address – relative address offset
At this point, it should be clear! Now, looking back at the definitions in the kernel, it should be easier to understand.
Having understood the definition of the doubly linked list in the kernel, let’s continue to explore other aspects of linked lists:
1. Initialization macros for linked lists
First, let’s confirm how to create a linked list head. In the kernel source code, in include/linux/list.h there are the following macros:
#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)There are also the following functions:
static inline void INIT_LIST_HEAD(struct list_head *list){ list->next = list; list->prev = list;}From the above, we can see that it simply assigns itself to the previous and next pointers, meaning that during initialization, the prev and next of the linked list head point to itself. This way, we can easily determine if the linked list is empty.
2. Common linked list operation functions and macros
static inline void list_add(struct list_head *new, struct list_head *head);static inline void list_add_tail(struct list_head *new, struct list_head *head);static inline void list_del(struct list_head *entry);static inline int list_empty(const struct list_head *head);#define list_entry(ptr, type, member) \ container_of(ptr, type, member)#define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))More functions and macros can be found in the kernel source file include/linux/list.h file.
3. Practical verification
Next, we will verify the practicality of this linked list structure in an application program, which will help us better apply the kernel’s ideas in our applications.
The example code is as follows:
list_test.c:
#include <stdio.h>#include <stdlib.h>#include "list.h"
struct test_list { int data; struct list_head list;};
int main(void){ LIST_HEAD(head); int i; struct test_list *ptr[10]; struct list_head *tmp = NULL; struct test_list *node;
for(i=0;i<10;i++){ ptr[i] = (struct test_list*)malloc(sizeof(struct test_list)); if(!ptr[i]){ printf("malloc error!\n"); } ptr[i]->data = i; }
for(i=0;i<10;i++){ list_add_tail(&ptr[i]->list,&head); }
printf("Test Link:\n"); list_for_each(tmp,&head){ node = list_entry(tmp,struct test_list,list); printf("%d ",node->data); }
printf("\n");
return 0;}list.h:
#ifndef _LINUX_LIST_H#define _LINUX_LIST_H
struct list_head { struct list_head *next, *prev;};
#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)
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;}
static inline void list_add_tail(struct list_head *new, struct list_head *head){ __list_add(new, head->prev, head);}
#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})#define list_entry(ptr, type, member) \ container_of(ptr, type, member)#endifMakefile:
all: gcc -o list_test list_test.c list.h
clean: rm -rf list_testThe running result is shown in the following image:
At this point, we have a preliminary understanding of the kernel linked list and begin to appreciate the design philosophy of the kernel.