メモリ管理

					2026年01月15日
情報科学類 オペレーティングシステム II

                                       筑波大学 システム情報系 
                                       新城 靖
                                       <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
https://www.coins.tsukuba.ac.jp/~yas/coins/os2-2025/2026-01-15
あるいは、次のページから手繰っていくこともできます。
https://www.coins.tsukuba.ac.jp/~yas/
https://www.cs.tsukuba.ac.jp/~yas/

■今日の大事な話

物理メモリの管理
- Buddyシステムによる物理メモリの管理
- kmalloc() と kfree()
- スラブアロケータ
仮想メモリの実装
- アドレス空間
- ページテーブル

■メモリ管理

物理メモリを管理する。各メモリのフレームごとに、何に使われているのか、空いているのかを管理する。メモリが必要になったら、空いているものを割り当てる。
カーネル自身の論理アドレス空間を管理し、物理メモリを割り当てる。
ユーザ・プロセスの論理アドレス空間を管理し、物理メモリを割り当てる。
空いているメモリが不足してきたら、ページアウトしたり、プロセスを殺して(Out of memory (OOM) killer) 空きメモリを確保する。

◆目標

外部フラグメンテーションを少なくする。
分かりやすい API
効率のよい実装

■物理メモリの管理

Linux では、搭載されているメモリをページサイズ(4KB-8KBが一般的)で分割し管理する。それを物理ページ(physical page)、あるいは、ページ・フレーム(page frame)と呼ぶ。
1つのページ・フレームには、構造体 struct page で管理する。 struct page の 1 要素で、物理メモリ1ページを管理する。1対1対応。相互に調べられる。
全メモリは、構造体 struct page の配列として保持される。たとえば、ページサイズ 4KB で、1GB の物理メモリを持ったシステムでは、 1024*1024*1024/(4*1024) == 262,144 個の要素からなる配列で管理される。
i 番目の struct page で i 番目のページを表す。
物理メモリ1ページのを割り当てると、それに対応した struct page を返す。
複数ページの物理メモリを割り当てる場合は、その先頭の struct page が返される。

struct page page[]、物理メモリ
図? struct page page[]による物理メモリの管理

注意: 物理メモリを読み書きするには、論理アドレスが必要だが、論理アドレスがない(カーネル空間にマップされていない)こともある。

◆ページ構造体

linux-6.18.2/include/linux/mm_types.h
  78:	struct page {
  79:	        memdesc_flags_t flags;          /* Atomic flags, some possibly
  80:	                                         * updated asynchronously */
...
  95:	                                struct list_head lru;
...
 102:	                        struct address_space *mapping;
...
 183:	        atomic_t _refcount;
...
 202:	        void *virtual;                  /* Kernel virtual address (NULL if
 203:	                                           not kmapped, ie. highmem) */
...
 221:	} _struct_page_alignment;

_refcount: ページの参照カウント。0 か負なら、そのページ・フレームは空いている( 他の目的で使ってよい)ことを意味する。 1以上なら、以下の目的で使われている。
- ページ・キャッシュ(page cache)
- プライベートなデータ
- プロセスのページテーブル
mappping: ページがページ・キャッシュ(ファイルの一部と対応しているメモリ)を保持している時、アドレス空間構造体(struct address_space)と結びつけられる。 mappping フィールドは、そのページがメンバとなっているアドレス空間構造体を指す。アドレス空間構造体が実現している「アドレス空間」とは、 inode等の「メモリ・オブジェクト」1個に属しているページの集まり。
lru: Least Recently Used でメモリ管理を行うための双方向リスト。 active_list (使われているメモリのリスト)か inactive_list (使われていないメモリのリスト、他の目的に使ってもよいメモリのリスト)につながれる。
virtual: そのページのカーネル内のアドレス。 high memory と呼ばれているメモリの場合、これは NULL になっているので、カーネル内のプログラムからアクセスする時には動的にマップする必要がある。

◆ページ構造体のflags(主要部分)

linux-6.18.2/include/linux/page-flags.h enum pageflags

page構造体のflags(主要部分)
PG_locked	ページがピン留めされている。ページアウトされない。入出力の処理中に設定され、完了後に解除される。
PG_referenced	ディスク入出力のために参照されている。
PG_uptodate	ページの内容が有効である。入力処理が完了した。
PG_dirty	ページの内容が変更された。
PG_lru	ページングのための LRU リストにある。
PG_active	ページがアクティブである。
PG_arch_1	アーキテクチャ固有のページ状態
PG_reserved	ページアウト禁止、または、ブード時のメモリ・アロケータで割り当てられた
PG_writeback	書き戻し中
PG_reclaim	開放すべきページ
PG_swapbacked	バックエンドはスワップ領域かRAM
PG_mlocked	vma でロック(ページアウトされいようにセット)されている

◆x86のページ・サイズ

2の12乗(1 << 12)==4096バイト。

linux-6.18.2/include/generated/autoconf.h
  20:	#define CONFIG_PAGE_SHIFT 12

linux-6.18.2/include/vdso/page.h
  13:	#define PAGE_SHIFT      CONFIG_PAGE_SHIFT
  15:	#define PAGE_SIZE       (_AC(1,UL) << CONFIG_PAGE_SHIFT)
  28:	#define PAGE_MASK       (~(PAGE_SIZE - 1))

linux-6.18.2/include/uapi/linux/const.h
  20:	#define __AC(X,Y)       (X##Y)
  21:	#define _AC(X,Y)        __AC(X,Y)

◆メモリ・ゾーン

歴史的な都合やハードウェアの制約で、メモリ・ページを「ゾーン」と呼ばれる領域に分割して管理する。

よく使われるゾーンの種類。

ZONE_DMA: (古いデバイスでも) DMA でアクセス可能なページ・フレーム。 x86 では、0-16M。 ISA バスのデバイスで 0-16M しかアクセスできないものがあった。
ZONE_DMA32: ZONE_DMAと同様に、32ビットのアドレスでアクセスできる範囲。x86_64 (64ビット) で使われる。
ZONE_NORMAL: カーネルの仮想アドレス空間に常にマップされている。古いデバイスのDMA ではアクセスできないが、新しいデバイスのDMA ではアクセスできる。 x86 (32ビット) では、16MB-896MBまで。
ZONE_HIGMEM: x86 (32ビット)で、普段はカーネルの仮想アドレス空間にマップされていない部分。使うときにはマップして使い、使い終わったらアンマップする。

zone、DMA、NORMAL、HIMEM
図? メモリのゾーンへの分割(x86-32)

x86_64 (64ビット) では、DMA, DMA32, Normal が使われる。

zone、DMA、DMA32,Normal、
図? メモリのゾーンへの分割(x86-64)

◆DMA (Direct Memory Access)

DMA は、ハードディスクやネットワークデバイス等で使われているの入出力方法の１つ。通常、メモリは、CPU が制御している。DMA では、周辺デバイスが CPU からメモリの制御を奪い、データの入出力を行う。

DMA の利点

入出力をデバイスにまかせて、CPU はプログラムの実行を行える。
CPU によるメモリのアクセスがないので、CPU のキャッシュが入出力データで汚染されない。

◆ページフレームの割当てと開放

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。

