Linux 内核学习(3) - Linux Kernel 常用的数据结构_init_list_head

Linux Kernel 常用的数据结构

List

1 List

• 所有的接口都定义在include/linux/list.h中

代码1 list结构体定义 include/linux/types.h

struct list_head {
	struct list_head *next, *prev;
};
1
2
3

• 虽然以 head 命名，但所有节点都是使用同一个结构
• 在使用的时候都是将该结构内嵌在其它的结构中(因为这个结构没有定义任何数据)

代码2 将list嵌入到自己的数据中

struct our_struct {
    int our_data;
    struct list_head node;
};
1
2
3
4

• list_entry()从list_head对应到我们自定义的结构

  • list_entry通过container_of实现

• list 常用接口

  • 初始化

    • 编译时初始化 LIST_HEAD_INIT() / LIST_HEAD()
    • 运行时初始化 INIT_LIST_HEAD()

  • 修改list

    • list_add(new, add)
    • list_del(entry)
    • list_replace(old, new)
    • list_move(list, head)
    • list_splice()
    • list_cut_position(list, head, entry) 将head从entry的位置删除分开，并将前一部分链入到list中

  • 测试

    • list_empty()
    • list_empty_careful() 测试list是否为空并且没有正在被修改，通常用于lockless的情况；注意，删除一端必须要重新初始化(list_del_init())，而不是重新加入List

  • 遍历

    • list_for_each_entry()
    • list_for_each_entry_reverse()
    • list_for_each_entry_continue(pos, head, member) 从指定的位置起开始遍历
    • list_for_each_entry_continue_reverse()
    • list_for_each_entry_safe() 用于在遍历的时候本身可能被删除的情况。注意，只限于本身被删除，如果是后续节点被删除必须重新开始遍历

代码3 list示例

#include <linux/module.h>
#include <linux/kthread.h>
#include <linux/delay.h>
#include <linux/slab.h>  // 用于内存分配
#include <linux/list.h>

MODULE_AUTHOR("OneGhost");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("The module is only used for test");

#define MAX_LIST 10

struct our_data {
    int i;
    struct list_head list;
};

static void list_test(void) {
    int i;
    struct our_data *node, *next;
    LIST_HEAD(lhead);
    for (i = 0; i < MAX_LIST; i++) {
        struct our_data *data;

        data = kmalloc(sizeof(*data), GFP_KERNEL);
        if (!data) {
            goto clean;
        }
        data->i = i;
        list_add(&data->list, &lhead);
    }
    list_for_each_entry(node, &lhead, list)
        printk("list entry: %d.\n", node->i);
    clean:
    list_for_each_entry_safe(node, next, &lhead, list)
        kfree(node);
}

static __init int minit(void) {
    printk("call %s.\n", __FUNCTION__);
    list_test();
    return 0;
}

static __exit void mexit(void) {
    printk("call %s.\n", __FUNCTION__);
}

module_init(minit)
module_exit(mexit)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

运行结果

[17528.366481] call minit.
[17528.366490] list entry: 9.
[17528.366497] list entry: 8.
[17528.366503] list entry: 7.
[17528.366510] list entry: 6.
[17528.366516] list entry: 5.
[17528.366522] list entry: 4.
[17528.366529] list entry: 3.
[17528.366536] list entry: 2.
[17528.366542] list entry: 1.
[17528.366549] list entry: 0.
[17532.834926] call mexit.
1
2
3
4
5
6
7
8
9
10
11
12

2 hlist

• 和list定义在同一个头文件中，且与list类似，但有区别
  • 区分头结点和中间结点，头结点用struct hlist_head，而中间节点用struct hlist_node:
  • head节点里面只有一个first指针，减少了指针使用。通常用于哈希表，表中的每一项都是hlist
  • 结点中的指针指向不一样
    • hlist_node中的prev指针是指向它前一个对象的next指针的地址
    • 这是因为hlist_head中的对象类型是hlist_node，所以不需要单独处理head的情况

代码4 hlist结构

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};
1
2
3
4
5
6
7

• 从内嵌的hlist转换到自定义的结构: hlist_entry()
• 常用接口
  • 初始化
    • 初始化头部 HLIST_HEAD_INIT HLIST_HEAD() INIT_HLIST_HEAD()
    • 初始化中间节点 INIT_HLIST_NODE()
  • 修改hlist
    • hlist_add_head()
    • hlist_add_before(n, new)
    • hlist_add_after(n, new)
    • hlist_del()
    • hlist_move_list()
  • 测试
    • hlist_empty()
    • hlist_unhashed() 测试中间节点是否在hlist中
  • 遍历
    • hlist_for_each_entry()
    • hlist_for_each_entry_safe() 一边遍历一边删除当前节点

