mmu.c 40.3 KB
Newer Older
A
Avi Kivity 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * Kernel-based Virtual Machine driver for Linux
 *
 * This module enables machines with Intel VT-x extensions to run virtual
 * machines without emulation or binary translation.
 *
 * MMU support
 *
 * Copyright (C) 2006 Qumranet, Inc.
 *
 * Authors:
 *   Yaniv Kamay  <yaniv@qumranet.com>
 *   Avi Kivity   <avi@qumranet.com>
 *
 * This work is licensed under the terms of the GNU GPL, version 2.  See
 * the COPYING file in the top-level directory.
 *
 */
A
Avi Kivity 已提交
19 20 21

#include "vmx.h"
#include "kvm.h"
22
#include "x86.h"
A
Avi Kivity 已提交
23

A
Avi Kivity 已提交
24 25 26 27 28
#include <linux/types.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/highmem.h>
#include <linux/module.h>
29
#include <linux/swap.h>
A
Avi Kivity 已提交
30

A
Avi Kivity 已提交
31 32
#include <asm/page.h>
#include <asm/cmpxchg.h>
33
#include <asm/io.h>
A
Avi Kivity 已提交
34

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
#undef MMU_DEBUG

#undef AUDIT

#ifdef AUDIT
static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg);
#else
static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg) {}
#endif

#ifdef MMU_DEBUG

#define pgprintk(x...) do { if (dbg) printk(x); } while (0)
#define rmap_printk(x...) do { if (dbg) printk(x); } while (0)

#else

#define pgprintk(x...) do { } while (0)
#define rmap_printk(x...) do { } while (0)

#endif

#if defined(MMU_DEBUG) || defined(AUDIT)
static int dbg = 1;
#endif
A
Avi Kivity 已提交
60

61 62 63
#ifndef MMU_DEBUG
#define ASSERT(x) do { } while (0)
#else
A
Avi Kivity 已提交
64 65 66 67 68
#define ASSERT(x)							\
	if (!(x)) {							\
		printk(KERN_WARNING "assertion failed %s:%d: %s\n",	\
		       __FILE__, __LINE__, #x);				\
	}
69
#endif
A
Avi Kivity 已提交
70

71 72 73 74
#define PT64_PT_BITS 9
#define PT64_ENT_PER_PAGE (1 << PT64_PT_BITS)
#define PT32_PT_BITS 10
#define PT32_ENT_PER_PAGE (1 << PT32_PT_BITS)
A
Avi Kivity 已提交
75 76 77 78 79 80 81 82 83 84 85 86 87

#define PT_WRITABLE_SHIFT 1

#define PT_PRESENT_MASK (1ULL << 0)
#define PT_WRITABLE_MASK (1ULL << PT_WRITABLE_SHIFT)
#define PT_USER_MASK (1ULL << 2)
#define PT_PWT_MASK (1ULL << 3)
#define PT_PCD_MASK (1ULL << 4)
#define PT_ACCESSED_MASK (1ULL << 5)
#define PT_DIRTY_MASK (1ULL << 6)
#define PT_PAGE_SIZE_MASK (1ULL << 7)
#define PT_PAT_MASK (1ULL << 7)
#define PT_GLOBAL_MASK (1ULL << 8)
88 89
#define PT64_NX_SHIFT 63
#define PT64_NX_MASK (1ULL << PT64_NX_SHIFT)
A
Avi Kivity 已提交
90 91 92 93 94 95 96

#define PT_PAT_SHIFT 7
#define PT_DIR_PAT_SHIFT 12
#define PT_DIR_PAT_MASK (1ULL << PT_DIR_PAT_SHIFT)

#define PT32_DIR_PSE36_SIZE 4
#define PT32_DIR_PSE36_SHIFT 13
M
Mike Day 已提交
97 98
#define PT32_DIR_PSE36_MASK \
	(((1ULL << PT32_DIR_PSE36_SIZE) - 1) << PT32_DIR_PSE36_SHIFT)
A
Avi Kivity 已提交
99 100 101 102 103 104 105 106 107 108 109 110


#define PT_FIRST_AVAIL_BITS_SHIFT 9
#define PT64_SECOND_AVAIL_BITS_SHIFT 52

#define PT_SHADOW_IO_MARK (1ULL << PT_FIRST_AVAIL_BITS_SHIFT)

#define VALID_PAGE(x) ((x) != INVALID_PAGE)

#define PT64_LEVEL_BITS 9

#define PT64_LEVEL_SHIFT(level) \
M
Mike Day 已提交
111
		(PAGE_SHIFT + (level - 1) * PT64_LEVEL_BITS)
A
Avi Kivity 已提交
112 113 114 115 116 117 118 119 120 121 122

#define PT64_LEVEL_MASK(level) \
		(((1ULL << PT64_LEVEL_BITS) - 1) << PT64_LEVEL_SHIFT(level))

#define PT64_INDEX(address, level)\
	(((address) >> PT64_LEVEL_SHIFT(level)) & ((1 << PT64_LEVEL_BITS) - 1))


#define PT32_LEVEL_BITS 10

#define PT32_LEVEL_SHIFT(level) \
M
Mike Day 已提交
123
		(PAGE_SHIFT + (level - 1) * PT32_LEVEL_BITS)
A
Avi Kivity 已提交
124 125 126 127 128 129 130 131

#define PT32_LEVEL_MASK(level) \
		(((1ULL << PT32_LEVEL_BITS) - 1) << PT32_LEVEL_SHIFT(level))

#define PT32_INDEX(address, level)\
	(((address) >> PT32_LEVEL_SHIFT(level)) & ((1 << PT32_LEVEL_BITS) - 1))


132
#define PT64_BASE_ADDR_MASK (((1ULL << 52) - 1) & ~(u64)(PAGE_SIZE-1))
A
Avi Kivity 已提交
133 134 135 136 137 138 139
#define PT64_DIR_BASE_ADDR_MASK \
	(PT64_BASE_ADDR_MASK & ~((1ULL << (PAGE_SHIFT + PT64_LEVEL_BITS)) - 1))

#define PT32_BASE_ADDR_MASK PAGE_MASK
#define PT32_DIR_BASE_ADDR_MASK \
	(PAGE_MASK & ~((1ULL << (PAGE_SHIFT + PT32_LEVEL_BITS)) - 1))

140 141
#define PT64_PERM_MASK (PT_PRESENT_MASK | PT_WRITABLE_MASK | PT_USER_MASK \
			| PT64_NX_MASK)
A
Avi Kivity 已提交
142 143 144 145

#define PFERR_PRESENT_MASK (1U << 0)
#define PFERR_WRITE_MASK (1U << 1)
#define PFERR_USER_MASK (1U << 2)
146
#define PFERR_FETCH_MASK (1U << 4)
A
Avi Kivity 已提交
147 148 149 150 151 152 153 154

#define PT64_ROOT_LEVEL 4
#define PT32_ROOT_LEVEL 2
#define PT32E_ROOT_LEVEL 3

#define PT_DIRECTORY_LEVEL 2
#define PT_PAGE_TABLE_LEVEL 1

155 156
#define RMAP_EXT 4

157 158 159 160 161
#define ACC_EXEC_MASK    1
#define ACC_WRITE_MASK   PT_WRITABLE_MASK
#define ACC_USER_MASK    PT_USER_MASK
#define ACC_ALL          (ACC_EXEC_MASK | ACC_WRITE_MASK | ACC_USER_MASK)

162 163 164 165 166
struct kvm_rmap_desc {
	u64 *shadow_ptes[RMAP_EXT];
	struct kvm_rmap_desc *more;
};

167 168
static struct kmem_cache *pte_chain_cache;
static struct kmem_cache *rmap_desc_cache;
169
static struct kmem_cache *mmu_page_header_cache;
170

171 172 173 174 175 176 177 178 179 180
static u64 __read_mostly shadow_trap_nonpresent_pte;
static u64 __read_mostly shadow_notrap_nonpresent_pte;

void kvm_mmu_set_nonpresent_ptes(u64 trap_pte, u64 notrap_pte)
{
	shadow_trap_nonpresent_pte = trap_pte;
	shadow_notrap_nonpresent_pte = notrap_pte;
}
EXPORT_SYMBOL_GPL(kvm_mmu_set_nonpresent_ptes);

A
Avi Kivity 已提交
181 182
static int is_write_protection(struct kvm_vcpu *vcpu)
{
183
	return vcpu->cr0 & X86_CR0_WP;
A
Avi Kivity 已提交
184 185 186 187 188 189 190
}

static int is_cpuid_PSE36(void)
{
	return 1;
}

191 192 193 194 195
static int is_nx(struct kvm_vcpu *vcpu)
{
	return vcpu->shadow_efer & EFER_NX;
}

A
Avi Kivity 已提交
196 197 198 199 200
static int is_present_pte(unsigned long pte)
{
	return pte & PT_PRESENT_MASK;
}

