plist 源码解析
plist 是内核中一种带优先级的双向链表数据结构,链表中每个元素的优先级按数值大小升序排序。plist 作为 pi-futex 的一部分补丁引入内核,初始提交链接为:https://github.com/torvalds/linux/commit/77ba89c5cf28d5d98a3cae17f67a3e42b102cc25。本文基于 6.2-rc2 版本内核解析 plist 实现,阅读本文需要了解 kernel 中 list 数据结构的实现,因为 plist 是基于 list 实现的。
基本结构
plist 是基于 kernel 中的双向链表 list 实现的,其有两个重要结构体:struct plist_head
和 struct plist_node
,分别表示 plist 的 head 和普通结点,它们的具体内容如下:
1 | struct plist_head { |
struct plist_head
中只有一个 struct list_head node_list;
成员,其是 struct plist_node
中 struct list_head node_list;
的 head,这个链表包含了加入 plist 的所有结点。从 struct plist_node
结构体中看到还有另外一个会由 struct list_head prio_list;
构成的链表,这个链表可能没有包含全部的结点,因为相同优先级的结点只有第一个会加入 prio_list
中。这个链表用于加速找到要插入结点的正确位置,由于每个优先级只有一个结点会在链表上,所以这个链表的长度最长是优先级的范围。假设优先级范围为 K,在插入一个新元素时就会遍历 prio_list
链表来找到正确的位置,那么最多就只会遍历 K 个元素,这保证了插入元素算法的最坏复杂度为 O(K)
。prio
成员自然就表示该结点的优先级了。
下面来个实例看看 plist 中具体结构是怎么样的。
通过类似
PLIST_HEAD(example_head)
定义并初始化一个struct plist_head example_head;
结点,我们将得到以下结构:上图中
node_list
表示struct plist_head
结构体中的struct list_head node_list;
成员,prev
和next
表示node_list
中的struct list_head *prev;
和struct list_head *next;
。往
example_head
中加入一个优先级为 20 的结点struct plist_node node1;
:
往
example_head
中加入一个优先级为 19 的结点struct plist_node node2;
:
再次往
example_head
中加入一个优先级为 20 的结点struct plist_node node3;
:
API
根据操作方法可以分为以下几种 API:
- 初始化
- 辅助性宏/函数,如第一个结点
plist_first
,下一个结点plist_next
等 - 遍历
- 增加删除
初始化
初始化有头结点初始化和普通结点初始化两种 API,这两种又分为静态初始化和动态初始化。
头结点初始化
头结点静态初始化有两个 API: PLIST_HEAD_INIT
和 PLIST_HEAD
,而 PLIST_HEAD
是通过 PLIST_HEAD_INIT
实现的。一般使用 PLIST_HEAD
初始化一个 struct plist_head
结构体:
1 |
具体用法如 mm/swapfile.c
中 static PLIST_HEAD(swap_active_head);
。当然也可借助 PLIST_HEAD_INIT
宏来完成 plist_head
的初始化了,如 kernel/power/qos.c
中这样使用:
1 | static struct pm_qos_constraints cpu_latency_constraints = { |
头结点的动态初始化 API 为 plist_head_init
:
1 | static inline void |
一般 head
不能或者不方便静态初始化时,譬如 mm/swapfile.c
中 plist_head_init(&swap_avail_heads[nid]);
。
普通结点初始化
普通结点通过 PLIST_NODE_INIT
静态初始化:
1 |
如 init/init_task.c
中:
1 | struct task_struct init_task |
通过 plist_node_init
来动态初始化:
1 | static inline void plist_node_init(struct plist_node *node, int prio) |
如 mm/swapfile.c
中 plist_node_init(&p->avail_lists[i], 0);
。
辅助性宏/函数
plist 中的辅助性宏/函数从功能、返回值来看可以分为三类,第一类是判断头结点或普通结点是否是空的,头结点如果是空的,表示链表是空链表,普通结点是空的则意味这个结点没有在任何一个链表上;第二类是返回值为 struct plist_node *
类型,即返回一个 plist 结点;第三类返回一个包含了 struct plist_node
的结构体地址。第二类和第三类假设 plist 是不为空的,如果在链表为空时调用这两类宏/函数,则会返回一个不正确的结构体地址,当访问这个结构体的某些成员时可能会造成内核功能紊乱或者 panic,如果开启了 CONFIG_DEBUG_PLIST
,某些宏/函数会调用 WARN_ON
发出警报。
第一类有两个内联函数,分别用于判断头结点和普通结点是否为空:
plist_head_empty
:这个函数用于判断链表是否为空,若为空返回非零值,否则返回 0。1
2
3
4
5
6
7
8/**
* plist_head_empty - return !0 if a plist_head is empty
* @head: &struct plist_head pointer
*/
static inline int plist_head_empty(const struct plist_head *head)
{
return list_empty(&head->node_list);
}plist_node_empty
:这个函数用于判断这个结点是否在一个链表上,若不在返回非零值,否则返回 0。1
2
3
4
5
6
7
8/**
* plist_node_empty - return !0 if plist_node is not on a list
* @node: &struct plist_node pointer
*/
static inline int plist_node_empty(const struct plist_node *node)
{
return list_empty(&node->node_list);
}
第二类有两个内联函数和两个宏:
plist_first
:这个函数返回 node_list 链表上第一个结点,这个结点也是优先级最高的结点(值越小,优先级越高)。1
2
3
4
5
6
7
8
9
10
11/**
* plist_first - return the first node (and thus, highest priority)
* @head: the &struct plist_head pointer
*
* Assumes the plist is _not_ empty.
*/
static inline struct plist_node *plist_first(const struct plist_head *head)
{
return list_entry(head->node_list.next,
struct plist_node, node_list);
}plist_last
:这个函数返回 node_list 链表上最后一个结点,这个结点也是优先级最低的结点(值越小,优先级越高)。1
2
3
4
5
6
7
8
9
10
11/**
* plist_last - return the last node (and thus, lowest priority)
* @head: the &struct plist_head pointer
*
* Assumes the plist is _not_ empty.
*/
static inline struct plist_node *plist_last(const struct plist_head *head)
{
return list_entry(head->node_list.prev,
struct plist_node, node_list);
}plist_prev
:这个宏的1
2
3
4
5
6/**
* plist_prev - get the prev entry in list
* @pos: the type * to cursor
*/pos
参数一定要是struct plist_node *
类型,并且不能是第一个结点。所以调用之前要确保1.链表不为空,2.pos
在链表上,3.plist_first(head) != pos.plist_next
:其功能和1
2
3
4
5
6/**
* plist_next - get the next entry in list
* @pos: the type * to cursor
*/plist_prev
相反。这个宏的pos
参数一定要是struct plist_node *
类型,并且不能是最后一个结点。所以调用之前要确保1️⃣链表不为空,2️⃣pos
在链表上,3️⃣plist_last(head) != pos.
第三类有两个宏:
plist_first_entry
:这个宏返回包含第一个结点的结构体,用法可参考1
2kernel/sched/rt.c
中的pick_next_pushable_task
函数:1
2
3
4struct task_struct *p;
p = plist_first_entry(&rq->rt.pushable_tasks,
struct task_struct, pushable_tasks);plist_last_entry
:这个宏返回包含最后一个结点的结构体,用法可参考1
2plist_first_entry
。
遍历
遍历 API 可以分为两类,第一类是每次迭代拿到的是 struct plist_node *
类型;第二类是每次迭代拿到的是包含 struct plist_node
的结构体。每一类都有三个 API。
第一类:
plist_for_each
:从头开始遍历 node_list,1
2pos
是struct plist_node *
类型变量,pos 可以不用做初始化,用法类似:1
2
3
4
5
6// 假设有一个链表 struct plist_head head;
struct plist_node *pos;
plist_for_each(pos, &head) {
...;
}plist_for_each_continue
:1
2pos
是一个struct plist_node *
类型,其一定要已经是链表上的一个结点。这个宏从pos
的下一个位置开始遍历直到 head。用法可参考plist_requeue
:1
2
3
4
5
6
7
8
9
10
11void plist_requeue(struct plist_node *node, struct plist_head *head)
{
struct plist_node *iter;
iter = plist_next(node);
plist_for_each_continue(iter, head) {
...;
}
...;
}plist_for_each_safe
:这个宏可以在遍历的过程中删除1
2pos
结点。pos
和n
都是struct plist_node *
类型,n
是用在遍历内部保存pos
的下一个结点的。用法参考:第二类的三个函数和第一类的三个函数功能基本一样,只不过1
2
3
4
5
6
7
8// 假设有一个链表 struct plist_head head;
struct plist_node *pos, *n;
plist_for_each_safe(pos, n, &head) {
// 这里面不能对 n 做任何操作,以免破坏遍历
plist_del(pos, &head);
...;
}pos
的类型是包含struct plist_node
的结构体类型。plist_for_each_entry
:从1
2head
开始遍历,用法参考mm/swapfile.c
中swapoff
系统调用:可见,第一个参数的类型已经不是1
2
3
4
5
6
7
8struct swap_info_struct *p = NULL;
// static struct plist_head *swap_avail_heads;
plist_for_each_entry(p, &swap_active_head, list) {
if (p->flags & SWP_WRITEOK) {
...;
}
}struct plist_node *
了,而是一个包含struct plist_node
类型的结构体指针:1
2
3
4
5struct swap_info_struct {
...;
struct plist_node list; /* entry in swap_active_head */
...;
};plist_for_each_entry_continue
:从1
2pos
的下一个元素开始遍历直到head
结点。用法参考mm/swapfile.c
中swapoff
系统调用:1
2
3
4
5struct swap_info_struct *si = p;
plist_for_each_entry_continue(si, &swap_active_head, list) {
...;
}plist_for_each_entry_safe
:遍历时可安全删除1
2pos
。用法参考mm/swapfile.c
中get_swap_pages
函数:1
2
3
4
5
6
7struct swap_info_struct *si, *next;
node = numa_node_id();
plist_for_each_entry_safe(si, next, &swap_avail_heads[node], avail_lists[node]) {
plist_requeue(&si->avail_lists[node], &swap_avail_heads[node]);
...;
}
增加删除
增加的 API 是 plist_add
函数,删除是 plist_del
函数。还有一个特殊的函数,相当于优化版本的先删除再加入:plist_requeue
,这个函数的用途是譬如系统中有很多个 swapfile,可能有几个 swapfile 的优先级是相同的,那么我们希望可以轮询使用相同优先级的 swapfile,具体操作就是遍历这个 swapfile 时,调用 plist_requeue
函数将当前 swapfile 置于相同优先级的最后一个,这样就可以达到轮询相同优先级的效果了。下面一一详解上述几个函数。
plist_add
plist_add
源码可结合前面的示例图来阅读,示例图除了第一步的初始化之外,后面的几步都是相当于调用 plist_add
函数来实现的。
1 | /** |
以下是我写的一个内核模块用于测试 plist_add
:
1 | // plist_add_test.c |
1 | # Makefile |
ubuntu 20.04 下编译:
1 | make |
插入模块:
1 | sudo insmod plist_add_test.ko |
查看 kernel log:
1 | dmesg -w |
删除模块:
1 | sudo rmmod plist_add_test.ko |
plist_del
plist_del
的功能是删除一个结点:
1 | void plist_del(struct plist_node *node, struct plist_head *head) |
plist_requeue
plist_requeue
相当于优化版本的 plist_del
,然后 plist_add
。优化点在于:假设 node_list 上有 n
个和 node 优先级一样的结点,其实现的相当于 plist_add
的操作仅需要遍历 n
次。当然这个实现也未必就会比 plist_add
好,如果 n
很大,但是 prio_list 上的结点数很少,那还是 plist_add
更快。
1 | void plist_requeue(struct plist_node *node, struct plist_head *head) |
debug
plist 的 debug 功能由 CONFIG_DEBUG_PLIST
控制,开启了之后, plist 会有一个单元测试模块 plist_test
对 plist 功能进行自检。此外,还有像在 plist_add
等函数中的 plist_check_head
函数,这个函数会遍历 prio_list 和 node_list,检查每个结点的 prev 和 next 值是否一致,若是不一致,只会调用 WARN
进行警告。CONFIG_DEBUG_PLIST
还会在 plist_first_entry
和 plist_last_entry
两个宏中检查链表是否为空,如果为空,也仅是 WARN_ON
。