Asynchronous page fault解析

はじめに

Linux-2.6.38でマージされたAsynchronous page fault(非同期ページフォールト、以降APFと略す)について調べてみました。

(追記：ゲストのプロセス切り替え可能判定の間違いを修正しました。)

Asynchronous page faultとは？

近代的なOSでは、ページフォールト時にディスクアクセス(I/O)が必要になる場合は、別のプロセスにCPUを割り当てることで、I/O待ちの間もCPUを有効利用しようとします。KVMゲストの場合も同じで、ゲストカーネルが(結果的に)ホストにI/O要求を出した後、別のプロセスをディスパッチします。これが可能なのは、ゲストカーネル自身がI/Oを発行するからです。

しかしながら、仮想環境ではゲストカーネルが知らないところで(仮想でない)I/Oが発生することがあります。その一つが、ゲストメモリがホストでスワップアウトされていた場合です。ホストでスワップアウトされていたページにゲストがアクセスしたときには、ゲストには透過な状態でホストでI/Oが発生します。その場合、CPUは当該ゲスト(VCPU)から奪われ、別のVCPUやホストユーザプロセスに割り当てられます。ですが、ゲストの中にはCPU割り当て待ちの別のプロセスが存在するかもしれず、ゲストから見ると不当にCPUが割り当てられない状態になるかもしれません(もちろん当該VCPUのタイムスライスが残っていることが前提)。

KVMに実装されたAPFとは、この不公平を解消するものです。ゲストが知らないホストのI/Oが必要になる場合に、ゲストに処理を戻すことで、ゲストカーネルが別プロセスをディスパッチする機会を与えます。もしディスパッチ可能であれば、当該ゲストはCPUを継続的に利用することができます。これにより、当該ゲストのスループットは上がるはずです*1。

より詳しくは、KVM forum 2010でのGleb Natapov氏の発表資料を参照ください。とても解りやすいです。

対象バージョン

• Linux 2.6.39
• qemu-kvm-0.14.1
• EPTが有効なIntelプロセッサ

予備知識

• CPUID
  • KVMの準仮想化機能の有無をゲストに知らせるときに使う
  • KVMが使えるかどうか調べるとき(grep vmx /proc/cpuinfo)のアレ
  • 仮想化環境ではハイパーバイザが柔軟に設定可能
• MSR
  • CPU固有の機能のために用意されたレジスタ
  • 仮想化環境ではハイパーバイザが柔軟に設定可能。また書き込み時にVM exitを起こすことも可能
  • APFではゲストからホストへ情報を送るときに使用される(後述)

動作概要

1. 初期化
   • ホスト・ゲストでお互いに機能の有無を調べる
2. ページフォールト
   • ホストでスワップアウトされたページにゲストがアクセスするとVM exitが起きる
   • ページの準備(スワップイン)ã‚’workqueueに任せて、ゲストに処理を戻す
   • ゲストは当該プロセスを待ち状態にして別のプロセスをディスパッチする
3. I/O発行とI/O完了
   • workqueueは普通にページアクセスしてスワップインを起こさせる
   • ページの準備が完了したら、その旨をKVM本体に伝える(完了キューにつなぐ)
   • KVM本体はメインループで定期的にチェックすることで準備が完了したことを知る
4. ゲストへの通知とページフォールト(再)
   • ホストはページが準備完了した旨をページフォールトを起こすことでゲストに知らせる
   • ゲストは待ち状態のプロセスを起こす

大雑把にはこのような動作をしますが、実際にはページフォールトが起きた状態によって動作が変わってきます。以下では、その辺りを含めた詳細を説明しています。

初期化

APFは準仮想化機能です。ホストはゲストがAPF機能を持っていることを確認してから初期化を行ないます。

動作概要は以下の通り。

1. ホスト
   • qemuがKVMにCPUIDを設定する(ioctl)。このときAPFが有効であることを含めておく
   • KVMはそのCPUIDを仮想マシン(VMCS)に設定する
2. ゲスト
   • カーネルはブート時にCPUIDを調べ、APFが有効になっていた場合、MSRの当該レジスタに書き込む(wrmsr)ことでホストにACKする
   • このとき、書き込む内容にゲストカーネルが割り当てているCPU毎の変数(per cpu var、以降APF要因変数と呼ぶ)のアドレス含める