201 202 203 204 205 206 207
static int is_shadow_present_pte(u64 pte)
{
	pte &= ~PT_SHADOW_IO_MARK;
	return pte != shadow_trap_nonpresent_pte
		&& pte != shadow_notrap_nonpresent_pte;
}

A
Avi Kivity 已提交
208 209 210 211 212
static int is_writeble_pte(unsigned long pte)
{
	return pte & PT_WRITABLE_MASK;
}

213 214 215 216 217
static int is_dirty_pte(unsigned long pte)
{
	return pte & PT_DIRTY_MASK;
}

A
Avi Kivity 已提交
218 219 220 221 222
static int is_io_pte(unsigned long pte)
{
	return pte & PT_SHADOW_IO_MARK;
}

223 224
static int is_rmap_pte(u64 pte)
{
225 226
	return pte != shadow_trap_nonpresent_pte
		&& pte != shadow_notrap_nonpresent_pte;
227 228
}

229 230 231 232 233 234 235
static gfn_t pse36_gfn_delta(u32 gpte)
{
	int shift = 32 - PT32_DIR_PSE36_SHIFT - PAGE_SHIFT;

	return (gpte & PT32_DIR_PSE36_MASK) << shift;
}

236 237 238 239 240 241 242 243 244
static void set_shadow_pte(u64 *sptep, u64 spte)
{
#ifdef CONFIG_X86_64
	set_64bit((unsigned long *)sptep, spte);
#else
	set_64bit((unsigned long long *)sptep, spte);
#endif
}

245
static int mmu_topup_memory_cache(struct kvm_mmu_memory_cache *cache,
246
				  struct kmem_cache *base_cache, int min)
247 248 249 250
{
	void *obj;

	if (cache->nobjs >= min)
251
		return 0;
252
	while (cache->nobjs < ARRAY_SIZE(cache->objects)) {
253
		obj = kmem_cache_zalloc(base_cache, GFP_KERNEL);
254
		if (!obj)
255
			return -ENOMEM;
256 257
		cache->objects[cache->nobjs++] = obj;
	}
258
	return 0;
259 260 261 262 263 264 265 266
}

static void mmu_free_memory_cache(struct kvm_mmu_memory_cache *mc)
{
	while (mc->nobjs)
		kfree(mc->objects[--mc->nobjs]);
}

A
Avi Kivity 已提交
267
static int mmu_topup_memory_cache_page(struct kvm_mmu_memory_cache *cache,
268
				       int min)
A
Avi Kivity 已提交
269 270 271 272 273 274
{
	struct page *page;

	if (cache->nobjs >= min)
		return 0;
	while (cache->nobjs < ARRAY_SIZE(cache->objects)) {
275
		page = alloc_page(GFP_KERNEL);
A
Avi Kivity 已提交
276 277 278 279 280 281 282 283 284 285 286
		if (!page)
			return -ENOMEM;
		set_page_private(page, 0);
		cache->objects[cache->nobjs++] = page_address(page);
	}
	return 0;
}

static void mmu_free_memory_cache_page(struct kvm_mmu_memory_cache *mc)
{
	while (mc->nobjs)
287
		free_page((unsigned long)mc->objects[--mc->nobjs]);
A
Avi Kivity 已提交
288 289
}

290
static int mmu_topup_memory_caches(struct kvm_vcpu *vcpu)
291
{
292 293
	int r;

294
	kvm_mmu_free_some_pages(vcpu);
295
	r = mmu_topup_memory_cache(&vcpu->mmu_pte_chain_cache,
296
				   pte_chain_cache, 4);
297 298 299
	if (r)
		goto out;
	r = mmu_topup_memory_cache(&vcpu->mmu_rmap_desc_cache,
300
				   rmap_desc_cache, 1);
301 302
	if (r)
		goto out;
303
	r = mmu_topup_memory_cache_page(&vcpu->mmu_page_cache, 8);
304 305 306
	if (r)
		goto out;
	r = mmu_topup_memory_cache(&vcpu->mmu_page_header_cache,
307
				   mmu_page_header_cache, 4);
308 309
out:
	return r;
310 311 312 313 314 315
}

static void mmu_free_memory_caches(struct kvm_vcpu *vcpu)
{
	mmu_free_memory_cache(&vcpu->mmu_pte_chain_cache);
	mmu_free_memory_cache(&vcpu->mmu_rmap_desc_cache);
A
Avi Kivity 已提交
316
	mmu_free_memory_cache_page(&vcpu->mmu_page_cache);
317
	mmu_free_memory_cache(&vcpu->mmu_page_header_cache);
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336
}

static void *mmu_memory_cache_alloc(struct kvm_mmu_memory_cache *mc,
				    size_t size)
{
	void *p;

	BUG_ON(!mc->nobjs);
	p = mc->objects[--mc->nobjs];
	memset(p, 0, size);
	return p;
}

static struct kvm_pte_chain *mmu_alloc_pte_chain(struct kvm_vcpu *vcpu)
{
	return mmu_memory_cache_alloc(&vcpu->mmu_pte_chain_cache,
				      sizeof(struct kvm_pte_chain));
}

337
static void mmu_free_pte_chain(struct kvm_pte_chain *pc)
338
{
339
	kfree(pc);
340 341 342 343 344 345 346 347
}

static struct kvm_rmap_desc *mmu_alloc_rmap_desc(struct kvm_vcpu *vcpu)
{
	return mmu_memory_cache_alloc(&vcpu->mmu_rmap_desc_cache,
				      sizeof(struct kvm_rmap_desc));
}

348
static void mmu_free_rmap_desc(struct kvm_rmap_desc *rd)
349
{
350
	kfree(rd);
351 352
}

353 354 355 356 357 358 359 360 361 362 363 364 365
/*
 * Take gfn and return the reverse mapping to it.
 * Note: gfn must be unaliased before this function get called
 */

static unsigned long *gfn_to_rmap(struct kvm *kvm, gfn_t gfn)
{
	struct kvm_memory_slot *slot;

	slot = gfn_to_memslot(kvm, gfn);
	return &slot->rmap[gfn - slot->base_gfn];
}

366 367 368
/*
 * Reverse mapping data structures:
 *
369 370
 * If rmapp bit zero is zero, then rmapp point to the shadw page table entry
 * that points to page_address(page).
371
 *
372 373
 * If rmapp bit zero is one, (then rmap & ~1) points to a struct kvm_rmap_desc
 * containing more mappings.
374
 */
375
static void rmap_add(struct kvm_vcpu *vcpu, u64 *spte, gfn_t gfn)
376
{
377
	struct kvm_mmu_page *sp;
378
	struct kvm_rmap_desc *desc;
379
	unsigned long *rmapp;
380 381 382 383
	int i;

	if (!is_rmap_pte(*spte))
		return;
384
	gfn = unalias_gfn(vcpu->kvm, gfn);
385 386
	sp = page_header(__pa(spte));
	sp->gfns[spte - sp->spt] = gfn;
387 388
	rmapp = gfn_to_rmap(vcpu->kvm, gfn);
	if (!*rmapp) {
389
		rmap_printk("rmap_add: %p %llx 0->1\n", spte, *spte);
390 391
		*rmapp = (unsigned long)spte;
	} else if (!(*rmapp & 1)) {
392
		rmap_printk("rmap_add: %p %llx 1->many\n", spte, *spte);
393
		desc = mmu_alloc_rmap_desc(vcpu);
394
		desc->shadow_ptes[0] = (u64 *)*rmapp;
395
		desc->shadow_ptes[1] = spte;
396
		*rmapp = (unsigned long)desc | 1;
397 398
	} else {
		rmap_printk("rmap_add: %p %llx many->many\n", spte, *spte);
399
		desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
400 401 402
		while (desc->shadow_ptes[RMAP_EXT-1] && desc->more)
			desc = desc->more;
		if (desc->shadow_ptes[RMAP_EXT-1]) {
403
			desc->more = mmu_alloc_rmap_desc(vcpu);
404 405 406 407 408 409 410 411
			desc = desc->more;
		}
		for (i = 0; desc->shadow_ptes[i]; ++i)
			;
		desc->shadow_ptes[i] = spte;
	}
}

412
static void rmap_desc_remove_entry(unsigned long *rmapp,
413 414 415 416 417 418 419 420 421
				   struct kvm_rmap_desc *desc,
				   int i,
				   struct kvm_rmap_desc *prev_desc)
{
	int j;

	for (j = RMAP_EXT - 1; !desc->shadow_ptes[j] && j > i; --j)
		;
	desc->shadow_ptes[i] = desc->shadow_ptes[j];
A
Al Viro 已提交
422
	desc->shadow_ptes[j] = NULL;
423 424 425
	if (j != 0)
		return;
	if (!prev_desc && !desc->more)
426
		*rmapp = (unsigned long)desc->shadow_ptes[0];
427 428 429 430
	else
		if (prev_desc)
			prev_desc->more = desc->more;
		else
431
			*rmapp = (unsigned long)desc->more | 1;
432
	mmu_free_rmap_desc(desc);
433 434
}

