メモリ管理

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

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

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

■今日の大事な話

■メモリ管理

◆目標

■物理メモリの管理

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

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

◆ページ構造体

linux-6.1.2/include/linux/mm_types.h
  73:	struct page {
  74:	        unsigned long flags;            /* Atomic flags, some possibly
  75:	                                         * updated asynchronously */
...
  90:	                                struct list_head lru;
...
 105:	                        struct address_space *mapping;
...
 206:	        atomic_t _refcount;
...
 223:	        void *virtual;                  /* Kernel virtual address (NULL if
 224:	                                           not kmapped, ie. highmem) */
...
 242:	} _struct_page_alignment;

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

linux-6.1.2/include/linux/page-flags.h
page構造体のflags(主要部分)
PG_locked ページがピン留めされている。ページアウトされない。入出力の処理中に設定され、完了後に解除される。
PG_referenced ディスク入出力のために参照されている。
PG_uptodate ページの内容が有効である。入力処理が完了した。
PG_dirty ページの内容が変更された。
PG_lru ページングのための LRU リストにある。
PG_active ページがアクティブである。
PG_error このページに対して入出力エラーが生じた。
PG_slab スラブ・アロケータで割り当てられた。
PG_arch_1 アーキテクチャ固有のページ状態
PG_reserved ページアウト禁止、または、ブード時のメモリ・アロケータで割り当てられた
PG_writeback 書き戻し中
PG_reclaim 開放すべきページ

◆x86のページ・サイズ

2の12乗(1 << 12)==4096バイト。
linux-6.1.2/arch/x86/include/asm/page_types.h
  10:	#define PAGE_SHIFT              12
  11:	#define PAGE_SIZE               (_AC(1,UL) << PAGE_SHIFT)
  12:	#define PAGE_MASK               (~(PAGE_SIZE-1))

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

DMA の利点

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

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。 struct pageへのポインタが得られた場合、メモリは割り当てられているが、論 理アドレス不明なので、そのままではプログラムでアクセスできない。論理ア ドレスが必要なら、void *page_address(page)を使って struct pageへのポイ ンタからアクセス可能な論理アドレスを得ることができる。

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

linux-6.1.2/include/linux/gfp.h
 280:	#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

 177:	struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
 178:	                nodemask_t *nodemask);

 289:	extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
 290:	extern unsigned long get_zeroed_page(gfp_t gfp_mask);

 302:	extern void __free_pages(struct page *page, unsigned int order);
 303:	extern void free_pages(unsigned long addr, unsigned int order);

 320:	#define free_page(addr) free_pages((addr), 0)

◆gfp_t gfp_mask

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

linux-6.1.2/include/linux/gfp_types.h
説明
GFP_ATOMIC 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。
GFP_KERNEL カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。
GFP_NOIO スリープ可、入出力不可。
GFP_NOFS スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。
GFP_USER ユーザ空間用のメモリの通常の方法。スリープ可。
GFP_HIGHUSER HIGHMEMゾーンからの割当て。スリープ可。
GFP_DMADMAゾーンからの割当て。デバイス・ドライバ等が使う。
GFP_DMA32DMA32ゾーンからの割当て。デバイス・ドライバ等が使う。
このようなフラグが存在する最も重要な理由は、スリープする可能性があるか ないかの違い。 その他に、どのゾーンからメモリを割り当てるべきかを表すものがある。

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

物理フレームの割当てと開放を繰り返していくと、外部フラグメンテーション (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システムでのメモリ管理手法

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 0 (4KB) に、1 個、2 1 (8KB) に、1 個、・・・、2 10 に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 0 (4KB) に、6 個、 2 1 (8KB) に、5 個、・・・、2 10 に2個の空きがある。 外部フラグメンテーションが起きると、大きな塊が少なくなる。

■kmallocとkfree

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

◆kmalloc()

C言語のユーザ空間で使えるライブラリ malloc() に似ている。
void *kmalloc(size_t size, gfp_t flags)
引数 結果: 最低限、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、オブジェクト4個
図? フリーリストの例

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

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

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

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

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

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

ページフレーム3つ、スラブ1つ、オブジェクト6つ
図? ページ・フレーム、スラブ、オブジェクトの関係

◆kmem_cache_create()

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *))
引数 結果: 成功した時には、struct kmem_cache へのポインタ。 失敗するとNULL。新しいページが割り当てられた時には、ctor で 指定された関数が呼ばれる。

