Linux kernel device driver kernel linked list usage notes

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

(1) Introduction

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

The definition of the linked list data structure is simple:

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

The list_head structure contains two pointers prev and next pointing to the list_head structure. The kernel's data structure is usually organized into a double circular linked list.

Different from the double linked list structure model introduced previously, the list_head here has no data domain. In Linux kernel linked lists, instead of containing data in the linked list structure, the linked list nodes are contained in the data structure. like:

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

The linked list in Linux does not have a fixed header, and access can start from any element. To traverse a linked list, you only need to start from a node and follow the pointer to access the next node until you return to the original node. Each individual node can be called a linked list head.

(2) Initialization of linked list

a. Static

If you create a linked list statically at compile time and reference it directly, as follows:

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

b. Dynamic

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

(3) Operation list

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

Notice! These functions all take one or more list_head structure pointers as parameters. Defined in <linux/list.h>

a. Add nodes

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

b. Add the node to the end of the linked list

list_add_tail(struct list_head *new, 
     struct list_head *head);
//Insert a new node in front of the head node of the specified linked list

c. Delete a node from the linked list

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

d. Move a node from one linked list to another

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

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

e.list_empty(struct list_head *head);

If the linked list is empty, it returns a non-zero value, otherwise it returns 0

f. Merge linked lists

list_splice(struct list_head *list, 
      struct list_head *head);
//Notice! The new linked list does not include the list node

(4) Traversing the linked list

The linked list itself is not important, accessing the structure that contains the linked list is important

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

list_entry(struct list_head *ptr,
      type_of_struct, 
      field_name);

• ptr: list_head pointer
• type_of_struct: the structure type containing ptr
• field_name: the name of the linked list field in the structure

like:

my_struct *p = (list_head *ptr, my_struct, list);

b. Traverse the linked list

list_for_each(struct list_head *cursor,
       struct list_head *list);
//Often used in conjunction with list_entry//Note! When traversing with list_for_each, the head node is not included

c. Get the pointer to the large structure while traversing

list_for_each_entry(type *cursor, 
      struct list_head *list,
      member);

d. Release each traversed node while traversing the linked list

list_for_each_entry_safe(type *cursor, 
     type *tmp;
     struct list_head *list,
     member);

Summarize

The above is the full content of this article. I hope that the content of this article will have certain reference learning value for your study or work. Thank you for your support of 123WORDPRESS.COM. If you want to learn more about this, please check out the following links