435
static void rmap_remove(struct kvm *kvm, u64 *spte)
436 437 438
{
	struct kvm_rmap_desc *desc;
	struct kvm_rmap_desc *prev_desc;
439
	struct kvm_mmu_page *sp;
A
Avi Kivity 已提交
440
	struct page *page;
441
	unsigned long *rmapp;
442 443 444 445
	int i;

	if (!is_rmap_pte(*spte))
		return;
446
	sp = page_header(__pa(spte));
A
Avi Kivity 已提交
447
	page = pfn_to_page((*spte & PT64_BASE_ADDR_MASK) >> PAGE_SHIFT);
448
	mark_page_accessed(page);
449
	if (is_writeble_pte(*spte))
A
Avi Kivity 已提交
450
		kvm_release_page_dirty(page);
451
	else
A
Avi Kivity 已提交
452
		kvm_release_page_clean(page);
453
	rmapp = gfn_to_rmap(kvm, sp->gfns[spte - sp->spt]);
454
	if (!*rmapp) {
455 456
		printk(KERN_ERR "rmap_remove: %p %llx 0->BUG\n", spte, *spte);
		BUG();
457
	} else if (!(*rmapp & 1)) {
458
		rmap_printk("rmap_remove:  %p %llx 1->0\n", spte, *spte);
459
		if ((u64 *)*rmapp != spte) {
460 461 462 463
			printk(KERN_ERR "rmap_remove:  %p %llx 1->BUG\n",
			       spte, *spte);
			BUG();
		}
464
		*rmapp = 0;
465 466
	} else {
		rmap_printk("rmap_remove:  %p %llx many->many\n", spte, *spte);
467
		desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
468 469 470 471
		prev_desc = NULL;
		while (desc) {
			for (i = 0; i < RMAP_EXT && desc->shadow_ptes[i]; ++i)
				if (desc->shadow_ptes[i] == spte) {
472
					rmap_desc_remove_entry(rmapp,
473
							       desc, i,
474 475 476 477 478 479 480 481 482 483
							       prev_desc);
					return;
				}
			prev_desc = desc;
			desc = desc->more;
		}
		BUG();
	}
}

484
static u64 *rmap_next(struct kvm *kvm, unsigned long *rmapp, u64 *spte)
485 486
{
	struct kvm_rmap_desc *desc;
487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513
	struct kvm_rmap_desc *prev_desc;
	u64 *prev_spte;
	int i;

	if (!*rmapp)
		return NULL;
	else if (!(*rmapp & 1)) {
		if (!spte)
			return (u64 *)*rmapp;
		return NULL;
	}
	desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
	prev_desc = NULL;
	prev_spte = NULL;
	while (desc) {
		for (i = 0; i < RMAP_EXT && desc->shadow_ptes[i]; ++i) {
			if (prev_spte == spte)
				return desc->shadow_ptes[i];
			prev_spte = desc->shadow_ptes[i];
		}
		desc = desc->more;
	}
	return NULL;
}

static void rmap_write_protect(struct kvm *kvm, u64 gfn)
{
514
	unsigned long *rmapp;
515 516
	u64 *spte;

517 518
	gfn = unalias_gfn(kvm, gfn);
	rmapp = gfn_to_rmap(kvm, gfn);
519

520 521
	spte = rmap_next(kvm, rmapp, NULL);
	while (spte) {
522 523 524
		BUG_ON(!spte);
		BUG_ON(!(*spte & PT_PRESENT_MASK));
		rmap_printk("rmap_write_protect: spte %p %llx\n", spte, *spte);
525 526
		if (is_writeble_pte(*spte))
			set_shadow_pte(spte, *spte & ~PT_WRITABLE_MASK);
527
		kvm_flush_remote_tlbs(kvm);
528
		spte = rmap_next(kvm, rmapp, spte);
529 530 531
	}
}

532
#ifdef MMU_DEBUG
533
static int is_empty_shadow_page(u64 *spt)
A
Avi Kivity 已提交
534
{
535 536 537
	u64 *pos;
	u64 *end;

538
	for (pos = spt, end = pos + PAGE_SIZE / sizeof(u64); pos != end; pos++)
539
		if ((*pos & ~PT_SHADOW_IO_MARK) != shadow_trap_nonpresent_pte) {
540 541
			printk(KERN_ERR "%s: %p %llx\n", __FUNCTION__,
			       pos, *pos);
A
Avi Kivity 已提交
542
			return 0;
543
		}
A
Avi Kivity 已提交
544 545
	return 1;
}
546
#endif
A
Avi Kivity 已提交
547

548
static void kvm_mmu_free_page(struct kvm *kvm, struct kvm_mmu_page *sp)
549
{
550 551 552 553 554
	ASSERT(is_empty_shadow_page(sp->spt));
	list_del(&sp->link);
	__free_page(virt_to_page(sp->spt));
	__free_page(virt_to_page(sp->gfns));
	kfree(sp);
555
	++kvm->n_free_mmu_pages;
556 557
}

558 559 560 561 562
static unsigned kvm_page_table_hashfn(gfn_t gfn)
{
	return gfn;
}

563 564
static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
					       u64 *parent_pte)
A
Avi Kivity 已提交
565
{
566
	struct kvm_mmu_page *sp;
A
Avi Kivity 已提交
567

568
	if (!vcpu->kvm->n_free_mmu_pages)
569
		return NULL;
A
Avi Kivity 已提交
570

571 572 573 574 575 576 577 578 579
	sp = mmu_memory_cache_alloc(&vcpu->mmu_page_header_cache, sizeof *sp);
	sp->spt = mmu_memory_cache_alloc(&vcpu->mmu_page_cache, PAGE_SIZE);
	sp->gfns = mmu_memory_cache_alloc(&vcpu->mmu_page_cache, PAGE_SIZE);
	set_page_private(virt_to_page(sp->spt), (unsigned long)sp);
	list_add(&sp->link, &vcpu->kvm->active_mmu_pages);
	ASSERT(is_empty_shadow_page(sp->spt));
	sp->slot_bitmap = 0;
	sp->multimapped = 0;
	sp->parent_pte = parent_pte;
A
Avi Kivity 已提交
580
	--vcpu->kvm->n_free_mmu_pages;
581
	return sp;
A
Avi Kivity 已提交
582 583
}

584
static void mmu_page_add_parent_pte(struct kvm_vcpu *vcpu,
585
				    struct kvm_mmu_page *sp, u64 *parent_pte)
586 587 588 589 590 591 592
{
	struct kvm_pte_chain *pte_chain;
	struct hlist_node *node;
	int i;

	if (!parent_pte)
		return;
593 594
	if (!sp->multimapped) {
		u64 *old = sp->parent_pte;
595 596

		if (!old) {
597
			sp->parent_pte = parent_pte;
598 599
			return;
		}
600
		sp->multimapped = 1;
601
		pte_chain = mmu_alloc_pte_chain(vcpu);
602 603
		INIT_HLIST_HEAD(&sp->parent_ptes);
		hlist_add_head(&pte_chain->link, &sp->parent_ptes);
604 605
		pte_chain->parent_ptes[0] = old;
	}
606
	hlist_for_each_entry(pte_chain, node, &sp->parent_ptes, link) {
607 608 609 610 611 612 613 614
		if (pte_chain->parent_ptes[NR_PTE_CHAIN_ENTRIES-1])
			continue;
		for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i)
			if (!pte_chain->parent_ptes[i]) {
				pte_chain->parent_ptes[i] = parent_pte;
				return;
			}
	}
615
	pte_chain = mmu_alloc_pte_chain(vcpu);
616
	BUG_ON(!pte_chain);
617
	hlist_add_head(&pte_chain->link, &sp->parent_ptes);
618 619 620
	pte_chain->parent_ptes[0] = parent_pte;
}

621
static void mmu_page_remove_parent_pte(struct kvm_mmu_page *sp,
622 623 624 625 626 627
				       u64 *parent_pte)
{
	struct kvm_pte_chain *pte_chain;
	struct hlist_node *node;
	int i;

628 629 630
	if (!sp->multimapped) {
		BUG_ON(sp->parent_pte != parent_pte);
		sp->parent_pte = NULL;
631 632
		return;
	}
633
	hlist_for_each_entry(pte_chain, node, &sp->parent_ptes, link)
634 635 636 637 638
		for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i) {
			if (!pte_chain->parent_ptes[i])
				break;
			if (pte_chain->parent_ptes[i] != parent_pte)
				continue;
639 640
			while (i + 1 < NR_PTE_CHAIN_ENTRIES
				&& pte_chain->parent_ptes[i + 1]) {
641 642 643 644 645
				pte_chain->parent_ptes[i]
					= pte_chain->parent_ptes[i + 1];
				++i;
			}
			pte_chain->parent_ptes[i] = NULL;
646 647
			if (i == 0) {
				hlist_del(&pte_chain->link);
648
				mmu_free_pte_chain(pte_chain);
649 650 651
				if (hlist_empty(&sp->parent_ptes)) {
					sp->multimapped = 0;
					sp->parent_pte = NULL;
652 653
				}
			}
654 655 656 657 658
			return;
		}
	BUG();
}

