本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
前回を読んでいない方はこちらからどうぞ．
Linuxカーネルの記事一覧はこちらからどうぞ．
LinuxカーネルはC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
今回のテーマは，「カーネルのデータ構造」です．
以下のデータ構造を理解していることを前提とします．
カーネルのデータ構造
カーネルのデータ構造は，Linuxカーネルで利用されているデータの集まりの形式化された構成のことです．
カーネルのデータ構造を理解すると，Linuxカーネルがどのように構成されているのか読み解くことができます．
具体的には，以下のデータ構造を解説します．
リスト
リーナス・トーバルズの見解
2016年2月にカナダのバンクーバーで開催されたTED2016で，Linuxの創始者「リーナス・トーバルズ」がカーネルのデータ構造に関して語る動画です．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next = entry->next; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
remove_list_entry(entry) { // The "indirect" pointer points to the // *address* of the thing we'll update indirect = &head; // Walk the list, looking for the thing that // points to the entry we want to remove while ((*indirect) != entry) indirect = &(*indirect)->next; // .. and just remove it *indirect = entry->next; } |
14:27で，上記の2つのコードに関してリーナス・トーバルズは以下のように語っています．
I think this is an example of not particularly good taste in code, and this one is better taste, which one can immediately see.
コードのセンスが特に良くない例（最初のremove_list_entry）で，こちら（2番目のremove_list_entry）の方がセンスが良いのはすぐにわかると思います．
https://www.youtube.com/watch?v=Vo9KPk-gqKk
また，2006年7月にリーナス・トーバルズはLWN.netで以下の内容のメールを送っています．
データ構造の理解が重要であることがわかります．
I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code and his data structures more important. Bad programmers worry about the code, Good programmers worry about data structures and their relationships.
私は実際，悪いプログラマーと良いプログラマーの違いは，コードとデータ構造のどちらを重要視するかだと主張することにしています．ダメなプログラマーはコードを気にし，優秀なプログラマーはデータ構造とその関係を気にします．https://lwn.net/Articles/193245/
動画内でデータ構造として話題に上がったリストを知りたいあなたはこちらからどうぞ．
Linuxカーネルの双方向循環リスト
上図にLinuxカーネルの双方向循環リストを示します．
Linuxカーネルの双方向循環リストの特徴は以下になります．
- HEADから開始し，HEADで終了する．
- 空の場合，HEADはNULLではない．
- HEADのprevとnextはHEADを指す．
- HEADはデータが格納されない番兵ノードとなります．
- リストの末尾に新しい要素を挿入するのが簡単です．
- NULLを扱うための例外的なケースは存在しません．
また，Linuxカーネルの双方向循環リストは，一般的なデザインと以下の2つが異なります．
- 構造体の中にリンクリストのノードを埋め込む．
- 番兵ノードをリストヘッダとして利用する．
linux/include/linux/types.hにLinuxカーネルの双方向循環リストの定義であるstruct list_head構造体があります．
struct list_head構造体は，ノードのデータ型に依存しない汎用的なデザインになっていることがわかります．
|
1 2 3 |
struct list_head { struct list_head *next, *prev; }; |
また，struct list_head構造体に格納されているノードからデータを取得するマクロは以下になります．
- list_entryマクロ
- 指定したエントリ（ノード）の構造体のポインタをリストから取得する．
- linux/include/linux/list.hで定義されている．
- container_ofマクロ
- list_entryマクロの実体として定義されている．
- linux/include/linux/kernel.hで定義されている．
- offsetofマクロ
- 構造体のメンバのオフセットを取得する．
- linux/include/linux/stddef.hで定義されている．
|
1 2 3 4 5 6 7 8 |
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); }) |
|
1 2 3 4 5 |
#ifdef __compiler_offsetof #define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER) #else #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) #endif |
linux/include/linux/list.hで定義されているリストを\(\mathcal{O}(1)\)の計算量で操作する主な関数は以下になります．
- list_add関数：エントリをリストに追加する．
- list_add_tail関数：エントリをリストの最後に追加する．
- list_del関数：エントリをリストから削除する．
- list_move関数：エントリをリストから削除し，新しいリストに追加する．
- list_move_tail関数：エントリをリストから削除し，新しいリストの最後に追加する．
- list_empty関数：リストが空かどうかチェックする．
- list_splice関数：リストを結合する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } /** * list_del - deletes entry from list. * @entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */ static inline void list_del(struct list_head *entry) { __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } /** * list_move - delete from one list and add as another's head * @list: the entry to move * @head: the head that will precede our entry */ static inline void list_move(struct list_head *list, struct list_head *head) { __list_del_entry(list); list_add(list, head); } /** * list_move_tail - delete from one list and add as another's tail * @list: the entry to move * @head: the head that will follow our entry */ static inline void list_move_tail(struct list_head *list, struct list_head *head) { __list_del_entry(list); list_add_tail(list, head); } /** * list_empty - tests whether a list is empty * @head: the list to test. */ static inline int list_empty(const struct list_head *head) { return READ_ONCE(head->next) == head; } /** * list_splice - join two lists, this is designed for stacks * @list: the new list to add. * @head: the place to add it in the first list. */ static inline void list_splice(const struct list_head *list, struct list_head *head) { if (!list_empty(list)) __list_splice(list, head, head->next); } |
linux/include/linux/list.hで定義されているリストを\(\mathcal{O}(n)\)の計算量（nはエントリ数）でイテレーションする主なマクロは以下になります．
- list_for_eachマクロ：リストを反復する．
- list_for_each_entryマクロ：与えられた型のリストを反復する．
- list_for_each_entry_reverseマクロ：与えられた型のリストを後方から反復する．
- list_for_each_safeマクロ：リストのエントリを削除しても安全な状態で，リストを反復する．
- list_for_each_entry_safeマクロ：リストのエントリを削除しても安全な状態で，与えられた型のリストを反復する．
- list_for_each_entry_safe_reverseマクロ：リストのエントリを削除しても安全な状態で，与えられた型のリストを後方から反復する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) /** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member)) /** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member)) /** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */ #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) /** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member), \ n = list_next_entry(pos, member); \ !list_entry_is_head(pos, head, member); \ pos = n, n = list_next_entry(n, member)) /** * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate backwards over list of given type, safe against removal * of list entry. */ #define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member), \ n = list_prev_entry(pos, member); \ !list_entry_is_head(pos, head, member); \ pos = n, n = list_prev_entry(n, member)) |
Linuxカーネルの双方向循環リストの利用例は以下になります．
なので，リストの操作は理解しておきましょう！
- 同じ親PIDのスレッドのリスト
- ファイルシステムのスーパーブロックのリスト
- その他多数
ハッシュテーブル
Linuxカーネルのハッシュテーブルの特徴は以下になります．
- シンプルな固定サイズのハッシュチェイン法
- バケット配列のサイズは初期化時に\(2^N\)として固定
- 各バケットにはハッシュの衝突を解決するための片方向リストを保持
- 時間計算量
- \(\mathcal{O}(1)\)：衝突がない場合
- \(\mathcal{O}(n)\)：衝突がある場合
ハッシュテーブルの実装方法であるハッシュチェイン法とオープンアドレス法を知りたいあなたはこちらからどうぞ．
linux/include/linux/types.hにLinuxカーネルのハッシュテーブルの定義であるstruct hlist_head構造体とノードの定義であるstruct hlist_node構造体があります．
|
1 2 3 4 5 6 7 |
struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; |
また，linux/include/linux/hashtable.hにハッシュテーブルを操作する主なマクロの定義や関数の宣言があります．
- DEFINE_HASHTABLEマクロ：ハッシュテーブルの変数を定義する．
- hash_initマクロ：ハッシュテーブルを初期化する．
- hash_addマクロ：ハッシュテーブルにオブジェクトを追加する．
- hash_for_eachマクロ：ハッシュテーブルを反復する．
- hash_for_each_possibleマクロ：同じバケットでハッシュテーブルに格納されている全てのオブジェクトを反復する．
- hash_del関数：ハッシュテーブルからオブジェクトを削除する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#define DEFINE_HASHTABLE(name, bits) \ struct hlist_head name[1 << (bits)] = \ { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT } /** * hash_init - initialize a hash table * @hashtable: hashtable to be initialized * * Calculates the size of the hashtable from the given parameter, otherwise * same as hash_init_size. * * This has to be a macro since HASH_BITS() will not work on pointers since * it calculates the size during preprocessing. */ #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable)) /** * hash_add - add an object to a hashtable * @hashtable: hashtable to add to * @node: the &struct hlist_node of the object to be added * @key: the key of the object to be added */ #define hash_add(hashtable, node, key) \ hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]) /** * hash_for_each - iterate over a hashtable * @name: hashtable to iterate * @bkt: integer to use as bucket loop cursor * @obj: the type * to use as a loop cursor for each entry * @member: the name of the hlist_node within the struct */ #define hash_for_each(name, bkt, obj, member) \ for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\ (bkt)++)\ hlist_for_each_entry(obj, &name[bkt], member) /** * hash_for_each_possible - iterate over all possible objects hashing to the * same bucket * @name: hashtable to iterate * @obj: the type * to use as a loop cursor for each entry * @member: the name of the hlist_node within the struct * @key: the key of the objects to iterate over */ #define hash_for_each_possible(name, obj, member, key) \ hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member) |
Linuxカーネルのハッシュテーブルの利用例は以下になります．
- 透過的なヒュージページ（Transparent Hugepage）
- CPU毎のホットプラグの状態保存
赤黒木
赤黒木は，平衡二分木の一種で，主に連想配列の実装に利用されています．
赤黒木の特徴は以下になります．
- ノード：赤か黒
- リーフ（葉）：黒かNO DATA
また，赤黒木のデータ構造を変更した場合，あるノードからその葉の一つまでの経路には，他の葉への最短経路と同じ数の黒ノードが含まれます．
赤黒木は時間計算量\(\mathcal{O}(\log n)\)で，データの挿入，検索，削除が可能です．
赤黒木を知りたいあなたはこちらからどうぞ．
linux/include/linux/rbtree_types.hにLinuxカーネルの赤黒木の定義があります．
- struct rb_node構造体：赤黒木のノード
- struct rb_root構造体：赤黒木のルート（根）
- RB_ROOTマクロ：struct rb_node構造体をNULLに初期化する．
|
1 2 3 4 5 6 7 8 9 10 11 12 |
struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */ struct rb_root { struct rb_node *rb_node; }; #define RB_ROOT (struct rb_root) { NULL, } |
また，linux/include/linux/rbtree.hにLinuxカーネルの赤黒木のデータにアクセスするマクロや操作関数があります．
- rb_parentマクロ：指定したノードの構造体の親ノードのポインタを赤黒木から取得する．
- rb_entryマクロ：指定したノードの構造体のポインタを赤黒木から取得する．
- rb_next関数：次のノードのポインタを赤黒木から取得する．
- rb_prev関数：前のノードのポインタを赤黒木から取得する．
- rb_first関数：最初のノードのポインタを赤黒木のルートから取得する．
- rb_last関数：最後のノードのポインタを赤黒木のルートから取得する．
- rb_link_node関数：ノードのリンクを親の情報から設定する．
- rb_insert_color関数：ノードを赤黒木に追加する．
- rb_erase関数：ノードを赤黒木から削除する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) #define rb_entry(ptr, type, member) container_of(ptr, type, member) /* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_next(const struct rb_node *); extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; *rb_link = node; } extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); |
Linuxカーネルの赤黒木の利用例はCompletely Fair Scheduler（CFS）になります．
赤黒木とCFSの関係は，こちらの動画がわかりやすいです．
Linuxカーネルのデータ構造のデザインパターン
Linuxカーネルのデータ構造のデザインパターンの特徴は以下になります．
- データ構造のポインタを埋め込んでいること
- list_head，hlist_node，rb_nodeが実例
- プログラマは，構造体内のフィールドの配置を完全に制御することができる．
- キャッシュの利用率を上げるために，重要なフィールドを近くに配置する必要がある場合，プログラマは構造体内のフィールドの配置を完全に制御できる．
- 複数のlist_headフィールドを持つだけで，1つの構造体を2つ以上のリスト上に独立に配置できる．
- container_of，list_entry，rb_entryは，埋め込みデータ構造を取得するために利用できる．
- 汎用サービスのための完全なソリューションではなく，ツールボックスであること
- 一般的なサービスに対して完全なソリューションを提供するのではなく，カスタムソリューションを構築するために使用できるツール群を提供することが最善である場合が多い．
- Linuxカーネルのリスト，ハッシュテーブル，rbtreeはどれも検索機能を備えていないので，与えられた低レベルプリミティブを使って自分で構築する必要がある．
- 呼び出し側でロックする必要があること
- 疑問がある場合は，呼び出される側ではなく，呼び出し側でロックを行います．こうすることで，関数のクライアントがより多くの制御を行えるようになります．
Radix Tree（マークルパトリシア木）
Radix Tree（マークルパトリシア木）は，あるノードの配下の全ノードは，自身に対応する文字列に共通するプレフィックス（接頭部）があり，ルート（根）には空の文字列が対応している順序付き木です．
Radix Treeを知りたいあなたはこちらからどうぞ．
LinuxカーネルのRadix Treeは，以下の特徴があります．
- unsigned long型とvoid *型をマッピングする．
- 各々のノードは64スロットを持つ．
- スロットは，キーの6ビット（\(2^6 = 64\)）部分でインデックスする．
- 葉では，スロットはデータのアドレスを指す．
- 葉でないノードでは，スロットは下位レイヤの別のノードを指す．
- その他のメタデータも各ノードで保存される．
- 例：タグ，親ノードのポインタ，親ノードのオフセット等
linux/include/linux/radix-tree.hにLinuxカーネルのRadix Treeの定義であるstruct radix_tree_root構造体やstruct radix_tree_node構造体があります．
|
1 2 3 |
/* Keep unconverted code working */ #define radix_tree_root xarray #define radix_tree_node xa_node |
Radix Treeの実装には後述するXArrayを利用していて，上記のマクロによりstruct radix_tree_root構造体はstruct xarray構造体，struct radix_tree_node構造体はstruct xa_node構造体として定義されます．
LinuxカーネルのRadix Treeの主な操作マクロ・関数は以下になります．
- RADIX_TREEマクロ：Radix Treeのルート変数の定義と初期化する．
- INIT_RADIX_TREEマクロ：Radix Treeのルートを実行中に初期化する．
- RADIX_TREE_INITマクロ：Radix Treeのノード変数を初期化する．
- radix_tree_insert関数：Radix Treeにアイテムを追加する．
- radix_tree_preload関数：次のRadix Treeにアイテムを追加が失敗しないように，十分なメモリを割り当てる．
- radix_tree_delete関数：ルートのRadix Treeからエントリを削除する．
- radix_tree_lookup関数：Radix Treeで検索する．
- radix_tree_lookup_slot関数：Radix Treeのスロットを検索する．
- radix_tree_gang_lookup関数：Radix Treeで複数回検索する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#define RADIX_TREE(name, mask) \ struct radix_tree_root name = RADIX_TREE_INIT(name, mask) #define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask) #define RADIX_TREE_INIT(name, mask) XARRAY_INIT(name, mask) int radix_tree_insert(struct radix_tree_root *, unsigned long index, void *); int radix_tree_preload(gfp_t gfp_mask); void *radix_tree_delete(struct radix_tree_root *, unsigned long); void *radix_tree_lookup(const struct radix_tree_root *, unsigned long); void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *, unsigned long index); unsigned int radix_tree_gang_lookup(const struct radix_tree_root *, void **results, unsigned long first_index, unsigned int max_items); |
ここで，Linuxカーネルの赤黒木ではタグというツリー内のアイテムに特定のビットを設定することで目印をつけることができます．
例えば，Dirty状態またはWrite Back中のメモリページの状態のアイテムにタグを設定することで高速に検索することが可能になります．
タグの主な操作関数は以下になります．
- radix_tree_tag_set関数：Radix Treeのノードのタグを設定する．
- radix_tree_tag_clear関数：Radix Treeのノードのタグを消去する．
- radix_tree_tag_get関数：Radix Treeのノードのタグを取得する．
- radix_tree_tagged関数：Radix Tree内のアイテムがタグ付けされているかどうかチェックする．
|
1 2 3 4 5 6 7 |
void *radix_tree_tag_set(struct radix_tree_root *, unsigned long index, unsigned int tag); void *radix_tree_tag_clear(struct radix_tree_root *, unsigned long index, unsigned int tag); int radix_tree_tag_get(const struct radix_tree_root *, unsigned long index, unsigned int tag); int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag); |
Radix Treeの解説動画はこちらがわかりやすいです．
XArray
XArrayは，非常に大きなポインタの配列のように振る舞う抽象データ型です．
XArrayが格納するデータ型はunsigned long型です．
XArrayは，ハッシュや従来のサイズ変更可能な配列と同じニーズを多く満たしています．
ハッシュとは異なり，キャッシュを効率的に使って次のエントリや前のエントリに移動することができます．
サイズを変更可能な配列とは対照的に，配列を大きくするためにデータをコピーしたり，MMUマッピングを変更したりする必要はありません．
2重連結リストよりもメモリ効率が高く，並列化可能で，キャッシュに優しい設計です．
また，Read Copy Update（RCU）の利点を生かし，ロックせずに検索を実行できます．
XArrayは，Linuxカーネルのバージョン4.19にメインラインにマージされ，主にLinuxカーネルのRadix Treeのためのラッパー関数として利用されます．
XArrayのエントリ（ノード）は，多くとも3つのタグビット（get/set/clear）を持ちます．（XArrayではマークとも呼ばれます．）
linux/include/linux/xarray.hに，XArrayの定義であるstruct xarray構造体とstruct xa_node構造体があります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/** * struct xarray - The anchor of the XArray. * @xa_lock: Lock that protects the contents of the XArray. * * To use the xarray, define it statically or embed it in your data structure. * It is a very small data structure, so it does not usually make sense to * allocate it separately and keep a pointer to it in your data structure. * * You may use the xa_lock to protect your own data structures as well. */ /* * If all of the entries in the array are NULL, @xa_head is a NULL pointer. * If the only non-NULL entry in the array is at index 0, @xa_head is that * entry. If any other entry in the array is non-NULL, @xa_head points * to an @xa_node. */ struct xarray { spinlock_t xa_lock; /* private: The rest of the data structure is not to be used directly. */ gfp_t xa_flags; void __rcu * xa_head; }; /* * @count is the count of every non-NULL element in the ->slots array * whether that is a value entry, a retry entry, a user pointer, * a sibling entry or a pointer to the next level of the tree. * @nr_values is the count of every element in ->slots which is * either a value entry or a sibling of a value entry. */ struct xa_node { unsigned char shift; /* Bits remaining in each slot */ unsigned char offset; /* Slot offset in parent */ unsigned char count; /* Total entry count */ unsigned char nr_values; /* Value entry count */ struct xa_node __rcu *parent; /* NULL at top of tree */ struct xarray *array; /* The array we belong to */ union { struct list_head private_list; /* For tree user */ struct rcu_head rcu_head; /* Used when freeing node */ }; void __rcu *[XA_CHUNK_SIZE]; union { unsigned long tags[XA_MAX_MARKS][XA_MARK_LONGS]; unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS]; }; }; |
また，XArrayの操作関数は以下になります．
- DEFINE_XARRAYマクロ：XArrayを初期化する．
- xa_load関数：XArrayから値を取得する．
- xa_store関数：XArrayに値を格納する．
- xa_erase関数：XArrayの値を削除する．
- xa_cmpxchg関数：XArrayの現在の値が古い値の場合，新しい値に交換する．
- xa_get_mark関数：マークを取得する．
- xa_set_mark関数：マークを設定する．
- xa_clear_mark関数：マークをクリアする．
- xa_for_eachマクロ：XArrayのノードを反復する．
- xa_for_each_markedマクロ：XArrayのマークされたノードを反復する．
|
1 2 3 4 5 6 7 8 9 10 |
/** * DEFINE_XARRAY() - Define an XArray. * @name: A string that names your XArray. * * This is intended for file scope definitions of XArrays. It declares * and initialises an empty XArray with the chosen name. It is equivalent * to calling xa_init() on the array, but it does the initialisation at * compiletime instead of runtime. */ #define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0) |
XArrayの利用例は以下になります．
- Radix Tree
- アドレス空間の管理
XArrayの解説動画はこちらがわかりやすいです．
ビットマップ
ビットマップは，1つまたは複数の符号なし整数型のビット配列です．
Linuxカーネルのビットマップはunsigned long型で定義されています．
ビットマップのメリットは以下になります．
- ビットをコンパクトに格納でき，メモリを節約できること
- ハードウェアのビットレベルの並列性を利用して演算を高速に実行できること
linux/include/linux/types.hにあるビットマップのマクロは以下になります．
- DECLEARE_BITMAPマクロ：ビットマップを定義する．
|
1 2 |
#define DECLARE_BITMAP(name,bits) \ unsigned long name[BITS_TO_LONGS(bits)] |
linux/include/asm-generic/bitops/instrumented-atomic.hに以下のビットマップの操作関数が定義されています．
- set_bit関数：ビットを1に設定する．
- clear_bit関数：ビットを0にクリアする．
- change_bit関数：ビットを反転する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/** * set_bit - Atomically set a bit in memory * @nr: the bit to set * @addr: the address to start counting from * * This is a relaxed atomic operation (no implied memory barriers). * * Note that @nr may be almost arbitrarily large; this function is not * restricted to acting on a single-word quantity. */ static inline void set_bit(long nr, volatile unsigned long *addr) { instrument_atomic_write(addr + BIT_WORD(nr), sizeof(long)); arch_set_bit(nr, addr); } /** * clear_bit - Clears a bit in memory * @nr: Bit to clear * @addr: Address to start counting from * * This is a relaxed atomic operation (no implied memory barriers). */ static inline void clear_bit(long nr, volatile unsigned long *addr) { instrument_atomic_write(addr + BIT_WORD(nr), sizeof(long)); arch_clear_bit(nr, addr); } /** * change_bit - Toggle a bit in memory * @nr: Bit to change * @addr: Address to start counting from * * This is a relaxed atomic operation (no implied memory barriers). * * Note that @nr may be almost arbitrarily large; this function is not * restricted to acting on a single-word quantity. */ static inline void change_bit(long nr, volatile unsigned long *addr) { instrument_atomic_write(addr + BIT_WORD(nr), sizeof(long)); arch_change_bit(nr, addr); } |
linux/include/linux/bitmap.hに以下のビットマップの操作関数が定義されています．
- bitmap_zero関数：ビットマップを0にクリアする．
- bitmap_fill関数：ビットマップを1に設定する．
|
1 2 3 4 5 6 7 8 9 10 11 |
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memset(dst, 0, len); } static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memset(dst, 0xff, len); } |
linux/include/asm-generic/bitops/find.hに以下のビットマップの操作関数が定義されています．
- find_first_bit関数：1に設定されている最初のビットを発見する．
- find_first_zero_bit関数：0にクリアされている最初のビットを発見する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
/** * find_first_bit - find the first set bit in a memory region * @addr: The address to start the search at * @size: The maximum number of bits to search * * Returns the bit number of the first set bit. * If no bits are set, returns @size. */ static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size) { if (small_const_nbits(size)) { unsigned long val = *addr & GENMASK(size - 1, 0); return val ? __ffs(val) : size; } return _find_first_bit(addr, size); } /** * find_first_zero_bit - find the first cleared bit in a memory region * @addr: The address to start the search at * @size: The maximum number of bits to search * * Returns the bit number of the first cleared bit. * If no bits are zero, returns @size. */ static inline unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) { if (small_const_nbits(size)) { unsigned long val = *addr | ~GENMASK(size - 1, 0); return val == ~0UL ? size : ffz(val); } return _find_first_zero_bit(addr, size); } |
linux/include/linux/bitops.hに以下のビットマップの操作関数が定義されています．
- for_each_set_bitマクロ：1に設定されている最初のビットを発見する操作を反復する．
- for_each_clear_bitマクロ：0にクリアされている最初のビットを発見する操作を反復する．
|
1 2 3 4 5 6 7 8 9 |
#define for_each_set_bit(bit, addr, size) \ for ((bit) = find_first_bit((addr), (size)); \ (bit) < (size); \ (bit) = find_next_bit((addr), (size), (bit) + 1)) #define for_each_clear_bit(bit, addr, size) \ for ((bit) = find_first_zero_bit((addr), (size)); \ (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) |
ビットマップの操作関数の自作を知りたいあなたはこちらからどうぞ．
ビットマップの利用例は以下になります．
- ホットプラグCPUをサポートするシステムのオンライン/オフラインプロセッサのセット
- Linuxカーネルの初期化時に割り当てられるIRQのセット
- ext2/3/4ファイルシステムにおける利用されていないinode/ディスクブロックの管理
CPUのホットプラグで動的にプロセッサを無効や有効にする方法を知りたいあなたはこちらからどうぞ．
まとめ
今回はカーネルとデータ構造を紹介しました．
具体的には，リスト，ハッシュテーブル，赤黒木，Radix Tree（マークルパトリシア木），XArray，ビットマップを解説しました．
Linuxカーネルのデータ構造を深く理解したいあなたは，以下の記事を読みましょう！
- Linux kernel design patterns - part 1，Linux kernel design patterns - part 2
- A generic hash table
- Hash Tables—Theory and Practice
- Relativistic hash tables, part 1: Algorithms，Relativistic hash tables, part 2: Implementation
- Trees I: Radix trees，Trees II: red-black trees
- Transparent Hugepage Support
- CFS Scheduler
- The XArray data structure
- XArray
- Bit arrays - Linux Inside
LinuxカーネルはC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
次回はこちらからどうぞ．
