Play with the kernel linked list list_head, how to manage the implementation of different types of nodes (10,000-character text) can be collected
In the Linux kernel, a structure list_head is provided for creating a two-way circular linked list. Although the Linux kernel is written in C language, the introduction of list_head allows the kernel data structure to also have object-oriented characteristics. It is easy to achieve code reuse by using a common interface for operating list_head, which is somewhat similar to the inheritance mechanism of C++ (hopefully I have the opportunity to write an article to study the object-oriented mechanism of C language).
First find the list_head structure definition, kernel/inclue/linux/types.h is as follows:
struct list_head {struct list_head *next, *prev;};
One thing to note is that the head node head is not used. This needs to be noted.
The structure of a linked list organized using list_head is as shown below:
Then we start building a linked list around this structure, then inserting and deleting nodes, traversing the entire linked list, etc. In fact, the kernel has already provided a ready-made interface. Next, let us enter kernel/include/linux/list.h:
1. Create a linked list
The kernel provides the following interfaces to initialize the linked list:
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;}
For example: You can initialize a linked list through LIST_HEAD(mylist). The prev and next pointers of mylist both point to yourself.
structlist_head mylist = {&mylist, &mylist} ;
But if you just use a structure like mylist to implement a linked list, it has no practical meaning, because normal linked lists are created to traverse other meaningful fields in the structure, and our mylist only has prev and next pointers, but There is no actual meaningful field data, so it is meaningless.
In summary, we can create a host structure, and then nest the mylist field in this structure. The host structure has other fields (process descriptor task_struct, page management page structure, etc. This method is used to create linked lists) . For ease of understanding, the definition is as follows:
struct mylist{int type;char name[MAX_NAME_LEN];struct list_head list;}
Create a linked list and initialize it
structlist_head myhead;INIT_LIST_HEAD(&myhead);
In this way, our linked list has been initialized, and the prev and next pointers of myhead at the head of the linked list point to myhead itself, as shown below:
2. Add nodes
The kernel already provides an interface for adding nodes.
1. list_add
As follows. According to the comments, a new node new is inserted after the head of the linked list.
/*** list_add - add a new entry* @new: new entry to be added* @head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.*/static inline void list_add(struct list_head *new, struct list_head *head){__list_add(new, head, head->next);}
list_add then calls the __list_add interface
/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/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);}
In fact, it is to insert a new node between the head of the myhead linked list and the first node after the head of the linked list. Then this new node becomes the first node after the head of the linked list.
Follow the above steps to create a node and insert it after myhead
struct mylist node1;node1.type = I2C_TYPE;strcpy(node1.name,"yikoulinux");list_add(&node1.list,&myhead);
Then create a second node and insert it after header_task
struct mylist node2;node2.type = I2C_TYPE;strcpy(node2.name,"yikoupeng");list_add(&node2.list,&myhead);
list_add
By analogy, every time a new node is inserted, it will be next to the header node, and the previously inserted nodes will be sorted later. The last node will be the node after the header was first inserted. In the end, it can be concluded that the nodes that come first are at the back, and the nodes that come later are at the front, "first in, last out, last in, first out". So this structure is similar to a stack "stack", and header_task is similar to the top pointer esp in the kernel stack, which is close to the last element pushed to the stack.
2. list_add_tail interface
The list_add interface mentioned above is a node added from the header of the linked list. Similarly, the kernel also provides the interface list_add_tail for adding nodes from the end of the linked list forward. Let us take a look at its specific implementation.
/*** list_add_tail - add a new entry* @new: new entry to be added* @head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.*/static inline void list_add_tail(struct list_head *new, struct list_head *head){__list_add(new, head->prev, head);}
It can be concluded from the comments: (1) Insert a node in front of a specific linked list head
(2) This method is very suitable for queue implementation (why?)
Further expand __list_add() as follows:
/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/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);}
Therefore, it is very clear that list_add_tail is equivalent to inserting new nodes in front of the head of the linked list (it can also be understood as inserting nodes from the end of the linked list. At this time, the header node is a node and remains unchanged)
Using the above method of analyzing the list_add interface, the data structure graph can be drawn as follows.
(1) For the code to create a linked list head (actually it should be the tail), refer to Section 1;
(2) Insert the first node node1.list and call
struct mylist node1;node1.type = I2C_TYPE;strcpy(node1.name,"yikoulinux");list_add_tail(&node1.list,&myhead);
(3) Insert the second node node2.list and call
struct mylist node2;node2.type = I2C_TYPE;strcpy(node2.name,"yikoupeng");list_add_tail(&node2.list,&myhead);
list_add_tail
By analogy, each new node inserted is next to the end of the header_task table, and the first node inserted, my_first_task, is ranked first, and my_second_task is ranked second. It can be concluded that the node inserted first In the front, the nodes inserted later are in the back, "first in, first out, last in, last out". Isn't this the characteristic of the queue (First in First out)!
3. Delete nodes
The kernel also provides the interface list_del() for deleting nodes in the list.h file. Let us take a look at its implementation process.
static inline void list_del(struct list_head *entry){__list_del_entry(entry);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;}/** Delete a list entry by making the prev/next entries* point to each other.** This is only for internal list manipulation where we know* the prev/next entries already!*/static inline void __list_del(struct list_head * prev, struct list_head * next){next->prev = prev;WRITE_ONCE(prev->next, next);}/*** list_del - deletes entry from list.* @entry: the element to delete from the list.* Note: list_empty() on entry does not return true after this, the entry is* in an undefined state.*/static inline void __list_del_entry(struct list_head *entry){if (!__list_del_entry_valid(entry))return;__list_del(entry->prev, entry->next);}
You can delete any node in the linked list by using the list_del(struct list_head *entry) interface, but please note that the prerequisite is that the node is known, it actually exists in the linked list, and the prev and next pointers are not NULL.
4. Linked list traversal
The kernel completes the traversal of the list_head linked list through the following macro definition, as follows:
/*** list_for_each - iterate over a list* @pos: the &struct list_head to use as a loop cursor.* @head: the head for your list.*/#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)
The above method traverses from front to back. You can also use the following macro to traverse in reverse:
/*** list_for_each_prev - iterate over a list backwards* @pos: the &struct list_head to use as a loop cursor.* @head: the head for your list.*/#define list_for_each_prev(pos, head) \for (pos = (head)->prev; pos != (head); pos = pos->prev)
Moreover, list.h also provides list_replace (node replacement) list_move (node shift), flip, search and other interfaces, which will not be analyzed one by one here.
5. Host structure
1. Find the host structure list_entry(ptr, type, member)
All the above operations are performed based on the list_head linked list, and the structures involved are also:
struct list_head {struct list_head *next, *prev;};
In fact, as mentioned at the beginning of the article, what we are really more concerned about is the host structure that contains the list_head structure field, because only by locating the starting address of the host structure can we make sense of other elements in the host structure. fields to operate on.
struct mylist{int type;char name[MAX_NAME_LEN];struct list_head list;};
So how do we find the location of the host structure node1 based on the address of the list field? The definition in list.h is as follows:
/*** 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)
The list_entry macro is provided in list.h to realize the conversion of the corresponding address, but in the end the container_of macro is called, so the greatness of the container_of macro is self-evident.
2 container_of
Students who are doing Linux driver development have thought of a very classic macro definition often used in the book LDD3!
container_of(ptr, type, member)It is mentioned many times in Chapter 3 Character Device Driver and Chapter 14 Driver Device Model in the book LDD3. I think this macro should be one of the most classic macros in the kernel. Then let us unveil her:
This macro is defined in the kernel code kernel/include/linux/kernel.h (the kernel version here is 3.10; this macro definition has changed after the new version 4.13, but the implementation ideas remain the same)
And offsetof is defined in kernel/include/linux/stddef.h, as follows:
For example, let’s briefly analyze the internal implementation mechanism of container_of.
For example:
struct test{int a;short b;char c;};struct test *p = (struct test *)malloc(sizeof(struct test));test_function(&(p->b));int test_function(short *addr_b){//获取struct test结构体空间的首地址struct test *addr;addr = container_of(addr_b,struct test,b);}
Expand the container_of macro and explore the internal implementation:
typeof ( ( (struct test *)0 )->b ) ; (1)typeof ( ( (struct test *)0 )->b ) *__mptr = addr_b ; (2)(struct test *)( (char *)__mptr - offsetof(struct test,b)) (3)
(1) Get the type of member variable b. What is obtained here is the short type. This is an extended syntax for GNU_C.
(2) Use the obtained variable type to define a pointer variable __mptr, and assign the first address of member variable b to it
(3) 这里的offsetof(struct test,b)是用来计算成员b在这个struct test 结构体的偏移。__mptr
是成员b的首地址, 现在 减去成员b在结构体里面的偏移值，算出来的是不是这个结构体的
首地址呀 。
3. 宿主结构的遍历
我们可以根据结构体中成员变量的地址找到宿主结构的地址，并且我们可以对成员变量所建立的链表进行遍历，那我们是不是也可以通过某种方法对宿主结构进行遍历呢？
答案肯定是可以的，内核在list.h中提供了下面的宏：
/*** 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_first_entry 和 list_next_entry宏都定义在list.h中，分别代表：获取第一个真正的宿主结构的地址；获取下一个宿主结构的地址。它们的实现都是利用list_entry宏。
/*** list_first_entry - get the first element from a list* @ptr: the list head to take the element from.* @type: the type of the struct this is embedded in.* @member: the name of the list_head within the struct.** Note, that list is expected to be not empty.*/#define list_first_entry(ptr, type, member) \list_entry((ptr)->next, type, member)/*** list_next_entry - get the next element in list* @pos: the type * to cursor* @member: the name of the list_head within the struct.*/#define list_next_entry(pos, member) \list_entry((pos)->member.next, typeof(*(pos)), member)
最终实现了宿主结构的遍历
#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))
首先pos定位到第一个宿主结构地址，然后循环获取下一个宿主结构地址，如果查到宿主结构中的member成员变量（宿主结构中struct list_head定义的字段）地址为head，则退出，从而实现了宿主结构的遍历。如果要循环对宿主结构中的其它成员变量进行操作，这个遍历操作就显得特别有意义了。
我们用上面的 nod结构举个例子：
struct my_list *pos_ptr = NULL ;list_for_each_entry (pos_ptr, &myhead, list ){printk ("val = %d\n" , pos_ptr->val);}
实例1 一个简单的链表的实现
为方便起见，本例把内核的list.h文件单独拷贝出来，这样就可以独立于内核来编译测试。
功能描述：
本例比较简单，仅仅实现了单链表节点的创建、删除、遍历。
struct list_head myhead;char *dev_name[]={"none","I2C","SPI"};struct mylist{int type;char name[MAX_NAME_LEN];struct list_head list;};void display_list(struct list_head *list_head){int i=0;struct list_head *p;struct mylist *entry;printf("-------list---------\n");list_for_each(p,list_head){printf("node[%d]\n",i++);entry=list_entry(p,struct mylist,list);printf("\ttype: %s\n",dev_name[entry->type]);printf("\tname: %s\n",entry->name);}printf("-------end----------\n");}int main(void){struct mylist node1;struct mylist node2;INIT_LIST_HEAD(&myhead);node1.type = I2C_TYPE;strcpy(node1.name,"yikoulinux");node2.type = I2C_TYPE;strcpy(node2.name,"yikoupeng");list_add(&node1.list,&myhead);list_add(&node2.list,&myhead);display_list(&myhead);list_del(&node1.list);display_list(&myhead);return 0;}
运行结果
实例2 如何在一个链表上管理不同类型的节点
功能描述：
本实例主要实现在同一个链表上管理两个不同类型的节点，实现增删改查的操作。
结构体定义
一个链表要想区分节点的不同类型，那么节点中必须要有信息能够区分该节点类型，为了方便节点扩展，我们参考Linux内核，定义一个统一类型的结构体：
struct device{int type;char name[MAX_NAME_LEN];struct list_head list;};
其中成员type表示该节点的类型：
有了该结构体，我们要定义其他类型的结构体只需要包含该结构体即可，这个思想有点像面向对象语言的基类，后续派生出新的属性叫子类，说到这，一口君又忍不住想挖个坑，写一篇如何用C语言实现面向对象思想的继承、多态、interface。
下面我们定义2种类型的结构体：
i2c这种类型设备的专用结构体：
struct i2c_node{int data;unsigned int reg;struct device dev;};
spi这种类型设备的专用结构体：
struct spi_node{unsigned int reg;struct device dev;};
我特意让两个结构体大小类型不一致。
结构类型
链表头结点定义
structlist_head device_list;
根据之前我们讲解的思想，这个链表链接起来后，应该是以下这种结构：
节点的插入
我们定义的节点要插入链表仍然是要依赖list_add（），既然我们定义了struct device这个结构体，那么我们完全可以参考linux内核，针对不同的节点封装函数，要注册到这个链表只需要调用该函数即可。
实现如下：
设备i2c的注册函数如下：
void i2c_register_device(struct device*dev){dev.type = I2C_TYPE;strcpy(dev.name,"yikoulinux");list_add(&dev->list,&device_list);}
设备spi的注册函数如下：
void spi_register_device(struct device*dev){dev.type = SPI_TYPE;strcpy(dev.name,"yikoupeng");list_add(&dev->list,&device_list);}
我们可以看到注册函数功能是填充了struct device 的type和name成员，然后再调用list_add（）注册到链表中。这个思想很重要，因为Linux内核中许许多多的设备节点也是这样添加到其他的链表中的。要想让自己的C语言编程能力得到质的提升，一定要多读内核代码，即使看不懂也要坚持看，古人有云： 代码读百遍其义自见 。
节点的删除
同理，节点的删除，我们也统一封装成函数，同样只传递参数device即可：
void i2c_unregister_device(struct device *device){// struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev);list_del(&device->list);}void spi_unregister_device(struct device *device){// struct spi_node *spi_device=container_of(dev, struct spi_node, dev);list_del(&device->list);}
在函数中，可以用container_of提取出了设备节点的首地址，实际使用中可以根据设备的不同释放不同的资源。
宿主结构的遍历
节点的遍历，在这里我们通过设备链表device_list开始遍历，假设该节点名是node，通过list_for_each（）可以得到node->dev->list的地址，然后利用container_of 可以得到node->dev、node的地址。
void display_list(struct list_head *list_head){int i=0;struct list_head *p;struct device *entry;printf("-------list---------\n");list_for_each(p,list_head){printf("node[%d]\n",i++);entry=list_entry(p,struct device,list);switch(entry->type){case I2C_TYPE:display_i2c_device(entry);break;case SPI_TYPE:display_spi_device(entry);break;default:printf("unknown device type!\n");break;}display_device(entry);}printf("-------end----------\n");}
由以上代码可知，利用内核链表的统一接口，找个每一个节点的list成员，然后再利用container_of 得到我们定义的标准结构体struct device，进而解析出节点的类型，调用对应节点显示函数，这个地方其实还可以优化，就是我们可以在struct device中添加一个函数指针，在xxx_unregister_device()函数中可以将该函数指针直接注册进来，那么此处代码会更精简高效一些。如果在做项目的过程中，写出这种面向对象思想的代码，那么你的地址是肯定不一样的。读者有兴趣可以自己尝试一下。
void display_i2c_device(struct device *device){struct i2c_node *i2c_device=container_of(device, struct i2c_node, dev);printf("\t i2c_device->data: %d\n",i2c_device->data);printf("\t i2c_device->reg: %#x\n",i2c_device->reg);}
void display_spi_device(struct device *device){struct spi_node *spi_device=container_of(device, struct spi_node, dev);printf("\t spi_device->reg: %#x\n",spi_device->reg);}
上述代码提取出来宿主节点的信息。
实例代码
struct list_head device_list;char *dev_name[]={"none","I2C","SPI"};struct device{int type;char name[MAX_NAME_LEN];struct list_head list;};struct i2c_node{int data;unsigned int reg;struct device dev;};struct spi_node{unsigned int reg;struct device dev;};void display_i2c_device(struct device *device){struct i2c_node *i2c_device=container_of(device, struct i2c_node, dev);printf("\t i2c_device->data: %d\n",i2c_device->data);printf("\t i2c_device->reg: %#x\n",i2c_device->reg);}void display_spi_device(struct device *device){struct spi_node *spi_device=container_of(device, struct spi_node, dev);printf("\t spi_device->reg: %#x\n",spi_device->reg);}void display_device(struct device *device){printf("\t dev.type: %d\n",device->type);printf("\t dev.type: %s\n",dev_name[device->type]);printf("\t dev.name: %s\n",device->name);}void display_list(struct list_head *list_head){int i=0;struct list_head *p;struct device *entry;printf("-------list---------\n");list_for_each(p,list_head){printf("node[%d]\n",i++);entry=list_entry(p,struct device,list);switch(entry->type){case I2C_TYPE:display_i2c_device(entry);break;case SPI_TYPE:display_spi_device(entry);break;default:printf("unknown device type!\n");break;}display_device(entry);}printf("-------end----------\n");}void i2c_register_device(struct device*dev){struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev);i2c_device->dev.type = I2C_TYPE;strcpy(i2c_device->dev.name,"yikoulinux");list_add(&dev->list,&device_list);}void spi_register_device(struct device*dev){struct spi_node *spi_device=container_of(dev, struct spi_node, dev);spi_device->dev.type = SPI_TYPE;strcpy(spi_device->dev.name,"yikoupeng");list_add(&dev->list,&device_list);}void i2c_unregister_device(struct device *device){struct i2c_node *i2c_device=container_of(dev, struct i2c_node, dev);list_del(&device->list);}void spi_unregister_device(struct device *device){struct spi_node *spi_device=container_of(dev, struct spi_node, dev);list_del(&device->list);}int main(void){struct i2c_node dev1;struct spi_node dev2;INIT_LIST_HEAD(&device_list);dev1.data = 1;dev1.reg = 0x40009000;i2c_register_device(&dev1.dev);dev2.reg = 0x40008000;spi_register_device(&dev2.dev);display_list(&device_list);unregister_device(&dev1.dev);display_list(&device_list);return 0;}
代码主要功能：
-
117-118 ：定义两个不同类型的节点dev1,dev2；
-
120 ：初始化设备链表；
-
121-122、124：初始化节点数据；
-
123/125 :向链表device_list注册这两个节点；
-
126 ：显示该链表；
-
127 ：删除节点dev1;
-
128 :显示该链表。
程序运行截图
读者可以试试如何管理更多类型的节点。
实例3 实现节点在两个链表上自由移动
功能描述：
初始化两个链表，实现两个链表上节点的插入和移动。每个节点维护大量的临时内存数据。
节点创建
节点结构体创建如下：
struct mylist{int number;char type;char *pmem; //内存存放地址，需要mallocstruct list_head list;};
需要注意成员pmem，因为要维护大量的内存，我们最好不要直定义个很大的数组，因为定义的变量位于栈中，而一般的系统给栈的空间是有限的，如果定义的变量占用空间太大，会导致栈溢出，一口君曾经就遇到过这个bug。
链表定义和初始化
链表定义如下：
structlist_head active_head;struct list_head free_head;
初始化
INIT_LIST_HEAD(&free_head);INIT_LIST_HEAD(&active_head);
这两个链表如下：
关于节点，因为该实例是从实际项目中剥离出来，节点启示是起到一个缓冲去的作用，数量不是无限的，所以在此我们默认最多10个节点。
我们不再动态创建节点，而是先全局创建指针数组，存放这10个节点的地址，然后将这10个节点插入到对应的队列中。
数组定义：
structmylist*list_array[BUFFER_NUM];这个数组只用于存放指针，所以定义之后实际情况如下：
初始化这个数组对应的节点：
static ssize_t buffer_ring_init(){int i=0;for(i=0;i<BUFFER_NUM;i++){list_array[i]=malloc(sizeof(struct mylist));INIT_LIST_HEAD(&list_array[i]->list);list_array[i]->pmem=kzalloc(DATA_BUFFER_SIZE,GFP_KERNEL);}return 0;}
5：为下标为i的节点分配实际大小为sizeof(structmylist)的内存
6：初始化该节点的链表
7：为pmem成员从堆中分配一块内存
初始化完毕，链表实际情况如下：
节点插入
static ssize_t insert_free_list_all(){int i=0;for(i=0;i<BUFFER_NUM;i++){list_add(&list_array[i]->list,&free_head);}return 0;}
8：用头插法将所有节点插入到free_head链表中
所有节点全部插入free链表后，结构图如下：
遍历链表
虽然可以通过数组遍历链表，但是实际在操作过程中，在链表中各个节点的位置是错乱的。所以最好从借助list节点来查找各个节点。
show_list(&free_head);
show_list(&active_head);
代码实现如下：
void show_list(struct list_head *list_head){int i=0;struct mylist*entry,*tmp;//判断节点是否为空if(list_empty(list_head)==true){return;}list_for_each_entry_safe(entry,tmp,list_head,list){printf("[%d]=%d\t",i++,entry->number);if(i%4==0){printf("\n");}}}
节点移动
Moving the node from the active_head linked list to the free_head linked list is a bit like the consumer in the producer-consumer model. After eating the resources, the node must be placed in the free linked list so that the producer can continue to produce data, so these two functions I named them eat and spit, which means eating and spitting. I hope you don’t think it’s weird.
int eat_node(){struct mylist*entry=NULL;if(list_empty(&active_head)==true){printf("list active_head is empty!-----------\n");}entry=list_first_entry(&active_head,struct mylist,list);printf("\t eat node=%d\n",entry->number);list_move_tail(&entry->list,&free_head);}
The idea of node movement is:
1. Use list_empty to determine whether the linked list is empty
2. Use list_first_entry to find a node from the active_head linked list, and use the pointer entry to point to the node
3. Use list_move_tail to move the node into the free_head linked list. Note that list_add cannot be used here, because I want to delete this node from the original linked list and then insert it into the new linked list.
Move the node from the free_head linked list to the active_head linked list.
spit_node(){struct mylist*entry=NULL;if(list_empty(&free_head)==true){printf("list free_head is empty!-----------\n");}entry=list_first_entry(&free_head,struct mylist,list);printf("\t spit node=%d\n",entry->number);list_move_tail(&entry->list,&active_head);}
Most of the functions have been explained, let’s post the complete code below.
Code example
enum {false = 0,true = 1};struct mylist{int number;char type;char *pmem;struct list_head list;};struct list_head active_head;struct list_head free_head;struct mylist*list_array[BUFFER_NUM];int born_number(int number){struct mylist *entry=NULL;if(list_empty(&free_head)==true){printf("list free_head is empty!----------------\n");}entry = list_first_entry(&free_head,struct mylist,list);entry->type = DATA_TYPE;entry->number=number;list_move_tail(&entry->list,&active_head);}int eat_node(){struct mylist*entry=NULL;if(list_empty(&active_head)==true){printf("list active_head is empty!-----------\n");}entry=list_first_entry(&active_head,struct mylist,list);printf("\t eat node=%d\n",entry->number);list_move_tail(&entry->list,&free_head);}spit_node(){struct mylist*entry=NULL;if(list_empty(&free_head)==true){printf("list free_head is empty!-----------\n");}entry=list_first_entry(&free_head,struct mylist,list);printf("\t spit node=%d\n",entry->number);list_move_tail(&entry->list,&active_head);}void show_list(struct list_head *list_head){int i=0;struct mylist*entry,*tmp;if(list_empty(list_head)==true){return;}list_for_each_entry_safe(entry,tmp,list_head,list){printf("[%d]=%d\t",i++,entry->number);if(i%4==0){printf("\n");}}}int list_num(struct list_head *list_head){int i=0;struct mylist *entry,*tmp;// printf("----------show free list-------------\n");list_for_each_entry_safe(entry,tmp,list_head,list){i++;}return i;}static ssize_t buffer_ring_init(){int i=0;for(i=0;i<BUFFER_NUM;i++){list_array[i]=malloc(sizeof(struct mylist));INIT_LIST_HEAD(&list_array[i]->list);list_array[i]->pmem=kzalloc(DATA_BUFFER_SIZE,GFP_KERNEL);list_add_tail(&list_array[i]->list,&free_head);}return 0;}static ssize_t insert_free_list_all(){int i=0;for(i=0;i<BUFFER_NUM;i++){list_add_tail(&list_array[i]->list,&free_head);}return 0;}static ssize_t buffer_ring_free(){int buffer_count=0;struct mylist*entry=NULL;for(;buffer_count<BUFFER_NUM;buffer_count++){free(list_array[buffer_count]->pmem);free(list_array[buffer_count]);}return 0;}int main(int argc,char**argv){INIT_LIST_HEAD(&free_head);INIT_LIST_HEAD(&active_head);buffer_ring_init();insert_free_list_all();born_number(1);born_number(2);born_number(3);born_number(4);born_number(5);born_number(6);born_number(7);born_number(8);born_number(9);born_number(10);printf("\n----------active list[%d]------------\n",list_num(&active_head));show_list(&active_head);printf("\n--------------end-----------------\n");printf("\n----------free list[%d]------------\n",list_num(&free_head));show_list(&free_head);printf("\n--------------end-----------------\n");printf("\n\n active list----------> free list \n");eat_node();eat_node();eat_node();printf("\n----------active list[%d]------------\n",list_num(&active_head));show_list(&active_head);printf("\n--------------end-----------------\n");printf("\n----------free list[%d]------------\n",list_num(&free_head));show_list(&free_head);printf("\n--------------end-----------------\n");printf("\n\n free list----------> active list \n");spit_node();spit_node();printf("\n----------active list[%d]------------\n",list_num(&active_head));show_list(&active_head);printf("\n--------------end-----------------\n");printf("\n----------free list[%d]------------\n",list_num(&free_head));show_list(&free_head);printf("\n--------------end-----------------\n");}
The running results are as follows:
list_head is short and concise, readers can learn from this article to implement other functions.
Reference documentation: https://kernelnewbies.org/FAQ/LinkedLists
"Understanding linux kernel"
《Linux device drivers》
list.h is relatively long, so I won’t post the source code here. If readers want to obtain this file, they can identify the QR code below and fill in a friend of Yiyijun to request the file. Yiyijun also has a lot of Linux learning materials.
Recommended reading
【2】 Teach Linux driver step by step 2-Module parameter param and symbol export export usage
【3】 Teach Linux driver step by step 3-Detailed explanation of character device architecture, this article is enough
[4] Step-by-step tutorial on Linux driver 4 - detailed explanation of the relationship between process, file descriptor, file, and inode
[5] How to recover accidentally deleted files or directories on Linux
5T technical resources are on sale! Including but not limited to: C/C++, Linux, Python, Java, PHP, artificial intelligence, microcontroller, Raspberry Pi, etc. Reply " 1024 " in the official account to get it for free! !
京公网安备 11010802033920号