常德建设企业网站,wordpress 安装主体,装修软件app哪个好,驻马店市可以做网站的公司lLinux内核代码中广泛使用了链表、红黑树和KFIFO。
一、 链表 linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的#xff0c;因此不需要占用连… lLinux内核代码中广泛使用了链表、红黑树和KFIFO。
一、 链表 linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的因此不需要占用连续的内存。链表通常由若干节点组成每个节点的结构都是一样的由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息而指针区用来指向链表的前继节点或者后继节点。因此链表就是利用指针将各个节点串联起来的一种存储结构。 l链表在 linux 内核中的使用无处不在可谓是基础中的基础。在很多的数据结构中都会嵌入struct list_head结构体变量它可以使结构体加入到一个双向链表中。链表的初始化增加删除等操作的接口在nclude\linux\list.h里面Kernel 中的文件、kobject、设备、驱动等等都是依赖链表连接起来的。
1.1、链表结构体定义 l链表结构体定义内容如下定义在 include\linux\types.h 中
struct list_head {struct list_head *next, *prev;
};l其成员就是两个指向list_head的指针next指向后一个链表节点、prev指向前一个链表节点。链表单独使用并没有太大意义一般都是嵌入到“宿主结构体”中。代码逻辑不关注list本身而是利用list将“宿主结构体”串联起来。链表API在源码中的路径是include\linux\list.h
1.2、初始化 在文件include\linux\list.h内
#define LIST_HEAD_INIT(name) { (name), (name) }#define LIST_HEAD(name) \struct list_head name LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list)
{list-next list;list-prev list;
}l把next和prev指针都初始化并指向自己这样便初始化了一个带头节点的空链表。
1.3、增删节点 l插入一个新节点的操作很简单就是把原有的链表从插入点断开再把新节点连接上去
/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)
{next-prev new;new-next next;new-prev prev;prev-next new;
}
#else
extern void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next);
#endif/*** list_add - add a new entry* new: new entry to be added* head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.*/
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head-next);
}
/*** list_add_tail - add a new entry* new: new entry to be added* head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head-prev, head);
}l插入前head – next l插入后head – new – next l删除节点同理也是重新更改前后节点的指针内容来实现
static inline void __list_del_entry(struct list_head *entry)
{__list_del(entry-prev, entry-next);
}static inline void list_del(struct list_head *entry)
{__list_del(entry-prev, entry-next);entry-next LIST_POISON1;entry-prev LIST_POISON2;
}l删除后节点的前后指针都被指向一个特殊的地址用于识别出这个链表指针不能使用
/** These are non-NULL pointers that will result in page faults* under normal circumstances, used to verify that nobody uses* non-initialized list entries.*/
#define LIST_POISON1 ((void *) 0x00100100 POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 POISON_POINTER_DELTA)l从增删节点的代码可以看出list内是无锁的。如果存在线程安全问题需要调用者自行加锁。
1.4、遍历链表
/*** list_for_each - iterate over a list* pos: the struct list_head to use as a loop cursor.* head: the head for your list.*/
#define list_for_each(pos, head) \for (pos (head)-next; pos ! (head); pos pos-next)/*** list_for_each_prev - iterate over a list backwards* pos: the struct list_head to use as a loop cursor.* head: the head for your list.*/
#define list_for_each_prev(pos, head) \for (pos (head)-prev; pos ! (head); pos pos-prev)/*** list_for_each_safe - iterate over a list safe against removal of list entry* pos: the struct list_head to use as a loop cursor.* n: another struct list_head to use as temporary storage* head: the head for your list.*/
#define list_for_each_safe(pos, n, head) \for (pos (head)-next, n pos-next; pos ! (head); \pos n, n pos-next)/*** list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry* pos: the struct list_head to use as a loop cursor.* n: another struct list_head to use as temporary storage* head: the head for your list.*/
#define list_for_each_prev_safe(pos, n, head) \for (pos (head)-prev, n pos-prev; \pos ! (head); \pos n, n pos-prev)/*** list_for_each_entry - iterate over list of given type* pos: the type * to use as a loop cursor.* head: the head for your list.* member: the name of the list_head within the struct.*/
#define list_for_each_entry(pos, head, member) \for (pos list_first_entry(head, typeof(*pos), member); \pos-member ! (head); \pos list_next_entry(pos, member)) llist_for_each函数是按照从前往后的顺序遍历链表通过不断指向元素的next元素直到元素的指针和链表头指针地址相同则表示链表遍历完成。 llist_for_each_prev函数则是从链表的尾部元素向前遍历。 llist_for_each_safe函数引入了指针n用于存储pos的下一个元素的地址。引入指针n可以方便在遍历链表的时候删除pos指向的元素而不影响遍历。list_for_each无法做到这一点。 llist_for_each_prev_safe函数和list_for_each_safe函数的区别是从后往前遍历。 llist_for_each_entry函数是list_for_each和list_entry的结合有posheadmember三个参数pos是一个中间变量指向当前访问的链表元素head指链表头member指pos指向的结构体中链表成员变量的名称
1.5、 查找链表元素
/*** 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_head within the struct.*/
#define list_entry(ptr, type, member) \container_of(ptr, type, member)list_entry宏有三个参数ptrtypemember。ptr是指数据结构中struct list_head变量成员的地址type是指数据结构的类型member是指数据结构中struct list_head的变量名。list_entry宏的结果是ptr指向的type类型的数据结构的变量地址。
1.6、使用示例
#include linux/kernel.h
#include linux/module.h
#include linux/init.h
#include linux/slab.h
#include linux/list.h
//实际数据结构
struct student
{ char name[100]; int num; struct list_head list;
};
//链表的头结点, (无数据)
struct list_head student_list;
static int mylist_init(void)
{ int i 0; printk( ###############################\n); INIT_LIST_HEAD(student_list); //链表头结点student_list前驱和后继都指向自身 struct student *pstudent;pstudent kmalloc(sizeof(struct student)*5,GFP_KERNEL); //申请了5个结点的内存内存地址是pstudent 而且这5个内存块是连续的。memset(pstudent,0,sizeof(struct student)*5);printk(KERN_INFO ************list_add_tail************\n);//1. 向链表添加结点for(i0;i5;i) { sprintf(pstudent[i].name,Student%d,i1); pstudent[i].num i1; list_add_tail((pstudent[i].list), student_list); //尾插法, 添加到链表的末尾//list_add_tail((pstudent[i].list), student_list); //头插法printk(0---student%d name: %s\n,pstudent[i].num,pstudent[i].name);}printk(KERN_INFO ************list_for_each************\n);//2. 从头依次遍历节点 方法一struct student *tmp_student;struct list_head *pos;list_for_each(pos,student_list) { //pos 是 每个节点中list 成员的地址tmp_student list_entry(pos,struct student,list); //根据pos获取每个节点的地址并赋值给tmp_studentprintk(1---student%d name: %s\n,tmp_student-num,tmp_student-name); }printk(KERN_INFO ************list_for_each_entry************\n);//3. 从头依次遍历节点 方法二: 方法一的简化版struct student *tmp_student2;list_for_each_entry(tmp_student2,student_list, list) { printk(2---student%d name: %s\n,tmp_student2-num,tmp_student2-name); }for(i0;i5;i) { list_del((pstudent[i].list)); } kfree(pstudent); printk( ###############################\n);return 0;
}
static void mylist_exit(void)
{
}
module_init(mylist_init);
module_exit(mylist_exit);
MODULE_LICENSE(GPL); 将代码在ubuntu的虚拟机里面测试makefile文件如下
KERNELDIR :/usr/src/linux-headers-5.4.0-149-generic
CURRENT_PATH : $(shell pwd)
#禁用签名
CONFIG_MODULE_SIGnobj-m : list.obuild: kernel_moduleskernel_modules:$(MAKE) -C $(KERNELDIR) M$(CURRENT_PATH) modulesclean:$(MAKE) -C $(KERNELDIR) M$(CURRENT_PATH) clean运行结果如下图所示
二、红黑树 红黑树Red Black Tree被广泛应用在内核的内存管理和进程调度中用于将排序的元素组织到树中。红黑树被广泛应用在计算机科学的各个领域中它在速度和实现复杂度之间提供一个很好的平衡。 红黑树是具有以下特征的二叉树。 每个节点或红或黑。 每个叶节点是黑色的。 如果结点都是红色那么两个子结点都是黑色。 从一个内部结点到叶结点的简单路径上对所有叶节点来说黑色结点的数目都是相同的。 红黑树的一个优点是所有重要的操作例如插入、删除、搜索都可以在O(log n)时间内完成n为树中元素的数目。这里只是列出一个内核中使用红黑树的例子。这个例子可以在内核代码的documentation/Rbtree.txt文件中找到。
#include linux/init.h
#include linux/list.h
#include linux/module.h
#include linux/kernel.h
#include linux/slab.h
#include linux/mm.h
#include linux/rbtree.hstruct mytype { struct rb_node node;int key;
};/*红黑树根节点*/struct rb_root mytree RB_ROOT;
/*根据key来查找节点*/
struct mytype *my_search(struct rb_root *root, int new){struct rb_node *node root-rb_node;while (node) {struct mytype *data container_of(node, struct mytype, node);if (data-key new)node node-rb_left;else if (data-key new)node node-rb_right;elsereturn data;}return NULL;}/*插入一个元素到红黑树中*/int my_insert(struct rb_root *root, struct mytype *data){struct rb_node **new (root-rb_node), *parentNULL;/* 寻找可以添加新节点的地方 */while (*new) {struct mytype *this container_of(*new, struct mytype, node);parent *new;if (this-key data-key)new ((*new)-rb_left);else if (this-key data-key) {new ((*new)-rb_right);} elsereturn -1;}/* 添加一个新节点 */rb_link_node(data-node, parent, new);rb_insert_color(data-node, root);return 0;}static int __init my_init(void)
{int i;struct mytype *data;struct rb_node *node;/*插入元素*/for (i 0; i 20; i2) {data kmalloc(sizeof(struct mytype), GFP_KERNEL);data-key i;my_insert(mytree, data);}/*遍历红黑树打印所有节点的key值*/for (node rb_first(mytree); node; node rb_next(node)) printk(key%d\n, rb_entry(node, struct mytype, node)-key);return 0;
}static void __exit my_exit(void)
{struct mytype *data;struct rb_node *node;for (node rb_first(mytree); node; node rb_next(node)) {data rb_entry(node, struct mytype, node);if (data) {rb_erase(data-node, mytree);kfree(data);}}
}
module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE(GPL);mytree是红黑树的根节点my_insert()实现插入一个元素到红黑树中my_search()根据key来查找节点。内核大量使用红黑树如虚拟地址空间VMA的管理。 关于红黑树可以参考 Linux内核中红黑树的使用方法 Linux内核中红黑树节点的插入原理分析 Linux内核中红黑树节点的删除原理分析
三、无锁环形缓冲区kfifo
3.1、kfifo介绍
3.1.1、kfifo作用 生产者和消费者模型是计算机编程中最常见的一种模型。生产者产生数据而消费者消耗数据如一个网络设备硬件设备接收网络包然后应用程序读取网络包。环形缓冲区是实现生产者和消费者模型的经典算法。环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据写指针指向环形缓冲区可写的数据。通过移动读指针和写指针实现缓冲区数据的读取和写入。FIFO主要用于缓冲速度不匹配的通信。 在Linux内核中KFIFO是采用无锁环形缓冲区的实现。FIFO的全称是“First In First Out”即先进先出的数据结构它采用环形缓冲区的方法来实现并提供一个无边界的字节流服务。采用环形缓冲区的好处是当一个数据元素被消耗之后其余数据元素不需要移动其存储位置从而减少复制提高效率。
3.1.2、kfifo原理 kfifo是linux内核的对队列功能的实现。在内核中它被称为无锁环形队列。所谓无锁就是当只有一个生产者和只有一个消费者时操作fifo不需要加锁。这是因为kfifo出队和入队时不会改动到相同的变量。 kfifo使用了in和out两个变量分别作为入队和出队的索引 入队n个数据时in变量就n 出队k个数据时out变量就k out不允许大于inout等于in时表示fifo为空 in不允许比out大超过fifo空间 如果in和out大于fifo空间了这两个索引会一直往前加不轻易回头为出入队操作省下了几个指令周期。 那入队和出队的数据从哪里开始存储/读取呢我们第一时间会想到把 in/out 用“%”对fifo大小取余就行了是吧不取余这种耗费资源的运算内核开发者怎会轻易采用呢kfifo的办法是把 in/out 与上fifo-mask。这个mask等于fifo的空间大小减一其要求fifo的空间必须是2的次方大小。这个“与”操作可比取余操作快得多了。 由此kfifo就实现了“无锁”“环形”队列。 了解了上述原理我们就能意识到这个无锁只是针对“单生产者-单消费者”而言的。“多生产者”时则需要对入队操作进行加锁同样的“多消费者”时需要对出队操作进行加锁。
3.2、linux中kfifo的实现 kfifo的源码在linux内核的include/linux/kfifo.h文件中
3.2.1、结构体 kfifo的结构体如下
struct __kfifo {unsigned int in;//入队unsigned int out;//出队unsigned int mask;//大小掩码unsigned int esize;大小void *data;队列缓存指针
};3.2.2、初始化并内存申请 在使用KFIFO之前需要进行初始化有静态初始化和动态初始化两种方式。 1、动态申请 动态初始化为kfifo_alloc在文件内include/linux/kfifo.h
/*** kfifo_alloc - dynamically allocates a new fifo buffer* fifo: pointer to the fifo* size: the number of elements in the fifo, this must be a power of 2* gfp_mask: get_free_pages mask, passed to kmalloc()** This macro dynamically allocates a new fifo buffer.** The numer of elements will be rounded-up to a power of 2.* The fifo will be release with kfifo_free().* Return 0 if no error, otherwise an error code.*/
#define kfifo_alloc(fifo, size, gfp_mask) \
__kfifo_int_must_check_helper( \
({ \typeof((fifo) 1) __tmp (fifo); \struct __kfifo *__kfifo __tmp-kfifo; \__is_kfifo_ptr(__tmp) ? \__kfifo_alloc(__kfifo, size, sizeof(*__tmp-type), gfp_mask) : \-EINVAL; \
}) \
)该函数创建并分配一个大小为size的KFIFO环形缓冲区。第一个参数fifo是指向该环形缓冲区的struct kfifo数据结构第二个参数size是指定缓冲区元素的数量第三个参数gfp_mask表示分配KFIFO元素使用的分配掩码。 其中__kfifo_alloc函数在\lib\kfifo.c文件内
int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,size_t esize, gfp_t gfp_mask)
{/** round down to the next power of 2, since our let the indices* wrap technique works only in this case.*/size roundup_pow_of_two(size);fifo-in 0;fifo-out 0;fifo-esize esize;if (size 2) {fifo-data NULL;fifo-mask 0;return -EINVAL;}fifo-data kmalloc(size * esize, gfp_mask);if (!fifo-data) {fifo-mask 0;return -ENOMEM;}fifo-mask size - 1;return 0;
}通过代码可以看到kfifo最终申请的内存空间是调用者要求空间的向上取2的次方。比如想申请7字节最终是申请8字节想申请9字节最终是申请16字节。这样才能实现用mask大小掩码“与”上in/out索引实现队列回环避免取余计算。 如果不了解这个规则则可能会踩坑。比如某个程序想申请100字节使用kfifo_alloc的动态方式或element大小为1但实际申请到的是128字节而不自知。假设这个程序每次入队和出队都是10字节当fifo存满后最后一次入队的10字节实际上只保存了8字节此后每次还是按10字节出队的话则会永远错位2字节。 2、静态申请 静态分配可以使用如下的宏。
#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)定义在include/linux/kfifo.h文件内
/*** DEFINE_KFIFO - macro to define and initialize a fifo* fifo: name of the declared fifo datatype* type: type of the fifo elements* size: the number of elements in the fifo, this must be a power of 2** Note: the macro can be used for global and local fifo data type variables.*/
#define DEFINE_KFIFO(fifo, type, size) \DECLARE_KFIFO(fifo, type, size) \(typeof(fifo)) { \{ \{ \.in 0, \.out 0, \.mask __is_kfifo_ptr((fifo)) ? \0 : \ARRAY_SIZE((fifo).buf) - 1, \.esize sizeof(*(fifo).buf), \.data __is_kfifo_ptr((fifo)) ? \NULL : \(fifo).buf, \} \} \}/*** INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO* fifo: name of the declared fifo datatype*/
#define INIT_KFIFO(fifo) \
(void)({ \typeof((fifo)) __tmp (fifo); \struct __kfifo *__kfifo __tmp-kfifo; \__kfifo-in 0; \__kfifo-out 0; \__kfifo-mask __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp-buf) - 1;\__kfifo-esize sizeof(*__tmp-buf); \__kfifo-data __is_kfifo_ptr(__tmp) ? NULL : __tmp-buf; \
})3.2.3、入队操作 把数据写入KFIFO环形缓冲区可以使用kfifo_in()函数接口。
int kfifo_in(fifo, buf, n)该函数把buf指针指向的n个数据复制到KFIFO环形缓冲区中。第一个参数fifo指的是KFIFO环形缓冲区第二个参数buf指向要复制的数据的buffer第三个数据是要复制数据元素的数量。 kfifo_in()函数定义在include/linux/kfifo.h文件内
/*** kfifo_in - put data into the fifo* fifo: address of the fifo to be used* buf: the data to be added* n: number of elements to be added** This macro copies the given buffer into the fifo and returns the* number of copied elements.** Note that with only one concurrent reader and one concurrent* writer, you dont need extra locking to use these macro.*/
#define kfifo_in(fifo, buf, n) \
({ \typeof((fifo) 1) __tmp (fifo); \typeof(__tmp-ptr_const) __buf (buf); \unsigned long __n (n); \const size_t __recsize sizeof(*__tmp-rectype); \struct __kfifo *__kfifo __tmp-kfifo; \(__recsize) ?\__kfifo_in_r(__kfifo, __buf, __n, __recsize) : \__kfifo_in(__kfifo, __buf, __n); \
})其中__kfifo_in函数定义在\lib\kfifo.c文件内
unsigned int __kfifo_in(struct __kfifo *fifo,const void *buf, unsigned int len)
{unsigned int l;l kfifo_unused(fifo);if (len l)len l;kfifo_copy_in(fifo, buf, len, fifo-in);fifo-in len;return len;
}入队共3个步骤 查询剩余空间确认最大可入队的长度 拷贝数据进内存 in索引更新 已用空间就是in-out总空间是mask1
3.2.4、出队操作 从KFIFO环形缓冲区中列出或者摘取数据可以使用kfifo_out()函数接口。
#define kfifo_out(fifo, buf, n)该函数是从fifo指向的环形缓冲区中复制n个数据元素到buf指向的缓冲区中。如果KFIFO环形缓冲区的数据元素小于n个那么复制出去的数据元素小于n个。 kfifo_out()函数定义在include/linux/kfifo.h文件内 /*** kfifo_out - get data from the fifo* fifo: address of the fifo to be used* buf: pointer to the storage buffer* n: max. number of elements to get** This macro get some data from the fifo and return the numbers of elements* copied.** Note that with only one concurrent reader and one concurrent* writer, you dont need extra locking to use these macro.*/
#define kfifo_out(fifo, buf, n) \
__kfifo_uint_must_check_helper( \
({ \typeof((fifo) 1) __tmp (fifo); \typeof(__tmp-ptr) __buf (buf); \unsigned long __n (n); \const size_t __recsize sizeof(*__tmp-rectype); \struct __kfifo *__kfifo __tmp-kfifo; \(__recsize) ?\__kfifo_out_r(__kfifo, __buf, __n, __recsize) : \__kfifo_out(__kfifo, __buf, __n); \
}) \
)出队操作和入队类似其中__kfifo_out()函数定义在\lib\kfifo.c文件内
3.3、kfifo的使用示例
#include linux/init.h
#include linux/module.h
#include linux/proc_fs.h
#include linux/mutex.h
#include linux/kfifo.h
struct kfifo Kfifo_Test;
//定义fifo最大保存的元素个数
#define DM_FIFO_ELEMENT_MAX 1024
static int mykfifo_init(void)
{char buf[100];int i 0;int ret 0;printk(KERN_INFO ###############################\n);//申请fifo内存空间一般在模块初始化时调用printk(KERN_INFO ************kfifo_alloc************\n);ret kfifo_alloc(Kfifo_Test, DM_FIFO_ELEMENT_MAX, GFP_KERNEL);if (ret) {printk(KERN_ERR kfifo_alloc fail ret%d\n, ret);return 1;}printk(KERN_INFO ************kfifo_in************\n);for ( i 0; i 10; i) {memset(buf, 0x00, 100);memset(buf, a i, i 1);kfifo_in(Kfifo_Test, buf, i 1);printk(KERN_ERR kfifo_in:%s\n, buf);}printk(KERN_INFO ************kfifo_out************\n);while (!kfifo_is_empty(Kfifo_Test)) {memset(buf, 0x00, 100);ret kfifo_out(Kfifo_Test, buf, sizeof(buf));printk(KERN_INFO kfifo_out: %s\n,buf);}printk(KERN_INFO ************kfifo_free************\n);//释放内存空间一般在模块退出时调用kfifo_free(Kfifo_Test);printk(KERN_INFO ###############################\n);
return 0;
}
static void mykfifo_exit(void)
{
}
module_init(mykfifo_init);
module_exit(mykfifo_exit);
MODULE_LICENSE(GPL); 将代码在ubuntu的虚拟机里面测试makefile文件如下
KERNELDIR :/usr/src/linux-headers-5.4.0-149-generic
CURRENT_PATH : $(shell pwd)
#禁用签名
CONFIG_MODULE_SIGnobj-m : kfifo.obuild: kernel_moduleskernel_modules:$(MAKE) -C $(KERNELDIR) M$(CURRENT_PATH) modulesclean:$(MAKE) -C $(KERNELDIR) M$(CURRENT_PATH) clean运行结果如下图所示
