VMAとMaple Tree

概要: vm_area_struct → VMA操作 (mmap/munmap/mprotect/mremap) → Maple TreeがRed-Black木に取って代わる (6.1+) → VMAマージ → page faultとVMA検索 カーネルバージョン: 2.6 ~ 6.x、Maple Treeへの移行を重点的に注釈

概要

各プロセスのアドレス空間は、一連のVMA（Virtual Memory Area：仮想メモリ領域）によって記述されます。1つのVMAは、同じ保護属性とマッピングタイプ（匿名メモリ、ファイルマッピング、デバイスマッピングなど）を持つ連続した仮想アドレス範囲を表します。mmap() はVMAを作成し、munmap() はVMAを破棄し、mprotect() はVMAの属性を変更します。

従来のVMAは、Red-Black木と双方向リストによって管理されていました（検索は O(log n)、走査は O(n)）。6.1で導入された Maple Tree は操作を O(log n) に抑えつつ、ロックレスの読み取り走査もサポートしています。これは、メモリ管理サブシステムにおいて近年最も重要なデータ構造の変更の一つです。

vm_area_struct

// include/linux/mm_types.h
struct vm_area_struct {
    // アドレス範囲
    unsigned long           vm_start;
    unsigned long           vm_end;         // VMA内に含まれない (半開区間)

    // リスト/ツリーノード (旧: Red-Black木, 新: Maple Tree)
    union {
        struct {
            struct list_head    vm_list;    // 双方向リスト (走査用)
            struct rb_node      vm_rb;      // Red-Black木 (検索用, 6.0-)
        };
        // 6.1+: VMAは完全にMaple Treeによって管理され、これらのフィールドは上書きされる
    };

    // 属性
    pgprot_t                vm_page_prot;  // ページ保護ビット (R/W/Xのエンコーディング)
    unsigned long           vm_flags;      // VM_READ, VM_WRITE, VM_EXEC, VM_SHARED, ...

    // 関連する mm_struct とファイル (ファイルバックドの場合)
    struct mm_struct        *vm_mm;
    struct file             *vm_file;      // 匿名の場合は NULL
    unsigned long           vm_pgoff;      // ファイル内のオフセット (ページ単位)

    // 操作関数テーブル
    const struct vm_operations_struct *vm_ops;  // open, close, fault, ...

    // 匿名マッピング (anonymous)
    struct anon_vma         *anon_vma;     // 逆参照 (rmap) の鍵
    struct anon_vma_name    *anon_name;    // [anon:name] (5.17+)

    // シェアードメモリ (shmem / MAP_SHARED anonymous)
    struct address_space    *vm_swap;      // スワップキャッシュの address_space
};

主要な vm_flags

VMAの匿名/ファイル分類

匿名 VMA (anonymous):
  vm_file == NULL
  例: malloc/mmap(MAP_ANONYMOUS) によって割り当てられたヒープ/スタック/heap
  データには対応するディスクファイルが存在しない
  スワップ時にスワップパーティション/ファイルに書き込まれる

ファイルマッピング VMA (file-backed):
  vm_file != NULL
  例: mmap(通常ファイル)、コードセグメント (exec の ELF LOAD セグメント)
  ページキャッシュ内のページはファイル内容と一致する
  ダーティページは対応するファイルに書き戻される

VMA操作

mmap: VMAの作成

flowchart TD
    SYSCALL["mmap() システムコール"] --> AREA["get_unmapped_area()<br/>空きアドレス範囲を検索"]

    AREA --> ARCH{"アーキテクチャ固有の検索"}
    ARCH -->|"x86"| TOPDOWN["トップダウン検索<br/>(top-down, ASLR)"]
    ARCH -->|"legacy"| BOTTOMUP["ボトムアップ<br/>(mmap_legacy_base)"]

    AREA --> REGION["mmap_region()"]

    REGION --> CHECK{"既存の<br/>VMAとの関係をチェック"}
    CHECK -->|"完全に一致"| MERGE["再利用またはマージ"]
    CHECK -->|"部分的に重複"| SPLIT["VMAを分割"]
    CHECK -->|"無関係"| NEW["新規VMAの作成"]

    NEW --> VM_OPS["vm_ops->mmap() を呼び出し<br/>ファイルシステムコールバック<br/>例: ext4: filemap_fault() を登録"]

    VM_OPS --> DEMAND["⚠️ ページテーブルは更新されない!<br/>デマンドページング:<br/>実際の割り当ては page fault 時まで遅延"]

    DEMAND --> RET["マッピング開始アドレスを返す ✅"]

    classDef sys call fill:#e3f2fd,stroke:#1565c0
    classDef step fill:#f3e5f5,stroke:#7b1fa2
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef done fill:#e8f5e9,stroke:#2e7d32
    class SYSCALL syscall
    class AREA,TOPDOWN,BOTTOMUP,REGION,MERGE,SPLIT,NEW,VM_OPS,DEMAND step
    class ARCH,CHECK decision
    class RET done

