VMAとMaple Tree：アドレス範囲の作成、変更、競合アクセス

3ページのマッピングの中央の1ページのみをリードオンリーに変更すると、maps には2つの新しいエントリが現れることがあります。中央のページを解除すると、残るホール（隙間）は PROT_NONE とは異なります。ここでは同じ3ページのアドレス空間を追跡し、範囲がどのように変化するかを確認した上で、競合する検索がこれらの変更をどのように保護するかを説明します。

1. VMA は範囲を記述し、ページテーブルはその範囲内の現在の変換を記述する

通常の VMA は半開区間 [vm_start, vm_end) をカバーし、始点を含み終点を含みません。同じ mm_struct 内の通常の VMA は互いに重なり合いませ ん。アドレス空間を共有するスレッドは通常この mm を共有参照するため、1つのスレッドによる mprotect は、他のスレッドが見るマッピング権限を変更します。

手計算：VMA 内のアドレスがファイルのどこに対応するか

基本ページを P、マッピング開始アドレスを A、vm_pgoff=8 とします。アドレス A + 2P + 17 について、2つのステップで位置を特定します。

1. ファイルの8番目の基本ページからマッピングが始まり、さらに2ページ進むと、ファイルの10番目のページになります。
2. ページ内のオフセット 17 を保持し、ファイルのバイトオフセットは 10P + 17 となります。

vm_pgoff の単位は基本ページであり、バイトではありません。また、このファイル記述子以降の read/seek によって進みません。

ファイルの MAP_PRIVATE VMA は、書き込み後、変更されていないファイルキャッシュページと分離された匿名 COW ページの両方を同時にカバーする可能性があるため、vm_file != NULL は「すべてのダーティページがこのファイルに書き戻される」ことを意味しません。通常の共有匿名マッピングは、カーネル内でも shmem ファイルオブジェクトによって支えられている場合があり、ユーザーフラグの MAP_ANONYMOUS と内部 vm_file が NULL かどうかは単純な1対1対応ではありません。

2. 3ページのマッピングで4つの操作を推論する

mmap：まずアドレス空間にコミットメントを作成する

通常の固定されていない mmap はアドレスのヒントを提供できますが、カーネルは既存のマッピングを上書きしない範囲で利用可能な範囲を選択し、権限、ファイル能力、オフセット、リソース制限などのチェックを行い、マッピング関係を確立します。新しい領域が隣接する領域とマージ条件を満たす場合、既存の VMA を直接拡張することがあるため、「1回の mmap で1つの恒久的に識別可能な VMA オブジェクトが作成される」とは限りません。

MAP_FIXED の意味は異なります。これは指定された範囲の使用を要求し、既存のマッピングを置き換えることができます。それは通常のヒントが失敗した場合の無害な強化版ではありません。「このアドレス範囲が完全に空いている場合にのみ占有したい」場合は、MAP_FIXED_NOREPLACE と戻り値のアドレスチェックを理解してください。maps を読んでホールを見つけ、その間に誰も占有していないと仮定して MAP_FIXED を使用しないでください。

通常、データページは必要に応じて作成されますが、MAP_POPULATE、ロック/プリフェッチの要件、デバイスマッピングなどのパスでは追加の作業が行われる可能性があります。ファイル mmap の作成は file_operations の関連インターフェースを介して接続され、vm_operations_struct の fault などのコールバックは後のマッピング操作に使用されます。汎用の vm_ops->mmap() を発明して「すべてのファイルがこれを呼び出す」と主張してはいけません。mmap(2) を参照してください。

mprotect：なぜ1ページだけを変更するのに、2つの記述オブジェクトが増えるのか

[A,A+3P) が元々読み書き可能だったと仮定します。[A+P,A+2P) をリードオンリーに変更すると、これら3セグメントはもはや同じ属性を持たないため、元の1つの VMA では正確に記述できず、前・中・後の3つに分割する必要があります。カーネルは既存のページテーブルに権限変更を適用し、要求に応じて TLB を維持する必要があります。メモリに存在しないページ部分は、新しい VMA のセマンティクスによって将来のページフォルトが制約されます。

