Linux内核设计与实现(五)一一内核数据结构

发表于 | 阅读次数

内核数据结构

Linux内核实现了一些通用的数据结构，提倡大家在开发时重用，内核开发者应该尽可能地使用这些数据结构。最常用的有：链表、队列、映射、二叉树

链表

链表是一种存放和操作可变数量元素(节点)的数据结构，动态创建，无需在内存中占用连续内存区。每个元素都必须包含指向下一个元素的指针，当有元素加入或从链表中删除时，只需要调整相应指针即可

单向链表

每个节点指向一个后驱

1
2
3
4
5
/* an element in a linked list */
struct list_element { 
    void *data; /* the payload */ 
    struct list_element *next; /* pointer to the next element */
};

双向链表

1
2
3
4
5
6
/* an element in a linked list */ 
struct list_element {
    void *data; /* the payload */ 
    struct list_element *next; /* pointer to the next element */ 
    struct list_element *prev; /* pointer to the previous element */
};

环形链表

内核链表实现

使用链表的理想情况是：需要遍历所有数据或需要动态加入或删除数据时

将链表节点塞入数据结构

Linux内核实现方式独树一帜，它不是将数据结构塞入链表，而是将链表节点塞入数据结构

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

比如创建一个fox数据结构来描述犬科动物一员，存储链表节点到fox数据结构中

1
2
3
4
5
6
struct fox { 
    unsigned long tail_length; /* length in centimeters of tail */ 
    unsigned long weight; /* weight in kilograms */ 
    bool is_fantastic; /* is this fox fantastic? */ 
    struct list_head list; /* list of all fox structures */
};

Fox中的list.next指向下一个元素，list.prev指向前一个元素，这样链表就可以被内核使用了。可以用一系列list_add(),list_del()等来操作，但他们有个共同特点，就是只接受list_head结构参数。

这样内核就用一个统一的链表实现，可以操作各种数据结构的应用；使用container_of宏可以很方便的从链表指针找到父结构中任何成员变量

container_of()宏

在C语言中，一个给定结构中的变量偏移，在编译时地址就被ABI固定下来了。
使用container_of()宏，定义一个简单的函数可以方便的返回包含list_head的父类结构体

#define container_of(ptr, type, member) ({ \
const typeof(((type )0)->member) mptr = (ptr); \
(type )((char )mptr - offsetof(type, member)); })

#endif

依靠list_entry()方法，内核提供了创建，操作以及其他管理链表的各种例程—所有这些方法都不需要知道list_head所嵌入对象的数据结构:

1
2
3
4
5
6
7
8
/**
 * 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_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
定义一个链表

list_head本身并没有意义，它需要被嵌入到你自己的数据结构中才能生效。

例如:

1
2
3
4
5
6
struct fox { 
    unsigned long tail_length; /* length in centimeters of tail */ 
    unsigned long weight; /* weight in kilograms */ 
    bool is_fantastic; /* is this fox fantastic? */ 
    struct list_head list; /* list of all fox structures */
};

链表使用前需要初始化:

运行时动态初始化链表

1
2
3
4
5
6
struct fox *red_fox; 
red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL); 
red_fox->tail_length = 40; 
red_fox->weight = 6; 
red_fox->is_fantastic = false; 
INIT_LIST_HEAD(&red_fox->list);

如果一个结构在编译期静态创建，而你需要在其中一个链表中直接引用，下面方式最简洁:

1
2
3
4
5
struct fox red_fox = { 
    .tail_length = 40, 
    .weight = 6, 
    .list = LIST_HEAD_INIT(red_fox.list),
};

如果需要明确的链表头，也可以这样声明:

1
static LIST_HEAD(fox_list);
链表基本操作(算法复杂度全都是O(1))

list_add向链表头后面添加新项，可以用来实现一个栈:

1
static inline void list_add(struct list_head *new, struct list_head *head);

假定创建一个新的struct fox，并把它加入fox_list，那么

1
list_add(&f->list,&fox_list)

list_add_tail向链表头的前面添加节点，可以实现一个FIFO:

1
static inline void list_add_tail(struct list_head *new, struct list_head *head);

