【Linux内核源码分析】内核数据结构

链表链表是Linux内核中最简单、最普通的数据结构Linux内核中的实现在2.1内核开发系列中首次引入了官方内核链表实现在linux/list.h中声明structlist_head{structlist_head*next,*prev;};使用宏container_of()可以方便地从链表指针找到父结构中包含的任何变量#defineoffsetof(TYPE,MEMBER)((size_t)((TYPE*)0)-MEMBER)/** * container_of - cast a member of a structure out to the containing structure * ptr: the pointer to the member. * type: the type of the container struct this is embedded in. * member: the name of the member within the struct. * */#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)-member)*__mptr(ptr);\(type*)((char*)__mptr-offsetof(type,member));})使用container_of()宏定义一个简单的函数可返回包含list_head的父类型结构体/** * 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. */#definelist_entry(ptr,type,member)\container_of(ptr,type,member)依靠list_entry()方法内核提供了创建、操作以及其他链表管理的各种方法所有这些方法都不需要知道list_head锁嵌入对象的数据结构操作链表内核中提供了一组函数来操作链表这些函数都要使用一个list_head结构体指针做参数函数都是用C语言以内联函数实现的所有这些函数的复杂度是O(1)向链表中添加一个节点staticinlinevoidlist_add(structlist_head*new,structlist_head*head)该函数向指定链表的head节点后插入new节点从链表中删除节点staticinlinevoidlist_del(structlist_head*entry)该函数从链表中删除entry()元素该操作并不会释放entry 或释放包含entry的数据结构体所占用的内存只是仅仅将entry元素从链表中移走staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prevprev;prev-nextnext;}staticinlinevoidlist_del(structlist_head*entry){__list_del(entry-prev,entry-next);}从链表中删除一个节点并对其重新初始化staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry-prev,entry-next);INIT_LIST_HEAD(entry);}虽然链表不再需要entry项但是还可以再次使用包含entry的数据结构体移动和合并链表节点把一个节点从一个链表移到另一个链表staticinlinevoidlist_move(structlist_head*list,structlist_head*head)该函数从一个链表中移除list项然后将其加入到另一个链表的head节点后面把节点从一个链表移到另一个链表的末尾staticinlinevoidlist_move_tail(structlist_head*list,structlist_head*head)该函数和list_move()函数一样唯一不同的是将list项插入到head项前检查链表是否为空staticinlineintlist_empty(conststructlist_head*head)将两个未连接的链表合并在一起staticinlinevoidlist_splice(conststructlist_head*list,structlist_head*head)它将list指向的链表插入到指定链表的head元素后面把两个未连接的链表合并在一起并重新初始化原来的链表staticinlinevoidlist_splice_init(structlist_head*list,structlist_head*head)遍历链表基本方法使用list_for_each()宏该宏使用两个list_head类型的参数第一个参数指向当前项第二个参数是需要遍历的链表的以头节点形式存在的list_head每次遍历中第一个参数在链表中不断移动指向下一个元素直到所有元素都被访问为止#definelist_for_each(pos,head)\for(pos(head)-next;prefetch(pos-next),pos!(head);\pospos-next)可用的方法多数内核代码采用list_for_each_entry()宏来遍历链表这里的pos是一个包含list_head节点对象的指针可将它看作是list_entry宏的返回值head是一个指向头节点的指针#definelist_for_each_entry(pos,head,member)\for(poslist_entry((head)-next,typeof(*pos),member);\prefetch(pos-member.next),pos-member!(head);\poslist_entry(pos-member.next,typeof(*pos),member))内核中的例子来自inotify内核文件系统的更新通知机制在inode结构串联起来的inotify_watches链表中查找inotify_handle与所提供的句柄相匹配的inotify_watche项/* * inotify_find_handle - find the watch associated with the given inode and * handle * * Callers must hold inode-inotify_mutex. */staticstructinotify_watch*inode_find_handle(structinode*inode,structinotify_handle*ih){structinotify_watch*watch;list_for_each_entry(watch,inode-inotify_watches,i_list){if(watch-ihih)returnwatch;}returnNULL;}反向遍历链表沿着prev指针向后遍历#definelist_for_each_entry_reverse(pos,head,member)\for(poslist_entry((head)-prev,typeof(*pos),member);\prefetch(pos-member.prev),pos-member!(head);\poslist_entry(pos-member.prev,typeof(*pos),member))遍历的同时删除如果当前项在遍历循环中被删除那么接下来的遍历就无法获取next/prev指针了因此开发人员在潜在的删除操作之前保存next/prev指针到一个临时变量中以便安全删除当前项#definelist_for_each_entry_safe(pos,n,head,member)\for(poslist_entry((head)-next,typeof(*pos),member),\nlist_entry(pos-member.next,typeof(*pos),member);\pos-member!(head);\posn,nlist_entry(n-member.next,typeof(*n),member))例子/** * inotify_inode_is_dead - an inode has been deleted, cleanup any watches * inode: inode that is about to be removed */voidinotify_inode_is_dead(structinode*inode){structinotify_watch*watch,*next;mutex_lock(inode-inotify_mutex);list_for_each_entry_safe(watch,next,inode-inotify_watches,i_list){structinotify_handle*ihwatch-ih;mutex_lock(ih-mutex);inotify_remove_watch_locked(ih,watch);mutex_unlock(ih-mutex);}mutex_unlock(inode-inotify_mutex);}反向遍历链表的同时删除#definelist_for_each_entry_safe_reverse(pos,n,head,member)\for(poslist_entry((head)-prev,typeof(*pos),member),\nlist_entry(pos-member.prev,typeof(*pos),member);\pos-member!(head);\posn,nlist_entry(n-member.prev,typeof(*n),member))队列Linux内核通用队列实现称为kfifo它实现在文件kernel/kfifo.c中kfifo主要提供了两个操作enqueue和dequeue维护了两个偏移量入口偏移量和出口偏移创建队列intkfifo_alloc(structkfifo*fifo,unsignedintsize,gfp_tgfp_mask)该函数创建并初始化一个大小为size的kfifo内核使用gfp_mask标识分配队列成功返回0错误则返回一个负数错误码自己分配缓冲可以调用voidkfifo_init(structkfifo*fifo,void*buffer,unsignedintsize)该函数创建并初始化一个kfifo对象它使用buffer指向size字节大小的内存对于kfifo_allor()和kfifo_init()size()必须是2的幂静态声明kfifo更简单但不大常用DECLARE_KFIFO(name,size);INIT_KFIFO(name)推入队列数据推入队列数据需要通过kfifo_in()方法完成unsignedintkfifo_in(structkfifo*fifo,constvoid*from,unsignedintlen)该函数把from指针所指的len字节数据拷贝到fifo所指的队列中成功返回推入字节的大小如果队列中空闲字节小于len则该函数值最多可拷贝队列可用空间那么多的数据这样的话返回值可能小于len也有可能返回0摘取