◆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.1.2/kernel/cred.c
 689:	void __init cred_init(void)
 690:	{
 691:	        /* allocate a slab in which we can store credentials */
 692:	        cred_jar = kmem_cache_create("cred_jar", sizeof(struct cred), 0,
 693:	                        SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT, NULL);
 694:	}

 252:	struct cred *prepare_creds(void)
 253:	{
 254:	        struct task_struct *task = current;
 255:	        const struct cred *old;
 256:	        struct cred *new;
...
 260:	        new = kmem_cache_alloc(cred_jar, GFP_KERNEL);
...
 266:	        old = task->cred;
 267:	        memcpy(new, old, sizeof(struct cred));
...
 295:	        return new;
...
 300:	}

  94:	static void put_cred_rcu(struct rcu_head *rcu)
  95:	{
  96:	        struct cred *cred = container_of(rcu, struct cred, rcu);
...
 126:	        kmem_cache_free(cred_jar, cred);
 127:	}

◆/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
# []
スラブ・アロケータには、2種類ある。

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

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

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

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

システム・コール ライブラリ その他

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

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

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 
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[])

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

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

利用者プロセスのプログラムは、線形な(linear)アドレス空間で仮想アドレス を使って機械語命令を読み出したり、データを読み書きする。 (x86 では、セグメンテーションも使えるので、線形ではないアドレス空間も可 能だが、Linux では、他のアーキテクチャとの兼ね合いもあり、線形な空間を 使う。)

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

◆task_struct構造体とmm_struct構造体

カーネル内では、プロセス(単一スレッド)のメモリは、次の構造体で表される。
linux-6.1.2/include/linux/sched.h
 737:	struct task_struct {
...
 870:	        struct mm_struct                *mm;
...
1546:	};
tast_struct の mm フィールド

◆mm_struct構造体

linux-6.1.2/include/linux/mm_types.h
 512:	struct mm_struct {
 513:	        struct {
 514:	                struct maple_tree mm_mt;
...
 528:	                pgd_t * pgd;
...
 549:	                atomic_t mm_users;
...
 558:	                atomic_t mm_count;
...
 563:	                int map_count;                  /* number of VMAs */
...
 582:	                struct list_head mmlist;
...
 609:	                unsigned long start_code, end_code, start_data, end_data;
 610:	                unsigned long start_brk, brk, start_stack;
 611:	                unsigned long arg_start, arg_end, env_start, env_end;
...
 719:	        } __randomize_layout;
 726:	};

◆vm_area_struct構造体

linux-6.1.2/include/linux/mm_types.h
 444:	struct vm_area_struct {
 445:	        /* The first cache line has the info for VMA tree walking. */
 446:	
 447:	        unsigned long vm_start;         /* Our start address within vm_mm. */
 448:	        unsigned long vm_end;           /* The first byte after our end address
 449:	                                           within vm_mm. */
 450:	
 451:	        struct mm_struct *vm_mm;        /* The address space we belong to. */
...
 457:	        pgprot_t vm_page_prot;
 458:	        unsigned long vm_flags;         /* Flags, see mm.h. */
...
 491:	        const struct vm_operations_struct *vm_ops;
...
 496:	        struct file * vm_file;          /* File we map to (can be NULL). */
...
 509:	} __randomize_layout;
vm_area_structのvm_flagsの値(include/linux/mm.h)
フラグ説明
VM_READ 読み込み可
VM_WRITE 書き込み可
VM_EXEC 実行可
VM_SHARED 共有されている
VM_GROWSDOWN アドレスが小さい方に伸びる
VM_GROWSUP アドレスが大きい方に伸びる
VM_DENYWRITE 書き込み不可。
VM_EXECUTABLE 実行可能。
VM_LOCKED ロックされている。
VM_DONTCOPY コピー不可
VM_DONTEXPAND 拡張不可。

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

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

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

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

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

元の実行形式に由来するテキスト、データ、スタックの他に、動的リンク・ラ イブラリに由来するテキストやデータのためのメモリ・エリアが作られる。 /proc/PID/maps というファイルを見ると、その様子が分かる。
$ echo $$ [←]
22696
$ ls /proc/$$ [←]
attr		 cwd	   map_files   oom_adj	      schedstat  task
autogroup	 environ   maps        oom_score      sessionid  timers
auxv		 exe	   mem	       oom_score_adj  setgroups  uid_map
cgroup		 fd	   mountinfo   pagemap	      smaps	 wchan
clear_refs	 fdinfo    mounts      patch_state    stack
cmdline		 gid_map   mountstats  personality    stat
comm		 io	   net	       projid_map     statm
coredump_filter  limits    ns	       root	      status
cpuset		 loginuid  numa_maps   sched	      syscall
$ cat /proc/$$/maps [←]
00400000-004de000 r-xp 00000000 fd:00 403270428                          /usr/bin/bash
006dd000-006de000 r--p 000dd000 fd:00 403270428                          /usr/bin/bash
006de000-006e7000 rw-p 000de000 fd:00 403270428                          /usr/bin/bash
006e7000-006ed000 rw-p 00000000 00:00 0
00b7a000-00bdc000 rw-p 00000000 00:00 0                                  [heap]
...
7fb437f5e000-7fb438122000 r-xp 00000000 fd:00 50035                      /usr/lib64/libc-2.17.so
7fb438122000-7fb438321000 ---p 001c4000 fd:00 50035                      /usr/lib64/libc-2.17.so
7fb438321000-7fb438325000 r--p 001c3000 fd:00 50035                      /usr/lib64/libc-2.17.so
7fb438325000-7fb438327000 rw-p 001c7000 fd:00 50035                      /usr/lib64/libc-2.17.so

