TECHNOLOGY LINUX KERNEL

【第4回】元東大教員から学ぶLinuxカーネル「カーネルのデータ構造」

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

前回を読んでいない方はこちらからどうぞ.

第3回 Linuxカーネル
【第3回】元東大教員から学ぶLinuxカーネル「アイソレーションとシステムコール」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマは,「アイソレーションとシステムコール」です. アイソレーションとシ ...

続きを見る

Linuxカーネルの記事一覧はこちらからどうぞ.

Linuxカーネル
元東大教員から学ぶLinuxカーネル

こういった私から学べます. Linuxカーネルとは,C言語で開発されたオープンソースのOSです. Linuxカーネルは主に以下のコンピュータで広く利用されています. スーパーコンピュータ サーバ An ...

続きを見る

今回のテーマは,「カーネルのデータ構造」です.

以下のデータ構造を理解していることを前提とします.

C言語 リスト
【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】

こういった悩みにお答えします. こういった私から学べます. 目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例:Linuxカーネル3. ...

続きを見る

C言語 ハッシュテーブル
【C言語】ハッシュテーブルとは【ハッシュチェイン法,オープンアドレス法】

こういった悩みにお答えします. こういった私から学べます. 目次1 ハッシュテーブル(ハッシュ表)2 ハッシュチェイン法(オープンハッシュ法)3 オープンアドレス法(クローズドハッシュ法)4 まとめ ...

続きを見る

C言語 キュー
【C言語】キューとは【FIFOキュー,優先度キュー,二項ヒープ,赤黒木】

こういった悩みにお答えします. こういった私から学べます. 目次1 【C言語】キューとは2 FIFOキュー3 優先度キュー4 二項ヒープ5 赤黒木6 まとめ 【C言語】キューとは キューとは,データを ...

続きを見る

C言語 マークル木 マークルパトリシア木
【C言語】マークル木とマークルパトリシア木【ビットコインとイーサリアムで利用】

こういった悩みにお答えします. こういった私から学べます. 本記事では,ハッシュテーブルを理解していることを前提とします. 目次1 マークル木(マークルハッシュ木,ハッシュ木)【ビットコインで利用】2 ...

続きを見る

C言語 ビット/シフト 応用
【C言語】ビット演算とシフト演算の応用:回転,セット/クリア,スキャン,カウント【x86-64/ARM64命令のコード】

こういった悩みにお答えします. こういった私から学べます. 目次1 C言語でビット演算とシフト演算の応用2 ビットの回転3 ビットのセット/クリア4 ビットのスキャン4.1 ビットをスキャンする関数4 ...

続きを見る

カーネルのデータ構造

カーネルのデータ構造は,Linuxカーネルで利用されているデータの集まりの形式化された構成のことです.

カーネルのデータ構造を理解すると,Linuxカーネルがどのように構成されているのか読み解くことができます.

具体的には,以下のデータ構造を解説します.

リスト

リーナス・トーバルズの見解

2016年2月にカナダのバンクーバーで開催されたTED2016で,Linuxの創始者「リーナス・トーバルズ」がカーネルのデータ構造に関して語る動画です.

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/

動画内でデータ構造として話題に上がったリストを知りたいあなたはこちらからどうぞ.

C言語 リスト
【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】

こういった悩みにお答えします. こういった私から学べます. 目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例:Linuxカーネル3. ...

続きを見る

Linuxカーネルの双方向循環リスト

double circular linked list in linux kernel

上図に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構造体は,ノードのデータ型に依存しない汎用的なデザインになっていることがわかります.

また,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で定義されている.

linux/include/linux/list.hで定義されているリストを\(\mathcal{O}(1)\)の計算量で操作する主な関数は以下になります.

linux/include/linux/list.hで定義されているリストを\(\mathcal{O}(n)\)の計算量(nはエントリ数)でイテレーションする主なマクロは以下になります.

Linuxカーネルの双方向循環リストの利用例は以下になります.

なので,リストの操作は理解しておきましょう!

  • 同じ親PIDのスレッドのリスト
  • ファイルシステムのスーパーブロックのリスト
  • その他多数

ハッシュテーブル

Linuxカーネルのハッシュテーブルの特徴は以下になります.

  • シンプルな固定サイズのハッシュチェイン法
  • バケット配列のサイズは初期化時に\(2^N\)として固定
  • 各バケットにはハッシュの衝突を解決するための片方向リストを保持
  • 時間計算量
    • \(\mathcal{O}(1)\):衝突がない場合
    • \(\mathcal{O}(n)\):衝突がある場合

ハッシュテーブルの実装方法であるハッシュチェイン法とオープンアドレス法を知りたいあなたはこちらからどうぞ.

C言語 ハッシュテーブル
【C言語】ハッシュテーブルとは【ハッシュチェイン法,オープンアドレス法】

こういった悩みにお答えします. こういった私から学べます. 目次1 ハッシュテーブル(ハッシュ表)2 ハッシュチェイン法(オープンハッシュ法)3 オープンアドレス法(クローズドハッシュ法)4 まとめ ...

続きを見る

linux/include/linux/types.hにLinuxカーネルのハッシュテーブルの定義であるstruct hlist_head構造体とノードの定義であるstruct hlist_node構造体があります.

また,linux/include/linux/hashtable.hにハッシュテーブルを操作する主なマクロの定義や関数の宣言があります.

  • DEFINE_HASHTABLEマクロ:ハッシュテーブルの変数を定義する.
  • hash_initマクロ:ハッシュテーブルを初期化する.
  • hash_addマクロ:ハッシュテーブルにオブジェクトを追加する.
  • hash_for_eachマクロ:ハッシュテーブルを反復する.
  • hash_for_each_possibleマクロ:同じバケットでハッシュテーブルに格納されている全てのオブジェクトを反復する.
  • hash_del関数:ハッシュテーブルからオブジェクトを削除する.

