Linux内核部件分析

在linux内核中，有一种通用的双向循环链表，构成了各种队列的基础。链表的结构定义和相关函数均在include/linux/list.h中，下面就来全面的介绍这一链表的各种API。

1. struct list_head {  
   
2.     struct list_head *next, *prev;  
   
3. };  

这是链表的元素结构。因为是循环链表，表头和表中节点都是这一结构。有prev和next两个指针，分别指向链表中前一节点和后一节点。

1. #define LIST_HEAD_INIT(name) { &(name), &(name) }   
   
2.   
   
3. #define LIST_HEAD(name) \   
   
4.     struct list_head name = LIST_HEAD_INIT(name)  
   
5.   
   
6. static inline void INIT_LIST_HEAD(struct list_head *list)  
   
7. {  
   
8.     list->next = list;  
   
9.     list->prev = list;  
   
10. }  

在初始化的时候，链表头的prev和next都是指向自身的。

1. static inline void __list_add(struct list_head *new,  
   
2.                   struct list_head *prev,  
   
3.                   struct list_head *next)  
   
4. {  
   
5.     next->prev = new;  
   
6.     new->next = next;  
   
7.     new->prev = prev;  
   
8.     prev->next = new;  
   
9. }  
   
10.   
    
11. static inline void list_add(struct list_head *new, struct list_head *head)  
    
12. {  
    
13.     __list_add(new, head, head->next);  
    
14. }  
    
15.   
    
16. static inline void list_add_tail(struct list_head *new, struct list_head *head)  
    
17. {  
    
18.     __list_add(new, head->prev, head);  
    
19. }  

双向循环链表的实现，很少有例外情况，基本都可以用公共的方式来处理。这里无论是加第一个节点，还是其它的节点，使用的方法都一样。

另外，链表API实现时大致都是分为两层：一层外部的，如list_add、list_add_tail，用来消除一些例外情况，调用内部实现；一层是内部的，函数名前会加双下划线，如__list_add，往往是几个操作公共的部分，或者排除例外后的实现。

1. static inline void __list_del(struct list_head * prev, struct list_head * next)  
   
2. {  
   
3.     next->prev = prev;  
   
4.     prev->next = next;  
   
5. }  
   
6.   
   
7. static inline void list_del(struct list_head *entry)  
   
8. {  
   
9.     __list_del(entry->prev, entry->next);  
   
10.     entry->next = LIST_POISON1;  
    
11.     entry->prev = LIST_POISON2;  
    
12. }  
    
13.   
    
14. static inline void list_del_init(struct list_head *entry)  
    
15. {  
    
16.     __list_del(entry->prev, entry->next);  
    
17.     INIT_LIST_HEAD(entry);  
    
18. }  

list_del是链表中节点的删除。之所以在调用__list_del后又把被删除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2，是为了调试未定义的指针。

list_del_init则是删除节点后，随即把节点中指针再次初始化，这种删除方式更为实用。

1. static inline void list_replace(struct list_head *old,  
   
2.                 struct list_head *new)  
   
3. {  
   
4.     new->next = old->next;  
   
5.     new->next->prev = new;  
   
6.     new->prev = old->prev;  
   
7.     new->prev->next = new;  
   
8. }  
   
9.   
   
10. static inline void list_replace_init(struct list_head *old,  
    
11.                     struct list_head *new)  
    
12. {  
    
13.     list_replace(old, new);  
    
14.     INIT_LIST_HEAD(old);  
    
15. }  

list_replace是将链表中一个节点old，替换为另一个节点new。从实现来看，即使old所在地链表只有old一个节点，new也可以成功替换，这就是双向循环链表可怕的通用之处。

list_replace_init将被替换的old随即又初始化。

1. static inline void list_move(struct list_head *list, struct list_head *head)  
   
2. {  
   
3.     __list_del(list->prev, list->next);  
   
4.     list_add(list, head);  
   
5. }  
   
6.   
   
7. static inline void list_move_tail(struct list_head *list,  
   
8.                   struct list_head *head)  
   
9. {  
   
10.     __list_del(list->prev, list->next);  
    
11.     list_add_tail(list, head);  
    
12. }  

list_move的作用是把list节点从原链表中去除，并加入新的链表head中。

list_move_tail只在加入新链表时与list_move有所不同，list_move是加到head之后的链表头部，而list_move_tail是加到head之前的链表尾部。

1. static inline int list_is_last(const struct list_head *list,  
   
2.                 const struct list_head *head)  
   
3. {  
   
4.     return list->next == head;  
   
5. }  

list_is_last 判断list是否处于head链表的尾部。

1. static inline int list_empty(const struct list_head *head)  
   
2. {  
   
3.     return head->next == head;  
   
4. }  
   
5.   
   
6. static inline int list_empty_careful(const struct list_head *head)  
   
7. {  
   
8.     struct list_head *next = head->next;  
   
9.     return (next == head) && (next == head->prev);  
   
10. }  

list_empty 判断head链表是否为空，为空的意思就是只有一个链表头head。

list_empty_careful 同样是判断head链表是否为空，只是检查更为严格。

1. static inline int list_is_singular(const struct list_head *head)  
   
2. {  
   
3.     return !list_empty(head) && (head->next == head->prev);  
   
4. }  

list_is_singular 判断head中是否只有一个节点，即除链表头head外只有一个节点。

1. static inline void __list_cut_position(struct list_head *list,  
   
2.         struct list_head *head, struct list_head *entry)  
   
3. {  
   
4.     struct list_head *new_first = entry->next;  
   
5.     list->next = head->next;  
   
6.     list->next->prev = list;  
   
7.     list->prev = entry;  
   
8.     entry->next = list;  
   
9.     head->next = new_first;  
   
10.     new_first->prev = head;  
    
11. }  
    
12.   
    
13. static inline void list_cut_position(struct list_head *list,  
    
14.         struct list_head *head, struct list_head *entry)  
    
15. {  
    
16.     if (list_empty(head))  
    
17.         return;  
    
18.     if (list_is_singular(head) &&  
    
19.         (head->next != entry && head != entry))  
    
20.         return;  
    
21.     if (entry == head)  
    
22.         INIT_LIST_HEAD(list);  
    
23.     else  
    
24.         __list_cut_position(list, head, entry);  
    
25. }  

list_cut_position 用于把head链表分为两个部分。从head->next一直到entry被从head链表中删除，加入新的链表list。新链表list应该是空的，或者原来的节点都可以被忽略掉。可以看到，list_cut_position中排除了一些意外情况，保证调用__list_cut_position时至少有一个元素会被加入新链表。

1. static inline void __list_splice(const struct list_head *list,  
   
2.                  struct list_head *prev,  
   
3.                  struct list_head *next)  
   
4. {  
   
5.     struct list_head *first = list->next;  
   
6.     struct list_head *last = list->prev;  
   
7.   
   
8.     first->prev = prev;  
   
9.     prev->next = first;  
   
10.   
    
11.     last->next = next;  
    
12.     next->prev = last;  
    
13. }  
    
14.   
    
15. static inline void list_splice(const struct list_head *list,  
    
16.                 struct list_head *head)  
    
17. {  
    
18.     if (!list_empty(list))  
    
19.         __list_splice(list, head, head->next);  
    
20. }  
    
21.   
    
22. static inline void list_splice_tail(struct list_head *list,  
    
23.                 struct list_head *head)  
    
24. {  
    
25.     if (!list_empty(list))  
    
26.         __list_splice(list, head->prev, head);  
    
27. }  

list_splice的功能和list_cut_position正相反，它合并两个链表。list_splice把list链表中的节点加入head链表中。在实际操作之前，要先判断list链表是否为空。它保证调用__list_splice时list链表中至少有一个节点可以被合并到head链表中。

list_splice_tail只是在合并链表时插入的位置不同。list_splice是把原来list链表中的节点全加到head链表的头部，而list_splice_tail则是把原来list链表中的节点全加到head链表的尾部。

1. static inline void list_splice_init(struct list_head *list,  
   
2.                     struct list_head *head)  
   
3. {  
   
4.     if (!list_empty(list)) {  
   
5.         __list_splice(list, head, head->next);  
   
6.         INIT_LIST_HEAD(list);  
   
7.     }  
   
8. }  
   
9.   
   
10. static inline void list_splice_tail_init(struct list_head *list,  
    
11.                      struct list_head *head)  
    
12. {  
    
13.     if (!list_empty(list)) {  
    
14.         __list_splice(list, head->prev, head);  
    
15.         INIT_LIST_HEAD(list);  
    
16.     }  
    
17. }  

list_splice_init 除了完成list_splice的功能，还把变空了的list链表头重新初始化。

list_splice_tail_init 除了完成list_splice_tail的功能，还吧变空了得list链表头重新初始化。

list操作的API大致如以上所列，包括链表节点添加与删除、节点从一个链表转移到另一个链表、链表中一个节点被替换为另一个节点、链表的合并与拆分、查看链表当前是否为空或者只有一个节点。接下来，是操作链表遍历时的一些宏，我们也简单介绍一下。

