在Linux中的list是系统通用链表,它广泛应用在系统各个地方,如系统消息队列、进程列表等地。可以说,只要有表的地方,就会用到这个list。 今天我们先解析一下跟初始化有关的代码: 1. 表头结点结构 struct list_head { struct list_head *next, *prev; }; 这和我们通常写链表一样,定义一个表头结点。 从next, prev可以看出,这是一个双向链表。 但区别是,这个结点结构中并没有内容,也就是我们常说的type data; 这也就是“通用”的体现吧。 2. #define LIST_HEAD_INIT(name) { &(name), &(name) } 定义一个LIST_HEAD初始化的宏,后面的大括号中内容我们目前似乎看不懂。 #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) 这样两个合在一起就看懂了,当执行LIST_HEAD(name)这个宏时,会创建一个头结点,并用&name初始化这个结点的两个成员指针。 3. static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } 这是一个初始化头结点函数,把next和prev指向本身。 1. 下面介绍list的插入函数: #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 这个函数的3个参数分别是: new: 要插入的结点; prev: 插入之后new的前一个结点; next: 插入之后new的后一个结点. 下面接着的是: #ifndef CONFIG_DEBUG_LIST static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } #else extern void list_add(struct list_head *new, struct list_head *head); #endif 这是将上面的3参函数改为2参函数的调用, 表示把new插入到head后面. 同理: static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } 这表示把new插入到head前面. 接下来的: static inline void __list_add_rcu(struct list_head * new, struct list_head * prev, struct list_head * next) { new->next = next; new->prev = prev; smp_wmb(); next->prev = new; prev->next = new; } 引领的是几个rcu protected的插入函数. 2. 下面介绍list的删除函数: static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } 通过要删除结点的前后两结点作为参数,使它们互相指向. static inline void list_del_init(struct list_head *entry) { __list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry); } 删除entry结点, 并把它的prev和next值指向安全区(即自己). #ifndef CONFIG_DEBUG_LIST static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } #else extern void list_del(struct list_head *entry); #endif 通过调用上面的__list_del函数实现删除结点, 并且指定entry结点prev,next指针的值. 两个宏在linux/poison.h中定义如下: /********** include/linux/list.h **********/ /* * 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) #define LIST_POISON2 ((void *) 0x00200200) 细心的人可能发现了, 结点在被从list中删除后并没有释放, 这是因为在创建和插入结点的时候也没有申请资源, 在C/C++中的原则是哪里申请哪里释放. rcu_del的函数同rcu_add, 不再说明. 3. 下面介绍list的替换函数: static inline void list_replace(struct list_head *old, struct list_head *new) { new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new; } 这个函数用new结点替换list中的old结点. static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } 这个函数把参数中的list结点的prev和next指向自己. static inline void list_replace_init(struct list_head *old, struct list_head *new) { list_replace(old, new); INIT_LIST_HEAD(old); } 这个函数是综合上面两个函数, 在用new替换old之后, 使old结点的prev和next指向安全区(即自己). 下面说一下list的move相关函数和empty相关判断函数: 1. static inline void list_move(struct list_head *list, struct list_head *head) { __list_del(list->prev, list->next); list_add(list, head); } 先解释一下参数, list是要移动的结点, head是移动的前一个位置. 即: 把list结点移动到head的后一个位置. 这是通过两步完成的: 先把list结点从链表中删除, 再把list结点插入到适当的位置. 2. static inline void list_move_tail(struct list_head *list, struct list_head *head) { __list_del(list->prev, list->next); list_add_tail(list, head); } 这是和move对应的tail函数. 即: 把list结点移动到head的前一个位置. 3. static inline int list_is_last(const struct list_head *list, const struct list_head *head) { return list->next == head; } 这个函数判断list结点是否为该链表的最后一个结点. 其中参数list是被判断结点, head是该链表的头结点. 4. static inline int list_empty(const struct list_head *head) { return head->next == head; } 这个函数判断链表是否为空, 是通过比较head和head->next的值是否相等实现的, 这与表结点的初始化方法有关. 因为初始化/重置表结点时, 把该结点的prev和next都指向本身. 参数head是表头结点. 5. static inline int list_empty_careful(const struct list_head *head) { struct list_head *next = head->next; return (next == head) && (next == head->prev); } 这个函数判断链表是否为空, 并且检查是否有进程在修改prev和next成员. 首先记录下head->next, 比较next和head是否相等, 同时比较next和prev是否相等, 要确定它们都是指向head本身才行. 这个函数只能与带有_init的函数一起使用(如__list_del_init),因为这些函数是有"重置"操作的. 下面介绍Linux通用链表(list)的splice(合并)函数: 1. static inline void __list_splice(struct list_head *list, struct list_head *head) { struct list_head *first = list->next; struct list_head *last = list->prev; struct list_head *at = head->next; first->prev = head; head->next = first; last->next = at; at->prev = last; } 这个是标准的合并函数,把list合并到另一链表的head的后一个位置. 2. static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); } } 这个函数是上面的应用版, 加了一个判断list是否为空. 3. static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); INIT_LIST_HEAD(list); } } 这是一个init版的splice应用, 加判断, 并且在合并之后对list进行重置. 介绍一下list中的关键函数container_of: /** * 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) 关于container_of见kernel.h中: /** * 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. * */ #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) container_of在Linux Kernel中的应用非常广泛,它用于获得某结构中某成员的入口地址. 关于offsetof见stddef.h中: #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) TYPE是某struct的类型 0是一个假想TYPE类型struct,MEMBER是该struct中的一个成员. 由于该struct的基地址为0, MEMBER的地址就是该成员相对与struct头地址的偏移量. 关于typeof,这是gcc的C语言扩展保留字,用于声明变量类型. const typeof( ((type *)0->member ) *__mptr = (ptr);意思是声明一个与member同一个类型的指针常量 *__mptr,并初始化为ptr. (type *)( (char *)__mptr - offsetof(type,member) );意思是__mptr的地址减去member在该struct中的偏移量得到的地址, 再转换成type型指针. 该指针就是member的入口地址了. 举例说明: 约定: 地址由高向低分配, 分配后指针指向高地址, 结构按逆序由高向低存储, 不做对齐处理. struct snow { char name; // 1 int size; // 4 time_t hold; // 16 }; struct snow *p = (struct snow)malloc(sizeof(struct snow)); 上面我们已经在堆中0x121至0x101分配了一个snow的struct, 并用p指针指向这段内存地址. 如果我们想取得p指向的结构中size变量的入口地址, 可以用container_of(p, struct snow, size); 这个调用的步骤是: 1` 取得p的指针地址, 121 2` 取得size在struct中的偏移量, 16 3` 相减获得size的入口地址, 105 通过这一个简单的例子应该能理解container_of的工作原理了, 这只是一个模仿的例子, 具体实现原理请参考ULK中的内存管理. 介绍一些list的iterate over函数: 1. #define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next) 关于这个遍历的循环似乎没什么好说的, 从head->next开始, 用next指针遍历, prefetch的是将指针推入CPU L1 cache的操作. #define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) 同上, 少了prefetch操作. #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ pos = pos->prev) 这是用prev指针遍历的带prefetch的操作. #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) 安全的iterate over函数, 参数n是用于临时存储的链表. 2. #define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) 这个函数中用到了前面解释过的著名的list_entry即container_of函数. pos是一个type结构型指针, head是list头结点, member是struct中的成员. 可以看出, 这个函数是用next指针对member成员的遍历. #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_entry((head)->prev, typeof(*pos), member); \ prefetch(pos->member.prev), &pos->member != (head); \#define list_for_each_entry_from(pos, head, member) \ for (; prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) pos = list_entry(pos->member.prev, typeof(*pos), member)) 同上, 是用prev指针对member成员的遍历. #define list_prepare_entry(pos, head, member) \ ((pos) ? : list_entry(head, typeof(*pos), member)) 获得pos指针, 用于list_for_each_entry_continuer(). 当如果pos为空时, 获得head结点的member成员入口地址. #define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) 用next指针对member成员进行从pos开始的继续遍历. #define list_for_each_entry_from(pos, head, member) \ for (; prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) 用next指针对member成员进行从当前位置开始的继续遍历. 3. safe系列和rcu系统函数类似于上面的, 不再重复. |
联系客服