はじめに
https://qiita.com/todok-r/items/1d83eb997e0c9e0d1baa
でユーザ層からのテストアプリを使用して、コピーオンライト時の仮想アドレス〜物理アドレスのマッピングが変化する様子を見てみましたが、カーネル層でどのようにコピーオンライトを実装しているかも気になったので、カーネルソースを調査してみました。
コピーオンライトを実現するための処理としては大きくは以下があると思いますが、本記事では1.に焦点を当てて見ていきます。
- fork時にコピーオンライト対象の領域を書き込み不可とし、この領域への書き込み発生時にページフォールトが発生するようにする
- ページフォールトハンドラは書き込みされた領域を別の領域にコピーし、親プロセスと子プロセスでの共有を解除する
ただし、カーネルソースコードを完全に理解し読み解くのは現状の知識では困難なので、わかる範囲での説明となっています。内容は随時更新していく予定です。
参照したLinuxカーネルのバージョンは4.19です。
引用しているソースコードは読みやすさや行数の関係から省略している場合があります。ソースコード中の処理を省略している箇所は"..."で表現しています。
また、ソースコード中の日本語コメントは私が追加したコメントとなります。
カーネルソースコードを見ていく
以下にforkを実行してからコピーオンライト領域の設定までに至るコードを抜き出しています。
まずはforkシステムコールの入り口です。Linuxではユーザ空間でfork実行時は実際にはcloneシステムコールが実行されます。
SYSCALL_DEFINE5(clone, unsigned long, clone_flags, unsigned long, newsp,
int __user *, parent_tidptr,
int __user *, child_tidptr,
unsigned long, tls)
{
return _do_fork(clone_flags, newsp, 0, parent_tidptr, child_tidptr, tls);
}
cloneから_do_forkが実行されますが、親プロセスをコピーして子プロセスを生成する処理はこの中のcopy_processで実行されています。
long _do_fork(unsigned long clone_flags,
unsigned long stack_start,
unsigned long stack_size,
int __user *parent_tidptr,
int __user *child_tidptr,
unsigned long tls)
{
struct completion vfork;
struct pid *pid;
struct task_struct *p;
int trace = 0;
long nr;
...
p = copy_process(clone_flags, stack_start, stack_size,
child_tidptr, NULL, trace, tls, NUMA_NO_NODE);
...
関数先頭のコメントにあるように、copy_processでは親プロセスから様々な情報をコピーするため、様々なcopy_XXX関数(XXXはfilesやsignal等)が実行されます。この中で今回注目しているコピーオンライトに関係するのはcopy_mmとなります。
dup_task_structは親プロセスのプロセスディスクリプタ(current)をコピーし、pにそのアドレスが格納されます。この時点ではp->mmとcurrent->mmは同じメモリディスクリプタ(struct mm_struct)を指します。
copy_mmの中でclone_flagsに応じたメモリディスクリプタのコピーを行います。
/*
* This creates a new process as a copy of the old one,
* but does not actually start it yet.
*
* It copies the registers, and all the appropriate
* parts of the process environment (as per the clone
* flags). The actual kick-off is left to the caller.
*/
static __latent_entropy struct task_struct *copy_process(
unsigned long clone_flags,
unsigned long stack_start,
unsigned long stack_size,
int __user *child_tidptr,
struct pid *pid,
int trace,
unsigned long tls,
int node)
{
int retval;
struct task_struct *p;
struct multiprocess_signals delayed;
...
p = dup_task_struct(current, node);
if (!p)
goto fork_out;
...
retval = copy_mm(clone_flags, p);
if (retval)
goto bad_fork_cleanup_signal;
...
copy_mmのメインの処理はdup_mmの実行です。
ちなみに、clone_flagsにCLONE_VMがセットされている場合はスレッドの生成になるので、dup_mmは実行されず、親プロセスと子プロセスのmmは同じメモリディスクリプタを指すことになります。
これにより、親プロセス、子プロセス(スレッド)でメモリ空間は共有されるため、スレッドはスレッド作成元のデータにアクセスが可能となります。
static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
{
struct mm_struct *mm, *oldmm;
int retval;
tsk->min_flt = tsk->maj_flt = 0;
tsk->nvcsw = tsk->nivcsw = 0;
#ifdef CONFIG_DETECT_HUNG_TASK
tsk->last_switch_count = tsk->nvcsw + tsk->nivcsw;
tsk->last_switch_time = 0;
#endif
tsk->mm = NULL;
tsk->active_mm = NULL;
/*
* Are we cloning a kernel thread?
*
* We need to steal a active VM for that..
*/
oldmm = current->mm;
if (!oldmm)
return 0;
/* initialize the new vmacache entries */
vmacache_flush(tsk);
/* スレッド生成なのでメモリ空間は親と子で共有する.dup_mmは実行しない */
if (clone_flags & CLONE_VM) {
mmget(oldmm);
mm = oldmm;
goto good_mm;
}
/* dup_mmでメモリディスクリプタをコピーする */
retval = -ENOMEM;
mm = dup_mm(tsk);
if (!mm)
goto fail_nomem;
good_mm:
tsk->mm = mm;
tsk->active_mm = mm;
return 0;
fail_nomem:
return retval;
}
dup_mmでは子プロセス用のメモリディスクリプタ領域をallocate_mmで確保し、その領域に親プロセスのメモリディスクリプタをそのままmemcpyで複製した後、mm_initで初期化が必要なパラメータを初期化します。また、後述するページテーブルの最上位(PGD)の領域も確保します。
その後にdup_mmapで仮想アドレス空間のコピーを行います。
/*
* Allocate a new mm structure and copy contents from the
* mm structure of the passed in task structure.
*/
static struct mm_struct *dup_mm(struct task_struct *tsk)
{
struct mm_struct *mm, *oldmm = current->mm;
int err;
mm = allocate_mm();
if (!mm)
goto fail_nomem;
memcpy(mm, oldmm, sizeof(*mm));
if (!mm_init(mm, tsk, mm->user_ns))
goto fail_nomem;
err = dup_mmap(mm, oldmm);
if (err)
goto free_pt;
mm->hiwater_rss = get_mm_rss(mm);
mm->hiwater_vm = mm->total_vm;
if (mm->binfmt && !try_module_get(mm->binfmt->module))
goto free_pt;
return mm;
free_pt:
/* don't put binfmt in mmput, we haven't got module yet */
mm->binfmt = NULL;
mmput(mm);
fail_nomem:
return NULL;
}
メモリディスクリプタ(struct mm_struct)内のmmapメンバ変数は各仮想アドレス空間(struct vm_area_struct)のリストの先頭を指していますが、 dup_mmapはfor文でこのリストを走査し、子プロセス向けのstruct vm_area_struct用の領域をvm_area_dupで確保します。
そして、copy_page_range以降でページテーブルのコピーを行います。
static __latent_entropy int dup_mmap(struct mm_struct *mm,
struct mm_struct *oldmm)
{
struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
struct rb_node **rb_link, *rb_parent;
int retval;
unsigned long charge;
LIST_HEAD(uf);
...
/*親プロセスの仮想アドレス空間を走査*/
for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
struct file *file;
...
/*親プロセスのvm_area_structをコピー*/
tmp = vm_area_dup(mpnt);
if (!tmp)
goto fail_nomem;
...
if (!(tmp->vm_flags & VM_WIPEONFORK))
retval = copy_page_range(mm, oldmm, mpnt);
...
ちなみに、struct vm_area_structはプロセスに割り当てられている仮想メモリ空間を表しており、以下のように定義されています。
struct vm_area_struct {
/* The first cache line has the info for VMA tree walking. */
unsigned long vm_start; /* Our start address within vm_mm. */
unsigned long vm_end; /* The first byte after our end address
within vm_mm. */
/* linked list of VM areas per task, sorted by address */
struct vm_area_struct *vm_next, *vm_prev;
...
pgprot_t vm_page_prot; /* Access permissions of this VMA. */
unsigned long vm_flags; /* Flags, see mm.h. */
...
struct file * vm_file; /* File we map to (can be NULL). */
...
プロセスの仮想メモリ空間の割当は以下のように/proc/pid/mapsで確認できますが、各行がvm_area_structを表しています。
開始アドレスはvm_start、終了アドレスはvm_end、パーミッション情報はvm_page_prot、inode情報はvm_fileのように、vm_area_structから抽出されています。
$ cat /proc/self/maps
00400000-0040c000 r-xp 00000000 08:01 4729393 /bin/cat
0060b000-0060c000 r--p 0000b000 08:01 4729393 /bin/cat
0060c000-0060d000 rw-p 0000c000 08:01 4729393 /bin/cat
02240000-02261000 rw-p 00000000 00:00 0 [heap]
7feaa45a4000-7feaa4979000 r--p 00000000 08:01 2886967 /usr/lib/locale/locale-archive
7feaa4979000-7feaa4b39000 r-xp 00000000 08:01 5767392 /lib/x86_64-linux-gnu/libc-2.23.so
7feaa4b39000-7feaa4d39000 ---p 001c0000 08:01 5767392 /lib/x86_64-linux-gnu/libc-2.23.so
7feaa4d39000-7feaa4d3d000 r--p 001c0000 08:01 5767392 /lib/x86_64-linux-gnu/libc-2.23.so
7feaa4d3d000-7feaa4d3f000 rw-p 001c4000 08:01 5767392 /lib/x86_64-linux-gnu/libc-2.23.so
7feaa4d3f000-7feaa4d43000 rw-p 00000000 00:00 0
7feaa4d43000-7feaa4d69000 r-xp 00000000 08:01 5767390 /lib/x86_64-linux-gnu/ld-2.23.so
7feaa4f24000-7feaa4f49000 rw-p 00000000 00:00 0
7feaa4f68000-7feaa4f69000 r--p 00025000 08:01 5767390 /lib/x86_64-linux-gnu/ld-2.23.so
7feaa4f69000-7feaa4f6a000 rw-p 00026000 08:01 5767390 /lib/x86_64-linux-gnu/ld-2.23.so
7feaa4f6a000-7feaa4f6b000 rw-p 00000000 00:00 0
7ffc2702b000-7ffc2704c000 rw-p 00000000 00:00 0 [stack]
7ffc270d7000-7ffc270da000 r--p 00000000 00:00 0 [vvar]
7ffc270da000-7ffc270dc000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
copy_page_rangeではvmaで指定された親プロセスの仮想アドレス空間に対応するページテーブルを子プロセス向けにコピーします。
ページテーブルは仮想アドレスを物理アドレスにマッピングするための変換テーブルで、プロセスごとに割り当てられます。
プロセスが仮想アドレスにアクセスした場合、実際にはこのテーブルによって変換された物理アドレスの指すメモリにアクセスすることになります。
ここで、ページテーブルは複数のレベルに分かれています。もしページテーブルが1次配列だとすると、仮想アドレスの取りうるサイズ分の配列サイズが必要となり、1つのプロセスのページテーブルを用意するだけで莫大なサイズとなってしまうためです。(32ビットアーキテクチャでは要素数が4G個必要)
ページテーブルは上位のレベルから、PGD、P4D、PUD、PMD、PTEと呼ばれています。上位のテーブルの各要素には次のレベルのテーブルへのアドレスが格納されます。
TODO _PAGE_PRESENTの説明
ただし、ページテーブルの実装はアーキテクチャに依存するため、すべてのアーキテクチャがこの構成というわけではありません。特にP4Dはカーネルバージョン4.11で導入されたらしく、その時点ではサポートしているハードはなかったようです(Five-level page tables参照)。
仮想アドレスから物理アドレスへの変換は上記のように複数のテーブルを辿ることになるため、仮想アドレスの実体は各テーブルのインデックス＋ページ内のオフセットになっています。
各テーブルの領域として1ページが使用されます。x86_64ではページサイズが4096バイト、アドレスサイズが8バイトなので、各テーブルの要素数は512個となります。
TODO 図で説明したい
ページテーブルについてはPage Tables、linux-memory等に詳しい説明があります。
copy_page_rangeは引数のvmaで指定された仮想アドレス空間に対応するPGDを走査します。
以降、上述のテーブル構成にしたがって、copy_p4d_range->copy_p4d_range->copy_pud_range->copy_pmd_range->copy_pte_rangeと関数を下っていきます。
各関数は大雑把には以下の処理を行っており、構成は似ています。
- 子プロセス向けのテーブル領域を確保する(XXX_alloc)
- 上位関数から指定された仮想アドレス(addr)に対応する親プロセスのテーブルを取得する(XXX_offset)
TODO もっと詳しく説明を書く
int copy_page_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
struct vm_area_struct *vma)
{
pgd_t *src_pgd, *dst_pgd;
unsigned long next;
unsigned long addr = vma->vm_start;
unsigned long end = vma->vm_end;
unsigned long mmun_start; /* For mmu_notifiers */
unsigned long mmun_end; /* For mmu_notifiers */
bool is_cow;
int ret;
...
ret = 0;
dst_pgd = pgd_offset(dst_mm, addr);
src_pgd = pgd_offset(src_mm, addr);
do {
next = pgd_addr_end(addr, end);
if (pgd_none_or_clear_bad(src_pgd))
continue;
if (unlikely(copy_p4d_range(dst_mm, src_mm, dst_pgd, src_pgd,
vma, addr, next))) {
ret = -ENOMEM;
break;
}
} while (dst_pgd++, src_pgd++, addr = next, addr != end);
...
static inline int copy_p4d_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
pgd_t *dst_pgd, pgd_t *src_pgd, struct vm_area_struct *vma,
unsigned long addr, unsigned long end)
{
p4d_t *src_p4d, *dst_p4d;
unsigned long next;
dst_p4d = p4d_alloc(dst_mm, dst_pgd, addr);
if (!dst_p4d)
return -ENOMEM;
src_p4d = p4d_offset(src_pgd, addr);
do {
next = p4d_addr_end(addr, end);
if (p4d_none_or_clear_bad(src_p4d))
continue;
if (copy_pud_range(dst_mm, src_mm, dst_p4d, src_p4d,
vma, addr, next))
return -ENOMEM;
} while (dst_p4d++, src_p4d++, addr = next, addr != end);
return 0;
}
static inline int copy_pud_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
p4d_t *dst_p4d, p4d_t *src_p4d, struct vm_area_struct *vma,
unsigned long addr, unsigned long end)
{
pud_t *src_pud, *dst_pud;
unsigned long next;
dst_pud = pud_alloc(dst_mm, dst_p4d, addr);
if (!dst_pud)
return -ENOMEM;
src_pud = pud_offset(src_p4d, addr);
do {
next = pud_addr_end(addr, end);
if (pud_trans_huge(*src_pud) || pud_devmap(*src_pud)) {
int err;
VM_BUG_ON_VMA(next-addr != HPAGE_PUD_SIZE, vma);
err = copy_huge_pud(dst_mm, src_mm,
dst_pud, src_pud, addr, vma);
if (err == -ENOMEM)
return -ENOMEM;
if (!err)
continue;
/* fall through */
}
if (pud_none_or_clear_bad(src_pud))
continue;
if (copy_pmd_range(dst_mm, src_mm, dst_pud, src_pud,
vma, addr, next))
return -ENOMEM;
} while (dst_pud++, src_pud++, addr = next, addr != end);
return 0;
}
static inline int copy_pmd_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
pud_t *dst_pud, pud_t *src_pud, struct vm_area_struct *vma,
unsigned long addr, unsigned long end)
{
pmd_t *src_pmd, *dst_pmd;
unsigned long next;
dst_pmd = pmd_alloc(dst_mm, dst_pud, addr);
if (!dst_pmd)
return -ENOMEM;
src_pmd = pmd_offset(src_pud, addr);
do {
next = pmd_addr_end(addr, end);
if (is_swap_pmd(*src_pmd) || pmd_trans_huge(*src_pmd)
|| pmd_devmap(*src_pmd)) {
int err;
VM_BUG_ON_VMA(next-addr != HPAGE_PMD_SIZE, vma);
err = copy_huge_pmd(dst_mm, src_mm,
dst_pmd, src_pmd, addr, vma);
if (err == -ENOMEM)
return -ENOMEM;
if (!err)
continue;
/* fall through */
}
if (pmd_none_or_clear_bad(src_pmd))
continue;
if (copy_pte_range(dst_mm, src_mm, dst_pmd, src_pmd,
vma, addr, next))
return -ENOMEM;
} while (dst_pmd++, src_pmd++, addr = next, addr != end);
return 0;
}
static int copy_pte_range(struct mm_struct *dst_mm, struct mm_struct *src_mm,
pmd_t *dst_pmd, pmd_t *src_pmd, struct vm_area_struct *vma,
unsigned long addr, unsigned long end)
{
pte_t *orig_src_pte, *orig_dst_pte;
pte_t *src_pte, *dst_pte;
spinlock_t *src_ptl, *dst_ptl;
int progress = 0;
int rss[NR_MM_COUNTERS];
swp_entry_t entry = (swp_entry_t){0};
again:
init_rss_vec(rss);
dst_pte = pte_alloc_map_lock(dst_mm, dst_pmd, addr, &dst_ptl);
if (!dst_pte)
return -ENOMEM;
src_pte = pte_offset_map(src_pmd, addr);
src_ptl = pte_lockptr(src_mm, src_pmd);
spin_lock_nested(src_ptl, SINGLE_DEPTH_NESTING);
orig_src_pte = src_pte;
orig_dst_pte = dst_pte;
arch_enter_lazy_mmu_mode();
do {
/*
* We are holding two locks at this point - either of them
* could generate latencies in another task on another CPU.
*/
if (progress >= 32) {
progress = 0;
if (need_resched() ||
spin_needbreak(src_ptl) || spin_needbreak(dst_ptl))
break;
}
if (pte_none(*src_pte)) {
progress++;
continue;
}
entry.val = copy_one_pte(dst_mm, src_mm, dst_pte, src_pte,
vma, addr, rss);
if (entry.val)
break;
progress += 8;
} while (dst_pte++, src_pte++, addr += PAGE_SIZE, addr != end);
arch_leave_lazy_mmu_mode();
spin_unlock(src_ptl);
pte_unmap(orig_src_pte);
add_mm_rss_vec(dst_mm, rss);
pte_unmap_unlock(orig_dst_pte, dst_ptl);
cond_resched();
if (entry.val) {
if (add_swap_count_continuation(entry, GFP_KERNEL) < 0)
return -ENOMEM;
progress = 0;
}
if (addr != end)
goto again;
return 0;
}
最後にcopy_one_pteにたどり着きました。この関数内でptep_set_wrprotectを実行し、親プロセスのメモリ領域にwrite protectをかけています。また、その下のpte_wrprotectで子プロセスのページにwrite protectを設定しています。
これにより、このページへの書き込み時にページフォールトが呼びだされ、コピーオンライトが実施されます。
TODO もっと詳しく説明を書く
/*
* copy one vm_area from one task to the other. Assumes the page tables
* already present in the new task to be cleared in the whole range
* covered by this vma.
*/
static inline unsigned long
copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,
pte_t *dst_pte, pte_t *src_pte, struct vm_area_struct *vma,
unsigned long addr, int *rss)
{
...
/*
* If it's a COW mapping, write protect it both
* in the parent and the child
*/
if (is_cow_mapping(vm_flags) && pte_write(pte)) {
ptep_set_wrprotect(src_mm, addr, src_pte);
pte = pte_wrprotect(pte);
}
...
out_set_pte:
set_pte_at(dst_mm, addr, dst_pte, pte);
return 0;
}
copy_one_pteでのwrite protect処理をなくしたらどうなるか
2018/12/24更新
uidが7777のときにwrite protect処理を行わないカーネルの動作を試してみましたが、uid=7777のユーザに切り替わるタイミングでbashが落ちてしまいました。
$ sudo su cow_test
*** stack smashing detected ***: bash terminated
単純にwrite protectを外しただけでは正常に動作しないようです。そのため、以下に記載の内容は実施不可のため、本実験は企画倒れとなってしまいました。
試しにcopy_one_pteで行っているwrite protectを外してみます。
ただし、単純にコメントアウトしてしまうと全プロセスに影響が出るため、システムがうまく立ち上がらなくなる可能性があります。
これを回避するために、特定のユーザがforkした場合にのみwrite protectを行わないようにしてみます。
以下の例ではuidが7777のユーザがforkした場合にはwrite protectを実行しないようにしています。
static inline unsigned long
copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,
pte_t *dst_pte, pte_t *src_pte, struct vm_area_struct *vma,
unsigned long addr, int *rss)
{
...
/*
* If it's a COW mapping, write protect it both
* in the parent and the child
*/
/* forkを実行したプロセスのuidが7777の場合はwrite protectを行わないようにする.
* 最近のkernelではcurrentからuidを直接参照できないようなので、
* __kuid_valとcurrent_uidマクロを使う */
/* if (is_cow_mapping(vm_flags) && pte_write(pte)) { */
if (is_cow_mapping(vm_flags) && pte_write(pte) && __kuid_val(current_uid()) != 7777) {
ptep_set_wrprotect(src_mm, addr, src_pte);
pte = pte_wrprotect(pte);
}
テストプログラムは
https://qiita.com/todok-r/items/1d83eb997e0c9e0d1baa
で作成したものを使用します。
uidを7777にするために、事前に以下のようにuid=7777のユーザ作成とそのユーザへの切り替えを行っておきます。
また、/proc/pid/pagemapを参照するためにroot権限が必要ですが、uidは7777で実行したいので、setuidビットを立てておきます。
ここではテストプログラムはa.outとします。
$ sudo chmod root:root a.out
$ sudo chmod ug+s a.out
$ sudo useradd cow_test -u 7777
$ sudo su cow_test
まとめ
コピーオンライト観点でfork時の処理の流れを見てみました。
知識不足のため、誤っている箇所も多々あるかと思います。気づいた点がありましたらご指摘いただけると幸いです。
参考文献
Linux Kernel Development
試して理解-Linuxのしくみ-実験と図解で学ぶOSとハードウェアの基礎知識
linux-memory
Five-level page tables
Page Tables