Summary of the list

As a basic data structure, linked list is widely used in various programming because of its simple structure and excellent performance (the complexity of insertion and deletion of two-way linked list is O(1)). Linked list is generally divided into unidirectional linked list and two-way linked list. For unidirectional linked list, the general complexity of deletion and insertion is O(n), so, engineering is rarely used in general, all the following lists are bidirectional linked list.

Common bidirectional linked list data structures are defined as follows:

Struct list_node_xxx{struct list_node_xxx *prev, *next; // Specify the data, such as a char array char data[100]; };Copy the code

• Prev and next point to the precursor and successor nodes of the current node, respectively.
• Each node contains specific data.

Design idea

The Linux kernel also supports bidirectional linked lists, which are exquisitely designed. Here is the definition:

struct list_head {
	struct list_head *next, *prev;
};
Copy the code

The first time to see the definition of the kernel list, the first feeling is amazing, really is too simple, after some questions how to achieve the structure of the list function? You will be amazed when you see this list definition for the first time (:>

Later, after years of experience for the use of the kernel list, slowly understand the essence of this design, briefly say their feelings, if there is something wrong, welcome criticism and correct (:>

1. This design perfectly embodies the Design philosophy of the Linux kernel: separation of mechanism and policy.

   The separation of mechanism and policy is a design philosophy shared by the Linux kernel and the entire Linux community. Mechanisms are used to provide specific functionality, and policies are used to specify how that functionality should be used. Mechanics are stable, whereas strategies are ever-changing. Just as the atom is the basic mechanism by which everything works, the complex world is a representation of the different combinations of strategies of the atom. The kernel linked list is a good example of the design philosophy of separating mechanism from policy. Struct list_head only defines the minimum set required by the linked list mechanism. When it comes to the policy, that is, the specific user of the linked list, the linked list mechanism can be combined to realize the related functions of the linked list.

2. The data is decoupled from the structure, and the kernel needs only one linked list definition.

   The traditional linked list definition coupling data and structure together, this data structure generally only uses a business scenario, after the business scenario changes, need to redefine the linked list data structure, the corresponding operation interface for the list, also need to redefine. For simple systems, the definition and use of such lists are generally fine. However, for complex systems, there are a variety of business subsystems, each of which is likely to use a linked list data structure. If we still follow the traditional linked list usage pattern, to define the list separately, it is conceivable that the extension and maintenance of the list will be very difficult.

   Based on the traditional list of “defects”, Linux kernel designers have a unique way, creative “data” and “structure” to understand the decoupling, from now on, only need to define a list structure, complete a set of list operation interface, you can achieve the unified management of all lists.

3. Unified linked list operation interface, interface oriented programming

   One of the basic design principles of object-oriented programming is to program to interfaces, not to definitions. Although the kernel code is fully implemented using C language, which is a process-oriented language, object-oriented programming is not related to language. In a fundamental sense, it is a relatively high-level design idea, which has important guiding significance for large and complex systems. All right, back to the Design of the Linux kernel linked list, which follows the principles of interface-oriented programming very well. Kernel for chain table this data structure, made a thorough abstraction, make its not related to any specific data, so to speak, it is a “pure” list, with the chain table structure interface, is the global unified, any business subsystem in the use of linked lists the structure, operation interface for are unified. This convenience of operation is very important, think of the relationship between wrench and nut can be deeply realized this.

Well, the above is about the kernel of the list of several insights, the principle is always abstract, only try to use, in order to have a profound experience, the following to say about the basic use of the kernel list.

use

Linux kernel: /include/ Linux /list.h, which defines all the operations on the list.

1. Chain table structure

    struct list_head {
    	struct list_head *next, *prev;
    };
   Copy the code

2. Define the list

   struct list_node_xxx{ char data[10]; struct list_head list; . . }node_xxx;Copy the code

   • Struct list_node_xxx: specific linked list definition.
   • Data: specific data of the linked list.
   • List: Linked list structure, data and structure separation.

3. Initialize the

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    #define LIST_HEAD(name) \
    	struct list_head name = LIST_HEAD_INIT(name)
   
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
    	WRITE_ONCE(list->next, list);
    	list->prev = list;
    }
    
   Copy the code

   The LIST_HEAD_INIT macro and INIT_LIST_HEAD can be used to initialize the list, such as the list in the struct list_node_xxx structure.

    struct list_node_xxx node_xxx;
    INIT_LIST_HEAD(&(node_xxx.list));
   Copy the code

4. insert

   The insertion mode of linked list is divided into head insertion and tail insertion.

    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }
    
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }
   Copy the code

   Both apis are implemented by calling the __list_add function, which begins with a double underscore to indicate that this is an internal use function.

   static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { if (! __list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); }Copy the code

