TECHNOLOGY LINUX KERNEL

【第10回】元東大教員から学ぶLinuxカーネル「メモリ管理」

本記事の信頼性

  • リアルタイムシステムの研究歴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)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を250本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

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

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

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

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

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

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

友だち追加

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

今回のテーマはメモリ管理です.

メモリ管理を理解することで,カーネルレベルのメモリの確保と解放する方法がわかります.

ページ(Page)とゾーン(Zone)

メモリ管理で必要となるページ(Page)とゾーン(Zone)を紹介します.

ページ

メモリは物理的なページまたはフレームに分割されます(下図).

physical page or frame

ページはカーネルにおける基本的な管理単位です.

ページサイズはマシンに依存します.

メモリ管理ユニット(MMU)のサポートによって決定されます.

一般的には4KB,2MBや1GBのものもあります.

私のLinux環境で「getconf PAGESIZE」と入力すると,ページサイズが4096(4KB)であることがわかります.

各物理ページは,linux/include/linux/mm_types.hで定義されているpage構造体で管理されます.

カーネルはpage構造体を使って,ページの所有者を追跡します.

ページの所有者は,ユーザ空間プロセス,カーネルが静的/動的割り当てしたデータ,ページキャッシュ等です.

物理メモリページごとに1つのpage構造体のオブジェクトが存在します.

「sizeof(struct page)」は64バイトです.

また,8GBのメモリと4Kサイズのページの場合,128MBがpage構造体オブジェクト用に確保されます.

メモリ全体の使用量の割合は128MB / 8GB ≒ 1.5%,page構造体の要素数は128MB / 64 = 2MBです.

ゾーン

ハードウェアの制限により,特定のコンテキストで特定の物理ページが必要な場合があります.

デバイスによっては,下位16MBの物理メモリ(下位アドレスのメモリ)にしかアクセスできない場合,ハイメモリ(上位アドレスのメモリ)はアクセスする前にマッピングされる必要があります.

そこで,物理メモリを同じ制約を持つゾーンに分割することで解決します.

ゾーンのレイアウトは,アーキテクチャとマシンに依存します.

ページアロケータはページを割り当てる際に制約を考慮します.

ゾーンの名前と説明は下表になります.

ゾーンの名前説明
ZONE_DMAページはDMAに使用可能
ZONE_DMA3232ビットDMAデバイス用ページ
ZONE_NORMAL常にアドレス空間にマッピングされるページ
ZONE_HIGHMEMアクセスする前にページをマッピングする必要あり

x86とx86-64のゾーンのレイアウトは下図になります.

x86 and x86-64 zones layout

各ゾーンは,linux/include/linux/mmzone.hで定義されているzone構造体で管理されます.

メモリアロケータ

hierarchy of memory allocators

上図にメモリアロケータの階層を示します.

本記事では以下を解説します.

  • Low-Level Memory Allocator(Buddy System)
  • kmalloc/vmalloc関数
  • Slab Allocator

Low-Level Memory Allocator(Buddy System)

Low-Level Memory Allocator(Buddy System)は,ページ単位でメモリを確保する低レベルの機構です.

Buddy Systemは,メモリの断片化を防ぐシステムです.

下図のようにBuddy Systemはメモリを管理します.

buddy system

/proc/buddyinfoでBuddy Systemの情報を表示できます.

私のPC環境での表示結果は以下になります.

linux/include/linux/gfp.hにあるページ割り当て/解放する関数やマクロは以下になります.

  • alloc_pages関数:2のorder乗の個数のページを割り当てて,page構造体のポインタを返す.
  • alloc_pageマクロ:2の0乗の個数(1個)のページを割り当てて,page構造体のポインタを返す.
  • free_pages関数:2のorder乗の個数のページを解放する.
  • free_pageマクロ:2の0乗の個数(1個)のページを解放する.
  • __get_free_pages関数:alloc_pages関数と同様に割り当てて,unsigned long型の仮想アドレスを返す.
  • __get_free_pageマクロ:alloc_pageマクロと同様に割り当てて,unsigned long型の仮想アドレスを返す.

linux/linux/include/linux/mm.hにあるページアクセス関数は以下になります.

  • page_address関数:ページの仮想アドレスを取得する.

ページデータはデフォルトではクリア(0に初期化)されません.

この場合,ページ割り当てによる情報漏えいの可能性があります.

そこで,情報漏えいを防ぐため,linux/include/linux/gfp.hにあるget_zeroed_page関数を利用してユーザ空間の要求に対して0に初期化されたページを確保します.

gfp_tはフリーページフラグを管理する型で,メモリ割り当てのためのオプションを指定します.

  • メモリの割り当て方法
  • どのゾーンからメモリを割り当てるか
  • アクションとゾーン修飾子の組み合わせ(これらを直接使用するよりも一般的に好ましい)

