![struct page page[]、物理メモリ](images/struct-page-page.png)
図? struct page page[]による物理メモリの管理
2017年01月20日
情報科学類 オペレーティングシステム II
筑波大学 システム情報系
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2016/2017-01-20
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/
図? struct page page[]による物理メモリの管理
linux-4.9.1/include/linux/mm_types.h
45: struct page {
...
47: unsigned long flags;
...
50: struct address_space *mapping;
...
108: atomic_t _refcount;
...
120: struct list_head lru;
...
209: void *virtual; /* Kernel virtual address (NULL if
210: not kmapped, ie. highmem) */
...
224: }
| PG_locked | ページがピン留めされている。ページアウトされない。入出力の処理中に設定され、完了後に解除される。 |
| PG_error | このページに対して入出力エラーが生じた。 |
| PG_referenced | ディスク入出力のために参照されている。 |
| PG_uptodate | ページの内容が有効である。入力処理が完了した。 |
| PG_dirty | ページの内容が変更された。 |
| PG_lru | ページングのための LRU リストにある。 |
| PG_active | ページがアクティブである。 |
| PG_slab | スラブ・アロケータで割り当てられた。 |
| PG_arch_1 | アーキテクチャ固有のページ状態 |
| PG_reserved | ページアウト禁止、または、ブード時のメモリ・アロケータで割り当てられた |
| PG_writeback | 書き戻し中 |
| PG_compound | 複合ページ |
| PG_reclaim | 開放すべきページ |
linux-4.9.1/arch/x86/include/asm/page_types.h 8: #define PAGE_SHIFT 12 9: #define PAGE_SIZE (_AC(1,UL) << PAGE_SHIFT) 10: #define PAGE_MASK (~(PAGE_SIZE-1)) linux-4.9.1/include/uapi/linux/const.h 19: #define __AC(X,Y) (X##Y) 20: #define _AC(X,Y) __AC(X,Y)
よく使われるゾーンの種類。
図? メモリのゾーンへの分割
DMA は、ハードディスクやネットワークデバイス等で使われているの入出力方 法の１つ。通常、メモリは、CPU が制御している。DMA では、周辺デバイスが CPU からメモリの制御を奪い、データの入出力を行う。
DMA の利点
次のような手続きで、メモリを開放する。
linux-4.9.1/include/linux/gfp.h 484: #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0) 429: static inline struct page * 430: __alloc_pages(gfp_t gfp_mask, unsigned int order, 431: struct zonelist *zonelist) 490: extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order); 491: extern unsigned long get_zeroed_page(gfp_t gfp_mask); 503: extern void __free_pages(struct page *page, unsigned int order); 504: extern void free_pages(unsigned long addr, unsigned int order); 514: #define free_page(addr) free_pages((addr), 0)
__get_free_pages(), alloc_pages(), alloc_page() や、 後述する kmalloc() では、 gfp_t のフラグ(gfp_mask) として、次のものがよく使われる。特に GFP_KERNEL がよく使われる。gfp は、get free pages に由来する。
linux-4.9.1/include/linux/gfp.h
| 型 | 説明 |
|---|---|
| GFP_ATOMIC | 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。 |
| GFP_NOIO | スリープ可、入出力不可。 |
| GFP_NOFS | スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。 |
| GFP_KERNEL | カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。 |
| GFP_USER | ユーザ空間用のメモリの通常の方法。スリープ可。 |
| GFP_HIGHUSER | HIGHMEMゾーンからの割当て。スリープ可。 |
| GFP_DMA | DMAゾーンからの割当て。デバイス・ドライバ等が使う。 |
図1(a) Buddyシステムによる空きページの管理(論理的な見方)
図1(b) Buddyシステムによる空きページの管理(線形な見方)
% cat /proc/buddyinfo ![[←]](../icons/screen-return.gif)
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
% ![[]](../icons/screen-cursor.gif)
この例では、DMA ゾーンの 2 0 (4KB) に、6 個、
2 1 (8KB) に、5 個、・・・、2 10 に2個の空きがある。
外部フラグメンテーションが起きると、大きな塊が少なくなる。
void *kmalloc(size_t size, gfp_t flags)引数
| 状況 | フラグ |
| プロセスのコンテキスト、スリープ可能 | GFP_KERNEL |
| プロセスのコンテキスト、スリープ不可 | GFP_ATOMIC |
| 割込みハンドラ | GFP_ATOMIC |
| 割込みハンドラ後半(Softirq,Tasklet,後述) | GFP_ATOMIC |
| DMA可能なメモリ、スリープ可能 | GFP_DMA|GFP_KERNEL |
| DMA可能なメモリ、スリープ不可 | GFP_DMA|GFP_ATOMIC |
void kfree(const void *objp)C言語のユーザ空間で使えるライブラリ free() と似ている。 kmalloc() で割り当てたメモリを解放する。
図? フリーリストの例
図? フリーリストの例(ページを意識)
図? ページ・フレーム、スラブ、オブジェクトの関係
struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags, void (*ctor)(void *))
引数
void kmem_cache_destroy(struct kmem_cache *c)kmem_cache_create() で割り当てた struct kmem_cache *を開放する。 shutdown (電源を切る操作)で呼ばれることがある。
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 で指定されたプロセッサで高速にアクセスできるメモリに割り当てられる。
linux-4.9.1/kernel/fork.c
138: static struct kmem_cache *task_struct_cachep;
428: void __init fork_init(void)
429: {
...
436: task_struct_cachep = kmem_cache_create("task_struct",
437: arch_task_struct_size, ARCH_MIN_TASKALIGN,
438: SLAB_PANIC|SLAB_NOTRACK|SLAB_ACCOUNT, NULL);
...
454: }
140: static inline struct task_struct *alloc_task_struct_node(int node)
141: {
142: return kmem_cache_alloc_node(task_struct_cachep, GFP_KERNEL, node);
143: }
145: static inline void free_task_struct(struct task_struct *tsk)
146: {
147: kmem_cache_free(task_struct_cachep, tsk);
148: }
% cat /proc/slabinfo
slabinfo - version: 2.0
# name <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <batchcount> <limit> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
ip_conntrack_expect 0 0 256 15 1 : tunables 120 60 8 : slabdata 0 0 0
ip_conntrack 22 50 384 10 1 : tunables 54 27 8 : slabdata 5 5 0
nfs_direct_cache 0 0 68 58 1 : tunables 120 60 8 : slabdata 0 0 0
nfs_write_data 36 42 512 7 1 : tunables 54 27 8 : slabdata 6 6 0
...
task_struct 84 115 1408 5 2 : tunables 24 12 8 : slabdata 23 23 0
anon_vma 767 1130 16 226 1 : tunables 120 60 8 : slabdata 5 5 0
pgd 54 238 32 119 1 : tunables 120 60 8 : slabdata 2 2 0
pmd 123 123 4096 1 1 : tunables 24 12 8 : slabdata 123 123 0
size-131072(DMA) 0 0 131072 1 32 : tunables 8 4 0 : slabdata 0 0 0
size-131072 0 0 131072 1 32 : tunables 8 4 0 : slabdata 0 0 0
size-65536(DMA) 0 0 65536 1 16 : tunables 8 4 0 : slabdata 0 0 0
size-65536 2 2 65536 1 16 : tunables 8 4 0 : slabdata 2 2 0
...
size-32 8314 8925 32 119 1 : tunables 120 60 8 : slabdata 75 75 0
kmem_cache 150 150 256 15 1 : tunables 120 60 8 : slabdata 10 10 0
%
スラブ・アロケータには、２種類ある。
size-番号 。
DMA が付いているものは、DMA 可能なメモリ。
図? プロセスのアドレス空間の構造
ELF ファイルは、ヘッダとセクションの並びからなる。重要なセクションに は、.text, .rodata, .data がある。
$ cat hello.c
main()
{
printf("hello, %s!\n","world");
}
$ cc -o hello hello.c
$ file hello
hello: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, not stripped
$ size hello
text data bss dec hex filename
1159 252 8 1419 58b hello
$ readelf -S hello
There are 30 section headers, starting at offset 0x7f4:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .interp PROGBITS 08048134 000134 000013 00 A 0 0 1
...
[13] .text PROGBITS 08048310 000310 00018c 00 AX 0 0 16
...
[15] .rodata PROGBITS 080484b8 0004b8 00001e 00 A 0 0 4
...
[24] .data PROGBITS 080496c8 0006c8 000004 00 WA 0 0 4
[25] .bss NOBITS 080496cc 0006cc 000008 00 WA 0 0 4
...
[28] .symtab SYMTAB 00000000 000ca4 000410 10 29 45 4
$
線形なアドレス空間は、メモリ・エリア(memory area)(または、memory region、memory interval)に分割される。
linux-4.9.1/include/linux/sched.h
1475: struct task_struct {
...
1549: struct mm_struct *mm, *active_mm;
...
1967: };
tast_struct の mm フィールド
図? プロセス関連のメモリの構造体
linux-4.9.1/include/linux/mm_types.h
396: struct mm_struct {
397: struct vm_area_struct *mmap; /* list of VMAs */
398: struct rb_root mm_rb;
...
409: pgd_t * pgd;
410: atomic_t mm_users; /* How many users with user space? */
411: atomic_t mm_count; /* How many references to "struct mm_struct" (users count as 1) */
...
416: int map_count; /* number of VMAs */
...
421: struct list_head mmlist;
...
437: unsigned long start_code, end_code, start_data, end_data;
438: unsigned long start_brk, brk, start_stack;
439: unsigned long arg_start, arg_end, env_start, env_end;
...
520: };
linux-4.9.1/include/linux/mm_types.h
300: struct vm_area_struct {
...
303: unsigned long vm_start; /* Our start address within vm_mm. */
304: unsigned long vm_end; /* The first byte after our end address
305: within vm_mm. */
...
310: struct rb_node vm_rb;
...
322: struct mm_struct *vm_mm; /* The address space we belong to. */
323: pgprot_t vm_page_prot; /* Access permissions of this VMA. */
324: unsigned long vm_flags; /* Flags, see mm.h. */
...
346: const struct vm_operations_struct *vm_ops;
...
351: struct file * vm_file; /* File we map to (can be NULL). */
...
361: };
| フラグ | 説明 |
|---|---|
| VM_READ | 読み込み可 |
| VM_WRITE | 書き込み可 |
| VM_EXEC | 実行可 |
| VM_SHARED | 共有されている |
| VM_GROWSDOWN | アドレスが小さい方に伸びる |
| VM_GROWSUP | アドレスが大きい方に伸びる |
| VM_DENYWRITE | 書き込み不可。 |
| VM_EXECUTABLE | 実行可能。 |
| VM_LOCKED | ロックされている。 |
| VM_DONTCOPY | コピー不可 |
| VM_DONTEXPAND | 拡張不可。 |
図? プロセスのアドレス空間の実現
/proc/PID/maps というファイルを見ると、その様子が分かる。
$ echo $$
3981
$ ls /proc/$$
attr cpuset fd maps oom_adj smaps task
auxv cwd io mem oom_score stat wchan
cmdline environ limits mounts root statm
coredump_filter exe loginuid mountstats schedstat status
$ cat /proc/$$/maps
00110000-00114000 r-xp 00000000 08:02 490576 /lib/libnss_dns-2.5.so
00114000-00115000 r--p 00003000 08:02 490576 /lib/libnss_dns-2.5.so
00115000-00116000 rw-p 00004000 08:02 490576 /lib/libnss_dns-2.5.so
...
08047000-080f5000 r-xp 00000000 08:02 481554 /bin/bash
080f5000-080fa000 rw-p 000ae000 08:02 481554 /bin/bash
080fa000-080ff000 rw-p 080fa000 00:00 0
09d66000-09e25000 rw-p 09d66000 00:00 0 [heap]
...
bffdd000-bfff2000 rw-p bffe9000 00:00 0 [stack]
$ wc /proc/$$/maps
45 263 2920 /proc/3981/maps
$
/proc/PID/maps のフィールドの意味
/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
481554 -rwxr-xr-x 1 root root 735004 Jan 22 2009 /bin/bash
$ ls -li /lib/libnss_dns-2.5.so
490576 -rwxr-xr-x 1 root root 21948 Oct 26 08:16 /lib/libnss_dns-2.5.so
$
図? MMUによる仮想アドレスから物理アドレスへの変換
図? 1段のページテーブル
unsigned 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 );
}
図? 1段のページテーブル
page_table[] は、0x100000 個 == 1024 * 1024 個 == 1M 個の要素からなる。 1要素が 4 バイト(32ビット) なら、4MB のメモリが必要になる。
仮想アドレスの構成の 例。 1ページが4KB、仮想アドレスが32ビットの時の分割の例(他の分割方法も考えら れる)
図? 仮想アドレスの4つの部分への分割例
図? 4段のページテーブル
unsigned int pgd[0x20];
unsigned long int physical_address( unsigned long int virtual v ) {
unsigned int *pud, *pmd, *pte, p, q, r, s, page, offset;
p = v >> (32-5) ;
q = (v >> (32-10)) & 0x1f;
r = (v >> (32-15)) & 0x1f;
s = (v >> (32-20)) & 0x1f;
offset = v & 0xfff;
pud = pgd[p];
pmd = pud[q];
pte = pmd[r];
page = pte[s]
return( page + offset );
}
図? 仮想アドレスの3つの部分への分割例
図? x86の2段のページテーブル
linux-4.9.1/arch/x86/mm/fault.c
1445: dotraplinkage void notrace
1446: do_page_fault(struct pt_regs *regs, unsigned long error_code)
1447: {
1448: unsigned long address = read_cr2(); /* Get the faulting address */
...
1460: __do_page_fault(regs, error_code, address);
...
1462: }
1214: static noinline void
1215: __do_page_fault(struct pt_regs *regs, unsigned long error_code,
1216: unsigned long address)
1217: {
1218: struct vm_area_struct *vma;
1219: struct task_struct *tsk;
1220: struct mm_struct *mm;
1221: int fault, major = 0;
1222: unsigned int flags = FAULT_FLAG_ALLOW_RETRY | FAULT_FLAG_KILLABLE;
1223:
1224: tsk = current;
1225: mm = tsk->mm;
...
1353: vma = find_vma(mm, address);
1354: if (unlikely(!vma)) {
1355: bad_area(regs, error_code, address);
1356: return;
1357: }
1358: if (likely(vma->vm_start <= address))
1359: goto good_area;
1360: if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
1361: bad_area(regs, error_code, address);
1362: return;
1363: }
...
1385: good_area:
1386: if (unlikely(access_error(error_code, vma))) {
1387: bad_area_access_error(regs, error_code, address, vma);
1388: return;
1389: }
...
1397: fault = handle_mm_fault(vma, address, flags);
...
1442: }
linux-4.9.1/mm/memory.c
3623: int handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
3624: unsigned int flags)
3625: {
...
3651: ret = __handle_mm_fault(vma, address, flags);
...
3678: return ret;
3679: }
3570: static int __handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
3571: unsigned int flags)
3572: {
3573: struct fault_env fe = {
3574: .vma = vma,
3575: .address = address,
3576: .flags = flags,
3577: };
3578: struct mm_struct *mm = vma->vm_mm;
3579: pgd_t *pgd;
3580: pud_t *pud;
...
3582: pgd = pgd_offset(mm, address);
3583: pud = pud_alloc(mm, pgd, address);
3584: if (!pud)
3585: return VM_FAULT_OOM;
3586: fe.pmd = pmd_alloc(mm, pud, address);
3587: if (!fe.pmd)
3588: return VM_FAULT_OOM;
...
3614: return handle_pte_fault(&fe);
3615: }
linux-4.9.1/mm/memory.c
3482: static int handle_pte_fault(struct fault_env *fe)
3483: {
3484: pte_t entry;
...
3506: entry = *fe->pte;
...
3523: if (!fe->pte) {
3524: if (vma_is_anonymous(fe->vma))
3525: return do_anonymous_page(fe);
3526: else
3527: return do_fault(fe);
3528: }
3529:
3530: if (!pte_present(entry))
3531: return do_swap_page(fe, entry);
3317: static int do_fault(struct fault_env *fe)
3318: {
3319: struct vm_area_struct *vma = fe->vma;
3320: pgoff_t pgoff = linear_page_index(vma, fe->address);
...
3326: return do_read_fault(fe, pgoff);
...
3330: }
3174: static int do_read_fault(struct fault_env *fe, pgoff_t pgoff)
3175: {
...
3191: ret = __do_fault(fe, pgoff, NULL, &fault_page, NULL);
...
3201: return ret;
3202: }
2850: static int __do_fault(struct fault_env *fe, pgoff_t pgoff,
2851: struct page *cow_page, struct page **page, void **entry)
2852: {
2853: struct vm_area_struct *vma = fe->vma;
2854: struct vm_fault vmf;
2855: int ret;
2856:
2857: vmf.virtual_address = (void __user *)(fe->address & PAGE_MASK);
2858: vmf.pgoff = pgoff;
2859: vmf.flags = fe->flags;
2860: vmf.page = NULL;
2861: vmf.gfp_mask = __get_fault_gfp_mask(vma);
2862: vmf.cow_page = cow_page;
2863:
2864: ret = vma->vm_ops->fault(vma, &vmf);
...
2885: return ret;
2886: }
vma->vm_ops->fault(vma, &vmf)で処理。
ELF 形式の実行形式や共有ライブラリから機械語命令やデータを読み出す。
struct s1 {
/* 省略 */
};
利用
struct s1 *p;
p = malloc( sizeof(struct s1) );
use( p );
free( p );
このプログラムを、カーネル内で動かすことを想定してkmalloc() と kfree()
を使って書き換えなさい。ただし、gfp のフラグとしては、GFP_KERNEL を使いなさい。
利用 struct s1 *p; /*回答*/ use( p ); /*回答*/
初期化 /*回答*/ 利用 struct s1 *p; /*回答*/ use( p ); /*回答*/
0x00000000 から 0x00000fff まで
0x00001000 から 0x00001fff まで
0xfffff000 から 0xffffffff まで