KVMのなかみ(KVM internals)

VMMの高速化について学ぶ過程でKVMのコードを読んだので、
メモ代わりに内部構造の解説記事を書きました。

KVMはqemuと連携して動作するため、以前私が書いたQEMU internals( http://rkx1209.hatenablog.com/entry/2015/11/15/214404 )
も合わせてご参照ください。また本記事はある程度システムプログラムに慣れており、
VT-xや仮想化の基本アーキテクチャは知っている物として進めます。

1.qemu-kvm,kvmの初期化
では早速見て行きましょう。まずはKVMの初期化の入り口となるqemu-kvmサイドから見ていきます。(ちなみに現在qemu-kvmはqemu本家に統合されておりconfigを変えることでkvmを有効化する仕様になっています)

qemuは/dev/kvmを通してKVMとやり取りを行います。全体的なアーキテクチャは以下のような感じです。

http://vm360degree.com/2011/09/24/2011-red-hat-forum-%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%97%E0%B8%B5%E0%B9%88-1-%E2%80%93-kvm-kernel-base-virtual-machine-%E0%B8%84%E0%B8%B7%E0%B8%AD-%E0%B8%AD%E0%B8%B0%E0%B9%84%E0%B8%A3/より
実際の初期化コードは以下のようになります。

(QEMU: kvm-all.c)

static int kvm_init(MachineState *ms)
{
    MachineClass *mc = MACHINE_GET_CLASS(ms);
    ...
    s = KVM_STATE(ms->accelerator); [*1]
    ...
    s->vmfd = -1;
    s->fd = qemu_open("/dev/kvm", O_RDWR); [*2]
    ...

    /* check the vcpu limits */
    soft_vcpus_limit = kvm_recommended_vcpus(s); [*3]
    hard_vcpus_limit = kvm_max_vcpus(s);
    ...
    do {
        ret = kvm_ioctl(s, KVM_CREATE_VM, type); [*4]
    } while (ret == -EINTR);

    ...
    s->vmfd = ret; [*5]
    ...

    if (machine_kernel_irqchip_allowed(ms)) { [*25]
        kvm_irqchip_create(ms, s); [*26]
    }

    kvm_state = s;
    ...
    return 0;
}

[*1]でMachineClassからAccelStateにアクセスしています。KVMState(kvm-all.c)はAccelStateを継承しておりこれもポリモーフィズムですね。(ポリモーフィズムの実現方法などはqemu internalsに載っています)

さて[*2]で/dev/kvmをopenしていますがこれは上でも述べたように、qemuがカーネルモジュールであるkvm.koとやり取りするためのインタフェースとして使用されます。

[*3]でKVMの必要とするCPUの数を調べています。中身はkvm_ioctl(kvm-all.c)を使って/dev/kvmにioctlでKVM_CHECK_EXTENSIONリクエストを飛ばしています。qemu-kvmはkvm_ioctlを利用してこのようなリクエストを頻繁に送ります。これらリクエストはKVMのAPIとして定義されています。(KVMのAPIはDocumentation/virtual/kvm/api.txtにマニュアルがあります)

[*4]でKVM_CREATE_VMを発行しKVM用のVMを作成するよう依頼します。

[*5]では作成したVMのfdをvmfdに代入しています。VMはKVMにおいてkvm-vmという名前のanonymous-inodeとして管理されており[*4]ではそのfdが返り値となっているわけです。

では次にKVMサイドの初期化処理を見て行きましょう。

(KVM: arch/x86/kvm/vmx.c)

static int __init vmx_init(void)
{
	int r = kvm_init(&vmx_x86_ops, sizeof(struct vcpu_vmx),
                     __alignof__(struct vcpu_vmx), THIS_MODULE); [*7]
	if (r)
		return r;
	...
	return 0;
}
...
module_init(vmx_init) [*6]

arch/x86/kvm/vmx.cはIntelのVT-Xを扱うKVMモジュールで、[*6]でvmx_initをカーネルモジュールの初期化関数として登録しています。また[*7]のkvm_initの第1引数にvmx_x86_opsのアドレスを渡しています。vmx_x86_opsはkvm_x86_ops構造体で、これはx86特有の操作を関数としてまとめた物です。(後で何度も出てくる重要な構造体です)

(KVM: virt/kvm/kvm_main.c)

int kvm_init(void *opaque, unsigned vcpu_size, unsigned vcpu_align,
		  struct module *module)
{
	int r;
	int cpu;

	...
	kvm_vcpu_cache = kmem_cache_create("kvm_vcpu", vcpu_size, vcpu_align,
					   0, NULL);
	...
	kvm_chardev_ops.owner = module;
	kvm_vm_fops.owner = module;
	kvm_vcpu_fops.owner = module;

	r = misc_register(&kvm_dev); [*8]
	...
	return 0;
	...
}

[*8]でkvm_devをmiscdeviceとして登録しています。miscdeviceはメジャー番号が10に固定されマイナー番号で識別されるキャラクタデバイスでここにkvmという名前のデバイスを登録します。(これが/dev/kvmデバイスとなるわけです)

kvm_devは以下のように定義されています。
(KVM: virt/kvm/kvm_main.c)

static struct file_operations kvm_chardev_ops = {
	.unlocked_ioctl = kvm_dev_ioctl,
	.compat_ioctl   = kvm_dev_ioctl,
	.llseek		= noop_llseek,
};

static struct miscdevice kvm_dev = {
	KVM_MINOR,
	"kvm",
	&kvm_chardev_ops,
};

(KVM: virt/kvm/kvm_main.c)

static long kvm_dev_ioctl(struct file *filp,
			  unsigned int ioctl, unsigned long arg)
{
	long r = -EINVAL;

	switch (ioctl) {
	case KVM_CREATE_VM:
		r = kvm_dev_ioctl_create_vm(arg); [*9]
		break;
	...
	}
out:
	return r;
}

[*9]のKVM_CREATE_VMを見てください。これは/dev/kvmにKVM_CREATE_VMがioctlで発行された場合に処理される箇所です。QEMUサイドの初期化で発行されていましたね。ここではkvm_dev_ioctl_create_vmを呼び出しVMを作成しています。

(KVM: virt/kvm/kvm_main.c)

static int kvm_dev_ioctl_create_vm(unsigned long type)
{
	int r;
	struct kvm *kvm;

	kvm = kvm_create_vm(type); [*10]
	...
	r = anon_inode_getfd("kvm-vm", &kvm_vm_fops, kvm, O_RDWR | O_CLOEXEC); [*11]
	if (r < 0)
		kvm_put_kvm(kvm);

	return r;
}

[*10]でVMを作成した後[*11]で"kvm-vm"という名前のanonymous-inodeを作成しています。これがVMの実体であり、上でも説明したようにqemu-kvmからアクセスする際はこのinodeのfdを通して行います。またkvm_vm_fopsは

(KVM: virt/kvm/kvm_main.c)

static struct file_operations kvm_vm_fops = {
	.release        = kvm_vm_release,
	.unlocked_ioctl = kvm_vm_ioctl,
#ifdef CONFIG_KVM_COMPAT
	.compat_ioctl   = kvm_vm_compat_ioctl,
#endif
	.llseek		= noop_llseek,
};

となっており、VMに対するioctlはkvm_vm_ioctlで処理されます。

では[*10]のkvm_create_vmについて見て行きましょう。

(KVM: virt/kvm/kvm_main.c)

static struct kvm *kvm_create_vm(unsigned long type)
{
	int r, i;
	struct kvm *kvm = kvm_arch_alloc_vm(); [*12]
	...
	r = -ENOMEM;
	for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) {
		kvm->memslots[i] = kvm_alloc_memslots(); [*13]
		if (!kvm->memslots[i])
			goto out_err_no_srcu;
	}
	...
	for (i = 0; i < KVM_NR_BUSES; i++) {
		kvm->buses[i] = kzalloc(sizeof(struct kvm_io_bus),
					GFP_KERNEL); [*14]
		if (!kvm->buses[i])
			goto out_err;
	}
	...

	r = kvm_init_mmu_notifier(kvm); [*15]
	...
	return kvm;
	...
}

