TECHNOLOGY LINUX KERNEL

【第11回】元東大教員から学ぶLinuxカーネル「プロセスアドレス空間」

2022年10月5日

本記事の信頼性

  • リアルタイムシステムの研究歴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社で自分に合うスクールを見つけましょう.後悔はさせません!

今回のテーマはプロセスアドレス空間です.

プロセスアドレス空間を学ぶとページテーブルや仮想メモリがわかります!

アドレス空間,メモリアドレス,仮想メモリ,ページテーブル

アドレス空間とは,プロセスがアクセスできるメモリのことです.

プロセスがシステムメモリの100%にアクセスできるように錯覚させます.

仮想メモリを使用すると,実際の物理メモリ量よりもはるかに大きくなる可能性があります.

Linuxカーネルが設定するプロセスページテーブルによって定義されます.

メモリアドレスは,アドレス空間内のインデックスとして,特定のバイトを識別します.

各プロセスには32/64ビットのフラットなアドレス空間が与えられています.

仮想メモリとは,2次メモリを主記憶の一部のように使用できるメモリ管理手法のことで,OSでよく使われる技術です.

Linuxカーネルは,プロセスのメモリマッピングを追跡するために仮想メモリ領域(VMA:Virtual Memory Area)を使用します.

ページテーブルとは,OSの中の仮想メモリシステムにおいて仮想アドレスと物理アドレスを対応付けるために使われるデータ構造です.

Linuxはブートプロセスの早い段階でページングを有効にします.

CPUが行う全てのメモリアクセスは仮想であり,ページテーブルを通じて物理アドレスに変換されます.

Linuxがページテーブルを設定し,MMUがページテーブルの内容に従って自動的に変換を行います.

アドレス空間はVMAによって定義され,まばらに配置されます.

1プロセスあたり1つのアドレス空間は,1プロセスあたり1つのページテーブルとなり,多くの「空白」(empty)領域があります.

ページテーブルは以下の動画がわかりやすいです.

mm_struct構造体:メモリディスクリプタ

Linuxカーネルのアドレス空間はメモリディスクリプタ「mm_struct構造体」で管理されます.

linux/include/linux/mm_types.hにmm_struct構造体の定義があります.

mm_usersはアドレス空間を利用しているプロセス(スレッド)の数です.

mm_countは参照カウントで,mm_users > 0 ならば+1,カーネルがアドレス空間を使用している場合は+1になります.

mm_countが0になると,mm_structを解放することができます.

mmapとmm_rbはそれぞれ,このアドレス空間内のすべてのVMAを含むリンクリストとツリーです.

すべてのVMAを昇順で反復処理するために使用されるリストです.

ツリーは特定のVMAを見つけるために使用されます.

mm_structの場合,mmlistメンバ変数を通じて,すべてのmm_structは双方向リストにリンクされています.

メモリディスクリプタの割り当てと解放

メモリディスクリプタの割り当てに関して,タスクメモリディスクリプタは,対応するtask_struct構造体のmmメンバ変数に配置されます.

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

現在のタスクのメモリディスクリプタはcurrent->mmになります.

fork関数で呼び出すcopy_mm関数は親メモリディスクリプタのコピーを子タスク用に作成します.

copy_mm関数はdup_mm関数を呼び,allocate_mm関数を呼び出します.

Slab Cacheからmm構造体オブジェクトを割り当てます.

同じアドレス空間を共有する2つのスレッドは,そのtask_structのmmメンバ変数が同じmm_structオブジェクトを指します.

スレッドはclone関数に渡されたCLONE_VMフラグで生成され,allocate_mm関数は呼ばれません.

メモリディスクリプタの解放では,プロセスが終了するとき,do_exit関数が呼ばれ,exit_mm関数を呼び出します.

exit_mm関数では,いくつかのハウスキーピング/統計情報の更新を行い,mmput関数を呼び出します.

mm_struct構造体とカーネルスレッド

カーネルスレッドにはユーザ空間のアドレス空間がないため,カーネルスレッドのtask_structのmmフィールドがNULLになります.

しかし,カーネルスレッドはカーネルアドレス空間にアクセスする必要があります.

カーネルスレッドがスケジュールされたとき,カーネルはそのmmがNULLであることに気づくので,以前のアドレス空間をロードしたままにします(ページテーブル).

カーネルは,カーネルスレッドのactive_mmメンバ変数が借りたmm_struct構造体を指すようにします.

カーネルのアドレス空間はすべてのタスクで同じなので正常に動作します.

processes and kernel thread

仮想メモリ領域(VMA:Virtual Memory Area)

仮想メモリ領域(VMA:Virtual Memory Area)は,プロセスがアクセスする権利を持つアドレスの区間です.

プロセスのアドレス空間に対して動的に追加または削除が可能です.

また,関連するパーミッションとして読み取り,書き込み,実行があります.

もし不正なアクセスをした場合,セグメンテーションフォールトが発生します.

