Linux カーネルのデータ構造

Linux のリスト API は侵入型です。リンク情報がサブシステムの所有するオブジェクトに埋め込まれています。侵入型にすると別個のノード割り当てが不要になり、1 つのオブジェクトが複数のインデックスに参加できますが、コンテナー API はメモリを所有せず、同期も提供しません。

循環双方向リンクリスト #

struct list_head はリンクだけを含みます。

struct list_head {
    struct list_head *next, *prev;
};

struct job {
    unsigned long id;
    struct list_head pending_link;
    struct list_head owner_link;
};

リストヘッドは埋め込みノードと同じ型です。空のリストでは next と prev はどちらもヘッド自身を指します。空でないリストでは、どちらの方向にたどっても最終的にヘッドへ戻ります。ヘッドはペイロードオブジェクトではなくセンチネルであるため、反復に NULL 終端はありません。

1 つのオブジェクトは、異なるメンバーを通じて複数のリストに現れることができます。すべての操作では正しいメンバーを指定する必要があり、pending_link と owner_link を混在させると両方のリストが破損します。

初期化と基本的な変更 #

宣言には LIST_HEAD() を使用し、既存のオブジェクトを初期化するときは INIT_LIST_HEAD() を使用します。

static LIST_HEAD(pending_jobs);

struct queue {
    spinlock_t lock;
    struct list_head jobs;
};

static void queue_init(struct queue *queue)
{
    spin_lock_init(&queue->lock);
    INIT_LIST_HEAD(&queue->jobs);
}

LIST_HEAD_INIT(name) は初期化子式であり、大きな静的初期化子の内部で便利です。リスト操作の前に初期化を行う必要があります。

挿入はセンチネルを基準にします。

list_add(&job->pending_link, &pending_jobs);      /* after head */
list_add_tail(&job->pending_link, &pending_jobs); /* before head */

list_add() は先頭へのスタック形式の挿入を、list_add_tail() は末尾へのキュー形式の挿入を実装します。list_move() と list_move_tail() は既存ノードをリンク解除し、移動先の先頭または末尾に挿入します。

list_del() はノードのリンクを解除し、リンクを poison して誤った再利用を明らかにします。切り離したノードを再び有効な自己リンクされた空ノードにする必要がある場合は、list_del_init() を使用します。

if (!list_empty(&pending_jobs)) {
    struct job *job =
        list_first_entry(&pending_jobs, struct job, pending_link);

    list_del_init(&job->pending_link);
    finish_job(job);
}

1 つのリンクメンバーを 2 回追加しないでください。自己リンクされたノードは list_empty(&job->pending_link) で確認できますが、この慣例が機能するのは、すべての削除でノードを再初期化する場合だけです。

container_of による所有オブジェクトの取得 #

イテレーターは struct list_head * に到達しますが、サブシステムコードにはそれを含むオブジェクトが必要です。container_of(ptr, type, member) は、member のコンパイル時オフセットを ptr から減算し、コンパイル時の型チェックを維持します。list_entry() はそのパターンに特化したものです。

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

struct job *job =
    list_entry(node, struct job, pending_link);

結果が有効なのは、node が実際に生きている struct job の指定されたメンバーを表す場合だけです。どちらのマクロも動的な型検証は行いません。

型付き反復を使うと明示的な変換を避けられます。

struct job *job;

list_for_each_entry(job, &pending_jobs, pending_link)
    run_job(job);

逆方向および継続用のバリエーションも、一般的でない走査パターン向けに存在します。センチネル処理がマクロに組み込まれているため、next と prev を手書きするのではなく、文書化された最も狭いマクロを選択します。

反復中の削除 #

通常の反復は、ループ本体の後で現在ノードの次のリンクを読み取ります。現在のノードを削除すると、その操作が無効になります。_safe イテレーターは次のオブジェクトを先に保存します。

struct job *job, *next;

list_for_each_entry_safe(job, next, &pending_jobs, pending_link) {
    if (job_cancelled(job)) {
        list_del(&job->pending_link);
        kfree(job);
    }
}

