List in FreeBSD

Linuxカーネルにおけるリスト型データ構造と同じように，FreeBSDでもリスト型のデータ構造が非常に多く使われている．

その簡単な説明

Queue

<sys/queue.h>に色々実装されており，結局そことかman読むのが一番早いが軽く一部を取り上げて説明する

LIST_HEAD

LIST_HEADマクロは以下の様に定義されており，

#define LIST_HEAD(name, type)           \
struct name {                           \
    struct type *lh_first;              \
}

以下の様に宣言される

LIST_HEAD(HEADNAME, TYPE) head;

ここで，HEADNAMEは定義する構造体の名前で，TYPEはリストにリンクする型である． リストのヘッドへのポインタは

struct HEADNAME *headp;

の様に宣言できる．

LIST_HEAD_INITIALIZER

listのheadのinitializer

#define LIST_HEAD_INITIALIZER(head)     \
    {NULL}

LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head);

みたいに使う．

LIST_ENTRY

リスト内の要素を接続する重要な奴

#define LIST_ENTRY(type)            \
struct {                            \
    struct type *le_next;           \
    struct type **pe_prev;          \
}

LIST_NEXT, LIST_FIRST

そのまんま．

#define LIST_NEXT(elm, field)   ((elm)->field.le_next)

#define LIST_FIRST(head)    ((head)->lh_first)

LIST_FOREACH

名前の通り

#define LIST_FOREACH(var, head, field)      \
    for ((var) = LIST_FIRST((head));        \
        (var);                              \
        (var) = LIST_NEXT((var), field))

fieldにはLIST_ENTRYで宣言された構造体が入る

LIST_REMOVE

要素を指定してリストから削除する

#define LIST_REMOVE(elm, field) do {                \
    QMD_SAVELINK(oldnext, (elm)->field.le_next);    \
    QMD_SAVELINK(oldprev, (elm)->field.le_prev);    \
    QMD_LIST_CHECK_NEXT(elm, field);                \
    QMD_LIST_CHECK_PREV(elm, field);                \
    if (LIST_NEXT((elm), field) != NULL)            \
        LIST_NEXT((elm), field)->field.le_prev =    \
            (elm)->field.le_prev;                   \
    *(elm)->field.le_prev = LIST_NEXT((elm), field);\
    TRASHIT(*oldnext);                              \
    TRASHIT(*oldprev);                              \
} while (0)

LIST_INSERT

#define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
        QMD_LIST_CHECK_NEXT(listelm, field);                            \
        if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
                LIST_NEXT((listelm), field)->field.le_prev =            \
                    &LIST_NEXT((elm), field);                           \
        LIST_NEXT((listelm), field) = (elm);                            \
        (elm)->field.le_prev = &LIST_NEXT((listelm), field);            \
} while (0)

#define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
        QMD_LIST_CHECK_PREV(listelm, field);                            \
        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        LIST_NEXT((elm), field) = (listelm);                            \
        *(listelm)->field.le_prev = (elm);                              \
        (listelm)->field.le_prev = &LIST_NEXT((elm), field);            \
} while (0)

#define LIST_INSERT_HEAD(head, elm, field) do {                         \
        QMD_LIST_CHECK_HEAD((head), field);                             \
        if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
                LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
        LIST_FIRST((head)) = (elm);                                     \
        (elm)->field.le_prev = &LIST_FIRST((head));                     \
} while (0)

QMD_SAVELINK, QMD_LIST_CHECK_*

ここらへんはまとめて定義書くだけにする． 名前の通りだし，カーネルの外では意味ないし

#if (defined(_KERNEL) && defined(INVARIANTS))
#define QMD_LIST_CHECK_HEAD(head, field) do {                           \
        if (LIST_FIRST((head)) != NULL &&                               \
            LIST_FIRST((head))->field.le_prev !=                        \
             &LIST_FIRST((head)))                                       \
                panic("Bad list head %p first->prev != head", (head));  \
} while (0)

#define QMD_LIST_CHECK_NEXT(elm, field) do {                            \
        if (LIST_NEXT((elm), field) != NULL &&                          \
            LIST_NEXT((elm), field)->field.le_prev !=                   \
             &((elm)->field.le_next))                                   \
                panic("Bad link elm %p next->prev != elm", (elm));      \
} while (0)

#define QMD_LIST_CHECK_PREV(elm, field) do {                            \
        if (*(elm)->field.le_prev != (elm))                             \
                panic("Bad link elm %p prev->next != elm", (elm));      \
} while (0)
~snip~
#ifdef QUEUE_MACRO_DEBUG
#define QMD_SAVELINK(name, link)        void **name = (void *)&(link)
~snip~

環境

FreeBSD 11.4 stable

参考文献

Designing BSD Rootkits