内核数据结构
Linux内核中实现了一些常见的数据结构,而且内核要求代码越高效越好,所以这些数据结构的实现极为优雅!因此,千万不要自己实现山寨的数据结构。
内核的数据结构包括:
- 链表(双向循环)
- 队列
- IDR & IDA
- 红黑树
链表
链表头文件
位于include/linux/link.h
链表实现
一般我们写链表的时候,可能会这样定义:
1 | struct list_item { |
这种链表实现将数据结构塞进链表中(数据结构data被放到了链表节点list_item中)。
而linux的链表实现则是将链表节点塞进数据结构中。
链表节点的定义十分简单:
1 | struct list_head { |
我们定义一个数据结构,将链表节点插入到数据结构中:
1 | struct student { |
那么问题来了,现在的链表中内存中大概是这样的:
1 | student Tom: student Jacky: |
通过student Tom的list.next指针访问的是student Jacky所在内存的next地址。
我们知道,c的数据类型是用来告诉编译器,这个数据有多长,仅此而已。
比如通过Jacky.name访问学生Jacky的名字,编译后,是直接通过Jacky内存地址偏移x个字节进行访问的,机器可不认你的变量名。
那么问题来了,获得Jacky中的list的地址是没用的,怎么获得Jacky的地址呢,难道要我们手动使用list地址 - x字节
计算?
其实内核都为我们考虑好了,我们可以通过list_entry获得jacky的指针,list_entry定义如下:
1 | #define list_entry(ptr, type, member) \ |
获得jacky的地址:
1 | /* |
链表使用
插入节点
给定节点后插入:
1 | list_add(struct list_head *new, struct list_head *head); |
插入到尾部(将新节点插入到给定的节点前):
1 | list_add_tail(struct list_head *new, struct list_head *head); |
删除节点
从链表中删除一个节点:
1 | /* |
从链表中删除一个节点,并重新初始化:
1 | /* |
移动与合并
移动节点到另一个链表:
1 | /* |
移动节点到另一个链表的尾部:
1 | /* |
合并链表:
1 | /* |
合并链表并重新初始化原来的链表:
1 | list_splice_init(struct list_head *list, struct list_head *head); |
遍历链表
1 | list_for_each(pos, head) |
pos是临时变量,保存临时节点,head是提供到“链表头”。
直接拿到包含链表节点到数据结构指针:
1 | list_for_each_entry(pos, head, member) |
pos是包含链表结构的结构类型,list是结构中链表节点的变量名。
反向遍历:
1 | list_for_each_entry_reverse(pos, head, member) |
保存next节点(用于删除):
1 | list_for_each_entry_safe(pos, next, head, member) |
demo
简单使用一下头部插入(栈的好实现)、遍历、删除
student_list.c:
1 | #include <linux/init.h> |
Makefile:
1 | ifneq ($(KERNELRELEASE),) |
结果:
1 | [ 340.637294] student_exit enter |
更多
list_bl.h
是一种特殊的链表版本,把链表头的最低位作为锁,实现hashtable的时候很有用!list_lru.h
有点复杂了,与内存收缩有关,开发者发现收缩时总是把最久最少使用的内存给释放掉,所以抽出了公共的list_lru。不太懂,不敢乱说,也还不会使用。list_nulls.h
也是一种特殊的链表版本,链表尾不是空指针,但却可以用来表示”空s”,可以有2^31不同的值。list_sort.h
用于链表排序,传入对比用的函数指针。
队列
队列头文件
位于include/linux/kfifo.h
,内核队列使用环形缓冲区实现,并且借助了内存屏障,实现了一个reader和一个writer的情况下的无锁并发访问。
这个头里面全部都是宏定义,看的头昏。
大概就是in指向队尾,out指向队头,in%size决定元素存放在第几个位置。在多个writer、一个reader时,只需要对writer加锁;在多个reader、一个writer时,只需要对reader加锁。
队列使用
初始化队列
静态声明+初始化(很少使用):
1 | // 声明队列 size时元素个数 为2的幂 |
或者
1 | // 声明+初始化 |
动态初始化:
1 | DECLARE_KFIFO_PTR(fifo, type); |
也可以自己提供缓冲区:
1 | // buffer是预分配的内存 |
基本方法
检查kfifo是否初始化:
1 | kfifo_initialized(fifo) |
返回kfifo单个元素大小:
1 | kfifo_esize(fifo) |
返回kfifo记录长度字段的大小:
1 | kfifo_recsize(fifo) |
返回kfifo元素大小:
1 | kfifo_size(fifo) |
重置kfifo:
1 | // 将in和out置为0 |
重置out(忽略当前入队的元素):
1 | kfifo_reset_out(fifo) |
返回kfifo元素个数:
1 | kfifo_len(fifo) |
判断kfifo是否为空:
1 | kfifo_is_empty(fifo) |
判断kfifo是否为空(自旋锁):
1 | kfifo_is_empty_spinlocked(fifo, lock) |
判断kfifo是否为空(自旋锁、不禁用中断):
1 | kfifo_is_empty_spinlocked_noirqsave(fifo, lock) |
判断kfifo是否满了
1 | kfifo_is_full(fifo) |
判断kfifo还有多少可用
1 | kfifo_avail(fifo) |
跳过kfifo当前队头元素
1 | kfifo_skip(fifo) |
返回kfifo下一条记录的大小
1 | kfifo_peek_len(fifo) |
插入一个元素到kfifo中:
1 | kfifo_put(fifo, val) |
弹出一个元素:
1 | kfifo_get(fifo, val) |
查看队头元素而不弹出:
1 | kfifo_peek(fifo, val) |
插入多个元素到kfifo中:
1 | kfifo_in(fifo, buf, n) |
插入多个元素到kfifo中(自旋锁):
1 | kfifo_in_spinlocked(fifo, buf, n, lock) |
插入多个元素到kfifo中(自旋锁、不禁用中断):
1 | kfifo_in_spinlocked_noirqsave(fifo, buf, n, lock) |
弹出n个元素:
1 | kfifo_out(fifo, buf, n) |
弹出n个元素(自旋锁):
1 | kfifo_out_spinlocked(fifo, buf, n, lock) |
弹出n个元素(自旋锁、不禁用中断):
1 | kfifo_out_spinlocked(fifo, buf, n, lock) |
从用户空间入队数据:
1 | kfifo_from_user(fifo, from, len, copied) |
从队列弹出到用户空间:
1 | kfifo_to_user(fifo, to, len, copied) |
查看队头数据:
1 | kfifo_out_peek(fifo, buf, n) |
demo
见samples/kfifo,啥都有
IDR & IDA
关于IDR & IDA
IDR和IDA基于XArray数据结构,4.20以前基于Radix Tree。
IDR可以用于ID到指针的映射;而IDA是特殊的IDR,只能存放ID,没有对应值的映射。
IDR & IDA的使用
只写一点较为混淆的接口。
静态初始化(声明+静态分配):
1 | DEFINE_IDR(name) |
为下个ida_alloc调用预分配内存:
1 | idr_preload |
这个函数会设置内存分配flag,然后把抢占关闭掉,之所以这么做是因为有时要拿锁并进行ida_alloc时,内存分配可能会失败,因此提前分配。
分配id:
1 | idr_alloc |
循环分配id:
1 | idr_alloc_cyclic |
id可能大于INT_MAX时:
1 | idr_alloc_u32 |
demo
1 | #include <linux/init.h> |
1 | / # insmod student_idr.ko |
红黑树
红黑树头文件
位于include/linux/rbtree.h
红黑树的使用
一般为了最好的性能,需要自己实现节点插入和查找的函数。插入之后,因为已经有序了,所以遍历则不需要提供自己的函数,由内核提供。当然提供节点对比回调函数来插入和查找也是可以的,但是内核不推荐你这么做,因为函数调用会损耗性能。回调函数的使用见我的demo的rb_find_add。
内核红黑树使用起来和链表一样,将节点塞到结构里,而不是把结构塞到节点里。
demo
1 | #include <linux/kernel.h> |
1 | / # insmod student_rbtree.ko |
结束语
基本的数据结构就整理到这里,内核的实现真的是很漂亮,后面在工作中如果遇到需要使用这些数据结构的场景,我选择直接移植这些数据结构到用户应用!
另外截止目前,Linux版本已经到5.19了,而《Linux内核设计与实现》讲的是2.6,这中间可能新增了很多数据结构,改天再开个博客再记录。