mmapにおけるMAP_PRIVATEの挙動

はじめに

mmap(2)とはmemory mappingを新規に作成するsystem callである。

#include <sys/mman.h>
void *mmap(void *addr, size_t len, int prot, int flags, int fildes, off_t off);

mmap(2)は下図(Reference[1]のch.49より引用)のようにmapping typeとprivate/sharedによって、大きく4つに区分できる。

f:id:knknkn11626:20190827115830j:plain
Reference[1] ch.49

Private/Sharedはflags引数にMAP_PRIVATE, MAP_SHAREDをそれぞれ付加する。Fileの場合は、flagに付加すべきものはないが、第５引数にfile descriptorを与える。Anonymousの場合は、MAP_ANONYMOUSを付け加え、fd=NULLとする。

prot引数にはPROT_EXEC, PROT_READ, PROT_WRITE, PROT_NONEのいずれかが入る。

mmapに初めて触れる人にとって、MAP_SHAREDは複数のprocessがmemoryを共有するというのでイメージが湧きやすいのだが、MAP_PRIVATEの概念はかなりわかりにくいと思う。一言でいうと、遅延読み込み/書き込みを可能にするflagである。"遅延"という意味合いは、Read/Writeのaddressのaccessまで物理メモリへの反映を遅延するという意味である。遅延にすることにより得られるメリットとしては、物理メモリ上のデータを重複させずに済むこと、初期化のための時間を最小限にすることができると言う点が挙げられる。

遅延書き込みはCopy On Write(CoW)の名称で知られる。(Copy On Writeについては、前の記事で書いたので参考にしてほしい)　(遅延読み込みについては決まった名称はないように思われる。)

mmap(MAP_PRIVATE)の典型的な使用場面については以下の通り：

  • dynamic loaderにて、shared libraryをメモリに展開するとき(file-mapped)
  • 0埋め領域を確保するとき(MAP_ANONYMOUSも付加する)

本記事では、mmapのflagsにMAP_PRIVATEを付加した場合(つまり上図の上段)について、Linux Kernelの内部実装を覗くことでその効果を理解することを目標にする。

Reference

  • [1]: The Linux Programming Interface ch.49 memory mappings

  • [2]: Understanding the Linux Kernel ch.8,9 Linux Kernel v2.6.11のコードを参考にしてます

  • [3] Intel SDM vol.3

mmapの概要

mmapの理解のためには、struct vm_area_structの権限(vm_flags及びvm_page_protメンバ)とPage Table Entry(PTE)の権限(下位12bit)の違いを把握することが大事である。

  • struct vm_area_structはvirtual memory regionを管理する構造体で、vm_flags及び、vm_page_protメンバでvirtual memory regionの権限を定める。(後述のようにvm_page_protメンバはvm_flagsから定められる)

  • PTE(Page Table Entry)はvirtual memory -> physical memoryに写像するために必要で、x86(32bit)では上位20bitがphysical memory addressで、下位12bitが諸々の権限のbitsetである。

mmapにMAP_PRIVATEを付加した場合、virtual memory regionのうち空いている領域を探した上で、struct vm_area_structを新規に作成するが、それに対応するPTEはmmap完了直後は設定されない。これにより、mmap(2)によって、PTEの権限(下位12bitの中にある)とvm_flagsメンバーの権限の間で齟齬が生じる。これは遅延読み込み/書き込みを実現するにあたって意図的なものである。