[*12]のkvm_arch_alloc_vm(include/linux/kvm_host.h)で新たなkvm構造体(include/linux/kvm_host.h)を確保しています。kvm構造体はゲストごとにそれぞれ一つずつ存在します。

[*13]のkvm_alloc_memslots(arch/x86/kvm/kvm_main.c)でメモリスロットをそれぞれ確保し初期化しています。また[*14]ではkvm_io_busを初期化しています。

[*15]のkvm_init_mmu_notifier(arch/x86/kvm/kvm_main.c)はMMU notifierフックハンドラを登録する関数です。MMU notifierはゲストのページテーブルが指すページテーブルエントリがホストOSによってスワップ(イン|アウト)された際にゲストへ通知するために呼ばれます。これはゲストOS側のカーネルが知らない間にホスト側でpteがスワップアウトされた場合、ゲスト側のメモリ管理が破綻してしまうのを防ぐためです。

では次にkvmにおけるvcpuの初期化を見ていきます。

ここでQEMU internals part1( http://rkx1209.hatenablog.com/entry/2015/11/15/214404 )の4.仮想CPUにもあるqemu_init_vcpuの処理を見てみましょう。

(QEMU: cpus.c)

static void qemu_kvm_start_vcpu(CPUState *cpu)
{
    char thread_name[VCPU_THREAD_NAME_SIZE];

    cpu->thread = g_malloc0(sizeof(QemuThread));
    cpu->halt_cond = g_malloc0(sizeof(QemuCond));
    qemu_cond_init(cpu->halt_cond);
    snprintf(thread_name, VCPU_THREAD_NAME_SIZE, "CPU %d/KVM",
             cpu->cpu_index);
    qemu_thread_create(cpu->thread, thread_name, qemu_kvm_cpu_thread_fn,
                       cpu, QEMU_THREAD_JOINABLE); [*18]
    while (!cpu->created) {
        qemu_cond_wait(&qemu_cpu_cond, &qemu_global_mutex); [*19]
    }
}

void qemu_init_vcpu(CPUState *cpu)
{
    cpu->nr_cores = smp_cores;
    cpu->nr_threads = smp_threads;
    cpu->stopped = true;
    if (kvm_enabled()) {
        qemu_kvm_start_vcpu(cpu); [*17]
    } else if (tcg_enabled()) {
        qemu_tcg_init_vcpu(cpu);[*16]
    } else {
        qemu_dummy_start_vcpu(cpu);
    }
}

QEMU internalsでは[*16]のqemu_tcg_init_vcpuを見ていきましたが、
kvmが有効な場合[*17]でqemu_kvm_start_vcpuが呼び出されるため今回はこちらを見ます。
qemu_kvm_start_vcpuでは[*18]でqemu_kvm_cpu_thread_fnを実行するvcpuスレッドを作成し、vcpuがキックインされるまで[*19]で待ちます。

ではqemu_kvm_cpu_thread_fnを見てみましょう。

(QEMU: cpus.c)

static void *qemu_kvm_cpu_thread_fn(void *arg)
{
    CPUState *cpu = arg;
    int r;

    current_cpu = cpu;
    ...
    r = kvm_init_vcpu(cpu); [*20]
    ...
    qemu_kvm_init_cpu_signals(cpu);

    /* signal CPU creation */
    cpu->created = true; [*23]
    qemu_cond_signal(&qemu_cpu_cond);

    while (1) {
        if (cpu_can_run(cpu)) {
            r = kvm_cpu_exec(cpu); [*24]
            if (r == EXCP_DEBUG) {
                cpu_handle_guest_debug(cpu);
            }
        }
        qemu_kvm_wait_io_event(cpu);
    }

    return NULL;
}

[*20]のkvm_init_vcpuでvcpuの初期化を行います。

(QEMU: kvm-all.c)

int kvm_init_vcpu(CPUState *cpu)
{
    KVMState *s = kvm_state;
    long mmap_size;
    int ret;

    DPRINTF("kvm_init_vcpu\n");

    ret = kvm_vm_ioctl(s, KVM_CREATE_VCPU, (void *)kvm_arch_vcpu_id(cpu)); [*21]

    cpu->kvm_fd = ret; [*22]
    cpu->kvm_state = s;
    cpu->kvm_vcpu_dirty = true;

    mmap_size = kvm_ioctl(s, KVM_GET_VCPU_MMAP_SIZE, 0);
    ...
    cpu->kvm_run = mmap(NULL, mmap_size, PROT_READ | PROT_WRITE, MAP_SHARED,
                        cpu->kvm_fd, 0);
    ...
    ret = kvm_arch_init_vcpu(cpu);
err:
    return ret;
}

[*21]でKVM_CREATE_VCPUを発行し[*22]でCPUStateのkvm_fdに代入しています。

vcpuの初期化が終われば[*23]でcreatedにtrueを設定しシグナルで通知します。

これでKVMにおける/dev/kvmデバイス,vCPU,VMの初期化が終わりました。
まとめると

• /dev/kvm(キャラクタデバイス)

KVM自体の制御に使われるインターフェース
qemu-kvm側からはkvm_ioctlでアクセス

• vCPU(anonymous-inode)

KVMのvCPUに対する制御を行うインターフェース
qemu-kvm側からはkvm_vcpu_ioctlでアクセス
ioctlのハンドラはKVM側のkvm_vcpu_fopsが用いられる。

• VM(anonymous-inode)

KVM自体の制御に使われるインターフェース
qemu-kvm側からはkvm_vm_ioctlでアクセス
ioctlのハンドラはKVM側のkvm_vm_fopsが用いられる。

となります。

さてではいよいよメイン処理を見て行きましょう。
[*24]のkvm_cpu_execがKVMの中心処理です。

2.仮想CPU(vCPU)

kvm_cpu_execはVMEnterしてからVMExitするまでの一回分の処理を担当します。

(QEMU: kvm-all.c)

int kvm_cpu_exec(CPUState *cpu)
{
    struct kvm_run *run = cpu->kvm_run;
    int ret, run_ret;
    ...
    do {
        MemTxAttrs attrs;
	...
        run_ret = kvm_vcpu_ioctl(cpu, KVM_RUN, 0); [*1]

	...
        switch (run->exit_reason) {
        case KVM_EXIT_IO:
            DPRINTF("handle_io\n");
            /* Called outside BQL */
            kvm_handle_io(run->io.port, attrs,
                          (uint8_t *)run + run->io.data_offset,
                          run->io.direction,
                          run->io.size,
                          run->io.count); [*14]
            ret = 0;
            break;
        case KVM_EXIT_MMIO:
            DPRINTF("handle_mmio\n");
            /* Called outside BQL */
            address_space_rw(&address_space_memory,
                             run->mmio.phys_addr, attrs,
                             run->mmio.data,
                             run->mmio.len,
                             run->mmio.is_write); [*15]
            ret = 0;
            break;
	...
        }
    } while (ret == 0);
    ...
    return ret;
}

[*1]でKVM_RUNを発行しKVMにVMEnterを行うよう指示しています。
vcpuに対してioctlが発行された場合、KVM側では以下のような処理が行われます。
(KVM: virt/kvm/kvm_main.c)

static long kvm_vcpu_ioctl(struct file *filp,
			   unsigned int ioctl, unsigned long arg)
{
	struct kvm_vcpu *vcpu = filp->private_data;
	...
	r = vcpu_load(vcpu);
	if (r)
		return r;
	switch (ioctl) {
	case KVM_RUN:
		...
		r = kvm_arch_vcpu_ioctl_run(vcpu, vcpu->run); [*2]
		...
		break;
	...
	return r;
}		

[*2]がKVM_RUNのフック関数です。実際の処理はこのkvm_arch_vcpu_ioctl_runに投げています。

(KVM: arch/x86/kvm/x86.c)

int kvm_arch_vcpu_ioctl_run(struct kvm_vcpu *vcpu, struct kvm_run *kvm_run)
{
	struct fpu *fpu = &current->thread.fpu;
	int r;
	sigset_t sigsaved;
	...

	r = vcpu_run(vcpu); [*3]

	...
	return r;
}

[*3]のvcpu_runで実際にゲストへenterします。

(KVM: arch/x86/kvm/x86.c)

static int vcpu_run(struct kvm_vcpu *vcpu)
{
	int r;
	struct kvm *kvm = vcpu->kvm;

	vcpu->srcu_idx = srcu_read_lock(&kvm->srcu);

	for (;;) {
		if (kvm_vcpu_running(vcpu)) {
			r = vcpu_enter_guest(vcpu); [*4]
		}
		...

	}

	return r;
}

[*4]のvcpu_enter_guestがコア部分の処理です。

(KVM: arch/x86/kvm/x86.c)

static int vcpu_enter_guest(struct kvm_vcpu *vcpu)
{
	int r;
	bool req_int_win =
		dm_request_for_irq_injection(vcpu) &&
		kvm_cpu_accept_dm_intr(vcpu);

	bool req_immediate_exit = false;

	if (vcpu->requests) { [*5]
		if (kvm_check_request(KVM_REQ_MMU_RELOAD, vcpu))
			kvm_mmu_unload(vcpu);
		...
	}
	...

	kvm_x86_ops->run(vcpu); [*6]

	...

	/* Interrupt is enabled by handle_external_intr() */
	kvm_x86_ops->handle_external_intr(vcpu);
	...
	r = kvm_x86_ops->handle_exit(vcpu);
	return r;

}

[*5]ではvcpuに届いた各リクエストを処理します。リクエストとはVMEnter前にするべき処理をvcpuに依頼する機構で、有名な例だとkvm-clockが時計の更新をVMEnter前に行う際このリクエストを使用します。
[*6]のrunはarch/x86/kvm/vmx.c内でvmx_vcpu_runに設定されています。

(KVM: arch/x86/kvm/vmx.c)

static void __noclone vmx_vcpu_run(struct kvm_vcpu *vcpu)
{
	struct vcpu_vmx *vmx = to_vmx(vcpu);
	unsigned long debugctlmsr, cr4;
	...
	vmx->__launched = vmx->loaded_vmcs->launched;
	asm(
		/* Store host registers */
		"push %%" _ASM_DX "; push %%" _ASM_BP ";" [*7]
		"push %%" _ASM_CX " \n\t" /* placeholder for guest rcx */
		"push %%" _ASM_CX " \n\t"
		"cmp %%" _ASM_SP ", %c[host_rsp](%0) \n\t"
		"je 1f \n\t"
		"mov %%" _ASM_SP ", %c[host_rsp](%0) \n\t"
		__ex(ASM_VMX_VMWRITE_RSP_RDX) "\n\t"
		"1: \n\t"
		/* Reload cr2 if changed */
		"mov %c[cr2](%0), %%" _ASM_AX " \n\t"
		"mov %%cr2, %%" _ASM_DX " \n\t"
		"cmp %%" _ASM_AX ", %%" _ASM_DX " \n\t"
		"je 2f \n\t"
		"mov %%" _ASM_AX", %%cr2 \n\t"
		"2: \n\t"
		/* Check if vmlaunch of vmresume is needed */
		"cmpl $0, %c[launched](%0) \n\t" [*8]
		/* Load guest registers.  Don't clobber flags. */
		"mov %c[rax](%0), %%" _ASM_AX " \n\t" [*11]
		"mov %c[rbx](%0), %%" _ASM_BX " \n\t"
		"mov %c[rdx](%0), %%" _ASM_DX " \n\t"
		"mov %c[rsi](%0), %%" _ASM_SI " \n\t"
		"mov %c[rdi](%0), %%" _ASM_DI " \n\t"
		"mov %c[rbp](%0), %%" _ASM_BP " \n\t"
		...
		"mov %c[rcx](%0), %%" _ASM_CX " \n\t" /* kills %0 (ecx) */

		/* Enter guest mode */
		"jne 1f \n\t"
		__ex(ASM_VMX_VMLAUNCH) "\n\t" [*9]
		"jmp 2f \n\t"
		"1: " __ex(ASM_VMX_VMRESUME) "\n\t" [*10]
		"2: "
		/* Save guest registers, load host registers, keep flags */
		"mov %0, %c[wordsize](%%" _ASM_SP ") \n\t" [*12]
		"pop %0 \n\t"
		"mov %%" _ASM_AX ", %c[rax](%0) \n\t"
		"mov %%" _ASM_BX ", %c[rbx](%0) \n\t"
		__ASM_SIZE(pop) " %c[rcx](%0) \n\t"
		"mov %%" _ASM_DX ", %c[rdx](%0) \n\t"
		"mov %%" _ASM_SI ", %c[rsi](%0) \n\t"
		"mov %%" _ASM_DI ", %c[rdi](%0) \n\t"
		"mov %%" _ASM_BP ", %c[rbp](%0) \n\t"
		...
		"mov %%cr2, %%" _ASM_AX "   \n\t"
		"mov %%" _ASM_AX ", %c[cr2](%0) \n\t"

		"pop  %%" _ASM_BP "; pop  %%" _ASM_DX " \n\t"
		"setbe %c[fail](%0) \n\t"
		".pushsection .rodata \n\t"
		".global vmx_return \n\t"
		"vmx_return: " _ASM_PTR " 2b \n\t"
		".popsection"
		...
	      );
	vmx->exit_reason = vmcs_read32(VM_EXIT_REASON); [*13]
	...
}

[*7]でホストレジスタのうちVT-xの退避対象になっていないレジスタをスタック上に退避しています。
次に[*8]ですでに一度VMEnterしたかどうか確認し、初めてであれば[*9]でVMLAUNCH命令を、二度目以降なら[*10]でVMRESUME命令を実行しています。[*11]でゲストのレジスタをvcpu.arch.regsからロードした後、処理をゲストへ移します。
[*12]ではVMExit後、ゲストのレジスタをvcpu.arch.regsに退避しホストのレジスタを復帰しています。
[*13]ではVMCSからVM_EXIT_REASONを読み出します。これによりVM_EXIT要因に合わせたエミュレートを行います。

では続いて仮想I/O処理を見ていきます。
[*14],[*15]のkvm_handle_io,address_space_rwが、I/O処理が理由でVMExitした際の処理になります。

3. 仮想I/O
KVMにおける仮想IOはqemu-kvmに全て任せています。そのため処理は非常に簡単です。

kvm_handle_ioは以下のようになっています。

(QEMU: kvm-all.c)

static void kvm_handle_io(uint16_t port, MemTxAttrs attrs, void *data, int direction,
                          int size, uint32_t count)
{
    int i;
    uint8_t *ptr = data;

    for (i = 0; i < count; i++) {
        address_space_rw(&address_space_io, port, attrs,
                         ptr, size,
                         direction == KVM_EXIT_IO_OUT); [*1]
        ptr += size;
    }
}

[*1]でaddress_space_rwを呼び出しています。これはqemuのaddress_space_ioというMemoryRegionを使用したIO処理です。(QEMU internals参照)
またのKVM_EXIT_MMIOの処理でもaddress_space_memoryをMemoryRegionとしたaddress_space_rwが呼ばれておりqemu側に丸投げしています。
このように仮想IO処理はqemu-kvmに移譲されています。

4. 仮想IRQ(APIC)
KVMは高速化のため、一部のハードウェアをqemu-kvmではなく独自にエミュレートしています。
具体的にはPIC,PIT,(I/O|Local)APICです。これらはqemu-kvm起動時に-no-kvm-irqchip, -no-kvm-pitなどのオプションをつける事でqemuにエミュレートを任せることができますが、せっかくなのでKVM独自のエミュレーションの実装を見て行きましょう。

まずはAPICから見ていきます。
1章の[*25]を見てください。machine_kernel_irqchip_allowedはkvmのIRQチップエミュレーションを利用する場合trueが返り、その後kvm_irqchip_createにてIRQチップの初期化を行っています。

(QEMU: kvm-all.c)

static void kvm_irqchip_create(MachineState *machine, KVMState *s)
{
    int ret;

    if (kvm_check_extension(s, KVM_CAP_IRQCHIP)) {
        ;
    }
    ...
    /* First probe and see if there's a arch-specific hook to create the
     * in-kernel irqchip for us */
    ret = kvm_arch_irqchip_create(s);
    if (ret == 0) {
        ret = kvm_vm_ioctl(s, KVM_CREATE_IRQCHIP); [*1]
    }
    ...
    kvm_kernel_irqchip = true;
    ...
    kvm_init_irq_routing(s); [*]
}

[*1]でKVMに対しKVM_CREATE_IRQCHIPを発行しています。これでKVM側のIRQチップが初期化されます。

(KVM: arch/x86/kvm/x86.c)

long kvm_arch_vm_ioctl(struct file *filp,
		       unsigned int ioctl, unsigned long arg)
{
	struct kvm *kvm = filp->private_data;
	void __user *argp = (void __user *)arg;
	int r = -ENOTTY;
	switch (ioctl) {
	...
	case KVM_CREATE_IRQCHIP: { [*2]
		struct kvm_pic *vpic;
		...
		if (vpic) {
			r = kvm_ioapic_init(kvm); [*3]
			...
		}
		...
		r = kvm_setup_default_irq_routing(kvm); [*11]
		...
	}
	...
    }
    ...
}

[*2]がKVM_CREATE_IRQCHIPを受け取った際の処理です。まず[*3]のkvm_ioapic_initでioapicを仮想デバイスとして初期化しています。

(KVM: arch/x86/kvm/ioapic.c)

static const struct kvm_io_device_ops ioapic_mmio_ops = {
	.read     = ioapic_mmio_read,
	.write    = ioapic_mmio_write,
};

int kvm_ioapic_init(struct kvm *kvm)
{
	struct kvm_ioapic *ioapic;
	int ret;

	ioapic = kzalloc(sizeof(struct kvm_ioapic), GFP_KERNEL);
	..
	kvm_ioapic_reset(ioapic); [*4]
	kvm_iodevice_init(&ioapic->dev, &ioapic_mmio_ops); [*5]
	...
	kvm_vcpu_request_scan_ioapic(kvm); [*10]
	return ret;
}

[*4]のkvm_ioapic_resetでioapicを初期化し、[*5]でioapic->dev->opsで表されるデバイスの操作メソッドをioapic_mmio_opsに設定しています。

(KVM: virt/kvm/kvm_main.c)

/* Caller must hold slots_lock. */
int kvm_io_bus_register_dev(struct kvm *kvm, enum kvm_bus bus_idx, gpa_t addr,
			    int len, struct kvm_io_device *dev)
{
	struct kvm_io_bus *new_bus, *bus;

	bus = kvm->buses[bus_idx]; [*6]
	...
	new_bus = kmalloc(sizeof(*bus) + ((bus->dev_count + 1) *
			  sizeof(struct kvm_io_range)), GFP_KERNEL);
			  
	memcpy(new_bus, bus, sizeof(*bus) + (bus->dev_count *
	       sizeof(struct kvm_io_range))); [*7]
	kvm_io_bus_insert_dev(new_bus, dev, addr, len); [*8]
	...

	return 0;
}

[*6]で指定されたバスに[*7]で新たに確保したkvm_io_busをコピーしています。また[*8]のkvm_io_bus_insert_devでは新たに作成したkvm_io_busにデバイスをつないでいます。

(KVM: virt/kvm/kvm_main.c)

static int kvm_io_bus_insert_dev(struct kvm_io_bus *bus, struct kvm_io_device *dev,
			  gpa_t addr, int len)
{
	bus->range[bus->dev_count++] = (struct kvm_io_range) {
		.addr = addr,
		.len = len,
		.dev = dev,
	}; [*9]

	sort(bus->range, bus->dev_count, sizeof(struct kvm_io_range),
		kvm_io_bus_sort_cmp, NULL);

	return 0;
}

[*9]でkvm_io_rengaeを新たに追加している事が分かります。
さてこれでAPICデバイスの登録は完了しました。最後に[*10]のkvm_vcpu_request_scan_ioapicで全てのvCPUに対してKVM_REQ_SCAN_IOAPICリクエストを送信しています。(これらリクエストの処理は後ほど説明します)

では戻って次に[*11]のkvm_setup_default_irq_routingを見てみましょう。

(KVM: arch/x86/kvm/irq_comm.c)

int kvm_setup_default_irq_routing(struct kvm *kvm)
{
	return kvm_set_irq_routing(kvm, default_routing,
				   ARRAY_SIZE(default_routing), 0);
}

(KVM: virt/kvm/irqchip.c)

int kvm_set_irq_routing(struct kvm *kvm,
			const struct kvm_irq_routing_entry *ue,
			unsigned nr,
			unsigned flags)
{
	struct kvm_irq_routing_table *new, *old;
	u32 i, j, nr_rt_entries = 0;
	int r;

	...

	new = kzalloc(sizeof(*new) + (nr_rt_entries * sizeof(struct hlist_head)),
		      GFP_KERNEL); [*12]


	new->nr_rt_entries = nr_rt_entries;
	for (i = 0; i < KVM_NR_IRQCHIPS; i++)
		for (j = 0; j < KVM_IRQCHIP_NUM_PINS; j++)
			new->chip[i][j] = -1;

	for (i = 0; i < nr; ++i) {
		struct kvm_kernel_irq_routing_entry *e;

		e = kzalloc(sizeof(*e), GFP_KERNEL); [*13]
		...
		r = setup_routing_entry(new, e, ue); [*14]
		...
		++ue;
	}

	...
	kvm_arch_irq_routing_update(kvm);[*15]
	...
}

[*12]でkvm_irq_routing_entryのリストであるkvm_irq_routing_tableを作成しています。kvm_irq_routing_entryはGSIからIRQへの対応(ルーティング)を表しており、[*13],[*14]で引数として渡されたkvm_irq_routing_entryのリストをnewに設定していきます。
これでIRQルーティングの登録は完了です。最後に[*15]で全てのvCPUにKVM_REQ_SCAN_IOAPICリクエストを送信しています。

さてこれで仮想APICの初期化は完了しました。

5. 仮想メモリ(EPT)
では次にアドレス空間の仮想化機構であるEPTがKVMでどのように扱われているか見ていきます。EPTはゲスト物理アドレス(GPA)からホスト物理アドレス(HPA)への変換を行う4段ページテーブルです。(以下これをshadowページテーブルと呼びます)
通常のページテーブル機構と同じように、まだテーブルにマッピングされていないアドレスへアクセスが発生した場合EPT Violationが発生しVMExitする仕組みです。

http://ytliu.info/blog/2014/11/24/shi-shang-zui-xiang-xi-de-kvm-mmu-pagejie-gou-he-yong-fa-jie-xi/より
EPT Violation発生時はhandle_ept_violation関数が実行されます。

(KVM: arch/x86/kvm/vmx.c)

static int handle_ept_violation(struct kvm_vcpu *vcpu)
{
	unsigned long exit_qualification;
	gpa_t gpa;
	...

	gpa = vmcs_read64(GUEST_PHYSICAL_ADDRESS); [*1]
	...
	return kvm_mmu_page_fault(vcpu, gpa, error_code, NULL, 0); [*2]
}

[*1]でVMCSからGPAを取得した後[*2]でページフォルトを処理します。

(KVM: arch/x86/kvm/mmu.c)

int kvm_mmu_page_fault(struct kvm_vcpu *vcpu, gva_t cr2, u32 error_code,
		       void *insn, int insn_len)
{
	int r, emulation_type = EMULTYPE_RETRY;
	enum emulation_result er;

	r = vcpu->arch.mmu.page_fault(vcpu, cr2, error_code, false); [*3]
	...
out:
	return r;
}

[*3]のarch.mmu.page_faultにはtdp_page_faultが設定されています。

(KVM: arch/x86/kvm/mmu.c)

static int tdp_page_fault(struct kvm_vcpu *vcpu, gva_t gpa, u32 error_code,
			  bool prefault)
{
	pfn_t pfn;
	int r;
	int level;
	bool force_pt_level;
	gfn_t gfn = gpa >> PAGE_SHIFT; [*4]
	...
	if (try_async_pf(vcpu, prefault, gfn, gpa, &pfn, write, &map_writable)) [*5]
		return 0;

	...
	r = __direct_map(vcpu, gpa, write, map_writable,
			 level, gfn, pfn, prefault); [*6]

	return r;

}

EPTの処理は単純で[*4]でまずGPAをゲストページフレーム(GFN)に変換した後、[*5]のtry_async_pfでGFNをホストページフレーム(PFN)に変換します。最後に[*6]でEPT table entryを新たに作成してページフォルト処理は終了です。
これらの処理を詳細に説明しても良いのですが、実は既に日本語記事で非常に詳しい説明記事( http://d.hatena.ne.jp/kvm/20110702/1309604602 )があるため、ここでは処理概要だけ述べます。

(適時、こちらのページと照らし合わせながら読んで頂ければと思います。決してサボったわけでは(ry )

処理概要:
try_async_pfはAsynchronous page fault(以下APF)を実行します。そもそもAPFとはゲストOSが""ホストOSによって""スワップアウトされた空間にアクセスした際、これはゲストOSにとって透過的なためゲスト内でスワップインの間のI/O待ち時間を、別のプロセスに割り当てられないという不平等な状態を解消するための機構です。

このような状態を解消するためにAPFではAPF要因という変数をホスト-ゲスト間の共有メモリに置いてスワップアウトされている事をゲストに通知し、スワップインI/O処理はworkqueueにまかせて再びVMEnterします。ちなみにこのメモリ空間の通知にはMSRを使用します。
ゲスト側(Linuxカーネルの場合ですが)はAPF用のページフォルトハンドラdo_async_page_faultを使いAPF要因を読んだ後、適時他プロセスにCPUリソースを明け渡します。

つまりゲストのLinuxカーネルに準仮想化的なアプローチを施し、ハイパーバイザと協調する事で、このようなプロセスディスパッチを行っているわけですね。

スワップインの処理はこれで良いとして、では実際にどのようなホスト物理アドレス(HPA)に変換してページを割り当てるのか見て行きましょう。

(KVM: virt/kvm/kvm_main.c)

static bool try_async_pf(struct kvm_vcpu *vcpu, bool prefault, gfn_t gfn,
			 gva_t gva, pfn_t *pfn, bool write, bool *writable)
{
	struct kvm_memory_slot *slot;
	bool async;

	slot = kvm_vcpu_gfn_to_memslot(vcpu, gfn); [*7]
	...
	*pfn = __gfn_to_pfn_memslot(slot, gfn, false, NULL, write, writable); [*9]
	return false;
}

(KVM: virt/kvm/kvm_main.c)

struct kvm_memory_slot *kvm_vcpu_gfn_to_memslot(struct kvm_vcpu *vcpu, gfn_t gfn)
{
	return __gfn_to_memslot(kvm_vcpu_memslots(vcpu), gfn);
}

(KVM: include/linux/kvm_host.h)

__gfn_to_memslot(struct kvm_memslots *slots, gfn_t gfn)
{
         return search_memslots(slots, gfn); [*8]
}

アドレス変換は先ほどのtry_async_pf内で行われています。
まず[*7]でGFNをmemslotに変換します。中身は[*8]のsearch_memslotsです。

search_memslotsによりGFNに該当するmemslotsを検索します。kvm_memslotsはアドレス変換のデータ構造で、kvm_memslots->base_gfnからkvm_memslots->base_gfn + kvm_memslots->npagesが変換対象のGFNです。これらの範囲をkvm_memslots->userspace_addrを開始アドレスとする範囲に写像する事でGFNをHVAに変換します。(qemuのsoftmmuと同じですね)

[*9]のkvm_memslotsを使った実際の変換処理を見てみましょう。

(KVM: virt/kvm/kvm_main.c)

static unsigned long __gfn_to_hva_many(struct kvm_memory_slot *slot, gfn_t gfn,
				       gfn_t *nr_pages, bool write)
{
	...
	return __gfn_to_hva_memslot(slot, gfn); [*11]
}
pfn_t __gfn_to_pfn_memslot(struct kvm_memory_slot *slot, gfn_t gfn, bool atomic,
			   bool *async, bool write_fault, bool *writable)
{
	unsigned long addr = __gfn_to_hva_many(slot, gfn, NULL, write_fault); [*10]

	return hva_to_pfn(addr, atomic, async, write_fault, 
			  writable); [*12]
}

まずは[*10]でGFNをHVAに変換しています。実際の処理は[*11]の__gfn_to_hva_memslotです。

static inline unsigned long
__gfn_to_hva_memslot(struct kvm_memory_slot *slot, gfn_t gfn)
{
	return slot->userspace_addr + (gfn - slot->base_gfn) * PAGE_SIZE;
}

見たままですが、上で述べた写像を行っていますね。

さて、HVAが出せたので次は[*12]のhva_to_pfnでPFNに変換して完了です。

(KVM: virt/kvm/kvm_main.c)

static pfn_t hva_to_pfn(unsigned long addr, bool atomic, bool *async,
			bool write_fault, bool *writable)
{
	struct vm_area_struct *vma;
	pfn_t pfn = 0;
	int npages;

	if (hva_to_pfn_fast(addr, atomic, async, write_fault, writable, &pfn)) [*13]
		return pfn;

	npages = hva_to_pfn_slow(addr, async, write_fault, writable, &pfn); [*14]

	vma = find_vma_intersection(current->mm, addr, addr + 1); [*15]
	...
	return pfn;
}

Linuxカーネルハッカーな方にはお馴染みの関数がありますね。このPFNへの変換はホストOSの処理を殆ど流用しているだけなためLinuxカーネル内APIがいろいろ使われています。
[*13]のfast処理は内部で__get_user_pages_fastを呼び出しているだけです。[*14]のslowも似たような物で、[*15]もaddrから赤黒木を辿ってVMAを取得するだけです。あくまでKVMの解説に専念するためこの辺りのカーネル内APIは既知とします。

さてこれでPFNへの変換が完了しました。

では実際にこのPFNをEPTテーブルにマップする[*6]の__direct_mapの処理を見て行きましょう。

(KVM: arch/x86/kvm/mmu.c)

static int __direct_map(struct kvm_vcpu *vcpu, gpa_t v, int write,
			int map_writable, int level, gfn_t gfn, pfn_t pfn,
			bool prefault)
{
	struct kvm_shadow_walk_iterator iterator;
	struct kvm_mmu_page *sp;
	int emulate = 0;
	gfn_t pseudo_gfn;

	if (!VALID_PAGE(vcpu->arch.mmu.root_hpa))
		return 0;

	for_each_shadow_entry(vcpu, (u64)gfn << PAGE_SHIFT, iterator) { [*16]
		if (iterator.level == level) { [*17]
			mmu_set_spte(vcpu, iterator.sptep, ACC_ALL,
				     write, &emulate, level, gfn, pfn,
				     prefault, map_writable); [*18]
			direct_pte_prefetch(vcpu, iterator.sptep);
			++vcpu->stat.pf_fixed;
			break;
		}

		if (!is_shadow_present_pte(*iterator.sptep)) { [*19]
			u64 base_addr = iterator.addr;

			base_addr &= PT64_LVL_ADDR_MASK(iterator.level);
			pseudo_gfn = base_addr >> PAGE_SHIFT;
			sp = kvm_mmu_get_page(vcpu, pseudo_gfn, iterator.addr,
					      iterator.level - 1,
					      1, ACC_ALL, iterator.sptep); [*20]

			link_shadow_page(iterator.sptep, sp, true); [*21]
		}
	}
	return emulate;
}

[*16]のfor_each_shadow_entryマクロを使い、shadowページテーブルの各レベルを走査していきます。[*17]で現在見ているレベルがマッピングを指定されたレベルの場合、[*18]のmmu_set_spte->set_pteでpfnをエントリーに設定します。
[*19]ではマッピングを指定されていないレベル、つまりミドルテーブル(level4~2)がまだエントリー上にない場合[*20]で新たにエントリーを作成し[*21]でつないでいます。

6. おわりに
vCPUに始まりKVMの基本的な構造を見てきました。本記事で説明した部分以外でも例えばkvm-clockなどの準仮想化クロックやVFIOなどまだまだKVMには様々な機構が備わっています。
これらについてもいつか書けたら良いなーと思いつつとりあえず今回はここまでにしておきます。

さいごに、実はこの記事はLinux Advent Calendar 2015 - Qiita17日目の記事です....
大遅刻していまい申し訳ありませんでした....

Reference

• 濃いバナ KVMの仕組み

http://pantora.net/datapool/osc2007-spring/v-tomo_koibana2_kvm.pdf

• Architecture of the Kernel-based Virtual Machine (KVM)

http://www.linux-kongress.org/2010/slides/KVM-Architecture-LK2010.pdf

• A small look inside

http://www.linux-kvm.org/page/Small_look_inside

• ハイパーバイザの作り方

http://syuu1228.github.io/howto_implement_hypervisor/

• Gerald J. Popek, Robert P. Goldberg

Formal Requirements for Virtualizable Third Generation Architectures
http://www.dc.uba.ar/materias/so/2010/verano/descargas/articulos/VM-requirements.pdf

• Sheng Yang(KVM Forum 2008)

Extending KVM with new Intel Virtualization technology
http://www.linux-kvm.org/images/c/c7/KvmForum2008$kdf2008_11.pdf

• Virtualization Architecture & KVM

http://surriel.com/system/files/KVM-Architecture-Chile-2012.pdf

• Linux KVM のコードを追いかけてみよう

http://www.slideshare.net/ozax86/linux-kvm

• Linuxメモリ管理の最先端を探る @IT

http://www.atmarkit.co.jp/flinux/rensai/watch2008/watchmema.html

• Xiao Guangrong LinuxCon'11

KVM MMU Virtualization
https://events.linuxfoundation.org/slides/2011/linuxcon-japan/lcj2011_guangrong.pdf

• 史上最详细的kvm_mmu_page结构和用法解析

http://ytliu.info/blog/2014/11/24/shi-shang-zui-xiang-xi-de-kvm-mmu-pagejie-gou-he-yong-fa-jie-xi/

• KVM地址翻译流程及EPT页表的建立过程

http://blog.csdn.net/lux_veritas/article/details/9284635

• Jun Nakajima(KVM Forum2012)

Enabling Optimized Interrupt/APIC Virtualization in KVM
http://www.linux-kvm.org/images/7/70/2012-forum-nakajima_apicv.pdf

• KVM日記 Asynchronous page fault解析

http://d.hatena.ne.jp/kvm/20110702/1309604602

• NARKIVE(MALINGLIST ARCHIVE) EPT page fault procedure

http://kvm.vger.kernel.narkive.com/8CNlP9QP/ept-page-fault-procedure