IT培训机构|91免费精品视频|专注编程培训|91免费精品|软件开发培训_91免费国产视频_华清远见教育

    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)的定義很簡單（<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ù)類型差別很大，如果對每一種數(shù)據(jù)項(xiàng)類型都需要定義各自的鏈表結(jié)構(gòu)，不利于抽象成為公共的模板。

    在Linux內(nèi)核鏈表中，需要用鏈表組織起來的數(shù)據(jù)通常會包含一個(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的簡捷實(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) }
    #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

    這樣，當(dāng)需要用LIST_HEAD(nf_sockopts)聲明一個(gè)名為nf_sockopts的鏈表頭時(shí)，它的next、prev指針都初始化為指向自己。這樣就構(gòu)建了一個(gè)空鏈表，因?yàn)長inux用頭指針的next是否指向自己來判斷鏈表是否為空。

    static inline int list_empty(const struct list_head *head)
    { return head->next == 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);
    (ptr)->prev = (ptr); } while (0)

    （2）插入

    對鏈表的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個(gè)接口：

    static inline void list_add(struct list_head *new, struct list_head *head);
    static inline void list_add_tail(struct list_head *new, struct list_head *head);

    因?yàn)長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,
    struct list_head *prev,
    struct list_head *next)
    {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
    }
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next);
    }
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head);
    }

    （3）刪除

    Linux中刪除的代碼也是類似的，通過__list_del來實(shí)現(xiàn)list_del接口，讀者可以自行分析以下代碼段：

    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;
    }
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
    }

    從接口函數(shù)中可以看到，被刪除下來的prev、next指針分別被設(shè)為LIST_POSITION2和LIST_POSITION1兩個(gè)特殊值，這樣設(shè)置是為了保證不在鏈表中的節(jié)點(diǎn)項(xiàng)不可訪問，對LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。與之相對應(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)鏈表
   2、嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
   3、嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之單向鏈表

更多新聞>>