← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-ti-omap4/precise

« back to all changes in this revision

Viewing changes to Documentation/kvm/mmu.txt

  • Committer: Bazaar Package Importer
  • Author(s): Paolo Pisati
  • Date: 2011-06-29 15:23:51 UTC
  • mfrom: (26.1.1 natty-proposed)
  • Revision ID: james.westby@ubuntu.com-20110629152351-xs96tm303d95rpbk
Tags: 3.0.0-1200.2
* Rebased against 3.0.0-6.7
* BSP from TI based on 3.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
Documentation/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
 
- reliablity:  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
 
  gfn:
169
 
    Either the guest page table containing the translations shadowed by this
170
 
    page, or the base page frame for linear translations.  See role.direct.
171
 
  spt:
172
 
    A pageful of 64-bit sptes containing the translations for this page.
173
 
    Accessed by both kvm and hardware.
174
 
    The page pointed to by spt will have its page->private pointing back
175
 
    at the shadow page structure.
176
 
    sptes in spt point either at guest pages, or at lower-level shadow pages.
177
 
    Specifically, if sp1 and sp2 are shadow pages, then sp1->spt[n] may point
178
 
    at __pa(sp2->spt).  sp2 will point back at sp1 through parent_pte.
179
 
    The spt array forms a DAG structure with the shadow page as a node, and
180
 
    guest pages as leaves.
181
 
  gfns:
182
 
    An array of 512 guest frame numbers, one for each present pte.  Used to
183
 
    perform a reverse map from a pte to a gfn. When role.direct is set, any
184
 
    element of this array can be calculated from the gfn field when used, in
185
 
    this case, the array of gfns is not allocated. See role.direct and gfn.
186
 
  slot_bitmap:
187
 
    A bitmap containing one bit per memory slot.  If the page contains a pte
188
 
    mapping a page from memory slot n, then bit n of slot_bitmap will be set
189
 
    (if a page is aliased among several slots, then it is not guaranteed that
190
 
    all slots will be marked).
191
 
    Used during dirty logging to avoid scanning a shadow page if none if its
192
 
    pages need tracking.
193
 
  root_count:
194
 
    A counter keeping track of how many hardware registers (guest cr3 or
195
 
    pdptrs) are now pointing at the page.  While this counter is nonzero, the
196
 
    page cannot be destroyed.  See role.invalid.
197
 
  multimapped:
198
 
    Whether there exist multiple sptes pointing at this page.
199
 
  parent_pte/parent_ptes:
200
 
    If multimapped is zero, parent_pte points at the single spte that points at
201
 
    this page's spt.  Otherwise, parent_ptes points at a data structure
202
 
    with a list of parent_ptes.
203
 
  unsync:
204
 
    If true, then the translations in this page may not match the guest's
205
 
    translation.  This is equivalent to the state of the tlb when a pte is
206
 
    changed but before the tlb entry is flushed.  Accordingly, unsync ptes
207
 
    are synchronized when the guest executes invlpg or flushes its tlb by
208
 
    other means.  Valid for leaf pages.
209
 
  unsync_children:
210
 
    How many sptes in the page point at pages that are unsync (or have
211
 
    unsynchronized children).
212
 
  unsync_child_bitmap:
213
 
    A bitmap indicating which sptes in spt point (directly or indirectly) at
214
 
    pages that may be unsynchronized.  Used to quickly locate all unsychronized
215
 
    pages reachable from a given page.
216
 
 
217
 
Reverse map
218
 
===========
219
 
 
220
 
The mmu maintains a reverse mapping whereby all ptes mapping a page can be
221
 
reached given its gfn.  This is used, for example, when swapping out a page.
222
 
 
223
 
Synchronized and unsynchronized pages
224
 
=====================================
225
 
 
226
 
The guest uses two events to synchronize its tlb and page tables: tlb flushes
227
 
and page invalidations (invlpg).
228
 
 
229
 
A tlb flush means that we need to synchronize all sptes reachable from the
230
 
guest's cr3.  This is expensive, so we keep all guest page tables write
231
 
protected, and synchronize sptes to gptes when a gpte is written.
232
 
 
233
 
A special case is when a guest page table is reachable from the current
234
 
guest cr3.  In this case, the guest is obliged to issue an invlpg instruction
235
 
before using the translation.  We take advantage of that by removing write
236
 
protection from the guest page, and allowing the guest to modify it freely.
237
 
We synchronize modified gptes when the guest invokes invlpg.  This reduces
238
 
the amount of emulation we have to do when the guest modifies multiple gptes,
239
 
or when the a guest page is no longer used as a page table and is used for
240
 
random guest data.
241
 
 
242
 
