Chapter 5:

コンピュータ内の翻訳家 Edit on GitHub

これまで、メモリの読み書きについて話すたびに、少し曖昧な感じがしました。たとえば、ELFファイルはデータをロードするための特定のメモリアドレスを指定していますが、異なるプロセスが競合するメモリを使用しようとする問題はなぜ発生しないのでしょうか？なぜ各プロセスごとに異なるメモリ環境を持つように見えるのでしょうか？

また、ここに来るまでに具体的にどのようにしてきたのでしょうか？私たちはexecveが現在のプロセスを新しいプログラムで「置き換える」シスコールであることを理解していますが、これは複数のプロセスがどのように開始されるかを説明していません。それは確かに最初のプログラムがどのように実行されるかを説明しません — どの鶏（プロセス）が他の卵（他のプロセス）を産むのでしょうか？

私たちの旅も終盤に差し掛かっています。これらの二つの質問に答えた後、コンピュータが起動から現在使用しているソフトウェアを実行するまでのプロセスをほぼ完全に理解することになります。

メモリは仮想的

さて、メモリについてです。CPUがメモリアドレスから読み取りまたは書き込みを行うとき、実際の物理メモリ（RAM）のその場所を指しているわけではありません。むしろ、仮想メモリ空間内の場所を指しています。

CPUは、メモリ管理ユニット（MMU）と呼ばれるチップと通信します。MMUは、仮想メモリ内の場所をRAM内の場所に変換する辞書を持つ通訳のように機能します。CPUにはメモリアドレス 0xfffaf54834067fe2 から読み取る命令が与えられた場合、それを変換するようMMUに依頼します。MMUは辞書を調べ、対応する物理アドレスが 0x53a4b64a90179fe2 であることを見つけ、その番号をCPUに返します。CPUはそれからRAM内のそのアドレスから読み取ることができます。

コンピュータが起動すると、最初はメモリアクセスが直接物理RAMに行きます。起動直後、OSは翻訳辞書を作成し、CPUにMMUの使用を開始するよう指示します。

この辞書は実際にはページテーブルと呼ばれ、すべてのメモリアクセスを翻訳するこのシステムはページングと呼ばれます。ページテーブル内のエントリはページと呼ばれ、それぞれが特定の仮想メモリの一部がRAMにどのようにマップされるかを表します。これらのチャンクは常に固定サイズで、各プロセッサアーキテクチャには異なるページサイズがあります。x86-64はデフォルトで4 KiBのページサイズを持ち、つまり各ページは4,096バイトのメモリブロックのマッピングを指定します。

言い換えれば、4 KiBのページを使用する場合、アドレスの下位12ビットはMMUの変換前後で常に同じであることになります。それは、4,096バイトのページを指し示すのに必要なビット数が12だからです。

x86-64では、オペレーティングシステムが大きな2 MiBまたは4 GiBのページを有効にすることも可能で、アドレス変換の速度を向上させるかもしれませんが、メモリの断片化と浪費を増加させる可能性があります。ページサイズが大きいほど、MMUによって翻訳されるアドレスの部分が小さくなります。

ページテーブル自体はRAMに存在します。それは何百万ものエントリーを含むことができますが、各エントリーのサイズはわずか数バイトのオーダーであり、したがってページテーブルはあまり多くのスペースを占有しません。

ブート時にページングを有効にするために、カーネルは最初にRAM内にページテーブルを構築します。それから、ページテーブルの先頭の物理アドレスをページテーブルベースレジスタ（PTBR）と呼ばれるレジスタに格納します。最後に、カーネルはMMUを使用してすべてのメモリアクセスを変換するためにページングを有効にします。x86-64では、制御レジスタ3（CR3）の上位20ビットがPTBRとして機能します。ページングを有効にするために、CR0のビット31であるPG（Pagingの略）は1に設定されます。

ページングシステムの魔法は、コンピュータが稼働中にページテーブルを編集できることです。これが各プロセスが独自の隔離されたメモリスペースを持つ方法です。オペレーティングシステムが1つのプロセスから別のプロセスにコンテキストを切り替えるとき、重要なタスクの1つは仮想メモリスペースを物理メモリ内の異なる領域に再マッピングすることです。たとえば、2つのプロセスがあるとしましょう：プロセスAはそのコードとデータを（おそらくELFファイルから読み込まれているでしょう！）0x0000000000400000に持っており、プロセスBも同じアドレスからそのコードとデータにアクセスできます。これらの2つのプロセスは同じプログラムのインスタンスでさえあるかもしれません。なぜなら、彼らは実際にはそのアドレス範囲を争っていないからです！プロセスAのデータは物理メモリ内でプロセスBからは遠くにあり、プロセスに切り替えるときにカーネルによって0x0000000000400000にマップされます。