659
static struct kvm_mmu_page *kvm_mmu_lookup_page(struct kvm *kvm, gfn_t gfn)
660 661 662
{
	unsigned index;
	struct hlist_head *bucket;
663
	struct kvm_mmu_page *sp;
664 665 666 667
	struct hlist_node *node;

	pgprintk("%s: looking for gfn %lx\n", __FUNCTION__, gfn);
	index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
668
	bucket = &kvm->mmu_page_hash[index];
669 670
	hlist_for_each_entry(sp, node, bucket, hash_link)
		if (sp->gfn == gfn && !sp->role.metaphysical) {
671
			pgprintk("%s: found role %x\n",
672 673
				 __FUNCTION__, sp->role.word);
			return sp;
674 675 676 677 678 679 680 681 682
		}
	return NULL;
}

static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu,
					     gfn_t gfn,
					     gva_t gaddr,
					     unsigned level,
					     int metaphysical,
683
					     unsigned access,
684 685 686 687 688 689
					     u64 *parent_pte)
{
	union kvm_mmu_page_role role;
	unsigned index;
	unsigned quadrant;
	struct hlist_head *bucket;
690
	struct kvm_mmu_page *sp;
691 692 693 694 695 696
	struct hlist_node *node;

	role.word = 0;
	role.glevels = vcpu->mmu.root_level;
	role.level = level;
	role.metaphysical = metaphysical;
697
	role.access = access;
698 699 700 701 702 703 704 705 706
	if (vcpu->mmu.root_level <= PT32_ROOT_LEVEL) {
		quadrant = gaddr >> (PAGE_SHIFT + (PT64_PT_BITS * level));
		quadrant &= (1 << ((PT32_PT_BITS - PT64_PT_BITS) * level)) - 1;
		role.quadrant = quadrant;
	}
	pgprintk("%s: looking gfn %lx role %x\n", __FUNCTION__,
		 gfn, role.word);
	index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
	bucket = &vcpu->kvm->mmu_page_hash[index];
707 708 709
	hlist_for_each_entry(sp, node, bucket, hash_link)
		if (sp->gfn == gfn && sp->role.word == role.word) {
			mmu_page_add_parent_pte(vcpu, sp, parent_pte);
710
			pgprintk("%s: found\n", __FUNCTION__);
711
			return sp;
712
		}
713 714 715
	sp = kvm_mmu_alloc_page(vcpu, parent_pte);
	if (!sp)
		return sp;
716
	pgprintk("%s: adding gfn %lx role %x\n", __FUNCTION__, gfn, role.word);
717 718 719 720
	sp->gfn = gfn;
	sp->role = role;
	hlist_add_head(&sp->hash_link, bucket);
	vcpu->mmu.prefetch_page(vcpu, sp);
721
	if (!metaphysical)
722
		rmap_write_protect(vcpu->kvm, gfn);
723
	return sp;
724 725
}

726
static void kvm_mmu_page_unlink_children(struct kvm *kvm,
727
					 struct kvm_mmu_page *sp)
728
{
729 730 731 732
	unsigned i;
	u64 *pt;
	u64 ent;

733
	pt = sp->spt;
734

735
	if (sp->role.level == PT_PAGE_TABLE_LEVEL) {
736
		for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
737
			if (is_shadow_present_pte(pt[i]))
738
				rmap_remove(kvm, &pt[i]);
739
			pt[i] = shadow_trap_nonpresent_pte;
740
		}
741
		kvm_flush_remote_tlbs(kvm);
742 743 744 745 746 747
		return;
	}

	for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
		ent = pt[i];

748 749
		pt[i] = shadow_trap_nonpresent_pte;
		if (!is_shadow_present_pte(ent))
750 751
			continue;
		ent &= PT64_BASE_ADDR_MASK;
752
		mmu_page_remove_parent_pte(page_header(ent), &pt[i]);
753
	}
754
	kvm_flush_remote_tlbs(kvm);
755 756
}

757
static void kvm_mmu_put_page(struct kvm_mmu_page *sp, u64 *parent_pte)
758
{
759
	mmu_page_remove_parent_pte(sp, parent_pte);
760 761
}

762 763 764 765 766 767 768 769 770
static void kvm_mmu_reset_last_pte_updated(struct kvm *kvm)
{
	int i;

	for (i = 0; i < KVM_MAX_VCPUS; ++i)
		if (kvm->vcpus[i])
			kvm->vcpus[i]->last_pte_updated = NULL;
}

771
static void kvm_mmu_zap_page(struct kvm *kvm, struct kvm_mmu_page *sp)
772 773 774
{
	u64 *parent_pte;

A
Avi Kivity 已提交
775
	++kvm->stat.mmu_shadow_zapped;
776 777 778
	while (sp->multimapped || sp->parent_pte) {
		if (!sp->multimapped)
			parent_pte = sp->parent_pte;
779 780 781
		else {
			struct kvm_pte_chain *chain;

782
			chain = container_of(sp->parent_ptes.first,
783 784 785
					     struct kvm_pte_chain, link);
			parent_pte = chain->parent_ptes[0];
		}
786
		BUG_ON(!parent_pte);
787
		kvm_mmu_put_page(sp, parent_pte);
788
		set_shadow_pte(parent_pte, shadow_trap_nonpresent_pte);
789
	}
790 791 792 793
	kvm_mmu_page_unlink_children(kvm, sp);
	if (!sp->root_count) {
		hlist_del(&sp->hash_link);
		kvm_mmu_free_page(kvm, sp);
A
Avi Kivity 已提交
794
	} else
795
		list_move(&sp->link, &kvm->active_mmu_pages);
796
	kvm_mmu_reset_last_pte_updated(kvm);
797 798
}

799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832
/*
 * Changing the number of mmu pages allocated to the vm
 * Note: if kvm_nr_mmu_pages is too small, you will get dead lock
 */
void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int kvm_nr_mmu_pages)
{
	/*
	 * If we set the number of mmu pages to be smaller be than the
	 * number of actived pages , we must to free some mmu pages before we
	 * change the value
	 */

	if ((kvm->n_alloc_mmu_pages - kvm->n_free_mmu_pages) >
	    kvm_nr_mmu_pages) {
		int n_used_mmu_pages = kvm->n_alloc_mmu_pages
				       - kvm->n_free_mmu_pages;

		while (n_used_mmu_pages > kvm_nr_mmu_pages) {
			struct kvm_mmu_page *page;

			page = container_of(kvm->active_mmu_pages.prev,
					    struct kvm_mmu_page, link);
			kvm_mmu_zap_page(kvm, page);
			n_used_mmu_pages--;
		}
		kvm->n_free_mmu_pages = 0;
	}
	else
		kvm->n_free_mmu_pages += kvm_nr_mmu_pages
					 - kvm->n_alloc_mmu_pages;

	kvm->n_alloc_mmu_pages = kvm_nr_mmu_pages;
}

833
static int kvm_mmu_unprotect_page(struct kvm *kvm, gfn_t gfn)
834 835 836
{
	unsigned index;
	struct hlist_head *bucket;
837
	struct kvm_mmu_page *sp;
838 839 840 841 842 843
	struct hlist_node *node, *n;
	int r;

	pgprintk("%s: looking for gfn %lx\n", __FUNCTION__, gfn);
	r = 0;
	index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
844
	bucket = &kvm->mmu_page_hash[index];
845 846
	hlist_for_each_entry_safe(sp, node, n, bucket, hash_link)
		if (sp->gfn == gfn && !sp->role.metaphysical) {
847
			pgprintk("%s: gfn %lx role %x\n", __FUNCTION__, gfn,
848 849
				 sp->role.word);
			kvm_mmu_zap_page(kvm, sp);
850 851 852
			r = 1;
		}
	return r;
853 854
}

855
static void mmu_unshadow(struct kvm *kvm, gfn_t gfn)
856
{
857
	struct kvm_mmu_page *sp;
858

859 860 861
	while ((sp = kvm_mmu_lookup_page(kvm, gfn)) != NULL) {
		pgprintk("%s: zap %lx %x\n", __FUNCTION__, gfn, sp->role.word);
		kvm_mmu_zap_page(kvm, sp);
862 863 864
	}
}

865
static void page_header_update_slot(struct kvm *kvm, void *pte, gfn_t gfn)
A
Avi Kivity 已提交
866
{
867
	int slot = memslot_id(kvm, gfn_to_memslot(kvm, gfn));
868
	struct kvm_mmu_page *sp = page_header(__pa(pte));
A
Avi Kivity 已提交
869

870
	__set_bit(slot, &sp->slot_bitmap);
A
Avi Kivity 已提交
871 872
}