7ffc24c64000-7ffc24c85000 rw-p 00000000 00:00 0                          [stack]
7ffc24dce000-7ffc24dd0000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
$ wc /proc/$$/maps [←]
41 239 3630 /proc/22696/maps
$ []
/proc/PID/maps のフィールドの意味
  1. メモリ・セグメントの開始番地と終了番地。
  2. アクセス許可。r(read), w(write), x(executable), p(private), s(shared)
  3. オフセット
  4. ブロック・デバイスのメジャー番号とマイナー番号。 8:2 なら、メジャー番号が、8、マイナー番号が2の意味。 デバイスに結びついていない場合には、00:00 になる。
  5. ファイルのinode番号。
  6. ファイル名。
ブロック・デバイスには、メジャー番号とマイナー番号がある。各ファイルに は、inode 番号がある。これらの3つの番号がわかると、カーネル内ではファイ ルを特定できる。(同じ inode 番号のファイルは、1つのブロック・デバイス内 では、1個しかない。) ファイル名は不要だが、/proc/PID/maps では、人間にとって 分かりやすいようにわざわざ表示している。

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

$ ls -l /dev/sda2 [←]
brw-r----- 1 root disk 8, 2 Jan 24 12:00 /dev/sda2
$ []
ファイルの inode 番号は、ls -i でわかる。
$ ls -li /bin/bash /usr/lib64/libc-2.17.so [←]
403270428 -rwxr-xr-x 1 root root  964536 Oct 27  2021 /bin/bash
    50035 -rwxr-xr-x 1 root root 2156592 Mar 23  2022 /usr/lib64/libc-2.17.so
$ []

■ページテーブル

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

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

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

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

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

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 のメモリが必要になる。

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

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

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

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

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

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段のページテーブルを用いている。次のように対応させている。

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

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

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

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

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

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

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

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

◆TLB (Translation Look-aside Buffer)

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

■ページ・フォールト

メモリが割り当てられていない場所をプロセスがアクセスした時には、ページ・ フォールトが発生する。 x86 では関数 handle_page_fault() がこのような処理を行う。この関数は、権 限外のアクセス、たとえば、書き込み禁止のメモリに書き込みを試みた場合の エラーも処理する。

◆handle_page_fault()

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

linux-6.1.2/arch/x86/mm/fault.c
1531:	DEFINE_IDTENTRY_RAW_ERRORCODE(exc_page_fault)
1532:	{
1533:	        unsigned long address = read_cr2();
...
1575:	        handle_page_fault(regs, error_code, address);
...
1579:	}

1506:	static __always_inline void
1507:	handle_page_fault(struct pt_regs *regs, unsigned long error_code,
1508:	                              unsigned long address)
1509:	{
...
1516:	        if (unlikely(fault_in_kernel_space(address))) {
1517:	                do_kern_addr_fault(regs, error_code, address);
1518:	        } else {
1519:	                do_user_addr_fault(regs, error_code, address);
...
1528:	        }
1529:	}

1250:	static inline
1251:	void do_user_addr_fault(struct pt_regs *regs,
1252:	                        unsigned long error_code,
1253:	                        unsigned long address)
1254:	{
1255:	        struct vm_area_struct *vma;
1256:	        struct task_struct *tsk;
1257:	        struct mm_struct *mm;
1258:	        vm_fault_t fault;
1259:	        unsigned int flags = FAULT_FLAG_DEFAULT;
1260:	
1261:	        tsk = current;
1262:	        mm = tsk->mm;
...
1389:	        vma = find_vma(mm, address);
1390:	        if (unlikely(!vma)) {
1391:	                bad_area(regs, error_code, address);
1392:	                return;
1393:	        }
1394:	        if (likely(vma->vm_start <= address))
1395:	                goto good_area;
1396:	        if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
1397:	                bad_area(regs, error_code, address);
1398:	                return;
1399:	        }
1400:	        if (unlikely(expand_stack(vma, address))) {
1401:	                bad_area(regs, error_code, address);
1402:	                return;
1403:	        }
...
1409:	good_area:
...
1428:	        fault = handle_mm_fault(vma, address, flags, regs);
...
1490:	}