munmap: VMAの破棄

SYSCALL_DEFINE2(munmap, ...) → do_munmap()

do_munmap():
  ├─ find_vma_intersection()   // 範囲を覆う VMA を検索
  ├─ VMA を分割 (部分的に消去する場合)
  ├─ detach_vmas_to_be_unmapped()
  │   └─ mm の VMA コレクションから分離
  ├─ unmap_region()
  │   └─ unmap_vmas → VMA リストを走査
  │       └─ unmap_page_range()
  │           → 対応するページテーブルエントリをクリア (zap_pte_range)
  │           → 物理ページを解放 (put_page → 最後の参照でなければページキャッシュに移動)
  │           → TLB shootdown (マルチコア向け)
  └─ remove_vma_list()
      └─ vm_area_struct を解放 (kmem_cache_free)

mprotect: 権限の変更

SYSCALL_DEFINE3(mprotect, ...) → do_mprotect_pkey()

// 物理ページの再割り当ては不要、PTEフラグの変更のみでよい:
//   VM_WRITE を変更 → PTE の R/W ビット
//   VM_EXEC を変更  → PTE の NX ビット
//   ページテーブルウォーク → set_pte_at() → TLB フラッシュ

mremap: サイズ調整/移動

SYSCALL_DEFINE5(mremap, ...) → do_mremap()

// MREMAP_MAYMOVE: 移動を許可
//   → 現在のアドレスの後ろに十分なスペースがない場合:
//     get_unmapped_area() で新しい位置を検索
//     move_page_tables() → ページテーブルエントリを新しい位置にコピー (物理ページはコピーしない!)
//     → TLB フラッシュ
//
// realloc との連携:
//   glibc は mremap を使用して大きな割り当てを拡張 → 物理メモリのコピーを回避

Maple Tree: VMA管理の新エンジン

なぜRed-Black木から置き換えるのか

旧設計 (Red-Black木 + リスト, 2.6 ~ 6.0):
  VMA は Red-Black木 (検索 O(log n)) と双方向リスト (走査 O(n)) の両方に存在
  欠点:
    - 2つのデータ構造を同期させる必要がある → 複雑
    - すべての操作が mmap_lock 下で行われる → ロック競合
    - VMAが密集したシナリオ (多くの mmap など) では、リスト走査が O(n)

新設計 (Maple Tree, 6.1+):
  VMA は Maple Tree のみに存在
  利点:
    - すべての操作が O(log n): 検索/挿入/削除/範囲クエリ
    - ロックレスの読み取り走査 (RCU保護) をサポート: 将来の page fault でロックが不要になる可能性
    - 範囲操作が効率的: 重複するすべての VMA を直接検索可能
    - B-tree 派生: キャッシュラインフレンドリー、ノードサイズ可変

Maple Treeの構造

// lib/maple_tree.c
// Maple Tree は B-tree の派生で、各ノードには最大 16 個のスロットがある

// ノードタイプ:
//   MAPLE_NODE_DENSE:  すべてのスロットがデータ (配列に類似)
//   MAPLE_NODE_RANGE:  スロットが範囲情報を持つ (疎なストレージ用)

// 各層で異なる範囲のキーをエンコードできる:
//   Node 0: [0, 4096)     (4K)
//   Node 1: [0, 16777216) (16M)
//   Node 2: [0, 68719476736) (64G)
//   ...
//   最大 8 層 (64ビットキーの場合)