873 874 875 876 877 878
struct page *gva_to_page(struct kvm_vcpu *vcpu, gva_t gva)
{
	gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, gva);

	if (gpa == UNMAPPED_GVA)
		return NULL;
A
Avi Kivity 已提交
879
	return gfn_to_page(vcpu->kvm, gpa >> PAGE_SHIFT);
880 881
}

A
Avi Kivity 已提交
882 883 884 885
static void nonpaging_new_cr3(struct kvm_vcpu *vcpu)
{
}

A
Avi Kivity 已提交
886
static int nonpaging_map(struct kvm_vcpu *vcpu, gva_t v, struct page *page)
A
Avi Kivity 已提交
887 888 889 890 891 892 893
{
	int level = PT32E_ROOT_LEVEL;
	hpa_t table_addr = vcpu->mmu.root_hpa;

	for (; ; level--) {
		u32 index = PT64_INDEX(v, level);
		u64 *table;
894
		u64 pte;
A
Avi Kivity 已提交
895 896 897 898 899

		ASSERT(VALID_PAGE(table_addr));
		table = __va(table_addr);

		if (level == 1) {
900 901
			int was_rmapped;

902
			pte = table[index];
903
			was_rmapped = is_rmap_pte(pte);
904
			if (is_shadow_present_pte(pte) && is_writeble_pte(pte)) {
905
				kvm_release_page_clean(page);
906
				return 0;
907
			}
A
Avi Kivity 已提交
908
			mark_page_dirty(vcpu->kvm, v >> PAGE_SHIFT);
909 910
			page_header_update_slot(vcpu->kvm, table,
						v >> PAGE_SHIFT);
A
Avi Kivity 已提交
911 912 913
			table[index] = page_to_phys(page)
				| PT_PRESENT_MASK | PT_WRITABLE_MASK
				| PT_USER_MASK;
914 915
			if (!was_rmapped)
				rmap_add(vcpu, &table[index], v >> PAGE_SHIFT);
916
			else
917 918
				kvm_release_page_clean(page);

A
Avi Kivity 已提交
919 920 921
			return 0;
		}

922
		if (table[index] == shadow_trap_nonpresent_pte) {
923
			struct kvm_mmu_page *new_table;
924
			gfn_t pseudo_gfn;
A
Avi Kivity 已提交
925

926 927 928 929
			pseudo_gfn = (v & PT64_DIR_BASE_ADDR_MASK)
				>> PAGE_SHIFT;
			new_table = kvm_mmu_get_page(vcpu, pseudo_gfn,
						     v, level - 1,
930
						     1, ACC_ALL, &table[index]);
931
			if (!new_table) {
A
Avi Kivity 已提交
932
				pgprintk("nonpaging_map: ENOMEM\n");
933
				kvm_release_page_clean(page);
A
Avi Kivity 已提交
934 935 936
				return -ENOMEM;
			}

937
			table[index] = __pa(new_table->spt) | PT_PRESENT_MASK
938
				| PT_WRITABLE_MASK | PT_USER_MASK;
A
Avi Kivity 已提交
939 940 941 942 943
		}
		table_addr = table[index] & PT64_BASE_ADDR_MASK;
	}
}

944 945 946 947 948 949 950 951 952
static void nonpaging_prefetch_page(struct kvm_vcpu *vcpu,
				    struct kvm_mmu_page *sp)
{
	int i;

	for (i = 0; i < PT64_ENT_PER_PAGE; ++i)
		sp->spt[i] = shadow_trap_nonpresent_pte;
}

953 954 955
static void mmu_free_roots(struct kvm_vcpu *vcpu)
{
	int i;
956
	struct kvm_mmu_page *sp;
957

A
Avi Kivity 已提交
958 959
	if (!VALID_PAGE(vcpu->mmu.root_hpa))
		return;
960 961 962 963
#ifdef CONFIG_X86_64
	if (vcpu->mmu.shadow_root_level == PT64_ROOT_LEVEL) {
		hpa_t root = vcpu->mmu.root_hpa;

964 965
		sp = page_header(root);
		--sp->root_count;
966 967 968 969 970 971 972
		vcpu->mmu.root_hpa = INVALID_PAGE;
		return;
	}
#endif
	for (i = 0; i < 4; ++i) {
		hpa_t root = vcpu->mmu.pae_root[i];

A
Avi Kivity 已提交
973 974
		if (root) {
			root &= PT64_BASE_ADDR_MASK;
975 976
			sp = page_header(root);
			--sp->root_count;
A
Avi Kivity 已提交
977
		}
978 979 980 981 982 983 984 985
		vcpu->mmu.pae_root[i] = INVALID_PAGE;
	}
	vcpu->mmu.root_hpa = INVALID_PAGE;
}

static void mmu_alloc_roots(struct kvm_vcpu *vcpu)
{
	int i;
986
	gfn_t root_gfn;
987
	struct kvm_mmu_page *sp;
988

989
	root_gfn = vcpu->cr3 >> PAGE_SHIFT;
990 991 992 993 994 995

#ifdef CONFIG_X86_64
	if (vcpu->mmu.shadow_root_level == PT64_ROOT_LEVEL) {
		hpa_t root = vcpu->mmu.root_hpa;

		ASSERT(!VALID_PAGE(root));
996
		sp = kvm_mmu_get_page(vcpu, root_gfn, 0,
997
				      PT64_ROOT_LEVEL, 0, ACC_ALL, NULL);
998 999
		root = __pa(sp->spt);
		++sp->root_count;
1000 1001 1002 1003 1004 1005 1006 1007
		vcpu->mmu.root_hpa = root;
		return;
	}
#endif
	for (i = 0; i < 4; ++i) {
		hpa_t root = vcpu->mmu.pae_root[i];

		ASSERT(!VALID_PAGE(root));
A
Avi Kivity 已提交
1008 1009 1010 1011 1012
		if (vcpu->mmu.root_level == PT32E_ROOT_LEVEL) {
			if (!is_present_pte(vcpu->pdptrs[i])) {
				vcpu->mmu.pae_root[i] = 0;
				continue;
			}
1013
			root_gfn = vcpu->pdptrs[i] >> PAGE_SHIFT;
A
Avi Kivity 已提交
1014
		} else if (vcpu->mmu.root_level == 0)
1015
			root_gfn = 0;
1016 1017
		sp = kvm_mmu_get_page(vcpu, root_gfn, i << 30,
				      PT32_ROOT_LEVEL, !is_paging(vcpu),
1018
				      ACC_ALL, NULL);
1019 1020
		root = __pa(sp->spt);
		++sp->root_count;
1021 1022 1023 1024 1025
		vcpu->mmu.pae_root[i] = root | PT_PRESENT_MASK;
	}
	vcpu->mmu.root_hpa = __pa(vcpu->mmu.pae_root);
}

A
Avi Kivity 已提交
1026 1027 1028 1029 1030 1031
static gpa_t nonpaging_gva_to_gpa(struct kvm_vcpu *vcpu, gva_t vaddr)
{
	return vaddr;
}

static int nonpaging_page_fault(struct kvm_vcpu *vcpu, gva_t gva,
A
Avi Kivity 已提交
1032
				u32 error_code)
A
Avi Kivity 已提交
1033
{
A
Avi Kivity 已提交
1034
	struct page *page;
1035
	int r;
A
Avi Kivity 已提交
1036

1037 1038 1039
	r = mmu_topup_memory_caches(vcpu);
	if (r)
		return r;
1040

A
Avi Kivity 已提交
1041 1042 1043
	ASSERT(vcpu);
	ASSERT(VALID_PAGE(vcpu->mmu.root_hpa));

A
Avi Kivity 已提交
1044
	page = gfn_to_page(vcpu->kvm, gva >> PAGE_SHIFT);
A
Avi Kivity 已提交
1045

A
Avi Kivity 已提交
1046 1047
	if (is_error_page(page)) {
		kvm_release_page_clean(page);
A
Avi Kivity 已提交
1048
		return 1;
1049
	}
A
Avi Kivity 已提交
1050

A
Avi Kivity 已提交
1051
	return nonpaging_map(vcpu, gva & PAGE_MASK, page);
A
Avi Kivity 已提交
1052 1053 1054 1055
}

static void nonpaging_free(struct kvm_vcpu *vcpu)
{
1056
	mmu_free_roots(vcpu);
A
Avi Kivity 已提交
1057 1058 1059 1060 1061 1062 1063 1064 1065 1066
}

static int nonpaging_init_context(struct kvm_vcpu *vcpu)
{
	struct kvm_mmu *context = &vcpu->mmu;

	context->new_cr3 = nonpaging_new_cr3;
	context->page_fault = nonpaging_page_fault;
	context->gva_to_gpa = nonpaging_gva_to_gpa;
	context->free = nonpaging_free;
1067
	context->prefetch_page = nonpaging_prefetch_page;
1068
	context->root_level = 0;
A
Avi Kivity 已提交
1069
	context->shadow_root_level = PT32E_ROOT_LEVEL;
A
Avi Kivity 已提交
1070
	context->root_hpa = INVALID_PAGE;
A
Avi Kivity 已提交
1071 1072 1073
	return 0;
}