これは一見不自然な失敗を説明しています。データメモリを増やすことを要求していないにもかかわらず、mprotect は VMA メタデータの追加が必要になったり、マッピング数の制限を超えたりすることで失敗する可能性があります。「PTE の1ビットを変更するだけ」ではこの現象を説明できません。中央のページを読み書き可能に戻すと、互換性のある隣接セグメントが再結合する可能性がありますが、マージにはバックストアオブジェクト、オフセットの連続性、匿名逆マッピング関係、その他の属性のチェックが必要であり、maps に表示される rw-p の4文字だけを比較することはできません。mprotect(2) を参照してください。

munmap：解除されるのはマッピングであり、データ自体を破棄する必要はない

中央のページを解除すると、中央は真のホールになります。アクセス禁止と比較すると、アドレス空間の占有関係が変化します。

munmap は変換の無効化と対応する参照の解放も行いますが、このステップはデータページの最終寿命を直接決定するものではありません。

ページが他のプロセスと共有されている場合、または通常のファイルページがまだページキャッシュにある場合、このプロセスのマッピング解除は、それを直接 buddy の空きページにはしません。逆に、物理ページがすでに回収されてスワップアウトされている場合、有効な VMA は存在し続けることができます。VMA の寿命、ページテーブルエントリの寿命、およびデータページの寿命は、それぞれ別に推論する必要があります。

mremap：アドレスは可変だが、データはバイト単位でコピーする必要はない

マッピングを拡張する際、隣接範囲が使用できない場合、移動可能な mremap は新しい位置を選択し、ページテーブルマッピングなどの状態を移動することができます。これにより、ユーザーデータの複製を回避できる場合もありますが、メタデータ、ページテーブル、無効化のコストは依然として存在し、すべてのマッピングを自由に移動できるわけではありません。移動に成功すると、旧アドレスおよびそこに保存された絶対自己参照ポインタは、アプリケーションの設計に従って処理する必要があります。「コンテンツが残っている」からといって「すべての元のポインタが有効である」とは限りません。

3つの寿命を同じ画面に置きます。中央のページを最初に読み取り、その後マッピングを解除し、どの範囲、PTE、キャッシュが実際に消去されるかを確認します。マッピングの復元とアクセス権限の復元は、それぞれ別個に操作することもできます。

$$file\_offset=Pvm\_pgoff+(a-vm\_start)$$

この式は、この VMA 内のファイルアドレスに使用されます。a はまず範囲とアクセス条件を満たす必要があり、ホールは計算に含まれません。

3. 実行可能な実験：これらの境界を直接観察する

以下では、5ページの PROT_NONE 空間を保持し、中央の3ページを実験用に使用し、両側をアドレス境界として使用します。各ステップで自身の maps を読み取り、指定されたアドレスの属性を検証します。リードオンリーページの書き込みアドレスにアクセスしたり、プロセスのクラッシュを引き起こしたりしません。

#define _GNU_SOURCE
#include <assert.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

