内核数据结构
Linux内核实现了这些通用数据结构，而且提倡大家在开发时重用。
内核开发者应该尽可能地使用这些数据结构，而不要自作主张的山寨方法。
通用的数据结构有以下几种：链表、队列、映射和二叉树
一、链表
1.1 单向链表和双向链表
链表是Linux中最简单、最普通的数据结构。
最简单的数据结构表示一个链表：
/* 一个链表中的一个元素 */
struct list_element {
void *data; /* 有效数据 */
struct list_element *next; /* 指向下一个元素的指针 */
};
list_element
然后还有双向链表
/* 一个链表中的一个元素 */
struct list_element {
void *data; /* 有效数据 */
struct list_element *next; /* 指向下一个元素的指针 */
struct list_element *prev; /* 指向前一个元素的指针 */
};
list_element
1.2 环形链表
通常情况下，链表最后一个元素后面没有元素了，所以将链表元素中的向后指针设置为NULL，以此表明是链表中的最后一个元素。
在有些链表中，链表尾元素指向链表首元素，这种链表首位相连，被称为环形链表。
1.3 沿链表移动
只能是线性移动，先访问某个元素，然后访问下一个元素，不断重复。
如果需要随机访问，一般不使用链表。
有时，首元素会用一个特殊指针表示，该指针称为头指针。
1.4 Linux内核中的实现
linux的内核方式与众不同，它不是将数据结构塞入链表，而是将链表结点塞入数据结构。
链表的数据结构在<linux/list.h>中声明，结构很简单：
struct list_head {
struct list_head *next;
struct list_head *prev;
};
list_head
这样子我们可以用这个来实现一个链表了
struct fox {
unsigned long tail_length; /* 尾巴长度，以厘米为单位 */
unsigned long weight; /* 重量，以千克为单位 */
bool is_fantasitic /* 这只狐狸奇妙吗？ */
struct list_head list; /* 所有fox结构体形成链表 */
};
fox例子
但是list_head的头链表要找到用户自动义的结构体指针还是要费点功夫
#define container_of(ptr, type, member) ({ \
const typeof( ((type *))->member) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
list_entry
依靠list_entry()方法，内核提供了创建、操作以及其他链表管理的各种例程。所有这些方法都不需要知道list_head所嵌入对象的数据结构。
1.4.2 定义一个链表
链表需要在使用前初始化，最常见的方式是在运行时初始化链表
struct fox *red_fox;
red_fox = kmalloc(sizeof(struct fox), GFP_KERNEL);
red_fox->tail_length = ;
red_fox->weight = ;
red_fox->is_fantastic = false;
INIT_LIST_HEAD(&red_fox->list);
链表初始化
当然如果一个结构在编译期静态创建，需要在其中给出一个链表的直接引用：
struct fox red_fox = {
.tail_length = ,
.weight = ,
.list = LIST_HEAD_INIT(red_fox.list),
};
链表静态创建
1.4.3 链表头
链表需要一个标准的索引指针指向整个链表，即链表的头文件。
内核链表最杰出的特性就是：任何节点都是无差别的，索引整个链表的节点，也是一个常规的节点。
static LIST_HEAD(fox_list);
该函数定义并初始化了一个名为fox_list的链表例程。
1.5 操作链表
相关的函数都在文件<linux/list.h>中有原型，大多都是以内联函数的形式实现的。
1.5.1 向链表中增加一个节点
给链表增加一个节点，向指定链表的head节点后插入new节点
list_add(struct list_head *new, struct list_head *head);
把节点增加到链表尾，
list_add_tail(struct list_head *new, struct list_head *head);
1.5.2 从链表中删除一个节点
函数从链表中删除entry元素，该操作不会释放entry或释放包含entry的数据结构体所占用的内存。仅仅是将entry元素从链表中一走，调用后通常还需要撤销包含entry的数据结构体和其他的entry项。
list_del(struct list_head *entry)
1.5.3 移动和合并链表节点
/* 把节点从一个链表移到另一个链表
从链表中移除list项，然后将其加入到另一链表的head节点后面 */
list_move(struct list_head *list, struct list_head *head); /* 把节点从一个链表移到另一个链表的末尾
和list_move一样，不过是将list项插入到head前面 */
list_move_tail(struct list_head *list, struct list_head *head); /* 检查链表是否为空,如果链表为空返回非0，否则返回0 */
list_empty(struct list_head *head); /* 把两个未连接的链表合并在一起
将list指向的链表插入到指定链表的head元素后面 */
list_splice(struct list_head *list, struct list_head *head); /* 把两个未连接的链表合并在一起，并重新初始化原来的链表
不同于list_splice，list指向的链表要被重新初始化 */
list_splice_init(struct list_head *list, struct list_head *head);
如果碰巧已经得到了next和prev指针，可以直接调用内部链表函数，从而省下一点时间。获取指针的时间。
1.6 遍历链表
和操作链表不同，链表遍历的复杂度为O(n)，n是链表所包含的元素数目
①基本方法
遍历链表最简单的方法是使用list_for_each()宏
/* 需要使用两个list_head类型的参数，第一个指向当前项，临时变量
第二个指向参数是需要遍历的链表以头节点的形式存在的list_head
每次遍历，第一个参数在链表中不断移动，知道访问完所有元素 */
struct list_head *p;
list_for_each(p, list) {
/* p指向链表中的元素 */
}
list_for_each使用例子
不过获得指向链表结构的指针基本没用，需要使用list_entry()宏，获取数据结构的指针。
struct list_head *p;
struct fox *f;
list_for_each(p, &fox_list) {
/* f points to the struct in which the list is embedded */
f = list_entry(p, struct fox, list);
}
list_entry使用例子
②可用的方法
上面的写法不够灵活，所以多数内核采用list_for_each_entry()宏遍历链表
/* 这里pos是一个指向包含list_head节点对象的指针，可以看成list_entry的返回值
head是一个指向头节点的指针，即遍历开始位置
member是pos中list_head结构的变量名 */
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 ... */
}
list_for_each_entry使用例子
在inotify内核文件系统的更新通知机制中，有实际的例子：
static struct inotify_watch *inode_find_handle(struct inode *inode,
struct inotify_handle *ih)
{
struct inotify_watch *watch; list_for_each_entry(watch, &inode->inotify_watches, i_list) {
if(watch->ih == ih)
return watch;
}
return NULL;
}
inotify的实际使用例子
③反向遍历链表
宏list_for_each_entry_reverse()和list_for_each_entry()类似，不同的是它是反向遍历
/* 函数不再是沿着next指针遍历，而是沿着prev遍历
用法和list_for_each_entry()相同 */
list_for_each_entry_reverse(pos, head, member);
list_for_each_entry_reverse说明
反向可以组成类似堆的功能
④遍历的同时删除
标准的链表遍历是无法同时删除节点的。
lsit_for_each_entry_safe(pos, next, head, member)
inotify中也有例子：
void inotify_inode_is_dead(struct inode *inode)
{
struct inotify_watch *watch, *next; mutex_lock(&inode->inotify_mutex);
list_for_each_entry_safe(watch, next, &inode->inotify_watches, i_list) {
struct inotify_handle *ih = watch->ih;
mutex_lock(&ih->mutex);
inotify_remove_watch_locked(ih, watch); /* deletes watch */
mutex_unlock(&ih->mutex);
}
mutex_unlock(&inode->inotify_mutex);
}
inotify_inode_is_dead例子
内核还提供了反向遍历并删除，list_for_each_entry_safe_reverse()
list_for_each_entry_safe_reverse(pos, n, head, member);
剩下的就在<linux/list.h>中。。。
1.7 链表练习的例子
二、队列
实现生产者和消费者最简单的方式是使用队列。
Linux内核通用队列实现称为kfifo。在<kernel/kfifo.h>中声明，在kernel/kfifo.c中实现。使用前请仔细检查文件<linux/kfifo.h>
2.1 kfifo
linux的kfifo和多数其他队列实现类似，提供两个主要操作：
- enqueue（入队列）：拷贝数据到队列中的入口偏移位置
- dequeue（出队列）：从队列中出口偏移处拷贝数据
kfifo对象维护两个偏移量：
- 入口偏移量：下一次入队列时的位置，入口偏移等于出口偏移时队列为空，入口偏移等于队列长度是满
- 出口偏移量：下一次出队列时的位置，出口偏移总是小于等于入口偏移
2.2 创建队列
使用kfifo前，必须对它进行定义和初始化，有静态和动态分配两种，动态更普遍：
/* size:初始化kfifo的大小 */
/* gfp_mask:表示分配队列，12章详细讨论 */
/* 成功：返回0，错误：返回负数错误码 */
int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask); /* 使用例子 */
struct kfifo fifo;
int ret; ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);
if(ret)
return ret;
/* "fifo"现在代表一个大小为PAGE_SIZE的队列 */ /* 如果自己分配缓冲，可以调用 */
/* 由buffer指定size字节大小的内存，而且提到的size必须是2的幂 */
void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);
kfifo_alloc动态分配
静态分配不太常用:
/* 创建一个名称为name，大小为size的kfifo对象 */
DECLARE_KFIFO(name, size);
INIT_KFIFO(name);
kfifo静态创建
2.3 推入队列数据
当kfifo对象创建和初始化后，推入数据到队列需要通过kfifo_in()方法完成：
/* from指针所指的len字节数据拷贝到fifo所指定的队列中
成功：返回推入数据的字节大小。
如果队列中空闲字节小于len，则最多拷贝可用空间大小。
然后返回值就会小于len，甚至会返回0
unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);
kfifo_in()说明
2.4 摘取队列数据
摘取数据通过函数kfifo_out()完成。
unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);
从fifo所指的队列中拷贝出长度为len字节的数据到to所指的缓冲中。
如果只是查看数据内容，而不删除它，可以使用kfifo_out_peek()方法。
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset);
该函数出口偏移不增加，下次还能被kfifo_out获得。
2.5 获取队列长度
kfifo相关的有，获取队列空间总体大小、获取队列已推入的数据大小、获取还有多少可用空间、
判断队列空、判断队列满
/* 获取用于存储kfifo队列的空间总体大小 */
static inline unsigned int kfifo_size(struct kfifo *fifo);
/* 获取kfifo队列中已推入的数据大小 */
static inline unsigned int kfifo_len(struct kfifo *fifo);
/* 获取kfifo队列中还有多少可用空间 */
static inline unsigned int kfifo_avail(struct kfifo *fifo);
/* 判断队列是否为空 */
static inline int kfifo_is_empty(struct kfifo *fifo);
/* 判断队列是否为满 */
static inline int kfifo_is_full(struct kfifo *fifo);
获取kfifo队列长度
2.6 重置和撤销队列
如果重置，那么之前的内容会被抛弃掉。如果撤销，需要根据不同初始化情况设置。
static inline void kfifo_reset(struct kfifo *fifo); void kfifo_free(struct kfifo *fifo);
重置和撤销
2.7 队列使用举例
内核例程：
#include <linux/init.h>
#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/mutex.h>
#include <linux/kfifo.h> #define FIFO_SIZE 128 #define PROC_FIFO "record-fifo" static DEFINE_MUTEX(read_lock); static DEFINE_MUTEX(write_lock); #if 0
#define DYNAMIC
#endif #ifdef DYNAMIC
struct kfifo_rec_ptr_1 test;
#else
typedef STRUCT_KFIFO_REC_1(FIFO_SIZE) mytest; static mytest test;
#endif static const char *expected_result[] = {
"a",
"bb",
"ccc",
"dddd",
"eeeee",
"ffffff",
"ggggggg",
"hhhhhhhh",
"iiiiiiiii",
"jjjjjjjjjj",
}; static int __init testfunc(void)
{
char buf[];
unsigned int i;
unsigned int ret;
struct { unsigned char buf[]; } hello = { "hello" }; printk(KERN_INFO "record fifo test start\n"); kfifo_in(&test, &hello, sizeof(hello)); printk(KERN_INFO "fifo peek len: %u\n" ,kfifo_peek_len(&test)); for(i=;i<;i++) {
memset(buf, 'a'+i, i+);
kfifo_in(&test, buf, i+);
} printk(KERN_INFO "skip 1st element\n");
kfifo_skip(&test); printk(KERN_INFO "fifo len: %u\n", kfifo_len(&test)); ret = kfifo_out_peek(&test, buf, sizeof(buf));
if(ret)
printk(KERN_INFO "%.*s\n", ret, buf); i = ;
while(!kfifo_is_empty(&test)) {
ret = kfifo_out(&test, buf, sizeof(buf));
buf[ret] = '\0';
printk(KERN_INFO "item = %.*s\n", ret, buf);
if(strcmp(buf, expected_result[i++])) {
printk(KERN_WARNING "value mismatch: test failed\n");
return -EIO;
}
} if(i != ARRAY_SIZE(expected_result)) {
printk(KERN_WARNING "value mismatch: test failed\n");
return -EIO;
}
printk(KERN_INFO "test passed\n"); return ;
} static ssize_t fifo_write(struct file *file, const char __user *buf,
size_t count, loff_t *ppos)
{
int ret;
unsigned int copied; if(mutex_lock_interruptible(&write_lock))
return -ERESTARTSYS; ret = kfifo_from_user(&test, buf, count, &copied); mutex_unlock(&write_lock); return ret ? ret : copied;
} static ssize_t fifo_read(struct file *file, char __user *buf, size_t count,
loff_t *ppos)
{
int ret;
unsigned int copied; if(mutex_lock_interruptible(&read_lock))
return -ERESTARTSYS; ret = kfifo_to_user(&test, buf, count, &copied); mutex_unlock(&read_lock); return ret ? ret : copied;
} static const struct file_operations fifo_fops = {
.owner = THIS_MODULE,
.read = fifo_read,
.write = fifo_write,
.llseek = noop_llseek,
}; static int __init example_init(void)
{
#ifdef DYNAMIC
int ret;
ret = kfifo_alloc(&test, FIFO_SIZE, GFP_KERNEL);
if(ret) {
printk(KERN_ERR "error kfifo_alloc\n");
return ret;
}
#else
INIT_KFIFO(test);
#endif
if(testfunc() < ) {
#ifdef DYNAMIC
kfifo_free(&test);
#endif
return -EIO;
} if(proc_create(PROC_FIFO, , NULL, &fifo_fops) == NULL) {
#ifdef DYNAMIC
kfifo_free(&test);
#endif
return -ENOMEM;
}
return ;
} static void __exit example_exit(void)
{
remove_proc_entry(PROC_FIFO, NULL);
#ifdef DYNAMIC
kfifo_free(&test);
#endif
} module_init(example_init);
module_exit(example_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Stefani Seibold <stefani@seibold.net>");
内核例程
读函数：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <semaphore.h>
#include <pthread.h> #define DEVICE_NAME "/proc/record-fifo"
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0])) static const char *expected_result[] = {
"a",
"bb",
"ccc",
"dddd",
"eeeee",
"ffffff",
"ggggggg",
"hhhhhhhh",
"iiiiiiiii",
"jjjjjjjjjj",
}; int main(void)
{
int fd;
int ret;
int i;
char *buf;
fd = open(DEVICE_NAME, O_RDWR);
if(fd < ) {
printf("open kfifo err!\n");
return -;
} buf = malloc();
if(buf<)
return -; while() {
ret = read(fd, buf, );
if(ret < )
printf("read kfifo err!\n");
else if(ret == )
printf("no kfifo read!\n");
else {
printf("----kfifo read----\n");
buf[ret] = '\0';
printf("read length is %d, and the string is %s\n", ret, buf);
}
sleep();
}
return ;
}
myfifo_read.c
写函数：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <semaphore.h>
#include <pthread.h> #define DEVICE_NAME "/proc/record-fifo"
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0])) static const char *expected_result[] = {
"a",
"bb",
"ccc",
"dddd",
"eeeee",
"ffffff",
"ggggggg",
"hhhhhhhh",
"iiiiiiiii",
"jjjjjjjjjj",
}; int main(void)
{
int fd;
int ret;
int i;
fd = open(DEVICE_NAME, O_RDWR);
if(fd < ) {
printf("open kfifo err!\n");
return -;
} while() {
for(i=;i<ARRAY_SIZE(expected_result);i++) {
ret = write(fd, expected_result[i], strlen(expected_result[i]));
printf("the size of array[%d])=%d\n", i, strlen(expected_result[i]));
if(ret < )
printf("write err!\n");
sleep();
printf("-----kfifo write -----\n");
}
}
return ;
}
myfifo_write.c
Makefile：
obj-m+=myfifo.o
#testkfifo-objs:= kfifo.o kn_common.o EXEC1 = myfifo_write
EXEC2 = myfifo_read OBJS1 = myfifo_write.o
OBJS2 = myfifo_read.o CURRENT_PATH:=$(shell pwd) LINUX_KERNEL:=$(shell uname -r) LINUX_KERNEL_PATH:=/usr/src/linux-headers-$(LINUX_KERNEL) all:$(EXEC1) $(EXEC2) modules
modules:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned $(EXEC1):$(OBJS1)
gcc -o $@ $(OBJS1) $(EXEC2):$(OBJS2)
gcc -o $@ $(OBJS2) clean:
rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
rm -f $(EXEC1) $(EXEC2)
Makefile
三、映射
映射也常称为关联数组，其实是一个由唯一键组成的集合，而每个键必然关联一个特定的值。
Add(key, value);
Remove(key);
value = Lookup(key);
主要是用在分配UID，通过数据结构idr来映射用户空间的UID
3.1 初始化一个dir
建立一个idr很简单，首先动态或者静态分配一个idr数据结构。
void idr_init(struct idr *idp); /* 动态分配idr结构 */ struct idr id_huh; /* 静态定义idr结构 */
idr_init(&id_huh); /* 初始化idr结构 */
idr初始化
3.2 分配一个新的UID
一旦建立idr，就可以分配新的UID了。具体分为两步：
- 告诉idr需要分配新的UID，允许其在必要时调整后备树大小
- 真正请求新的UID。
/* 调整由idp指向的idr的大小 */
/* 成功：返回1，失败：返回0 */
int idr_pre_get(struct idr *idp, gfp_t gfp_mask); /* 执行获取新的UID，并加到idr方法 */
int idr_get_new(struct idr *idp, void *ptr, int *id);
调整后备树的大小
3.3 查找UID
在idr中分配的UID，需要查找他们。
/* 如果调用成功，返回id关联的指针 */
/* 如果错误，返回空指针 */
/* 值得注意的是如果UID映射的是空指针，哪怕成功也返回NULL */
void *idr_find(struct idr *idp, int id);
idr_find查找UID
3.4 删除UID
/* 将id关联的指针一起从映射中删除 */
void idr_remove(struct idr *idp, int id);
从idr中删除UID
3.5 撤销idr
释放idr中未使用的内存
/* 不释放当前分配给UID使用的任何内存 */
void idr_destroy(struct idr *idp);
四、二叉树
4.1 二叉搜索树
二叉搜索树（BST）是一个节点有序的二叉树，顺序通常遵循下列法则：
- 根的左分支节点都小于根节点值
- 右分支节点值都大于根节点值
- 所有的子树也都是二叉搜索树
树中搜索一个给定值或按序遍历树都相当快捷。
4.2 自平衡二叉搜索树
深度：根结点要到它节点需要经过的父结点数目
高度：树处于最底层节点的深度
自平衡二叉树：所有节点的深度差不超过1
4.2.1 红黑树
红黑树是一种自平衡二叉搜索树，主要遵循下面六个属性
- 所有节点要么着红色，要么着黑色
- 叶子节点都是黑色
- 叶子节点不包含数据
- 所有非叶子节点都有两个子节点
- 如果一个节点是红色，则它的子节点都是黑色
- 在一个节点到其叶子节点的路径中，如果总是包含同样数目的黑色节点，则该路径相比其他路径是最短的
4.2.2 rbtree
在linux中红黑树称为rbtree，在文件lib/rbtree.c中，声明在文件<linux/rbtree.h>
创建一个红黑树，需要分配一个rb_root结构，并且需要初始化为特殊值RB_ROOT：
五、数据结构以及选择
上面介绍了四种数据结构：链表、队列、映射和红黑树
- 如果对数据集合的主要操作是遍历数据，使用链表
- 如果你的代码符合生产者/消费者模式，使用队列
- 如果你需要映射一个UID到一个对象，使用映射
- 如果你需要存储大量数据，并且检索迅速，使用红黑树
六、算法复杂度
在计算机中，有必要将算法的复杂度量化地表示出来。
6.1 算法
算法就是一系列的指令，它可能有一个或多个输入，最后产生一个结果或输出。
6.2 大o符号
大O符号用来描述这种增长率