例子5

#include <linux/module.h>
#include <linux/kthread.h>
#include <linux/delay.h>
#include <linux/slab.h>  // 用于内存分配
#include <linux/list.h>

MODULE_AUTHOR("OneGhost");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("The module is only used for test");

#define MAX_LIST 10

struct our_data {
    int i;
    struct hlist_node list;
};

static void list_test(void) {
    int i;
    struct our_data *node;
    struct hlist_node *next;
    HLIST_HEAD(lhead);
    for (i = 0; i < MAX_LIST; i++) {
        struct our_data *data;
        data = kmalloc(sizeof(*data), GFP_KERNEL);
        if (!data) {
            goto clean;
        }
        data->i = i;
        hlist_add_head(&data->list, &lhead);
    }
    hlist_for_each_entry(node, &lhead, list)
        printk("list entry: %d.\n", node->i);
    clean:
    hlist_for_each_entry_safe(node, next, &lhead, list)
        kfree(node);
}

static __init int minit(void) {
    printk("call %s.\n", __FUNCTION__);
    list_test();
    return 0;
}

static __exit void mexit(void) {
    printk("call %s.\n", __FUNCTION__);
}

module_init(minit)
module_exit(mexit)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3 RCU list

• 包括 rcu list 和 rcu hlist
• 定义在#include <linux/rculist.h>
• RCU list的APIs封装了rcu的使用接口
• 主要用于持有rcu lock来对list/hlist进行只读遍历
• 对list/hlist进行更改时，需要调用者本身进行并发控制访问
• 常用接口
  • 初始化
    • INIT_LIST_HEAD_RCU();
    • 用hlist_first_rcu来初始化hlist_head
  • 读侧
    • 使用rcu来保护list / hlist
    • list_for_each_entry_rcu()
    • hlist_for_each_entry_rcu()
  • 更新侧
    • 需要自己做并发控制，在释放资源的时候需要使用RCU的同步机制来和写侧进行同步
    • list_add_rcu()
    • list_add_tail_rcu()
    • list_del_rcu()
    • list_replace_rcu()
    • list_splice_init_rcu()
    • hlist_del_rcu()
    • hlist_replace_rcu()
    • hlist_add_head_rcu()

4 RB tree 红黑树

• Linux Kernel中的红黑树
  • 定义在include/linux/rbtree.h中
  • 中间节点和叶子节点定义为 struct rb_node，其内嵌在我们自定义的结构体（与list类似），使用rb_entry()来从rb_node转换到自定义结构
  • 根节点定义为 struct rb_root
• 使用红黑树
  • 初始化根节点： struct rb_root mytree = RB_ROOT;
  • 红黑树的搜索 (linux kernel中通常使用的是小序)
    • 与普通二叉树类似，都是从根节点开始遍历，如果当前节点的值小于查找值则查找左孩子，如果等于就是当前节点，如果大于则查找右孩子
  • 插入节点：利用上述的搜索算法找到要插入的位置然后调用rb_list_node(node, parent, rb_link)将新节点插入到tree，最后调用rb_insert_color(node, root)来配色
  • 删除节点： rb_erase(victim, root)
  • 其它
    • rb_replace_node(old, new, tree)
    • rb_fist(tree)
    • rb_last(tree)
    • rb_next(tree)
    • rb_prev(tree)

代码6 红黑树的搜索

struct mytype *my_search(struct rb_root *root, char *string) {
    struct rb_node *node = root->rb_node;
    while (node) {
        struct mytype *data = container_of(node, struct mytype, node);
        int result;
        result = strcmp(string, data->keystring);
        if (result < 0)
            node = node->rb_left;
        else if (result > 0)
            node = node->rb_right;
        else
            return data;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码7 插入红黑树

int my_insert(struct rb_root *root, struct mytype *data) {
    struct rb_node **new = &(root->rb_node), *parent = NULL;
    while (*new) {
        struct mytype *this = container_of(*new, struct mytype, node);
        int result = strcmp(data->keystring, this->keystring);
        parent = *new;
        if (result < 0)
            new = &((*new)->rb_left);
        else if (result > 0)
            new = &((*new)->rb_right);
        else
            return FALSE;
    }
    rb_link_node(&data->node, parent, new);
    rb_insert_color(&data->node, root);
    return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17