例如删除上面添加的f, list_del(&f->list):

1
static inline void list_del(struct list_head *entry);

如果entry删除之后，还有可能添加到另一个链表，删除之后，还应做初始化:

1
static inline void list_del_init(struct list_head *entry);

把节点list从链表中移除，然后加入另一个链表head节点的后面:

1
static inline void list_move(struct list_head *list, struct list_head *head);

把节点list从链表中移除，然后加入另一个链表head节点的前面:

1
static inline void list_move_tail(struct list_head *list, struct list_head *head);

检查链表是否为空:

1
static inline int list_empty(const struct list_head *head)

把链表list添加到head的后面去:

1
static inline void list_splice(const struct list_head *list, struct list_head *head)
遍历链表:算法复杂度是O(n)

f返回每次获取的结构体，fox_list是链表头, list是链表头在fox结构体里的成员名字:

1
2
3
4
5
6
list_for_each_entry(pos, head, member);
    struct fox *f;
    list_for_each_entry(f, &fox_list, list) { 
        /* on each iteration, ‘f’ points to the next fox structure ... */
        if (f->is_fantastic) return f;
}
1
2
3
list_for_each_entry_reverse(pos, head, member)；//反向遍历
list_for_each_entry_safe(pos, n, head, member)；//遍历可以删除pos，n与pos同类型

注意：当用list_for_each_entry()的安全版本遍历链表时，有可能会有其他地方并发操作删除节点，所以做删除操作时，必须锁定链表。

队列

任何操作系统内核都少不了一种编程模型：生产者和消费者。生产者产生数据，消费者处理数据。实现该模型，最简单的就是队列。生产者将数据入队列，消费者摘取数据

Linux内核通用队列实现为kfifo

创建队列

1
2
3
int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);//成功返回0
void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);//用buffer指向的内存来实现fifo

静态声明:

1
2
3
DECLARE_KFIFO(name,size);
INIT_KFIFO(name);

操作队列

入列 :

1
unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len)；

出列 :

1
unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)；

出列的数据，就不存在于fifo中了，要是只“偷窥”(偷偷一瞥)队列中数据，而不想删除它，可以用

1
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset)

其他操作

获取kfifo总体大小:

1
static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)；

获取Kfifo中已推入数据长度:

1
static inline unsigned int kfifo_len(struct kfifo *fifo)；

获取Kfifo中还有多少空间可用:

1
static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)；

判断kfifo为空或满:

1
2
3
static inline __must_check int kfifo_is_empty(struct kfifo *fifo)；
static inline __must_check int kfifo_is_full(struct kfifo *fifo)；

销毁队列:

1
void kfifo_free(struct kfifo *fifo);

重置队列:

1
static inline void kfifo_reset(struct kfifo *fifo)；//抛弃所有队列内

映射

虽然散列表是一种映射，但并非所有映射都是散列表实现的。此外，还可以用自平衡二叉搜索树存储数据。散列表提供更好的平均的渐进复杂度，但二叉搜索树在最坏的情况下能有更好的表现(对数复杂性相比线性复杂性)，散列表同时满足顺序保证。

一个映射至少实现三种操作

  • add (key, value)

  • remove(key)

  • value = lookup(key)

Linux内核提供了一个简单有效的映射数据结构，但并非是通用的映射，它的目标是：映射一个唯一的标识数(UID)到一个指针。

初始化一个idr

1
void idr_init(struct idr *idp);

举个栗子:

1
2
3
struct idr id_huh;  /* statically define idr structure */
idr_init(&id_huh);  /* initialize provided idr structure */

分配一个新的UID，分两步

调整后备树大小方法
1
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)；//成功返回1
获取新的UID，并将其添加到idr的方法
1
int idr_get_new(struct idr *idp, void *ptr, int *id)；//分配新UID关联到ptr上，UID存于id

我们来看一个完整的例子:

1
2
3
4
5
6
int id;
do {
    if (!idr_pre_get(&idr_huh, GFP_KERNEL)) 
    return -ENOSPC;
    ret = idr_get_new(&idr_huh, ptr, &id); 
} while (ret == -EAGAIN);