static int permission(uintptr_t address, char output[5]) {
    FILE *file = fopen("/proc/self/maps", "r");
    assert(file != NULL);
    char line[1024];
    int found = 0;
    while (fgets(line, sizeof(line), file)) {
        uintptr_t start, end;
        char mode[5];
        if (sscanf(line, "%" SCNxPTR "-%" SCNxPTR " %4s",
                   &start, &end, mode) == 3 &&
            start <= address && address < end) {
            memcpy(output, mode, 5);
            found = 1;
            break;
        }
    }
    assert(fclose(file) == 0);
    return found;
}
static void check(unsigned char *base, size_t page,
                  const char *middle) {
    for (size_t i = 0; i < 3; ++i) {
        char mode[5] = "";
        int found = permission((uintptr_t)(base + i * page), mode);
        const char *expected = i == 1 ? middle : "rw-p";
        if (expected) {
            assert(found && strcmp(mode, expected) == 0);
        } else {
            assert(!found);
        }
        printf("page %zu: %s\n", i, found ? mode : "hole");
    }
}
int main(void) {
    long size = sysconf(_SC_PAGESIZE);
    assert(size > 0);
    size_t page = (size_t)size;
    unsigned char *whole = mmap(NULL, 5 * page, PROT_NONE,
                               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    assert(whole != MAP_FAILED);
    unsigned char *base = whole + page;
    assert(mprotect(base, 3 * page, PROT_READ | PROT_WRITE) == 0);
    puts("初期:"); check(base, page, "rw-p");
    assert(mprotect(base + page, page, PROT_READ) == 0);
    puts("中央ページをリードオンリーに:"); check(base, page, "r--p");
    assert(mprotect(base + page, page, PROT_READ | PROT_WRITE) == 0);
    puts("権限を復元:"); check(base, page, "rw-p");
    assert(munmap(base + page, page) == 0);
    puts("中央ページをマッピング解除:"); check(base, page, NULL);
    assert(munmap(whole, 2 * page) == 0);
    assert(munmap(whole + 3 * page, 2 * page) == 0);
}

cc -std=c11 -Wall -Wextra -Werror vma-demo.c -o vma-demo でコンパイルし、-DNDEBUG を付けません。チェックはアドレスに基づいて行われ、実際の VMA 境界が mmap リクエストの境界と完全に一致すると仮定せず、権限復元後にカーネルが特定のマージレイアウトを選択することを強要しません。maps が表示するのは VMA の属性であり、中央の3ページが実際に物理ページを割り当てられたことを据此断定することはできません。

4. Maple Tree が解決するのは範囲の整理問題

アドレス空間は複数のクエリに答える必要があります。このアドレスがどのマッピングに含まれるか、次のマッピングはどこにあるか、どの区間がどの VMA と交差するか、そして新しいマッピングを配置するのに十分な大きさのホールがどこにあるか。従来の実装は赤黒木と linked list を協調して使用していましたが、Maple Tree は範囲指向の多分岐構造と反復インターフェースを使用してこれらの作業を引き受け、木の高さの削減、局所性の改善、範囲情報の維持において利点を提供します。

まずクエリがどの程度の結果を返すかを明確にし、その上で木の利点を議論します。

Maple Tree は木の高さ、局所性、範囲の整理を改善しますが、大量のマッピングにまたがる削除とトラバースでは、関連するオブジェクトの規模に比例した作業コストを支払う必要があります。

VMA は半開区間を使用しますが、Maple Tree の範囲インターフェースが終端を含むインデックス範囲を使用する場合、[vm_start, vm_end-1] として表現されます。値は VMA ポインタであり、範囲境界は検索方向を決定するために使用されます。ノードタイプ、スロット数、ピボットレイアウトは実装の詳細です。木はページテーブルのように各レベルでアドレスの特定の9ビットを固定して消費するものではなく、ページテーブルの階層に基づいて Maple Tree に固定のアドレスカバーテーブルを発明することもできません。

ホール情報を保存することで、割り当て検索は、リクエストを収容できないサブツリーをスキップする機会があり、各バイトを順に試す必要がありません。例えば、4P の連続する仮想空間が必要で、合計の空きが 8P であっても、複数の 1P のホールで構成されている可能性があります。範囲インデックスは、十分に長い単一のセグメントを探す必要があります。これは仮想アドレスの断片化であり、buddy 方式で連続する物理ページが見つからない断片化とは異なる問題です。Maple Tree の設計と API を参照してください。

「次の VMA を見つける」ことと「アドレスがカバーされている」ことは等しくない

一部の検索インターフェースは、ホールの中で次の VMA を返すことを許可しています。find_vma(mm, address) の一般的な契約を例にとると、結果は vm_end > address となる最初の VMA になる可能性があります。address < vm_start の場合、アドレスは依然としてホールの中にあります。呼び出し側は、インターフェースのセマンティクスに従ってカバーを再判定する必要があり、戻り値が NULL でないかどうかだけを判断してはいけません。正確なカバーが必要な場合は、対応するインターフェースを選択し、そのロック要件に従ってください。

プローブを区間の末端とホールに停止させ、「どの候補が返されたか」と「候補が実際にカバーしているか」を比較します。終了境界は元の範囲には含まれません。

5. 木を読む、VMA をロックする、ページテーブルをロックする：なぜ1つのロックに合成できないのか

スレッド R がアドレス A でページフォルト し、スレッド W が同時に A に対して munmap を実行しているとします。R が木から VMA ポインタを取得した後、W が範囲を摘出してオブジェクトを回収すると、R がフィールドにアクセスすると use-after-free になる可能性があります。RCU がオブジェクトの回収を遅らせていても、R が読み取る始点、終点、バックストアオブジェクトは、現在のページフォルト 処理を許可する安定した状態を構成する必要があります。

3層の保護、それぞれが異なるオブジェクトを安定させる

rmap 関連のロックは、ページからマッピングを逆引きするためにも使用されます。サポートされるページフォルト パスは per-VMA の処理経路を試すことができるが、保証できない場合はより広範な調整パスに戻る。1つの層で読み取りロックを取得しても、自動的に別の層での書き込み権限が付与されるわけではない。

競合発生時：検証失敗時は再試行

読者 R はまず候補を見つけ、VMA を安定化させてアドレスを検証しようとする。書き手 W は範囲を取り消す前に、プロトコルに従って排他権を取得する。R が必要な保証を確立できない場合、再試行するか、より保守的な mm レベルのロックパスを採用する。

時間のかかる I/O は、ロックの解放、再取得、再検証を要求する可能性がある。待機中に、以前成立していた「アドレスはまだこの VMA 内にある」という状態が変更されている可能性があり、古い検索結果をそのまま続けて使用することはできない。

Maple Tree の RCU 機能は、その一部のみを解決する。ノードのトラバースの並行安全性は、データオブジェクトが長期的に変化しないことを自動的に証明するものではなく、すべての書き手が木全体をコピーして置き換えることを意味するものでもない。現在サポートされているアーキテクチャには per-VMA ページフォルト パスがすでにあり、将来の構想として扱うべきではない。しかし、逆に mmap_lock がすでに消失したと主張することもできない。ロック契約は Process Addresses を参照、対象となるカーネルは lock_vma_under_rcu() などのエントリから特定できる。

6. 最後にページフォルト 処理をこのモデルに戻す

同じ書き込み保護例外でも、処理結果はソフトウェアセマンティクスに依存する。

ハードウェアは現象を報告し、VMA とバックストアの状態が解釈を決定する。したがって、handle_mm_fault() は「範囲を見つけるとページを割り当てる」という統一アクションではない。

VMA が合法であっても、ファイルマッピングアクセスがバックエンドファイルの有効範囲を超えると SIGBUS が発生する可能性がある。割り当ての失敗、特殊マッピング、スワップインにもそれぞれ処理結果がある。したがって、handle_mm_fault() は「VMA が見つかったら新しいページを割り当てる」と要約することはできない。ページキャッシュの再利用、スワップインの処理、プライベートページの分離、または操作契約に従ったアクセス拒否が行われる可能性がある。

トラブルシューティングでは、まず maps で範囲と権限を判断し、次に smaps/smaps_rollup で残留と共有占有を区別し、最後に fault、I/O、メモリ圧力を組み合わせてコストを特定する。大量の mmap/mprotect は VMA 数とメタデータオーバーヘッドを増加させる可能性があるが、maps が長いこと自体がパフォーマンスボトルネックであることを証明するものではない。物理割り当て側の問題は 物理メモリ管理 に続き、残留ページがどのように回収されるかは ページ回収とスワップ を参照。