struct page *alloc_pages(gfp_mask,order): 2のorder乗(^order, 1 << order)単位でメモリを割り当てる。先頭のページフレームに対応した struct page へのポインタを返す。
unsigned long __get_free_pages(gfp_mask,order): alloc_pages() と同様にメモリを割り当てる。ただし、リターンするのは、論理アドレス。
struct page *alloc_page(gfp_mask): 1ページ割り当て、struct page へのポインタを返す。
unsigned long __get_free_page(gfp_mask): alloc_page() と同様にメモリを割り当てる。割り当てたメモリの論理アドレスを返す。
unsigned long get_zeroed_page(gfp_mask): __get_free_page() と同様にメモリを割り当て、割り当てたメモリの論理アドレスを返す。メモリは、0 で埋められる。

struct pageへのポインタが得られた場合、メモリは割り当てられているが、論理アドレス不明なので、そのままではプログラムでアクセスできない。論理アドレスが必要なら、void *page_address(page)を使って struct pageへのポインタからアクセス可能な論理アドレスを得ることができる。

次のような手続きで、メモリを開放する。

__free_pages(page,order)
free_pages(addr, order)
free_page(addr)

◆gfp_t gfp_mask

__get_free_pages(), alloc_pages(), alloc_page() や、後述する kmalloc() では、 gfp_t のフラグ(gfp_mask) として、次のものがよく使われる。特に GFP_KERNEL がよく使われる。gfp は、get free pages に由来する。

linux-6.18.2/include/linux/gfp_types.h a

型説明

GFP_ATOMIC 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。

GFP_KERNEL カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。

GFP_NOIO スリープ可、入出力不可。

GFP_NOFS スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。

GFP_USER ユーザ空間用のメモリの通常の方法。スリープ可。

GFP_HIGHUSER HIGHMEMゾーンからの割当て。スリープ可。

GFP_DMA DMAゾーンからの割当て。デバイス・ドライバ等が使う。

GFP_DMA32 DMA32ゾーンからの割当て。デバイス・ドライバ等が使う。

このようなフラグが存在する最も重要な理由は、スリープする可能性があるかないかの違い。その他に、どのゾーンからメモリを割り当てるべきかを表すものがある。

型	説明
GFP_ATOMIC	高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。
GFP_KERNEL	カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。
GFP_NOIO	スリープ可、入出力不可。
GFP_NOFS	スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。
GFP_USER	ユーザ空間用のメモリの通常の方法。スリープ可。
GFP_HIGHUSER	HIGHMEMゾーンからの割当て。スリープ可。
GFP_DMA	DMAゾーンからの割当て。デバイス・ドライバ等が使う。
GFP_DMA32	DMA32ゾーンからの割当て。デバイス・ドライバ等が使う。

◆外部フラグメンテーション

物理フレームの割当てと開放を繰り返していくと、外部フラグメンテーション (external fragmentation) が生じる。全体としては空きメモリは存在しているのに、小さなメモリ・フレームがあちこちに分散していて、大きさのページフレームが存在しないためにメモリが割り当てられない状態に陥る。

◆Buddyシステム

「Buddy システム」は、Linux で使われている外部フラグメンテーションを起こしにくいメモリ割当てアルゴリズム。

buddy とは、仲間の意味。

buddyの例
0 1

2 3

4 5

6 7

0,1 2,3

4,5 6,7

0,1,2,3 4,5,6,7

buddyの例
0	1
2	3
4	5
6	7
0,1	2,3
4,5	6,7
0,1,2,3	4,5,6,7

Buddyシステムでのメモリ管理手法

利用可能なメモリ・ブロックのリストを管理する。リストの数は、MAX_ORDER個。
各リストは、2のべき乗の大きさのメモリ・ブロックを保持する( 2 ⁰, 2 ¹, 2 ², ..., 2 ^{(MAX_ORDER-1)}, )。
ページフレームの割当て(alloc_pages())では、必要な最小のメモリ・ブロックを割り当てる。(大きなブロックを温存する。) 2 ^order が欲しい時に、そのメモリがあれば、それを返す。なければ、2 ^order+1 を探して、それを半分に分割して、返す。（使わなかった分は、2 ^order のリストにつなぐ。）
ページフレームの開放(__free_pages())では、 2 ^order のサイズのブロックを利用可能なリストに接続する。同じ大きさのブロックの中で連続しているもの(buddy)がないかを探す。あれば、結合して大きなブロック(2 ^(order+1)) にしてリストに接続する。

zone、free_area、page
図1(a) Buddyシステムによる空きページの管理(論理的な見方)

zone、free_area、page
図1(b) Buddyシステムによる空きページの管理(線形な見方)

◆Buddyシステムの状態

/proc/buddyinfo を見ると、現在の空きページの状態が分かる。 x86-64 の例。

$ cat /proc/buddyinfo 
Node 0, zone      DMA      1      1      1      1      1      1      1      0      1      1      3
Node 0, zone    DMA32   3544   7608   4945   3129   1783    840    337    121     33      0      0
Node 0, zone   Normal  27583   9215  14233   4512   1288    208    127     20      3      1      0
$

この例では、DMA ゾーンの 2 ⁰ (4KB) に、1 個、2 ¹ (8KB) に、1 個、・・・、2 ¹⁰ に3個の空きがある。外部フラグメンテーションが起きると、大きな塊が少なくなる。

x86 (32ビット)の例

% cat /proc/buddyinfo 
Node 0, zone      DMA      6      5      3      3      4      2      2      0      1      1      2 
Node 0, zone   Normal    476   2577    990    354    174    104     65     34     19      1    135 
Node 0, zone  HighMem   1416   2920   1718   1082    933    504    251    152     87     43     53 
%

この例では、DMA ゾーンの 2 ⁰ (4KB) に、6 個、 2 ¹ (8KB) に、5 個、・・・、2 ¹⁰ に2個の空きがある。外部フラグメンテーションが起きると、大きな塊が少なくなる。

■kmallocとkfree

物理メモリは、ページ単位（4KBのページフレーム単位）で管理している。しかし、カーネル内のデータ構造は、4KB にぴったりはまらない。 Linux でページ単位ではない単位でメモリを確保・開放できるには、次のような方法がある。

kmalloc(), kfree(): malloc(), free() と類似の API
スラブ・アロケータ

◆kmalloc()

C言語のユーザ空間で使えるライブラリ malloc() に似ている。

void *kmalloc(size_t size, gfp_t flags)

引数

size: バイト数
flags: フラグ。gfp_t 型の gfp_mask。スリープしても良いか良くないかやその他の属性を表す。以下の kmalloc()のフラグの選択参照。

結果: 最低限、size 分のメモリを割り当て、その先頭の番地（カーネル内の仮想アドレス）を返す。割り当てられたメモリは、物理的にも連続になる。割当てできない時には、NULL を返す。

◆kmalloc()のフラグの選択

状況	フラグ
プロセスのコンテキスト、スリープ可能	`GFP_KERNEL`
プロセスのコンテキスト、スリープ不可	`GFP_ATOMIC`
割込みハンドラ	`GFP_ATOMIC`
割込みハンドラ後半(Softirq,Tasklet,後述)	`GFP_ATOMIC`
DMA可能なメモリ、スリープ可能	`GFP_DMA\|GFP_KERNEL`
DMA可能なメモリ、スリープ不可	`GFP_DMA\|GFP_ATOMIC`