linux/incude/linux/gfp.hで定義されている,よく利用するGFPフラグの組み合わせは以下になります.

GFPフラグ説明
GFP_ATOMICGFP_ATOMICはスリープできず,割り当てを成功させる必要があります.「アトミックリザーブ」へのアクセスを可能にするために,より低い透かしが適用されます.現在の実装では,NMIと他のいくつかの厳密なノンプリエンプティブコンテキスト (raw_spin_lock等) はサポートされていません.
GFP_KERNELGFP_KERNELは,カーネル内部での割り当ての典型です.呼び出し側には,直接アクセスのためにZONE_NORMALまたはそれより低いゾーンが必要ですが,直接再請求することができます.
GFP_DMAGFP_DMAは歴史的な理由で存在しており,可能であれば利用は避けるべきです.GFP_DMAは,呼び出し元が最低ゾーン(x86-64ではZONE_DMAまたは16M)を使用するよう要求していることを示します.理想的には,これは削除されるべきです.一部のユーザはGFP_DMAを利用し,他のユーザはZONE_DMAのローメモリリザーブを回避し,最低ゾーンを緊急リザーブの一種として扱うためにこのフラグを利用します.

gfp_tの主な使い方は下表になります.

コンテキスト利用するgfp_t
プロセスコンテキストでスリープできる場合GFP_KERNEL
プロセスコンテキストでスリープできない場合GFP_ATOMIC
割り込みハンドラGFP_ATOMIC
softirq,taskletGFP_ATOMIC
DMA可能でスリープできる場合GFP_DMA | GFP_KERNEL
DMA可能でスリープできない場合GFP_DMA | GFP_ATOMIC

Low-Level Memory Allocatorのコード一式はこちらからダウンロードして下さい.

Low-Level Memory Allocatorのコードlow_level_memory_allocator_kernel_module.cは以下になります.

実行結果は以下になります.

Buddy Systemの解説は以下の動画がわかりやすいです.

High Memory

x86では,896MBを超える物理メモリ(High Memory)はカーネルアドレス空間内に恒久的にマッピングされません.

アドレス空間のサイズに制限があり,最大4GBのカーネル/ユーザ空間のメモリがカーネル空間は約1GB(正確には896MB),ユーザ空間は3GBに分割されているためです.

なので,使用する前に,ハイメモリからのページをアドレス空間にマップする必要があります.

linux/include/linux/highmem.hにメモリを恒久的にマップ/アンマップするkmap/kunmap関数があります.

linux/include/linux/highmem-internal.hにメモリを一時的にマップ/アンマップするkmap_atomic/kunmap_atomic関数があります.

※kmap_atomic関数ではなくlinux/include/linux/highmem.hにあるkmap_local_page関数を推奨しているので注意して下さい.将来的にはkmap_atomic関数は廃止予定だと思われます.

kmalloc/kfree/vmalloc/vfree関数

kmalloc関数は,malloc関数のカーネル版で,(主に)カーネルでページサイズより小さいオブジェクトのために物理的に連続したメモリを割り当てます.

kmalloc関数は後述するvmalloc関数よりオーバーヘッドが低いため,カーネル内でよく利用されます.

kfree関数は,free関数のカーネル版で,カーネルで割り当てられたメモリを解放します.

vmalloc関数は,仮想的に連続したメモリを割り当てます.

物理的に連続したメモリでない可能性がありますので注意して下さい.

また,物理的に連続したメモリを必要とするI/Oバッファには使用できません.

kmalloc関数で確保するメモリはページサイズが上限なので,vmalloc関数はより大きなメモリを割り当てるために使用されます.

vfree関数は,vmalloc関数で割り当てたメモリを解放します.

kmalloc/kfree関数を利用するコード

kmalloc/kfree関数の利用するコード一式はこちらからダウンロードして下さい.

kmalloc/kfree関数を利用するkmalloc_kernel_module.cは以下になります.

実行結果は以下になります.

38行目で「[  423.932226] allocate 4194304 bytes」と表示されているので,「4194304 bytes = 4MB」までメモリ確保できていますが,8MBでメモリ確保に失敗していることがわかります.

vmalloc/vfree関数を利用するコード

vmalloc/vfree関数の利用するコード一式はこちらからダウンロードして下さい.

vmalloc/vfree関数を利用するvmalloc_kernel_module.cは以下になります.

実行結果は以下になります.

48行目で「[  230.475101] allocate 4294967296 bytes」と表示されているので,「4294967296 bytes = 4GB」までメモリ確保できていますが,8GBでメモリ確保に失敗していることがわかります.

