git.oblomov.eu Git - linux-2.6/blob - drivers/kvm/mmu.c

   1 /*
   2  * Kernel-based Virtual Machine driver for Linux
   3  *
   4  * This module enables machines with Intel VT-x extensions to run virtual
   5  * machines without emulation or binary translation.
   6  *
   7  * MMU support
   8  *
   9  * Copyright (C) 2006 Qumranet, Inc.
  10  *
  11  * Authors:
  12  *   Yaniv Kamay  <yaniv@qumranet.com>
  13  *   Avi Kivity   <avi@qumranet.com>
  14  *
  15  * This work is licensed under the terms of the GNU GPL, version 2.  See
  16  * the COPYING file in the top-level directory.
  17  *
  18  */
  19
  20 #include "vmx.h"
  21 #include "kvm.h"
  22 #include "x86.h"
  23
  24 #include <linux/types.h>
  25 #include <linux/string.h>
  26 #include <linux/mm.h>
  27 #include <linux/highmem.h>
  28 #include <linux/module.h>
  29
  30 #include <asm/page.h>
  31 #include <asm/cmpxchg.h>
  32
  33 #undef MMU_DEBUG
  34
  35 #undef AUDIT
  36
  37 #ifdef AUDIT
  38 static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg);
  39 #else
  40 static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg) {}
  41 #endif
  42
  43 #ifdef MMU_DEBUG
  44
  45 #define pgprintk(x...) do { if (dbg) printk(x); } while (0)
  46 #define rmap_printk(x...) do { if (dbg) printk(x); } while (0)
  47
  48 #else
  49
  50 #define pgprintk(x...) do { } while (0)
  51 #define rmap_printk(x...) do { } while (0)
  52
  53 #endif
  54
  55 #if defined(MMU_DEBUG) || defined(AUDIT)
  56 static int dbg = 1;
  57 #endif
  58
  59 #ifndef MMU_DEBUG
  60 #define ASSERT(x) do { } while (0)
  61 #else
  62 #define ASSERT(x)                                                       \
  63         if (!(x)) {                                                     \
  64                 printk(KERN_WARNING "assertion failed %s:%d: %s\n",     \
  65                        __FILE__, __LINE__, #x);                         \
  66         }
  67 #endif
  68
  69 #define PT64_PT_BITS 9
  70 #define PT64_ENT_PER_PAGE (1 << PT64_PT_BITS)
  71 #define PT32_PT_BITS 10
  72 #define PT32_ENT_PER_PAGE (1 << PT32_PT_BITS)
  73
  74 #define PT_WRITABLE_SHIFT 1
  75
  76 #define PT_PRESENT_MASK (1ULL << 0)
  77 #define PT_WRITABLE_MASK (1ULL << PT_WRITABLE_SHIFT)
  78 #define PT_USER_MASK (1ULL << 2)
  79 #define PT_PWT_MASK (1ULL << 3)
  80 #define PT_PCD_MASK (1ULL << 4)
  81 #define PT_ACCESSED_MASK (1ULL << 5)
  82 #define PT_DIRTY_MASK (1ULL << 6)
  83 #define PT_PAGE_SIZE_MASK (1ULL << 7)
  84 #define PT_PAT_MASK (1ULL << 7)
  85 #define PT_GLOBAL_MASK (1ULL << 8)
  86 #define PT64_NX_MASK (1ULL << 63)
  87
  88 #define PT_PAT_SHIFT 7
  89 #define PT_DIR_PAT_SHIFT 12
  90 #define PT_DIR_PAT_MASK (1ULL << PT_DIR_PAT_SHIFT)
  91
  92 #define PT32_DIR_PSE36_SIZE 4
  93 #define PT32_DIR_PSE36_SHIFT 13
  94 #define PT32_DIR_PSE36_MASK \
  95         (((1ULL << PT32_DIR_PSE36_SIZE) - 1) << PT32_DIR_PSE36_SHIFT)
  96
  97
  98 #define PT_FIRST_AVAIL_BITS_SHIFT 9
  99 #define PT64_SECOND_AVAIL_BITS_SHIFT 52
 100
 101 #define PT_SHADOW_IO_MARK (1ULL << PT_FIRST_AVAIL_BITS_SHIFT)
 102
 103 #define VALID_PAGE(x) ((x) != INVALID_PAGE)
 104
 105 #define PT64_LEVEL_BITS 9
 106
 107 #define PT64_LEVEL_SHIFT(level) \
 108                 (PAGE_SHIFT + (level - 1) * PT64_LEVEL_BITS)
 109
 110 #define PT64_LEVEL_MASK(level) \
 111                 (((1ULL << PT64_LEVEL_BITS) - 1) << PT64_LEVEL_SHIFT(level))
 112
 113 #define PT64_INDEX(address, level)\
 114         (((address) >> PT64_LEVEL_SHIFT(level)) & ((1 << PT64_LEVEL_BITS) - 1))
 115
 116
 117 #define PT32_LEVEL_BITS 10
 118
 119 #define PT32_LEVEL_SHIFT(level) \
 120                 (PAGE_SHIFT + (level - 1) * PT32_LEVEL_BITS)
 121
 122 #define PT32_LEVEL_MASK(level) \
 123                 (((1ULL << PT32_LEVEL_BITS) - 1) << PT32_LEVEL_SHIFT(level))
 124
 125 #define PT32_INDEX(address, level)\
 126         (((address) >> PT32_LEVEL_SHIFT(level)) & ((1 << PT32_LEVEL_BITS) - 1))
 127
 128
 129 #define PT64_BASE_ADDR_MASK (((1ULL << 52) - 1) & ~(u64)(PAGE_SIZE-1))
 130 #define PT64_DIR_BASE_ADDR_MASK \
 131         (PT64_BASE_ADDR_MASK & ~((1ULL << (PAGE_SHIFT + PT64_LEVEL_BITS)) - 1))
 132
 133 #define PT32_BASE_ADDR_MASK PAGE_MASK
 134 #define PT32_DIR_BASE_ADDR_MASK \
 135         (PAGE_MASK & ~((1ULL << (PAGE_SHIFT + PT32_LEVEL_BITS)) - 1))
 136
 137 #define PT64_PERM_MASK (PT_PRESENT_MASK | PT_WRITABLE_MASK | PT_USER_MASK \
 138                         | PT64_NX_MASK)
 139
 140 #define PFERR_PRESENT_MASK (1U << 0)
 141 #define PFERR_WRITE_MASK (1U << 1)
 142 #define PFERR_USER_MASK (1U << 2)
 143 #define PFERR_FETCH_MASK (1U << 4)
 144
 145 #define PT64_ROOT_LEVEL 4
 146 #define PT32_ROOT_LEVEL 2
 147 #define PT32E_ROOT_LEVEL 3
 148
 149 #define PT_DIRECTORY_LEVEL 2
 150 #define PT_PAGE_TABLE_LEVEL 1
 151
 152 #define RMAP_EXT 4
 153
 154 struct kvm_rmap_desc {
 155         u64 *shadow_ptes[RMAP_EXT];
 156         struct kvm_rmap_desc *more;
 157 };
 158
 159 static struct kmem_cache *pte_chain_cache;
 160 static struct kmem_cache *rmap_desc_cache;
 161 static struct kmem_cache *mmu_page_header_cache;
 162
 163 static u64 __read_mostly shadow_trap_nonpresent_pte;
 164 static u64 __read_mostly shadow_notrap_nonpresent_pte;
 165
 166 void kvm_mmu_set_nonpresent_ptes(u64 trap_pte, u64 notrap_pte)
 167 {
 168         shadow_trap_nonpresent_pte = trap_pte;
 169         shadow_notrap_nonpresent_pte = notrap_pte;
 170 }
 171 EXPORT_SYMBOL_GPL(kvm_mmu_set_nonpresent_ptes);
 172
 173 static int is_write_protection(struct kvm_vcpu *vcpu)
 174 {
 175         return vcpu->cr0 & X86_CR0_WP;
 176 }
 177
 178 static int is_cpuid_PSE36(void)
 179 {
 180         return 1;
 181 }
 182
 183 static int is_nx(struct kvm_vcpu *vcpu)
 184 {
 185         return vcpu->shadow_efer & EFER_NX;
 186 }
 187
 188 static int is_present_pte(unsigned long pte)
 189 {
 190         return pte & PT_PRESENT_MASK;
 191 }
 192
 193 static int is_shadow_present_pte(u64 pte)
 194 {
 195         pte &= ~PT_SHADOW_IO_MARK;
 196         return pte != shadow_trap_nonpresent_pte
 197                 && pte != shadow_notrap_nonpresent_pte;
 198 }
 199
 200 static int is_writeble_pte(unsigned long pte)
 201 {
 202         return pte & PT_WRITABLE_MASK;
 203 }
 204
 205 static int is_dirty_pte(unsigned long pte)
 206 {
 207         return pte & PT_DIRTY_MASK;
 208 }
 209
 210 static int is_io_pte(unsigned long pte)
 211 {
 212         return pte & PT_SHADOW_IO_MARK;
 213 }
 214
 215 static int is_rmap_pte(u64 pte)
 216 {
 217         return pte != shadow_trap_nonpresent_pte
 218                 && pte != shadow_notrap_nonpresent_pte;
 219 }
 220
 221 static void set_shadow_pte(u64 *sptep, u64 spte)
 222 {
 223 #ifdef CONFIG_X86_64
 224         set_64bit((unsigned long *)sptep, spte);
 225 #else
 226         set_64bit((unsigned long long *)sptep, spte);
 227 #endif
 228 }
 229
 230 static int mmu_topup_memory_cache(struct kvm_mmu_memory_cache *cache,
 231                                   struct kmem_cache *base_cache, int min)
 232 {
 233         void *obj;
 234
 235         if (cache->nobjs >= min)
 236                 return 0;
 237         while (cache->nobjs < ARRAY_SIZE(cache->objects)) {
 238                 obj = kmem_cache_zalloc(base_cache, GFP_KERNEL);
 239                 if (!obj)
 240                         return -ENOMEM;
 241                 cache->objects[cache->nobjs++] = obj;
 242         }
 243         return 0;
 244 }
 245
 246 static void mmu_free_memory_cache(struct kvm_mmu_memory_cache *mc)
 247 {
 248         while (mc->nobjs)
 249                 kfree(mc->objects[--mc->nobjs]);
 250 }
 251
 252 static int mmu_topup_memory_cache_page(struct kvm_mmu_memory_cache *cache,
 253                                        int min)
 254 {
 255         struct page *page;
 256
 257         if (cache->nobjs >= min)
 258                 return 0;
 259         while (cache->nobjs < ARRAY_SIZE(cache->objects)) {
 260                 page = alloc_page(GFP_KERNEL);
 261                 if (!page)
 262                         return -ENOMEM;
 263                 set_page_private(page, 0);
 264                 cache->objects[cache->nobjs++] = page_address(page);
 265         }
 266         return 0;
 267 }
 268
 269 static void mmu_free_memory_cache_page(struct kvm_mmu_memory_cache *mc)
 270 {
 271         while (mc->nobjs)
 272                 free_page((unsigned long)mc->objects[--mc->nobjs]);
 273 }
 274
 275 static int mmu_topup_memory_caches(struct kvm_vcpu *vcpu)
 276 {
 277         int r;
 278
 279         kvm_mmu_free_some_pages(vcpu);
 280         r = mmu_topup_memory_cache(&vcpu->mmu_pte_chain_cache,
 281                                    pte_chain_cache, 4);
 282         if (r)
 283                 goto out;
 284         r = mmu_topup_memory_cache(&vcpu->mmu_rmap_desc_cache,
 285                                    rmap_desc_cache, 1);
 286         if (r)
 287                 goto out;
 288         r = mmu_topup_memory_cache_page(&vcpu->mmu_page_cache, 8);
 289         if (r)
 290                 goto out;
 291         r = mmu_topup_memory_cache(&vcpu->mmu_page_header_cache,
 292                                    mmu_page_header_cache, 4);
 293 out:
 294         return r;
 295 }
 296
 297 static void mmu_free_memory_caches(struct kvm_vcpu *vcpu)
 298 {
 299         mmu_free_memory_cache(&vcpu->mmu_pte_chain_cache);
 300         mmu_free_memory_cache(&vcpu->mmu_rmap_desc_cache);
 301         mmu_free_memory_cache_page(&vcpu->mmu_page_cache);
 302         mmu_free_memory_cache(&vcpu->mmu_page_header_cache);
 303 }
 304
 305 static void *mmu_memory_cache_alloc(struct kvm_mmu_memory_cache *mc,
 306                                     size_t size)
 307 {
 308         void *p;
 309
 310         BUG_ON(!mc->nobjs);
 311         p = mc->objects[--mc->nobjs];
 312         memset(p, 0, size);
 313         return p;
 314 }
 315
 316 static struct kvm_pte_chain *mmu_alloc_pte_chain(struct kvm_vcpu *vcpu)
 317 {
 318         return mmu_memory_cache_alloc(&vcpu->mmu_pte_chain_cache,
 319                                       sizeof(struct kvm_pte_chain));
 320 }
 321
 322 static void mmu_free_pte_chain(struct kvm_pte_chain *pc)
 323 {
 324         kfree(pc);
 325 }
 326
 327 static struct kvm_rmap_desc *mmu_alloc_rmap_desc(struct kvm_vcpu *vcpu)
 328 {
 329         return mmu_memory_cache_alloc(&vcpu->mmu_rmap_desc_cache,
 330                                       sizeof(struct kvm_rmap_desc));
 331 }
 332
 333 static void mmu_free_rmap_desc(struct kvm_rmap_desc *rd)
 334 {
 335         kfree(rd);
 336 }
 337
 338 /*
 339  * Take gfn and return the reverse mapping to it.
 340  * Note: gfn must be unaliased before this function get called
 341  */
 342
 343 static unsigned long *gfn_to_rmap(struct kvm *kvm, gfn_t gfn)
 344 {
 345         struct kvm_memory_slot *slot;
 346
 347         slot = gfn_to_memslot(kvm, gfn);
 348         return &slot->rmap[gfn - slot->base_gfn];
 349 }
 350
 351 /*
 352  * Reverse mapping data structures:
 353  *
 354  * If rmapp bit zero is zero, then rmapp point to the shadw page table entry
 355  * that points to page_address(page).
 356  *
 357  * If rmapp bit zero is one, (then rmap & ~1) points to a struct kvm_rmap_desc
 358  * containing more mappings.
 359  */
 360 static void rmap_add(struct kvm_vcpu *vcpu, u64 *spte, gfn_t gfn)
 361 {
 362         struct kvm_mmu_page *page;
 363         struct kvm_rmap_desc *desc;
 364         unsigned long *rmapp;
 365         int i;
 366
 367         if (!is_rmap_pte(*spte))
 368                 return;
 369         gfn = unalias_gfn(vcpu->kvm, gfn);
 370         page = page_header(__pa(spte));
 371         page->gfns[spte - page->spt] = gfn;
 372         rmapp = gfn_to_rmap(vcpu->kvm, gfn);
 373         if (!*rmapp) {
 374                 rmap_printk("rmap_add: %p %llx 0->1\n", spte, *spte);
 375                 *rmapp = (unsigned long)spte;
 376         } else if (!(*rmapp & 1)) {
 377                 rmap_printk("rmap_add: %p %llx 1->many\n", spte, *spte);
 378                 desc = mmu_alloc_rmap_desc(vcpu);
 379                 desc->shadow_ptes[0] = (u64 *)*rmapp;
 380                 desc->shadow_ptes[1] = spte;
 381                 *rmapp = (unsigned long)desc | 1;
 382         } else {
 383                 rmap_printk("rmap_add: %p %llx many->many\n", spte, *spte);
 384                 desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
 385                 while (desc->shadow_ptes[RMAP_EXT-1] && desc->more)
 386                         desc = desc->more;
 387                 if (desc->shadow_ptes[RMAP_EXT-1]) {
 388                         desc->more = mmu_alloc_rmap_desc(vcpu);
 389                         desc = desc->more;
 390                 }
 391                 for (i = 0; desc->shadow_ptes[i]; ++i)
 392                         ;
 393                 desc->shadow_ptes[i] = spte;
 394         }
 395 }
 396
 397 static void rmap_desc_remove_entry(unsigned long *rmapp,
 398                                    struct kvm_rmap_desc *desc,
 399                                    int i,
 400                                    struct kvm_rmap_desc *prev_desc)
 401 {
 402         int j;
 403
 404         for (j = RMAP_EXT - 1; !desc->shadow_ptes[j] && j > i; --j)
 405                 ;
 406         desc->shadow_ptes[i] = desc->shadow_ptes[j];
 407         desc->shadow_ptes[j] = NULL;
 408         if (j != 0)
 409                 return;
 410         if (!prev_desc && !desc->more)
 411                 *rmapp = (unsigned long)desc->shadow_ptes[0];
 412         else
 413                 if (prev_desc)
 414                         prev_desc->more = desc->more;
 415                 else
 416                         *rmapp = (unsigned long)desc->more | 1;
 417         mmu_free_rmap_desc(desc);
 418 }
 419
 420 static void rmap_remove(struct kvm *kvm, u64 *spte)
 421 {
 422         struct kvm_rmap_desc *desc;
 423         struct kvm_rmap_desc *prev_desc;
 424         struct kvm_mmu_page *page;
 425         struct page *release_page;
 426         unsigned long *rmapp;
 427         int i;
 428
 429         if (!is_rmap_pte(*spte))
 430                 return;
 431         page = page_header(__pa(spte));
 432         release_page = pfn_to_page((*spte & PT64_BASE_ADDR_MASK) >> PAGE_SHIFT);
 433         if (is_writeble_pte(*spte))
 434                 kvm_release_page_dirty(release_page);
 435         else
 436                 kvm_release_page_clean(release_page);
 437         rmapp = gfn_to_rmap(kvm, page->gfns[spte - page->spt]);
 438         if (!*rmapp) {
 439                 printk(KERN_ERR "rmap_remove: %p %llx 0->BUG\n", spte, *spte);
 440                 BUG();
 441         } else if (!(*rmapp & 1)) {
 442                 rmap_printk("rmap_remove:  %p %llx 1->0\n", spte, *spte);
 443                 if ((u64 *)*rmapp != spte) {
 444                         printk(KERN_ERR "rmap_remove:  %p %llx 1->BUG\n",
 445                                spte, *spte);
 446                         BUG();
 447                 }
 448                 *rmapp = 0;
 449         } else {
 450                 rmap_printk("rmap_remove:  %p %llx many->many\n", spte, *spte);
 451                 desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
 452                 prev_desc = NULL;
 453                 while (desc) {
 454                         for (i = 0; i < RMAP_EXT && desc->shadow_ptes[i]; ++i)
 455                                 if (desc->shadow_ptes[i] == spte) {
 456                                         rmap_desc_remove_entry(rmapp,
 457                                                                desc, i,
 458                                                                prev_desc);
 459                                         return;
 460                                 }
 461                         prev_desc = desc;
 462                         desc = desc->more;
 463                 }
 464                 BUG();
 465         }
 466 }
 467
 468 static u64 *rmap_next(struct kvm *kvm, unsigned long *rmapp, u64 *spte)
 469 {
 470         struct kvm_rmap_desc *desc;
 471         struct kvm_rmap_desc *prev_desc;
 472         u64 *prev_spte;
 473         int i;
 474
 475         if (!*rmapp)
 476                 return NULL;
 477         else if (!(*rmapp & 1)) {
 478                 if (!spte)
 479                         return (u64 *)*rmapp;
 480                 return NULL;
 481         }
 482         desc = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
 483         prev_desc = NULL;
 484         prev_spte = NULL;
 485         while (desc) {
 486                 for (i = 0; i < RMAP_EXT && desc->shadow_ptes[i]; ++i) {
 487                         if (prev_spte == spte)
 488                                 return desc->shadow_ptes[i];
 489                         prev_spte = desc->shadow_ptes[i];
 490                 }
 491                 desc = desc->more;
 492         }
 493         return NULL;
 494 }
 495
 496 static void rmap_write_protect(struct kvm *kvm, u64 gfn)
 497 {
 498         unsigned long *rmapp;
 499         u64 *spte;
 500
 501         gfn = unalias_gfn(kvm, gfn);
 502         rmapp = gfn_to_rmap(kvm, gfn);
 503
 504         spte = rmap_next(kvm, rmapp, NULL);
 505         while (spte) {
 506                 BUG_ON(!spte);
 507                 BUG_ON(!(*spte & PT_PRESENT_MASK));
 508                 rmap_printk("rmap_write_protect: spte %p %llx\n", spte, *spte);
 509                 if (is_writeble_pte(*spte))
 510                         set_shadow_pte(spte, *spte & ~PT_WRITABLE_MASK);
 511                 kvm_flush_remote_tlbs(kvm);
 512                 spte = rmap_next(kvm, rmapp, spte);
 513         }
 514 }
 515
 516 #ifdef MMU_DEBUG
 517 static int is_empty_shadow_page(u64 *spt)
 518 {
 519         u64 *pos;
 520         u64 *end;
 521
 522         for (pos = spt, end = pos + PAGE_SIZE / sizeof(u64); pos != end; pos++)
 523                 if ((*pos & ~PT_SHADOW_IO_MARK) != shadow_trap_nonpresent_pte) {
 524                         printk(KERN_ERR "%s: %p %llx\n", __FUNCTION__,
 525                                pos, *pos);
 526                         return 0;
 527                 }
 528         return 1;
 529 }
 530 #endif
 531
 532 static void kvm_mmu_free_page(struct kvm *kvm,
 533                               struct kvm_mmu_page *page_head)
 534 {
 535         ASSERT(is_empty_shadow_page(page_head->spt));
 536         list_del(&page_head->link);
 537         __free_page(virt_to_page(page_head->spt));
 538         __free_page(virt_to_page(page_head->gfns));
 539         kfree(page_head);
 540         ++kvm->n_free_mmu_pages;
 541 }
 542
 543 static unsigned kvm_page_table_hashfn(gfn_t gfn)
 544 {
 545         return gfn;
 546 }
 547
 548 static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
 549                                                u64 *parent_pte)
 550 {
 551         struct kvm_mmu_page *page;
 552
 553         if (!vcpu->kvm->n_free_mmu_pages)
 554                 return NULL;
 555
 556         page = mmu_memory_cache_alloc(&vcpu->mmu_page_header_cache,
 557                                       sizeof *page);
 558         page->spt = mmu_memory_cache_alloc(&vcpu->mmu_page_cache, PAGE_SIZE);
 559         page->gfns = mmu_memory_cache_alloc(&vcpu->mmu_page_cache, PAGE_SIZE);
 560         set_page_private(virt_to_page(page->spt), (unsigned long)page);
 561         list_add(&page->link, &vcpu->kvm->active_mmu_pages);
 562         ASSERT(is_empty_shadow_page(page->spt));
 563         page->slot_bitmap = 0;
 564         page->multimapped = 0;
 565         page->parent_pte = parent_pte;
 566         --vcpu->kvm->n_free_mmu_pages;
 567         return page;
 568 }
 569
 570 static void mmu_page_add_parent_pte(struct kvm_vcpu *vcpu,
 571                                     struct kvm_mmu_page *page, u64 *parent_pte)
 572 {
 573         struct kvm_pte_chain *pte_chain;
 574         struct hlist_node *node;
 575         int i;
 576
 577         if (!parent_pte)
 578                 return;
 579         if (!page->multimapped) {
 580                 u64 *old = page->parent_pte;
 581
 582                 if (!old) {
 583                         page->parent_pte = parent_pte;
 584                         return;
 585                 }
 586                 page->multimapped = 1;
 587                 pte_chain = mmu_alloc_pte_chain(vcpu);
 588                 INIT_HLIST_HEAD(&page->parent_ptes);
 589                 hlist_add_head(&pte_chain->link, &page->parent_ptes);
 590                 pte_chain->parent_ptes[0] = old;
 591         }
 592         hlist_for_each_entry(pte_chain, node, &page->parent_ptes, link) {
 593                 if (pte_chain->parent_ptes[NR_PTE_CHAIN_ENTRIES-1])
 594                         continue;
 595                 for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i)
 596                         if (!pte_chain->parent_ptes[i]) {
 597                                 pte_chain->parent_ptes[i] = parent_pte;
 598                                 return;
 599                         }
 600         }
 601         pte_chain = mmu_alloc_pte_chain(vcpu);
 602         BUG_ON(!pte_chain);
 603         hlist_add_head(&pte_chain->link, &page->parent_ptes);
 604         pte_chain->parent_ptes[0] = parent_pte;
 605 }
 606
 607 static void mmu_page_remove_parent_pte(struct kvm_mmu_page *page,
 608                                        u64 *parent_pte)
 609 {
 610         struct kvm_pte_chain *pte_chain;
 611         struct hlist_node *node;
 612         int i;
 613
 614         if (!page->multimapped) {
 615                 BUG_ON(page->parent_pte != parent_pte);
 616                 page->parent_pte = NULL;
 617                 return;
 618         }
 619         hlist_for_each_entry(pte_chain, node, &page->parent_ptes, link)
 620                 for (i = 0; i < NR_PTE_CHAIN_ENTRIES; ++i) {
 621                         if (!pte_chain->parent_ptes[i])
 622                                 break;
 623                         if (pte_chain->parent_ptes[i] != parent_pte)
 624                                 continue;
 625                         while (i + 1 < NR_PTE_CHAIN_ENTRIES
 626                                 && pte_chain->parent_ptes[i + 1]) {
 627                                 pte_chain->parent_ptes[i]
 628                                         = pte_chain->parent_ptes[i + 1];
 629                                 ++i;
 630                         }
 631                         pte_chain->parent_ptes[i] = NULL;
 632                         if (i == 0) {
 633                                 hlist_del(&pte_chain->link);
 634                                 mmu_free_pte_chain(pte_chain);
 635                                 if (hlist_empty(&page->parent_ptes)) {
 636                                         page->multimapped = 0;
 637                                         page->parent_pte = NULL;
 638                                 }
 639                         }
 640                         return;
 641                 }
 642         BUG();
 643 }
 644
 645 static struct kvm_mmu_page *kvm_mmu_lookup_page(struct kvm *kvm,
 646                                                 gfn_t gfn)
 647 {
 648         unsigned index;
 649         struct hlist_head *bucket;
 650         struct kvm_mmu_page *page;
 651         struct hlist_node *node;
 652
 653         pgprintk("%s: looking for gfn %lx\n", __FUNCTION__, gfn);
 654         index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
 655         bucket = &kvm->mmu_page_hash[index];
 656         hlist_for_each_entry(page, node, bucket, hash_link)
 657                 if (page->gfn == gfn && !page->role.metaphysical) {
 658                         pgprintk("%s: found role %x\n",
 659                                  __FUNCTION__, page->role.word);
 660                         return page;
 661                 }
 662         return NULL;
 663 }
 664
 665 static struct kvm_mmu_page *kvm_mmu_get_page(struct kvm_vcpu *vcpu,
 666                                              gfn_t gfn,
 667                                              gva_t gaddr,
 668                                              unsigned level,
 669                                              int metaphysical,
 670                                              unsigned hugepage_access,
 671                                              u64 *parent_pte)
 672 {
 673         union kvm_mmu_page_role role;
 674         unsigned index;
 675         unsigned quadrant;
 676         struct hlist_head *bucket;
 677         struct kvm_mmu_page *page;
 678         struct hlist_node *node;
 679
 680         role.word = 0;
 681         role.glevels = vcpu->mmu.root_level;
 682         role.level = level;
 683         role.metaphysical = metaphysical;
 684         role.hugepage_access = hugepage_access;
 685         if (vcpu->mmu.root_level <= PT32_ROOT_LEVEL) {
 686                 quadrant = gaddr >> (PAGE_SHIFT + (PT64_PT_BITS * level));
 687                 quadrant &= (1 << ((PT32_PT_BITS - PT64_PT_BITS) * level)) - 1;
 688                 role.quadrant = quadrant;
 689         }
 690         pgprintk("%s: looking gfn %lx role %x\n", __FUNCTION__,
 691                  gfn, role.word);
 692         index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
 693         bucket = &vcpu->kvm->mmu_page_hash[index];
 694         hlist_for_each_entry(page, node, bucket, hash_link)
 695                 if (page->gfn == gfn && page->role.word == role.word) {
 696                         mmu_page_add_parent_pte(vcpu, page, parent_pte);
 697                         pgprintk("%s: found\n", __FUNCTION__);
 698                         return page;
 699                 }
 700         page = kvm_mmu_alloc_page(vcpu, parent_pte);
 701         if (!page)
 702                 return page;
 703         pgprintk("%s: adding gfn %lx role %x\n", __FUNCTION__, gfn, role.word);
 704         page->gfn = gfn;
 705         page->role = role;
 706         hlist_add_head(&page->hash_link, bucket);
 707         vcpu->mmu.prefetch_page(vcpu, page);
 708         if (!metaphysical)
 709                 rmap_write_protect(vcpu->kvm, gfn);
 710         return page;
 711 }
 712
 713 static void kvm_mmu_page_unlink_children(struct kvm *kvm,
 714                                          struct kvm_mmu_page *page)
 715 {
 716         unsigned i;
 717         u64 *pt;
 718         u64 ent;
 719
 720         pt = page->spt;
 721
 722         if (page->role.level == PT_PAGE_TABLE_LEVEL) {
 723                 for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
 724                         if (is_shadow_present_pte(pt[i]))
 725                                 rmap_remove(kvm, &pt[i]);
 726                         pt[i] = shadow_trap_nonpresent_pte;
 727                 }
 728                 kvm_flush_remote_tlbs(kvm);
 729                 return;
 730         }
 731
 732         for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
 733                 ent = pt[i];
 734
 735                 pt[i] = shadow_trap_nonpresent_pte;
 736                 if (!is_shadow_present_pte(ent))
 737                         continue;
 738                 ent &= PT64_BASE_ADDR_MASK;
 739                 mmu_page_remove_parent_pte(page_header(ent), &pt[i]);
 740         }
 741         kvm_flush_remote_tlbs(kvm);
 742 }
 743
 744 static void kvm_mmu_put_page(struct kvm_mmu_page *page,
 745                              u64 *parent_pte)
 746 {
 747         mmu_page_remove_parent_pte(page, parent_pte);
 748 }
 749
 750 static void kvm_mmu_reset_last_pte_updated(struct kvm *kvm)
 751 {
 752         int i;
 753
 754         for (i = 0; i < KVM_MAX_VCPUS; ++i)
 755                 if (kvm->vcpus[i])
 756                         kvm->vcpus[i]->last_pte_updated = NULL;
 757 }
 758
 759 static void kvm_mmu_zap_page(struct kvm *kvm,
 760                              struct kvm_mmu_page *page)
 761 {
 762         u64 *parent_pte;
 763
 764         ++kvm->stat.mmu_shadow_zapped;
 765         while (page->multimapped || page->parent_pte) {
 766                 if (!page->multimapped)
 767                         parent_pte = page->parent_pte;
 768                 else {
 769                         struct kvm_pte_chain *chain;
 770
 771                         chain = container_of(page->parent_ptes.first,
 772                                              struct kvm_pte_chain, link);
 773                         parent_pte = chain->parent_ptes[0];
 774                 }
 775                 BUG_ON(!parent_pte);
 776                 kvm_mmu_put_page(page, parent_pte);
 777                 set_shadow_pte(parent_pte, shadow_trap_nonpresent_pte);
 778         }
 779         kvm_mmu_page_unlink_children(kvm, page);
 780         if (!page->root_count) {
 781                 hlist_del(&page->hash_link);
 782                 kvm_mmu_free_page(kvm, page);
 783         } else
 784                 list_move(&page->link, &kvm->active_mmu_pages);
 785         kvm_mmu_reset_last_pte_updated(kvm);
 786 }
 787
 788 /*
 789  * Changing the number of mmu pages allocated to the vm
 790  * Note: if kvm_nr_mmu_pages is too small, you will get dead lock
 791  */
 792 void kvm_mmu_change_mmu_pages(struct kvm *kvm, unsigned int kvm_nr_mmu_pages)
 793 {
 794         /*
 795          * If we set the number of mmu pages to be smaller be than the
 796          * number of actived pages , we must to free some mmu pages before we
 797          * change the value
 798          */
 799
 800         if ((kvm->n_alloc_mmu_pages - kvm->n_free_mmu_pages) >
 801             kvm_nr_mmu_pages) {
 802                 int n_used_mmu_pages = kvm->n_alloc_mmu_pages
 803                                        - kvm->n_free_mmu_pages;
 804
 805                 while (n_used_mmu_pages > kvm_nr_mmu_pages) {
 806                         struct kvm_mmu_page *page;
 807
 808                         page = container_of(kvm->active_mmu_pages.prev,
 809                                             struct kvm_mmu_page, link);
 810                         kvm_mmu_zap_page(kvm, page);
 811                         n_used_mmu_pages--;
 812                 }
 813                 kvm->n_free_mmu_pages = 0;
 814         }
 815         else
 816                 kvm->n_free_mmu_pages += kvm_nr_mmu_pages
 817                                          - kvm->n_alloc_mmu_pages;
 818
 819         kvm->n_alloc_mmu_pages = kvm_nr_mmu_pages;
 820 }
 821
 822 static int kvm_mmu_unprotect_page(struct kvm *kvm, gfn_t gfn)
 823 {
 824         unsigned index;
 825         struct hlist_head *bucket;
 826         struct kvm_mmu_page *page;
 827         struct hlist_node *node, *n;
 828         int r;
 829
 830         pgprintk("%s: looking for gfn %lx\n", __FUNCTION__, gfn);
 831         r = 0;
 832         index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
 833         bucket = &kvm->mmu_page_hash[index];
 834         hlist_for_each_entry_safe(page, node, n, bucket, hash_link)
 835                 if (page->gfn == gfn && !page->role.metaphysical) {
 836                         pgprintk("%s: gfn %lx role %x\n", __FUNCTION__, gfn,
 837                                  page->role.word);
 838                         kvm_mmu_zap_page(kvm, page);
 839                         r = 1;
 840                 }
 841         return r;
 842 }
 843
 844 static void mmu_unshadow(struct kvm *kvm, gfn_t gfn)
 845 {
 846         struct kvm_mmu_page *page;
 847
 848         while ((page = kvm_mmu_lookup_page(kvm, gfn)) != NULL) {
 849                 pgprintk("%s: zap %lx %x\n",
 850                          __FUNCTION__, gfn, page->role.word);
 851                 kvm_mmu_zap_page(kvm, page);
 852         }
 853 }
 854
 855 static void page_header_update_slot(struct kvm *kvm, void *pte, gpa_t gpa)
 856 {
 857         int slot = memslot_id(kvm, gfn_to_memslot(kvm, gpa >> PAGE_SHIFT));
 858         struct kvm_mmu_page *page_head = page_header(__pa(pte));
 859
 860         __set_bit(slot, &page_head->slot_bitmap);
 861 }
 862
 863 hpa_t gpa_to_hpa(struct kvm *kvm, gpa_t gpa)
 864 {
 865         struct page *page;
 866         hpa_t hpa;
 867
 868         ASSERT((gpa & HPA_ERR_MASK) == 0);
 869         page = gfn_to_page(kvm, gpa >> PAGE_SHIFT);
 870         hpa = ((hpa_t)page_to_pfn(page) << PAGE_SHIFT) | (gpa & (PAGE_SIZE-1));
 871         if (is_error_page(page))
 872                 return hpa | HPA_ERR_MASK;
 873         return hpa;
 874 }
 875
 876 hpa_t gva_to_hpa(struct kvm_vcpu *vcpu, gva_t gva)
 877 {
 878         gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, gva);
 879
 880         if (gpa == UNMAPPED_GVA)
 881                 return UNMAPPED_GVA;
 882         return gpa_to_hpa(vcpu->kvm, gpa);
 883 }
 884
 885 struct page *gva_to_page(struct kvm_vcpu *vcpu, gva_t gva)
 886 {
 887         gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, gva);
 888
 889         if (gpa == UNMAPPED_GVA)
 890                 return NULL;
 891         return pfn_to_page(gpa_to_hpa(vcpu->kvm, gpa) >> PAGE_SHIFT);
 892 }
 893
 894 static void nonpaging_new_cr3(struct kvm_vcpu *vcpu)
 895 {
 896 }
 897
 898 static int nonpaging_map(struct kvm_vcpu *vcpu, gva_t v, hpa_t p)
 899 {
 900         int level = PT32E_ROOT_LEVEL;
 901         hpa_t table_addr = vcpu->mmu.root_hpa;
 902         struct page *page;
 903
 904         page = pfn_to_page(p >> PAGE_SHIFT);
 905         for (; ; level--) {
 906                 u32 index = PT64_INDEX(v, level);
 907                 u64 *table;
 908                 u64 pte;
 909
 910                 ASSERT(VALID_PAGE(table_addr));
 911                 table = __va(table_addr);
 912
 913                 if (level == 1) {
 914                         int was_rmapped;
 915
 916                         pte = table[index];
 917                         was_rmapped = is_rmap_pte(pte);
 918                         if (is_shadow_present_pte(pte) && is_writeble_pte(pte)) {
 919                                 kvm_release_page_clean(page);
 920                                 return 0;
 921                         }
 922                         mark_page_dirty(vcpu->kvm, v >> PAGE_SHIFT);
 923                         page_header_update_slot(vcpu->kvm, table, v);
 924                         table[index] = p | PT_PRESENT_MASK | PT_WRITABLE_MASK |
 925                                                                 PT_USER_MASK;
 926                         if (!was_rmapped)
 927                                 rmap_add(vcpu, &table[index], v >> PAGE_SHIFT);
 928                         else
 929                                 kvm_release_page_clean(page);
 930
 931                         return 0;
 932                 }
 933
 934                 if (table[index] == shadow_trap_nonpresent_pte) {
 935                         struct kvm_mmu_page *new_table;
 936                         gfn_t pseudo_gfn;
 937
 938                         pseudo_gfn = (v & PT64_DIR_BASE_ADDR_MASK)
 939                                 >> PAGE_SHIFT;
 940                         new_table = kvm_mmu_get_page(vcpu, pseudo_gfn,
 941                                                      v, level - 1,
 942                                                      1, 3, &table[index]);
 943                         if (!new_table) {
 944                                 pgprintk("nonpaging_map: ENOMEM\n");
 945                                 kvm_release_page_clean(page);
 946                                 return -ENOMEM;
 947                         }
 948
 949                         table[index] = __pa(new_table->spt) | PT_PRESENT_MASK
 950                                 | PT_WRITABLE_MASK | PT_USER_MASK;
 951                 }
 952                 table_addr = table[index] & PT64_BASE_ADDR_MASK;
 953         }
 954 }
 955
 956 static void nonpaging_prefetch_page(struct kvm_vcpu *vcpu,
 957                                     struct kvm_mmu_page *sp)
 958 {
 959         int i;
 960
 961         for (i = 0; i < PT64_ENT_PER_PAGE; ++i)
 962                 sp->spt[i] = shadow_trap_nonpresent_pte;
 963 }
 964
 965 static void mmu_free_roots(struct kvm_vcpu *vcpu)
 966 {
 967         int i;
 968         struct kvm_mmu_page *page;
 969
 970         if (!VALID_PAGE(vcpu->mmu.root_hpa))
 971                 return;
 972 #ifdef CONFIG_X86_64
 973         if (vcpu->mmu.shadow_root_level == PT64_ROOT_LEVEL) {
 974                 hpa_t root = vcpu->mmu.root_hpa;
 975
 976                 page = page_header(root);
 977                 --page->root_count;
 978                 vcpu->mmu.root_hpa = INVALID_PAGE;
 979                 return;
 980         }
 981 #endif
 982         for (i = 0; i < 4; ++i) {
 983                 hpa_t root = vcpu->mmu.pae_root[i];
 984
 985                 if (root) {
 986                         root &= PT64_BASE_ADDR_MASK;
 987                         page = page_header(root);
 988                         --page->root_count;
 989                 }
 990                 vcpu->mmu.pae_root[i] = INVALID_PAGE;
 991         }
 992         vcpu->mmu.root_hpa = INVALID_PAGE;
 993 }
 994
 995 static void mmu_alloc_roots(struct kvm_vcpu *vcpu)
 996 {
 997         int i;
 998         gfn_t root_gfn;
 999         struct kvm_mmu_page *page;
1000
1001         root_gfn = vcpu->cr3 >> PAGE_SHIFT;
1002
1003 #ifdef CONFIG_X86_64
1004         if (vcpu->mmu.shadow_root_level == PT64_ROOT_LEVEL) {
1005                 hpa_t root = vcpu->mmu.root_hpa;
1006
1007                 ASSERT(!VALID_PAGE(root));
1008                 page = kvm_mmu_get_page(vcpu, root_gfn, 0,
1009                                         PT64_ROOT_LEVEL, 0, 0, NULL);
1010                 root = __pa(page->spt);
1011                 ++page->root_count;
1012                 vcpu->mmu.root_hpa = root;
1013                 return;
1014         }
1015 #endif
1016         for (i = 0; i < 4; ++i) {
1017                 hpa_t root = vcpu->mmu.pae_root[i];
1018
1019                 ASSERT(!VALID_PAGE(root));
1020                 if (vcpu->mmu.root_level == PT32E_ROOT_LEVEL) {
1021                         if (!is_present_pte(vcpu->pdptrs[i])) {
1022                                 vcpu->mmu.pae_root[i] = 0;
1023                                 continue;
1024                         }
1025                         root_gfn = vcpu->pdptrs[i] >> PAGE_SHIFT;
1026                 } else if (vcpu->mmu.root_level == 0)
1027                         root_gfn = 0;
1028                 page = kvm_mmu_get_page(vcpu, root_gfn, i << 30,
1029                                         PT32_ROOT_LEVEL, !is_paging(vcpu),
1030                                         0, NULL);
1031                 root = __pa(page->spt);
1032                 ++page->root_count;
1033                 vcpu->mmu.pae_root[i] = root | PT_PRESENT_MASK;
1034         }
1035         vcpu->mmu.root_hpa = __pa(vcpu->mmu.pae_root);
1036 }
1037
1038 static gpa_t nonpaging_gva_to_gpa(struct kvm_vcpu *vcpu, gva_t vaddr)
1039 {
1040         return vaddr;
1041 }
1042
1043 static int nonpaging_page_fault(struct kvm_vcpu *vcpu, gva_t gva,
1044                                u32 error_code)
1045 {
1046         gpa_t addr = gva;
1047         hpa_t paddr;
1048         int r;
1049
1050         r = mmu_topup_memory_caches(vcpu);
1051         if (r)
1052                 return r;
1053
1054         ASSERT(vcpu);
1055         ASSERT(VALID_PAGE(vcpu->mmu.root_hpa));
1056
1057
1058         paddr = gpa_to_hpa(vcpu->kvm, addr & PT64_BASE_ADDR_MASK);
1059
1060         if (is_error_hpa(paddr)) {
1061                 kvm_release_page_clean(pfn_to_page((paddr & PT64_BASE_ADDR_MASK)
1062                                        >> PAGE_SHIFT));
1063                 return 1;
1064         }
1065
1066         return nonpaging_map(vcpu, addr & PAGE_MASK, paddr);
1067 }
1068
1069 static void nonpaging_free(struct kvm_vcpu *vcpu)
1070 {
1071         mmu_free_roots(vcpu);
1072 }
1073
1074 static int nonpaging_init_context(struct kvm_vcpu *vcpu)
1075 {
1076         struct kvm_mmu *context = &vcpu->mmu;
1077
1078         context->new_cr3 = nonpaging_new_cr3;
1079         context->page_fault = nonpaging_page_fault;
1080         context->gva_to_gpa = nonpaging_gva_to_gpa;
1081         context->free = nonpaging_free;
1082         context->prefetch_page = nonpaging_prefetch_page;
1083         context->root_level = 0;
1084         context->shadow_root_level = PT32E_ROOT_LEVEL;
1085         context->root_hpa = INVALID_PAGE;
1086         return 0;
1087 }
1088
1089 void kvm_mmu_flush_tlb(struct kvm_vcpu *vcpu)
1090 {
1091         ++vcpu->stat.tlb_flush;
1092         kvm_x86_ops->tlb_flush(vcpu);
1093 }
1094
1095 static void paging_new_cr3(struct kvm_vcpu *vcpu)
1096 {
1097         pgprintk("%s: cr3 %lx\n", __FUNCTION__, vcpu->cr3);
1098         mmu_free_roots(vcpu);
1099 }
1100
1101 static void inject_page_fault(struct kvm_vcpu *vcpu,
1102                               u64 addr,
1103                               u32 err_code)
1104 {
1105         kvm_x86_ops->inject_page_fault(vcpu, addr, err_code);
1106 }
1107
1108 static void paging_free(struct kvm_vcpu *vcpu)
1109 {
1110         nonpaging_free(vcpu);
1111 }
1112
1113 #define PTTYPE 64
1114 #include "paging_tmpl.h"
1115 #undef PTTYPE
1116
1117 #define PTTYPE 32
1118 #include "paging_tmpl.h"
1119 #undef PTTYPE
1120
1121 static int paging64_init_context_common(struct kvm_vcpu *vcpu, int level)
1122 {
1123         struct kvm_mmu *context = &vcpu->mmu;
1124
1125         ASSERT(is_pae(vcpu));
1126         context->new_cr3 = paging_new_cr3;
1127         context->page_fault = paging64_page_fault;
1128         context->gva_to_gpa = paging64_gva_to_gpa;
1129         context->prefetch_page = paging64_prefetch_page;
1130         context->free = paging_free;
1131         context->root_level = level;
1132         context->shadow_root_level = level;
1133         context->root_hpa = INVALID_PAGE;
1134         return 0;
1135 }
1136
1137 static int paging64_init_context(struct kvm_vcpu *vcpu)
1138 {
1139         return paging64_init_context_common(vcpu, PT64_ROOT_LEVEL);
1140 }
1141
1142 static int paging32_init_context(struct kvm_vcpu *vcpu)
1143 {
1144         struct kvm_mmu *context = &vcpu->mmu;
1145
1146         context->new_cr3 = paging_new_cr3;
1147         context->page_fault = paging32_page_fault;
1148         context->gva_to_gpa = paging32_gva_to_gpa;
1149         context->free = paging_free;
1150         context->prefetch_page = paging32_prefetch_page;
1151         context->root_level = PT32_ROOT_LEVEL;
1152         context->shadow_root_level = PT32E_ROOT_LEVEL;
1153         context->root_hpa = INVALID_PAGE;
1154         return 0;
1155 }
1156
1157 static int paging32E_init_context(struct kvm_vcpu *vcpu)
1158 {
1159         return paging64_init_context_common(vcpu, PT32E_ROOT_LEVEL);
1160 }
1161
1162 static int init_kvm_mmu(struct kvm_vcpu *vcpu)
1163 {
1164         ASSERT(vcpu);
1165         ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));
1166
1167         if (!is_paging(vcpu))
1168                 return nonpaging_init_context(vcpu);
1169         else if (is_long_mode(vcpu))
1170                 return paging64_init_context(vcpu);
1171         else if (is_pae(vcpu))
1172                 return paging32E_init_context(vcpu);
1173         else
1174                 return paging32_init_context(vcpu);
1175 }
1176
1177 static void destroy_kvm_mmu(struct kvm_vcpu *vcpu)
1178 {
1179         ASSERT(vcpu);
1180         if (VALID_PAGE(vcpu->mmu.root_hpa)) {
1181                 vcpu->mmu.free(vcpu);
1182                 vcpu->mmu.root_hpa = INVALID_PAGE;
1183         }
1184 }
1185
1186 int kvm_mmu_reset_context(struct kvm_vcpu *vcpu)
1187 {
1188         destroy_kvm_mmu(vcpu);
1189         return init_kvm_mmu(vcpu);
1190 }
1191 EXPORT_SYMBOL_GPL(kvm_mmu_reset_context);
1192
1193 int kvm_mmu_load(struct kvm_vcpu *vcpu)
1194 {
1195         int r;
1196
1197         mutex_lock(&vcpu->kvm->lock);
1198         r = mmu_topup_memory_caches(vcpu);
1199         if (r)
1200                 goto out;
1201         mmu_alloc_roots(vcpu);
1202         kvm_x86_ops->set_cr3(vcpu, vcpu->mmu.root_hpa);
1203         kvm_mmu_flush_tlb(vcpu);
1204 out:
1205         mutex_unlock(&vcpu->kvm->lock);
1206         return r;
1207 }
1208 EXPORT_SYMBOL_GPL(kvm_mmu_load);
1209
1210 void kvm_mmu_unload(struct kvm_vcpu *vcpu)
1211 {
1212         mmu_free_roots(vcpu);
1213 }
1214
1215 static void mmu_pte_write_zap_pte(struct kvm_vcpu *vcpu,
1216                                   struct kvm_mmu_page *page,
1217                                   u64 *spte)
1218 {
1219         u64 pte;
1220         struct kvm_mmu_page *child;
1221
1222         pte = *spte;
1223         if (is_shadow_present_pte(pte)) {
1224                 if (page->role.level == PT_PAGE_TABLE_LEVEL)
1225                         rmap_remove(vcpu->kvm, spte);
1226                 else {
1227                         child = page_header(pte & PT64_BASE_ADDR_MASK);
1228                         mmu_page_remove_parent_pte(child, spte);
1229                 }
1230         }
1231         set_shadow_pte(spte, shadow_trap_nonpresent_pte);
1232 }
1233
1234 static void mmu_pte_write_new_pte(struct kvm_vcpu *vcpu,
1235                                   struct kvm_mmu_page *page,
1236                                   u64 *spte,
1237                                   const void *new, int bytes,
1238                                   int offset_in_pte)
1239 {
1240         if (page->role.level != PT_PAGE_TABLE_LEVEL) {
1241                 ++vcpu->kvm->stat.mmu_pde_zapped;
1242                 return;
1243         }
1244
1245         ++vcpu->kvm->stat.mmu_pte_updated;
1246         if (page->role.glevels == PT32_ROOT_LEVEL)
1247                 paging32_update_pte(vcpu, page, spte, new, bytes,
1248                                     offset_in_pte);
1249         else
1250                 paging64_update_pte(vcpu, page, spte, new, bytes,
1251                                     offset_in_pte);
1252 }
1253
1254 static bool need_remote_flush(u64 old, u64 new)
1255 {
1256         if (!is_shadow_present_pte(old))
1257                 return false;
1258         if (!is_shadow_present_pte(new))
1259                 return true;
1260         if ((old ^ new) & PT64_BASE_ADDR_MASK)
1261                 return true;
1262         old ^= PT64_NX_MASK;
1263         new ^= PT64_NX_MASK;
1264         return (old & ~new & PT64_PERM_MASK) != 0;
1265 }
1266
1267 static void mmu_pte_write_flush_tlb(struct kvm_vcpu *vcpu, u64 old, u64 new)
1268 {
1269         if (need_remote_flush(old, new))
1270                 kvm_flush_remote_tlbs(vcpu->kvm);
1271         else
1272                 kvm_mmu_flush_tlb(vcpu);
1273 }
1274
1275 static bool last_updated_pte_accessed(struct kvm_vcpu *vcpu)
1276 {
1277         u64 *spte = vcpu->last_pte_updated;
1278
1279         return !!(spte && (*spte & PT_ACCESSED_MASK));
1280 }
1281
1282 void kvm_mmu_pte_write(struct kvm_vcpu *vcpu, gpa_t gpa,
1283                        const u8 *new, int bytes)
1284 {
1285         gfn_t gfn = gpa >> PAGE_SHIFT;
1286         struct kvm_mmu_page *page;
1287         struct hlist_node *node, *n;
1288         struct hlist_head *bucket;
1289         unsigned index;
1290         u64 entry;
1291         u64 *spte;
1292         unsigned offset = offset_in_page(gpa);
1293         unsigned pte_size;
1294         unsigned page_offset;
1295         unsigned misaligned;
1296         unsigned quadrant;
1297         int level;
1298         int flooded = 0;
1299         int npte;
1300
1301         pgprintk("%s: gpa %llx bytes %d\n", __FUNCTION__, gpa, bytes);
1302         ++vcpu->kvm->stat.mmu_pte_write;
1303         kvm_mmu_audit(vcpu, "pre pte write");
1304         if (gfn == vcpu->last_pt_write_gfn
1305             && !last_updated_pte_accessed(vcpu)) {
1306                 ++vcpu->last_pt_write_count;
1307                 if (vcpu->last_pt_write_count >= 3)
1308                         flooded = 1;
1309         } else {
1310                 vcpu->last_pt_write_gfn = gfn;
1311                 vcpu->last_pt_write_count = 1;
1312                 vcpu->last_pte_updated = NULL;
1313         }
1314         index = kvm_page_table_hashfn(gfn) % KVM_NUM_MMU_PAGES;
1315         bucket = &vcpu->kvm->mmu_page_hash[index];
1316         hlist_for_each_entry_safe(page, node, n, bucket, hash_link) {
1317                 if (page->gfn != gfn || page->role.metaphysical)
1318                         continue;
1319                 pte_size = page->role.glevels == PT32_ROOT_LEVEL ? 4 : 8;
1320                 misaligned = (offset ^ (offset + bytes - 1)) & ~(pte_size - 1);
1321                 misaligned |= bytes < 4;
1322                 if (misaligned || flooded) {
1323                         /*
1324                          * Misaligned accesses are too much trouble to fix
1325                          * up; also, they usually indicate a page is not used
1326                          * as a page table.
1327                          *
1328                          * If we're seeing too many writes to a page,
1329                          * it may no longer be a page table, or we may be
1330                          * forking, in which case it is better to unmap the
1331                          * page.
1332                          */
1333                         pgprintk("misaligned: gpa %llx bytes %d role %x\n",
1334                                  gpa, bytes, page->role.word);
1335                         kvm_mmu_zap_page(vcpu->kvm, page);
1336                         ++vcpu->kvm->stat.mmu_flooded;
1337                         continue;
1338                 }
1339                 page_offset = offset;
1340                 level = page->role.level;
1341                 npte = 1;
1342                 if (page->role.glevels == PT32_ROOT_LEVEL) {
1343                         page_offset <<= 1;      /* 32->64 */
1344                         /*
1345                          * A 32-bit pde maps 4MB while the shadow pdes map
1346                          * only 2MB.  So we need to double the offset again
1347                          * and zap two pdes instead of one.
1348                          */
1349                         if (level == PT32_ROOT_LEVEL) {
1350                                 page_offset &= ~7; /* kill rounding error */
1351                                 page_offset <<= 1;
1352                                 npte = 2;
1353                         }
1354                         quadrant = page_offset >> PAGE_SHIFT;
1355                         page_offset &= ~PAGE_MASK;
1356                         if (quadrant != page->role.quadrant)
1357                                 continue;
1358                 }
1359                 spte = &page->spt[page_offset / sizeof(*spte)];
1360                 while (npte--) {
1361                         entry = *spte;
1362                         mmu_pte_write_zap_pte(vcpu, page, spte);
1363                         mmu_pte_write_new_pte(vcpu, page, spte, new, bytes,
1364                                               page_offset & (pte_size - 1));
1365                         mmu_pte_write_flush_tlb(vcpu, entry, *spte);
1366                         ++spte;
1367                 }
1368         }
1369         kvm_mmu_audit(vcpu, "post pte write");
1370 }
1371
1372 int kvm_mmu_unprotect_page_virt(struct kvm_vcpu *vcpu, gva_t gva)
1373 {
1374         gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, gva);
1375
1376         return kvm_mmu_unprotect_page(vcpu->kvm, gpa >> PAGE_SHIFT);
1377 }
1378
1379 void __kvm_mmu_free_some_pages(struct kvm_vcpu *vcpu)
1380 {
1381         while (vcpu->kvm->n_free_mmu_pages < KVM_REFILL_PAGES) {
1382                 struct kvm_mmu_page *page;
1383
1384                 page = container_of(vcpu->kvm->active_mmu_pages.prev,
1385                                     struct kvm_mmu_page, link);
1386                 kvm_mmu_zap_page(vcpu->kvm, page);
1387                 ++vcpu->kvm->stat.mmu_recycled;
1388         }
1389 }
1390
1391 int kvm_mmu_page_fault(struct kvm_vcpu *vcpu, gva_t cr2, u32 error_code)
1392 {
1393         int r;
1394         enum emulation_result er;
1395
1396         mutex_lock(&vcpu->kvm->lock);
1397         r = vcpu->mmu.page_fault(vcpu, cr2, error_code);
1398         if (r < 0)
1399                 goto out;
1400
1401         if (!r) {
1402                 r = 1;
1403                 goto out;
1404         }
1405
1406         r = mmu_topup_memory_caches(vcpu);
1407         if (r)
1408                 goto out;
1409
1410         er = emulate_instruction(vcpu, vcpu->run, cr2, error_code, 0);
1411         mutex_unlock(&vcpu->kvm->lock);
1412
1413         switch (er) {
1414         case EMULATE_DONE:
1415                 return 1;
1416         case EMULATE_DO_MMIO:
1417                 ++vcpu->stat.mmio_exits;
1418                 return 0;
1419         case EMULATE_FAIL:
1420                 kvm_report_emulation_failure(vcpu, "pagetable");
1421                 return 1;
1422         default:
1423                 BUG();
1424         }
1425 out:
1426         mutex_unlock(&vcpu->kvm->lock);
1427         return r;
1428 }
1429 EXPORT_SYMBOL_GPL(kvm_mmu_page_fault);
1430
1431 static void free_mmu_pages(struct kvm_vcpu *vcpu)
1432 {
1433         struct kvm_mmu_page *page;
1434
1435         while (!list_empty(&vcpu->kvm->active_mmu_pages)) {
1436                 page = container_of(vcpu->kvm->active_mmu_pages.next,
1437                                     struct kvm_mmu_page, link);
1438                 kvm_mmu_zap_page(vcpu->kvm, page);
1439         }
1440         free_page((unsigned long)vcpu->mmu.pae_root);
1441 }
1442
1443 static int alloc_mmu_pages(struct kvm_vcpu *vcpu)
1444 {
1445         struct page *page;
1446         int i;
1447
1448         ASSERT(vcpu);
1449
1450         if (vcpu->kvm->n_requested_mmu_pages)
1451                 vcpu->kvm->n_free_mmu_pages = vcpu->kvm->n_requested_mmu_pages;
1452         else
1453                 vcpu->kvm->n_free_mmu_pages = vcpu->kvm->n_alloc_mmu_pages;
1454         /*
1455          * When emulating 32-bit mode, cr3 is only 32 bits even on x86_64.
1456          * Therefore we need to allocate shadow page tables in the first
1457          * 4GB of memory, which happens to fit the DMA32 zone.
1458          */
1459         page = alloc_page(GFP_KERNEL | __GFP_DMA32);
1460         if (!page)
1461                 goto error_1;
1462         vcpu->mmu.pae_root = page_address(page);
1463         for (i = 0; i < 4; ++i)
1464                 vcpu->mmu.pae_root[i] = INVALID_PAGE;
1465
1466         return 0;
1467
1468 error_1:
1469         free_mmu_pages(vcpu);
1470         return -ENOMEM;
1471 }
1472
1473 int kvm_mmu_create(struct kvm_vcpu *vcpu)
1474 {
1475         ASSERT(vcpu);
1476         ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));
1477
1478         return alloc_mmu_pages(vcpu);
1479 }
1480
1481 int kvm_mmu_setup(struct kvm_vcpu *vcpu)
1482 {
1483         ASSERT(vcpu);
1484         ASSERT(!VALID_PAGE(vcpu->mmu.root_hpa));
1485
1486         return init_kvm_mmu(vcpu);
1487 }
1488
1489 void kvm_mmu_destroy(struct kvm_vcpu *vcpu)
1490 {
1491         ASSERT(vcpu);
1492
1493         destroy_kvm_mmu(vcpu);
1494         free_mmu_pages(vcpu);
1495         mmu_free_memory_caches(vcpu);
1496 }
1497
1498 void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot)
1499 {
1500         struct kvm_mmu_page *page;
1501
1502         list_for_each_entry(page, &kvm->active_mmu_pages, link) {
1503                 int i;
1504                 u64 *pt;
1505
1506                 if (!test_bit(slot, &page->slot_bitmap))
1507                         continue;
1508
1509                 pt = page->spt;
1510                 for (i = 0; i < PT64_ENT_PER_PAGE; ++i)
1511                         /* avoid RMW */
1512                         if (pt[i] & PT_WRITABLE_MASK)
1513                                 pt[i] &= ~PT_WRITABLE_MASK;
1514         }
1515 }
1516
1517 void kvm_mmu_zap_all(struct kvm *kvm)
1518 {
1519         struct kvm_mmu_page *page, *node;
1520
1521         list_for_each_entry_safe(page, node, &kvm->active_mmu_pages, link)
1522                 kvm_mmu_zap_page(kvm, page);
1523
1524         kvm_flush_remote_tlbs(kvm);
1525 }
1526
1527 void kvm_mmu_module_exit(void)
1528 {
1529         if (pte_chain_cache)
1530                 kmem_cache_destroy(pte_chain_cache);
1531         if (rmap_desc_cache)
1532                 kmem_cache_destroy(rmap_desc_cache);
1533         if (mmu_page_header_cache)
1534                 kmem_cache_destroy(mmu_page_header_cache);
1535 }
1536
1537 int kvm_mmu_module_init(void)
1538 {
1539         pte_chain_cache = kmem_cache_create("kvm_pte_chain",
1540                                             sizeof(struct kvm_pte_chain),
1541                                             0, 0, NULL);
1542         if (!pte_chain_cache)
1543                 goto nomem;
1544         rmap_desc_cache = kmem_cache_create("kvm_rmap_desc",
1545                                             sizeof(struct kvm_rmap_desc),
1546                                             0, 0, NULL);
1547         if (!rmap_desc_cache)
1548                 goto nomem;
1549
1550         mmu_page_header_cache = kmem_cache_create("kvm_mmu_page_header",
1551                                                   sizeof(struct kvm_mmu_page),
1552                                                   0, 0, NULL);
1553         if (!mmu_page_header_cache)
1554                 goto nomem;
1555
1556         return 0;
1557
1558 nomem:
1559         kvm_mmu_module_exit();
1560         return -ENOMEM;
1561 }
1562
1563 /*
1564  * Caculate mmu pages needed for kvm.
1565  */
1566 unsigned int kvm_mmu_calculate_mmu_pages(struct kvm *kvm)
1567 {
1568         int i;
1569         unsigned int nr_mmu_pages;
1570         unsigned int  nr_pages = 0;
1571
1572         for (i = 0; i < kvm->nmemslots; i++)
1573                 nr_pages += kvm->memslots[i].npages;
1574
1575         nr_mmu_pages = nr_pages * KVM_PERMILLE_MMU_PAGES / 1000;
1576         nr_mmu_pages = max(nr_mmu_pages,
1577                         (unsigned int) KVM_MIN_ALLOC_MMU_PAGES);
1578
1579         return nr_mmu_pages;
1580 }
1581
1582 #ifdef AUDIT
1583
1584 static const char *audit_msg;
1585
1586 static gva_t canonicalize(gva_t gva)
1587 {
1588 #ifdef CONFIG_X86_64
1589         gva = (long long)(gva << 16) >> 16;
1590 #endif
1591         return gva;
1592 }
1593
1594 static void audit_mappings_page(struct kvm_vcpu *vcpu, u64 page_pte,
1595                                 gva_t va, int level)
1596 {
1597         u64 *pt = __va(page_pte & PT64_BASE_ADDR_MASK);
1598         int i;
1599         gva_t va_delta = 1ul << (PAGE_SHIFT + 9 * (level - 1));
1600
1601         for (i = 0; i < PT64_ENT_PER_PAGE; ++i, va += va_delta) {
1602                 u64 ent = pt[i];
1603
1604                 if (ent == shadow_trap_nonpresent_pte)
1605                         continue;
1606
1607                 va = canonicalize(va);
1608                 if (level > 1) {
1609                         if (ent == shadow_notrap_nonpresent_pte)
1610                                 printk(KERN_ERR "audit: (%s) nontrapping pte"
1611                                        " in nonleaf level: levels %d gva %lx"
1612                                        " level %d pte %llx\n", audit_msg,
1613                                        vcpu->mmu.root_level, va, level, ent);
1614
1615                         audit_mappings_page(vcpu, ent, va, level - 1);
1616                 } else {
1617                         gpa_t gpa = vcpu->mmu.gva_to_gpa(vcpu, va);
1618                         hpa_t hpa = gpa_to_hpa(vcpu, gpa);
1619                         struct page *page;
1620
1621                         if (is_shadow_present_pte(ent)
1622                             && (ent & PT64_BASE_ADDR_MASK) != hpa)
1623                                 printk(KERN_ERR "xx audit error: (%s) levels %d"
1624                                        " gva %lx gpa %llx hpa %llx ent %llx %d\n",
1625                                        audit_msg, vcpu->mmu.root_level,
1626                                        va, gpa, hpa, ent,
1627                                        is_shadow_present_pte(ent));
1628                         else if (ent == shadow_notrap_nonpresent_pte
1629                                  && !is_error_hpa(hpa))
1630                                 printk(KERN_ERR "audit: (%s) notrap shadow,"
1631                                        " valid guest gva %lx\n", audit_msg, va);
1632                         page = pfn_to_page((gpa & PT64_BASE_ADDR_MASK)
1633                                            >> PAGE_SHIFT);
1634                         kvm_release_page_clean(page);
1635
1636                 }
1637         }
1638 }
1639
1640 static void audit_mappings(struct kvm_vcpu *vcpu)
1641 {
1642         unsigned i;
1643
1644         if (vcpu->mmu.root_level == 4)
1645                 audit_mappings_page(vcpu, vcpu->mmu.root_hpa, 0, 4);
1646         else
1647                 for (i = 0; i < 4; ++i)
1648                         if (vcpu->mmu.pae_root[i] & PT_PRESENT_MASK)
1649                                 audit_mappings_page(vcpu,
1650                                                     vcpu->mmu.pae_root[i],
1651                                                     i << 30,
1652                                                     2);
1653 }
1654
1655 static int count_rmaps(struct kvm_vcpu *vcpu)
1656 {
1657         int nmaps = 0;
1658         int i, j, k;
1659
1660         for (i = 0; i < KVM_MEMORY_SLOTS; ++i) {
1661                 struct kvm_memory_slot *m = &vcpu->kvm->memslots[i];
1662                 struct kvm_rmap_desc *d;
1663
1664                 for (j = 0; j < m->npages; ++j) {
1665                         unsigned long *rmapp = &m->rmap[j];
1666
1667                         if (!*rmapp)
1668                                 continue;
1669                         if (!(*rmapp & 1)) {
1670                                 ++nmaps;
1671                                 continue;
1672                         }
1673                         d = (struct kvm_rmap_desc *)(*rmapp & ~1ul);
1674                         while (d) {
1675                                 for (k = 0; k < RMAP_EXT; ++k)
1676                                         if (d->shadow_ptes[k])
1677                                                 ++nmaps;
1678                                         else
1679                                                 break;
1680                                 d = d->more;
1681                         }
1682                 }
1683         }
1684         return nmaps;
1685 }
1686
1687 static int count_writable_mappings(struct kvm_vcpu *vcpu)
1688 {
1689         int nmaps = 0;
1690         struct kvm_mmu_page *page;
1691         int i;
1692
1693         list_for_each_entry(page, &vcpu->kvm->active_mmu_pages, link) {
1694                 u64 *pt = page->spt;
1695
1696                 if (page->role.level != PT_PAGE_TABLE_LEVEL)
1697                         continue;
1698
1699                 for (i = 0; i < PT64_ENT_PER_PAGE; ++i) {
1700                         u64 ent = pt[i];
1701
1702                         if (!(ent & PT_PRESENT_MASK))
1703                                 continue;
1704                         if (!(ent & PT_WRITABLE_MASK))
1705                                 continue;
1706                         ++nmaps;
1707                 }
1708         }
1709         return nmaps;
1710 }
1711
1712 static void audit_rmap(struct kvm_vcpu *vcpu)
1713 {
1714         int n_rmap = count_rmaps(vcpu);
1715         int n_actual = count_writable_mappings(vcpu);
1716
1717         if (n_rmap != n_actual)
1718                 printk(KERN_ERR "%s: (%s) rmap %d actual %d\n",
1719                        __FUNCTION__, audit_msg, n_rmap, n_actual);
1720 }
1721
1722 static void audit_write_protection(struct kvm_vcpu *vcpu)
1723 {
1724         struct kvm_mmu_page *page;
1725         struct kvm_memory_slot *slot;
1726         unsigned long *rmapp;
1727         gfn_t gfn;
1728
1729         list_for_each_entry(page, &vcpu->kvm->active_mmu_pages, link) {
1730                 if (page->role.metaphysical)
1731                         continue;
1732
1733                 slot = gfn_to_memslot(vcpu->kvm, page->gfn);
1734                 gfn = unalias_gfn(vcpu->kvm, page->gfn);
1735                 rmapp = &slot->rmap[gfn - slot->base_gfn];
1736                 if (*rmapp)
1737                         printk(KERN_ERR "%s: (%s) shadow page has writable"
1738                                " mappings: gfn %lx role %x\n",
1739                                __FUNCTION__, audit_msg, page->gfn,
1740                                page->role.word);
1741         }
1742 }
1743
1744 static void kvm_mmu_audit(struct kvm_vcpu *vcpu, const char *msg)
1745 {
1746         int olddbg = dbg;
1747
1748         dbg = 0;
1749         audit_msg = msg;
1750         audit_rmap(vcpu);
1751         audit_write_protection(vcpu);
1752         audit_mappings(vcpu);
1753         dbg = olddbg;
1754 }
1755
1756 #endif