◆kfree()

void kfree(const void *objp)

C言語のユーザ空間で使えるライブラリ free() と似ている。 kmalloc() で割り当てたメモリを解放する。

◆vmalloc()とvfree()

kmallc()/kfree() と似ているが、割り当てられるメモリは物理的に連続している保証はない。（カーネル空間の仮想アドレスとしては連続している。）

■スラブアロケータ(slab allocator)

同じ大きさの構造体を割り当てる時に使う。 kmalloc(), kfree() よりも、効率がよい。

◆free list方式とその問題点

構造体の割当てには、free list 方式が使われることもある。

構造体を割り当てる時には、free list から取り出す。
free list が空なら、構造体が複数入るような大きなメモリ(ページ単位)を割当て、free list につなぐ。
構造体が使われなくなったら、free list につなぐ。

この方法では、メモリに空きがあっても、解放できるか簡単にはわからない。

free list、オブジェクト4個
図? フリーリストの例

オブジェクトは、1ページに2個入る。オブジェクトが次の順番で開放された。

object 2
object 6
object 3
object 1

free list、オブジェクト4個
図? フリーリストの例(ページを意識)

object 2 と object 3 の部分は、1ページ空いている。

◆スラブ・アロケータの目標

よく使われるオブジェクトは、すぐに開放される傾向にある。その性質を生かすために「キャッシュ」する。
free list では、メモリ・フラグメンテーションが起きる。スラブ・アロケータでは、複数の未使用のメモリをつなげて大きくして、開放できる。
マルチプロセッサでは、CPU ごとに割り当てたるなどして、ロックを減らす。
オブジェクトが別のキャッシュ・ラインに乗るように、「色をつける(colored)」。

スラブ・アロケータ自身は、alloc_pages() 等のページ単位のメモリ割当て機能を呼出してメモリを確保する。

◆ページ・フレーム、スラブ、オブジェクトの関係

ページフレーム３つ、スラブ１つ、オブジェクト６つ
図? ページ・フレーム、スラブ、オブジェクトの関係

オブジェクトの大きさ(構造体の大きさ)は、プログラミングの都合で決まる。ページの大きさとは無関係。
１つのスラブは、ヘッダと複数のオブジェクトから構成される。
小さいオブジェクトは、1スラブが1つのページフレームに収まるようにすることが多い。
１つのスラブが、複数のページフレームにまたがることもある。

◆kmem_cache_create()

4引数(新)か5引数(旧)。

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
        unsigned long flags)

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *))

引数

name: 文字列の名前。/proc/slabinfo で使われる。
size: オブジェクトのサイズ。
align: オブジェクト(構造体)に必要なアラインメント。
flags: フラグ。SLAB_PANIC が指定されると、メモリの割当てに失敗すれば、システムがクラッシュする。SLAB_CACHE_DMA が指定されると、ZONE_DMA のメモリに割り当てられる。
ctor: オブジェクトのコンストラクタ。新しいページが割り当てられる度に呼ばれる関数へのポインタ。

結果: 成功した時には、struct kmem_cache へのポインタ。失敗するとNULL。新しいページが割り当てられた時には、ctor で指定された関数が呼ばれる。

KMEM_CACHE(__struct, __flags)

引数

__struct: 構造体名。(構造体名から自動的に文字列の名前が作られる。)
__flags: フラグ。
(size には、自動的に sizeof(struct __struct) が指定される。)
(align には、自動的に構造体の __alignof__(struct __struct) が指定される。)
(cotr はなし)

◆kmem_cache_destroy()

void kmem_cache_destroy(struct kmem_cache *c)

kmem_cache_create() で割り当てた struct kmem_cache *を開放する。 shutdown (電源を切る操作)で呼ばれることがある。

◆kmem_cache_alloc()とkmem_cache_free()

void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)

void *kmem_cache_alloc_node(struct kmem_cache *cachep,gfp_t flags, int node)

void kmem_cache_free(struct kmem_cache *cachep, void *b)

生成した struct kmem_cache *を使ってオブジェクトのメモリを割り当てる。割り当てたオブジェクトのメモリは、kmem_cache_free()で開放する。

kmem_cache_alloc_node() は、メモリ・アクセスが不均質なマルチプロセッサ用。メモリを割り当てるという働きは、kmem_cache_alloc() と同じ。ただし、 node で指定されたプロセッサで高速にアクセスできるメモリに割り当てられる。

◆利用例(struct cred)

linux-6.18.2/include/linux/slab.h
 478:	#define KMEM_CACHE(__struct, __flags)                                   \
 479:	        __kmem_cache_create_args(#__struct, sizeof(struct __struct),    \
 480:	                        &(struct kmem_cache_args) {                     \
 481:	                                .align  = __alignof__(struct __struct), \
 482:	                        }, (__flags))

linux-6.18.2/kernel/cred.c
  36:	static struct kmem_cache *cred_jar;
...
 556:	void __init cred_init(void)
 557:	{
 558:	        /* allocate a slab in which we can store credentials */
 559:	        cred_jar = KMEM_CACHE(cred,
 560:	                              SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT);
 561:	}

 206:	struct cred *prepare_creds(void)
 207:	{
 208:	        struct task_struct *task = current;
 209:	        const struct cred *old;
 210:	        struct cred *new;
 211:	
 212:	        new = kmem_cache_alloc(cred_jar, GFP_KERNEL);
...
 218:	        old = task->cred;
 219:	        memcpy(new, old, sizeof(struct cred));
...
 245:	        return new;
...
 250:	}

  68:	static void put_cred_rcu(struct rcu_head *rcu)
  69:	{
  70:	        struct cred *cred = container_of(rcu, struct cred, rcu);
...

  89:	        kmem_cache_free(cred_jar, cred);
  90:	}

文字列の名前は、"cred" (以前は "cred_jar")
大きさは、sizeof(struct cred) バイト
align は、 __alignof__(struct cred) 。
SLAB_HWCACHE_ALIGN により、アラインメントをハードウェアのキャッシュ・ラインに合わせる。 SLAB_PANIC により、メモリが割り当てられなければ、panic (システム全体をクラッシュ)する。 SLAB_ACCOUNT は、資源管理(cgroup) 関連。
コンストラクタは、なし(NULL)。
struct cred の割り当ては、prepare_creds() 等で行われる。 (fork() では参照カウンタを増やすだけなので、この関数は呼ばれない。)
開放は、put_cred_rcu() で行われる。

◆/proc/slabinfo

/proc/slabinfo を見ると、スラブアロケータの状態がわかる。