※私のLinux環境のメモリが8GBなので,この結果になりましたが,メモリサイズによって結果が変動します.

「kmalloc and vmalloc : Linux kernel memory allocation API Limits」の記事でも同様の実験が行われていますので,是非読みましょう!

Slab Allocator

Slab Allocatorは,オブジェクトの効率的なメモリ割り当てを目的としたメモリ管理機構です.

従来の機構と比較して,割り当てと解放に起因する断片化を軽減することができます.

Slab Allocatorは,ある型のデータオブジェクト(Slab Object)を含む割り当てられたメモリを保持し,同じ型のSlab Objectを次に割り当てる際に再利用するために使用されます.

Object Poolのデザインパターンに似ているが,メモリにのみ適用され,他のリソースには適用されません.

データ構造の割り当て/解放は,カーネルで非常に頻繁に行われます.

メモリ割り当てを高速化する方法としてフリーリストを使ったSlab Cacheが採用されています.

フリーリストは,特定の種類のデータ構造に対してあらかじめ割り当てられたメモリのブロックです.

フリーリストから割り当てることはフリーリストの中の要素(element)を選ぶこと,フリーリストの要素を解放することは要素をフリーリストに追加することを意味します(下図).

fully allocated free list

アドホックなフリーリストの問題点は, グローバルな制御ができないことです.

いつ,どのようにフリーリストを解放するかを管理するのがSlab Allocatorです.

Slab Allocatorは,一般的なアロケーションキャッシュインタフェースを提供し,データ構造型(例:task_struct構造体)のSlabオブジェクトをキャッシュします.

また,データ構造のサイズ,ページサイズ,NUMA,Cache Coloringを考慮します.

slab allocator

上図のようにSlab Cacheは1つまたは複数のSlabを持ちます.

Slabは,物理的に連続した1ページまたは数ページです.

SlabにはSlab Objectが含まれます.

Slabは,empty,partially full,またはfullの場合があります.

メモリの断片化を防ぐために,partially fullのSlab Objectを割り当てます.

/proc/slabinfoにSlabの情報があります.

Slab Allocatorのバリエーションは以下になります.

  • SLOB(Simple List Of Blocks):初期のLinux(1991年以降)で使用された機構で,メモリフットプリントが小さく,組込みシステムに向いている.
  • SLAB:1999年にマージされた機構で,Cache-Friendlyな(キャッシュと親和性が高い)設計である.
  • SLUB:2008年にマージされた機構で,メニーコアシステムでSLABよりスケーラビリティが向上する.

linux/include/linux/slab_def.hにSlabを管理するkmem_cache構造体があります.

linux/include/linux/slab.hにSlabの操作関数があります.

Slab Allocatorのコード一式はこちらからダウンロードして下さい.

Slab Allocatorのコードslab_allocator_kernel_module.cは以下になります.

実行結果は以下になります.

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

その他のメモリ管理:CPU毎のデータ構造,スタック

その他のメモリ管理を紹介します.

CPU毎のデータ構造

CPU毎のデータ構造では,各コアが独自の値を持つことが可能です.

ロックが不要で,キャッシュのスラッシングを低減します.

また,各インデックスがCPUのコアIDに対応する配列で実装されます.

linux/include/linux/smp.hに以下が定義されています.

  • smp_processor_idマクロ:コアIDを取得する.
  • get_cpuマクロ:プリエンプションを無効にしてコアIDを取得する.
  • set_cpuマクロ:プリエンプションを有効にする.

スタック

各プロセスは実行用のユーザ空間のスタックとカーネル内実行のためのカーネルスタックを持ちます.

ユーザ空間スタックは大きく,動的に増加します.

カーネルスタックは小さく固定サイズ(2ページ,多くの場合で8KB)です.

割り込みスタックは割り込みハンドラ用で,各コアで1ページです.

カーネルスタックの使用量を最小限に抑えるためには,ローカル変数と関数パラメータが重要になります.

まとめ

今回はメモリ管理を紹介しました.

メモリ管理に関してまとめると以下になります.

  • 物理的に連続したメモリが必要な場合は,kmalloc関数またはalloc_pageファミリー関数を利用する.
  • 仮想的に連続したメモリが必要な場合は,vmalloc関数を利用する.
  • 同じデータ構造を大量に作成/破棄することが多い場合は,Slab Allocatorを利用する.
  • ハイメモリ(上位アドレスのメモリ)から割り当てる必要がある場合は,alloc_pageファミリー関数の後にkmap/kmap_atomic関数を利用する.

メモリ管理を深掘りしたいあなたは,以下の記事を読みましょう!

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

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

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

友だち追加

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

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

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