5. delete

   Deleting a linked list node is very efficient and simple.

   static inline void list_del(struct list_head *entry) { __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } where \_\_list_del_entry is used to delete the list node, after which, two statements are used to set the next and prev Pointers to the entry to invalid list entries. static inline void __list_del_entry(struct list_head *entry) { if (! __list_del_entry_valid(entry)) return; __list_del(entry->prev, entry->next); } static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; WRITE_ONCE(prev->next, next); }Copy the code

6. List empty test

   The test list is empty. static inline int list_empty(const struct list_head *head) { return READ_ONCE(head->next) == head; }

7. Traversing the list

   As mentioned above, the design philosophy of Linux kernel linked lists is to separate the data from the structure. Instead of using the linked list structure directly, the kernel will embed it into a specific business data structure, such as the struct list_node_xxx above. So, here’s the problem. So far, all of the interface parameters we’ve dealt with with linked lists have been Pointers to struct list_head, which are typically embedded in specific business data structures. The question is how do we access the real business data structure through the struct list_head? Struct list_node_xxx (struct list_node_xxx) This is where the list_Entry macro must be used.

   /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ const typeof(((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) ); }) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)Copy the code

You can see that list_Entry calls the container_of macro. Here’s how it works. Container_of takes the same three arguments as list_entry: PTR, type, and member. Struct list_node_xxx struct list_node_xxx struct list_node_xxx

In the figure, relative to struct list_node_xxx, the meanings of PTR,type,member parameters are marked, and “?” Represents the address of the target business data structure of interest to us, locally the address of node_xxx.

• PTR: indicates the address of list in node_xxx structure
• Struct list_node_xxx struct list_node_xxx
• Member: indicates the field name of struct list_head in struct list_node_XXX

The container_of macro has two parts:

	1. const typeof(((type *)0)->member ) *__mptr = (ptr);
	
	2. (type *)( (char *)__mptr - offsetof(type,member) );
Copy the code

The first part is used to get an __mptr pointer. Typeof is a GNU/GCC extension keyword that gives you the typeof a variable by its name. Struct list_node_xxx (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx)->member (struct list_node_xxx) Here’s the struct list_head.

The second part calculates the address of node_xxx from the position of __mptr and list relative to node_xxx. The offsetof macro here uses a trick (TYPE *)0)->MEMBER in which 0 acts as part 1.

List_entry is a list traversal function.

/** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member ! = (head); \ pos = list_next_entry(pos, member)) /** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ &pos->member ! = (head); \ pos = list_prev_entry(pos, member))Copy the code

List_for_each_entry forwards traverses the entire list. Pos represents a pointer to the current list data item, head represents the list header, and member represents the field name of struct list_head in the list data item.

List_for_each_entry_reverse is used to reverse traversal the entire list.

Specific instance

Here is an example of how to use linked lists in the kernel.

struct list_node_xxx { char data[100]; struct list_head list; }; // Define the list header LIST_HEAD(node_head); Struct list_node_xxx *node_xxx_1 = kzalloc(sizeof(*node_xxx), GFP_KERNL); struct list_node_xxx *node_xxx_2 = kzalloc(sizeof(*node_xxx), GFP_KERNL); List_add (&(node_xxx_1), &node_head); // Add list_add(&(node_xxx_1), &node_head); list_add(&(node_xxx_2), &node_head); struct list_node_xxx *entry; // List_for_each_entry (entry, &node_head, list) {memcpy(entry->data, "hello, world.", strlen(hello,world."); } // Delete struct list_head *pos; list_for_each(pos, &node_head) { list_del(pos); }Copy the code