3. ホスト
   • wrmsrによりVM exitが発生し、ゲストがAPFに対応していることを知る
   • APF要因変数のアドレスを覚えておく(後で、ページフォールト時に利用する)

以降は重要な部分だけコードを見ながら説明していきます。ホストでCPUIDを設定するところは省略して、ゲストがブートする部分からです。

まずゲストカーネルはホストのAPFが有効であることがわかると、ページフォールト割り込みハンドラを、(do_)page_fault()から(do_)async_page_fault()へ変更します。

static void __init kvm_apf_trap_init(void)
{
        set_intr_gate(14, &async_page_fault);
}

(do_)async_page_fault()はページフォールト時にAPFかどうかチェックして、APFならばAPF要因毎のハンドラ(後述)を呼び出し、そうでなければdo_page_fault()を呼びます*2。

続いて、CPU毎の初期化処理の途中でKVMゲスト向け初期化関数kvm_guest_cpu_init()が呼ばれます。

void __cpuinit kvm_guest_cpu_init(void)
{
        if (!kvm_para_available())
                return;

        if (kvm_para_has_feature(KVM_FEATURE_ASYNC_PF) && kvmapf) {
                u64 pa = __pa(&__get_cpu_var(apf_reason));

#ifdef CONFIG_PREEMPT
                pa |= KVM_ASYNC_PF_SEND_ALWAYS;
#endif
                wrmsrl(MSR_KVM_ASYNC_PF_EN, pa | KVM_ASYNC_PF_ENABLED);
                __get_cpu_var(apf_reason).enabled = 1;
                printk(KERN_INFO"KVM setup async PF for cpu %d\n",
                       smp_processor_id());
        }
}

kvm_para_has_feature()でAPFが有効であることがわかると、__get_cpu_var(apf_reason)でAPF要因変数のアドレスにフラグを加えたものをMSRに書き込みます*3。このapf_reasonは、前述のゲストのページフォールトハンドラの分岐判定に使われます。

フラグに関してですが、CONFIG_PREEMPTが有効のときにKVM_ASYNC_PF_SEND_ALWAYSが設定されています。CONFIG_PREEMPTが有効になっている場合は、ここの説明のとおり、カーネル内コードを実行中にプロセス切り替え可能です。逆に有効でない場合は、もしAPFでホストからプロセス切り替えの機会を与えられても困ります。KVM_ASYNC_PF_SEND_ALWAYSã‚’offにしておくと、ページフォールト時にゲストのCPLが0の場合は、ホストはAPFでゲストに処理を戻さないようになります(後述)。

wrmsrl()でMSR書き込み専用命令が呼ばれるとVM exitが起き、処理がホストに戻ります。ホストでは最終的にkvm_pv_enable_async_pf()が呼ばれます。

static int kvm_pv_enable_async_pf(struct kvm_vcpu *vcpu, u64 data)
{
        gpa_t gpa = data & ~0x3f;

        /* Bits 2:5 are resrved, Should be zero */
        if (data & 0x3c)
                return 1;

        vcpu->arch.apf.msr_val = data;

        if (!(data & KVM_ASYNC_PF_ENABLED)) {
                kvm_clear_async_pf_completion_queue(vcpu);
                kvm_async_pf_hash_reset(vcpu);
                return 0;
        }

        if (kvm_gfn_to_hva_cache_init(vcpu->kvm, &vcpu->arch.apf.data, gpa))
                return 1;

        vcpu->arch.apf.send_user_only = !(data & KVM_ASYNC_PF_SEND_ALWAYS);
        kvm_async_pf_wakeup_all(vcpu);
        return 0;
}

ここでは、渡されたAPF要因変数のアドレスを登録し、素早く書き込みできるようにkvm_gfn_to_hva_cache_init()でキャッシュを設定しています。このキャッシュはゲスト物理アドレス→ホスト仮想アドレス(qemuプロセスのアドレス)変換結果を保持するもので、後述のkvm_write_guest_cached()で使われます。

またKVM_ASYNC_PF_SEND_ALWAYSフラグがoffのとき、send_user_only = trueと設定され、ゲストがユーザモードで動いているときだけAPFの割り込みが送られるようになります。

ページフォールト

ホストでスワップアウトされたページにゲストがアクセスした場合は、VM exitが起きてホストに処理が移ります。まずはそちらの処理内容から説明していきます。

ホスト

