catalogue

summary

List in kernel_ Implementation of head

1.list_head structure

2.list_ Operation implemented by head

3.list_entry macro

list_ Use of head

epilogue

summary

The two-way circular linked list in Linux kernel is realized by separating abstract structure and data, that is, abstract linked list_head is embedded in the data structure that stores specific data, and the list is used_ The entry macro (explained below) connects the linked list structure with data.

List in kernel_ Implementation of head

list.h file implements list_ All functions of head can be found in/ include/linux (version 2.6 kernel used by bloggers)

1.list_head structure

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

list_ The structure of head is very simple. It only stores the front and back nodes, which is in line with its abstract characteristics.

2.list_ Operation implemented by head

list.h internal operations on the linked list are all on the list_ The of the head linked list itself includes initialization, insertion, deletion, movement and other operations, but it does not realize the operation of the embedded data structure. For the reason of length, here are only a few examples of initialization and insertion operations

initialization

//Use example list_head *head = LIST_HEAD_INIT(head)
#define LIST_HEAD_INIT(name) { &(name), &(name) }

//Use example list_head *head;
//         LIST_Head(head);
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

//Use example list_head *head;
//         INIT_LIST_HEAD(head);
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

It should be noted that because it is a two-way circular linked list, the prev and next of the initialized head node point to the head itself

insert

//Insert between two known nodes
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;
}

//Add a new node after the head node
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

//Adding a new node before the head node inserts it into the tail
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

list.h implements three insert operations, the latter two of which are convenient to implement queue.

list. Other functions in H are not complex. Please study them yourself. Let's introduce an important macro list_entry .

3.list_entry macro

list_ The key link between the head structure and the structure for storing data is the list_ The entry macro is generally provided for the data structure bound to it. First, let's look at its definition:

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

You can see the list_ The entry macro re encapsulates another macro container_of, which is often used in the kernel, is defined as follows:

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

This macro is complex. Let's analyze it layer by layer. First, let's look at three parameters. ptr is the member pointer of the instantiated structure, type is the type name of the structure, and member is the name of a member embedded in the structure.

Let's make the contents of the macro more tidy

{

        const typeof( ((type *)0)->member ) *__mptr = (ptr);

        (type *)( (char *)__mptr - offsetof(type, member) );

}

The first line skillfully converts 0 to a type ， type pointer and points to its member, then uses typeof to obtain the type of this member, that is, typeof (((type *) 0) - > member), and then assigns ptr to the temporary pointer of this type__ mptr, pre const prevents the content pointed to by ptr from being modified. [1. The type of member is not provided in the macro parameters. 2. The macro typeof is used to obtain the type name]

The second line, offsetof, is used to obtain the memory offset of the member in the data structure__ The mptr pointer subtracts the offset to obtain the address of the data structure embedded in the member, that is, the address of the structure storing the data, and then forcibly convert this address to a type pointer. The macro returns a type pointer. [offsetof is provided by the compiler to calculate the offset of the element relative to the head of the structure]

The following figure will help you understand:

 

Use list_node address minus data_ Size to get the instantiated data_ The address of struct. Note that the address identified in the figure is relative to the inside of the structure. [note that the data_size here is da'xiao of the pointer data

Use the following:

struct data_struct {
    void *data;
    list_head list_node;
};

struct data_struct *temp = init();
list_entry(&temp->list_node, struct data_struct, list_node);

list_ Use of head

Data above_ The example of struct is using list_head is the data organization structure, list H encapsulates many operations on the linked list, which can be used directly to form the linked list, and the data needs to be processed separately except data.

//The data used above is quoted here_ struct

struct data_struct *head = init();

//insert
struct data_struct *new_1 = init();
list_add(&new->list_node, &head->list_node);

//delete
struct data_struct *new_2 = init();
list_del(&new1->list_node);//Only deleting the elements in the abstract linked list does not clear any memory

The above deletion operation well reflects the separation of data and abstract linked list. When we need to really delete an element, we need to define our own deletion function to realize the operation.

void list_del_m(struct data_struct *node)
{
    list_del(&node->list_node);
    free(node->data);
    node->data = NULL;
    free(node);
    node = NULL;
}

//Reference the above code
list_del_m(new_1);

epilogue

Due to space limitations, this article is written here first. For list_ For more use of head, please refer to the task structure and its related functions in the kernel, which can be found in/ include/linux/sched.h find task_struct definition.

Finally, thank you very much for reading here. If there is anything wrong, please correct it.