Linux内核链表
·
通常，链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，针域用于建立与下一个节点的联系。但在Linux内核链表中，不是在链表结构中包含数据，而是在各种特定数据结构中包含链表节点。在linux中许多大规模的数据就是通过内嵌链表，将数据很好的组织起来的，给遍历，查询的相关处理提供了方便。
内核链表的结构是个双向循环链表，只有指针域，数据域根据使用链表的人的具体需求而定。内核链表设计哲学：
既然链表不能包含万事万物，那么就让万事万物来包含链表。
首先先解析两个宏，内核链表里面大量用到了这两个宏offsetof 和 container_of。
一、offset_of
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)1.1、作用
给定一个结构体类型 TYPE 和其成员 MEMBER，获取结构体成员相对于结构体起始位置的偏移量。
1.2、解析
参数 (TYPE, MEMBER)：
TYPE 是要计算偏移量的结构体的类型。
MEMBER 是这个结构体中的一个成员。
类型转换 ((TYPE *)0)：
(TYPE *)0 将地址0强制转换为指向结构体 TYPE 的指针。这并不会真正访问该地址，因为我们只不过是想利用指针运算的特性来计算偏移量，而不是实际访问。
成员访问 (->MEMBER)：
((TYPE *)0)->MEMBER 意味着我们以类型为 TYPE 的结构体对象来访问 MEMBER。在这里，0地址被用作基地址，通过指针指向该结构体的假设位置。
取地址 (&)：
&操作符用于获取 MEMBER 的地址。因为基础地址是0，所以这里的地址实际上就是成员在结构体中的偏移量。
转换为size_t：
将最后的结果显式转换为 size_t 类型，以确保结果是一个无符号整数，通常用于表示内存大小或偏移量。
二、container_of
/**
* 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) );})2.1、作用
用于从指向结构体成员的指针获取指向包含该成员的结构体的指针。
2.2、解析
宏定义：
#define container_of(ptr, type, member)此宏定义使用了三个参数：
ptr: 指向某个结构体成员的指针，对应成员变量 member。
type: 包含该成员的结构体类型。
member: 在结构体中的成员变量，对应指针 ptr。
类型推断：
const typeof( ((type *)0)->member ) *__mptr = (ptr);typeof：这一语法用于推断指定表达式的类型，在这里它推断的是成员变量member的类型。
((type *)0)->member：这一句和我们之前的offset_of类似，通过将0转换为结构体类型的指针并获取成员，实际上不会访问位置0，而是用于获取该成员的类型。
__mptr：是一个const类型的指针，指向member成员类型，用于确保ptr与成员类型一致。
计算结构体起始地址：
(type *)((char *)__mptr - offset_of(type, member));(char *)__mptr：将__mptr（即ptr）转换为char*，这样可以进行字节级的指针运算。
offset_of(type, member)：计算成员在结构体中的偏移量。见之前对offset_of的解释，该宏通过指针运算实现。
((char *)__mptr - offset_of(type, member))：通过从ptr中减去成员相对于结构体的偏移，得到整个结构体在内存中的起始地址。
(type *)：把计算得到的地址转换为type结构体类型的指针，得到指向整个结构体的指针。
总结
offset_of：对于给定的一个结构的成员，获取其成员相对于首地址的偏移。
container_of：对于给定结构成员的地址，返回其结构体指针（所有者）首地址。
三、list_head
struct list_head {
struct list_head *next, *prev;
};要了解内核链表，就不得不提 list_head。这个结构很有意思，整个结构没有数据域，只有两个指针域。
链表初始化
内核提供两种方式来初始化链表：宏初始化和接口初始化。
3.1 宏初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)LIST_HEAD_INIT 设计的很精妙，这个宏本身不包含任何数据类型，也就是说没有限定唯一的数据类型，这就使得整个链表足够灵活，具备通用性。
LIST_HEAD 这个宏定义了对于任意给定的结构指针，将前驱 (prev) 和后继 (next) 指针都指向自己，作为链表头指针。
宏初始化用一句话表示，如下：
struct list_head name = { &(name), &(name) }可见，结构体 name 的指针next、prev都指向自己。
3.2 接口初始化
/**
* INIT_LIST_HEAD - Initialize a list_head structure
* @list: list_head structure to be initialized.
*
* Initializes the list_head to point to itself. If it is a list header,
* the result is an empty list.
*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}接口操作就比较直接明了，和宏实现的意图一样，直接将链表头指针的前驱 (prev) 和后继 (next) 都指向自己。
创建一个链表头：
3.3 链表节点的创建
前面说了 list_head 只有指针域，没有数据域，如果只是这样就没有什么意义了。所以我们需要创建一个宿主结构，然后再再此结构包含 list 字段，宿主结构，也有其他字段（进程描述符，页面管理结构等都是采用这种方法创建链表的）。
创建链表的一个节点：
这里list 的prev 和next 都指向list 自己了，并且list 属于链表节点struct student的成员。只需要遍历到 list 节点就能根据前面讲的 container_of 推导得到其宿主结构的地址，从而访问 data 值。如果有其他方法，也可访问。
四、插入
/**
* 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_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);
}内核链表提供了相应的添加节点的接口：list_add、list_add_tail。list_add 和 list_add_tail 最终调用的都是 __list_add 函数。list_add 是头部插入一个节点，list_add_tail 是尾部插入一个节点。
list_add 和 list_add_tail的区别是：
list_add 始终是在链表头后的的第一个位置进行插入：例如链表：head --> 数据1 --> 数据2 --> 数据3，插入新元素后：head --> new --> 数据1 --> 数据2 --> 数据3
list_add_tail 始终实在链表末尾插入新元素：例如链表：head --> 数据1 --> 数据2 --> 数据3，插入新元素后：head --> 数据1 --> 数据2 --> 数据3 --> new
仔细分析上述函数，可以发现其函数抽象的巧妙。
__list_add 接收三个参数：分别是new, prev, next。任何位置的双链表插入操作，只需这3个参数。那么new元素一定是在prev和next之间进行插入。
所以很明显：list_add是在head和head->next之间插入，那就是链表的第一个元素。
list_add_tail实在head->prev和head之间插入，那就是链表的最后一个元素。
4.1 list_add 示例如下
（1）创建一个链表头：g_stu_list
INIT_LIST_HEAD(&g_stu_list);
（2）再创建第一个链表节点
（3）把这个节点插入到list后
list_add(&p->list, &g_stu_list);
（4）再创建、插入第二个链表节点
以此类推，每次插入一个新节点，都是紧靠着 header 节点，而之前插入的节点依次排序靠后，那最后一个节点则是第一次插入 header 后的那个节点。先来的节点靠后，而后来的节点靠前。
使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu;
struct list_head *pos;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list);
for (i = 0; i < 5; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add(&p->list, &g_stu_list);
}
printf("\r\n");
printf("..............list_for_each start................\n");
list_for_each(pos, &g_stu_list) {
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("..............list_for_each start................\n");
printf("\r\n");
return 0;
}
运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list test_list.c
bjws210:~/Desktop/klist$ ./test_list
i: 0, id: 0, name: mt-00, score: 90, &list = 0x55795c9942c8
i: 1, id: 1, name: mt-01, score: 91, &list = 0x55795c994718
i: 2, id: 2, name: mt-02, score: 92, &list = 0x55795c994758
i: 3, id: 3, name: mt-03, score: 93, &list = 0x55795c994798
i: 4, id: 4, name: mt-04, score: 94, &list = 0x55795c9947d8
..............list_for_each start................
id: 4----name: mt-04----score: 94
id: 3----name: mt-03----score: 93
id: 2----name: mt-02----score: 92
id: 1----name: mt-01----score: 91
id: 0----name: mt-00----score: 90
..............list_for_each start................4.2 list_add_tail 的示例如下
（1）创建一个链表头：g_stu_list
INIT_LIST_HEAD(&g_stu_list);
（2）再创建第一个链表节点
（3）尾部插入第一个节点
（4）尾部插入第二个节点
每次插入的新节点都是紧挨着 header 表尾，而插入的第一个节点排在了第一位，第二个排在了第二位。先插入的节点排在前面，后插入的节点排在后面。
使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu;
struct list_head *pos;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list);
for (i = 0; i < 5; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list);
}
printf("\r\n");
printf("..............list_for_each start................\n");
list_for_each(pos, &g_stu_list) {
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("..............list_for_each start................\n");
printf("\r\n");
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_add_tail.c
bjws210:~/Desktop/klist$ ./test_list
i: 0, id: 0, name: mt-00, score: 90, &list = 0x55fd6c6212c8
i: 1, id: 1, name: mt-01, score: 91, &list = 0x55fd6c621718
i: 2, id: 2, name: mt-02, score: 92, &list = 0x55fd6c621758
i: 3, id: 3, name: mt-03, score: 93, &list = 0x55fd6c621798
i: 4, id: 4, name: mt-04, score: 94, &list = 0x55fd6c6217d8
..............list_for_each start................
id: 0----name: mt-00----score: 90
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
..............list_for_each start................五、删除
内核链表同样定义了删除节点的两个接口 list_del、list_del_init。
/**
* 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(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
list_del 和 list_del_init 是内核链表外部接口，__list_del 和 __list_entry 是内核链表内部节点。__list_del 这个接口，根据prev/next 删除其节点，删除的节点必须是已知的并且 prev 和 next 不为空。
__list_del_entry 本质还是调用了__list_del 。list_del 作用是删除双链表中的一个节点，并将节点的 prev 和 next 都指向特定位置LIST_POSITION1和LIST_POSITION2。
list_del_init 作用是删除双链表中的一个节点，并将节点的 prev 和 next 都指向自己，回到最开始创建节点前的状态。被删除的节点，list_del 中将其 prev、next 指针分别被设为 LIST_POSITION2和LIST_POSITION1两个特值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应，list_del_init 函数将节点从链表中解下来之后，调用LIST_INIT_HEAD 将节点置为空链状态。利用 list_del 和 list_del_init 接口都可以删除链表中的任意节点了，需注意，前提条件是这个节点是已知的，既在链表中真实存在，且prev，next指针都不为NULL。
使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu;
struct list_head *pos = NULL, *temp = NULL;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list);
for (i = 0; i < 5; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list);
}
printf("\r\n");
printf("..............list_for_each_safe delete node start................\n");
list_for_each_safe(pos, temp, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
if (pstu->id == 3)
{
list_del(&pstu->list);
}
}
printf("..............list_for_each_safe delete node end................\n");
printf("\r\n");
printf("..............list_for_each_safe delete and print list................\n");
list_for_each_safe(pos, temp, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("..............list_for_each_safe delete node end................\n");
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_del.c
bjws210:~/Desktop/klist$ ./test_list
i: 0, id: 0, name: mt-00, score: 90, &list = 0x558b01fd62c8
i: 1, id: 1, name: mt-01, score: 91, &list = 0x558b01fd6718
i: 2, id: 2, name: mt-02, score: 92, &list = 0x558b01fd6758
i: 3, id: 3, name: mt-03, score: 93, &list = 0x558b01fd6798
i: 4, id: 4, name: mt-04, score: 94, &list = 0x558b01fd67d8
..............list_for_each_safe delete node start................
id: 0----name: mt-00----score: 90
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
..............list_for_each_safe delete node end................
..............list_for_each_safe delete and print list................
id: 0----name: mt-00----score: 90
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 4----name: mt-04----score: 94
..............list_for_each_safe delete node end................六、搬移
内核链表提供了将原本属于一个链表的节点移动到另一个链表的操作，并根据插入到新链表的位置分为两类：头部搬移和尾部搬移。搬移的本质就是删除加插入。内核链表提供了相应的搬移节点的接口：list_move、list_move_tail。
6.1 头部搬移
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}头部搬移即在一个链表中用内部函数 __list_del_entry 删除该节点，在另一个链表用 list_add 头部插入该节点。
6.2 尾部搬移
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del_entry(list);
list_add_tail(list, head);
}尾部搬移即在一个链表中用内部函数 __list_del_entry 删除该节点，在另一个链表用 list_add_tail 尾部插入该节点。
使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list1;
struct list_head g_stu_list2;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu;
struct list_head *pos = NULL, *temp = NULL;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list1);
INIT_LIST_HEAD(&g_stu_list2);
printf("..............build 1st list................\n");
for (i = 1; i < 4; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list1);
}
printf("\r\n");
printf("..............build 2st list................\n");
for (i = 4; i < 7; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list2);
}
printf("\r\n");
printf("..............add list2 id5 to list1 tail................\n");
list_for_each_safe(pos, temp, &g_stu_list2) {
pstu = list_entry(pos, struct student, list);
if (pstu->id == 5)
{
list_move_tail(&pstu->list, &g_stu_list1);
break;
}
}
list_for_each_safe(pos, temp, &g_stu_list1) {
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_move.c
bjws210:~/Desktop/klist$ ./test_list
..............build 1st list................
i: 1, id: 1, name: mt-01, score: 91, &list = 0x556cedf436d8
i: 2, id: 2, name: mt-02, score: 92, &list = 0x556cedf43718
i: 3, id: 3, name: mt-03, score: 93, &list = 0x556cedf43758
..............build 2st list................
i: 4, id: 4, name: mt-04, score: 94, &list = 0x556cedf43798
i: 5, id: 5, name: mt-05, score: 95, &list = 0x556cedf437d8
i: 6, id: 6, name: mt-06, score: 96, &list = 0x556cedf43818
..............add list2 id5 to list1 tail................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 5----name: mt-05----score: 95七、合并
内核链表还提供两组合并操作，将两条链表合并在一起，list_splice 和 list_splice_init，list_splice_tail 和 list_splice_tail_init。
/**
* list_splice - join two lists, this is designed for stacks
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(const struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head, head->next);
}
/**
* list_splice_tail - join two lists, each list being a queue
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head->prev, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head, head->next);
INIT_LIST_HEAD(list);
}
}
/**
* list_splice_tail_init - join two lists and reinitialise the emptied list
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* Each of the lists is a queue.
* The list at @list is reinitialised
*/
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head->prev, head);
INIT_LIST_HEAD(list);
}
}list_splice 将源链表的所有节点插入到目标链表的头部，不改变源链表头指针的状态，源链表头指针仍然指向原来的节点。
list_splice_tail 将源链表的所有节点插入到目标链表的尾部，不改变源链表头指针的状态，源链表头指针仍然指向原来的节点。
list_splice_init 将源链表的所有节点插入到目标链表的头部，用 INIT_LIST_HEAD 将源链表设置为空链，源链表的头指针的 prev 和 next 都指向自己，回到最开始初始化前的状态。
list_splice_tail_init 将源链表的所有节点插入到目标链表的尾部，用 INIT_LIST_HEAD 将源链表设置为空链，源链表的头指针的 prev 和 next 都指向自己，回到最开始初始化前的状态。
用 list_splice 和 list_splice_tail 函数合并链表 list1 和 list2 时，当 list2 被挂接到 list1 之后，作为原表头指针的 list2 的 next、prev 仍然指向原来的节点，为了避免引起混乱，Linux提供了一个list_splice_init 和 list_splice_tail_init 函数，该函数在将 list2 合并到 list1 链表的基础上，调用 INIT_LIST_HEAD 将 list2 设置为空链。
使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list1;
struct list_head g_stu_list2;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu;
struct list_head *pos;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list1);
INIT_LIST_HEAD(&g_stu_list2);
printf("..............build 1st list................\n");
for (i = 1; i < 4; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list1);
}
printf("\r\n");
printf("..............build 2st list................\n");
for (i = 4; i < 7; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list2);
}
printf("\r\n");
printf("..............add list2 to list1................\n");
list_splice_tail_init(&g_stu_list2, &g_stu_list1);
list_for_each(pos, &g_stu_list1) {
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_splice.c
bjws210:~/Desktop/klist$ ./test_list
..............build 1st list................
i: 1, id: 1, name: mt-01, score: 91, &list = 0x55f025e956d8
i: 2, id: 2, name: mt-02, score: 92, &list = 0x55f025e95718
i: 3, id: 3, name: mt-03, score: 93, &list = 0x55f025e95758
..............build 2st list................
i: 4, id: 4, name: mt-04, score: 94, &list = 0x55f025e95798
i: 5, id: 5, name: mt-05, score: 95, &list = 0x55f025e957d8
i: 6, id: 6, name: mt-06, score: 96, &list = 0x55f025e95818
..............add list2 to list1................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
id: 5----name: mt-05----score: 95
id: 6----name: mt-06----score: 96
八、替换
内核链表还提供一组替换链表节点的操作。
list_replace：将新的节点替换到旧的节点上。
list_replace_init：将新的节点替换到旧的节点上。同时将旧的节点的 prev 和 next 指向自己，反初始化。
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/**
* list_replace_init - replace old entry by new one and initialize the old one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}使用示例：
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu, *pstu_temp;
struct list_head *pos = NULL, *temp = NULL;
char tmp[32] = { 0 };
struct student new_stu = {.id = 8, .name = "mt-08", .score = 100};
INIT_LIST_HEAD(&g_stu_list);
for (i = 1; i < 6; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list);
}
printf("\r\n");
printf("..............replace list id4 with id8................\n");
list_for_each_entry_safe(pstu, pstu_temp, &g_stu_list, list)
{
if(pstu->id == 4)
{
list_replace(&pstu->list, &new_stu.list);
}
}
list_for_each_entry(pstu, &g_stu_list, list)
{
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_replace.c
bjws210:~/Desktop/klist$ ./test_list
i: 1, id: 1, name: mt-01, score: 91, &list = 0x55705da352c8
i: 2, id: 2, name: mt-02, score: 92, &list = 0x55705da35718
i: 3, id: 3, name: mt-03, score: 93, &list = 0x55705da35758
i: 4, id: 4, name: mt-04, score: 94, &list = 0x55705da35798
i: 5, id: 5, name: mt-05, score: 95, &list = 0x55705da357d8
..............replace list id4 with id8................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 8----name: mt-08----score: 100
id: 5----name: mt-05----score: 95九、检测
9.1 检测是否是链表最后一个节点
/**
* list_is_last - tests whether @list is the last entry in list @head
* @list: the entry to test
* @head: the head of the list
*/
static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}list_is_last 用于检测一个节点 list 是否为链表 head 中的最后一个节点。换句话说，它检查指定的节点的下一个节点是否指向链表头，从而确定该节点是否是链表中的最后一个有效节点。如果节点 list 是链表中的最后一个节点，则返回 true（非零值），否则返回 false（0）。
9.2 检测是否是链表第一个节点
/**
* list_is_first -- tests whether @list is the first entry in list @head
* @list: the entry to test
* @head: the head of the list
*/
static inline int list_is_first(const struct list_head *list,
const struct list_head *head)
{
return list->prev == head;
}9.3 检测链表是否为空
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head *head)
{
return READ_ONCE(head->next) == head;
}list_empty 用于检查链表是否为空。它通过检查链表头的下一个节点是否指向链表头本身来确定链表是否没有元素。该函数是很重要的工具，用于在对链表进行操作之前验证是否有需要处理的元素，从而避免不必要的操作或访问无效内存。如果 head 链表为空，则返回 true（非零值），否则返回 false（0）。
十、遍历
10.1 list_entry
1）list_entry
/**
* 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)遍历的关键就是这个 list_entry 宏。本质就是 container_of 宏。这个宏的主要作用就是获取宿主结构的指针地址。前文提到，我们是以 list 指针为节点组成的一条双链表，遍历的过程中只能得到 list 的地址，那么对于其所有者地址就是通过这个宏获取的。
ptr: 指向 struct list_head 的指针，即链表节点。
type: 链表节点所属的结构体类型。
member: struct list_head 成员在结构体中的名称。
2）list_first_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_first_entry 用于获取链表中第一个元素的指针。使用 list_first_entry 之前，需要确保链表不是空的，否则可能会解引用一个无效指针。
ptr：指向链表头部的指针 (struct list_head 类型)。
type：包含 struct list_head 成员的结构体类型。
member：结构体内 struct list_head 类型的成员名。
3）list_last_entry
/**
* list_last_entry - get the last 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_last_entry(ptr, type, member) \
list_entry((ptr)->prev, type, member)list_last_entry 用于获取链表中最后一个元素的指针。使用 list_last_entry 前必须确认链表不为空，否则会导致内存访问错误。
ptr：指向链表头部的指针（类型为 struct list_head）。
type：包含 struct list_head 成员的结构体类型。
member：此结构体中的 struct list_head 成员的名称。
4）list_first_entry_or_null
/**
* list_first_entry_or_null - 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 if the list is empty, it returns NULL.
*/
#define list_first_entry_or_null(ptr, type, member) ({ \
struct list_head *head__ = (ptr); \
struct list_head *pos__ = READ_ONCE(head__->next); \
pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
})list_first_entry_or_null 用于从一个链表中获取第一个元素的指针。如果链表为空，则该宏返回 NULL。
ptr: 指向链表头部的指针 (struct list_head 类型)。
type: 包含 struct list_head 成员的结构体类型。
member: 此结构体中的 struct list_head 成员的名称。
本质是调用list_empty 判断是否为空，list_empty 用于检查链表是否为空。它返回一个布尔值，链表为空时为真。如果链表不为空，使用 list_first_entry 返回第一个元素。如果链表为空，返回 NULL。
5）list_next_entry
/**
* 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)list_next_entry 用于在一个链表中获取给定元素的下一个元素的指针。在遍历链表时，请注意循环的结束条件，避免无限循环或访问越界。
pos: 当前链表元素的指针，指向一个包含 struct list_head 成员的结构体。
member: 结构体中的 struct list_head 成员的名称。
6）list_prev_entry
/**
* list_prev_entry - get the prev element in list
* @pos: the type * to cursor
* @member: the name of the list_head within the struct.
*/
#define list_prev_entry(pos, member) \
list_entry((pos)->member.prev, typeof(*(pos)), member)list_prev_entry 用于在一个链表中获取给定元素的前一个元素的指针。在遍历链表时，请注意循环的结束条件，以避免无限循环或访问越界。
pos: 当前链表元素的指针，指向一个包含 struct list_head 成员的结构体。
member: 结构体中的 struct list_head 成员的名称。
10.2 list_for_each
1）list_for_each
/**
* 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)list_for_each 用于遍历链表中的每一个元素。该宏假设链表已经初始化，即便没有元素，至少有一个有效的头节点。
pos: struct list_head 类型的指针，用于在循环中指示当前迭代位置。
head: 链表头，是一个 struct list_head 指针，指向链表的头部位置。
2）list_for_each_prev
/**
* 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)list_for_each_prev 从尾到头遍历一个链表，对链表的反向遍历，list_for_each 是对链表的正向遍历，从头到尾遍历一个链表。在使用 list_for_each_prev 之前，请确保链表已经正确初始化。即使链表为空，也需要有一个有效的头节点。
pos: 遍历时的游标，用于指向当前链表节点的 struct list_head 指针。
head: 链表头，一个 struct list_head 指针，指示循环链表的根。
10.3 list_for_each_safe
1）list_for_each_safe
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)list_for_each_safe 用于遍历链表，能够在遍历过程中安全地移除链表的元素而不会导致遍历失败。这在链表操作中尤为常见，因为有时需要在循环中根据某种条件删除节点。pos: 循环游标，一个 struct list_head 类型的指针，表示当前遍历到的链表节点。
n: 临时存储的 struct list_head 指针，用于在删除当前节点后，保存下一个节点的位置。
head: 链表头，一个 struct list_head 指针，指示循环链表的起点。在每次循环中，pos 是当前位置节点，n 是下一个节点。在循环体结束时用 pos = n 更新 pos，使用 n = pos->next 更新 n。这样保持 n 总是指向 pos 的下一个节点，确保了即使 pos 被删除，n 仍然有效，使得链表的浏览既安全又稳定。
2）list_for_each_prev_safe
/**
* list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)list_for_each_prev_safe 与 list_for_each_safe 不同之处，list_for_each_safe 是正向遍历，list_for_each_prev_safe 是反向遍历。
10.4 list_for_each_entry
1）list_for_each_entry
/**
* 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); \
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))list_for_each_entry 主要功能是遍历一个双向链表（list_head）的所有元素，同时允许用户访问每个节点的具体结构体。pos: 用于循环的指针，类型为实际节点结构体指针（如 struct my_struct *）。
head: 指向链表头节点的指针。
member: 链表节点在结构体中的 struct list_head 成员的名称。
list_for_each_entry 和 list_for_each有什么区别呢？
list_for_each：提供底层的遍历，适用于需要链表头结构或进行复杂指针操作的场景。但使用时需要手动转换节点类型，可能导致类型错误。
list_for_each_entry：针对特定节点类型的高层次遍历方式，简化代码并提高可读性。在大多数情况下，更推荐使用此宏，尤其当你直接需要访问节点中的数据时。
2）list_for_each_entry_reverse
/**
* 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); \
!list_entry_is_head(pos, head, member); \
pos = list_prev_entry(pos, member))相比list_for_each_entry，list_for_each_entry_reverse 用于以反向顺序遍历Linux内核中的双向链表。
10.5 list_for_each_entry_safe
1）list_for_each_entry_safe
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))list_for_each_entry_safe 允许在遍历链表时安全地删除当前节点。即使在删除当前节点的情况下，遍历的下一个节点仍然可以访问，这避免了因删除操作导致的遍历错误。pos：一个指针，指向当前遍历到的链表节点。通常是在结构体中定义的，例如 struct my_struct *pos。
n：另一个指针，指向下一个将要遍历的节点。它用于保存当前节点的下一个节点，以确保在当前节点被删除时，仍能继续遍历链表。
head：指向链表头节点的指针，通常是一个 struct list_head 类型的指针。这个指针用于判断遍历是否到达链表的端点。
member：表示链表节点在其结构体中的 list_head 成员的名称。这通常是一个 struct list_head 类型的指针，允许宏在结构体中访问链接到链表的成员。
2）list_for_each_entry_safe_reverse
/**
* list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*
* Iterate backwards over list of given type, safe against removal
* of list entry.
*/
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member), \
n = list_prev_entry(pos, member); \
!list_entry_is_head(pos, head, member); \
pos = n, n = list_prev_entry(n, member))list_for_each_entry_safe_reverse 的主要作用是在双向链表中从最后一个节点开始安全反向遍历，同时支持在遍历过程中删除当前节点。确保删除操作不会导致指针失效，允许后续的遍历继续进行。pos：指向当前遍历的链表节点的指针，通常是指向节点结构体的类型，例如 struct my_struct *pos。
n：用于保存当前节点 pos 的前一个节点的指针，以便在当前节点被删除时，可以继续遍历。
head：指向链表头节点的指针，通常是一个 struct list_head 类型。它用于判断是否到达链表的起始位置。
member：表示链表节点中 list_head 成员的名称，允许宏访问链表中节点的连接成员。
10.6 使用示例
#include "list.h"
struct student
{
int id;
char name[32];
unsigned int score;
struct list_head list;
};
struct list_head g_stu_list;
int main(int argc,char **argv)
{
int i;
struct student *p, *pstu, *pstu_temp;
struct list_head *pos = NULL, *temp = NULL;
char tmp[32] = { 0 };
INIT_LIST_HEAD(&g_stu_list);
for (i = 1; i < 6; i++) {
p = (struct student *)malloc(sizeof(struct student));
p->id = i;
memset(tmp, 0, sizeof(tmp));
snprintf(tmp, sizeof(tmp) - 1, "mt-0%d", i);
strcpy(p->name, tmp);
p->score = 90 + i;
printf("i: %d, id: %d, name: %s, score: %d, &list = %p\n", i, p->id, p->name, p->score, &p->list);
list_add_tail(&p->list, &g_stu_list);
}
printf("\r\n");
printf("..............list_for_each................\n");
list_for_each(pos, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_safe................\n");
list_for_each_safe(pos, temp, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_entry................\n");
list_for_each_entry(pstu, &g_stu_list, list)
{
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_entry_safe................\n");
list_for_each_entry_safe(pstu, pstu_temp, &g_stu_list, list)
{
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n \r\n");
printf("..............xxx_prev................\n");
printf("..............list_for_each_prev................\n");
list_for_each_prev(pos, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_prev_safe................\n");
list_for_each_prev_safe(pos, temp, &g_stu_list)
{
pstu = list_entry(pos, struct student, list);
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_entry_reverse................\n");
list_for_each_entry_reverse(pstu, &g_stu_list, list)
{
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
printf("..............list_for_each_entry_safe_reverse................\n");
list_for_each_entry_safe_reverse(pstu, pstu_temp, &g_stu_list, list)
{
printf("id: %d----name: %s----score: %d\n", pstu->id, pstu->name, pstu->score);
}
printf("\r\n");
return 0;
}运行结果：
bjws210:~/Desktop/klist$ gcc -o test_list list_for_each.c
bjws210:~/Desktop/klist$ ./test_list
i: 1, id: 1, name: mt-01, score: 91, &list = 0x55b492bf42c8
i: 2, id: 2, name: mt-02, score: 92, &list = 0x55b492bf4718
i: 3, id: 3, name: mt-03, score: 93, &list = 0x55b492bf4758
i: 4, id: 4, name: mt-04, score: 94, &list = 0x55b492bf4798
i: 5, id: 5, name: mt-05, score: 95, &list = 0x55b492bf47d8
..............list_for_each................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
id: 5----name: mt-05----score: 95
..............list_for_each_safe................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
id: 5----name: mt-05----score: 95
..............list_for_each_entry................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
id: 5----name: mt-05----score: 95
..............list_for_each_entry_safe................
id: 1----name: mt-01----score: 91
id: 2----name: mt-02----score: 92
id: 3----name: mt-03----score: 93
id: 4----name: mt-04----score: 94
id: 5----name: mt-05----score: 95
..............xxx_prev................
..............list_for_each_prev................
id: 5----name: mt-05----score: 95
id: 4----name: mt-04----score: 94
id: 3----name: mt-03----score: 93
id: 2----name: mt-02----score: 92
id: 1----name: mt-01----score: 91
..............list_for_each_prev_safe................
id: 5----name: mt-05----score: 95
id: 4----name: mt-04----score: 94
id: 3----name: mt-03----score: 93
id: 2----name: mt-02----score: 92
id: 1----name: mt-01----score: 91
..............list_for_each_entry_reverse................
id: 5----name: mt-05----score: 95
id: 4----name: mt-04----score: 94
id: 3----name: mt-03----score: 93
id: 2----name: mt-02----score: 92
id: 1----name: mt-01----score: 91
..............list_for_each_entry_safe_reverse................
id: 5----name: mt-05----score: 95
id: 4----name: mt-04----score: 94
id: 3----name: mt-03----score: 93
id: 2----name: mt-02----score: 92
id: 1----name: mt-01----score: 91十一， 使用双向链表实现一个FIFO
//链表元素的定义
/*Define a data structure that contains a list_head*/
struct fifo_queue {
struct list_head next;
unsigned char *fifo_data;
unsigned int data_length;
#ifdef REPLACE_KTIME
struct timespec64 timestamp;
#else
struct timeval timestamp;
#endif
};
struct ts_tcm {
/* fifo to pass the data to userspace */
unsigned int fifo_remaining_frame;
//链表头
struct list_head frame_fifo_queue;
wait_queue_head_t wait_frame;
unsigned char report_to_queue[REPORT_TYPES];
};
//链表初始化
INIT_LIST_HEAD(&tcm->frame_fifo_queue);
//生产者
/**
* ts_cdev_insert_fifo()
*
* Insert/Push the data to the queue.
*
* This function is called by ts_cdev_update_report_queue(),
* where the event data will be placed as the below format in byte
* and use this function to store the data in queue.
* [0 ] : status / report code
* [1 : 2 ] : length of data frame
* [3 : N + 3] : N bytes of data payload
*
* @param
* [ in] tcm: the driver handle
* [ in] buf_ptr: points to a data going to push
* [ in] length: data length
*
* @return
* on success, 0; otherwise, negative value on error.
*/
static int ts_cdev_insert_fifo(struct ts_tcm *tcm,
unsigned char *buf_ptr, unsigned int length)
{
int retval = 0;
struct fifo_queue *pfifo_data;
struct fifo_queue *pfifo_data_temp;
static int pre_remaining_frames = -1;
//锁保护
ts_pal_mutex_lock(&g_fifo_queue_mutex);
/* check queue buffer limit */
//如果fifo达到了limit，丢弃掉最旧的节点
if (tcm->fifo_remaining_frame >= FIFO_QUEUE_MAX_FRAMES) {
if (tcm->fifo_remaining_frame != pre_remaining_frames)
LOGI("Reached %d and drop FIFO first frame\n",
tcm->fifo_remaining_frame);
pfifo_data_temp = list_first_entry(&tcm->frame_fifo_queue,
struct fifo_queue, next);
list_del(&pfifo_data_temp->next);
kfree(pfifo_data_temp->fifo_data);
kfree(pfifo_data_temp);
pre_remaining_frames = tcm->fifo_remaining_frame;
tcm->fifo_remaining_frame--;
} else if (pre_remaining_frames >= FIFO_QUEUE_MAX_FRAMES) {
LOGI("Reached limit, dropped oldest frame, remaining:%d\n",
tcm->fifo_remaining_frame);
pre_remaining_frames = tcm->fifo_remaining_frame;
}
//构建一个新的链表节点
pfifo_data = kmalloc(sizeof(*pfifo_data), GFP_KERNEL);
if (!(pfifo_data)) {
LOGE("Failed to allocate memory\n");
LOGE("Allocation size = %zu\n", (sizeof(*pfifo_data)));
retval = -ENOMEM;
goto exit;
}
pfifo_data->fifo_data = kmalloc(length, GFP_KERNEL);
if (!(pfifo_data->fifo_data)) {
LOGE("Failed to allocate memory, size = %d\n", length);
retval = -ENOMEM;
goto exit;
}
pfifo_data->data_length = length;
memcpy((void *)pfifo_data->fifo_data, (void *)buf_ptr, length);
#ifdef REPLACE_KTIME
ktime_get_real_ts64(&(pfifo_data->timestamp));
#else
do_gettimeofday(&(pfifo_data->timestamp));
#endif
/* append the data to the tail for FIFO queueing */
//尾部插入
list_add_tail(&pfifo_data->next, &tcm->frame_fifo_queue);
tcm->fifo_remaining_frame++;
retval = 0;
exit:
ts_pal_mutex_unlock(&g_fifo_queue_mutex);
return retval;
}
//消费者
/**
* ts_cdev_ioctl_get_frame()
*
* Read the data from the queue and return to userspace if data is
* copied or the specified timeout is expired.
*
* Please be noted that the retried data is formatted as follows.
* [0 ] : status / report code
* [1 : 2 ] : length of data frame
* [3 : N + 3] : N bytes of data payload
*
* @param
* [ in] tcm: the driver handle
* [in/out] ubuf_ptr: points to a memory space from userspace
* [ in] buf_size: size of given space
* [out] frame_size: frame size returned
*
* @return
* on success, 0; otherwise, negative value on error.
*/
static int ts_cdev_ioctl_get_frame(struct ts_tcm *tcm,
const unsigned char *ubuf_ptr, unsigned int buf_size,
unsigned int *frame_size)
{
int retval = 0;
int timeout = 0;
unsigned char timeout_data[4] = {0};
struct fifo_queue *pfifo_data;
if (!tcm->is_connected) {
LOGE("Not connected\n");
return _EINVAL;
}
if (buf_size < sizeof(timeout_data)) {
LOGE("Invalid sync data size, buf_size:%d\n", buf_size);
retval = -EINVAL;
goto exit;
}
retval = copy_from_user(timeout_data, ubuf_ptr, sizeof(timeout_data));
if (retval) {
LOGE("Fail to copy data from user space, size:%d\n", retval);
retval = -EBADE;
goto exit;
}
/* get the waiting duration */
timeout = ts_pal_le4_to_uint(&timeout_data[0]);
LOGD("Wait time: %dms\n", timeout);
//如果fifo是空的，等待timeout ms
if (list_empty(&tcm->frame_fifo_queue)) {
LOGD("The queue is empty, wait for the frame\n");
retval = wait_event_interruptible_timeout(tcm->wait_frame,
(tcm->fifo_remaining_frame > 0),
msecs_to_jiffies(timeout));
if (retval == 0) {
LOGD("Queue waiting timed out after %dms\n", timeout);
retval = -ETIMEDOUT;
*frame_size = 0;
goto exit;
}
LOGD("Data queued\n");
}
/* confirm the queue status */
if (list_empty(&tcm->frame_fifo_queue)) {
LOGD("Is queue empty? The remaining frame = %d\n",
tcm->fifo_remaining_frame);
retval = -ENODATA;
goto exit;
}
//锁保护
ts_pal_mutex_lock(&g_fifo_queue_mutex);
//从头部取出链表的第一个节点
pfifo_data = list_first_entry(&tcm->frame_fifo_queue,
struct fifo_queue, next);
LOGD("Pop data from the queue, data length = %d\n",
pfifo_data->data_length);
if (buf_size >= pfifo_data->data_length) {
retval = copy_to_user((void *)ubuf_ptr,
pfifo_data->fifo_data,
pfifo_data->data_length);
if (retval) {
LOGE("Fail to copy data to user space, size:%d\n",
retval);
retval = -EBADE;
}
*frame_size = pfifo_data->data_length;
} else {
LOGE("No enough space for data copy, buf_size:%d data:%d\n",
buf_size, pfifo_data->data_length);
retval = -EOVERFLOW;
goto exit;
}
LOGD("From FIFO: (0x%02x, 0x%02x, 0x%02x, 0x%02x)\n",
pfifo_data->fifo_data[0], pfifo_data->fifo_data[1],
pfifo_data->fifo_data[2], pfifo_data->fifo_data[3]);
//删除出fifo的链表节点
list_del(&pfifo_data->next);
if (retval >= 0)
retval = pfifo_data->data_length;
kfree(pfifo_data->fifo_data);
kfree(pfifo_data);
if (tcm->fifo_remaining_frame != 0)
tcm->fifo_remaining_frame--;
ts_pal_mutex_unlock(&g_fifo_queue_mutex);
exit:
return retval;
}
/**
* ts_cdev_clean_queue()
*
* Clean the data queue.
* All data in the queue will be cleaned up in every time of device
* open and close.
*
* @param
* [ in] tcm: the driver handle
*
* @return
* void.
*/
static void ts_cdev_clean_queue(struct ts_tcm *tcm)
{
struct fifo_queue *pfifo_data;
//插入/删除fifo节点的时候都需要加锁保护
ts_pal_mutex_lock(&g_fifo_queue_mutex);
while (!list_empty(&tcm->frame_fifo_queue)) {
pfifo_data = list_first_entry(&tcm->frame_fifo_queue,
struct fifo_queue, next);
list_del(&pfifo_data->next);
kfree(pfifo_data->fifo_data);
kfree(pfifo_data);
if (tcm->fifo_remaining_frame != 0)
tcm->fifo_remaining_frame--;
}
LOGD("Queue cleaned, frame: %d\n", tcm->fifo_remaining_frame);
ts_pal_mutex_unlock(&g_fifo_queue_mutex);
}
参考链接：
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
26
0- 0
已为社区贡献1条内容
所有评论(0)