 |
|
ARM Linux中鏈表使用實例 |
|
|
1、ARM Linux內核鏈表概述 在ARM Linux中(zhong)，鏈(lian)表(biao)(biao)是(shi)(shi)為(wei)基(ji)本的(de)(de)數(shu)據(ju)結(jie)構(gou)，也是(shi)(shi)為(wei)常用的(de)(de)數(shu)據(ju)結(jie)構(gou)。在本文中(zhong)盡管使用2.6內核作為(wei)講解的(de)(de)基(ji)礎，但實際上2.4內核中(zhong)的(de)(de)鏈(lian)表(biao)(biao)結(jie)構(gou)和2.6并(bing)沒有太大區別(bie)。二者不同之處(chu)在于2.6擴(kuo)充了兩種鏈(lian)表(biao)(biao)數(shu)據(ju)結(jie)構(gou)：鏈(lian)表(biao)(biao)的(de)(de)讀拷貝更新（rcu）和HASH鏈(lian)表(biao)(biao)（hlist）。這兩種擴(kuo)展都是(shi)(shi)基(ji)于基(ji)本的(de)(de)list結(jie)構(gou)。因此，在此處(chu)主要介(jie)紹基(ji)本鏈(lian)表(biao)(biao)結(jie)構(gou)。 鏈表數據結構的定義很簡單（<include/linux/list.h>，以(yi)下所有代(dai)碼除非加以(yi)說明(ming)，其余(yu)均取自該文件(jian)）： struct list_head { struct list_head *next, *prev; }; list_head結構包含兩個指(zhi)向list_head結構的指(zhi)針prev和next，由此可見，內核的鏈(lian)表具備雙鏈(lian)表功能，實際上(shang)，通常它(ta)都(dou)組織成雙循環鏈(lian)表。 和之前介紹的雙鏈表結構模型不同，這里(li)的(de)list_head沒有數據(ju)域。在(zai)Linux內核鏈(lian)表(biao)(biao)中，不是(shi)在(zai)鏈(lian)表(biao)(biao)結構中包含數據(ju)，而是(shi)在(zai)數據(ju)結構中包含鏈(lian)表(biao)(biao)節點。由于(yu)鏈(lian)表(biao)(biao)數據(ju)類型差別(bie)很大，如果對每一種數據(ju)項類型都需要(yao)定義各自的(de)鏈(lian)表(biao)(biao)結構，不利于(yu)抽象成為(wei)公共(gong)的(de)模板。 在Linux內(nei)核鏈表(biao)中(zhong)，需(xu)要用(yong)鏈表(biao)組織起來(lai)的(de)(de)(de)(de)數(shu)據通常(chang)會包含一(yi)個(ge)(ge)(ge)struct list_head成員(yuan)，例如在<include/linux/netfilter.h>中(zhong)定義(yi)了一(yi)個(ge)(ge)(ge)nf_sockopt_ops結構來(lai)描述netfilter為某一(yi)協議族準(zhun)備(bei)的(de)(de)(de)(de)getsockopt/setsockopt接口，其中(zhong)就(jiu)有(you)一(yi)個(ge)(ge)(ge)（struct list_head list）成員(yuan)，各(ge)個(ge)(ge)(ge)協議族的(de)(de)(de)(de)nf_sockopt_ops結構都通過這個(ge)(ge)(ge)list成員(yuan)組織在一(yi)個(ge)(ge)(ge)鏈表(biao)中(zhong)，表(biao)頭(tou)是定義(yi)在<net/core/netfilter.c>中(zhong)的(de)(de)(de)(de)nf_sockopts（struct list_head）。讀者可以看(kan)到(dao)，Linux的(de)(de)(de)(de)簡捷(jie)實用(yong)、不(bu)求完美和標準(zhun)的(de)(de)(de)(de)風格在這里體現得相當充分。 2、Linux內核鏈表接口 （1）聲明和初始化 實際上(shang)Linux只(zhi)定義了鏈(lian)表(biao)(biao)節點，并沒(mei)有專門定義鏈(lian)表(biao)(biao)頭，那么(me)一(yi)個鏈(lian)表(biao)(biao)結構(gou)是如何建立起來的呢？這里(li)是使用LIST_HEAD()這個宏來構(gou)建的。 #define LIST_HEAD_INIT(name) { &(name), &(name) } 這樣(yang)，當需要用LIST_HEAD(nf_sockopts)聲明一個名為(wei)nf_sockopts的(de)鏈表頭時，它的(de)next、prev指針(zhen)都(dou)初始化為(wei)指向(xiang)自己。這樣(yang)就構(gou)建了(le)一個空(kong)鏈表，因(yin)為(wei)Linux用頭指針(zhen)的(de)next是(shi)否指向(xiang)自己來判(pan)斷鏈表是(shi)否為(wei)空(kong)。 static inline int list_empty(const struct list_head *head) ; 除了(le)用LIST_HEAD()宏(hong)在聲明(ming)的(de)時(shi)候創建一個鏈表以外，Linux還提供了(le)一個INIT_LIST_HEAD宏(hong)用于運行時(shi)創建鏈表： #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); （2）插(cha)入 對(dui)鏈表的插(cha)入(ru)操(cao)作(zuo)有(you)兩種：在表頭(tou)插(cha)入(ru)和在表尾插(cha)入(ru)。Linux為此提(ti)供(gong)了(le)兩個(ge)接口： static inline void list_add(struct list_head *new, struct list_head *head); 因為Linux鏈表是循環表，且表頭的next、prev分別指向鏈表中的第(di)一(yi)個和末一(yi)個節點(dian)，所以，list_add()和list_add_tail()的區別并不(bu)大，實(shi)際上(shang)，Linux分別用以下兩(liang)個函數來實(shi)現接(jie)口。 static inline void __list_add(struct list_head *new, （3）刪除 Linux中刪除的(de)代碼也是類似的(de)，通過(guo)__list_del來實現list_del接口，讀(du)者可以自行分析以下代碼段： static inline void __list_del(struct list_head * prev, struct list_head * next) 從接口函(han)數中可以看到(dao)，被刪(shan)除下來的(de)prev、next指針分別被設為LIST_POSITION2和LIST_POSITION1兩個特殊(shu)值，這樣設置是(shi)為了保證不在鏈(lian)表中的(de)節(jie)點(dian)項不可訪(fang)問，對LIST_POSITION1和LIST_POSITION2的(de)訪(fang)問都將引(yin)起頁(ye)故障。與之相對應，list_del_init()函(han)數將節(jie)點(dian)從鏈(lian)表中解(jie)下來之后(hou)，調用LIST_INIT_HEAD()將節(jie)點(dian)置為空鏈(lian)狀態。 熱點鏈接：
1、嵌入式linux內核數據結構之循環鏈表 |