◆handle_mm_fault()

mm/memory.c は、アーキテクチャから独立したコード。
linux-6.1.2/include/linux/mm.h
 481:	struct vm_fault {
...
 525:	};

linux-6.1.2/mm/memory.c
5187:	vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
5188:	                           unsigned int flags, struct pt_regs *regs)
5189:	{
5190:	        vm_fault_t ret;
...
5217:	                ret = __handle_mm_fault(vma, address, flags);
...
5235:	        return ret;
5236:	}

5004:	static vm_fault_t __handle_mm_fault(struct vm_area_struct *vma,
5005:	                unsigned long address, unsigned int flags)
5006:	{
5007:	        struct vm_fault vmf = {
5008:	                .vma = vma,
5009:	                .address = address & PAGE_MASK,
5010:	                .real_address = address,
5011:	                .flags = flags,
5012:	                .pgoff = linear_page_index(vma, address),
5013:	                .gfp_mask = __get_fault_gfp_mask(vma),
5014:	        };
5015:	        struct mm_struct *mm = vma->vm_mm;
5016:	        unsigned long vm_flags = vma->vm_flags;
5017:	        pgd_t *pgd;
5018:	        p4d_t *p4d;
5019:	        vm_fault_t ret;
5020:	
5021:	        pgd = pgd_offset(mm, address);
5022:	        p4d = p4d_alloc(mm, pgd, address);
...
5026:	        vmf.pud = pud_alloc(mm, p4d, address);
...
5056:	        vmf.pmd = pmd_alloc(mm, vmf.pud, address);
...
5096:	        return handle_pte_fault(&vmf);
5097:	}

◆handle_pte_fault()

linux-6.1.2/mm/memory.c
4897:	static vm_fault_t handle_pte_fault(struct vm_fault *vmf)
4898:	{
...
4950:	        if (!vmf->pte) {
4951:	                if (vma_is_anonymous(vmf->vma))
4952:	                        return do_anonymous_page(vmf);
4953:	                else
4954:	                        return do_fault(vmf);
4955:	        }
4956:	
4957:	        if (!pte_present(vmf->orig_pte))
4958:	                return do_swap_page(vmf);
...
4996:	}

4646:	static vm_fault_t do_fault(struct vm_fault *vmf)
4647:	{
4648:	        struct vm_area_struct *vma = vmf->vma;
4649:	        struct mm_struct *vm_mm = vma->vm_mm;
4650:	        vm_fault_t ret;
...
4655:	        if (!vma->vm_ops->fault) {
...
4681:	        } else if (!(vmf->flags & FAULT_FLAG_WRITE))
4682:	                ret = do_read_fault(vmf);
4683:	        else if (!(vma->vm_flags & VM_SHARED))
4684:	                ret = do_cow_fault(vmf);
4685:	        else
4686:	                ret = do_shared_fault(vmf);
...
4693:	        return ret;
4694:	}

4538:	static vm_fault_t do_read_fault(struct vm_fault *vmf)
4539:	{
...
4553:	        ret = __do_fault(vmf);
...
4561:	        return ret;
4562:	}

4176:	static vm_fault_t __do_fault(struct vm_fault *vmf)
4177:	{
4178:	        struct vm_area_struct *vma = vmf->vma;
4179:	        vm_fault_t ret;
...
4202:	        ret = vma->vm_ops->fault(vmf);
...
4229:	        return ret;
4230:	}

◆maple tree

maple tree は、B木の一種。

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

◆Linux red-black treeの基本操作

linux-6.1.2/mm/mmap.c
1826:	struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
1827:	{
1828:	        unsigned long index = addr;
1829:	
1830:	        mmap_assert_locked(mm);
1831:	        return mt_find(&mm->mm_mt, &index, ULONG_MAX);
1832:	}

■課題2 メモリ管理

★問題(201) Buddyシステム

Buddyシステムで、次のメモリ・ページの buddy を答えなさい。

★問題(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とする。 次の3ページが割り当てられてしたとする。 1段のページテーブル を用いていた場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。 また、ページテーブルに必要なメモリは何バイトになるか。ページテーブルの 1エントリのバイトは、4バイトとする。 なお、末端のページ・フレームに必要なメモリ(この場合は、3ページ、12KB)は、 ページテーブルに必要なメモリではないので、計算に入れない。

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

問題(204) で、次のような2段のページテーブル (「x86のページ・テーブル」と同じ) を用いていたとする。 この場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。 また、ページテーブルに必要なメモリは何バイトになるか。ページテーブル の1エントリのバイトは、上位のページテーブルも下位のページテーブルも4バ イトとする。
Last updated: 2023/02/06 22:06:53
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>