As a side effect we have to resynchronize all reachable unsynchronized shadow
243
 
pages on a tlb flush.
244
 
 
245
 
 
246
 
Reaction to events
247
 
==================
248
 
 
249
 
- guest page fault (or npt page fault, or ept violation)
250
 
 
251
 
This is the most complicated event.  The cause of a page fault can be:
252
 
 
253
 
  - a true guest fault (the guest translation won't allow the access) (*)
254
 
  - access to a missing translation
255
 
  - access to a protected translation
256
 
    - when logging dirty pages, memory is write protected
257
 
    - synchronized shadow pages are write protected (*)
258
 
  - access to untranslatable memory (mmio)
259
 
 
260
 
  (*) not applicable in direct mode
261
 
 
262
 
Handling a page fault is performed as follows:
263
 
 
264
 
 - if needed, walk the guest page tables to determine the guest translation
265
 
   (gva->gpa or ngpa->gpa)
266
 
   - if permissions are insufficient, reflect the fault back to the guest
267
 
 - determine the host page
268
 
   - if this is an mmio request, there is no host page; call the emulator
269
 
     to emulate the instruction instead
270
 
 - walk the shadow page table to find the spte for the translation,
271
 
   instantiating missing intermediate page tables as necessary
272
 
 - try to unsynchronize the page
273
 
   - if successful, we can let the guest continue and modify the gpte
274
 
 - emulate the instruction
275
 
   - if failed, unshadow the page and let the guest continue
276
 
 - update any translations that were modified by the instruction
277
 
 
278
 
invlpg handling:
279
 
 
280
 
  - walk the shadow page hierarchy and drop affected translations
281
 
  - try to reinstantiate the indicated translation in the hope that the
282
 
    guest will use it in the near future
283
 
 
284
 
Guest control register updates:
285
 
 
286
 
- mov to cr3
287
 
  - look up new shadow roots
288
 
  - synchronize newly reachable shadow pages
289
 
 
290
 
- mov to cr0/cr4/efer
291
 
  - set up mmu context for new paging mode
292
 
  - look up new shadow roots
293
 
  - synchronize newly reachable shadow pages
294
 
 
295
 
Host translation updates:
296
 
 
297
 
  - mmu notifier called with updated hva
298
 
  - look up affected sptes through reverse map
299
 
  - drop (or update) translations
300
 
 
301
 
Emulating cr0.wp
302
 
================
303
 
 
304
 
If tdp is not enabled, the host must keep cr0.wp=1 so page write protection
305
 
works for the guest kernel, not guest guest userspace.  When the guest
306
 
cr0.wp=1, this does not present a problem.  However when the guest cr0.wp=0,
307
 
we cannot map the permissions for gpte.u=1, gpte.w=0 to any spte (the
308
 
semantics require allowing any guest kernel access plus user read access).
309
 
 
310
 
We handle this by mapping the permissions to two possible sptes, depending
311
 
on fault type:
312
 
 
313
 
- kernel write fault: spte.u=0, spte.w=1 (allows full kernel access,
314
 
  disallows user access)
315
 
- read fault: spte.u=1, spte.w=0 (allows full read access, disallows kernel
316
 
  write access)
317
 
 
318
 
(user write faults generate a #PF)
319
 
 
320
 
Large pages
321
 
===========
322
 
 
323
 
The mmu supports all combinations of large and small guest and host pages.
324
 
Supported page sizes include 4k, 2M, 4M, and 1G.  4M pages are treated as
325
 
two separate 2M pages, on both guest and host, since the mmu always uses PAE
326
 
paging.
327
 
 
328
 
To instantiate a large spte, four constraints must be satisfied:
329
 
 
330
 
- the spte must point to a large host page
331
 
- the guest pte must be a large pte of at least equivalent size (if tdp is
332
 
  enabled, there is no guest pte and this condition is satisified)
333
 
- if the spte will be writeable, the large page frame may not overlap any
334
 
  write-protected pages
335
 
- the guest page must be wholly contained by a single memory slot
336
 
 
337
 
To check the last two conditions, the mmu maintains a ->write_count set of
338
 
arrays for each memory slot and large page size.  Every write protected page
339
 
causes its write_count to be incremented, thus preventing instantiation of
340
 
a large spte.  The frames at the end of an unaligned memory slot have
341
 
artificically inflated ->write_counts so they can never be instantiated.
342
 
 
343
 
Further reading
344
 
===============
345
 
 
346
 
- NPT presentation from KVM Forum 2008
347
 
  http://www.linux-kvm.org/wiki/images/c/c8/KvmForum2008%24kdf2008_21.pdf
348