1. #define list_entry(ptr, type, member) \   
   
2.     container_of(ptr, type, member)  

list_entry主要用于从list节点查找其内嵌在的结构。比如定义一个结构struct A{ struct list_head list; }; 如果知道结构中链表的地址ptrList，就可以从ptrList进而获取整个结构的地址(即整个结构的指针) struct A *ptrA = list_entry(ptrList, struct A, list);

这种地址翻译的技巧是linux的拿手好戏，container_of随处可见，只是链表节点多被封装在更复杂的结构中，使用专门的list_entry定义也是为了使用方便。

1. #define list_first_entry(ptr, type, member) \   
   
2.     list_entry((ptr)->next, type, member)  

list_first_entry是将ptr看完一个链表的链表头，取出其中第一个节点对应的结构地址。使用list_first_entry是应保证链表中至少有一个节点。

1. #define list_for_each(pos, head) \   
   
2.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \  
   
3.             pos = pos->next)  

list_for_each循环遍历链表中的每个节点，从链表头部的第一个节点，一直到链表尾部。中间的prefetch是为了利用平台特性加速链表遍历，在某些平台下定义为空，可以忽略。

1. #define __list_for_each(pos, head) \   
   
2.     for (pos = (head)->next; pos != (head); pos = pos->next)  

__list_for_each与list_for_each没什么不同，只是少了prefetch的内容，实现上更为简单易懂。

1. #define list_for_each_prev(pos, head) \   
   
2.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \  
   
3.             pos = pos->prev)  

list_for_each_prev与list_for_each的遍历顺序相反，从链表尾逆向遍历到链表头。

1. #define list_for_each_safe(pos, n, head) \   
   
2.     for (pos = (head)->next, n = pos->next; pos != (head); \  
   
3.         pos = n, n = pos->next)  

list_for_each_safe 也是链表顺序遍历，只是更加安全。即使在遍历过程中，当前节点从链表中删除，也不会影响链表的遍历。参数上需要加一个暂存的链表节点指针n。

1. #define list_for_each_prev_safe(pos, n, head) \   
   
2.     for (pos = (head)->prev, n = pos->prev; \  
   
3.          prefetch(pos->prev), pos != (head); \  
   
4.          pos = n, n = pos->prev)  

list_for_each_prev_safe 与list_for_each_prev同样是链表逆序遍历，只是加了链表节点删除保护。

1. #define list_for_each_entry(pos, head, member)              \   
   
2.     for (pos = list_entry((head)->next, typeof(*pos), member);   \  
   
3.          prefetch(pos->member.next), &pos->member != (head);  \  
   
4.          pos = list_entry(pos->member.next, typeof(*pos), member))  

list_for_each_entry不是遍历链表节点，而是遍历链表节点所嵌套进的结构。这个实现上较为复杂，但可以等价于list_for_each加上list_entry的组合。

1. #define list_for_each_entry_reverse(pos, head, member)          \   
   
2.     for (pos = list_entry((head)->prev, typeof(*pos), member);   \  
   
3.          prefetch(pos->member.prev), &pos->member != (head);  \  
   
4.          pos = list_entry(pos->member.prev, typeof(*pos), member))  

list_for_each_entry_reverse 是逆序遍历链表节点所嵌套进的结构，等价于list_for_each_prev加上list_etnry的组合。

1. #define list_for_each_entry_continue(pos, head, member)         \   
   
2.     for (pos = list_entry(pos->member.next, typeof(*pos), member);   \  
   
3.          prefetch(pos->member.next), &pos->member != (head);  \  
   
4.          pos = list_entry(pos->member.next, typeof(*pos), member))  

list_for_each_entry_continue也是遍历链表上的节点嵌套的结构。只是并非从链表头开始，而是从结构指针的下一个结构开始，一直到链表尾部。

1. #define list_for_each_entry_continue_reverse(pos, head, member)     \   
   
2.     for (pos = list_entry(pos->member.prev, typeof(*pos), member);   \  
   
3.          prefetch(pos->member.prev), &pos->member != (head);  \  
   
4.          pos = list_entry(pos->member.prev, typeof(*pos), member))  

list_for_each_entry_continue_reverse 是逆序遍历链表上的节点嵌套的结构。只是并非从链表尾开始，而是从结构指针的前一个结构开始，一直到链表头部。

1. #define list_for_each_entry_from(pos, head, member)             \   
   
2.     for (; prefetch(pos->member.next), &pos->member != (head);    \  
   
3.          pos = list_entry(pos->member.next, typeof(*pos), member))  

list_for_each_entry_from 是从当前结构指针pos开始，顺序遍历链表上的结构指针。

1. #define list_for_each_entry_safe(pos, n, head, member)          \   
   
