カーネルデータ構造
* Linked Lists(連結リスト)
連結リストは、Linuxカーネルで最も単純で最も一般的なデータ構造です。連結リスト
は、可変数の記憶および操作を可能にするデータ構造であるリストのノードと呼ばれる
要素の集合。静的配列とは異なり、連結リストの要素動的に作成され、リストに挿入さ
れます。これにより、コンパイル時に不明な要素の数。要素は異なる時間に、彼らは必
ずしもメモリ内の連続した領域を占有するとは限りません。要素同士をリンクさせる必
要があります。したがって、リストの各要素には、次の要素。リストに要素が追加また
は削除されると、その要素へのポインタ次のノードは単に調整されます。
code: C言語
図 6.1
/* an element in a linked list */
struct list_element {
void *data; /* the payload */
struct list_element *next; /* pointer to the next element */
};
┌────┐ ┌────┐ ┌────┐ ┌──┐
│...|next──>│...|next──>│...|next──>│null│
└────┘ └────┘ └────┘ └──┘
Figure 6.1 A singly linked list.
いくつかの連結リストでは、各要素には前の要素へのポインタも含まれています。これ
らの要素リストは前方および後方の両方にリンクされているため、リストは二重リンク
リストと呼ばれます。のような、前の要素へのポインタを持たないリンクされたリスト
単一連結リストと呼ばれます。二重にリンクされたリストを表すデータ構造は、次の
ようになります。
code: C言語
図 6.2
/* an element in a linked list */
struct list_element {
void *data; /* the payload */
struct list_element *next; /* pointer to the next element */
struct list_element *prev; /* pointer to the previous element */
};
┌──┐┌──────-┐ ┌──────-┐ ┌──────-┐ ┌──┐
│null││prev|...|next──>│prev|...|next──>│prev|...|next──>│null│
└──┘└-│─────┘ └-│─────┘ └-│─────┘ └──┘
∧ │ ∧ │ ∧ │
└───┘ └──────-┘ └──────-┘
Figure 6.2 A doubly linked list.
** Circular Linked Lists(循環型連結リスト)
通常、連結リストの最後の要素は次の要素を持たないため、ポイントするように設定さ
れていますそれがリストの最後の要素であることを示すNULLなどの特別な値。一部のリ
ンク先最後の要素は特別な値を指しません。代わりに、最初のこの連結リストは循環連
結リストなので循環連結リストと呼ばれます。循環連結リストは、二重にリンクされた
バージョンと単独でリンクされたバージョンの両方で提供されます。環状の二重連結リ
ストでは、最初のノードの「前の」ポインタは最後のノードを指します。図6.3と6.4は
単独で二重循環リンクリストと呼ばれる。
code: C言語
┌────┐ ┌────┐ ┌────┐
│...|next──>│...|next──>│...|next──┐
└────┘ └────┘ └────┘ │
∧ │
└──────────────────-┘
Figure 6.3 A circular singly linked list.
┌─────────────────────┐
│ ∨
┌-│─────┐ ┌──────-┐ ┌──────-┐
│prev|...|next──>│prev|...|next──>│prev|...|next──┐
└──────-┘ └-│─────┘ └-│─────┘ │
∧ │ ∧ │ │
│<──────-┘ └──────-┘ │
│ │
└─────────────────────────┘
Figure 6.4 A circular doubly linked list.
Linuxカーネルのリンクリストの実装はユニークですが、基本的には環状の二重リンクリスト(6.4)。このタイプのリンクされたリストを使用すると、最大の柔軟性が得られます。
** 連結リスト構造体
昔のカーネルコードでは、next, prev など同じようなコードが重複していました。
code: C言語
struct fox {
unsigned long tail_length; /* length in centimeters of tail */
unsigned long weight; /* weight in kilograms */
bool is_fantastic; /* is this fox fantastic? */
struct fox *next; /* next fox in linked list */
struct fox *prev; /* previous fox in linked list */
};
そこで、次のような構造体が実装されました。
code: C言語
struct list_head {
struct list_head *next
struct list_head *prev;
};
これを利用することで、重複を防げます。
code: C言語
struct fox {
unsigned long tail_length; /* length in centimeters of tail */
unsigned long weight; /* weight in kilograms */
bool is_fantastic; /* is this fox fantastic? */
struct list_head list; /* list of all fox structures */
};
次のノードにアクセスするときは list.next、前なら list.prev でアクセスできます。
** 便利なマクロ
- container_of
ポインタが指す構造体のメンバ、それを含む構造体へのポインタを返す。
code: C言語
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
例えば、
code: C言語
struct example {
int mem_a;
char mem_b;
};
struct example hoge;
という構造体があったとする。
code: C言語
int *mem_ptr = &hoge.a;
上記のような、構造体のメンバへのポインタ mem_ptr しか 分からない状態から hoge
へのポインタを得たいときに container_of を 使う。
code: C言語
struct example *ptr = container_of(mem_ptr, struct example, mem_a);
すると ptr が指す先（hoge.mem_a）を含む構造体への ポインタ（&hoge）が得られる。
** 連結リストの定義
次のような構造体があるとします。
code: C言語
struct fox {
unsigned long tail_length; /* length in centimeters of tail */
unsigned long weight; /* weight in kilograms */
bool is_fantastic; /* is this fox fantastic? */
struct list_head list; /* list of all fox structures */
};
リストを使用するには、そのリストを初期化する必要があります。要素のほとんどは
（おそらくリンクされたリストが必要な理由で）動的に作成されます。最も一般的な初
期化の方法ですリンクされたリストは実行時に表示されます。
code: C言語
struct fox *red_fox;
red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL);
red_fox->tail_length = 40;
red_fox->weight = 6;
red_fox->is_fantastic = false;
INIT_LIST_HEAD(&red_fox->list);
このコード、コンパイル時に構造体が静的に作成され、次のようになります。
code: C言語
struct fox red_fox = {
.tail_length = 40,
.weight = 6,
.list = LIST_HEAD_INIT(red_fox.list),
};
** 先頭リスト
code: C言語
static LIST_HEAD(fox_list);
これは、fox_list という名前で list_head を定義して初期化します。リンクされたリ
ストルーチンは、ヘッドノードまたはヘッドノードに実際のものを加えた1つまたは2つ
のパラメータを受け入れますリストノード。
** 連結リストの操作
カーネルは、連結リストを操作するための一連の関数を提供します。1 つまたは複数の
list_head 構造体に渡します。これらの関数は、インライン関数ジェネリック C であ
り、<linux / list.h>にあります。興味深いことに、これらの関数はすべて O(1) で
す。これは、それらが一定の時間内に実行されることを意味し、リストのサイズやその
他の入力にかかわらずたとえば、同じ金額リストに 3 または 3,000 があるかどうかに
関わらず、リストにエントリを追加または削除する時間これはおそらく驚くべきことで
はありませんが、まだ分かっています。
*** 連結リストへのノード追加
code: C言語
list_add(struct list_head *new, struct list_head *head)
この関数は、指定されたリストの先頭ノードへ新しいノードを追加します。
code: C言語
list_add(&f->list, &fox_list);
リストの最後に新しいノードを追加するには list_add_tail() を使用します。一般的
に、キューを実装する際に使用されます。# つまり、これが出てきたらキューの可能性
が高い？
code: C言語
list_add_tail(struct list_head *new, struct list_head *head)
*** 連結リストからのノード削除
連結リストからノードを削除するには、list_del() を使用します。
code: C言語
list_del(struct list_head *entry)
この関数は、要素のエントリをリストから削除します。その際、メモリの解放などは行
いません。また、構造体そのものを受け取ることもできません。単に特定のノードのポ
インタを変更するだけです。実行例は次のとおりです。
code: C言語
list_del(&f->list);
list_del の実装は次のとおりです。
code: C言語
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
カーネルでは list_del_init(struct list_head *entry) <include/linux/list.h> と
して実装されています。
*** 連結リストの移動と結合
- 他リストへのノード移動
code: C言語
list_move(struct list_head *list, struct list_head *head)
連結リストからのエントリを削除し、指定リストの先頭へ追加します
- 他リストの末尾へノード移動
code: C言語
list_move_tail(struct list_head *list, struct list_head *head)
list_move() と似た動作をしますが、リストの先頭に要素を挿入します
- リストが空かどうかチェック
code: C言語
list_empty(struct list_head *head)
空なら非0、それ以外は0を返します
- 2つのリストを結合
code: C言語
list_splice(struct list_head *list, struct list_hea *head)
2つのリストを結合します。指定リストを頭の後に追加します
- 2つのリストを結合し、古いリストを初期化
code: C言語
list_splice_init(struct list_head *list, struct list_head *head)
list_splice() と似た動作をしますが、listが指す空のリストは再初期化されます。
# __ 付きの関数について
# __ 付きの関数は内部関数です。一般的にラッパー関数と同じ名前が使われます。こう
# することで、ラッパー関数を外部で使っている処理への影響を無くせます？？。たと
# えば、list_add() は __list_add() を使っていますが、これがたんに list_add() だ
# けだったとして、名前が不適切ということで、変更された場合 list_add() を使用し
# ている個所をすべて修正する必要があります。内部関数を使用していれば、変更する
# 個所はとても少なく済みます。
** 連結リストへのアクセス
いままでで、連結リストの定義、初期化、操作の方法が分かりました。しかし、データ
へはアクセスできないと意味がありません。
*** 基本的なアプローチ
リストを反復する最も基本的な方法は、list_for_each() マクロを使用することです。
このマクロは2つの引数をとります。1つ目は現在のエントリ、2つ目は反復させたい
list_head 型 list の先頭ノードを指定します。
code: C言語
struct list_head *p;
list_for_each(p, fox_list) {
/* p points to an entry in the list */
}
リスト構造体へのポインタは通常良くありません。我々はlist_head を含む構造体への
ポインタが必要です。たとえば、前の fox 構造体の例では、リストへのポインタでは
なく、各 fox へのポインタが必要です。メンバーは構造体内にあります。先ほど説明
した list_entry() マクロを使うことができます。指定された list_head を含む構造
体を取得します。
code: C言語
struct list_head *p;
struct fox *f;
list_for_each(p, &fox_list) {
/* f points to the structure in which the list is embedded */
f = list_entry(p, struct fox, list)
}
*** 使用可能なアプローチ
これまでのアプローチでは、特に直感的で洗練されたコードは作成されませんが
list_head ノードの機能を説明しています。したがって、ほとんどのカーネルコードで
は、list_for_each_entry() マクロを使用して、リンクされたリストを反復処理しま
す。このマクロは、list_entry() によって実行され、リストの反復を単純化します。
code: C言語
list_for_each_entry(pos, head, member)
pos は、特定のオブジェクトを指すポインターで、list_head ノードに含まれていま
す。list_entry() からの戻り値 head はlist_head ヘッドノードへのポインタです。
先ほどの例では、fox_list を反復処理したいと思っています。 member は変数です
この例では、pos-list の list_head構造体の名前です。これは混乱しますが、使いや
すいです。以前の list_for_each() をすべての Fox ノードを反復処理します。
code: C言語
struct fox *f;
list_for_each_entry(f, &fox_list, list) {
/* on each iteration, ‘f’ points to the next fox structure ... */
}
次に、カーネルのファイルシステム通知システムである inotify の実際の例を見てみま
しょう。
code: C言語
static struct inotify_watch *inode_find_handle(struct inode *inode,
struct inotify_handle *ih)
{
struct inotify_watch *watch;
list_for_each_entry(watch, &inode->inotify_watches, i_list) {
if (watch->ih == ih)
return watch;
}
return NULL;
}
この関数は、inode->inotify_watches リストの全エントリを反復処理します。各エン
トリは、struct inotify_watch 型であり、メンバの list_head には i_list という名
前が付けられています。ループが繰り返されるたびに、リスト内の新しいノードにポイ
ントが表示されます。この単純な関数の目的は、提供された inode 構造体の
inotify_watches リストを検索することです inotify_handle が指定されたハンドルと
一致する inotify_watch エントリを検索します。
*** 連結リストへの逆順アクセス
逆順アクセスには list_for_each_entry_reverse() を使用します。これは逆順にアク
セスするという点を除き、list_for_each_entry() と同じ動作をします。
code: C言語
list_for_entry_reverse(pos, head, member)
逆順にリストへアクセスすることのメリットの1つはパフォーマンスです。たとえば、
検索対象のアイテムがノードの後ろにある可能性が高い場合、後ろから検索した方が
効率が良いのは明白です。たとえば、LIFO(Last In First Out)など。
*** 削除の反復処理
標準のリスト反復メソッドは、反復処理中にリストからエントリを削除する場合は適切
ではありません。標準のメソッドは、リストエントリがそのエントリの下から変更され
ていないという事実に依存しており、したがって、後続の反復は次の（または前の）ポ
インタに進むことができません。これはループ内の一般的なパターンであり、プログラ
マは潜在的な削除操作の前に一時変数に次の（または前の）ポインタを格納することに
よって解決します。 Linuxカーネルは、この状況を処理するルーチンを提供します。
code: C言語
list_for_each_entry_safe(pos, next, head, member)
このバージョンは list_for_each_entry() と同じ方法で使用します。ただし、pos と同
じ型の次のポインタを指定する点が異なります。list_for_each_entry_safe() マクロ
は次のポインタを使用してリストに次のエントリを格納し、現在のエントリを安全に削
除できます。再び inotify の例を考えてみましょう：
code: C言語
void inotify_inode_is_dead(struct inode *inode)
{
struct inotify_watch *watch, *next;
mutex_lock(&inode->inotify_mutex);
list_for_each_entry_safe(watch, next, &inode->inotify_watches, i_list) {
struct inotify_handle *ih = watch->ih;
mutex_lock(&ih->mutex);
inotify_remove_watch_locked(ih, watch); /* deletes watch */
mutex_unlock(&ih->mutex);
}
mutex_unlock(&inode->inotify_mutex);
}
この関数は inotify_watches リスト内の全ての項目を繰り返し処理して削除します。も
し、list_for_each_entry() を使用した場合、このコードでは、解放済メモリ使用(use-
after-free)バグが発生します。リスト内の次の項目に移動すると、watch にアクセス
する必要があり、そうすると破壊されます。
連結リストを反復して逆に要素を削除する必要がある場合に備えて、カーネルは
list_for_each_entry_safe_reverse（）を提供します。
code: C言語
list_for_each_entry_safe_reverse(pos, n, head, member) or
list_for_each_entry_safe(pos, n, head, member)
list_for_each_entry() の "安全な"変種は、ループ本体内のリストからの削除からの
みあなたを保護します。他のコードからの並行削除の可能性がある場合や他の形式の同
時リスト操作の場合は、リストへのアクセスを適切にロックする必要があります。同期
とロックについては、第9章「カーネル同期の概要」と第10章「カーネル同期方法」を
参照してください。
------------------------------------------------------------------------------
* Queues(キュー)
** kfifo
** キューの作成
** エンキューデータ
** デキューデータ
** キューサイズの取得
** キューのリセットと破棄
** キューの使いどころ
* Maps(マップ)
* Binary trees(2分木)