// VMAの場合:
//   key = 仮想アドレス (開始)
//   value = vm_area_struct *
//   検索: mas_find() → 指定されたアドレスを覆う VMA を検索

ロックレス走査

// Maple Tree の RCU安全設計:
//   書き込み側: spinlock を取得 → ノードを変更 (ノードが満杯の場合 → split + コピー)
//   読み取り側: ロックを取得しない → rcu_dereference でノードを読み取り
//           ノードは書き込み側によって直接上書きされることはなく、コピー後に修正される → RCU で古いノードを回収
//
// これこそが Maple Tree の最大の価値:
//   将来の do_page_fault() は RCU read lock 下で VMA を検索できる
//   → mmap_lock (読み取り側) が不要 → mmap_lock のロック競合を解消

Page FaultとVMA検索

// arch/x86/mm/fault.c
// do_page_fault() は最もホットな VMA 検索パス

static void do_page_fault(struct pt_regs *regs, unsigned long error_code) {
    unsigned long address = read_cr2();  // エラー発生した仮想アドレスを取得

    // 1. mmap_read_lock(mm) を取得
    //
    // 2. find_vma(mm, address)
    //    旧: find_vma() → Red-Black木検索
    //    新: find_vma() → mas_find(&mas, address, ...) → Maple Tree検索
    //
    //    見つかった場合: address を覆う VMA を返す
    //    見つからない場合: SIGSEGV
    //
    // 3. VMAの権限をチェック (vm_flags と error_code の比較)
    //    読み込みだが VM_READ が有効でない? → SIGSEGV
    //    書き込みだが VM_WRITE が有効でない? → SIGSEGV (COPY-ON-WRITE時に特に重要!)
    //
    // 4. handle_mm_fault() → 物理ページを割り当て + PTE を構築
    //    匿名: do_anonymous_page() / do_swap_page()
    //    ファイル: do_fault() → filemap_fault()
    //
    // 5. mmap_read_lock(mm) を解放
}

VMAマージ (Merging)

隣接し、属性が同じVMAは自動的にマージされます：

// mm/mmap.c
// vma_merge():
//   新しい mmap リクエストが前後の VMA と比較:
//     vm_flags が同じか?
//     vm_file が同じか? (またはどちらも匿名か)
//     vm_pgoff が連続しているか?
//     PROT が一致するか?
//     anon_vma が互換性があるか?
//   → 条件を満たす場合: 1つの大きな VMA にマージ
//
// なぜマージするのか?
//   VMAの数を減らす → 検索時間の短縮
//   slab割り当てを減らす (vm_area_struct)
//   /proc/<pid>/maps の表示が簡潔になる
//
// 古典的な例:
//   brk() でヒープを拡張 → 複数の小さな拡張 → 自動的に大きな [heap] VMA にマージ

デバッグ

# VMAレイアウト
cat /proc/<pid>/maps  # 人間可読
cat /proc/<pid>/smaps # 各 VMA のメモリ統計 (RSS/PSS/Swap)

# VMA統計
cat /proc/<pid>/status | grep Vm
# VmPeak: 歴史的な最大仮想メモリ
# VmSize: 現在の仮想メモリ総量
# VmRSS:  物理メモリ使用量 (Resident Set Size)
# VmData/VmStk/VmExe/VmLib: データ/スタック/コード/ライブラリ

# VMA数のモニタリング (VMAが多すぎるとパフォーマンスが低下する)
wc -l /proc/<pid>/maps

参考と拡張

• カーネルドキュメント⁠: Documentation/core-api/maple_tree.rst, Documentation/mm/mmap.rst
• LWN:
  • "Introducing the Maple Tree" (lwn.net/Articles/867525/)
  • "The state of the Maple Tree" (lwn.net/Articles/905317/)
  • "mmap_lock and VMA locking" (lwn.net/Articles/909840/)
• ソースファイル⁠:
  • lib/maple_tree.c — Maple Tree 実装
  • mm/mmap.c — VMA管理 (mmap/munmap/mprotect)
  • include/linux/mm_types.h — vm_area_struct 定義
  • arch/x86/mm/fault.c — page fault ハンドラ

キーワード: vm_area_struct, VMA, mmap, munmap, Maple Tree, page fault, find_vma, VM_MERGEABLE, mmap_lock