余談：呪われたELFの事実

特定の状況では、binfmt_elfは最初のメモリページをゼロにマップする必要があります。1988年に登場した最初のELFをサポートしたOSであるUNIX System V Release 4.0（SVr4）向けに書かれた一部のプログラムは、ヌルポインタが読み取り可能であることに依存しています。そして、なぜかまだ一部のプログラムはその動作に依存しています。

この振る舞いを実装したLinuxカーネルの開発者は、少し不満を抱いていたようです：

“なぜか、と聞かれるかもしれませんが？ それはSVr4がページ0を読み取り専用としてマップし、一部のアプリケーションがこの動作に ‘依存’ しているからです。これらを再コンパイルする権限がないため、SVr4の振る舞いをエミュレートしています。ため息。”

ため息。

ページングによるセキュリティ

メモリ・ページングによって実現されるプロセスの隔離は、コードの使いやすさを向上させます（プロセスはメモリを使用するために他のプロセスを意識する必要はありません）。しかし、同時にセキュリティのレベルも確立します：プロセスは他のプロセスのメモリにアクセスできません。これは、この記事の冒頭で述べた元の質問の一部に対する回答の半分です：

プログラムがCPU上で直接実行され、CPUはRAMに直接アクセスできるので、なぜコードが他のプロセスまたは、もしやってしまうと、カーネルのメモリにアクセスできないのですか？

覚えていますか？それはずいぶん昔のことのように感じます…

では、カーネルメモリはどうでしょうか？まず最初に: カーネルは明らかにすべての実行中のプロセスとページテーブル自体を追跡するために十分なデータを保存する必要があります。ハードウェア割り込み、ソフトウェア割り込み、またはシステムコールがトリガーされ、CPUがカーネルモードに入るたびに、カーネルコードはそのメモリにどうやってアクセスするかを考える必要があります。

Linuxの解決策は、常に仮想メモリ空間の上半分をカーネルに割り当てることです。そのため、Linuxはハイハーフカーネルと呼ばれます。Windowsも似たような手法を採用しており、一方、macOSは… 少し 複雑 で、それについて読んでいると私の脳が耳から滲み出るかのような感じです。 ~(++)~

しかし、ユーザーランドのプロセスがカーネルメモリを読み取ったり書き込んだりできるとセキュリティ上の問題です。そのため、ページングはセキュリティの第2のレイヤーを有効にします：各ページはアクセス許可フラグを指定する必要があります。1つのフラグは領域が書き込み可能か読み取り専用かを決定します。もう1つのフラグはCPUに対して領域のメモリにアクセスできるのはカーネルモードのみ許可することを伝えます。後者のフラグは、上半分のカーネルスペース全体を保護するために使用されます。実際、ユーザースペースプログラムの仮想メモリマッピングにはカーネルメモリ全体が含まれていますが、それにアクセスする許可は持っていないだけです。

ページテーブル自体は実際にはカーネルメモリスペース内に含まれています！タイマーチップがプロセス切り替えのためにハードウェア割り込みをトリガーすると、CPUは特権レベルをカーネルモードに切り替えてLinuxカーネルコードにジャンプします。カーネルモード（Intelリング0）にあると、CPUはカーネル保護メモリ領域にアクセスできます。その後、カーネルはページテーブルに書き込むことができます（それはメモリの上半分のどこかに存在します）以前のプロセスのために仮想メモリの下半分を再マップするため。カーネルが新しいプロセスに切り替え、CPUがユーザーモードに入ると、カーネルメモリにはアクセスできなくなります。

ほぼすべてのメモリアクセスはMMUを介して行われます。割り込みディスクリプタテーブルのハンドラポインター？それらはカーネルの仮想メモリ空間を指します。

階層型ページングとその他の最適化

64ビットシステムは、メモリアドレスが64ビットであるため、64ビットの仮想メモリスペースは16 エクスビバイトものサイズです。これは非常に大きなサイズであり、今日存在するか、すぐに存在するであろうどんなコンピュータよりもはるかに大きいものです。私の知る限り、これまでのどのコンピュータにも、Blue Watersスーパーコンピュータの1.5ペタバイトを超えるRAMがありましたが、それでも16 EiBの0.01%未満です。