2.     for (pos = list_entry((head)->next, typeof(*pos), member),   \  
   
3.         n = list_entry(pos->member.next, typeof(*pos), member);  \  
   
4.          &pos->member != (head);                     \  
   
5.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  

list_for_each_entry_safe 也是顺序遍历链表上节点嵌套的结构。只是加了删除节点的保护。

1. #define list_for_each_entry_safe_continue(pos, n, head, member)         \   
   
2.     for (pos = list_entry(pos->member.next, typeof(*pos), member),       \  
   
3.         n = list_entry(pos->member.next, typeof(*pos), member);      \  
   
4.          &pos->member != (head);                     \  
   
5.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  

list_for_each_entry_safe_continue 是从pos的下一个结构指针开始，顺序遍历链表上的结构指针，同时加了节点删除保护。

1. #define list_for_each_entry_safe_from(pos, n, head, member)             \   
   
2.     for (n = list_entry(pos->member.next, typeof(*pos), member);     \  
   
3.          &pos->member != (head);                     \  
   
4.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  

list_for_each_entry_safe_from 是从pos开始，顺序遍历链表上的结构指针，同时加了节点删除保护。 

1. #define list_for_each_entry_safe_reverse(pos, n, head, member)      \   
   
2.     for (pos = list_entry((head)->prev, typeof(*pos), member),   \  
   
3.         n = list_entry(pos->member.prev, typeof(*pos), member);  \  
   
4.          &pos->member != (head);                     \  
   
5.          pos = n, n = list_entry(n->member.prev, typeof(*n), member))  

list_for_each_entry_safe_reverse 是从pos的前一个结构指针开始，逆序遍历链表上的结构指针，同时加了节点删除保护。

至此为止，我们介绍了linux中双向循环链表的结构、所有的操作函数和遍历宏定义。相信以后在linux代码中遇到链表的使用，不会再陌生。

1. typedef struct {  


2.     volatile int counter;  


3. } atomic_t;  

原子类型其实是int类型，只是禁止寄存器对其暂存。

1. #define ATOMIC_INIT(i)  { (i) }  

原子类型的初始化。32位x86平台下atomic API在arch/x86/include/asm/atomic_32.h中实现。

1. static inline int atomic_read(const atomic_t *v)  


2. {  


3.     return v->counter;  


4. }  


5.   


6. static inline void atomic_set(atomic_t *v, int i)  


7. {  


8.     v->counter = i;  


9. }  

单独的读操作或者写操作，在x86下都是原子性的。

1. static inline void atomic_add(int i, atomic_t *v)  


2. {  


3.     asm volatile(LOCK_PREFIX “addl %1,%0”  


4.              : “+m” (v->counter)  


5.              : “ir” (i));  


6. }  


7.   


8. static inline void atomic_sub(int i, atomic_t *v)  


9. {  


10.     asm volatile(LOCK_PREFIX “subl %1,%0”  


11.              : “+m” (v->counter)  


12.              : “ir” (i));  


13. }  

atomic_add和atomic_sub属于读修改写操作，实现时需要加lock前缀。

1. static inline int atomic_sub_and_test(int i, atomic_t *v)  


2. {  


3.     unsigned char c;  


4.   


5.     asm volatile(LOCK_PREFIX “subl %2,%0; sete %1”  


6.              : “+m” (v->counter), “=qm” (c)  


7.              : “ir” (i) : “memory”);  


8.     return c;  


9. }  

atomic_sub_and_test执行完减操作后检查结果是否为0。

1. static inline void atomic_inc(atomic_t *v)  


2. {  


3.     asm volatile(LOCK_PREFIX “incl %0”  


4.              : “+m” (v->counter));  


5. }  


6.   


7. static inline void atomic_dec(atomic_t *v)  


8. {  


9.     asm volatile(LOCK_PREFIX “decl %0”  


10.              : “+m” (v->counter));  


11. }  

atomic_inc和atomic_dec是递增递减操作。

1. static inline int atomic_dec_and_test(atomic_t *v)  


2. {  


3.     unsigned char c;  


4.   


5.     asm volatile(LOCK_PREFIX “decl %0; sete %1”  


6.              : “+m” (v->counter), “=qm” (c)  


7.              : : “memory”);  


8.     return c != 0;  


9. }  

atomic_dec_and_test在递减后检查结果是否为0。

1. static inline int atomic_inc_and_test(atomic_t *v)  


2. {  


3.     unsigned char c;  


4.   


5.     asm volatile(LOCK_PREFIX “incl %0; sete %1”  


6.              : “+m” (v->counter), “=qm” (c)  


7.              : : “memory”);  


8.     return c != 0;  


9. }  

atomic_inc_and_test在递增后检查结果是否为0。

1. static inline int atomic_add_negative(int i, atomic_t *v)  


2. {  


3.     unsigned char c;  


4.   


5.     asm volatile(LOCK_PREFIX “addl %2,%0; sets %1”  


6.              : “+m” (v->counter), “=qm” (c)  


7.              : “ir” (i) : “memory”);  


8.     return c;  


9. }  

atomic_add_negative在加操作后检查结果是否为负数。

1. static inline int atomic_add_return(int i, atomic_t *v)  


2. {  


3.     int __i;  


4. #ifdef CONFIG_M386   


5.     unsigned long flags;  


6.     if (unlikely(boot_cpu_data.x86 <= 3))  


7.         goto no_xadd;  


8. #endif   


9.     /* Modern 486+ processor */  


10.     __i = i;  


11.     asm volatile(LOCK_PREFIX “xaddl %0, %1”  


12.              : “+r” (i), “+m” (v->counter)  


13.              : : “memory”);  


14.     return i + __i;  


15.   


16. #ifdef CONFIG_M386   


17. no_xadd: /* Legacy 386 processor */  


18.     local_irq_save(flags);  


19.     __i = atomic_read(v);  


20.     atomic_set(v, i + __i);  


21.     local_irq_restore(flags);  


22.     return i + __i;  


23. #endif   


24. }  

atomic_add_return 不仅执行加操作，而且把相加的结果返回。它是通过xadd这一指令实现的。

1. static inline int atomic_sub_return(int i, atomic_t *v)  


2. {  


3.     return atomic_add_return(-i, v);  


4. }  

atomic_sub_return 不仅执行减操作，而且把相减的结果返回。它是通过atomic_add_return实现的。

1. static inline int atomic_cmpxchg(atomic_t *v, int old, int new)  


2. {  


3.     return cmpxchg(&v->counter, old, new);  


4. }  


5.   


6. #define cmpxchg(ptr, o, n)                      \   


7.     ((__typeof__(*(ptr)))__cmpxchg((ptr), (unsigned long)(o),   \  


8.                        (unsigned long)(n),      \  


9.                        sizeof(*(ptr))))  


10.   


11. static inline unsigned long __cmpxchg(volatile void *ptr, unsigned long old,  


12.                       unsigned long new, int size)  


13. {  


14.     unsigned long prev;  


15.     switch (size) {  


16.     case 1:  


17.         asm volatile(LOCK_PREFIX “cmpxchgb %b1,%2”  


18.                  : “=a”(prev)  


19.                  : “q”(new), “m”(*__xg(ptr)), “0”(old)  


20.                  : “memory”);  


21.         return prev;  


22.     case 2:  


23.         asm volatile(LOCK_PREFIX “cmpxchgw %w1,%2”  


24.                  : “=a”(prev)  


25.                  : “r”(new), “m”(*__xg(ptr)), “0”(old)  


26.                  : “memory”);  


27.         return prev;  


28.     case 4:  


29.         asm volatile(LOCK_PREFIX “cmpxchgl %k1,%2”  


30.                  : “=a”(prev)  


31.                  : “r”(new), “m”(*__xg(ptr)), “0”(old)  


32.                  : “memory”);  


33.         return prev;  


34.     case 8:  


35.         asm volatile(LOCK_PREFIX “cmpxchgq %1,%2”  


36.                  : “=a”(prev)  


37.                  : “r”(new), “m”(*__xg(ptr)), “0”(old)  


38.                  : “memory”);  


39.         return prev;  


40.     }  


41.     return old;  


42. }  

atomic_cmpxchg是由cmpxchg指令完成的。它把旧值同atomic_t类型的值相比较，如果相同，就把新值存入atomic_t类型的值中，返回atomic_t类型变量中原有的值。

1. static inline int atomic_xchg(atomic_t *v, int new)  


2. {  


3.     return xchg(&v->counter, new);  


4. }  


5.   


6. #define xchg(ptr, v)                            \   


7.     ((__typeof__(*(ptr)))__xchg((unsigned long)(v), (ptr), sizeof(*(ptr))))  


8.   


9. static inline unsigned long __xchg(unsigned long x, volatile void *ptr,  


10.                    int size)  


11. {  


12.     switch (size) {  


13.     case 1:  


14.         asm volatile(“xchgb %b0,%1”  


15.                  : “=q” (x)  


16.                  : “m” (*__xg(ptr)), “0” (x)  


17.                  : “memory”);  


18.         break;  


19.     case 2:  


20.         asm volatile(“xchgw %w0,%1”  


21.                  : “=r” (x)  


22.                  : “m” (*__xg(ptr)), “0” (x)  


23.                  : “memory”);  


24.         break;  


25.     case 4:  


26.         asm volatile(“xchgl %k0,%1”  


27.                  : “=r” (x)  


28.                  : “m” (*__xg(ptr)), “0” (x)  


29.                  : “memory”);  


30.         break;  


31.     case 8:  


32.         asm volatile(“xchgq %0,%1”  


33.                  : “=r” (x)  


34.                  : “m” (*__xg(ptr)), “0” (x)  


35.                  : “memory”);  


36.         break;  


37.     }  


38.     return x;  


39. }  

atomic_xchg则是将新值存入atomic_t类型的变量，并将变量的旧值返回。它使用xchg指令实现。

1. /** 


2.  * atomic_add_unless – add unless the number is already a given value 


3.  * @v: pointer of type atomic_t 


4.  * @a: the amount to add to v… 


5.  * @u: …unless v is equal to u. 


6.  * 


7.  * Atomically adds @a to @v, so long as @v was not already @u. 


8.  * Returns non-zero if @v was not @u, and zero otherwise. 


9.  */  


10. static inline int atomic_add_unless(atomic_t *v, int a, int u)  


11. {  


12.     int c, old;  


13.     c = atomic_read(v);  


14.     for (;;) {  


15.         if (unlikely(c == (u)))  


16.             break;  


17.         old = atomic_cmpxchg((v), c, c + (a));  


18.         if (likely(old == c))  


19.             break;  


20.         c = old;  


21.     }  


22.     return c != (u);  


23. }  

atomic_add_unless的功能比较特殊。它检查v是否等于u，如果不是则把v的值加上a，返回值表示相加前v是否等于u。因为在atomic_read和atomic_cmpxchg中间可能有其它的写操作，所以要循环检查自己的值是否被写进去。

1. #define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0)   


2.   


3. #define atomic_inc_return(v)  (atomic_add_return(1, v))   


4. #define atomic_dec_return(v)  (atomic_sub_return(1, v))  

atomic_inc_not_zero在v值不是0时加1。

atomic_inc_return对v值加1，并返回相加结果。

atomic_dec_return对v值减1，并返回相减结果。

1. #define atomic_clear_mask(mask, addr)               \   


2.     asm volatile(LOCK_PREFIX “andl %0,%1”           \  


3.              : : “r” (~(mask)), “m” (*(addr)) : “memory”)  

atomic_clear_mask清除变量某些位。

1. #define atomic_set_mask(mask, addr)             \   


2.     asm volatile(LOCK_PREFIX “orl %0,%1”                \  


3.              : : “r” (mask), “m” (*(addr)) : “memory”)  

atomic_set_mask将变量的某些位置位。

1. /* Atomic operations are already serializing on x86 */  


2. #define smp_mb__before_atomic_dec() barrier()   


3. #define smp_mb__after_atomic_dec()  barrier()   


4. #define smp_mb__before_atomic_inc() barrier()   


5. #define smp_mb__after_atomic_inc()  barrier()  

因为x86的atomic操作大多使用原子指令或者带lock前缀的指令。带lock前缀的指令执行前会完成之前的读写操作，对于原子操作来说不会受之前对同一位置的读写操作，所以这里只是用空操作barrier()代替。barrier()的作用相当于告诉编译器这里有一个内存屏障，放弃在寄存器中的暂存值，重新从内存中读入。

本节的atomic_t类型操作是最基础的，为了介绍下面的内容，必须先介绍它。如果可以使用atomic_t类型代替临界区操作，也可以加快不少速度。

kref的头文件在include/linux/kref.h，实现在lib/kref.c。闲话少说，上代码。

1. struct kref {  


2.     atomic_t refcount;  


3. };  

1. void kref_set(struct kref *kref, int num)  


2. {  


3.     atomic_set(&kref->refcount, num);  


4.     smp_mb();  


5. }  

1. void kref_init(struct kref *kref)  


2. {  


3.     kref_set(kref, 1);  


4. }  

kref_init 初始化kref的计数值为1。

1. void kref_get(struct kref *kref)  


2. {  


3.     WARN_ON(!atomic_read(&kref->refcount));  


4.     atomic_inc(&kref->refcount);  


5.     smp_mb__after_atomic_inc();  


6. }  

kref_get递增kref的计数值。

1. int kref_put(struct kref *kref, void (*release)(struct kref *kref))  


2. {  


3.     WARN_ON(release == NULL);  


4.     WARN_ON(release == (void (*)(struct kref *))kfree);  


5.   


6.     if (atomic_dec_and_test(&kref->refcount)) {  


7.         release(kref);  


8.         return 1;  


9.     }  


10.     return 0;  


11. }  

kref_put递减kref的计数值，如果计数值减为0，说明kref所指向的结构生命周期结束，会执行release释放函数。

所以说kref的API很简单，kref_init和kref_set基本都是初始时才会用到，平时常用的就是kref_get和kref_put。一旦在kref_put时计数值清零，立即调用结束函数。

kref设计得如此简单，是为了能灵活地用在各种结构的生命周期管理中。要用好它可不简单，好在Documentation/kref.txt中为我们总结了一些使用规则，下面简单翻译一下。

对于那些用在多种场合，被到处传递的结构，如果没有引用计数，bug几乎总是肯定的事。所以我们需要kref。kref允许我们在已有的结构中方便地添加引用计数。

你可以以如下方式添加kref到你的数据结构中：

1. struct my_data {  


2.     …  


3.     struct kref refcount;  


4.     …  


5. };  

kref可以出现在你结构中的任意位置。

在分配kref后你必须初始化它，可以调用kref_init，把kref计数值初始为1。

1. struct my_data *data;  


2.   


3. data = kmalloc(sizeof(*data), GFP_KERNEL);  


4. if(!data)  


5.     return -ENOMEM;  


6. kref_init(&data->refcount);  

初始化之后，kref的使用应该遵循以下三条规则：

1） 如果你制造了一个结构指针的非暂时性副本，特别是当这个副本指针会被传递到其它执行线程时，你必须在传递副本指针之前执行kref_get：

1. kref_put(&data->refcount);  

2）当你使用完，不再需要结构的指针，必须执行kref_put。如果这是结构指针的最后一个引用，release函数会被调用。如果代码绝不会在没有拥有引用计数的请求下去调用kref_get，在kref_put时就不需要加锁。

1. kref_put(&data->refcount, data_release);  

3）如果代码试图在还没拥有引用计数的情况下就调用kref_get，就必须串行化kref_put和kref_get的执行。因为很可能在kref_get执行之前或者执行中，kref_put就被调用并把整个结构释放掉了。 

例如，你分配了一些数据并把它传递到其它线程去处理：

1. void data_release(struct kref *kref)  


2. {  


3.     struct my_data *data = container_of(kref, struct my_data, refcount);  


4.     kree(data);  


5. }  


6.   


7. void more_data_handling(void *cb_data)  


8. {  


9.     struct my_data *data = cb_data;  


10.     .  


11.     .  do stuff with data here  


12.     .  


13.     kref_put(&data->refcount, data_release);  


14. }  


15.   


16. int my_data_handler(void)  


17. {  


18.     int rv = 0;  


19.     struct my_data *data;  


20.     struct task_struct *task;  


21.     data = kmalloc(sizeof(*data), GFP_KERNEL);  


22.      if (!data)  


23.         return -ENOMEM;  


24.     kref_init(&data->refcount);  


25.     kref_get(&data->refcount);  


26.     task = kthread_run(more_data_handling, data, “more_data_handling”);  


27.     if (task == ERR_PTR(-ENOMEM)){  


28.          rv = -ENOMEM;  


29.          goto out;  


30.     }  


31.     .  


32.     .  do stuff with data here  


33.     .  


34. out:  


35.     kref_put(&data->refcount, data_release);  


36.     return rv;  


37. }  

这样做，无论两个线程的执行顺序是怎样的都无所谓，kref_put知道何时数据不再有引用计数，可以被销毁。kref_get()调用不需要加锁，因为在my_data_handler中调用kref_get时已经拥有一个引用。同样地原因，kref_put也不需要加锁。

要注意规则一中的要求，必须在传递指针之前调用kref_get。决不能写下面的代码：

1. task = kthread_run(more_data_handling, data, “more_data_handling”);  


2. if(task == ERR_PTR(-ENOMEM)) {  


3.     rv = -ENOMEM;  


4.     goto out;  


5. }  


6. else {  


7.      /* BAD BAD BAD – get is after the handoff */  


8.     kref_get(&data->refcount);  

不要认为自己在使用上面的代码时知道自己在做什么。首先，你可能并不知道你在做什么。其次，你可能知道你在做什么（在部分加锁情况下上面的代码也是正确的），但一些修改或者复制你代码的人并不知道你在做什么。这是一种坏的使用方式。

当然在部分情况下也可以优化对get和put的使用。例如，你已经完成了对这个数据的处理，并要把它传递给其它线程，就不需要再做多余的get和put了。

1. /* Silly extra get and put */  


2. kref_get(&obj->ref);  


3. enqueue(obj);  


4. kref_put(&obj->ref, obj_cleanup);  

只需要做enqueue操作即可，可以在其后加一条注释。

1. enqueue(obj);  


2. /* We are done with obj , so we pass our refcount off to the queue. DON’T TOUCH obj AFTER HERE! */  

第三条规则是处理起来最麻烦的。例如，你有一列数据，每条数据都有kref计数，你希望获取第一条数据。但你不能简单地把第一条数据从链表中取出并调用kref_get。这违背了第三条，在调用kref_get前你并没有一个引用。你需要增加一个mutex（或者其它锁）。

1. static DEFINE_MUTEX(mutex);  


2. static LIST_HEAD(q);  


3. struct my_data  


4. {  


5.     struct kref refcount;  


6.     struct list_head link;  


7. };  


8.   


9. static struct my_data *get_entry()  


10. {  


11.     struct my_data *entry = NULL;  


12.     mutex_lock(&mutex);  


13.     if(!list_empty(&q)){  


14.         entry = container_of(q.next, struct my_q_entry, link);  


15.         kref_get(&entry->refcount);  


16.     }  


17.     mutex_unlock(&mutex);  


18.     return entry;  


19. }  


20.           


21. static void release_entry(struct kref *ref)  


22. {  


23.     struct my_data *entry = container_of(ref, struct my_data, refcount);  


24.       


25.     list_del(&entry->link);  


26.     kfree(entry);  


27. }  


28.   


29. static void put_entry(struct my_data *entry)  


30. {  


31.     mutex_lock(&mutex);  


32.     kref_put(&entry->refcount, release_entry);  


33.     mutex_unlock(&mutex);  


34. }  

如果你不想在整个释放过程中都加锁，kref_put的返回值就有用了。例如你不想在加锁情况下调用kfree，你可以如下使用kref_put。

1. static void release_entry(struct kref *ref)  


2. {  


3.       


4. }  


5.   


6. static void put_entry(struct my_data *entry)  


7. {  


8.     mutex_lock(&mutex);  


9.     if(kref_put(&entry->refcount, release_entry)){  


10.         list_del(&entry->link);  


11.         mutex_unlock(&mutex);  


12.         kfree(entry);  


13.     }  


14.     else  


15.         mutex_unlock(&mutex);  


16. }  

如果你在撤销结构的过程中需要调用其它的需要较长时间的函数，或者函数也可能要获取同样地互斥锁，这样做就很有用了。但要注意在release函数中做完撤销工作会使代码看起来更整洁。

同hlist一样，klist也是为了适应某类特殊情形的要求。考虑一个被简化的情形，假设一些设备被链接在设备链表中，一个线程命令卸载某设备，即将其从设备链表中删除，但这时该设备正在使用中，这时就出现了冲突。当前可以设置临界区并加锁，但因为使用一个设备而锁住整个设备链表显然是不对的；又或者可以从设备本身做文章，让线程阻塞，这当然也可以。但我们上节了解了kref，就该知道linux对待这种情况的风格，给它一个引用计数kref，等计数为零就删除。klist就是这么干的，它把kref直接保存在了链表节点上。之前说到有线程要求删除设备，之前的使用仍存在，所以不能实际删除，但不应该有新的应用访问到该设备。klist就提供了一种让节点在链表上隐身的方法。下面还是来看实际代码吧。

klist的头文件是include/linux/klist.h，实现在lib/klist.c。

1. struct klist_node;  
   
2. struct klist {  
   
3.     spinlock_t      k_lock;  
   
4.     struct list_head    k_list;  
   
5.     void            (*get)(struct klist_node *);  
   
6.     void            (*put)(struct klist_node *);  
   
7. } __attribute__ ((aligned (4)));  
   
8.   
   
9. #define KLIST_INIT(_name, _get, _put)                   \   
   
10.     { .k_lock   = __SPIN_LOCK_UNLOCKED(_name.k_lock),       \  
    
11.       .k_list   = LIST_HEAD_INIT(_name.k_list),         \  
    
12.       .get      = _get,                     \  
    
13.       .put      = _put, }  
    
14.   
    
15. #define DEFINE_KLIST(_name, _get, _put)                 \   
    
16.     struct klist _name = KLIST_INIT(_name, _get, _put)  
    
17.   
    
18. extern void klist_init(struct klist *k, void (*get)(struct klist_node *),  
    
19.                void (*put)(struct klist_node *));  
    
20.   
    
21. struct klist_node {  
    
22.     void            *n_klist;   /* never access directly */  
    
23.     struct list_head    n_node;  
    
24.     struct kref     n_ref;  
    
25. };  

可以看到，klist的链表头是struct klist结构，链表节点是struct klist_node结构。先看struct klist，除了包含链表需要的k_list，还有用于加锁的k_lock。剩余的get()和put()函数是用于struct klist_node嵌入在更大的结构中，这样在节点初始时调用get()，在节点删除时调用put()，以表示链表中存在对结构的引用。再看struct klist_node，除了链表需要的n_node，还有一个引用计数n_ref。还有一个比较特殊的指针n_klist，n_klist是指向链表头struct klist的，但它的第0位用来表示是否该节点已被请求删除，如果已被请求删除则在链表循环时是看不到这一节点的，循环函数将其略过。现在你明白为什么非要在struct klist的定义后加上__attribute__((aligned(4)))。不过说实话这样在x86下仍然不太保险，但linux选择了相信gcc，毕竟是多年的战友和兄弟了，相互知根知底。

看过这两个结构，想必大家已经较为清楚了，下面就来看看它们的实现。

1. /* 
   
2.  * Use the lowest bit of n_klist to mark deleted nodes and exclude 
   
3.  * dead ones from iteration. 
   
4.  */  
   
5. #define KNODE_DEAD      1LU   
   
6. #define KNODE_KLIST_MASK    ~KNODE_DEAD   
   
7.   
   
8. static struct klist *knode_klist(struct klist_node *knode)  
   
9. {  
   
10.     return (struct klist *)  
    
11.         ((unsigned long)knode->n_klist & KNODE_KLIST_MASK);  
    
12. }  
    
13.   
    
14. static bool knode_dead(struct klist_node *knode)  
    
15. {  
    
16.     return (unsigned long)knode->n_klist & KNODE_DEAD;  
    
17. }  
    
18.   
    
19. static void knode_set_klist(struct klist_node *knode, struct klist *klist)  
    
20. {  
    
21.     knode->n_klist = klist;  
    
22.     /* no knode deserves to start its life dead */  
    
23.     WARN_ON(knode_dead(knode));  
    
24. }  
    
25.   
    
26. static void knode_kill(struct klist_node *knode)  
    
27. {  
    
28.     /* and no knode should die twice ever either, see we’re very humane */  
    
29.     WARN_ON(knode_dead(knode));  
    
30.     *(unsigned long *)&knode->n_klist |= KNODE_DEAD;  
    
31. }  

前面的四个函数都是内部静态函数，帮助API实现的。knode_klist()是从节点找到链表头。knode_dead()是检查该节点是否已被请求删除。

knode_set_klist设置节点的链表头。knode_kill将该节点请求删除。细心的话大家会发现这四个函数是对称的，而且都是操作节点的内部函数。

1. void klist_init(struct klist *k, void (*get)(struct klist_node *),  
   
2.         void (*put)(struct klist_node *))  
   
3. {  
   
4.     INIT_LIST_HEAD(&k->k_list);  
   
5.     spin_lock_init(&k->k_lock);  
   
6.     k->get = get;  
   
7.     k->put = put;  
   
8. }  

klist_init，初始化klist。

1. static void add_head(struct klist *k, struct klist_node *n)  
   
2. {  
   
3.     spin_lock(&k->k_lock);  
   
4.     list_add(&n->n_node, &k->k_list);  
   
5.     spin_unlock(&k->k_lock);  
   
6. }  
   
7.   
   
8. static void add_tail(struct klist *k, struct klist_node *n)  
   
9. {  
   
10.     spin_lock(&k->k_lock);  
    
11.     list_add_tail(&n->n_node, &k->k_list);  
    
12.     spin_unlock(&k->k_lock);  
    
13. }  
    
14.   
    
15. static void klist_node_init(struct klist *k, struct klist_node *n)  
    
16. {  
    
17.     INIT_LIST_HEAD(&n->n_node);  
    
18.     kref_init(&n->n_ref);  
    
19.     knode_set_klist(n, k);  
    
20.     if (k->get)  
    
21.         k->get(n);  
    
22. }  

又是三个内部函数，add_head()将节点加入链表头，add_tail()将节点加入链表尾，klist_node_init()是初始化节点。注意在节点的引用计数初始化时，因为引用计数变为1，所以也要调用相应的get()函数。

1. void klist_add_head(struct klist_node *n, struct klist *k)  
   
2. {  
   
3.     klist_node_init(k, n);  
   
4.     add_head(k, n);  
   
5. }  
   
6.   
   
7. void klist_add_tail(struct klist_node *n, struct klist *k)  
   
8. {  
   
9.     klist_node_init(k, n);  
   
10.     add_tail(k, n);  
    
11. }  

klist_add_head()将节点初始化，并加入链表头。

klist_add_tail()将节点初始化，并加入链表尾。

它们正是用上面的三个内部函数实现的，可见linux内核中对函数复用有很强的执念，其实这里add_tail和add_head是不用的，纵观整个文件，也只有klist_add_head()和klist_add_tail()对它们进行了调用。

1. void klist_add_after(struct klist_node *n, struct klist_node *pos)  
   
2. {  
   
3.     struct klist *k = knode_klist(pos);  
   
4.   
   
5.     klist_node_init(k, n);  
   
6.     spin_lock(&k->k_lock);  
   
7.     list_add(&n->n_node, &pos->n_node);  
   
8.     spin_unlock(&k->k_lock);  
   
9. }  
   
10.   
    
11. void klist_add_before(struct klist_node *n, struct klist_node *pos)  
    
12. {  
    
13.     struct klist *k = knode_klist(pos);  
    
14.   
    
15.     klist_node_init(k, n);  
    
16.     spin_lock(&k->k_lock);  
    
17.     list_add_tail(&n->n_node, &pos->n_node);  
    
18.     spin_unlock(&k->k_lock);  
    
19. }  

klist_add_after()将节点加到指定节点后面。

klist_add_before()将节点加到指定节点前面。

这两个函数都是对外提供的API。在list_head中都没有看到有这种API，所以说需求决定了接口。虽说只有一步之遥，klist也不愿让外界介入它的内部实现。

之前出现的API都太常见了，既没有使用引用计数，又没有跳过请求删除的节点。所以klist的亮点在下面，klist链表的遍历。

1. struct klist_iter {  
   
2.     struct klist    *i_klist;  
   
3.     struct klist_node   *i_cur;  
   
4. };  
   
5.   
   
6.   
   
7. extern void klist_iter_init(struct klist *k, struct klist_iter *i);  
   
8. extern void klist_iter_init_node(struct klist *k, struct klist_iter *i,  
   
9.                  struct klist_node *n);  
   
10. extern void klist_iter_exit(struct klist_iter *i);  
    
11. extern struct klist_node *klist_next(struct klist_iter *i);  

以上就是链表遍历需要的辅助结构struct klist_iter，和遍历用到的四个函数。

1. struct klist_waiter {  
   
2.     struct list_head list;  
   
3.     struct klist_node *node;  
   
4.     struct task_struct *process;  
   
5.     int woken;  
   
6. };  
   
7.   
   
8. static DEFINE_SPINLOCK(klist_remove_lock);  
   
9. static LIST_HEAD(klist_remove_waiters);  
   
10.   
    
11. static void klist_release(struct kref *kref)  
    
12. {  
    
13.     struct klist_waiter *waiter, *tmp;  
    
14.     struct klist_node *n = container_of(kref, struct klist_node, n_ref);  
    
15.   
    
16.     WARN_ON(!knode_dead(n));  
    
17.     list_del(&n->n_node);  
    
18.     spin_lock(&klist_remove_lock);  
    
19.     list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {  
    
20.         if (waiter->node != n)  
    
21.             continue;  
    
22.   
    
23.         waiter->woken = 1;  
    
24.         mb();  
    
25.         wake_up_process(waiter->process);  
    
26.         list_del(&waiter->list);  
    
27.     }  
    
28.     spin_unlock(&klist_remove_lock);  
    
29.     knode_set_klist(n, NULL);  
    
30. }  
    
31.   
    
32. static int klist_dec_and_del(struct klist_node *n)  
    
33. {  
    
34.     return kref_put(&n->n_ref, klist_release);  
    
35. }  
    
36.   
    
37. static void klist_put(struct klist_node *n, bool kill)  
    
38. {  
    
39.     struct klist *k = knode_klist(n);  
    
40.     void (*put)(struct klist_node *) = k->put;  
    
41.   
    
42.     spin_lock(&k->k_lock);  
    
43.     if (kill)  
    
44.         knode_kill(n);  
    
45.     if (!klist_dec_and_del(n))  
    
46.         put = NULL;  
    
47.     spin_unlock(&k->k_lock);  
    
48.     if (put)  
    
49.         put(n);  
    
50. }  
    
51.   
    
52. /** 
    
53.  * klist_del – Decrement the reference count of node and try to remove. 
    
54.  * @n: node we’re deleting. 
    
55.  */  
    
56. void klist_del(struct klist_node *n)  
    
57. {  
    
58.     klist_put(n, true);  
    
59. }  

以上的内容乍一看很难理解，其实都是klist实现必须的。因为使用kref动态删除，自然需要一个计数降为零时调用的函数klist_release。

klist_dec_and_del()就是对kref_put()的包装，起到减少节点引用计数的功能。

至于为什么会出现一个新的结构struct klist_waiter，也很简单。之前说有线程申请删除某节点，但节点的引用计数仍在，所以只能把请求删除的线程阻塞，就是用struct klist_waiter阻塞在klist_remove_waiters上。所以在klist_release()调用时还要将阻塞的线程唤醒。knode_kill()将节点设为已请求删除。而且还会调用put()函数。

释放引用计数是调用klist_del()，它通过内部函数klist_put()完成所需操作：用knode_kill()设置节点为已请求删除，用klist_dec_and_del()释放引用，调用可能的put()函数。

1. /** 
   
2.  * klist_remove – Decrement the refcount of node and wait for it to go away. 
   
3.  * @n: node we’re removing. 
   
4.  */  
   
5. void klist_remove(struct klist_node *n)  
   
6. {  
   
7.     struct klist_waiter waiter;  
   
8.   
   
9.     waiter.node = n;  
   
10.     waiter.process = current;  
    
11.     waiter.woken = 0;  
    
12.     spin_lock(&klist_remove_lock);  
    
13.     list_add(&waiter.list, &klist_remove_waiters);  
    
14.     spin_unlock(&klist_remove_lock);  
    
15.   
    
16.     klist_del(n);  
    
17.   
    
18.     for (;;) {  
    
19.         set_current_state(TASK_UNINTERRUPTIBLE);  
    
20.         if (waiter.woken)  
    
21.             break;  
    
22.         schedule();  
    
23.     }  
    
24.     __set_current_state(TASK_RUNNING);  
    
25. }  

klist_remove()不但会调用klist_del()减少引用计数，还会一直阻塞到节点被删除。这个函数才是请求删除节点的线程应该调用的。

1. int klist_node_attached(struct klist_node *n)  
   
2. {  
   
3.     return (n->n_klist != NULL);  
   
4. }  

klist_node_attached()检查节点是否被包含在某链表中。

以上是klist的链表初始化，节点加入，节点删除函数。下面是klist链表遍历函数。

1. struct klist_iter {  
   
2.     struct klist        *i_klist;  
   
3.     struct klist_node   *i_cur;  
   
4. };  
   
5.   
   
6.   
   
7. extern void klist_iter_init(struct klist *k, struct klist_iter *i);  
   
8. extern void klist_iter_init_node(struct klist *k, struct klist_iter *i,  
   
9.                  struct klist_node *n);  
   
10. extern void klist_iter_exit(struct klist_iter *i);  
    
11. extern struct klist_node *klist_next(struct klist_iter *i);  

klist的遍历有些复杂，因为它考虑到了在遍历过程中节点删除的情况，而且还要忽略那些已被删除的节点。宏实现已经无法满足要求，迫不得已，只能用函数实现，并用struct klist_iter记录中间状态。

1. void klist_iter_init_node(struct klist *k, struct klist_iter *i,  
   
2.               struct klist_node *n)  
   
3. {  
   
4.     i->i_klist = k;  
   
5.     i->i_cur = n;  
   
6.     if (n)  
   
7.         kref_get(&n->n_ref);  
   
8. }  
   
9.   
   
10. void klist_iter_init(struct klist *k, struct klist_iter *i)  
    
11. {  
    
12.     klist_iter_init_node(k, i, NULL);  
    
13. }  

klist_iter_init_node()是从klist中的某个节点开始遍历，而klist_iter_init()是从链表头开始遍历的。

但你又要注意，klist_iter_init()和klist_iter_init_node()的用法又不同。klist_iter_init_node()可以在其后直接对当前节点进行访问，也可以调用klist_next()访问下一节点。而klist_iter_init()只能调用klist_next()访问下一节点。或许klist_iter_init_node()的本意不是从当前节点开始，而是从当前节点的下一节点开始。

1. static struct klist_node *to_klist_node(struct list_head *n)  
   
2. {  
   
3.     return container_of(n, struct klist_node, n_node);  
   
4. }  

1. struct klist_node *klist_next(struct klist_iter *i)  
   
2. {  
   
3.     void (*put)(struct klist_node *) = i->i_klist->put;  
   
4.     struct klist_node *last = i->i_cur;  
   
5.     struct klist_node *next;  
   
6.   
   
7.     spin_lock(&i->i_klist->k_lock);  
   
8.   
   
9.     if (last) {  
   
10.         next = to_klist_node(last->n_node.next);  
    
11.         if (!klist_dec_and_del(last))  
    
12.             put = NULL;  
    
13.     } else  
    
14.         next = to_klist_node(i->i_klist->k_list.next);  
    
15.   
    
16.     i->i_cur = NULL;  
    
17.     while (next != to_klist_node(&i->i_klist->k_list)) {  
    
18.         if (likely(!knode_dead(next))) {  
    
19.             kref_get(&next->n_ref);  
    
20.             i->i_cur = next;  
    
21.             break;  
    
22.         }  
    
23.         next = to_klist_node(next->n_node.next);  
    
24.     }  
    
25.   
    
26.     spin_unlock(&i->i_klist->k_lock);  
    
27.   
    
28.     if (put && last)  
    
29.         put(last);  
    
30.     return i->i_cur;  
    
31. }  

klist_next()是将循环进行到下一节点。实现中需要注意两点问题：1、加锁，根据经验，单纯对某个节点操作不需要加锁，但对影响整个链表的操作需要加自旋锁。比如之前klist_iter_init_node()中对节点增加引用计数，就不需要加锁，因为只有已经拥有节点引用计数的线程才会特别地从那个节点开始。而之后klist_next()中则需要加锁，因为当前线程很可能没有引用计数，所以需要加锁，让情况固定下来。这既是保护链表，也是保护节点有效。符合kref引用计数的使用原则。2、要注意，虽然在节点切换的过程中是加锁的，但切换完访问当前节点时是解锁的，中间可能有节点被删除（这个通过spin_lock就可以搞定），也可能有节点被请求删除，这就需要注意。首先要忽略链表中已被请求删除的节点，然后在减少前一个节点引用计数时，可能就把前一个节点删除了。这里之所以不调用klist_put()，是因为本身已处于加锁状态，但仍要有它的实现。这里的实现和klist_put()中类似，代码不介意在加锁状态下唤醒另一个线程，但却不希望在加锁状态下调用put()函数，那可能会涉及释放另一个更大的结构。

1. void klist_iter_exit(struct klist_iter *i)  
   
2. {  
   
3.     if (i->i_cur) {  
   
4.         klist_put(i->i_cur, false);  
   
5.         i->i_cur = NULL;  
   
6.     }  
   
7. }  

klist_iter_exit()，遍历结束函数。在遍历完成时调不调无所谓，但如果想中途结束，就一定要调用klist_iter_exit()。

klist主要用于设备驱动模型中，为了适应那些动态变化的设备和驱动，而专门设计的链表。klist并不通用，但它真的很新奇。 我看到它时，震惊于链表竟然可以专门异化成这种样子。如果你是松耦合的结构，如果你手下净是些桀骜不驯的家伙，那么不要只考虑kref，你可能还需要klist。

    kobject的头文件在include/linux/kobject.h，实现在lib/kobject.c。闲话少说，上代码。

1. struct kobject {  


2.     const char      *name;  


3.     struct list_head    entry;  


4.     struct kobject      *parent;  


5.     struct kset     *kset;  


6.     struct kobj_type    *ktype;  


7.     struct sysfs_dirent *sd;  


8.     struct kref     kref;  


9.     unsigned int state_initialized:1;  


10.     unsigned int state_in_sysfs:1;  


11.     unsigned int state_add_uevent_sent:1;  


12.     unsigned int state_remove_uevent_sent:1;  


13.     unsigned int uevent_suppress:1;  


14. };  

在struct kobject中，name是名字，entry是用于kobject所属kset下的子kobject链表，parent指向kobject的父节点，kset指向kobject所属的kset，ktype定义了kobject所属的类型，sd指向kobject对应的sysfs目录，kref记录kobject的引用计数，之后是一系列标志。

1. struct kobj_type {  


2.     void (*release)(struct kobject *kobj);  


3.     struct sysfs_ops *sysfs_ops;  


4.     struct attribute **default_attrs;  


5. };  

struct kobj_type就是定义了kobject的公共类型，其中既有操作的函数，也有公共的属性。其中release()是在kobject释放时调用的，sysfs_ops中定义了读写属性文件时调用的函数。default_attrs中定义了这类kobject公共的属性。

1. struct kset {  


2.     struct list_head list;  


3.     spinlock_t list_lock;  


4.     struct kobject kobj;  


5.     struct kset_uevent_ops *uevent_ops;  


6. };  

struct kset可以看成在kobject上的扩展，它包含一个kobject的链表，可以方便地表示sysfs中目录与子目录的关系。其中，list是所属kobject的链表头，list_lock用于在访问链表时加锁，kobj是kset的内部kobject，要表现为sysfs中的目录就必须拥有kobject的功能，最后的kset_uevent_ops定义了对发往用户空间的uevent的处理。我对uevent不了解，会尽量忽略。

1. struct kobj_attribute {  


2.     struct attribute attr;  


3.     ssize_t (*show)(struct kobject *kobj, struct kobj_attribute *attr,  


4.             char *buf);  


5.     ssize_t (*store)(struct kobject *kobj, struct kobj_attribute *attr,  


6.              const char *buf, size_t count);  


7. };  

struct kobj_attribute是kobject在attribute上做出的扩展，添加了两个专门读写kobject属性的函数。无论是kobject，还是kset（说到底是kset内部的kobject），都提供了使用kobj_attribute的快速创建方法。

结构差不多介绍完了，下面看看实现。我所知道的代码分析风格，喜欢自顶向下的方式，从一个函数开始，介绍出一个函数调用树。在代码量很大，涉及调用层次很深的时候，确实要采用这种打洞的方式来寻找突破口。但这种自顶向下的方式有两个问题：一是很容易迷失，二是代码分析的难度会逐渐增大而不是减小。在茫茫的代码中，你一头下去，周围都是你不认识的函数，一个函数里调用了三个陌生的函数，其中一个陌生的函数又调用了五个更陌生的函数…不久你就会产生很强的挫败感。这就像走在沙漠上，你不知道终点在哪，也许翻过一个沙丘就到了，也许还有无数个沙丘。而且在这种分析时，人是逐渐走向细节，容易被细节所困扰，忽略了整体的印象与代码的层次感。所以，我觉得在分析代码时，也可以采用自底向上的方式，从细小的、内部使用的函数，到比较宏观的、供外部调用的函数。而且按照这种顺序来看代码，基本就是文件从头读到尾的顺序，也比较符合写代码的流程。linux代码喜欢在文件开始处攒内部静态函数，攒到一定程度爆发，突然实现几个外部API，然后再攒，再实现。而且之前的内部静态函数会反复调用到。linux代码写得很有层次感，除了内外有别，还把意思相近的，或者功能刚好相反的，或者使用时顺序调用的函数放在一起，很便于阅读。闲话少说，等你看完kobject的实现自然就清楚了。

1. static int populate_dir(struct kobject *kobj)  


2. {  


3.     struct kobj_type *t = get_ktype(kobj);  


4.     struct attribute *attr;  


5.     int error = 0;  


6.     int i;  


7.   


8.     if (t && t->default_attrs) {  


9.         for (i = 0; (attr = t->default_attrs[i]) != NULL; i++) {  


10.             error = sysfs_create_file(kobj, attr);  


11.             if (error)  


12.                 break;  


13.         }  


14.     }  


15.     return error;  


16. }  


17.   


18. static int create_dir(struct kobject *kobj)  


19. {  


20.     int error = 0;  


21.     if (kobject_name(kobj)) {  


22.         error = sysfs_create_dir(kobj);  


23.         if (!error) {  


24.             error = populate_dir(kobj);  


25.             if (error)  


26.                 sysfs_remove_dir(kobj);  


27.         }  


28.     }  


29.     return error;  


30. }  

create_dir()在sysfs中创建kobj对应的目录，populate_dir()创建kobj中默认属性对应的文件。create_dir()正是调用populate_dir()实现的。

1. static int get_kobj_path_length(struct kobject *kobj)  


2. {  


3.     int length = 1;  


4.     struct kobject *parent = kobj;  


5.   


6.     /* walk up the ancestors until we hit the one pointing to the 


7.      * root. 


8.      * Add 1 to strlen for leading ‘/’ of each level. 


9.      */  


10.     do {  


11.         if (kobject_name(parent) == NULL)  


12.             return 0;  


13.         length += strlen(kobject_name(parent)) + 1;  


14.         parent = parent->parent;  


15.     } while (parent);  


16.     return length;  


17. }  


18.   


19. static void fill_kobj_path(struct kobject *kobj, char *path, int length)  


20. {  


21.     struct kobject *parent;  


22.   


23.     –length;  


24.     for (parent = kobj; parent; parent = parent->parent) {  


25.         int cur = strlen(kobject_name(parent));  


26.         /* back up enough to print this name with ‘/’ */  


27.         length -= cur;  


28.         strncpy(path + length, kobject_name(parent), cur);  


29.         *(path + –length) = ‘/’;  


30.     }  


31.   


32.     pr_debug(“kobject: ‘%s’ (%p): %s: path = ‘%s’\n”, kobject_name(kobj),  


33.          kobj, __func__, path);  


34. }  


35.   


36. /** 


37.  * kobject_get_path – generate and return the path associated with a given kobj and kset pair. 


38.  * 


39.  * @kobj:   kobject in question, with which to build the path 


40.  * @gfp_mask:   the allocation type used to allocate the path 


41.  * 


42.  * The result must be freed by the caller with kfree(). 


43.  */  


44. char *kobject_get_path(struct kobject *kobj, gfp_t gfp_mask)  


45. {  


46.     char *path;  


47.     int len;  


48.   


49.     len = get_kobj_path_length(kobj);  


50.     if (len == 0)  


51.         return NULL;  


52.     path = kzalloc(len, gfp_mask);  


53.     if (!path)  


54.         return NULL;  


55.     fill_kobj_path(kobj, path, len);  


56.   


57.     return path;  


58. }  

前面两个是内部函数，get_kobj_path_length()获得kobj路径名的长度，fill_kobj_path()把kobj路径名填充到path缓冲区中。

kobject_get_path()靠两个函数获得kobj的路径名，从攒函数到爆发一气呵成。

1. static void kobj_kset_join(struct kobject *kobj)  


2. {  


3.     if (!kobj->kset)  


4.         return;  


5.   


6.     kset_get(kobj->kset);  


7.     spin_lock(&kobj->kset->list_lock);  


8.     list_add_tail(&kobj->entry, &kobj->kset->list);  


9.     spin_unlock(&kobj->kset->list_lock);  


10. }  


11.   


12. /* remove the kobject from its kset’s list */  


13. static void kobj_kset_leave(struct kobject *kobj)  


14. {  


15.     if (!kobj->kset)  


16.         return;  


17.   


18.     spin_lock(&kobj->kset->list_lock);  


19.     list_del_init(&kobj->entry);  


20.     spin_unlock(&kobj->kset->list_lock);  


21.     kset_put(kobj->kset);  


22. }  

kobj_kset_join()把kobj加入kobj->kset的链表中，kobj_kset_leave()把kobj从kobj->kset的链表中去除，两者功能相对。

1. static void kobject_init_internal(struct kobject *kobj)  


2. {  


3.     if (!kobj)  


4.         return;  


5.     kref_init(&kobj->kref);  


6.     INIT_LIST_HEAD(&kobj->entry);  


7.     kobj->state_in_sysfs = 0;  


8.     kobj->state_add_uevent_sent = 0;  


9.     kobj->state_remove_uevent_sent = 0;  


10.     kobj->state_initialized = 1;  


11. }  


12.   


13.   


14. static int kobject_add_internal(struct kobject *kobj)  


15. {  


16.     int error = 0;  


17.     struct kobject *parent;  


18.   


19.     if (!kobj)  


20.         return -ENOENT;  


21.   


22.     if (!kobj->name || !kobj->name[0]) {  


23.         WARN(1, “kobject: (%p): attempted to be registered with empty “  


24.              “name!\n”, kobj);  


25.         return -EINVAL;  


26.     }  


27.   


28.     parent = kobject_get(kobj->parent);  


29.   


30.     /* join kset if set, use it as parent if we do not already have one */  


31.     if (kobj->kset) {  


32.         if (!parent)  


33.             parent = kobject_get(&kobj->kset->kobj);  


34.         kobj_kset_join(kobj);  


35.         kobj->parent = parent;  


36.     }  


37.   


38.     pr_debug(“kobject: ‘%s’ (%p): %s: parent: ‘%s’, set: ‘%s’\n”,  


39.          kobject_name(kobj), kobj, __func__,  


40.          parent ? kobject_name(parent) : “<NULL>”,  


41.          kobj->kset ? kobject_name(&kobj->kset->kobj) : “<NULL>”);  


42.   


43.     error = create_dir(kobj);  


44.     if (error) {  


45.         kobj_kset_leave(kobj);  


46.         kobject_put(parent);  


47.         kobj->parent = NULL;  


48.   


49.         /* be noisy on error issues */  


50.         if (error == -EEXIST)  


51.             printk(KERN_ERR “%s failed for %s with “  


52.                    “-EEXIST, don’t try to register things with “  


53.                    “the same name in the same directory.\n”,  


54.                    __func__, kobject_name(kobj));  


55.         else  


56.             printk(KERN_ERR “%s failed for %s (%d)\n”,  


57.                    __func__, kobject_name(kobj), error);  


58.         dump_stack();  


59.     } else  


60.         kobj->state_in_sysfs = 1;  


61.   


62.     return error;  


63. }  

kobject_init_internal()初始化kobj。

kobject_add_internal()把kobj加入已有的结构。

这两个函数看似无关，实际很有关系。在kobject中有好几个结构变量，但重要的只有两个，一个是kset，一个是parent。这两个都是表示当前kobject在整个体系中的位置，决不能自行决定，需要外部参与设置。那把kobject创建的过程分为init和add两个阶段也就很好理解了。kobject_init_internal()把一些能自动初始化的结构变量初始化掉，等外界设置了parent和kset，再调用kobject_add_internal()把kobject安在适当的位置，并创建相应的sysfs目录及文件。

1. int kobject_set_name_vargs(struct kobject *kobj, const char *fmt,  


2.                   va_list vargs)  


3. {  


4.     const char *old_name = kobj->name;  


5.     char *s;  


6.   


7.     if (kobj->name && !fmt)  


8.         return 0;  


9.   


10.     kobj->name = kvasprintf(GFP_KERNEL, fmt, vargs);  


11.     if (!kobj->name)  


12.         return -ENOMEM;  


13.   


14.     /* ewww… some of these buggers have ‘/’ in the name … */  


15.     while ((s = strchr(kobj->name, ‘/’)))  


16.         s[0] = ‘!’;  


17.   


18.     kfree(old_name);  


19.     return 0;  


20. }  


21.   


22. /** 


23.  * kobject_set_name – Set the name of a kobject 


24.  * @kobj: struct kobject to set the name of 


25.  * @fmt: format string used to build the name 


26.  * 


27.  * This sets the name of the kobject.  If you have already added the 


28.  * kobject to the system, you must call kobject_rename() in order to 


29.  * change the name of the kobject. 


30.  */  


31. int kobject_set_name(struct kobject *kobj, const char *fmt, …)  


32. {  


33.     va_list vargs;  


34.     int retval;  


35.   


36.     va_start(vargs, fmt);  


37.     retval = kobject_set_name_vargs(kobj, fmt, vargs);  


38.     va_end(vargs);  


39.   


40.     return retval;  


41. }  

kobject_set_name()是设置kobj名称的，它又调用kobject_set_name_vargs()实现。但要注意，这个kobject_set_name()仅限于kobject添加到体系之前，因为它只是修改了名字，并未通知用户空间。

1. void kobject_init(struct kobject *kobj, struct kobj_type *ktype)  


2. {  


3.     char *err_str;  


4.   


5.     if (!kobj) {  


6.         err_str = “invalid kobject pointer!”;  


7.         goto error;  


8.     }  


9.     if (!ktype) {  


10.         err_str = “must have a ktype to be initialized properly!\n”;  


11.         goto error;  


12.     }  


13.     if (kobj->state_initialized) {  


14.         /* do not error out as sometimes we can recover */  


15.         printk(KERN_ERR “kobject (%p): tried to init an initialized “  


16.                “object, something is seriously wrong.\n”, kobj);  


17.         dump_stack();  


18.     }  


19.   


20.     kobject_init_internal(kobj);  


21.     kobj->ktype = ktype;  


22.     return;  


23.   


24. error:  


25.     printk(KERN_ERR “kobject (%p): %s\n”, kobj, err_str);  


26.     dump_stack();  


27. }  

kobject_init()就是调用kobject_init_internal()自动初始化了一些结构变量，然后又设置了ktype。其实这个ktype主要是管理一些默认属性什么的，只要在kobject_add_internal()调用create_dir()之前设置就行，之所以会出现在kobject_init()中，完全是为了与后面的kobject_create()相对比。

1. static int kobject_add_varg(struct kobject *kobj, struct kobject *parent,  


2.                 const char *fmt, va_list vargs)  


3. {  


4.     int retval;  


5.   


6.     retval = kobject_set_name_vargs(kobj, fmt, vargs);  


7.     if (retval) {  


8.         printk(KERN_ERR “kobject: can not set name properly!\n”);  


9.         return retval;  


10.     }  


11.     kobj->parent = parent;  


12.     return kobject_add_internal(kobj);  


13. }  


14.   


15. /** 


16.  * kobject_add – the main kobject add function 


17.  * @kobj: the kobject to add 


18.  * @parent: pointer to the parent of the kobject. 


19.  * @fmt: format to name the kobject with. 


20.  * 


21.  * The kobject name is set and added to the kobject hierarchy in this 


22.  * function. 


23.  * 


24.  * If @parent is set, then the parent of the @kobj will be set to it. 


25.  * If @parent is NULL, then the parent of the @kobj will be set to the 


26.  * kobject associted with the kset assigned to this kobject.  If no kset 


27.  * is assigned to the kobject, then the kobject will be located in the 


28.  * root of the sysfs tree. 


29.  * 


30.  * If this function returns an error, kobject_put() must be called to 


31.  * properly clean up the memory associated with the object. 


32.  * Under no instance should the kobject that is passed to this function 


33.  * be directly freed with a call to kfree(), that can leak memory. 


34.  * 


35.  * Note, no “add” uevent will be created with this call, the caller should set 


36.  * up all of the necessary sysfs files for the object and then call 


37.  * kobject_uevent() with the UEVENT_ADD parameter to ensure that 


38.  * userspace is properly notified of this kobject’s creation. 


39.  */  


40. int kobject_add(struct kobject *kobj, struct kobject *parent,  


41.         const char *fmt, …)  


42. {  


43.     va_list args;  


44.     int retval;  


45.   


46.     if (!kobj)  


47.         return -EINVAL;  


48.   


49.     if (!kobj->state_initialized) {  


50.         printk(KERN_ERR “kobject ‘%s’ (%p): tried to add an “  


51.                “uninitialized object, something is seriously wrong.\n”,  


52.                kobject_name(kobj), kobj);  


53.         dump_stack();  


54.         return -EINVAL;  


55.     }  


56.     va_start(args, fmt);  


57.     retval = kobject_add_varg(kobj, parent, fmt, args);  


58.     va_end(args);  


59.   


60.     return retval;  


61. }  

kobject_add()把kobj添加到体系中。但它还有一个附加功能，设置kobj的名字。parent也是作为参数传进来的，至于为什么kset没有同样传进来，或许是历史遗留原因吧。

1. int kobject_init_and_add(struct kobject *kobj, struct kobj_type *ktype,  


2.              struct kobject *parent, const char *fmt, …)  


3. {  


4.     va_list args;  


5.     int retval;  


6.   


7.     kobject_init(kobj, ktype);  


8.   


9.     va_start(args, fmt);  


10.     retval = kobject_add_varg(kobj, parent, fmt, args);  


11.     va_end(args);  


12.   


13.     return retval;  


14. }  

kobject_init_and_add()虽然是kobject_init()和kobject_add()的合并，但并不常用，因为其中根本没留下设置kset的空挡，这无疑不太合适。

1. int kobject_rename(struct kobject *kobj, const char *new_name)  


2. {  


3.     int error = 0;  


4.     const char *devpath = NULL;  


5.     const char *dup_name = NULL, *name;  


6.     char *devpath_string = NULL;  


7.     char *envp[2];  


8.   


9.     kobj = kobject_get(kobj);  


10.     if (!kobj)  


11.         return -EINVAL;  


12.     if (!kobj->parent)  


13.         return -EINVAL;  


14.   


15.     devpath = kobject_get_path(kobj, GFP_KERNEL);  


16.     if (!devpath) {  


17.         error = -ENOMEM;  


18.         goto out;  


19.     }  


20.     devpath_string = kmalloc(strlen(devpath) + 15, GFP_KERNEL);  


21.     if (!devpath_string) {  


22.         error = -ENOMEM;  


23.         goto out;  


24.     }  


25.     sprintf(devpath_string, “DEVPATH_OLD=%s”, devpath);  


26.     envp[0] = devpath_string;  


27.     envp[1] = NULL;  


28.   


29.     name = dup_name = kstrdup(new_name, GFP_KERNEL);  


30.     if (!name) {  


31.         error = -ENOMEM;  


32.         goto out;  


33.     }  


34.   


35.     error = sysfs_rename_dir(kobj, new_name);  


36.     if (error)  


37.         goto out;  


38.   


39.     /* Install the new kobject name */  


40.     dup_name = kobj->name;  


41.     kobj->name = name;  


42.   


43.     /* This function is mostly/only used for network interface. 


44.      * Some hotplug package track interfaces by their name and 


45.      * therefore want to know when the name is changed by the user. */  


46.     kobject_uevent_env(kobj, KOBJ_MOVE, envp);  


47.   


48. out:  


49.     kfree(dup_name);  


50.     kfree(devpath_string);  


51.     kfree(devpath);  


52.     kobject_put(kobj);  


53.   


54.     return error;  


55. }