# cat /proc/slabinfo 
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
nfs_direct_cache       0      0    352   23    2 : tunables    0    0    0 : slabdata      0      0      0
nfs_commit_data       92     92    704   23    4 : tunables    0    0    0 : slabdata      4      4      0
...
UDP                  240    240   1088   30    8 : tunables    0    0    0 : slabdata      8      8      0
tw_sock_TCP          160    160    256   16    1 : tunables    0    0    0 : slabdata     10     10      0
TCP                  155    240   1984   16    8 : tunables    0    0    0 : slabdata     15     15      0
...
task_struct          763    784   4224    7    8 : tunables    0    0    0 : slabdata    112    112      0
cred_jar            1588   2982    192   21    1 : tunables    0    0    0 : slabdata    142    142      0
anon_vma           18794  19584     80   51    1 : tunables    0    0    0 : slabdata    384    384      0
pid                 1984   1984    128   32    1 : tunables    0    0    0 : slabdata     62     62      0
...
dma-kmalloc-8192       0      0   8192    4    8 : tunables    0    0    0 : slabdata      0      0      0
dma-kmalloc-4096       0      0   4096    8    8 : tunables    0    0    0 : slabdata      0      0      0
...
dma-kmalloc-16         0      0     16  256    1 : tunables    0    0    0 : slabdata      0      0      0
dma-kmalloc-8          0      0      8  512    1 : tunables    0    0    0 : slabdata      0      0      0
...
kmalloc-8192          74     88   8192    4    8 : tunables    0    0    0 : slabdata     22     22      0
kmalloc-4096         371    392   4096    8    8 : tunables    0    0    0 : slabdata     49     49      0
...
kmalloc-32         47009  48256     32  128    1 : tunables    0    0    0 : slabdata    377    377      0
kmalloc-16        115733 117760     16  256    1 : tunables    0    0    0 : slabdata    460    460      0
kmalloc-8          65406  68608      8  512    1 : tunables    0    0    0 : slabdata    134    134      0
kmem_cache_node      320    320     64   64    1 : tunables    0    0    0 : slabdata      5      5      0
kmem_cache           160    160    256   16    1 : tunables    0    0    0 : slabdata     10     10      0
#

スラブ・アロケータには、２種類ある。

専用。たとえば、task_struct なら、sizeof(struct task_struct) としてキャッシュに保存。前半に表示される。
汎用。いくつかの大きさのメモリ。8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192。後半の size-番号 。 DMA が付いているものは、DMA 可能なメモリ。

■ユーザ・プロセスの仮想メモリの実現

◆OSに求められる機能(オペレーティングシステム(I)復習)

1台のコンピュータで複数のプロセスを走らせる(multiprogramming)。
プロセスは、それぞれ独立したアドレス空間を持つ。多重(仮想)アドレス空間(multiple (virtual) address spaces)
仮想記憶(virtual memory)を実現する。物理メモリよりも大きなメモリを利用可能にする。ディスクを二次記憶として使って。
物理メモリを固定長のページ・フレーム(page frame)に分割する。
プロセスの仮想アドレス空間は、ページ(page)の並びに分割する。
ページの大きさとページ・フレームの大きさは、同じ。ページ・サイズと呼ぶ。ページ・サイズは、2のべき乗の大きさ。4KB-64KB が多い。
任意のページは、任意のページ・フレームにマップできる。
CPU は、プログラムを実行中に仮想アドレス(virtual address)を出力して、機械語命令やデータをアクセスする。
MMU (Memory Management Unit) は、仮想アドレスを物理アドレス(physical address) に変換する。
MMU は、メモリ中に作られたページテーブル(page table)を見ながら変換する。ページテーブルは、仮想アドレスと物理アドレスの対応表。
しばらく使わないページの内容を、ディスクに退避する(page out)。
ディスクから要求されているページの内容をメモリにコピーする（page in）
ページアウトされているメモリをアクセスすると、ページフォールト(page fault) が発生する。 OSは、ページインの処理を行い、再開する。
仮想アドレスの大きさは、普通、32ビットのシステムなら、32ビット。 64ビットのシステムなら、64ビット。
物理アドレスの大きさは、搭載しているメモリのサイズによる。 32ビットのシステムでも、4GB 以上のメモリを搭載している時には、 64ビットの物理アドレスが使われることがある。 (物理的な配線は、64本より少ないことがある。)

x86 には、その他、Multics 由来の「セグメント」がある。Linux 等の複数アーキテクチャで動作する OS は、x86 依存の機能には依存しない形で設計される。

◆Unixにおけるメモリに関するシステム・コールとライブラリ

システム・コール

execve(): メモリ中のプログラムを入れ替える。アドレス空間を作る。
mmap(): ファイルをメモリにマップする。
brk(), sbrk(): ヒープメモリを増やす。
mprotect(): メモリの保護モードを変更する。
mlock(): メモリをページアウトされないようにする（pinning、ピン留め）
munlock(): mlock() でピン留めした状態を解除する。

ライブラリ

malloc(): ヒープからメモリを割り当てる。(原資は、mmap(), brk(), sbrk() で得る。)
free(): malloc() で割り当てたメモリを解放する。

その他

スタックの自動拡張。(許された範囲(ulimit -s)で)、自動的にスタックを大きくする。

◆Unixにおけるプロセスのアドレス空間の基本的な構造

テキスト、データ、ＢＳＳ、スタック
図? プロセスのアドレス空間の構造(64ビット)

テキスト、データ、スタックの３つに分割
テキストは、機械語命令を入れる。読み込み専用。
データは、大域変数、静的変数、malloc() 等で確保したデータを置く。3つに分割。
- データ。初期値付きの変数。
- BSS。初期値なしの変数。OSが自動的に0に初期化。
- ヒープ。malloc() で確保。
スタックには、関数の局所変数(auto変数、static が付かないもの)、関数の引数が置かれる。
スタックの底には、引数と環境変数が置かれる。
スタックは、高い番地から低い番地へ伸びる。
ヒープは、低い番地から高い番地へ伸びる。
0番地付近は、メモリを割り当てないことが一般的。NULLポインタの利用ですぐに落ちる。

Linux x86 (32ビット) では、32ビットのアドレス空間 0x00000000-0xffffffff のうち0xc0000000-0xffffffff の間は、オペレーティング・システム・カーネルが使うので、ユーザ空間では使えない。

◆実行形式の構造

Linux では、実行形式として ELF(Executable and Linkable Format) が使われている。ELF ファイルは、readelf コマンドや objdump で容を観察できる。

ELF ファイルは、ヘッダとセクションの並びからなる。重要なセクションには、.text, .rodata, .data がある。