VMAは以下を含むことができます.

  • 実行ファイルのコードへのマッピング(テキストセクション)
  • 実行ファイルの初期化変数へのマッピング(データセクション)
  • 未初期化変数のゼロページ(中身がすべて0のページ)へのマッピング(BSSセクション)
  • ユーザ空間スタックのゼロページへのマッピング
  • 使用する各共有ライブラリのテキスト,データ,BSS
  • メモリマップドファイル,共有メモリセグメント,匿名マッピング(malloc関数で使用)

address space

/proc/1/mapsでinitプロセス(PIDが1)のVMAを確認できます.

各行が1つのVMAに対応します.

3列目のパーミッションは以下になります.

  • r:read(読み込み)
  • w:write(書き込み)
  • x:execute(実行)
  • s:shared(共有)(以下の例ではありません.)
  • p:private(プライベート,排他)(CoW:Copy-on-Write)

linux/include/linux/mm_types.hで定義されているvm_area_struct構造体でVMAを管理します.

VMAは対応するアドレス空間の[vm start, vm end)で存在します.

つまり,VMAのバイトサイズはvm_end - vm_startになります.

アドレス空間はmm_struct構造体のvm_mmメンバ変数で指定されます.

各VMAは関連するmm_struct構造体に対してユニークです.

同じファイルをマッピングする2つのプロセスは,2つの異なるmm_structオブジェクトと,2つの異なるvm_area_structオブジェクトを持ちます.

mm_structオブジェクトを共有する2つのスレッドは,vm_area_structオブジェクトも共有します.

主なVMAフラグは下表になります.

VMAフラグVMAとそのページへの影響
VM_READページを読み込み可能
VM_WRITEページを書き込み可能
VM_EXECページを実行可能
VM_SEQ_READページへのアクセスをシーケンシャルに実行
VM_RAND_READページへのアクセスをランダムに実行
VM_HUGETLBhugetlbのページ(hugepage)を利用

VM_READ,VM_WRITE,VM_EXECを組み合わせると,全領域の権限が与えられます.

例えば,オブジェクトコードはVM_READとVM_EXEC,スタックはVM_READとVM_WRITEになります.

VM_SEQ_READとVM_RAND_READはmadviseシステムコールで設定されます.

madviseシステムコールは,ファイルプリフェッチアルゴリズム「readahead」にプリフェッチウィンドウを増減するよう指示します.

VM_HUGETLBは,その領域が通常のサイズより大きなhugetlbのページ(hugepage)を利用することを示します.

通常のページと比較して,hugepageを利用することは,TLBミスが少なくメモリアクセスが速いことを意味します.

x86-64のhugepageは2Mと1Gです.

ARM64のhugepageは以下の2つの要素を組み合わせて実現します.

  • pud/pmdレベルでのブロックマッピング:pud/pmdページテーブルエントリがメモリブロックを指す通常のhugepageです.TLBでサポートされるエントリのサイズに関係なく,ブロックマッピングは,hugepageアドレスを変換するために必要なページテーブルウォークの深さを減少させます.
  • contiguous bit(連続ビット)の利用:1つのTLBエントリにキャッシュできる連続したエントリのセットの1つであることをMMUに示唆する変換テーブルエントリ内のcontiguous bitを提供します.

Linuxカーネルでは,contiguous bitのpmdおよびpte(最終)レベルでのマッピングサイズを大きくするために使用されます.

サポートされる連続エントリの数は,ページサイズとページテーブルのレベルによって異なります.

まとめるとARM64のhugepageは下表になります.

通常のページサイズcontiguous bitのpteを利用するhugepagepmdを利用するhugepagecontiguous bitのpmdを利用するhugepagepudを利用するhugepage
4K64K2M32M1G
16K2M32M1G-
64K2M512M16G-

VMAの操作

vm_area_struct構造体のvm_opsメンバ変数は,特定のVMAを操作するための関数ポインタのvm_operations_struct構造体です.

vm_operations_struct構造体は,linux/include/linux/mm.hで定義されています.

VMAの操作関数は以下になります.

  • find_vma関数:addr < vm_endを満たす最初のVMAを返します.
  • find_vma_prev関数:find_vma関数と同じですが,直前のVMAへのポインタを*pprev(第3引数**pprev)に設定する.
  • find_vma_intersection関数:[start_addr, end_addr)の最初のVMAを返す.

アドレスの間隔を操作する関数は以下になります.

  • do_mmap関数:新しいメモリアドレス範囲を作成するために使用されます.新しいVMAが作成される可能性があります.同じパーミッションの場合,作成した領域と隣接する領域をマージします.また,mmap2関数によりユーザ空間にエクスポートします.
  • do_munmap関数:メモリアドレス範囲を削除します.また,munmap関数によりユーザ空間にエクスポートします.

まとめ

今回はプロセスアドレス空間を紹介しました.

具体的には,以下の内容を解説しました.

  • アドレス空間,メモリアドレス,仮想メモリ,ページテーブル
  • mm_struct構造体:メモリディスクリプタ
  • 仮想メモリ領域(VMA:Virtual Memory Area)
  • VMAの操作

プロセスアドレス空間を深掘りしたいあなたは,以下の記事を読みましょう!

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

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

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

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

友だち追加

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

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

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