仮想メモリスペースの各4 KiBセクションに対してページテーブルのエントリが必要な場合、4,503,599,627,370,496個のページテーブルエントリが必要です。8バイトのページテーブルエントリを使用する場合、ページテーブルだけでも32ペビバイトのRAMが必要です。これは、コンピュータの最大RAMの世界記録よりも大きいことに気づくかもしれません。

余談: なぜ奇妙な単位を使うのか？

これは一般的ではなく、非常に見苦しいかもしれませんが、2の冪乗であるバイナリバイトサイズ単位と、10の冪乗であるメトリック単位とを明確に区別することが重要だと考えています。キロバイト（kB）は1,000バイトを意味する国際単位系（SI）の単位です。キビバイト（KiB）は、1,024バイトを意味するIEC勧告の単位です。CPUとメモリアドレスの観点からは、バイト数は通常2の冪乗であり、コンピュータは2進数システムであるためです。1,024を意味するKB（またはさらに悪い場合、kB）を使用すると、曖昧性が増す可能性があります。

可能な仮想メモリスペース全体に連続したページテーブルエントリを持つことは不可能（または非常に実用的でない）であるため、CPUアーキテクチャでは階層型ページングを実装しています。階層型ページングシステムでは、ますます細かい粒度の複数のページテーブルがあります。トップレベルエントリは大きなメモリブロックをカバーし、より小さなブロックのページテーブルを指し、ツリー構造を作成します。4 KiBまたはページサイズに関する個々のエントリは、ツリーの葉となります。

x86-64は歴史的には4レベルの階層型ページングを使用しています。このシステムでは、各ページテーブルエントリは、アドレスの一部をオフセットにして含まれるテーブルの開始位置を探し出します。この部分は最も有効ビットから始まり、エントリはこれらのビットで始まるすべてのアドレスをカバーします。エントリは次のビットコレクションでインデックスされる次のレベルのテーブルの開始位置を指します。

x86-64の4レベルのページングの設計者は、ページテーブルスペースを節約するために仮想ポインタの上位16ビットを無視することを選択しました。48ビットは128 TiBの仮想アドレススペースを提供し、これは十分大きいと見なされました。（完全な64ビットでは16 EiBになりますが、それはかなり多いです。）

最初の16ビットがスキップされているため、ページテーブルの最初のレベルをインデックスするための「最上位ビット」は、63ではなく47ビットから開始します。これはまた、この章の前半で示されていたハイハーフカーネルダイアグラムが技術的に不正確であることを意味します。カーネルスペースの開始アドレスは、64ビットよりも小さいアドレススペースの中央点として描かれるべきでした。

階層型ページングは、ツリーの任意のレベルで、次のエントリへのポインタをnull（0x0）にできるため、スペースの問題を解決します。これにより、ページテーブルのサブツリー全体を省略でき、仮想メモリ空間のアンマップされた領域はRAM内でスペースを占有しません。アンマップされたメモリアドレスでの検索は、CPUがツリーの上位で空のエントリを見るとすぐにエラーが発生できるため、迅速に失敗することができます。また、ページテーブルエントリには、アドレスが有効であるように見えても使用できないようにマークするために使用できる存在フラグもあります。

階層型ページングのもう一つの利点は、仮想メモリ空間の大部分を効率的に切り替える能力です。大きな仮想メモリ領域の大部分は、1つのプロセスのために物理メモリのある領域にマップされ、別のプロセスのためには別の領域にマップされることがあります。カーネルは両方のマッピングをメモリに保存し、プロセスを切り替える際には単にツリーのトップレベルのポインタを更新するだけです。仮にメモリ空間マッピング全体がエントリのフラットな配列として保存されていた場合、カーネルは多くのエントリを更新する必要があり、遅く、それにもかかわらず各プロセスのメモリマッピングを独立に追跡する必要があります。

私はx86-64が「歴史的に」4レベルのページングを使用してきたと言いましたが、最近のプロセッサは5レベルのページングを実装しています。5レベルのページングは、アドレススペースを57ビットのアドレスで128 PiBに拡張するために、別の間接レベルとさらに9つのアドレッシングビットを追加します。5レベルのページングは、Linuxを含むオペレーティングシステムで2017年以降にサポートされており、最新のWindows 10および11サーバーバージョンでもサポートされています。