$ file hello.c 
hello.c: C source, ASCII text
$ cat hello.c 
#include <stdio.h>
int main()
{
        printf("hello, %s!\n","world");
}
$ cc -o hello hello.c 
$ file hello 
hello: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked
 (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=68c4fff13c07df8738b2e
0f20a27f9a03a20f5c1, not stripped
$ size hello 
   text	   data	    bss	    dec	    hex	filename
   1234    548        4    1786     6fa	hello
$ readelf -S hello 
There are 30 section headers, starting at offset 0x1928:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         0000000000400238  00000238
       000000000000001c  0000000000000000   A       0     0     1
...
  [13] .text             PROGBITS         0000000000400440  00000440
       0000000000000182  0000000000000000  AX       0     0     16
...
  [15] .rodata           PROGBITS         00000000004005d0  000005d0
       0000000000000022  0000000000000000   A       0     0     8
...
  [24] .data             PROGBITS         0000000000601030  00001030
       0000000000000004  0000000000000000  WA       0     0     1
  [25] .bss              NOBITS           0000000000601034  00001034
       0000000000000004  0000000000000000  WA       0     0     1
...
  [27] .symtab           SYMTAB           0000000000000000  00001068
       00000000000005e8  0000000000000018          28    46     8
...
$

◆execve() システム・コール

システムプログラムの講義資料参照。

int execve(const char *filename, char *const argv[], char *const envp[])

filename は、普通、ELF 形式等の実行形式。 #!でインタプリタを指定することもできる。
argv は、main の引数。
envp は、環境変数。

■Linuxにおけるユーザプロセスのアドレス空間の実装

◆アドレス空間とメモリ・エリア

利用者プロセスのプログラムは、線形な(linear)アドレス空間で仮想アドレスを使って機械語命令を読み出したり、データを読み書きする。

32ビットシステムで、0x00000000-0xffffffff
64ビットシステムで、0x00000000-0xffffffffffffffff (実際には、全部は使わない。 0xffffffffffff (48ビット) か 0x1ffffffffffffff (57 ビット)。)

(x86 では、セグメンテーションも使えるので、線形ではないアドレス空間も可能だが、Linux では、他のアーキテクチャとの兼ね合いもあり、線形な空間を使う。)

線形なアドレス空間は、メモリ・エリア(memory area)(または、memory region、memory interval)に分割される。

メモリ・エリアには、開始番地と終了番地（または大きさ）がある。
メモリ・エリア毎に保護方法を変えられる。テキストを読み込み専用 (read-only)にするなど。
メモリ・エリア毎にファイルに対応させられる。

◆task_struct構造体とmm_struct構造体

カーネル内では、プロセス(単一スレッド)のメモリは、次の構造体で表される。

構造体 task_struct: 1プロセスで1個。
構造体 mm_struct: 普通、1プロセスで1個。(複数プロセスで共有されていることがある。)
構造体 vm_area: 1プロセスで複数。

linux-6.18.2/include/linux/sched.h
 819:	struct task_struct {
...
 961:	        struct mm_struct                *mm;
...
1668:	} __attribute__ ((aligned (64)));

tast_struct の mm フィールド

mm_alloc() で割当て。execve() の処理の途中で呼ばれる。
copy_mm() でコピーされる。fork() の処理の途中で呼ばれる。
exit_mm() で後始末。exit() (自発的な終了) の処理の途中や、強制終了させられた時の処理で呼ばれる。

◆mm_struct構造体

linux-6.18.2/include/linux/mm_types.h
 944:	struct mm_struct {
...
 958:	                        atomic_t mm_count;
...
 961:	                struct maple_tree mm_mt;
...
 971:	                pgd_t * pgd;
...
 992:	                atomic_t mm_users;
...
1035:	                int map_count;                  /* number of VMAs */
...
1054:	                struct list_head mmlist;
...
1111:	                unsigned long start_code, end_code, start_data, end_data;
1112:	                unsigned long start_brk, brk, start_stack;
1113:	                unsigned long arg_start, arg_end, env_start, env_end;
...
1237:	};

mm_mt: vm_area_struct を保持するための maple_tree (B木)。
pgd: page global drectory へのポインタ。後述。
mm_users: 共有されている場合、そのプロセスの数。普通は、1。
mm_count: この構造体の参照カウンタ。0ならどのオブジェクトがも指されていない。
mmlist: mm_struct 構造体のリストを作るためのフィールド。
start_code, end_code: テキスト・セグメントの開始番地と終了番地。
start_brk, brk: ヒープの開始番地と終了番地。
start_stack: スタックの開始番地。
arg_start, arg_end: 引数の開始番地と終了番地。
env_start, env_end: 環境変数の開始番地と終了番地。

◆vm_area_struct構造体

linux-6.18.2/include/linux/mm_types.h
 813:	struct vm_area_struct {
...
 819:	                        unsigned long vm_start;
 820:	                        unsigned long vm_end;
...
 829:	        struct mm_struct *vm_mm;
 830:	        pgprot_t vm_page_prot;          /* Access permissions of this VMA. */
...
 837:	                const vm_flags_t vm_flags;
...
 869:	        const struct vm_operations_struct *vm_ops;
...
 874:	        struct file * vm_file;          /* File we map to (can be NULL). */
...
 917:	} __randomize_layout;

vm_start, vm_end: メモリ・エリアの開始番地と終了番地。
vm_mm: 親の mm_struct 構造体へのポインタ
vm_page_prot: ページ単位の保護モード(proection)。PTE で使う。ハードウェア依存。
vm_flags: フラグ。下の表参照。
vm_ops: 関数へのポインタ。opsは、operations。open, close, unmap　を含む。
vm_file: 対応しているファイル。

vm_area_structのvm_flagsの値(include/linux/mm.h)
フラグ	説明
VM_READ	読み込み可
VM_WRITE	書き込み可
VM_EXEC	実行可
VM_SHARED	共有されている
VM_GROWSDOWN	アドレスが小さい方に伸びる
VM_GROWSUP	アドレスが大きい方に伸びる
VM_LOCKED	ロックされている。
VM_DONTCOPY	fork() でコピーしない
VM_DONTEXPAND	mremap()で拡張不可。

◆プロセスのアドレス空間の実装

プロセスのアドレス空間は、次のような領域に分割されて実装されている。

mm_struct、アドレス空間、maple tree、vm_area、実行形式ファイル
図? プロセスのアドレス空間の実現

各領域には、struct vm_area_struct が対応している。
テキストとデータ(初期値付き)は、vm_area_struct を経由して、実行形式のファイルと結びついている。最初にアクセスされた時に実行形式のファイルから読み込まれる。
BSS、ヒープ、スタックは、ファイルと結びついていない。最初にアクセスされた時に、0 で埋められたページ・フレーム(anonymous page)が割り当てられる。

各領域は、次のように実装されている。

テキスト: 機械語を置く。VM_EXEC 属性と VM_READ属性が付いている。書き込み禁止で共有可能。mm_struct の start_code と end_code が、開始番地と終了番地を保持する。
データ(初期値付き): データを置く。VM_READ|VM_WRITE 属性が付いている(以下同様)。共有不可。ファイルに初期値が含まている。
BSS(初期値無しデータ): 0 で初期化されるデータを置く。ファイルに初期値が含まれない。
ヒープ: データを置く。malloc() の原資(の１つ)。brk() や sbrk() システム・コールで大きさが変更される。番地が大きい方に伸びる。mm_struct の start_brk とbrk が開始番地と終了番地を保持する。
スタック: 関数呼び出しのスタックが置かれる。スタック・ポインタが指す。局所変数や関数の戻り番地が置かれる。スタックポインタが下限を越えて小さくなると、自動拡張されることがあるる

◆プロセスのアドレス空間のレイアウト(動的リンクライブラリ)

元の実行形式に由来するテキスト、データ、スタックの他に、動的リンク・ライブラリに由来するテキストやデータのためのメモリ・エリアが作られる。 /proc/PID/maps というファイルを見ると、その様子が分かる。

$ echo $$ 
1808928
$ ls /proc/$$ 
attr		    cpuset   loginuid	 numa_maps	sched	      status
autogroup	    cwd      map_files	 oom_adj	schedstat     syscall
auxv		    environ  maps	 oom_score	sessionid     task
cgroup		    exe      mem	 oom_score_adj	setgroups     timens_offsets
clear_refs	    fd	     mountinfo	 pagemap	smaps	      timers
cmdline		    fdinfo   mounts	 patch_state	smaps_rollup  timerslack_ns
comm		    gid_map  mountstats  personality	stack	      uid_map
coredump_filter     io	     net	 projid_map	stat	      wchan
cpu_resctrl_groups  limits   ns		 root		statm
$ cat /proc/$$/maps 
55adebbdd000-55adebce5000 r-xp 00000000 fd:00 402654849                  /usr/bin/bash
55adebee5000-55adebee9000 r--p 00108000 fd:00 402654849                  /usr/bin/bash
55adebee9000-55adebef2000 rw-p 0010c000 fd:00 402654849                  /usr/bin/bash
55adebef2000-55adebefc000 rw-p 00000000 00:00 0
55aded31f000-55aded529000 rw-p 00000000 00:00 0                          [heap]
...
7f7358592000-7f735875f000 r-xp 00000000 fd:00 224854                     /usr/lib64/libc-2.28.so
7f735875f000-7f735895e000 ---p 001cd000 fd:00 224854                     /usr/lib64/libc-2.28.so
7f735895e000-7f7358962000 r--p 001cc000 fd:00 224854                     /usr/lib64/libc-2.28.so
7f7358962000-7f7358964000 rw-p 001d0000 fd:00 224854                     /usr/lib64/libc-2.28.so
7f7358964000-7f7358968000 rw-p 00000000 00:00 0
...
7fffeea18000-7fffeea39000 rw-p 00000000 00:00 0                          [stack]
7fffeeb2a000-7fffeeb2e000 r--p 00000000 00:00 0                          [vvar]
7fffeeb2e000-7fffeeb30000 r-xp 00000000 00:00 0                          [vdso]
$ wc /proc/$$/maps 
40 235 3620 /proc/1808928/maps
$ wc /proc/$$/maps 
40 235 3620 /proc/1808928/maps
$

/proc/PID/maps のフィールドの意味

メモリ・セグメントの開始番地と終了番地。
アクセス許可。r(read), w(write), x(executable), p(private), s(shared)
オフセット
ブロック・デバイスのメジャー番号とマイナー番号。 fd:0 なら、メジャー番号が、fd(253)、マイナー番号が0の意味。デバイスに結びついていない場合には、00:00 になる。
ファイルのinode番号。
ファイル名。

ブロック・デバイスには、メジャー番号とマイナー番号がある。各ファイルには、inode 番号がある。これらの3つの番号がわかると、カーネル内ではファイルを特定できる。(同じ inode 番号のファイルは、1つのブロック・デバイス内では、1個しかない。) ファイル名は不要だが、/proc/PID/maps では、人間にとって分かりやすいようにわざわざ表示している。

ブロック・デバイスのメジャー番号とマイナー番号は、ls -l でわかる。

$ ls -l /dev/dm-0 
brw-rw---- 1 root disk 253, 0 Dec 25 10:26 /dev/dm-0
$

ファイルの inode 番号は、ls -i でわかる。

$ ls -li /bin/bash /usr/lib64/libc-2.28.so 
402654849 -rwxr-xr-x 1 root root 1154680  7月  7  2025 /bin/bash
   224854 -rwxr-xr-x 1 root root 2164784 11月 21 02:12 /usr/lib64/libc-2.28.so
$

■ページテーブル

◆仮想アドレスと物理アドレス

メモリには、物理アドレスがふられている。
ユーザ・プロセスが実行されると、CPUは、仮想アドレス(virtual address) を出力する。
仮想アドレスのうち、上位は、MMU (MMU) により変換する。
仮想アドレスのうち、下位(ページサイズ分)は、そのままメモリに送られる。

MMU による変換方法は、ページテーブルに保存される。

CPU、MMU、ページテーブル、メモリ
図? MMUによる仮想アドレスから物理アドレスへの変換

◆1段のページ・テーブル

仮想アドレスの構成の例。 1ページが4KB (4096, 0x1000)で、仮想アドレスが32ビットの時。

p: 31..12ビット。ページテーブルのインデックス (20ビット)
offset: 11..0。ページ内オフセット (12ビット)

p(20ビット)+offset
図? 1段のページテーブル

ページテーブルは、次のような配列になる。

unsigned long int page_table[0x100000];

この配列の要素は、ページ・フレームの先頭番地(物理アドレス)。

MMU(ハードウェア) は、このページテーブルを使って、次のようにして仮想アドレスから物理アドレスを求める。以下は、MMU の動きを C 言語で説明したもの。

unsigned long int physical_address( unsigned long int virtual v ) {
    unsigned long int p, page, offset;
    p = v >> 12;         // 32中、上位20ビット(32-12==20)の取り出し
    offset = v & 0xfff;  // 下位 12 ビットの取り出し
    page = page_table[p];
    return( page + offset );
}

mm_struct、page_table、page frame
図? 1段のページテーブル

注意: 白い部分は、0 が入っている。0 の部分は、ページ・フレームが割り当てられていないことを意味する。0 を保持するためにも、メモリが必要である。

page_table[] は、0x100000 個 == 1024 * 1024 個 == 1M 個の要素からなる。 1要素が 4 バイト(32ビット) なら、4MB のメモリが必要になる。

◆多段のページ・テーブル

実際のプロセスでは、使われていない空間が圧倒的に多い。１段のページテーブルでは、ページテーブルを保持するためのメモリが多くなってしまう。多くのCPUでは、多段のページテーブルを採用している。アドレス空間のうち、使われていない部分のポインタを NULL にする。 Linux では、最大5段のページテーブルを想定している。

仮想アドレスの構成の例。 1ページが4KB、仮想アドレスが32ビットの時の分割の例(他の分割方法も考えられる)

p: 31..28ビット。PGDのインデックス(4ビット)
q: 27..24ビット。P4Dのインデックス(4ビット)
r: 23..20ビット。PUDのインデックス(4ビット)
s: 19..16ビット。PMDのインデックス(4ビット)
t: 15..12ビット。PTEのインデックス(4ビット)
offset: 11..0ビット。ページ内オフセット(12ビット)

4+4+4+4+4+12
図? 仮想アドレス上位20ビットの5つの部分への分割例

mm_struct、PGD、P4D、PUD、PMD、PTE、page frame
図? 5段のページテーブル

PGD: Page Global Directory
P4D: Page (Level-4?) Directory
PUD: Page Upper Directory
PMD: Page Middle Directory
Page Table Entryの配列 (pte の配列)

unsigned int pgd[0x10];

unsigned long int physical_address( unsigned long int virtual v ) {
    unsigned int *pud, *p4d, *pmd, *pte, p, q, r, s, t, page, offset;
    p = v >>  (32-4) ;
    q = (v >> (32-8)) & 0xf;
    r = (v >> (32-12)) & 0xf;
    s = (v >> (32-16)) & 0xf;
    t = (v >> (32-20)) & 0xf;
    offset = v & 0xfff;
    p4d = pgd[p];
    pud = p4d[q];
    pmd = pud[r];
    pte = pmd[s];
    page = pte[t]
    return( page + offset );
}

◆x86のページ・テーブル

x86 では、従来、2段のページテーブルを用いている。次のように対応させている。

p が 10 ビット (31..22ビット)
q が 0 ビット
r が 0 ビット
s が 0 ビット
t が 10 ビット (21..12ビット)
offset が 12 ビット (11..0ビット)

10+10+12
図? 仮想アドレス位20ビットの2つの部分への分割例

mm_struct、pgd、pte、page frame。
図? x86の2段のページテーブル

◆x86のページ・テーブル(PAE有効)

x86 で PAE（Physical Address Extension) が有効の時には、次のようになる。 PAE を使うと、仮想アドレスは、32ビットであるが、物理アドレスは、36ビットまで使えるようになる。

