Priority List

| 分类 Kernel  | 标签 kernel  linux  list 

1 概念与实现

Priority List (plist) 是用双向链表 (double-linked list) 构建的,降序排列优先级的链表。

/**
 * Simplifications of the original code by
 * Oleg Nesterov <oleg@tv-sign.ru>
 *
 * Licensed under the FSF's GNU Public License v2 or later.
 *
 * Based on simple lists (include/linux/list.h).
 *
 * This is a priority-sorted list of nodes; each node has a
 * priority from INT_MIN (highest) to INT_MAX (lowest).
 *
 * Addition is O(K), removal is O(1), change of priority of a node is
 * O(K) and K is the number of RT priority levels used in the system.
 * (1 <= K <= 99)
 *
 */

相关定义:

 1: struct list_head {
 2:     struct list_head *next, *prev;
 3: };
 4: 
 5: struct plist_head {
 6:     struct list_head node_list;
 7: };
 8: 
 9: struct plist_node {
10:     int         prio;
11:     struct list_head    prio_list;
12:     struct list_head    node_list;
13: };

其中:

  • list_head 1 是简单的双向链表
  • plist_head 5 是 Priority List
  • plist_node 9 是 PList 的节点

plist_head 可被其他模块作为 List 头来使用,而 plist_node 则是 plist 实现的核心,其中:

  • prio 为优先级
    如前面的注释所解释的一样,优先级可以是 INT_MININT_MAX 的任意数值。
  • prio_list 优先级列表
    用来标识不同优先级的节点。并非所有的 plist_node 都会被使用该表,在同一个 plist 里面,每一个优先级里面只会有一个 plist_node 会用到 prio_list ,其余的node 的该表指针均指向他自己。这在 plist_add 的代码中可以看出来。 prio_list 起到的作用和 skip_list 类似,可以快速的定位到第一个优先级为 prio 的 data node 上。
  • node_list 排序的 node list
    所有的节点的 node_list 都会被使用,并最终链接都表头。

函数 plist_add 用于向 plist_head 中添加新的 plist_node ,其实现的代码很精简,可以体现出插入过程中做了什么东西,也可以推测插入后的效果:

 1: /**
 2:  * plist_add - add @node to @head
 3:  *
 4:  * @node:   &struct plist_node pointer
 5:  * @head:   &struct plist_head pointer
 6:  */
 7: void plist_add(struct plist_node *node, struct plist_head *head)
 8: {
 9:     struct plist_node *first, *iter, *prev = NULL;
10:     struct list_head *node_next = &head->node_list;
11: 
12:     plist_check_head(head);
13:     WARN_ON(!plist_node_empty(node));
14:     WARN_ON(!list_empty(&node->prio_list));
15: 
16:     if (plist_head_empty(head))
17:         goto ins_node;
18: 
19:     first = iter = plist_first(head);
20: 
21:     do {
22:         if (node->prio < iter->prio) {
23:             node_next = &iter->node_list;
24:             break;
25:         }
26: 
27:         prev = iter;
28:         iter = list_entry(iter->prio_list.next,
29:                 struct plist_node, prio_list);
30:     } while (iter != first);
31: 
32:     if (!prev || prev->prio != node->prio)
33:         list_add_tail(&node->prio_list, &iter->prio_list);
34: ins_node:
35:     list_add_tail(&node->node_list, node_next);
36: 
37:     plist_check_head(head);
38: }

2 图解几个状态

  1. 未添加任何 node 的表头

empty_phead.png

  1. 未加入 list 的 plist_node

    各种指针都指向自己

    pnode_0.png

  2. 添加一个 plist_node

    1node.png

  3. 添加两个不同的 Node:

    2nodes.png

  1. 添加三个 Node,其中有两个 prio 相同:

    3nodes.png

3 测试代码

 1: #include <linux/module.h>   /* Needed by all modules */
 2: #include <linux/kernel.h>   /* Needed for KERN_INFO */
 3: #include <linux/list.h>
 4: #include <linux/plist.h>
 5: 
 6: MODULE_LICENSE("Dual BSD/GPL");
 7: 
 8: 
 9: extern void plist_add(struct plist_node *node, struct plist_head *head);
10: 
11: struct
12: {
13:     struct plist_node n;
14:     int idx;
15: } t_node;
16: 
17: #define ARRAY_SIZE(X)       (int)(sizeof(X)/sizeof(X[0]))
18: 
19: static inline void t_node_init(t_node* n, int i) {
20:     plist_node_init((struct plist_node*)n, 0);
21:     n->idx = i;
22: }
23: void plist_add(struct plist_node *node, struct plist_head *head)
24: {
25:     struct plist_node *first, *iter, *prev = NULL;
26:     struct list_head *node_next = &head->node_list;
27: 
28:     WARN_ON(!plist_node_empty(node));
29:     WARN_ON(!list_empty(&node->prio_list));
30: 
31:     if (plist_head_empty(head))
32:         goto ins_node;
33: 
34:     first = iter = plist_first(head);
35: 
36:     do {
37:         if (node->prio < iter->prio) {
38:             node_next = &iter->node_list;
39:             break;
40:         }
41: 
42:         prev = iter;
43:         iter = list_entry(iter->prio_list.next,
44:                           struct plist_node, prio_list);
45:     } while (iter != first);
46: 
47:     if (!prev || prev->prio != node->prio)
48:         list_add_tail(&node->prio_list, &iter->prio_list);
49: ins_node:
50:     list_add_tail(&node->node_list, node_next);
51: 
52: }
53: 
54: static int  __init plist_test2(void)
55: {
56:     int i;
57:     struct plist_head test_head;
58:     t_node test_node[16];
59:     t_node* p = test_node;
60:     struct plist_node* pn;
61: 
62:     plist_head_init(&test_head);
63: 
64:     for (i = 0; i < ARRAY_SIZE(test_node); i++) {
65:         p = test_node + i;
66:         t_node_init(p, i);
67:         p->n.prio = i % 3;
68:         plist_add((struct plist_node*)p, &test_head);
69:     }
70: 
71:     plist_for_each(pn, &test_head) {
72:         p = (t_node*) pn;
73:         printk(KERN_INFO
74:                "Note: %p, priv: %d, index: %d,  dnext: %p, dprev: %p, pnext: %p, pprev: %p,\n",
75:                 p,  p->n.prio, p->idx,
76:                 p->n.node_list.next, p->n.node_list.prev,
77:                 p->n.prio_list.next, p->n.prio_list.prev
78:                 );
79:     }
80:     return 0;
81: }
82: 
83: module_init(plist_test2);