1. KVMカーネルモジュールのページフォールトハンドラ(tdp_page_fault())でI/Oが必要になるかチェックする
   • __get_user_pages_fast()というI/Oが必要な場合はエラーを返す関数を使う
2. I/Oが必要な場合、workqueueにI/Oを実行する仕事を登録する
   • 登録先workqueueはCPU毎に用意されるシステムグローバルなもの([events/?]という名前をもつスレッド)
3. VM entry時にゲストにページフォールト割り込みが発生するように設定する
   • APF要因変数に当該ページがホストでスワップアウトされている旨を書いておく
4. VM entryする
   • しない場合もある(後述)

ページフォールトハンドラはtry_async_pf() → gfn_to_pfn_async() …→ __get_user_pages_fast() と呼び出し、I/Oなしで当該ページが存在するかチェックします。もし存在しなければ、kvm_arch_setup_async_pf() → kvm_setup_async_pf()でworkqueueの初期化をします(workqueueの処理内容は後述)。その後、kvm_arch_async_page_not_present()でゲストにAPF割り込みをかけようとします。

void kvm_arch_async_page_not_present(struct kvm_vcpu *vcpu,
                                     struct kvm_async_pf *work)
{
        struct x86_exception fault;

        trace_kvm_async_pf_not_present(work->arch.token, work->gva);
        kvm_add_async_pf_gfn(vcpu, work->arch.gfn);

        if (!(vcpu->arch.apf.msr_val & KVM_ASYNC_PF_ENABLED) ||
            (vcpu->arch.apf.send_user_only &&
             kvm_x86_ops->get_cpl(vcpu) == 0))
                kvm_make_request(KVM_REQ_APF_HALT, vcpu);
        else if (!apf_put_user(vcpu, KVM_PV_REASON_PAGE_NOT_PRESENT)) {
                fault.vector = PF_VECTOR;
                fault.error_code_valid = true;
                fault.error_code = 0;
                fault.nested_page_fault = false;
                fault.address = work->arch.token;
                kvm_inject_page_fault(vcpu, &fault);
        }
}

まずゲストにAPF割り込み可能かどうかチェックします。ゲストで有効になっていないか、send_user_only=trueかつゲストがカーネルモードのときにページフォールトが起きた場合は、割り込みをかけません。代わりにVCPUをhaltさせます。

Halt状態のVCPUは、溜まっているシグナルの処理などは実行しますが、条件が整うまでVM entryしなくなります。APFの場合は、workqueueで実行されているI/Oが完了するまでhaltのままになります。

APF割り込みに可能な場合は、apf_put_user()でAPF要因変数にページフォールト要因(KVM_PV_REASON_PAGE_NOT_PRESENT)を書き込み、KVMに割り込みを起こさせるように設定しています。なお、APF要因変数はqemuプロセスのメモリ上(のゲストのメモリ領域)に見えているので、書き込みにはcopy_to_user()を用いることになります。

ゲスト

1. 割り込みハンドラ(do_async_page_fault())が呼ばれる
2. カレントプロセスをwaitqueueに入れて、可能ならプロセス切り替え(schedule())を行なう
3. プロセス切り替えできない場合は、CPUをhaltさせる

まずページフォールトハンドラです。

dotraplinkage void __kprobes
do_async_page_fault(struct pt_regs *regs, unsigned long error_code)
{
        switch (kvm_read_and_reset_pf_reason()) {
        default:
                do_page_fault(regs, error_code);
                break;
        case KVM_PV_REASON_PAGE_NOT_PRESENT:
                /* page is swapped out by the host. */
                kvm_async_pf_task_wait((u32)read_cr2());
                break;
        case KVM_PV_REASON_PAGE_READY:
                kvm_async_pf_task_wake((u32)read_cr2());
                break;
        }
}

kvm_read_and_reset_pf_reason()で、ホストが設定したAPF要因変数を調べて分岐します。ここでは、KVM_PV_REASON_PAGE_NOT_PRESENTがセットされてるはずなので、kvm_async_pf_task_wait()が呼ばれます。