p が 2 ビット
q が 9 ビット
r が 0 ビット
s が 0 ビット
t が 9 ビット
offset が 12 ビット

◆x86_64のページ・テーブル(4レベル)

x86_64 (64ビット) では、仮想アドレスとして 48 ビットつかう。ページサイズは、4KB、ページテーブルの単数は、4 段である。

p が 9 ビット
q が 0 ビット
r が 9 ビット
s が 9 ビット
t が 9 ビット
offset が 12 ビット

◆x86_64のページ・テーブル(5レベル)

x86_64 (64ビット) では、仮想アドレスとして 57 ビットつかう。ページサイズは、4KB、ページテーブルの単数は、5 段である。

p が 9 ビット
q が 9 ビット
r が 9 ビット
s が 9 ビット
t が 9 ビット
offset が 12 ビット

◆TLB (Translation Look-aside Buffer)

(多段の)ページテーブルを毎回のメモリ・アクセスでたどっていたら遅くてしょうがない。実際には、一度変換した結果を、TLB (Translation Look-aside Buffer) と呼ばれるキャッシュに保存しておき、ページテーブルをたどる操作はそんなには行わないようにする。

■ページ・フォールト

メモリが割り当てられていない場所をプロセスがアクセスした時には、ページ・フォールトが発生する。