Linuxカーネルのハッシュテーブルの利用例は以下になります.

赤黒木

赤黒木は,平衡二分木の一種で,主に連想配列の実装に利用されています.

赤黒木の特徴は以下になります.

  • ノード:赤か黒
  • リーフ(葉):黒かNO DATA

また,赤黒木のデータ構造を変更した場合,あるノードからその葉の一つまでの経路には,他の葉への最短経路と同じ数の黒ノードが含まれます.

赤黒木は時間計算量\(\mathcal{O}(\log n)\)で,データの挿入,検索,削除が可能です.

赤黒木を知りたいあなたはこちらからどうぞ.

C言語 キュー
【C言語】キューとは【FIFOキュー,優先度キュー,二項ヒープ,赤黒木】

こういった悩みにお答えします. こういった私から学べます. 目次1 【C言語】キューとは2 FIFOキュー3 優先度キュー4 二項ヒープ5 赤黒木6 まとめ 【C言語】キューとは キューとは,データを ...

続きを見る

linux/include/linux/rbtree_types.hにLinuxカーネルの赤黒木の定義があります.

  • struct rb_node構造体:赤黒木のノード
  • struct rb_root構造体:赤黒木のルート(根)
  • RB_ROOTマクロ:struct rb_node構造体を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関数:ノードを赤黒木から削除する.

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を知りたいあなたはこちらからどうぞ.

C言語 マークル木 マークルパトリシア木
【C言語】マークル木とマークルパトリシア木【ビットコインとイーサリアムで利用】

こういった悩みにお答えします. こういった私から学べます. 本記事では,ハッシュテーブルを理解していることを前提とします. 目次1 マークル木(マークルハッシュ木,ハッシュ木)【ビットコインで利用】2 ...

続きを見る

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構造体があります.

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で複数回検索する.

ここで,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内のアイテムがタグ付けされているかどうかチェックする.

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構造体があります.

また,XArrayの操作関数は以下になります.

XArrayの利用例は以下になります.

  • Radix Tree
  • アドレス空間の管理

XArrayの解説動画はこちらがわかりやすいです.

ビットマップ

ビットマップは,1つまたは複数の符号なし整数型のビット配列です.

Linuxカーネルのビットマップはunsigned long型で定義されています.

ビットマップのメリットは以下になります.

  • ビットをコンパクトに格納でき,メモリを節約できること
  • ハードウェアのビットレベルの並列性を利用して演算を高速に実行できること

linux/include/linux/types.hにあるビットマップのマクロは以下になります.

linux/include/asm-generic/bitops/instrumented-atomic.hに以下のビットマップの操作関数が定義されています.

linux/include/linux/bitmap.hに以下のビットマップの操作関数が定義されています.

  • bitmap_zero関数:ビットマップを0にクリアする.
  • bitmap_fill関数:ビットマップを1に設定する.

linux/include/asm-generic/bitops/find.hに以下のビットマップの操作関数が定義されています.

  • find_first_bit関数:1に設定されている最初のビットを発見する.
  • find_first_zero_bit関数:0にクリアされている最初のビットを発見する.

linux/include/linux/bitops.hに以下のビットマップの操作関数が定義されています.

  • for_each_set_bitマクロ:1に設定されている最初のビットを発見する操作を反復する.
  • for_each_clear_bitマクロ:0にクリアされている最初のビットを発見する操作を反復する.

ビットマップの操作関数の自作を知りたいあなたはこちらからどうぞ.

C言語 ビット/シフト 応用
【C言語】ビット演算とシフト演算の応用:回転,セット/クリア,スキャン,カウント【x86-64/ARM64命令のコード】

こういった悩みにお答えします. こういった私から学べます. 目次1 C言語でビット演算とシフト演算の応用2 ビットの回転3 ビットのセット/クリア4 ビットのスキャン4.1 ビットをスキャンする関数4 ...

続きを見る

ビットマップの利用例は以下になります.

  • ホットプラグCPUをサポートするシステムのオンライン/オフラインプロセッサのセット
  • Linuxカーネルの初期化時に割り当てられるIRQのセット
  • ext2/3/4ファイルシステムにおける利用されていないinode/ディスクブロックの管理

CPUのホットプラグで動的にプロセッサを無効や有効にする方法を知りたいあなたはこちらからどうぞ.

C言語 get_nprocs関数
【C言語】Linuxのプロセッサ数を取得するget_nprocs_conf/get_nprocs関数の使い方【CPUのホットプラグ】

こういった悩みにお答えします. こういった私から学べます. 目次1 get_nprocs_conf/get_nprocs関数2 get_nprocs_conf/get_nprocs関数の使い方3 CP ...

続きを見る

まとめ

今回はカーネルとデータ構造を紹介しました.

具体的には,リスト,ハッシュテーブル,赤黒木,Radix Tree(マークルパトリシア木),XArray,ビットマップを解説しました.

Linuxカーネルのデータ構造を深く理解したいあなたは,以下の記事を読みましょう!

最後まで読んで頂きありがとうございました.

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

次回はこちらからどうぞ.

第5回Linuxカーネル
【第5回】元東大教員から学ぶLinuxカーネル「プロセス管理」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマはプロセス管理です. プロセス管理により,プロセスのライフサイクルが ...

続きを見る

-TECHNOLOGY, LINUX KERNEL
-, , , , , , ,