iommu/exynos: Add callback for initializing devices from device tree
[sfrench/cifs-2.6.git] / Documentation / virtual / kvm / mmu.txt
1 The x86 kvm shadow mmu
2 ======================
3
4 The mmu (in arch/x86/kvm, files mmu.[ch] and paging_tmpl.h) is responsible
5 for presenting a standard x86 mmu to the guest, while translating guest
6 physical addresses to host physical addresses.
7
8 The mmu code attempts to satisfy the following requirements:
9
10 - correctness: the guest should not be able to determine that it is running
11                on an emulated mmu except for timing (we attempt to comply
12                with the specification, not emulate the characteristics of
13                a particular implementation such as tlb size)
14 - security:    the guest must not be able to touch host memory not assigned
15                to it
16 - performance: minimize the performance penalty imposed by the mmu
17 - scaling:     need to scale to large memory and large vcpu guests
18 - hardware:    support the full range of x86 virtualization hardware
19 - integration: Linux memory management code must be in control of guest memory
20                so that swapping, page migration, page merging, transparent
21                hugepages, and similar features work without change
22 - dirty tracking: report writes to guest memory to enable live migration
23                and framebuffer-based displays
24 - footprint:   keep the amount of pinned kernel memory low (most memory
25                should be shrinkable)
26 - reliability:  avoid multipage or GFP_ATOMIC allocations
27
28 Acronyms
29 ========
30
31 pfn   host page frame number
32 hpa   host physical address
33 hva   host virtual address
34 gfn   guest frame number
35 gpa   guest physical address
36 gva   guest virtual address
37 ngpa  nested guest physical address
38 ngva  nested guest virtual address
39 pte   page table entry (used also to refer generically to paging structure
40       entries)
41 gpte  guest pte (referring to gfns)
42 spte  shadow pte (referring to pfns)
43 tdp   two dimensional paging (vendor neutral term for NPT and EPT)
44
45 Virtual and real hardware supported
46 ===================================
47
48 The mmu supports first-generation mmu hardware, which allows an atomic switch
49 of the current paging mode and cr3 during guest entry, as well as
50 two-dimensional paging (AMD's NPT and Intel's EPT).  The emulated hardware
51 it exposes is the traditional 2/3/4 level x86 mmu, with support for global
52 pages, pae, pse, pse36, cr0.wp, and 1GB pages.  Work is in progress to support
53 exposing NPT capable hardware on NPT capable hosts.
54
55 Translation
56 ===========
57
58 The primary job of the mmu is to program the processor's mmu to translate
59 addresses for the guest.  Different translations are required at different
60 times:
61
62 - when guest paging is disabled, we translate guest physical addresses to
63   host physical addresses (gpa->hpa)
64 - when guest paging is enabled, we translate guest virtual addresses, to
65   guest physical addresses, to host physical addresses (gva->gpa->hpa)
66 - when the guest launches a guest of its own, we translate nested guest
67   virtual addresses, to nested guest physical addresses, to guest physical
68   addresses, to host physical addresses (ngva->ngpa->gpa->hpa)
69
70 The primary challenge is to encode between 1 and 3 translations into hardware
71 that support only 1 (traditional) and 2 (tdp) translations.  When the
72 number of required translations matches the hardware, the mmu operates in
73 direct mode; otherwise it operates in shadow mode (see below).
74
75 Memory
76 ======
77
78 Guest memory (gpa) is part of the user address space of the process that is
79 using kvm.  Userspace defines the translation between guest addresses and user
80 addresses (gpa->hva); note that two gpas may alias to the same hva, but not
81 vice versa.
82
83 These hvas may be backed using any method available to the host: anonymous
84 memory, file backed memory, and device memory.  Memory might be paged by the
85 host at any time.
86
87 Events
88 ======
89
90 The mmu is driven by events, some from the guest, some from the host.
91
92 Guest generated events:
93 - writes to control registers (especially cr3)
94 - invlpg/invlpga instruction execution
95 - access to missing or protected translations
96
97 Host generated events:
98 - changes in the gpa->hpa translation (either through gpa->hva changes or
99   through hva->hpa changes)
100 - memory pressure (the shrinker)
101
102 Shadow pages
103 ============
104
105 The principal data structure is the shadow page, 'struct kvm_mmu_page'.  A
106 shadow page contains 512 sptes, which can be either leaf or nonleaf sptes.  A
107 shadow page may contain a mix of leaf and nonleaf sptes.
108
109 A nonleaf spte allows the hardware mmu to reach the leaf pages and
110 is not related to a translation directly.  It points to other shadow pages.
111
112 A leaf spte corresponds to either one or two translations encoded into
113 one paging structure entry.  These are always the lowest level of the
114 translation stack, with optional higher level translations left to NPT/EPT.
115 Leaf ptes point at guest pages.
116
117 The following table shows translations encoded by leaf ptes, with higher-level
118 translations in parentheses:
119
120  Non-nested guests:
121   nonpaging:     gpa->hpa
122   paging:        gva->gpa->hpa
123   paging, tdp:   (gva->)gpa->hpa
124  Nested guests:
125   non-tdp:       ngva->gpa->hpa  (*)
126   tdp:           (ngva->)ngpa->gpa->hpa
127
128 (*) the guest hypervisor will encode the ngva->gpa translation into its page
129     tables if npt is not present
130
131 Shadow pages contain the following information:
132   role.level:
133     The level in the shadow paging hierarchy that this shadow page belongs to.
134     1=4k sptes, 2=2M sptes, 3=1G sptes, etc.
135   role.direct:
136     If set, leaf sptes reachable from this page are for a linear range.
137     Examples include real mode translation, large guest pages backed by small
138     host pages, and gpa->hpa translations when NPT or EPT is active.
139     The linear range starts at (gfn << PAGE_SHIFT) and its size is determined
140     by role.level (2MB for first level, 1GB for second level, 0.5TB for third
141     level, 256TB for fourth level)
142     If clear, this page corresponds to a guest page table denoted by the gfn
143     field.
144   role.quadrant:
145     When role.cr4_pae=0, the guest uses 32-bit gptes while the host uses 64-bit
146     sptes.  That means a guest page table contains more ptes than the host,
147     so multiple shadow pages are needed to shadow one guest page.
148     For first-level shadow pages, role.quadrant can be 0 or 1 and denotes the
149     first or second 512-gpte block in the guest page table.  For second-level
150     page tables, each 32-bit gpte is converted to two 64-bit sptes
151     (since each first-level guest page is shadowed by two first-level
152     shadow pages) so role.quadrant takes values in the range 0..3.  Each
153     quadrant maps 1GB virtual address space.
154   role.access:
155     Inherited guest access permissions in the form uwx.  Note execute
156     permission is positive, not negative.
157   role.invalid:
158     The page is invalid and should not be used.  It is a root page that is
159     currently pinned (by a cpu hardware register pointing to it); once it is
160     unpinned it will be destroyed.
161   role.cr4_pae:
162     Contains the value of cr4.pae for which the page is valid (e.g. whether
163     32-bit or 64-bit gptes are in use).
164   role.nxe:
165     Contains the value of efer.nxe for which the page is valid.
166   role.cr0_wp:
167     Contains the value of cr0.wp for which the page is valid.
168   role.smep_andnot_wp:
169     Contains the value of cr4.smep && !cr0.wp for which the page is valid
170     (pages for which this is true are different from other pages; see the
171     treatment of cr0.wp=0 below).
172   gfn:
173     Either the guest page table containing the translations shadowed by this
174     page, or the base page frame for linear translations.  See role.direct.
175   spt:
176     A pageful of 64-bit sptes containing the translations for this page.
177     Accessed by both kvm and hardware.
178     The page pointed to by spt will have its page->private pointing back
179     at the shadow page structure.
180     sptes in spt point either at guest pages, or at lower-level shadow pages.
181     Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point
182     at __pa(sp2->spt).  sp2 will point back at sp1 through parent_pte.
183     The spt array forms a DAG structure with the shadow page as a node, and
184     guest pages as leaves.
185   gfns:
186     An array of 512 guest frame numbers, one for each present pte.  Used to
187     perform a reverse map from a pte to a gfn. When role.direct is set, any
188     element of this array can be calculated from the gfn field when used, in
189     this case, the array of gfns is not allocated. See role.direct and gfn.
190   root_count:
191     A counter keeping track of how many hardware registers (guest cr3 or
192     pdptrs) are now pointing at the page.  While this counter is nonzero, the
193     page cannot be destroyed.  See role.invalid.
194   parent_ptes:
195     The reverse mapping for the pte/ptes pointing at this page's spt. If
196     parent_ptes bit 0 is zero, only one spte points at this pages and
197     parent_ptes points at this single spte, otherwise, there exists multiple
198     sptes pointing at this page and (parent_ptes & ~0x1) points at a data
199     structure with a list of parent_ptes.
200   unsync:
201     If true, then the translations in this page may not match the guest's
202     translation.  This is equivalent to the state of the tlb when a pte is
203     changed but before the tlb entry is flushed.  Accordingly, unsync ptes
204     are synchronized when the guest executes invlpg or flushes its tlb by
205     other means.  Valid for leaf pages.
206   unsync_children:
207     How many sptes in the page point at pages that are unsync (or have
208     unsynchronized children).
209   unsync_child_bitmap:
210     A bitmap indicating which sptes in spt point (directly or indirectly) at
211     pages that may be unsynchronized.  Used to quickly locate all unsychronized
212     pages reachable from a given page.
213   mmu_valid_gen:
214     Generation number of the page.  It is compared with kvm->arch.mmu_valid_gen
215     during hash table lookup, and used to skip invalidated shadow pages (see
216     "Zapping all pages" below.)
217   clear_spte_count:
218     Only present on 32-bit hosts, where a 64-bit spte cannot be written
219     atomically.  The reader uses this while running out of the MMU lock
220     to detect in-progress updates and retry them until the writer has
221     finished the write.
222   write_flooding_count:
223     A guest may write to a page table many times, causing a lot of
224     emulations if the page needs to be write-protected (see "Synchronized
225     and unsynchronized pages" below).  Leaf pages can be unsynchronized
226     so that they do not trigger frequent emulation, but this is not
227     possible for non-leafs.  This field counts the number of emulations
228     since the last time the page table was actually used; if emulation
229     is triggered too frequently on this page, KVM will unmap the page
230     to avoid emulation in the future.
231
232 Reverse map
233 ===========
234
235 The mmu maintains a reverse mapping whereby all ptes mapping a page can be
236 reached given its gfn.  This is used, for example, when swapping out a page.
237
238 Synchronized and unsynchronized pages
239 =====================================
240
241 The guest uses two events to synchronize its tlb and page tables: tlb flushes
242 and page invalidations (invlpg).
243
244 A tlb flush means that we need to synchronize all sptes reachable from the
245 guest's cr3.  This is expensive, so we keep all guest page tables write
246 protected, and synchronize sptes to gptes when a gpte is written.
247
248 A special case is when a guest page table is reachable from the current
249 guest cr3.  In this case, the guest is obliged to issue an invlpg instruction
250 before using the translation.  We take advantage of that by removing write
251 protection from the guest page, and allowing the guest to modify it freely.
252 We synchronize modified gptes when the guest invokes invlpg.  This reduces
253 the amount of emulation we have to do when the guest modifies multiple gptes,
254 or when the a guest page is no longer used as a page table and is used for
255 random guest data.
256
257 As a side effect we have to resynchronize all reachable unsynchronized shadow
258 pages on a tlb flush.
259
260
261 Reaction to events
262 ==================
263
264 - guest page fault (or npt page fault, or ept violation)
265
266 This is the most complicated event.  The cause of a page fault can be:
267
268   - a true guest fault (the guest translation won't allow the access) (*)
269   - access to a missing translation
270   - access to a protected translation
271     - when logging dirty pages, memory is write protected
272     - synchronized shadow pages are write protected (*)
273   - access to untranslatable memory (mmio)
274
275   (*) not applicable in direct mode
276
277 Handling a page fault is performed as follows:
278
279  - if the RSV bit of the error code is set, the page fault is caused by guest
280    accessing MMIO and cached MMIO information is available.
281    - walk shadow page table
282    - check for valid generation number in the spte (see "Fast invalidation of
283      MMIO sptes" below)
284    - cache the information to vcpu->arch.mmio_gva, vcpu->arch.access and
285      vcpu->arch.mmio_gfn, and call the emulator
286  - If both P bit and R/W bit of error code are set, this could possibly
287    be handled as a "fast page fault" (fixed without taking the MMU lock).  See
288    the description in Documentation/virtual/kvm/locking.txt.
289  - if needed, walk the guest page tables to determine the guest translation
290    (gva->gpa or ngpa->gpa)
291    - if permissions are insufficient, reflect the fault back to the guest
292  - determine the host page
293    - if this is an mmio request, there is no host page; cache the info to
294      vcpu->arch.mmio_gva, vcpu->arch.access and vcpu->arch.mmio_gfn
295  - walk the shadow page table to find the spte for the translation,
296    instantiating missing intermediate page tables as necessary
297    - If this is an mmio request, cache the mmio info to the spte and set some
298      reserved bit on the spte (see callers of kvm_mmu_set_mmio_spte_mask)
299  - try to unsynchronize the page
300    - if successful, we can let the guest continue and modify the gpte
301  - emulate the instruction
302    - if failed, unshadow the page and let the guest continue
303  - update any translations that were modified by the instruction
304
305 invlpg handling:
306
307   - walk the shadow page hierarchy and drop affected translations
308   - try to reinstantiate the indicated translation in the hope that the
309     guest will use it in the near future
310
311 Guest control register updates:
312
313 - mov to cr3
314   - look up new shadow roots
315   - synchronize newly reachable shadow pages
316
317 - mov to cr0/cr4/efer
318   - set up mmu context for new paging mode
319   - look up new shadow roots
320   - synchronize newly reachable shadow pages
321
322 Host translation updates:
323
324   - mmu notifier called with updated hva
325   - look up affected sptes through reverse map
326   - drop (or update) translations
327
328 Emulating cr0.wp
329 ================
330
331 If tdp is not enabled, the host must keep cr0.wp=1 so page write protection
332 works for the guest kernel, not guest guest userspace.  When the guest
333 cr0.wp=1, this does not present a problem.  However when the guest cr0.wp=0,
334 we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the
335 semantics require allowing any guest kernel access plus user read access).
336
337 We handle this by mapping the permissions to two possible sptes, depending
338 on fault type:
339
340 - kernel write fault: spte.u=0, spte.w=1 (allows full kernel access,
341   disallows user access)
342 - read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel
343   write access)
344
345 (user write faults generate a #PF)
346
347 In the first case there is an additional complication if CR4.SMEP is
348 enabled: since we've turned the page into a kernel page, the kernel may now
349 execute it.  We handle this by also setting spte.nx.  If we get a user
350 fetch or read fault, we'll change spte.u=1 and spte.nx=gpte.nx back.
351
352 To prevent an spte that was converted into a kernel page with cr0.wp=0
353 from being written by the kernel after cr0.wp has changed to 1, we make
354 the value of cr0.wp part of the page role.  This means that an spte created
355 with one value of cr0.wp cannot be used when cr0.wp has a different value -
356 it will simply be missed by the shadow page lookup code.  A similar issue
357 exists when an spte created with cr0.wp=0 and cr4.smep=0 is used after
358 changing cr4.smep to 1.  To avoid this, the value of !cr0.wp && cr4.smep
359 is also made a part of the page role.
360
361 Large pages
362 ===========
363
364 The mmu supports all combinations of large and small guest and host pages.
365 Supported page sizes include 4k, 2M, 4M, and 1G.  4M pages are treated as
366 two separate 2M pages, on both guest and host, since the mmu always uses PAE
367 paging.
368
369 To instantiate a large spte, four constraints must be satisfied:
370
371 - the spte must point to a large host page
372 - the guest pte must be a large pte of at least equivalent size (if tdp is
373   enabled, there is no guest pte and this condition is satisfied)
374 - if the spte will be writeable, the large page frame may not overlap any
375   write-protected pages
376 - the guest page must be wholly contained by a single memory slot
377
378 To check the last two conditions, the mmu maintains a ->write_count set of
379 arrays for each memory slot and large page size.  Every write protected page
380 causes its write_count to be incremented, thus preventing instantiation of
381 a large spte.  The frames at the end of an unaligned memory slot have
382 artificially inflated ->write_counts so they can never be instantiated.
383
384 Zapping all pages (page generation count)
385 =========================================
386
387 For the large memory guests, walking and zapping all pages is really slow
388 (because there are a lot of pages), and also blocks memory accesses of
389 all VCPUs because it needs to hold the MMU lock.
390
391 To make it be more scalable, kvm maintains a global generation number
392 which is stored in kvm->arch.mmu_valid_gen.  Every shadow page stores
393 the current global generation-number into sp->mmu_valid_gen when it
394 is created.  Pages with a mismatching generation number are "obsolete".
395
396 When KVM need zap all shadow pages sptes, it just simply increases the global
397 generation-number then reload root shadow pages on all vcpus.  As the VCPUs
398 create new shadow page tables, the old pages are not used because of the
399 mismatching generation number.
400
401 KVM then walks through all pages and zaps obsolete pages.  While the zap
402 operation needs to take the MMU lock, the lock can be released periodically
403 so that the VCPUs can make progress.
404
405 Fast invalidation of MMIO sptes
406 ===============================
407
408 As mentioned in "Reaction to events" above, kvm will cache MMIO
409 information in leaf sptes.  When a new memslot is added or an existing
410 memslot is changed, this information may become stale and needs to be
411 invalidated.  This also needs to hold the MMU lock while walking all
412 shadow pages, and is made more scalable with a similar technique.
413
414 MMIO sptes have a few spare bits, which are used to store a
415 generation number.  The global generation number is stored in
416 kvm_memslots(kvm)->generation, and increased whenever guest memory info
417 changes.  This generation number is distinct from the one described in
418 the previous section.
419
420 When KVM finds an MMIO spte, it checks the generation number of the spte.
421 If the generation number of the spte does not equal the global generation
422 number, it will ignore the cached MMIO information and handle the page
423 fault through the slow path.
424
425 Since only 19 bits are used to store generation-number on mmio spte, all
426 pages are zapped when there is an overflow.
427
428 Unfortunately, a single memory access might access kvm_memslots(kvm) multiple
429 times, the last one happening when the generation number is retrieved and
430 stored into the MMIO spte.  Thus, the MMIO spte might be created based on
431 out-of-date information, but with an up-to-date generation number.
432
433 To avoid this, the generation number is incremented again after synchronize_srcu
434 returns; thus, the low bit of kvm_memslots(kvm)->generation is only 1 during a
435 memslot update, while some SRCU readers might be using the old copy.  We do not
436 want to use an MMIO sptes created with an odd generation number, and we can do
437 this without losing a bit in the MMIO spte.  The low bit of the generation
438 is not stored in MMIO spte, and presumed zero when it is extracted out of the
439 spte.  If KVM is unlucky and creates an MMIO spte while the low bit is 1,
440 the next access to the spte will always be a cache miss.
441
442
443 Further reading
444 ===============
445
446 - NPT presentation from KVM Forum 2008
447   http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf
448