 |
|
ARM Linux中鏈表使用實(shí)例 |
|
|
1、ARM Linux內(nèi)核鏈表概述 在ARM Linux中，鏈表是為基本的數(shù)據(jù)結(jié)構(gòu)，也是為常用的數(shù)據(jù)結(jié)構(gòu)。在本文中盡管使用2.6內(nèi)核作為講解的基礎(chǔ)，但實(shí)際上2.4內(nèi)核中的鏈表結(jié)構(gòu)和2.6并沒有太大區(qū)別。二者不同之處在于2.6擴(kuò)充了兩種鏈表數(shù)據(jù)結(jié)構(gòu)：鏈表的讀拷貝更新（rcu）和HASH鏈表（hlist）。這兩種擴(kuò)展都是基于基本的list結(jié)構(gòu)。因此，在此處主要介紹基本鏈表結(jié)構(gòu)。 鏈表數(shù)據(jù)結(jié)構(gòu)的定義很簡(jiǎn)單（<include/linux/list.h>，以下所有代碼除非加以說明，其余均取自該文件）： struct list_head { struct list_head *next, *prev; }; list_head結(jié)構(gòu)包含兩個(gè)指向list_head結(jié)構(gòu)的指針prev和next，由此可見，內(nèi)核的鏈表具備雙鏈表功能，實(shí)際上，通常它都組織成雙循環(huán)鏈表。 和之前介紹的雙鏈表結(jié)構(gòu)模型不同，這里的list_head沒有數(shù)據(jù)域。在Linux內(nèi)核鏈表中，不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點(diǎn)。由于鏈表數(shù)據(jù)類型差別很大，如果對(duì)每一種數(shù)據(jù)項(xiàng)類型都需要定義各自的鏈表結(jié)構(gòu)，不利于抽象成為公共的模板。 在Linux內(nèi)核鏈表中，需要用鏈表組織起來的數(shù)據(jù)通常會(huì)包含一個(gè)struct list_head成員，例如在<include/linux/netfilter.h>中定義了一個(gè)nf_sockopt_ops結(jié)構(gòu)來描述netfilter為某一協(xié)議族準(zhǔn)備的getsockopt/setsockopt接口，其中就有一個(gè)（struct list_head list）成員，各個(gè)協(xié)議族的nf_sockopt_ops結(jié)構(gòu)都通過這個(gè)list成員組織在一個(gè)鏈表中，表頭是定義在<net/core/netfilter.c>中的nf_sockopts（struct list_head）。讀者可以看到，Linux的簡(jiǎn)捷實(shí)用、不求完美和標(biāo)準(zhǔn)的風(fēng)格在這里體現(xiàn)得相當(dāng)充分。 2、Linux內(nèi)核鏈表接口 （1）聲明和初始化 實(shí)際上Linux只定義了鏈表節(jié)點(diǎn)，并沒有專門定義鏈表頭，那么一個(gè)鏈表結(jié)構(gòu)是如何建立起來的呢？這里是使用LIST_HEAD()這個(gè)宏來構(gòu)建的。 #define LIST_HEAD_INIT(name) { &(name), &(name) } 這樣，當(dāng)需要用LIST_HEAD(nf_sockopts)聲明一個(gè)名為nf_sockopts的鏈表頭時(shí)，它的next、prev指針都初始化為指向自己。這樣就構(gòu)建了一個(gè)空鏈表，因?yàn)長(zhǎng)inux用頭指針的next是否指向自己來判斷鏈表是否為空。 static inline int list_empty(const struct list_head *head) 除了用LIST_HEAD()宏在聲明的時(shí)候創(chuàng)建一個(gè)鏈表以外，Linux還提供了一個(gè)INIT_LIST_HEAD宏用于運(yùn)行時(shí)創(chuàng)建鏈表： #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); （2）插入 對(duì)鏈表的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個(gè)接口： static inline void list_add(struct list_head *new, struct list_head *head); 因?yàn)長(zhǎng)inux鏈表是循環(huán)表，且表頭的next、prev分別指向鏈表中的第一個(gè)和末一個(gè)節(jié)點(diǎn)，所以，list_add()和list_add_tail()的區(qū)別并不大，實(shí)際上，Linux分別用以下兩個(gè)函數(shù)來實(shí)現(xiàn)接口。 static inline void __list_add(struct list_head *new, （3）刪除 Linux中刪除的代碼也是類似的，通過__list_del來實(shí)現(xiàn)list_del接口，讀者可以自行分析以下代碼段： static inline void __list_del(struct list_head * prev, struct list_head * next) 從接口函數(shù)中可以看到，被刪除下來的prev、next指針分別被設(shè)為L(zhǎng)IST_POSITION2和LIST_POSITION1兩個(gè)特殊值，這樣設(shè)置是為了保證不在鏈表中的節(jié)點(diǎn)項(xiàng)不可訪問，對(duì)LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。與之相對(duì)應(yīng)，list_del_init()函數(shù)將節(jié)點(diǎn)從鏈表中解下來之后，調(diào)用LIST_INIT_HEAD()將節(jié)點(diǎn)置為空鏈狀態(tài)。 熱點(diǎn)鏈接：
1、嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表 |