遅延処理のトリガーは、mmapで確保したvirtual memory regionに初回アクセスしたときで、このときPage Fault Exception(#14)が発生する。Exception handlerが実行されるので、その処理の過程で、やっとこの領域の権限に対応するPTEが設定/修正される。

これに対する回答は、

mmap(MAP_PRIVATE)のときは、virtual memory regionのみ作成されるので、mmapの時点では未だ「同じ(対応する)実メモリを割り当て」ない。1。割り当てるトリガーは、Read/Writeのaccessが初めて起こったとき

である。

以下の章では、mmapとPage Fault Exception発生時のhandlerの処理について、内部実装を追いながら述べることにする。

mmapの内部実装の流れ

Reference[2]の本を参考にしているので、かなり古いがversion2.6.11のソースコードを見ながらmmapの骨格を追っていく2。

mmapのsystem callのentrypointはold_mmapになっており、old_mmapは単にdo_mmap2を呼び出しているだけなので、do_mmap2から説明する。memory mapped fileの場合(MAP_ANONYMOUSでない場合)は処理が更に増えるので、[fileonly]と書くことにする：

1: [fileonly] file descriptorからstruct file(file 構造体)を引っ張ってくる

2: do_mmap_pgoffを呼び出す(mmapのコア関数)。

2-1: addr = get_unmapped_area(file, addr, len, pgoff, flags);で未使用のvirtual memory areaを取得する。

2-1-1: ext2 filesystemでは、get_unmapped_area関数はないので、addr = arch_get_unmapped_area(file, addr, len, pgoff, flags);が呼ばれる3。この関数は本質的には以下の図のようなfree areaのvirutal memory regionを確保しようとする関数である。

f:id:knknkn11626:20190827140905j:plain
get_unmapped_area

addrは一般的にはaddr = vma->vm_end;がセットされる。vmaはstruct vm_area_structのこと。vma間の間隔がlenのsize以上空いているかの判定はここの部分で行う。(空いていなければ、次のvmaに移動した上で再度判定する) find_vma関数に関しては以前書いた記事を参照のこと。

2-2: struct vm_area_structをallocate、設定する。

// struct vm_area_struct
vma = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
if (!vma) {
    error = -ENOMEM;
    goto unacct_error;
}
memset(vma, 0, sizeof(*vma));

vma->vm_mm = mm;
vma->vm_start = addr; // specified by 2-1-1
vma->vm_end = addr + len;
vma->vm_flags = vm_flags;
vma->vm_page_prot = protection_map[vm_flags & 0x0f];
vma->vm_pgoff = pgoff;

addrは2-1-1で得られたaddressである。vm_flagsはmmap(2)引数のprotとflagsをもとに設定されている(https://kernel.googlesource.com/pub/scm/linux/kernel/git/stable/linux-stable/+/refs/heads/linux-2.6.11.y/mm/mmap.c#926)。 具体的にはprot=PROT_(READ|WRITE|EXEC)の場合、VM_(READ|WRITE|EXEC)に変換してvm_flagsに設定している。vm_page_protはPTE(Page Table Entry)の下位12bitに入れるべきbitsetが格納される。

2-3: [fileonly] vma->vm_file = file;とvma->vm_ops = &generic_file_vm_ops;を設定する4。

2-4: 2-1-1で取得したaddrを返す。これがsystemcallの戻り値に対応している。

いちばん重要なのが、2-1-1の処理である。virtual memoryの中からfree areaを確保しているだけで、対応するPTE(Page Table Entry)の設定を全くしていない(具体的には、補足の2-level pagingの図のPTE: not presentのまま)。mapped fileの場合は加えて2-3でfile構造体をvma->vm_fileに保存している(これは後述するようにPage Fault Exceptionのhandler内で用いられる)。

両者の権限の齟齬はPage Fault Exception handlerによって解消される。

mmapの内部実装の概要を説明したので、実際にexceptionが発生したときにどのように修正を施すのかを次章で述べたいと思う。

page fault

Linuxにおけるpage fault exceptionのhandlerの役割は実は遅延読み込み/書き込みの他にも多岐にわたるが、今回はmmapでMAP_PRIVATEを付加したケースに絞ってpage faultの挙動を説明する。以下ではpage fault exceptionを#PFと略す。

注意) x86のinterruptやexceptionの基本的な説明は以前の記事でも詳しく書いているので省略する

#PFのhandlerはdo_page_faultが出発点で、この全体的な流れはReference[2]のch.9に書いてあるが、主要な登場人物だけ簡単にまとめる：

  • page faultを起こしたaddress: #PFが起こったとき、cr2 register(Page Fault Linear Address (PFLA)とも呼ばれる)で取得できる。
  • struct vm_area_struct vma: vma = find_vma(mm, address);で取得できる。mmapでvmaを確保しているので、vmaの範囲内にaddressがある
  • error_code: exception/interrupt発生時にx86が自動的に各種レジスタとerror_codeをstackに積む様になっている(Reference[3]のFigure 6-4を参照)。error_codeはexceptionごとに異なるが#PFの場合は、下図の通り。mmapの場合はbit1でRead/Write accessの判別ができる：

f:id:knknkn11626:20190827154151j:plain
error_code

  • vma->vm_flags: mmapで設定した権限がvm_flagsなので、error_codeから取得したRead/Write accessとマッチしている必要がある。vm_flagsにVM_WRITEがセットされており、かつ、Write accessの場合はwrite変数が有効になる。(この変数は後に使用される)

mmapではdo_page_fault-> handle_mm_faultとたどる。この関数はaddressに対応するPage Table Entryを取得(pte_alloc_map)し、handle_pte_fault関数にうつる。mmapの場合は、PTEの反映を全く何もしていないため、PTEのbitは全て0である。よって、!pte_present(entry)とpte_none(entry)が真となり、do_no_pageに移動する。

注意)PROT_READとPROT_WRITEを指定していた場合は事情はやや複雑となる。read -> writeの順でアクセスすると、2回とも#PFが発生する。これは、read accessのときにPTEにwrite権限を与えないためである。このとき、2回目のwriteでdo_wp_pageが呼ばれる。do_wp_pageはforkのpaging構成の際にも呼ばれる関数なので、本記事ではdo_wp_pageの実装まで踏み込まない(実際の処理は最初にwrite accessでdo_no_page が起こったときの処理と本質的に同じになる)