「safe」とは、このループによる削除に対して安全という意味です。別の CPU、割り込み、コールバックによるリスト変更から保護するものではなく、kfree() が合法であることも確立しません。外部参照には、参照カウント、RCU、または別のライフタイムプロトコルが必要になる場合があります。

リストのスプライス #

スプライス操作はリスト全体を定数時間で再リンクします。

LIST_HEAD(batch);

build_batch(&batch);
list_splice_tail_init(&batch, &pending_jobs);

• list_splice() は移動先ヘッドの後ろに挿入する。
• list_splice_tail() は移動先ヘッドの前に挿入する。
• _init バリエーションはソースヘッドも再初期化する。

_init なしの list_splice() の後では、ソースヘッドは転送されたチェーンを指したままです。リンクは独立した循環リストを表さなくなっているため、そのソースを独立したリストとして反復すると誤ってループする可能性があります。所有権を移転し、ソースを空にする必要がある場合は _init バリエーションを使用します。

list_cut_position() はプレフィックスを別のヘッドへ移動します。すべてのリスト変更と同様に、すべてのノードとヘッドが想定されたリストに属していることを呼び出し元が保証する必要があります。

ハッシュ化された単方向リスト #

ハッシュテーブルには多数のバケットヘッドが必要なため、hlist は 1 ポインターのヘッドを使用します。

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

struct cache_entry {
    unsigned long key;
    struct hlist_node hash_node;
};

pprev はノードを指すリンクを指します。これはバケットの first メンバーまたは前のノードの next メンバーのいずれかです。したがって、削除時に通常の prev ポインターを格納せず、定数時間で先行リンクを更新できます。この非対称な表現は、すべてのバケットに多くのバケットがある場合に重要となる、各バケットヘッドのポインター 1 つを節約します。

static struct hlist_head table[256];

static void cache_insert(struct cache_entry *entry)
{
    unsigned int bucket = hash_long(entry->key, 8);

    hlist_add_head(&entry->hash_node, &table[bucket]);
}

static struct cache_entry *cache_find(unsigned long key)
{
    struct cache_entry *entry;

    hlist_for_each_entry(entry, &table[hash_long(key, 8)], hash_node)
        if (entry->key == key)
            return entry;
    return NULL;
}

コードが hlist_unhashed() に依存する場合は、独立したノードを INIT_HLIST_NODE() で初期化します。削除後に再利用する場合は hlist_del_init() を使用し、現在のループでエントリを削除する場合は hlist_for_each_entry_safe() を使用します。

並行性とライフタイムは呼び出し元の責任 #

リストと hlist の操作はポインターの書き換えであり、トランザクションではありません。API は暗黙のロック、参照カウント、ペイロードフィールド公開用のメモリバリア、再利用猶予期間を提供しません。サブシステムは次を定義する必要があります。

1. 挿入と削除を直列化するロック。
2. コンテナーを走査できるコンテキスト。
3. 読み取り側がオブジェクト参照を取得する方法。
4. 削除されたオブジェクトを解放できる時点。

クリティカルセクションがスリープできない場合は、スピンロックで走査と変更の両方を保護できます。スリープ可能なプロセスコンテキストではミューテックスが適しています。読み取りが多い構造では、list_add_rcu()、list_del_rcu()、hlist_for_each_entry_rcu() などの RCU 固有 API によりロックレスリーダーを許可できますが、必要な公開プリミティブと猶予期間後の遅延再利用を伴う場合に限ります。完全なプロトコルなしに通常のバリエーションと RCU バリエーションを混在させるのは安全ではありません。

_safe 反復サフィックスと _rcu サフィックスは異なる問題を解決します。_safe はローカル削除中のループカーソルを保持し、_rcu は同時リーダーのライフタイムスキームに参加します。

参照 #

• Kernel Documentation: Linked Lists
• Kernel Source: include/linux/list.h
• Kernel Documentation: RCU List APIs