![struct page page[]、物理メモリ](images/struct-page-page.png)
図? struct page page[]による物理メモリの管理
2022年01月13日
情報科学類 オペレーティングシステム II
筑波大学 システム情報系
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2021/2022-01-13
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/
図? struct page page[]による物理メモリの管理
linux-5.15.12/include/linux/mm_types.h
70: struct page {
71: unsigned long flags; /* Atomic flags, some possibly
72: * updated asynchronously */
...
86: struct list_head lru;
87: /* See page-flags.h for PAGE_MAPPING_FLAGS */
88: struct address_space *mapping;
...
216: atomic_t _refcount;
...
233: void *virtual; /* Kernel virtual address (NULL if
234: not kmapped, ie. highmem) */
...
240: } _struct_page_alignment;
| 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 | 開放すべきページ |
linux-5.15.12/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-5.15.12/include/uapi/linux/const.h 20: #define __AC(X,Y) (X##Y) 21: #define _AC(X,Y) __AC(X,Y)
よく使われるゾーンの種類。
図? メモリのゾーンへの分割
DMA は、ハードディスクやネットワークデバイス等で使われているの入出力方 法の１つ。通常、メモリは、CPU が制御している。DMA では、周辺デバイスが CPU からメモリの制御を奪い、データの入出力を行う。
DMA の利点
次のような手続きで、メモリを開放する。
linux-5.15.12/include/linux/gfp.h 604: #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0) 595: static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order) 608: extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order); 609: extern unsigned long get_zeroed_page(gfp_t gfp_mask); 621: extern void __free_pages(struct page *page, unsigned int order); 622: extern void free_pages(unsigned long addr, unsigned int order); 621: extern void __free_pages(struct page *page, unsigned int order); 622: extern void free_pages(unsigned long addr, unsigned int order); 639: #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-5.15.12/include/linux/gfp.h
| 型 | 説明 |
|---|---|
| GFP_ATOMIC | 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。 |
| GFP_KERNEL | カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。 |
| GFP_NOIO | スリープ可、入出力不可。 |
| GFP_NOFS | スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。 |
| GFP_USER | ユーザ空間用のメモリの通常の方法。スリープ可。 |
| GFP_HIGHUSER | HIGHMEMゾーンからの割当て。スリープ可。 |
| GFP_DMA | DMAゾーンからの割当て。デバイス・ドライバ等が使う。 |
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システムでのメモリ管理手法
図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-5.15.12/kernel/cred.c
695: void __init cred_init(void)
696: {
697: /* allocate a slab in which we can store credentials */
698: cred_jar = kmem_cache_create("cred_jar", sizeof(struct cred), 0,
699: SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT, NULL);
700: }
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: }
% 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 可能なメモリ。
図? プロセスのアドレス空間の構造
0xc0000000-0xffffffff の間は、
オペレーティング・システム・カーネルが使うので、
ユーザ空間では使えない。
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
$
int execve(const char *filename, char *const argv[], char *const envp[])
線形なアドレス空間は、メモリ・エリア(memory area)(または、memory region、memory interval)に分割される。
linux-5.15.12/include/linux/sched.h
723: struct task_struct {
...
857: struct mm_struct *mm;
...
1506: };
tast_struct の mm フィールド
図? プロセス関連のメモリの構造体
linux-5.15.12/include/linux/mm_types.h
402: struct mm_struct {
...
404: struct vm_area_struct *mmap; /* list of VMAs */
405: struct rb_root mm_rb;
..
421: pgd_t * pgd;
...
442: atomic_t mm_users;
...
451: atomic_t mm_count;
...
456: int map_count; /* number of VMAs */
...
475: struct list_head mmlist;
...
502: unsigned long start_code, end_code, start_data, end_data;
503: unsigned long start_brk, brk, start_stack;
504: unsigned long arg_start, arg_end, env_start, env_end;
...
590: };
linux-5.15.12/include/linux/mm_types.h
319: struct vm_area_struct {
320: /* The first cache line has the info for VMA tree walking. */
321:
322: unsigned long vm_start; /* Our start address within vm_mm. */
323: unsigned long vm_end; /* The first byte after our end address
324: within vm_mm. */
325:
326: /* linked list of VM areas per task, sorted by address */
327: struct vm_area_struct *vm_next, *vm_prev;
328:
329: struct rb_node vm_rb;
...
341: struct mm_struct *vm_mm; /* The address space we belong to. */
...
347: pgprot_t vm_page_prot;
348: unsigned long vm_flags; /* Flags, see mm.h. */
...
370: const struct vm_operations_struct *vm_ops;
...
375: struct file * vm_file; /* File we map to (can be NULL). */
...
388: } __randomize_layout;
| フラグ | 説明 |
|---|---|
| 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 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 );
}
図? 1段のページテーブル
page_table[] は、0x100000 個 == 1024 * 1024 個 == 1M 個の要素からなる。 1要素が 4 バイト(32ビット) なら、4MB のメモリが必要になる。
仮想アドレスの構成の 例。 1ページが4KB、仮想アドレスが32ビットの時の分割の例(他の分割方法も考えら れる)
図? 仮想アドレス上位20ビットの5つの部分への分割例
図? 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 );
}
図? 仮想アドレス位20ビットの2つの部分への分割例
図? x86の2段のページテーブル
linux-5.15.12/arch/x86/include/asm/idtentry.h
163: #define DEFINE_IDTENTRY_RAW_ERRORCODE(func) \
164: __visible noinstr void func(struct pt_regs *regs, unsigned long error_code)
linux-5.15.12/arch/x86/mm/fault.c
1497: DEFINE_IDTENTRY_RAW_ERRORCODE(exc_page_fault)
1498: {
1499: unsigned long address = read_cr2();
1500: irqentry_state_t state;
...
1541: handle_page_fault(regs, error_code, address);
...
1545: }
1472: static __always_inline void
1473: handle_page_fault(struct pt_regs *regs, unsigned long error_code,
1474: unsigned long address)
1475: {
1482: if (unlikely(fault_in_kernel_space(address))) {
1483: do_kern_addr_fault(regs, error_code, address);
1484: } else {
1485: do_user_addr_fault(regs, error_code, address);
...
1494: }
1495: }
1219: static inline
1220: void do_user_addr_fault(struct pt_regs *regs,
1221: unsigned long error_code,
1222: unsigned long address)
1223: {
1224: struct vm_area_struct *vma;
1225: struct task_struct *tsk;
1226: struct mm_struct *mm;
1227: vm_fault_t fault;
1228: unsigned int flags = FAULT_FLAG_DEFAULT;
1229:
1230: tsk = current;
1231: mm = tsk->mm;
1358: vma = find_vma(mm, address);
1359: if (unlikely(!vma)) {
1360: bad_area(regs, error_code, address);
1361: return;
1362: }
1363: if (likely(vma->vm_start <= address))
1364: goto good_area;
1365: if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
1366: bad_area(regs, error_code, address);
1367: return;
1368: }
1369: if (unlikely(expand_stack(vma, address))) {
1370: bad_area(regs, error_code, address);
1371: return;
1372: }
...
1378: good_area:
...
1397: fault = handle_mm_fault(vma, address, flags, regs);
...
1456: }
linux-5.15.12/include/linux/mm.h
531: struct vm_fault {
...
574: };
linux-5.15.12/mm/memory.c
4773: vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
4774: unsigned int flags, struct pt_regs *regs)
4775: {
4776: vm_fault_t ret;
...
4801: ret = __handle_mm_fault(vma, address, flags);
...
4818: }
4617: static vm_fault_t __handle_mm_fault(struct vm_area_struct *vma,
4618: unsigned long address, unsigned int flags)
4619: {
4620: struct vm_fault vmf = {
4621: .vma = vma,
4622: .address = address & PAGE_MASK,
4623: .flags = flags,
4624: .pgoff = linear_page_index(vma, address),
4625: .gfp_mask = __get_fault_gfp_mask(vma),
4626: };
...
4628: struct mm_struct *mm = vma->vm_mm;
4629: pgd_t *pgd;
4630: p4d_t *p4d;
4631: vm_fault_t ret;
...
4633: pgd = pgd_offset(mm, address);
4634: p4d = p4d_alloc(mm, pgd, address);
...
4638: vmf.pud = pud_alloc(mm, p4d, address);
...
4665: vmf.pmd = pmd_alloc(mm, vmf.pud, address);
...
4703: return handle_pte_fault(&vmf);
4704: }
linux-5.15.12/mm/memory.c
4513: static vm_fault_t handle_pte_fault(struct vm_fault *vmf)
4514: {
...
4546: vmf->pte = pte_offset_map(vmf->pmd, vmf->address);
4547: vmf->orig_pte = *vmf->pte;
...
4564: if (!vmf->pte) {
4565: if (vma_is_anonymous(vmf->vma))
4566: return do_anonymous_page(vmf);
4567: else
4568: return do_fault(vmf);
4569: }
4570:
4571: if (!pte_present(vmf->orig_pte))
4572: return do_swap_page(vmf);
...
4609: }
4274: static vm_fault_t do_fault(struct vm_fault *vmf)
4275: {
4276: struct vm_area_struct *vma = vmf->vma;
4277: struct mm_struct *vm_mm = vma->vm_mm;
4278: vm_fault_t ret;
...
4283: if (!vma->vm_ops->fault) {
...
4309: } else if (!(vmf->flags & FAULT_FLAG_WRITE))
4310: ret = do_read_fault(vmf);
4311: else if (!(vma->vm_flags & VM_SHARED))
4312: ret = do_cow_fault(vmf);
4313: else
4314: ret = do_shared_fault(vmf);
...
4321: return ret;
4322: }
4164: static vm_fault_t do_read_fault(struct vm_fault *vmf)
4165: {
4166: struct vm_area_struct *vma = vmf->vma;
4167: vm_fault_t ret = 0;
...
4182: ret = __do_fault(vmf);
...
4190: return ret;
4191: }
3831: static vm_fault_t __do_fault(struct vm_fault *vmf)
3832: {
3833: struct vm_area_struct *vma = vmf->vma;
3834: vm_fault_t ret;
...
3858: ret = vma->vm_ops->fault(vmf);
...
3876: return ret;
3877: }
vma->vm_ops->fault(vma, &vmf)で処理。
ELF 形式の実行形式や共有ライブラリから機械語命令やデータを読み出す。
なるべく授業時間中に次の問題を解き、Manaba の「レポート」で回答しなさい。 回答は、図を含んでいる。 PDF ファイルで回答しなさい。
0x00000000 から 0x00000fff まで
0x00001000 から 0x00001fff まで
0xfffff000 から 0xffffffff まで