Linux内核链表实现剖析
內核鏈表詳細信息見 include/ linux / list.h 。
?
1. 定義和初始化內核鏈表
?
struct list_head {
??????struct? list_head *prev, *next ;
} ;
list_head不包含數據，一般內嵌于其它數據結構中。
定義list_head
struct my_struct {
??????? struct list_head list ;
??????? unsigned long dog ;
??????? void *cat ;
} ;
靜態初始化鏈表
struct my_struct *p ;
p = kmalloc( sizeof(struct my_struct) , GFP_KERNEL) ;
if ( !p )
??????? return -ENOMEM ;
p->dog = 0 ;
p->cat = NULL ;
p->list = LIST_HEAD_INIT( p->list ) ; // #define LIST_HEAD_INIT(name) { &(name), &(name) }
或者
struct my_struct mine = {
??????? .list = LIST_HEAD_INIT( mine->list ) ;
????????.dog = 0 ;
??????? .cat = NULL ;
} ;
或者
static LIST_HEAD( list ) ; //定義加初始化
#define LIST_HEAD(name) \
?????? ?struct list_head name = LIST_HEAD_INIT(name)
?
動態初始化鏈表
struct my_struct *p ;
..................
INIT_LIST_HEAD( &p->list ) ;
//函數說明
static inline void INIT_LIST_HEAD(struct list_head *list)
{
?list->next = list;
?list->prev = list;
}
?
2. 操作鏈表
?
2.1判斷鏈表
/**
?*list_empty - test whether a list is empty
?*@head : the list to test
?*/
static inline int list_empty( const struct list_head * head )
{
??????? return head->next == head ;
}
/**
?* list_is_last - test whether @list is the last entry in list @head
?* @list : the entry to test
?* @head : the head of the list
?*/
static inline int list_is_last( const struct list_head *list ,
??????????????? const struct list_head *head )
{
??????? return list->next == head ;
}
2.2插入
/**
?*Insert a new entry between two known consecutive entries.
?*This is only for internal list manipulation where we know
?*the prev/next entries already!
?*/
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 ;
}
/**
?*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 *new )
{
??????? __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 ) ;
}
對鏈表的插入有兩種：在表頭插入和在表尾插入。
例：
struct my_struct new_my_struct ;
/* 初始化new_my_struct */
LIST_HEAD(list) ;
list_add ( &new_my_struct . list , &list ) ;
?
2.3 刪除
/**
?* Delete a list entry by making the prev / next entries
?* point to each other.
?*
?* This is only for internal list manipulation where we know
?* the prev/next entries already!
?*/
static inline void __list_del( struct list_head * prev , struct list_head * next )
{
??????? next->prev = prev ;
??????? prev->next = next ;
}
?
/**
?* list_del - deletes entry from list.
?* @entry : the element to delete from the list.
?* Note : list_empty() on entry does not return true after this , the entry is
?* in an undefined state.
?*/
static inline void list_del( struct list_head *entry )
{
??????? __list_del( entry->prev , entry->next ) ;
??????? entry->next = LIST_POISON1 ;
??????? entry->prev = LIST_POISON2 ;
}
例：
list_del ( &new_my_struct . list ) ;
?
2.4 替換
/**
?* list_replace - replace old entry by new one
?* @old : the element to be replaced
?* @new : the new element to insert
?*
?* If @old was empty , it will be overwritten. ？不會oops？
?*/
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 ;
}
static inline void list_replace_init ( struct list_head *old ,
??????????????? struct list_head *new )
{
??????? list_replace( old , new ) ;
??????? INIT_LIST_HEAD( old ) ;
}
/**
?* list_del_init - deletes entry from list and reinitialize it .
?* @entry : the element to delete from the list .
?*/
static inline void list_del_init ( struct list_head *entry )
{
??????? __list_del( entry->prev , entry->next ) ;
??????? INIT_LIST_HEAD( entry ) ;
}
?
2.5 搬移
/**
?* list_move - delete from the list and add as another's head
?* @list : the entry to move
?* @head : the head that will precede our entry
?*/
static inline void list_move ( struct list_head *list , struct list_head *head )
{
??????? __list_del( list->prev , list->next ) ;
??????? list_add( list , head ) ;
}
/**
?* list_move_tail - delete from one list and add as another's tail
?* @list : the entry to move
?* @head : the head that will follow our entry
?*/
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 ) ;
}
?
2.6合并
把第一個鏈表合并到第二個鏈表。注意，第一個鏈表首節點被放棄。
/**
?* list_splice - join two lists , this is designed for stacks
?* @list : the new list to add.
?* @head : the place to add the first list.
?*/
static inline void list_splice( const struct list_head *list ,
??????????????? struct list_head *head )
{
??????? if( !list_empty( list ) )
?????????????? __list_splice( list , head , head->next ) ;
}
static inline void __list_splice( const struct list_head *list ,
??????????????? struct list_head *prev ,
??????????????? struct list_head *next )
{
??????? struct list_head *first = list->next ;
??????? struct list_head *last = list->prev ;
??????? first->prev = prev ;
??????? prev->next = first ;
??????? last->next = next ;
??????? next->prev = last ;
}
/**
?* list_splice_tail - join two lists , each list being a queue
?* @list : the new list to add.
?* @head : the place to add it in the first list .
?*/
static inline void list_splice_tail( struct list_head *list ,
??????????????? struct list_head *head )
{
?????? if( ! list_empty( list ) )
??????????????? __list_splice( list , head ->prev , head ) ;
}
?
3. 遍歷
?
/**
?* 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 )
例：
// mine為初始化了得my_struct結構體
struct my_struct *p = list_entry( &mine . list , my_struct , list ) ;
?
#define container_of ( ptr , type , member ) ( {?? \
??????? const typeof( ( ( type *)0)->member) *__mptr = (ptr) ;? \
??????????????? (type *) ( ( char *) __mptr - offsetof (type , member) ) ;
?
#define offsetof( TYPE , MEMBER) ( ( size_t) & ( (TYPE *) 0)->MEMBER)
這里使用的是一個利用編譯器技術的小技巧，即先求得結構成員在與結構中的偏移量，然后根據成員變量的地址反過來得出屬主結構變量的地址。
container_of()和offsetof()并不僅用于鏈表操作，這里最有趣的地方是((type *)0)->member，它將0地址強制"轉換"為type結構的指針，再訪問到type結構中的member成員。在container_of宏中，它用來給typeof()提供參數（typeof()是gcc的擴展，和sizeof()類似），以獲得member成員的數據類型；在offsetof()中，這個member成員的地址實際上就是type數據結構中member成員相對于結構變量的偏移量。
?
/**
?* 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 ; prefetch(pos->next ) , pos != head ; \
??????????????? pos = pos->next )
它實際上是一個for循環，利用傳入的pos作為循環變量，從表頭head開始，逐項向后（next方向）移動pos，直至又回到head（prefetch()可以不考慮，用于預取以提高遍歷速度）。
例：
//遍歷my_struct鏈表，從mine開始
struct list_head *p ;
list_for_each( p , &mine . list ) {
??????? struct my_struct *ptr = list_entry ( p , my_struct , list ) ;
??????? printk(KERN_ALERT" the number of dog : %ld " , ptr->dog ) ;
}
大多數情況下，遍歷鏈表的時候都需要獲得鏈表節點數據項，也就是說list_for_each()和list_entry()總是同時使用。
/**
?* 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_struct within the struct.
?*/
#define list_for_each_entry ( pos , head , member )
??????? for ( pos = list_entry ( (head)->next , typeof(*pos) , member ) ; \
?????????????? &pos->member != (head) ; \
?????????????? pos = list_entry (pos->member.next , typeof(*pos) , member ))
?
list_for_each_entry相當于list_for_each和list_entry的結合，可以更加方便的使用。
?
4. 安全性考慮
在并發執行的環境下，鏈表操作通常都應該考慮同步安全性問題，為了方便，Linux將這一操作留給應用自己處理。Linux鏈表自己考慮的安全性主要有兩個方面：
a) list_empty()判斷
基本的list_empty()僅以頭指針的next是否指向自己來判斷鏈表是否為空，Linux鏈表另行提供了一個list_empty_careful()宏，它同時判斷頭指針的next和prev，僅當兩者都指向自己時才返回真。這主要是為了應付另一個cpu正在處理同一個鏈表而造成next、prev不一致的情況。但代碼注釋也承認，這一安全保障能力有限：除非其他cpu的鏈表操作只有list_del_init()，否則仍然不能保證安全，也就是說，還是需要加鎖保護。
b) 遍歷時節點刪除
前面介紹了用于鏈表遍歷的幾個宏，它們都是通過移動pos指針來達到遍歷的目的。但如果遍歷的操作中包含刪除pos指針所指向的節點，pos指針的移動就會被中斷，因為list_del(pos)將把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
當然，調用者完全可以自己緩存next指針使遍歷操作能夠連貫起來，但為了編程的一致性，Linux鏈表仍然提供了兩個對應于基本遍歷操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它們要求調用者另外提供一個與pos同類型的指針n，在for循環中暫存pos下一個節點的地址，避免因pos節點被釋放而造成的斷鏈。
?
擴展
1. hlist
?list和hlist
精益求精的Linux鏈表設計者（因為list.h沒有署名，所以很可能就是Linus Torvalds）認為雙頭（next、prev）的雙鏈表對于HASH表來說"過于浪費"，因而另行設計了一套用于HASH表應用的hlist數據結構--單指針表頭雙循環鏈表，從上圖可以看出，hlist的表頭僅有一個指向首節點的指針，而沒有指向尾節點的指針，這樣在可能是海量的HASH表中存儲的表頭就能減少一半的空間消耗。
因為表頭和節點的數據結構不同，插入操作如果發生在表頭和首節點之間，以往的方法就行不通了：表頭的first指針必須修改指向新插入的節點，卻不能使用類似list_add()這樣統一的描述。為此，hlist節點的prev不再是指向前一個節點的指針，而是指向前一個節點（可能是表頭）中的next（對于表頭則是first）指針（struct list_head **pprev），從而在表頭插入的操作可以通過一致的"*(node->pprev)"訪問和修改前驅節點的next（或first）指針。
?
2. read-copy update
在Linux鏈表功能接口中還有一系列以"_rcu"結尾的宏，與以上介紹的很多函數一一對應。RCU（Read-Copy Update）是2.5/2.6內核中引入的新技術，它通過延遲寫操作來提高同步性能。
我們知道，系統中數據讀取操作遠多于寫操作，而rwlock機制在smp環境下隨著處理機增多性能會迅速下降。針對這一應用背景，IBM Linux技術中心的Paul E. McKenney提出了"讀拷貝更新"的技術，并將其應用于Linux內核中。RCU技術的核心是寫操作分為寫-更新兩步，允許讀操作在任何時候無阻訪問，當系統有寫操作時，更新動作一直延遲到對該數據的所有讀操作完成為止。
參考：http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/?很詳細的一個帖子
?
?
轉載于:https://www.cnblogs.com/aiwz/archive/2011/11/24/6333405.html
總結
以上是生活随笔為你收集整理的Linux内核链表实现剖析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 查看Tomcat使用的版本
- 下一篇： 依赖注入机制