余談：物理アドレススペースの制限

オペレーティングシステムが仮想アドレスのためにすべての64ビットを使用しないように、プロセッサも64ビットの物理アドレスを完全に使用しません。4レベルのページングが標準だったとき、x86-64 CPUは46ビット以上を使用しなかったため、物理アドレススペースは64 TiBに制限されていました。5レベルのページングでは、サポートが52ビットまで拡張され、4 PiBの物理アドレススペースをサポートしています。

OSのレベルでは、仮想アドレススペースが物理アドレススペースよりも大きいことが有利です。Linus Torvaldsは次のように述べています（https://www.realworldtech.com/forum/?threadid=76912&curpostid=76973）：「それは少なくとも2倍、正直なところそれは限界であり、10倍以上がはるかに良いです。それを理解していない人は愚か者です。議論の余地はありません。」

スワップとデマンドページング

メモリアクセスが失敗する可能性がいくつかあります。アドレスが範囲外であるか、ページテーブルにマップされていないか、存在しないとマークされたエントリがあるかもしれません。いずれの場合でも、MMU（メモリ管理ユニット）はカーネルが問題を処理するために ページフォルト と呼ばれるハードウェア割り込みをトリガーします。

一部の場合、読み取りは実際には無効または禁止されているかもしれません。これらの場合、カーネルはおそらくプログラムを セグメンテーションフォルト エラーで終了させるでしょう。

$ ./program
Segmentation fault (core dumped)
$

余談：セグフォールトのオントロジー

“Segmentation fault”（セグメンテーションフォルト）は、異なる文脈で異なる意味を持つ言葉です。メモリが許可なく読み取られると、MMU（メモリ管理ユニット）は「セグメンテーションフォルト」と呼ばれるハードウェア割り込みを発生させますが、「セグメンテーションフォルト」はまた、OSが実行中のプログラムに対して不正なメモリアクセスによりそれらを終了させるために送信できるシグナルの名前でもあります。

他の場合では、メモリアクセスは意図的に失敗することもあり、OSはメモリを埋めることができ、その後CPUに制御を戻して再試行できます。たとえば、OSはディスク上のファイルを実際にRAMにロードせずに仮想メモリにマップし、アドレスが要求され、ページフォルトが発生したときに物理メモリにロードします。これをデマンドページングと呼びます。

一方、これにより、mmapなどのシスコールが存在することができます。これらのシスコールはディスクから仮想メモリにファイル全体を遅延マップするものです。LLaMa.cppというFacebookのリークした言語モデルのランタイムがわかる場合、最近Justine Tunneyはすべてのローディングロジックをmmapに使うように最適化しました。もし彼女を以前聞いたことがない場合は、彼女の作品をチェックしてみてください！Cosmopolitan LibcとAPEは本当にクールで、この記事を楽しんでいるなら興味があるかもしれません。

明らかに多くの ドラマ が Justineのこの変更に関与しているようです。無作為なインターネットユーザーから叫ばれないように、これを指摘しておきます。私はそのドラマのほとんどを読んでいないことを告白しなければなりませんが、私が言ったことがJustineの作品がクールだということはまだ本当です。

プログラムとそのライブラリを実行するとき、カーネルは実際には何もメモリにロードしません。カーネルはファイルのmmapを作成するだけです。CPUがコードを実行しようとすると、ページはすぐにフォルトが発生し、カーネルはページを実際のメモリブロックで置き換えます。

デマンドページングはまた、おそらく「スワッピング」または「ページング」として知っているテクニックを可能にします。オペレーティングシステムはメモリページをディスクに書き込んで物理メモリから削除し、仮想メモリに存在フラグを0に設定したままにします。その仮想メモリが読み取られると、OSはメモリをディスクからRAMに復元し、存在フラグを1に戻します。OSはディスクの読み取りと書き込みが遅いため、オペレーティングシステムは効率的なページ置換アルゴリズムを使用してスワップをできるだけ少なくするように努力します。

興味深いハックの1つは、ファイルの物理ストレージ内の場所を格納するためにページテーブルの物理メモリポインタを使用することです。MMUは存在フラグが負の場合すぐにページフォルトが発生するため、無効なメモリアドレスであることは関係ありません。これはすべてのケースで実用的ではありませんが、考えるだけでも面白いアイデアです。