void kvm_async_pf_task_wait(u32 token)
{
        u32 key = hash_32(token, KVM_TASK_SLEEP_HASHBITS);
        struct kvm_task_sleep_head *b = &async_pf_sleepers[key];
        struct kvm_task_sleep_node n, *e;
        DEFINE_WAIT(wait);
        int cpu, idle;

        cpu = get_cpu();
        idle = idle_cpu(cpu);
        put_cpu();

        spin_lock(&b->lock);
        e = _find_apf_task(b, token);
        if (e) {
                /* dummy entry exist -> wake up was delivered ahead of PF */
                hlist_del(&e->link);
                kfree(e);
                spin_unlock(&b->lock);
                return;
        }

        n.token = token;
        n.cpu = smp_processor_id();
        n.mm = current->active_mm;
        n.halted = idle || preempt_count() > 1;
        atomic_inc(&n.mm->mm_count);
        init_waitqueue_head(&n.wq);
        hlist_add_head(&n.link, &b->list);
        spin_unlock(&b->lock);

        for (;;) {
                if (!n.halted)
                        prepare_to_wait(&n.wq, &wait, TASK_UNINTERRUPTIBLE);
                if (hlist_unhashed(&n.link))
                        break;

                if (!n.halted) {
                        local_irq_enable();
                        schedule(); /* ※プロセス切り替え */
                        local_irq_disable();
                } else {
                        /*
                         * We cannot reschedule. So halt.
                         */
                        native_safe_halt();
                        local_irq_disable();
                }
        }
        if (!n.halted)
                finish_wait(&n.wq, &wait);

        return;
}

長いですが、コメントに書いた「※プロセス切り替え」の箇所が一番正常なパスです。ユーザモードでページフォールトが起きたときは、ほとんどの場合は、プロセスを待ち状態に設定した後、ここで他のプロセスをディスパッチするはずです。

しかし、コードを見てみるとschedule()ではなく、native_safe_halt()が呼ばれる、つまりCPUをhaltさせているパスもあります。どういった場合にこうなるのでしょうか？

[修正]native_safe_halt()が呼ばれるのはn.halted=trueのときです。そうなるのは、まずカレントプロセスがidleプロセスのときです。カレントプロセスがidleプロセスということは、他にCPUを割り当てるべきプロセスがいないということなので、haltにするのは妥当です。

次にCPUを横取り可能できるかどうか調べています。preempt_count() > 1の箇所です。(通常ならば、preempt_count() > 0でチェックするところなのですが、上の方でspin_lock()を呼んでいるのでそれを考慮して> 1となっています。)この条件式がtrueになるのは、割り込みコンテキストで動いているときと、ロックを保持しているときです。このカウンタがどう扱われているかはこちらを参照ください。またロックを保持したままCPUを横取りするとまずい理由はpreempt-locking.txtを参照してください。[/修正]

Haltした場合は、ホストがそれを検出可能なので、別の仮想マシンやホストプロセスにCPUがディスパッチされるはずです。

I/O発行とI/O完了

ここでは、実際にI/Oを発行させているworkqueueの設定と完了処理を見ていきます。

1. workqueueにはasync_pf_execute()が設定される
2. カーネルスレッド([events/?])がasync_pf_execute()を呼ぶ
   • APF I/O用のオブジェクトを割り当てる
   • get_user_pages()を呼ぶ。結果I/O(スワップイン)が発生する
3. I/Oが完了したらAPF I/O完了リストに上記オブジェクトをつなぐ

workqueueはプロセスコンテキストで動いておりsleep可能です。つまり、普通のユーザプロセスでページフォールトが発生した状態とほぼ同じ状況になります。

APF I/O完了リスト登録は以下の通りで、後述のVCPUループ(KVMのメインループ)でこのリストがチェックされます。

list_add_tail(&apf->link, &vcpu->async_pf.done);

ゲストへの通知とページフォールト(再)

当該ページがスワップインされたら、その旨をゲストに通知し、ゲストは当該プロセスを起床させます。

1. ホスト
   • VCPUのループでI/O完了を定期的にチェックする
   • 完了していたら、KVMページフォールトハンドラを再度呼び出してSPTEを設定する
   • APF要因変数のフラグを立ててゲストに割り込みをかける
2. ゲスト
   • 割り込みハンドラが呼ばれる
   • 当該プロセス(プロセスコンテキストで実行中のカーネル、カーネルスレッドもあり得る)を起こす。

完了チェックは__vcpu_run()のループ内のkvm_check_async_pf_completion()で行なわれます。もし完了していたら、kvm_arch_async_page_ready() → tdp_page_fault()と呼び、SPTEを設定します。(SPTEの設定に関しては d:id:kvm:20110514 を参照ください。)