1074
void kvm_mmu_flush_tlb(struct kvm_vcpu *vcpu)
A
Avi Kivity 已提交
1075
{
A
Avi Kivity 已提交
1076
	++vcpu->stat.tlb_flush;
1077
	kvm_x86_ops->tlb_flush(vcpu);
A
Avi Kivity 已提交
1078 1079 1080 1081
}

static void paging_new_cr3(struct kvm_vcpu *vcpu)
{
1082
	pgprintk("%s: cr3 %lx\n", __FUNCTION__, vcpu->cr3);
1083
	mmu_free_roots(vcpu);
A
Avi Kivity 已提交
1084 1085 1086 1087 1088 1089
}

static void inject_page_fault(struct kvm_vcpu *vcpu,
			      u64 addr,
			      u32 err_code)
{
1090
	kvm_inject_page_fault(vcpu, addr, err_code);
A
Avi Kivity 已提交
1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
}

static void paging_free(struct kvm_vcpu *vcpu)
{
	nonpaging_free(vcpu);
}

#define PTTYPE 64
#include "paging_tmpl.h"
#undef PTTYPE

#define PTTYPE 32
#include "paging_tmpl.h"
#undef PTTYPE

1106
static int paging64_init_context_common(struct kvm_vcpu *vcpu, int level)
A
Avi Kivity 已提交
1107 1108 1109 1110 1111 1112 1113
{
	struct kvm_mmu *context = &vcpu->mmu;

	ASSERT(is_pae(vcpu));
	context->new_cr3 = paging_new_cr3;
	context->page_fault = paging64_page_fault;
	context->gva_to_gpa = paging64_gva_to_gpa;
1114
	context->prefetch_page = paging64_prefetch_page;
A
Avi Kivity 已提交
1115
	context->free = paging_free;
1116 1117
	context->root_level = level;
	context->shadow_root_level = level;
A
Avi Kivity 已提交
1118
	context->root_hpa = INVALID_PAGE;
A
Avi Kivity 已提交
1119 1120 1121
	return 0;
}

1122 1123 1124 1125 1126
static int paging64_init_context(struct kvm_vcpu *vcpu)
{
	return paging64_init_context_common(vcpu, PT64_ROOT_LEVEL);
}

A
Avi Kivity 已提交
1127 1128 1129 1130 1131 1132 1133 1134
static int paging32_init_context(struct kvm_vcpu *vcpu)
{
	struct kvm_mmu *context = &vcpu->mmu;

	context->new_cr3 = paging_new_cr3;
	context->page_fault = paging32_page_fault;
	context->gva_to_gpa = paging32_gva_to_gpa;
	context->free = paging_free;
1135
	context->prefetch_page = paging32_prefetch_page;
A
Avi Kivity 已提交
1136 1137
	context->root_level = PT32_ROOT_LEVEL;
	context->shadow_root_level = PT32E_ROOT_LEVEL;
A
Avi Kivity 已提交
1138
	context->root_hpa = INVALID_PAGE;
A
Avi Kivity 已提交
1139 1140 1141 1142 1143
	return 0;
}

static int paging32E_init_context(struct kvm_vcpu *vcpu)
{
1144
	return paging64_init_context_common(vcpu, PT32E_ROOT_LEVEL);
A
Avi Kivity 已提交
1145 1146 1147 1148 1149 1150 1151 1152 1153
}

static int init_kvm_mmu(struct kvm_vcpu *vcpu)
{
	ASSERT(vcpu);
	ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));

	if (!is_paging(vcpu))
		return nonpaging_init_context(vcpu);
A
Avi Kivity 已提交
1154
	else if (is_long_mode(vcpu))
A
Avi Kivity 已提交
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171
		return paging64_init_context(vcpu);
	else if (is_pae(vcpu))
		return paging32E_init_context(vcpu);
	else
		return paging32_init_context(vcpu);
}

static void destroy_kvm_mmu(struct kvm_vcpu *vcpu)
{
	ASSERT(vcpu);
	if (VALID_PAGE(vcpu->mmu.root_hpa)) {
		vcpu->mmu.free(vcpu);
		vcpu->mmu.root_hpa = INVALID_PAGE;
	}
}

int kvm_mmu_reset_context(struct kvm_vcpu *vcpu)
A
Avi Kivity 已提交
1172 1173 1174 1175
{
	destroy_kvm_mmu(vcpu);
	return init_kvm_mmu(vcpu);
}
1176
EXPORT_SYMBOL_GPL(kvm_mmu_reset_context);
A
Avi Kivity 已提交
1177 1178

int kvm_mmu_load(struct kvm_vcpu *vcpu)
A
Avi Kivity 已提交
1179
{
1180 1181
	int r;

S
Shaohua Li 已提交
1182
	mutex_lock(&vcpu->kvm->lock);
1183
	r = mmu_topup_memory_caches(vcpu);
A
Avi Kivity 已提交
1184 1185 1186
	if (r)
		goto out;
	mmu_alloc_roots(vcpu);
1187
	kvm_x86_ops->set_cr3(vcpu, vcpu->mmu.root_hpa);
A
Avi Kivity 已提交
1188
	kvm_mmu_flush_tlb(vcpu);
1189
out:
S
Shaohua Li 已提交
1190
	mutex_unlock(&vcpu->kvm->lock);
1191
	return r;
A
Avi Kivity 已提交
1192
}
A
Avi Kivity 已提交
1193 1194 1195 1196 1197 1198
EXPORT_SYMBOL_GPL(kvm_mmu_load);

void kvm_mmu_unload(struct kvm_vcpu *vcpu)
{
	mmu_free_roots(vcpu);
}
A
Avi Kivity 已提交
1199

1200
static void mmu_pte_write_zap_pte(struct kvm_vcpu *vcpu,
1201
				  struct kvm_mmu_page *sp,
1202 1203 1204 1205 1206 1207
				  u64 *spte)
{
	u64 pte;
	struct kvm_mmu_page *child;

	pte = *spte;
1208
	if (is_shadow_present_pte(pte)) {
1209
		if (sp->role.level == PT_PAGE_TABLE_LEVEL)
1210
			rmap_remove(vcpu->kvm, spte);
1211 1212
		else {
			child = page_header(pte & PT64_BASE_ADDR_MASK);
1213
			mmu_page_remove_parent_pte(child, spte);
1214 1215
		}
	}
1216
	set_shadow_pte(spte, shadow_trap_nonpresent_pte);
1217 1218
}

1219
static void mmu_pte_write_new_pte(struct kvm_vcpu *vcpu,
1220
				  struct kvm_mmu_page *sp,
1221
				  u64 *spte,
1222 1223
				  const void *new, int bytes,
				  int offset_in_pte)
1224
{
1225
	if (sp->role.level != PT_PAGE_TABLE_LEVEL) {
A
Avi Kivity 已提交
1226
		++vcpu->kvm->stat.mmu_pde_zapped;
1227
		return;
A
Avi Kivity 已提交
1228
	}
1229

A
Avi Kivity 已提交
1230
	++vcpu->kvm->stat.mmu_pte_updated;
1231 1232
	if (sp->role.glevels == PT32_ROOT_LEVEL)
		paging32_update_pte(vcpu, sp, spte, new, bytes, offset_in_pte);
1233
	else
1234
		paging64_update_pte(vcpu, sp, spte, new, bytes, offset_in_pte);
1235 1236
}

1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257
static bool need_remote_flush(u64 old, u64 new)
{
	if (!is_shadow_present_pte(old))
		return false;
	if (!is_shadow_present_pte(new))
		return true;
	if ((old ^ new) & PT64_BASE_ADDR_MASK)
		return true;
	old ^= PT64_NX_MASK;
	new ^= PT64_NX_MASK;
	return (old & ~new & PT64_PERM_MASK) != 0;
}

static void mmu_pte_write_flush_tlb(struct kvm_vcpu *vcpu, u64 old, u64 new)
{
	if (need_remote_flush(old, new))
		kvm_flush_remote_tlbs(vcpu->kvm);
	else
		kvm_mmu_flush_tlb(vcpu);
}

1258 1259 1260 1261 1262 1263 1264
static bool last_updated_pte_accessed(struct kvm_vcpu *vcpu)
{
	u64 *spte = vcpu->last_pte_updated;

	return !!(spte && (*spte & PT_ACCESSED_MASK));
}

1265
void kvm_mmu_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
1266
		       const u8 *new, int bytes)