以下ではdo_no_pageがどのような挙動なのかを述べる。

do_no_page

以下の観点に着目すると良いと思う。

  • read accessの場合は、既存のpageのphysical memory addressとvirtual addressを結びつけること、write accessの場合はpageの複製も行ったうえで、新規のpageのphysical memory addressとvirtual addressを結びつけること。

  • MAP_ANONYMOUSの場合は、0埋め領域を取得すること、及びmemory-mapped fileの場合は、file中のpageを取得すること。

MAP_ANONYMOUSの場合

MAP_ANONYMOUSの場合、すぐにdo_anonymous_pageに移行する。

1: entry = pte_wrprotect(mk_pte(virt_to_page(empty_zero_page), vma->vm_page_prot));でPTE(32bit)を作成する(pte_wrprotectはPTEのbit1(R/W)が0、つまりRead onlyと指定される)。empty_zero_pageは以下のように静的に定義されている(これが理由で、最初から0埋め領域として取得できるようになっている)：

// arch/i386/kernel/head.S
ENTRY(empty_zero_page)
    .fill 4096,1,0

2: set_pte(page_table, entry);で1のPTEとvirtual addressとを結びつける。(page_tableはPTEの場所であり、handle_mm_faultのpte_alloc_mapから取得している。)

1: page = alloc_zeroed_user_highpage(vma, addr);で0埋め領域が確保されたうえで、page descriptorが返される。alloc_zeroed_user_highpageはalloc_pages_node(0, gfp_mask=GFP_HIGHUSER | __GFP_ZERO, 0)がコアの関数であり、0埋め領域を担保している。read accessの場合と異なり、empty_zero_pageとは異なる物理上の領域であるので、Copy On Writeが実現されている。

2: entry = maybe_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot)), vma);にてPTE(32bit)を作成する。PTEのbit1(R/W)は1(Write)にセットされる

3: set_pte(page_table, entry);によって、paging設定。2で作成したPTEとvirtual addressとを結びつける

