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代碼中遇到鏈表的使用，不會再陌生。