Linux kernel device driver in the kernel of the use of the linked list note collation

/********************
 *  Application of linked lists in the kernel 
 ********************/

(1) is introduced

In the Linux kernel, a large number of linked list structures are used to organize data, including device lists and data organization in various functional modules. Most of these lists are implemented in include/linux/ list.h, a rather wonderful linked list data structure.

The definition of a linked list data structure is simple:

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

The list_head structure contains two Pointers to the list_head structure, prev and next, and the kernel's data structure is usually organized as a double-loop linked list.

Unlike the previously introduced double-linked list structure model, list_head here has no data fields. In the Linux kernel linked list, the data is not contained in the linked list structure, but the linked list nodes are contained in the data structure. Such as:

struct my_struct{
 struct list_head list;
 unsigned long dog;
 void *cat;
};

Linked lists in linux have no fixed header and can be accessed from any element. Traversing a linked list is simply a matter of starting at one node, following the pointer to the next node, and returning to the original node. Each individual node can be referred to as a linked header.

(2) Initialization of linked list

a. Static

If a linked list is created statically at compile time and referenced directly, it looks like this:

struct my_struct mine={
 .lost = LIST_HEAD_INIT(mine.list);
 .dog = 0,
 .cat = NULL
};
// or 
static LIST_HEAD(fox);
/* Is equal to the struct list_head fox = LIST_HEAD_INIT(fox); */

Dynamic b.

struct my_struct *p;
p = kmalloc(GFP_KERNEL, sizeof(my_struct));
p->dog = 0;
p->cat = NULL;
INIT_LIST_HEAD(&p->list);

(3) Operate the linked list

The kernel provides a set of functions to manipulate linked lists.

Attention! These functions take one or more list_head structure Pointers as arguments. Defined in the < linux/list.h >

a. Add nodes

list_add(struct list_head *new, 
     struct list_head *head);
// To specify a linked list head Insert after the node new node 

b. Adds nodes to the end of the list

list_add_tail(struct list_head *new, 
     struct list_head *head);
// To specify a linked list head Insert in front of nodes new node 

c. Removes 1 node from the linked list

list_del(struct list_head *entry);
// will entry Remove from the list 

Move a node from one linked list to another

list_move(struct list_head *list, 
     struct list_head *head);

Remove the list item from a linked list and insert it after head

e.list_empty(struct list_head *head);

The linked list returns a non-0 value for null, otherwise returns 0

Merge linked lists

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

0

(4) Traversing the linked list

The list itself is not important, access to the structure containing the list is important

a. Obtains a pointer to the structure containing the linked list from a pointer to the linked list

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

1 ptr: list_head pointer type_of_struct: The structural type that contains ptr field_name: The name of the linked list field in the structure

Such as:

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

2

b. Traverse the linked list

list_for_each(struct list_head *cursor,
       struct list_head *list);
// And often list_entry Supporting the use 
// Attention! with list_for_each Traversal, excluding header nodes 

c. Get pointer to large structure while traversing

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

4

d. Traverses the linked list while releasing each traversal to the node

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

5

conclusion