TECHNOLOGY LINUX KERNEL

【第13回】元東大教員から学ぶLinuxカーネル「ページキャッシュとページフォールト」

2022年10月11日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/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社で自分に合うスクールを見つけましょう.後悔はさせません!

今回のテーマはページキャッシュページフォールトです.

本記事を読むとページ,キャッシュ,メモリの関係がわかります.

キャッシュの背景:コンピュータの遅延

キャッシュの背景としてコンピュータの遅延が挙げられます.

下記にLatency numbers every programmer should knowに記載されているコンピュータの遅延を示します.

L1キャッシュの遅延0.5nsですが,カリフォルニアとオランダ間のパケットのRound-Trip Timeは150msになります.

人間で表現した場合(10億倍の遅延)は以下になります.

なぜキャッシュが必要なのかというと,ディスクアクセスはメモリアクセスに比べ数桁遅いからです.

また,一度アクセスしたデータは,近い将来に再びアクセスされる可能性が高いという「時間的局所性」の性質を利用することで,コンピュータの性能を向上させることができます.

ページキャッシュ(バッファキャッシュ

ページキャッシュ(バッファキャッシュ)は,ディスクの内容(ブロック)を保持するメモリ上の物理ページのことです.

ディスクはバッキングストアと呼ばれ,通常のファイル,メモリマップドファイル,ブロックデバイスのファイルに対して機能します.

バッキングストアとは,メモリのバックアップとしてディスク(HDD/SSD)に保存するファイルシステムの領域のことです.

これに対して,バッキングストアと似た概念であるスワップ領域とは,特殊なパーティションの1つで,メモリの容量の延長としてプログラムやデータを記録することができる領域のことです.

バッキングストアとスワップ領域の違いは「Swap Space vs Backing Store」で議論されています.

ページキャッシュは動的なサイズなので,カーネルやプロセスで使用されていない空きメモリを消費するためサイズを拡大したり,メモリの圧迫を緩和するために縮小したりします.

バッファードI/O操作(O_DIRECTなし)では,まずファイルのページキャッシュがチェックされます.

  • キャッシュヒット(cache hit):データがページキャッシュにある場合,ユーザメモリから/へコピーされます.
  • キャッシュミス(cache miss):そうでなければ,仮想ファイルシステムは具体的なファイルシステム(例:ext4)にディスクからデータを読み込むように要求します.つまり,読み取り/書き込み操作でページキャッシュにデータを入れます.

write caching policies

キャッシュのデータ更新ポリシーは以下になります(上図).

  • no write:書き込み操作をキャッシュしない.
  • write through:書き込み操作を即座にディスクに通す.キャッシュのコヒーレント性を保ち,キャッシュされたデータを無効化する必要がないためシンプルです.
  • write back:書き込み操作はページキャッシュを更新しますが,ディスクはすぐには更新されない「Linuxのページキャッシュポリシー」です.書き込まれたページは,radix treeのタグを使ってdirtyとマークされます.定期的にdirtyページをディスクに書き込むことがWrite Backです.ページキャッシュは時間的な局所性を吸収してディスクアクセスを削減します.マルチコア/メニーコアプロセッサで有用です.

キャッシュの追い出し(eviction)ポリシー

キャッシュの追い出し(eviction)ポリシーを紹介します.

キャッシュからデータを削除するタイミングは,より多くの空きメモリが必要(メモリ圧迫)な場合です.

どのデータをキャッシュから削除すべきかは,理想は将来アクセスされないキャッシュページを退避させることです.

キャッシュの追い出しポリシーは,どのキャッシュを追い出す(メモリに書き出す)のかを決めることです.

LRU(Least Recently Used)ポリシーは,各ページがいつアクセスされたかを記録し,最も古いタイムスタンプを持つページを追い出すポリシーです.

LRUポリシーの失敗例は,多くのファイルは一度アクセスされると二度とアクセスされない場合です.

LRUはこれらのファイルをLRUリストの先頭に置くので,最適ではないです.

LinuxのLRUは,以下の2つのリンクリスト(Two-List or LRU/2 Strategy)で管理します.

  • active list:アクティブリスト内のページがホット(hot)とみなされ,追い出し不可になります.
  • inactive list:非アクティブリスト内のページはコールド(cold)とみなされ,追い出し可能です.

新規にアクセスされたページはinactive listに追加されます.

inactive listに登録されたページが再びアクセスされた場合,active listに昇格されます.

ページがinactive listに移動されると,ページテーブルのアクセス権が削除されます.

active listがinactive listよりはるかに大きくなった場合,active listの先頭のアイテムはinactive listに戻されます.

ページがinactive listに追加されると,そのアクセスを追跡するために,ページテーブルのアクセス許可が無効になります.

address_space and vm_area_struct

linux/include/linux/fs.hのaddress_space構造体でページキャッシュに存在するエンティティ(実体)を管理します.

「アドレス空間 = ファイル = ファイルのページキャッシュにアクセス = 1つ以上のvm_area_struct構造体」になります(上図).

address_space構造体の主なメンバ変数は以下になります.

  • host : 対応するファイルのinodeへのポインタ
  • i_mmap : このアドレス空間に関するすべての共有マッピングおよびプライベートマッピング
  • nrpages : アドレス空間に含まれるページの総数
  • a_ops : アドレス空間での操作

linux/include/linux/fs.hのaddress_space_operations構造体でアドレス空間を操作します.

アドレス空間を操作する主な関数ポインタは以下になります.

  • writepage関数ポインタ:dirtyページをバッキングストアに書き込むために仮想メモリサブシステムから呼び出されます.
  • readpage関数ポインタ:バッキングストアからページを読み込むために仮想メモリサブシステムから呼び出されます.
  • writepages関数ポインタ:address_spaceオブジェクトに関連するページを書き出すために仮想メモリサブシステムによって呼び出されます.
  • set_page_dirty関数ポインタ:仮想メモリサブシステムがページをdirtyに設定するために呼び出されます.
  • readpages関数ポインタ:address_spaceオブジェクトに関連するページを読み込むために仮想メモリサブシステムによって呼び出されます.これは本質的にreadpageのベクターバージョンです.
  • readahead関数ポインタ:address_spaceオブジェクトに関連するページを読み込むために仮想メモリサブシステムによって呼び出されます.ページはページキャッシュに連続し,ロックされています.
  • write_begin関数ポインタ:汎用バッファの書き込みライトコードによって呼び出され,ファイルシステムに対して,ファイル内の与えられたオフセットにlenバイトを書き込む準備をするように要求します.
  • write_end関数ポインタ:write_begin関数ポインタの呼び出しが成功し,データのコピーが完了した後に呼び出されます.

参考:Multi-Gen LRU(MGLRU)

Multi-Gen LRU(MGLRU)は,グーグルが開発したLRUです.

MGLRUは,上述したLRU(baseline)より性能が数%~数十%程度も向上しています.

Linuxカーネルのバージョン6.1にMGLRUがメインラインにマージされるとのことです(2022年10月現在の最新版はバージョン6.0).

2022年9月12日に開催されたLPC 2022でMGLRUが発表されました.

以下の動画の2:10:38で観られます.

MGLRUの解説動画です.

メモリ管理との連携とページフォールト

メモリ管理との連携では,以下の構造体を利用します.

  • file/file_operations構造体:ファイルの内容にアクセスする方法
  • address_space/address_space_operations構造体:ファイルのページキャッシュにアクセスする方法
  • vm_area_struct/vm_operations_struct構造体:仮想メモリ領域のページフォールトの処理方法

file/file_operations構造体を知りたいあなたはこちらからどうぞ.

vm_area_struct/vm_operations_struct構造体を知りたいあなたはこちらからどうぞ.

ページフォールトとは,プロセスが適切な準備なしにメモリページにアクセスしたときにメモリ管理ユニット(MMU)が発生させる例外です.

ページにアクセスするには,プロセスの仮想アドレス空間にマッピングを追加する必要があります.

さらに,実際のページの内容をディスクなどのバッキングストアから読み込む必要がある場合もあります.

MMUはページフォルトを検出しますが,OSのカーネルは,必要なページを物理メモリでアクセスできるようにするか,不正なメモリアクセスを拒否することで例外を処理します.

Linuxカーネルにおけるページフォールトのエントリーポイントは,linux/mm/memory.cにあるhandle_pte_fault関数です.

どの仮想メモリ領域のフォールトアドレスに該当するかを特定し,仮想メモリ領域に登録されたフォールトハンドラがあるかどうかを確認します.

デフォルトのフォールトハンドラは以下になります.

  • do_anonymous_page関数:ページもファイルもないの場合
  • filemap_fault関数:ファイルにバックアップされたページの場合
  • do_wp_page関数:書き込み保護ページ(コピーオンライト,CoW:Copy-on-Write)の場合
  • do_swap_page関数:スワップによってバックアップされたページの場合

filemap_fault関数を呼び出す場合,ページテーブルエントリ(PTE:Page Table Entry)が存在しない場合(パーミッションは「---」)に呼び出されます.

しかし,仮想メモリ領域はアクセス可能(例:パーミッションは「rwx」)とマークされ,関連するファイル(vm_file)を保持しています.

ページフォルトハンドラが違いを認識します.

ファイルのページキャッシュを検索し,キャッシュにヒットした場合,キャッシュのページをマップします.

そうでなければ,「mapping->a_ops->readpage(file, page)」を実行します.

do_wp_page関数を呼び出す場合,ページテーブルエントリが書き込み不可とマークされています(例:r--).

しかし,仮想メモリ領域は書き込み可能としてマークされている(例:rw-).

ページフォルトハンドラはその違いに認識し,CoWを意味するため,物理ページの複製を作成します.

そして,ページテーブルエントリを更新し,TLBエントリをフラッシュします.

Flusher Daemon

Flusher Daemonは,複数のスレッドがページキャッシュからディスクにdirtyページを同期することです.

書き込み動作が遅延していて,データがdirtyとマークされている状態,つまりメモリのデータが記憶媒体と同期していない状態の場合,dirtyページのwrite backは以下の条件で発生します.

  • 空きメモリが少なくなり,ページキャッシュを縮小する必要がある場合
  • dirtyデータが特定のスレッショルドより古くなる場合
  • ユーザプロセスがsync関数またはfsync関数を呼び出す場合

空きメモリが所定の閾値を下回ると,カーネルはwakeup_flusher_threads関数を呼び出します.

bdi_writeback_all関数がライトバックを実行している1つまたは複数のFlusher Threadを起床します.

num_pages_to_writeが書き込まれるかつメモリ量がスレッショルドを下回るまでスレッドはデータをディスクに書き込みます.

Flusher Daemonが起動する総メモリ量のパーセンテージは/proc/sys/vm/dirty_background_ratioで確認できます.

私の環境ではdirty_background_ratioは10%です.

ブート時にタイマを初期化し,wb_writeback関数を呼び出すFlusher Threadを起動します.

与えられた値より古いすべてのデータをwrite backする期間は,/proc/sys/vm/dirty_expire_centisecsで確認できます(単位は1/100秒(10ms)).

私の環境では,dirty_expire_centisecsは3000(つまり30秒)です.

将来の指定された時間に期限切れとなるように再初期化されたタイマ(現在 + 期間)は,/proc/sys/vm/dirty_writeback_centisecsで確認できます(単位は1/100秒(10ms)).

私の環境では,dirty_writeback_centisecsは500(つまり5秒)です.

ライトバックと一般的なページキャッシュの制御に関連する他の複数のパラメータは,/proc/sys/vmにあります(詳細はこちら).

まとめ

今回はページキャッシュとページフォールトを紹介しました.

ページ,キャッシュ,メモリの関係がわかりました.

ページキャッシュとページフォールトを深掘りしたいあなたは,以下を読みましょう!

以下の動画もおすすめです!

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

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

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

友だち追加

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

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

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