正しいアドレスを最初にアクセスした場合
- ページテーブルがなければ作る。
- ページ・フレームが割り当てられていなければ、割り当てる。
- ファイルと対応していれば、ファイルから内容を読み込む。対応していなければ、0 で埋める。
正しいアドレスを２回目以降にアクセスした場合
- ページインの処理を行う
不正なアドレスをアクセス
- エラー(EFAULT等) でプロセスを終了させる

x86 では関数 handle_page_fault() がこのような処理を行う。この関数は、権限外のアクセス、たとえば、書き込み禁止のメモリに書き込みを試みた場合のエラーも処理する。

◆handle_page_fault()

linux-6.18.2/arch/x86/include/asm/idtentry.h
 180:	#define DEFINE_IDTENTRY_RAW_ERRORCODE(func)                             \
 181:	__visible noinstr void func(struct pt_regs *regs, unsigned long error_code)

linux-6.18.2/arch/x86/mm/fault.c
1488:	DEFINE_IDTENTRY_RAW_ERRORCODE(exc_page_fault)
1489:	{
...
1491:	        unsigned long address;
1492:	
1493:	        address = cpu_feature_enabled(X86_FEATURE_FRED) ? fred_event_data(regs) : read_cr2();
...
1532:	        handle_page_fault(regs, error_code, address);
...
1536:	}

1463:	static __always_inline void
1464:	handle_page_fault(struct pt_regs *regs, unsigned long error_code,
1465:	                              unsigned long address)
1466:	{
...
1473:	        if (unlikely(fault_in_kernel_space(address))) {
1474:	                do_kern_addr_fault(regs, error_code, address);
1475:	        } else {
1476:	                do_user_addr_fault(regs, error_code, address);
...
1485:	        }
1486:	}

1208:	static inline
1209:	void do_user_addr_fault(struct pt_regs *regs,
1210:	                        unsigned long error_code,
1211:	                        unsigned long address)
1212:	{
1213:	        struct vm_area_struct *vma;
1214:	        struct task_struct *tsk;
1215:	        struct mm_struct *mm;
1216:	        vm_fault_t fault;
1217:	        unsigned int flags = FAULT_FLAG_DEFAULT;
1218:	
1219:	        tsk = current;
1220:	        mm = tsk->mm;
...
1327:	        vma = lock_vma_under_rcu(mm, address);
1328:	        if (!vma)
1329:	                goto lock_mmap;
...
1336:	        fault = handle_mm_fault(vma, address, flags | FAULT_FLAG_VMA_LOCK, regs);
...
1356:	lock_mmap:
...
1359:	        vma = lock_mm_and_find_vma(mm, address, regs);
...
1387:	        fault = handle_mm_fault(vma, address, flags, regs);
...
1450:	}

exc_page_fault() は、ハードウェア依存のコード。 arch/x86 の下にある。 x86 で CPU により例外(exception)が検出されたと時に呼ばれる。
address には、ページ・フォールトが生じたアドレスが含まれている。 x86 の cr2 (control register 2) から取得できる。
exc_page_fault() は、handle_page_fault() を呼ぶ。 handle_page_fault() は、address がユーザ空間の番地であれば、 do_user_addr_fault() を呼ぶ。
do_user_addr_fault() では、まず current を参照し、 tsk に現在実行中のプロセスの task_struct を保持する。
mm に現在実行中のプロセスの mm_struct を保持する。
Linux カーネルに出てくる likely() や unlikely() は、高速化のためのヒントなので、意味を把握する時には存在しないものとしてよい。
lock_vma_under_rcu() で、vm_area_struct を探す。見つからなければ、 lock_mm_and_find_vma() で探す。これは、 maple tree を使って高速に vm_area_struct を探す。
handle_mm_fault() を呼び、ページテーブルを作る。

◆handle_mm_fault()

mm/memory.c は、アーキテクチャから独立したコード。

linux-6.18.2/include/linux/mm.h
 562:	struct vm_fault {
...
 606:	};

linux-6.18.2/mm/memory.c
6470:	vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
6471:	                           unsigned int flags, struct pt_regs *regs)
6472:	{
6473:	        /* If the fault handler drops the mmap_lock, vma may be freed */
6474:	        struct mm_struct *mm = vma->vm_mm;
...
6484:	        if (!arch_vma_access_permitted(vma, flags & FAULT_FLAG_WRITE,
6485:	                                            flags & FAULT_FLAG_INSTRUCTION,
6486:	                                            flags & FAULT_FLAG_REMOTE)) {
6487:	                ret = VM_FAULT_SIGSEGV;
6488:	                goto out;
6489:	        }
...
6505:	                ret = __handle_mm_fault(vma, address, flags);
...
6533:	        return ret;
6534:	}