1267
{
1268
	gfn_t gfn = gpa >> PAGE_SHIFT;
1269
	struct kvm_mmu_page *sp;
1270
	struct hlist_node *node, *n;
1271 1272
	struct hlist_head *bucket;
	unsigned index;
1273
	u64 entry;
1274 1275
	u64 *spte;
	unsigned offset = offset_in_page(gpa);
1276
	unsigned pte_size;
1277
	unsigned page_offset;
1278
	unsigned misaligned;
1279
	unsigned quadrant;
1280
	int level;
1281
	int flooded = 0;
1282
	int npte;
1283

1284
	pgprintk("%s: gpa %llx bytes %d\n", __FUNCTION__, gpa, bytes);
A
Avi Kivity 已提交
1285
	++vcpu->kvm->stat.mmu_pte_write;
1286
	kvm_mmu_audit(vcpu, "pre pte write");
1287 1288
	if (gfn == vcpu->last_pt_write_gfn
	    && !last_updated_pte_accessed(vcpu)) {
1289 1290 1291 1292 1293 1294
		++vcpu->last_pt_write_count;
		if (vcpu->last_pt_write_count >= 3)
			flooded = 1;
	} else {
		vcpu->last_pt_write_gfn = gfn;
		vcpu->last_pt_write_count = 1;
1295
		vcpu->last_pte_updated = NULL;
1296
	}
1297 1298
	index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
	bucket = &vcpu->kvm->mmu_page_hash[index];
1299 1300
	hlist_for_each_entry_safe(sp, node, n, bucket, hash_link) {
		if (sp->gfn != gfn || sp->role.metaphysical)
1301
			continue;
1302
		pte_size = sp->role.glevels == PT32_ROOT_LEVEL ? 4 : 8;
1303
		misaligned = (offset ^ (offset + bytes - 1)) & ~(pte_size - 1);
1304
		misaligned |= bytes < 4;
1305
		if (misaligned || flooded) {
1306 1307 1308 1309
			/*
			 * Misaligned accesses are too much trouble to fix
			 * up; also, they usually indicate a page is not used
			 * as a page table.
1310 1311 1312 1313 1314
			 *
			 * If we're seeing too many writes to a page,
			 * it may no longer be a page table, or we may be
			 * forking, in which case it is better to unmap the
			 * page.
1315 1316
			 */
			pgprintk("misaligned: gpa %llx bytes %d role %x\n",
1317 1318
				 gpa, bytes, sp->role.word);
			kvm_mmu_zap_page(vcpu->kvm, sp);
A
Avi Kivity 已提交
1319
			++vcpu->kvm->stat.mmu_flooded;
1320 1321
			continue;
		}
1322
		page_offset = offset;
1323
		level = sp->role.level;
1324
		npte = 1;
1325
		if (sp->role.glevels == PT32_ROOT_LEVEL) {
1326 1327 1328 1329 1330 1331 1332
			page_offset <<= 1;	/* 32->64 */
			/*
			 * A 32-bit pde maps 4MB while the shadow pdes map
			 * only 2MB.  So we need to double the offset again
			 * and zap two pdes instead of one.
			 */
			if (level == PT32_ROOT_LEVEL) {
1333
				page_offset &= ~7; /* kill rounding error */
1334 1335 1336
				page_offset <<= 1;
				npte = 2;
			}
1337
			quadrant = page_offset >> PAGE_SHIFT;
1338
			page_offset &= ~PAGE_MASK;
1339
			if (quadrant != sp->role.quadrant)
1340
				continue;
1341
		}
1342
		spte = &sp->spt[page_offset / sizeof(*spte)];
1343
		while (npte--) {
1344
			entry = *spte;
1345 1346
			mmu_pte_write_zap_pte(vcpu, sp, spte);
			mmu_pte_write_new_pte(vcpu, sp, spte, new, bytes,
1347
					      page_offset & (pte_size - 1));
1348
			mmu_pte_write_flush_tlb(vcpu, entry, *spte);
1349
			++spte;
1350 1351
		}
	}
1352
	kvm_mmu_audit(vcpu, "post pte write");
1353 1354
}

1355 1356 1357 1358
int kvm_mmu_unprotect_page_virt(struct kvm_vcpu *vcpu, gva_t gva)
{
	gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, gva);

1359
	return kvm_mmu_unprotect_page(vcpu->kvm, gpa >> PAGE_SHIFT);
1360 1361
}

1362
void __kvm_mmu_free_some_pages(struct kvm_vcpu *vcpu)
A
Avi Kivity 已提交
1363 1364
{
	while (vcpu->kvm->n_free_mmu_pages < KVM_REFILL_PAGES) {
1365
		struct kvm_mmu_page *sp;
A
Avi Kivity 已提交
1366

1367 1368 1369
		sp = container_of(vcpu->kvm->active_mmu_pages.prev,
				  struct kvm_mmu_page, link);
		kvm_mmu_zap_page(vcpu->kvm, sp);
A
Avi Kivity 已提交
1370
		++vcpu->kvm->stat.mmu_recycled;
A
Avi Kivity 已提交
1371 1372 1373
	}
}

1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388
int kvm_mmu_page_fault(struct kvm_vcpu *vcpu, gva_t cr2, u32 error_code)
{
	int r;
	enum emulation_result er;

	mutex_lock(&vcpu->kvm->lock);
	r = vcpu->mmu.page_fault(vcpu, cr2, error_code);
	if (r < 0)
		goto out;

	if (!r) {
		r = 1;
		goto out;
	}

1389 1390 1391 1392
	r = mmu_topup_memory_caches(vcpu);
	if (r)
		goto out;

1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413
	er = emulate_instruction(vcpu, vcpu->run, cr2, error_code, 0);
	mutex_unlock(&vcpu->kvm->lock);

	switch (er) {
	case EMULATE_DONE:
		return 1;
	case EMULATE_DO_MMIO:
		++vcpu->stat.mmio_exits;
		return 0;
	case EMULATE_FAIL:
		kvm_report_emulation_failure(vcpu, "pagetable");
		return 1;
	default:
		BUG();
	}
out:
	mutex_unlock(&vcpu->kvm->lock);
	return r;
}
EXPORT_SYMBOL_GPL(kvm_mmu_page_fault);

A
Avi Kivity 已提交
1414 1415
static void free_mmu_pages(struct kvm_vcpu *vcpu)
{
1416
	struct kvm_mmu_page *sp;
A
Avi Kivity 已提交
1417

1418
	while (!list_empty(&vcpu->kvm->active_mmu_pages)) {
1419 1420 1421
		sp = container_of(vcpu->kvm->active_mmu_pages.next,
				  struct kvm_mmu_page, link);
		kvm_mmu_zap_page(vcpu->kvm, sp);
1422
	}
1423
	free_page((unsigned long)vcpu->mmu.pae_root);
A
Avi Kivity 已提交
1424 1425 1426 1427
}

static int alloc_mmu_pages(struct kvm_vcpu *vcpu)
{
1428
	struct page *page;
A
Avi Kivity 已提交
1429 1430 1431 1432
	int i;

	ASSERT(vcpu);

1433 1434 1435 1436
	if (vcpu->kvm->n_requested_mmu_pages)
		vcpu->kvm->n_free_mmu_pages = vcpu->kvm->n_requested_mmu_pages;
	else
		vcpu->kvm->n_free_mmu_pages = vcpu->kvm->n_alloc_mmu_pages;
1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448
	/*
	 * When emulating 32-bit mode, cr3 is only 32 bits even on x86_64.
	 * Therefore we need to allocate shadow page tables in the first
	 * 4GB of memory, which happens to fit the DMA32 zone.
	 */
	page = alloc_page(GFP_KERNEL | __GFP_DMA32);
	if (!page)
		goto error_1;
	vcpu->mmu.pae_root = page_address(page);
	for (i = 0; i < 4; ++i)
		vcpu->mmu.pae_root[i] = INVALID_PAGE;

A
Avi Kivity 已提交
1449 1450 1451 1452 1453 1454 1455
	return 0;

error_1:
	free_mmu_pages(vcpu);
	return -ENOMEM;
}

1456
int kvm_mmu_create(struct kvm_vcpu *vcpu)
A
Avi Kivity 已提交
1457 1458 1459 1460
{
	ASSERT(vcpu);
	ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));

1461 1462
	return alloc_mmu_pages(vcpu);
}
A
Avi Kivity 已提交
1463

1464 1465 1466 1467
int kvm_mmu_setup(struct kvm_vcpu *vcpu)
{
	ASSERT(vcpu);
	ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));
1468

1469
	return init_kvm_mmu(vcpu);
A
Avi Kivity 已提交
1470 1471 1472 1473 1474 1475 1476 1477
}

void kvm_mmu_destroy(struct kvm_vcpu *vcpu)
{
	ASSERT(vcpu);

	destroy_kvm_mmu(vcpu);
	free_mmu_pages(vcpu);
1478
	mmu_free_memory_caches(vcpu);
A
Avi Kivity 已提交
1479 1480
}