Makefile 如下:

 1: #
 2: # Makefile by appleboy <appleboy.tw AT gmail.com>
 3: #
 4: obj-m       += test_list.o
 5: KVERSION := $(shell uname -r)
 6: 
 7: all:
 8:     $(MAKE) -C /lib/modules/$(KVERSION)/build M=$(PWD) modules
 9: 
10: clean:
11:     $(MAKE) -C /lib/modules/$(KVERSION)/build M=$(PWD) clean

当将 test_list.ko 插入内核时:

 1: localhost libtool # dmesg
 2: [ 5746.704648] Note: ffff88000430fa20, priv: 0, index: 0,  dnext: ffff88000430fac8, dprev: ffff88000430fa10, pnext: ffff88000430fa58, pprev: ffff88000430fa88,
 3: [ 5746.704652] Note: ffff88000430fab0, priv: 0, index: 3,  dnext: ffff88000430fb58, dprev: ffff88000430fa38, pnext: ffff88000430fab8, pprev: ffff88000430fab8,
 4: [ 5746.704653] Note: ffff88000430fb40, priv: 0, index: 6,  dnext: ffff88000430fbe8, dprev: ffff88000430fac8, pnext: ffff88000430fb48, pprev: ffff88000430fb48,
 5: [ 5746.704655] Note: ffff88000430fbd0, priv: 0, index: 9,  dnext: ffff88000430fc78, dprev: ffff88000430fb58, pnext: ffff88000430fbd8, pprev: ffff88000430fbd8,
 6: [ 5746.704656] Note: ffff88000430fc60, priv: 0, index: 12,  dnext: ffff88000430fd08, dprev: ffff88000430fbe8, pnext: ffff88000430fc68, pprev: ffff88000430fc68,
 7: [ 5746.704658] Note: ffff88000430fcf0, priv: 0, index: 15,  dnext: ffff88000430fa68, dprev: ffff88000430fc78, pnext: ffff88000430fcf8, pprev: ffff88000430fcf8,
 8: [ 5746.704659] Note: ffff88000430fa50, priv: 1, index: 1,  dnext: ffff88000430faf8, dprev: ffff88000430fd08, pnext: ffff88000430fa88, pprev: ffff88000430fa28,
 9: [ 5746.704661] Note: ffff88000430fae0, priv: 1, index: 4,  dnext: ffff88000430fb88, dprev: ffff88000430fa68, pnext: ffff88000430fae8, pprev: ffff88000430fae8,
10: [ 5746.704662] Note: ffff88000430fb70, priv: 1, index: 7,  dnext: ffff88000430fc18, dprev: ffff88000430faf8, pnext: ffff88000430fb78, pprev: ffff88000430fb78,
11: [ 5746.704664] Note: ffff88000430fc00, priv: 1, index: 10,  dnext: ffff88000430fca8, dprev: ffff88000430fb88, pnext: ffff88000430fc08, pprev: ffff88000430fc08,
12: [ 5746.704665] Note: ffff88000430fc90, priv: 1, index: 13,  dnext: ffff88000430fa98, dprev: ffff88000430fc18, pnext: ffff88000430fc98, pprev: ffff88000430fc98,
13: [ 5746.704667] Note: ffff88000430fa80, priv: 2, index: 2,  dnext: ffff88000430fb28, dprev: ffff88000430fca8, pnext: ffff88000430fa28, pprev: ffff88000430fa58,
14: [ 5746.704668] Note: ffff88000430fb10, priv: 2, index: 5,  dnext: ffff88000430fbb8, dprev: ffff88000430fa98, pnext: ffff88000430fb18, pprev: ffff88000430fb18,
15: [ 5746.704669] Note: ffff88000430fba0, priv: 2, index: 8,  dnext: ffff88000430fc48, dprev: ffff88000430fb28, pnext: ffff88000430fba8, pprev: ffff88000430fba8,
16: [ 5746.704671] Note: ffff88000430fc30, priv: 2, index: 11,  dnext: ffff88000430fcd8, dprev: ffff88000430fbb8, pnext: ffff88000430fc38, pprev: ffff88000430fc38,
17: [ 5746.704672] Note: ffff88000430fcc0, priv: 2, index: 14,  dnext: ffff88000430fa10, dprev: ffff88000430fc48, pnext: ffff88000430fcc8, pprev: ffff88000430fcc8,

上一篇     下一篇