6245:	static vm_fault_t __handle_mm_fault(struct vm_area_struct *vma,
6246:	                unsigned long address, unsigned int flags)
6247:	{
6248:	        struct vm_fault vmf = {
6249:	                .vma = vma,
6250:	                .address = address & PAGE_MASK,
6251:	                .real_address = address,
6252:	                .flags = flags,
6253:	                .pgoff = linear_page_index(vma, address),
6254:	                .gfp_mask = __get_fault_gfp_mask(vma),
6255:	        };
6256:	        struct mm_struct *mm = vma->vm_mm;
6257:	        vm_flags_t vm_flags = vma->vm_flags;
6258:	        pgd_t *pgd;
6259:	        p4d_t *p4d;
6260:	        vm_fault_t ret;
6261:	
6262:	        pgd = pgd_offset(mm, address);
6263:	        p4d = p4d_alloc(mm, pgd, address);
...
6267:	        vmf.pud = pud_alloc(mm, p4d, address);
...
6297:	        vmf.pmd = pmd_alloc(mm, vmf.pud, address);
...
6336:	        return handle_pte_fault(&vmf);
6337:	}

ページテーブルを pgd, p4d, pud, pmd の順に割り当てていく。
最後に pte を handle_pte_fault() で作る。

◆handle_pte_fault()

linux-6.18.2/mm/memory.c
6151:	static vm_fault_t handle_pte_fault(struct vm_fault *vmf)
6152:	{
...
6180:	                vmf->pte = pte_offset_map_rw_nolock(vmf->vma->vm_mm, vmf->pmd,
6181:	                                                    vmf->address, &dummy_pmdval,
6182:	                                                    &vmf->ptl);
...
6185:	                vmf->orig_pte = ptep_get_lockless(vmf->pte);
6186:	                vmf->flags |= FAULT_FLAG_ORIG_PTE_VALID;
...
6194:	        if (!vmf->pte)
6195:	                return do_pte_missing(vmf);
6196:	
6197:	        if (!pte_present(vmf->orig_pte))
6198:	                return do_swap_page(vmf);
...
6237:	}

4357:	static vm_fault_t do_pte_missing(struct vm_fault *vmf)
4358:	{
4359:	        if (vma_is_anonymous(vmf->vma))
4360:	                return do_anonymous_page(vmf);
4361:	        else
4362:	                return do_fault(vmf);
4363:	}

5820:	static vm_fault_t do_fault(struct vm_fault *vmf)
5821:	{
5822:	        struct vm_area_struct *vma = vmf->vma;
5823:	        struct mm_struct *vm_mm = vma->vm_mm;
5824:	        vm_fault_t ret;
...
5829:	        if (!vma->vm_ops->fault) {
...
5849:	        } else if (!(vmf->flags & FAULT_FLAG_WRITE))
5850:	                ret = do_read_fault(vmf);
5851:	        else if (!(vma->vm_flags & VM_SHARED))
5852:	                ret = do_cow_fault(vmf);
5853:	        else
5854:	                ret = do_shared_fault(vmf);
...
5861:	        return ret;
5862:	}

5696:	static vm_fault_t do_read_fault(struct vm_fault *vmf)
5697:	{
..
5716:	        ret = __do_fault(vmf);
...
5725:	        return ret;
5726:	}

5254:	static vm_fault_t __do_fault(struct vm_fault *vmf)
5255:	{
5256:	        struct vm_area_struct *vma = vmf->vma;
...
5258:	        vm_fault_t ret;
...
5281:	        ret = vma->vm_ops->fault(vmf);
...
5307:	        return ret;
5308:	}

pte がまっさら(初めてアクセスされた)
- do_anonymous_page() で処理。0 で初期化されたページを割り当てる。
- do_fault(), do_read_fault(), __do_fault() で処理。
  - vma->vm_ops->fault(vmf)で処理。 ELF 形式の実行形式や共有ライブラリから機械語命令やデータを読み出す。
pte がまっさらではない
- ...
- do_swap_page() でページイン。仮想記憶の二次記憶(ディスク、スワップ領域)から１ページ読み出す。

◆maple tree

maple tree は、B木の一種。

キーは、0 から ULONG_MAX まで。オーバーラップしない。
保存: mtree_store(), mtree_store_range() 等。
検索: mtree_load(), mt_find() 等。
削除: mtree_erase() か mtree_store() で NULL を保存。
struct ma_state に中間状態を保存するAPIがある。mas_find() 等。

以前は、赤黒木(red-black tree)が使われていた所が、maple tree への置き換えられた。参考

◆maple treeでvm_area_structを探す

linux-6.18.2/mm/mmap_lock.c
 424:	struct vm_area_struct *lock_mm_and_find_vma(struct mm_struct *mm,
 425:	                        unsigned long addr, struct pt_regs *regs)
 426:	{
 427:	        struct vm_area_struct *vma;
...
 432:	        vma = find_vma(mm, addr);
...
 434:	                return vma;
...
 477:	}

linux-6.18.2/mm/mmap.c
 904:	struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 905:	{
 906:	        unsigned long index = addr;
...
 909:	        return mt_find(&mm->mm_mt, &index, ULONG_MAX);
 910:	}

■課題2 メモリ管理

★問題(201) Buddyシステム

図1 Buddyシステムによる空きページの管理次のようなメモリ確保の要求と開放がなされた時に、どのようなページが返されるか。ページ・フレーム番号で答えなさい。

1ページの確保
1ページの確保
1ページの確保
1ページの確保
1ページの確保

★問題(202) kmalloc()とkfree()

以下は、ユーザ空間でメモリを割当て、利用し、開放するプログラムの一部である。

struct s1 {
   /* 省略 */
};
利用
   struct s1 *p;
   p = malloc( sizeof(struct s1) );
   use( p );
   free( p );

このプログラムを、カーネル内で動かすことを想定してkmalloc() と kfree() を使って書き換えなさい。ただし、gfp のフラグとしては、GFP_KERNEL を使いなさい。

利用
   struct s1 *p;
   /*回答*/
   use( p );
   /*回答*/

★問題(203) スラブアロケータ

問題(202) のプログラムを、スラブアロケータを使って書き換えなさい。すなわち、kmem_cache_create()、kmem_cache_alloc()、および、 kmem_cache_free()を使って書き換えなさい。ただし、kmem_cache_create() の第3引数のalign としては、0を、第4引数のflagsとしては、SLAB_PANIC、第5引数のコンストラクタとしては、NULL を指定しなさい。

初期化
   /*回答*/

利用
   struct s1 *p;
   /*回答*/
   use( p );
   /*回答*/

★問題(204) 1段のページテーブル

仮想アドレスのサイズが32ビット、1ページの大きさが4KBとする。次の３ページが割り当てられてしたとする。

0x00000000 から 0x00000fff まで
0x00001000 から 0x00001fff まで
0xfffff000 から 0xffffffff まで

1段のページテーブルを用いていた場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。また、ページテーブルに必要なメモリは何バイトになるか。ページテーブルの 1エントリのバイトは、4バイトとする。なお、末端のページ・フレームに必要なメモリ(この場合は、3ページ、12KB)は、ページテーブルに必要なメモリではないので、計算に入れない。

★問題(205) 2段のページテーブル

問題(204) で、次のような2段のページテーブル (「x86のページ・テーブル」と同じ) を用いていたとする。

1段目: 31..22ビット (上位10ビット)
2段目: 21..12ビット
オフセット: 下位12ビット (11..0ビット)

この場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。また、ページテーブルに必要なメモリは何バイトになるか。ページテーブルの1エントリのバイトは、上位のページテーブルも下位のページテーブルも4バイトとする。

Last updated: 2026/01/21 17:32:16

Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>