page fault handlerが終了したら、%eip registerが復元され、user modeに戻るので、実際のmemoryへの書き込みが可能となる。

memory-mapped fileの場合

mmap(2)にてvma->vm_file=file、vma->vm_ops=&generic_file_vm_opsと指定したことに留意する。do_no_pageは以下のような処理になる：

1: vma->vm_ops->nopage関数(filemap_nopage関数)を実行する。この関数は、new_page = find_get_page(vma->vm_file->f_mapping, pgoff);を実行して、fileのpgoff: offsetの場所のphysical memoryに対応するpage descriptorを返す。

2: entry = mk_pte(new_page, vma->vm_page_prot);6でPTE(32bit)を作成する。

3: set_pte(page_table, entry);にて、paging設定。virtual addressとphysical addressを結びつける。

  • write accessの場合: 1の後にpageを複製する処理が入る(Copy On Writeの処理)。

1: read accessの1番と同じ(new_pageに結果が格納される)

2: page = alloc_page_vma(GFP_HIGHUSER, vma, address);で新たにpageを確保し、そのpageのpage descriptorを返す。copy_user_highpage(page, new_page, address);でsrc: new_page => dst: pageに内容が複製される(Copy On Write)。

3: entry = maybe_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot)), vma);にてPTE(32bit)を作成

4: set_pte(page_table, entry);でpaging設定。3の領域のphysical addressとvirtual addressとが対応づく。

補足

virtual memory, physical memory

virtual memory, physical memoryの関係は大体このような感じ：

paging: [virtual memory address] -> [physical memory address]

"virtual memory"はprocessごとに異なるのに対し、"physical memory"はmachineごとに(普通は)1つ存在するものである。pagingは本質的にはvirtual memory addressからphysical memory addressを変換するための写像である。

virtual memoryはprocessごとに異なるので、struct task_struct(process descriptor)のmmメンバ(virtual memory descriptor: struct mm)で管理されている。更に、(struct task_struct)tsk->mmには複数の使用中のareaを管理する構造体(struct vm_area_struct: memory regions)が下図のようにぶら下がっている。

f:id:knknkn11626:20190827123048j:plain
Reference[2]のch.9より

paging

2-level pagingの場合の概略図は以下のようになっている：

f:id:knknkn11626:20190827132548j:plain
2-level pagingの概略図

Page Directoryの先頭アドレスはcr3 registerに格納されており、2-level pagingの場合、virtual memory addressの上位10bitがpage directory tableのindexerにあたるので、PDE(Page Directory Entry)がわかる。そこから上の図のようにたどっていくと、Page Frame(4K byte)の先頭addressがわかる。

f:id:knknkn11626:20190827132032j:plain
Reference[3] 4.4より

本記事で登場するPTEをみると、上位20bitが"Address of 4K page frame"であり、下位12bitがRead/WriteやUser/Supervisorなどを表すflag達になっている。これらbitの意味はReference[3]のTable 4-6を参考にしてほしい。

  1. ただし、MAP_PRIVATEとともにMAP_POPULATEも付加された場合は、mmap時点で同じ実メモリを割り当てる(mmapで要求するmemory regionを最初からpagingと物理メモリに反映させるので、page fault exceptionが生じない)。つまり、MAP_POPULATEをつけると、即時読み込み/書き込みとなる↩

  2. vma_mergeは条件が合えば２つの隣接するvm_area_structをmergeする関数だが、判定条件が結構細かいので、mergeされない(ちゃんというとmergeに失敗するので何もしない)場合を想定する。↩

  3. Flexible memory region layoutというものを採用しているとarch_get_unmapped_area_topdown関数が呼ばれる。これについては、Reference[2]のTable 20-4を参照のこと。↩

  4. ext2の場合↩

  5. anon_vma_prepare, page_add_anon_rmapはReverse mappingで用いられる。Reference[1]のch.17とかFigure 17.1を参照のこと。↩

  6. ここはpte_wrprotect(write protect)をつけていないのは大丈夫なの？↩