1481
void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot)
A
Avi Kivity 已提交
1482
{
1483
	struct kvm_mmu_page *sp;
A
Avi Kivity 已提交
1484

1485
	list_for_each_entry(sp, &kvm->active_mmu_pages, link) {
A
Avi Kivity 已提交
1486 1487 1488
		int i;
		u64 *pt;

1489
		if (!test_bit(slot, &sp->slot_bitmap))
A
Avi Kivity 已提交
1490 1491
			continue;

1492
		pt = sp->spt;
A
Avi Kivity 已提交
1493 1494
		for (i = 0; i < PT64_ENT_PER_PAGE; ++i)
			/* avoid RMW */
1495
			if (pt[i] & PT_WRITABLE_MASK)
A
Avi Kivity 已提交
1496 1497 1498
				pt[i] &= ~PT_WRITABLE_MASK;
	}
}
1499

1500
void kvm_mmu_zap_all(struct kvm *kvm)
D
Dor Laor 已提交
1501
{
1502
	struct kvm_mmu_page *sp, *node;
D
Dor Laor 已提交
1503

1504 1505
	list_for_each_entry_safe(sp, node, &kvm->active_mmu_pages, link)
		kvm_mmu_zap_page(kvm, sp);
D
Dor Laor 已提交
1506

1507
	kvm_flush_remote_tlbs(kvm);
D
Dor Laor 已提交
1508 1509
}

1510 1511 1512 1513 1514 1515
void kvm_mmu_module_exit(void)
{
	if (pte_chain_cache)
		kmem_cache_destroy(pte_chain_cache);
	if (rmap_desc_cache)
		kmem_cache_destroy(rmap_desc_cache);
1516 1517
	if (mmu_page_header_cache)
		kmem_cache_destroy(mmu_page_header_cache);
1518 1519 1520 1521 1522 1523
}

int kvm_mmu_module_init(void)
{
	pte_chain_cache = kmem_cache_create("kvm_pte_chain",
					    sizeof(struct kvm_pte_chain),
1524
					    0, 0, NULL);
1525 1526 1527 1528
	if (!pte_chain_cache)
		goto nomem;
	rmap_desc_cache = kmem_cache_create("kvm_rmap_desc",
					    sizeof(struct kvm_rmap_desc),
1529
					    0, 0, NULL);
1530 1531 1532
	if (!rmap_desc_cache)
		goto nomem;

1533 1534
	mmu_page_header_cache = kmem_cache_create("kvm_mmu_page_header",
						  sizeof(struct kvm_mmu_page),
1535
						  0, 0, NULL);
1536 1537 1538
	if (!mmu_page_header_cache)
		goto nomem;

1539 1540 1541 1542 1543 1544 1545
	return 0;

nomem:
	kvm_mmu_module_exit();
	return -ENOMEM;
}

1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564
/*
 * Caculate mmu pages needed for kvm.
 */
unsigned int kvm_mmu_calculate_mmu_pages(struct kvm *kvm)
{
	int i;
	unsigned int nr_mmu_pages;
	unsigned int  nr_pages = 0;

	for (i = 0; i < kvm->nmemslots; i++)
		nr_pages += kvm->memslots[i].npages;

	nr_mmu_pages = nr_pages * KVM_PERMILLE_MMU_PAGES / 1000;
	nr_mmu_pages = max(nr_mmu_pages,
			(unsigned int) KVM_MIN_ALLOC_MMU_PAGES);

	return nr_mmu_pages;
}

1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586
#ifdef AUDIT

static const char *audit_msg;

static gva_t canonicalize(gva_t gva)
{
#ifdef CONFIG_X86_64
	gva = (long long)(gva << 16) >> 16;
#endif
	return gva;
}

static void audit_mappings_page(struct kvm_vcpu *vcpu, u64 page_pte,
				gva_t va, int level)
{
	u64 *pt = __va(page_pte & PT64_BASE_ADDR_MASK);
	int i;
	gva_t va_delta = 1ul << (PAGE_SHIFT + 9 * (level - 1));

	for (i = 0; i < PT64_ENT_PER_PAGE; ++i, va += va_delta) {
		u64 ent = pt[i];

1587
		if (ent == shadow_trap_nonpresent_pte)
1588 1589 1590
			continue;

		va = canonicalize(va);
1591 1592 1593 1594 1595 1596 1597
		if (level > 1) {
			if (ent == shadow_notrap_nonpresent_pte)
				printk(KERN_ERR "audit: (%s) nontrapping pte"
				       " in nonleaf level: levels %d gva %lx"
				       " level %d pte %llx\n", audit_msg,
				       vcpu->mmu.root_level, va, level, ent);

1598
			audit_mappings_page(vcpu, ent, va, level - 1);
1599
		} else {
1600
			gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, va);
A
Avi Kivity 已提交
1601 1602
			struct page *page = gpa_to_page(vcpu, gpa);
			hpa_t hpa = page_to_phys(page);
1603

1604
			if (is_shadow_present_pte(ent)
1605
			    && (ent & PT64_BASE_ADDR_MASK) != hpa)
1606 1607
				printk(KERN_ERR "xx audit error: (%s) levels %d"
				       " gva %lx gpa %llx hpa %llx ent %llx %d\n",
1608
				       audit_msg, vcpu->mmu.root_level,
M
Mike Day 已提交
1609 1610
				       va, gpa, hpa, ent,
				       is_shadow_present_pte(ent));
1611 1612 1613 1614
			else if (ent == shadow_notrap_nonpresent_pte
				 && !is_error_hpa(hpa))
				printk(KERN_ERR "audit: (%s) notrap shadow,"
				       " valid guest gva %lx\n", audit_msg, va);
1615
			kvm_release_page_clean(page);
1616

1617 1618 1619 1620 1621 1622
		}
	}
}

static void audit_mappings(struct kvm_vcpu *vcpu)
{
1623
	unsigned i;
1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645

	if (vcpu->mmu.root_level == 4)
		audit_mappings_page(vcpu, vcpu->mmu.root_hpa, 0, 4);
	else
		for (i = 0; i < 4; ++i)
			if (vcpu->mmu.pae_root[i] & PT_PRESENT_MASK)
				audit_mappings_page(vcpu,
						    vcpu->mmu.pae_root[i],
						    i << 30,
						    2);
}

static int count_rmaps(struct kvm_vcpu *vcpu)
{
	int nmaps = 0;
	int i, j, k;

	for (i = 0; i < KVM_MEMORY_SLOTS; ++i) {
		struct kvm_memory_slot *m = &vcpu->kvm->memslots[i];
		struct kvm_rmap_desc *d;

		for (j = 0; j < m->npages; ++j) {
1646
			unsigned long *rmapp = &m->rmap[j];
1647

1648
			if (!*rmapp)
1649
				continue;
1650
			if (!(*rmapp & 1)) {
1651 1652 1653
				++nmaps;
				continue;
			}
1654
			d = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670
			while (d) {
				for (k = 0; k < RMAP_EXT; ++k)
					if (d->shadow_ptes[k])
						++nmaps;
					else
						break;
				d = d->more;
			}
		}
	}
	return nmaps;
}

static int count_writable_mappings(struct kvm_vcpu *vcpu)
{
	int nmaps = 0;
1671
	struct kvm_mmu_page *sp;
1672 1673
	int i;

1674 1675
	list_for_each_entry(sp, &vcpu->kvm->active_mmu_pages, link) {
		u64 *pt = sp->spt;
1676

1677
		if (sp->role.level != PT_PAGE_TABLE_LEVEL)
1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704
			continue;

		for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
			u64 ent = pt[i];

			if (!(ent & PT_PRESENT_MASK))
				continue;
			if (!(ent & PT_WRITABLE_MASK))
				continue;
			++nmaps;
		}
	}
	return nmaps;
}

static void audit_rmap(struct kvm_vcpu *vcpu)
{
	int n_rmap = count_rmaps(vcpu);
	int n_actual = count_writable_mappings(vcpu);

	if (n_rmap != n_actual)
		printk(KERN_ERR "%s: (%s) rmap %d actual %d\n",
		       __FUNCTION__, audit_msg, n_rmap, n_actual);
}

static void audit_write_protection(struct kvm_vcpu *vcpu)
{
1705
	struct kvm_mmu_page *sp;
1706 1707 1708
	struct kvm_memory_slot *slot;
	unsigned long *rmapp;
	gfn_t gfn;
1709

1710 1711
	list_for_each_entry(sp, &vcpu->kvm->active_mmu_pages, link) {
		if (sp->role.metaphysical)
1712 1713
			continue;

1714 1715
		slot = gfn_to_memslot(vcpu->kvm, sp->gfn);
		gfn = unalias_gfn(vcpu->kvm, sp->gfn);
1716 1717
		rmapp = &slot->rmap[gfn - slot->base_gfn];
		if (*rmapp)
1718 1719
			printk(KERN_ERR "%s: (%s) shadow page has writable"
			       " mappings: gfn %lx role %x\n",
1720 1721
			       __FUNCTION__, audit_msg, sp->gfn,
			       sp->role.word);
1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737
	}
}

static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg)
{
	int olddbg = dbg;

	dbg = 0;
	audit_msg = msg;
	audit_rmap(vcpu);
	audit_write_protection(vcpu);
	audit_mappings(vcpu);
	dbg = olddbg;
}

#endif