その後、kvm_check_async_pf_completion()はkvm_arch_async_page_present()を呼んで、APF要因変数をKVM_PV_REASON_PAGE_READYに設定し、ゲストに割り込みがかかるように設定します(KVM_PV_REASON_PAGE_NOT_PRESENTの場合とだいたい同じなのでコードは省略)。なお、ここでVCPUのhalt状態が解除され、VM entryするようになります。

割り込みを受けたゲストは、do_async_page_fault() → kvm_async_pf_task_wake() → apf_task_wake_one()と呼びます。

static void apf_task_wake_one(struct kvm_task_sleep_node *n)
{
        hlist_del_init(&n->link);
        if (!n->mm)
                return;
        mmdrop(n->mm);
        if (n->halted)
                smp_send_reschedule(n->cpu);
        else if (waitqueue_active(&n->wq))
                wake_up(&n->wq);
}

起こす対象がhaltしてる場合は、この割り込みハンドラは別の(V)CPUで動いているはずなので、IPIでCPUを起こします(smp_send_reschedule())。そうでなければ、当該プロセスを起床させます。

おわりに

いろいろと端折っていますが、APFの動作をひと通り見ていきました。

思ったより複雑で、カーネルやハードウェアに関する知識がないと理解するのが難しかったです。非同期処理を実現するのはやっぱり大変ですね。

以下は、コードを読むときに参考にしたサイト、コミットやコードの関数定義などへのリンクを付録として付けました。(本文中でリンクを張ると本文の編集がやりにくかったので付録にしました。)APFを読んでみようと思った人の参考になれば幸いです。

参考文献

• kernelnewbie.org
• KVM forum 2010
• CPUIDとMSR
  • Documentation/kvm/msr.txt
  • Documentation/kvm/cpuid.txt
  • http://en.wikipedia.org/wiki/Machine_state_register
  • http://mcn.oops.jp/wiki/index.php?CPU%2FCPUID
  • http://mcn.oops.jp/wiki/index.php?CPU%2FCPUID%2FMSR

関連コミット(主要なもの)

カーネル

• KVM: Halt vcpu if page it tries to access is swapped out
• KVM: Retry fault before vmentry
• KVM: Add PV MSR to enable asynchronous page faults delivery
• KVM: Handle async PF in a guest
• KVM: Inject asynchronous page fault into a PV guest if page is swapped out
• KVM paravirt: Handle async PF in non preemptable context
• KVM: Let host know whether the guest can handle async PF in non-userspace context
• KVM: Send async PF when guest is not in userspace too
• KVM: expose async pf through our standard mechanism

qemu-kvm

• Add support for async page fault to qemu

関連ソースコード(主要なもの)

• virt/kvm/async_pf.c
• virt/kvm/async_pf.h
• virt/kvm/kvm_main.c
• arch/x86/kvm/x86.c
• arch/x86/kvm/mmu.c
• arch/x86/kvm/paging_tmpl.h
• arch/x86/kernel/kvm.c
• arch/x86/kernel/entry_32.S
• arch/x86/kernel/entry_64.S

個々の関数や構造体などへのリンク

• tdp_page_fault()
• try_async_pf()
• hva_to_pfn()
• __get_user_pages_fast()
• kvm_arch_async_page_not_present()
• kvm_arch_async_page_present()
• KVM_REQ_APF_HALT
• struct kvm_async_pf
• struct kvm_arch_async_pf
• kvm_make_request()
• struct kvm_vcpu_arch.apf
• kvm_setup_async_pf()
• kvm_arch_setup_async_pf()
• kvm_arch_async_page_ready()
• kvm_check_async_pf_completion()
• __vcpu_run()
• kvm_inject_page_fault()
• async_pf_execute()
• schedule_work()
• get_user_pages()
• kvm_apf_trap_init()
• do_async_page_fault()
• kvm_guest_cpu_init()
• struct kvm_vcpu_pv_apf_data
• apf_reason
• apf_put_user()
• kvm_gfn_to_hva_cache_init()

*1:注：ホスト視点では、他にディスパッチ可能なプロセスがいる場合はスループットは変わらないかもしれません。

*2:つまり、通常のページフォールト時のオーバヘッドが少し増える。

*3:apf_reasonは64bitでalignされているので、下位6bitをフラグに使えます。