如果成功，上述代码将获得一个新的UID，它被存储在变量id中，并且将UID映射到ptr。

1
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)；//可以指定一个最小UID，这样除了新的UID大雨或等于starting_id外，还确保UID系统运行期间唯一

查找UID

1
void *idr_find(struct idr *idp, int id)；//调用成功返回ptr指针，失败返回NULL，所以最好不要将UID映射到空指针，这样无法区分调用成功还是失败

使用栗子:

1
2
3
struct my_struct *ptr = idr_find(&idr_huh, id); 
if (!ptr)
    return -EINVAL; /* error */

删除UID

1
void idr_remove(struct idr *idp, int id)；//id关联指针从映射中删除

撤销idr

1
2
3
void idr_destroy(struct idr *idp)；//释放idr中未使用内存，通常内核不会撤销idr，除非关闭或卸载。若需要强制删除所有UID
void idr_remove_all(struct idr *idp)；

应该先调用idr_remove_all(),然后调用idr_destroy()，这样就能是idr占用的内存都被释放。

二叉树

挖个坑，到时候总结一下红黑树

主要常用到的就是经典的红黑树了，这次终于把总结的博客写完了C++数据结构复习(三)一一红黑树%E4%B8%80%E4%B8%80%E7%BA%A2%E9%BB%91%E6%A0%91/)

数据结构的选择

  • 链表：对数据集合的主要操作是遍历数据，就用链表；当需要存储相对较少的数据项，或当你需要和内核中其他使用链表的代码交互时，首选链表。如果存储的大小不明的数据集合，链表更合适，可以动态添加任何数据类型。

  • 队列：如果代码符合生产者/消费者模式，就用队列；如果你想用一个定长缓冲，队列的添加和删除操作简单有效；

  • 映射：如果需要映射一个UID到一个对象，就用映射。Linux的映射接口是针对UID到指针的映射，并不适合其他场景。

  • 红黑树：如果需要存储大量数据，并且迅速检索，用红黑树最好；但如果没有执行太多次时间紧迫的查找操作，则红黑树不是最好选择，可以用链表；

当上述数据结构都不能满足你需要，内核还是下了一些较少使用的数据结构，比如基树和位图，只有当寻遍所有内核提供的数据结构都不能满足时，才需要自己设计数据结构。

经常在独立的源文件中实现的一种常见数据结构是散列表，因为散列表无非是一些“桶”和一个散列函数，而且这个散列函数是针对每个用例的，因此非泛型编程语言实现内核范围内的统一散列表，其实并没有什么价值。

算法复杂度

算法复杂度最常用的技术还是研究算法的渐进行为，渐进行为是指当算法的输入变大非常大或接近于无限大时算法的行为。研究算法的伸缩度(当输入增大时算法执行的变化)可以帮助我们以特定基准抽象出算法模型，从而更好理解算法行为。

大O符号

大O符号（Big O notation）是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。

大θ符号

人们讨论的大O符号，实际上更接近于Knuth教授提出的大θ符号，大θ符号更多的是指最小上限，或一个抽象出具有上限和下限的函数。

时间复杂度，常用的函数阶

下面是在分析算法的时候常见的函数分类列表:

所有这些函数都处于n趋近于无穷大的情况下，增长得慢的函数列在上面。c是一个任意常数。

显然要避免使用O(n!) or O(2n)的算法，比较算法时，还需要考虑输入规模。

我们不赞成使用复杂的算法，但是可要注意算法的负载和典型输入集合大小的关系，不要为了你根本不需要支持的伸缩度要求，盲目地去优化算法。

但 O(n3)O(n3) 真的很糟糕，O(1)O(1) 真的就很好吗？虽然在单纯的算法分析中是如此，但是在计算机系统中，算法只是一小部分。假设一个 O(1)O(1) 的算法会导致死锁，虽然看起来比 O(n3)O(n3) 的算法好得多，然而真正执行起来，可能就是无尽的等待了。

参考

《Linux内核设计与实现》

Linux内核设计与实现(7)—内核数据结构