x86: 64 bit pmap code
[akaros.git] / kern / arch / x86 / pmap64.c
1 /* Copyright (c) 2013 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * 64 bit virtual memory / address space management (and a touch of pmem).
6  *
7  * TODO:
8  * - better testing: check my helper funcs, a variety of inserts/segments remove
9  * it all, etc (esp with jumbos).  check permissions and the existence of
10  * mappings.
11  * - mapping segments doesn't support having a PTE already present
12  * - mtrrs break big machines
13  * - jumbo pages are only supported at the VM layer, not PM (a jumbo is 2^9
14  * little pages, for example)
15  * - usermemwalk and freeing might need some help (in higher layers of the
16  * kernel). */
17
18 #include <arch/x86.h>
19 #include <arch/arch.h>
20 #include <arch/mmu.h>
21 #include <arch/apic.h>
22 #include <error.h>
23 #include <sys/queue.h>
24 #include <atomic.h>
25 #include <string.h>
26 #include <assert.h>
27 #include <pmap.h>
28 #include <kclock.h>
29 #include <env.h>
30 #include <stdio.h>
31 #include <kmalloc.h>
32 #include <page_alloc.h>
33
34 extern char boot_pml4[], gdt64[], gdt64desc[];
35 pde_t *boot_pgdir;
36 physaddr_t boot_cr3;
37 segdesc_t *gdt;
38 pseudodesc_t *gdt_pd;
39
40 #define PG_WALK_SHIFT_MASK              0x00ff          /* first byte = target shift */
41 #define PG_WALK_CREATE                  0x0100
42
43 pte_t *pml_walk(pte_t *pml, uintptr_t va, int flags);
44 void map_segment(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa,
45                  int perm, int pml_shift);
46 typedef int (*pte_cb_t)(pte_t *pte, uintptr_t kva, int pml_shift,
47                         bool visited_subs, void *arg);
48 int pml_for_each(pte_t *pml, uintptr_t start, size_t len, pte_cb_t callback,
49                  void *arg);
50
51 /* Helper: returns true if we do not need to walk the page table any further.
52  *
53  * The caller may or may not know if a jumbo is desired.  pml_shift determines
54  * which layer we are at in the page walk, and flags contains the target level
55  * we're looking for, like a jumbo or a default.
56  *
57  * Regardless of the desired target, if we find a jumbo page, we're also done.
58  */
59 static bool walk_is_complete(pte_t *pte, int pml_shift, int flags)
60 {
61         if ((pml_shift == (flags & PG_WALK_SHIFT_MASK)) || (*pte & PTE_PS))
62                 return TRUE;
63         return FALSE;
64 }
65
66 /* PTE_ADDR should only be used on a PTE that has a physical address of the next
67  * PML inside.  i.e., not a final PTE in the page table walk. */
68 static pte_t *pte2pml(pte_t pte)
69 {
70         return (pte_t*)KADDR(PTE_ADDR(pte));
71 }
72
73 static pte_t *__pml_walk(pte_t *pml, uintptr_t va, int flags, int pml_shift)
74 {
75         pte_t *pte;
76         void *new_pml_kva;
77
78         pte = &pml[PMLx(va, pml_shift)];
79         if (walk_is_complete(pte, pml_shift, flags))
80                 return pte;
81         if (!(*pte & PTE_P)) {
82                 if (!(flags & PG_WALK_CREATE))
83                         return NULL;
84                 new_pml_kva = kpage_zalloc_addr();
85                 /* Might want better error handling (we're probably out of memory) */
86                 if (!new_pml_kva)
87                         return NULL;
88                 /* We insert the new PT into the PML with U and W perms.  Permissions on
89                  * page table walks are anded together (if any of them are !User, the
90                  * translation is !User).  We put the perms on the last entry, not the
91                  * intermediates. */
92                 *pte = PADDR(new_pml_kva) | PTE_P | PTE_U | PTE_W;
93         }
94         return __pml_walk(pte2pml(*pte), va, flags, pml_shift - BITS_PER_PML);
95 }
96
97 /* Returns a pointer to the page table entry corresponding to va.  Flags has
98  * some options and selects which level of the page table we're happy with
99  * stopping at.  Normally, this is PML1 for a normal page (e.g. flags =
100  * PML1_SHIFT), but could be for a jumbo page (PML3 or PML2 entry).
101  *
102  * Flags also controls whether or not intermediate page tables are created or
103  * not.  This is useful for when we are checking whether or not a mapping
104  * exists, but aren't interested in creating intermediate tables that will not
105  * get filled.  When we want to create intermediate pages (i.e. we're looking
106  * for the PTE to insert a page), pass in PG_WALK_CREATE with flags.
107  *
108  * Returns 0 on error or absence of a PTE for va. */
109 pte_t *pml_walk(pte_t *pml, uintptr_t va, int flags)
110 {
111         return __pml_walk(pml, va, flags, PML4_SHIFT);
112 }
113
114 /* Helper: determines how much va needs to be advanced until it is aligned to
115  * pml_shift. */
116 static uintptr_t amt_til_aligned(uintptr_t va, int pml_shift)
117 {
118         /* find the lower bits of va, subtract them from the shift to see what we
119          * would need to add to get to the shift.  va might be aligned already, and
120          * we subtracted 0, so we mask off the top part again. */
121         return ((1UL << pml_shift) - (va & ((1UL << pml_shift) - 1))) &
122                ((1UL << pml_shift) - 1);
123 }
124
125 /* Helper: determines how much of size we can take, in chunks of pml_shift */
126 static uintptr_t amt_of_aligned_bytes(uintptr_t size, int pml_shift)
127 {
128         /* creates a mask all 1s from MSB down to (including) shift */
129         return (~((1UL << pml_shift) - 1)) & size;
130 }
131
132 /* Helper: Advance pte, given old_pte.  Will do pml walks when necessary. */
133 static pte_t *get_next_pte(pte_t *old_pte, pte_t *pgdir, uintptr_t va,
134                            int flags)
135 {
136         /* PTEs (undereferenced) are addresses within page tables.  so long as we
137          * stay inside the PML, we can just advance via pointer arithmetic.  if we
138          * advance old_pte and it points to the beginning of a page (offset == 0),
139          * we've looped outside of our original PML, and need to get a new one. */
140         old_pte++;
141         if (!PGOFF(old_pte))
142                 return pml_walk(pgdir, va, flags);
143         return old_pte;
144 }
145
146 /* Helper: maps pages from va to pa for size bytes, all for a given page size */
147 static void map_my_pages(pte_t *pgdir, uintptr_t va, size_t size,
148                          physaddr_t pa, int perm, int pml_shift)
149 {
150         /* set to trigger a pml walk on the first get_next */
151         pte_t *pte = (pte_t*)PGSIZE - 1;
152         size_t pgsize = 1UL << pml_shift;
153
154         for (size_t i = 0; i < size; i += pgsize, va += pgsize,
155              pa += pgsize) {
156                 pte = get_next_pte(pte, pgdir, va, PG_WALK_CREATE | pml_shift);
157                 assert(pte);
158                 *pte = PTE_ADDR(pa) | PTE_P | perm |
159                        (pml_shift != PML1_SHIFT ? PTE_PS : 0);
160                 printd("Wrote *pte %p, for va %p to pa %p tried to cover %p\n",
161                        *pte, va, pa, amt_mapped);
162         }
163 }
164
165 /* Maps all pages possible from va->pa, up to size, preferring to use pages of
166  * type pml_shift (size == (1 << shift)).  Assumes that it is possible to map va
167  * to pa at the given shift. */
168 static uintptr_t __map_segment(pte_t *pgdir, uintptr_t va, size_t size,
169                                physaddr_t pa, int perm, int pml_shift)
170 {
171         printd("__map_segment, va %p, size %p, pa %p, shift %d\n", va, size,
172                pa, pml_shift);
173         uintptr_t amt_to_submap, amt_to_map, amt_mapped = 0;
174
175         amt_to_submap = amt_til_aligned(va, pml_shift);
176         amt_to_submap = MIN(amt_to_submap, size);
177         if (amt_to_submap) {
178                 amt_mapped = __map_segment(pgdir, va, amt_to_submap, pa, perm,
179                                            pml_shift - BITS_PER_PML);
180                 va += amt_mapped;
181                 pa += amt_mapped;
182                 size -= amt_mapped;
183         }
184         /* Now we're either aligned and ready to map, or size == 0 */
185         amt_to_map = amt_of_aligned_bytes(size, pml_shift);
186         if (amt_to_map) {
187                 map_my_pages(pgdir, va, amt_to_map, pa, perm, pml_shift);
188                 va += amt_to_map;
189                 pa += amt_to_map;
190                 size -= amt_to_map;
191                 amt_mapped += amt_to_map;
192         }
193         /* Map whatever is left over */
194         if (size)
195                 amt_mapped += __map_segment(pgdir, va, amt_to_submap, pa, perm,
196                                             pml_shift - BITS_PER_PML);
197         return amt_mapped;
198 }
199
200 /* Returns the maximum pml shift possible between a va->pa mapping.  It is the
201  * number of least-significant bits the two addresses have in common.  For
202  * instance, if the two pages are 0x456000 and 0x156000, this returns 20.  For
203  * regular pages, it will be at least 12 (every page ends in 0x000).
204  *
205  * The max pml shift possible for an va->pa mapping is determined by the
206  * least bit that differs between va and pa.
207  *
208  * We can optimize this a bit, since we know the first 12 bits are the same, and
209  * we won't go higher than max_pml_shift. */
210 static int max_possible_shift(uintptr_t va, uintptr_t pa)
211 {
212         int shift = 0;
213         if (va == pa)
214                 return sizeof(uintptr_t) * 8;
215         while ((va & 1) == (pa & 1)) {
216                 va >>= 1;
217                 pa >>= 1;
218                 shift++;
219         }
220         return shift;
221 }
222
223 /* Map [va, va+size) of virtual (linear) address space to physical [pa, pa+size)
224  * in the page table rooted at pgdir.  Size is a multiple of PGSIZE.  Use
225  * permission bits perm|PTE_P for the entries.  Set pml_shift to the shift of
226  * the largest page size you're willing to use.
227  *
228  * Doesn't handle having pages currently mapped yet, and while supporting that
229  * is relatively easy, doing an insertion of small pages into an existing jumbo
230  * would be trickier.  Might have the vmem region code deal with this.
231  *
232  * Don't use this to set the PAT flag on jumbo pages in perm, unless you are
233  * absolultely sure you won't map regular pages.  */
234 void map_segment(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa,
235                  int perm, int pml_shift)
236 {
237         int max_shift_possible;
238         if (PGOFF(va) || PGOFF(pa) || PGOFF(size))
239                 panic("Asked to map with bad alignment.  va %p, pa %p, size %p\n", va,
240                       pa, size);
241         /* Given the max_page_size, try and use larger pages.  We'll figure out the
242          * largest possible jumbo page, up to whatever we were asked for. */
243         if (pml_shift != PGSHIFT) {
244                 max_shift_possible = max_possible_shift(va, pa);
245                 /* arch-specific limitation (can't have jumbos beyond PML3) */
246                 max_shift_possible = MIN(max_shift_possible, PML3_SHIFT);
247                 /* Assumes we were given a proper PML shift 12, 21, 30, etc */
248                 while (pml_shift > max_shift_possible)
249                         pml_shift -= BITS_PER_PML;
250         }
251         assert((pml_shift == PML1_SHIFT) ||
252                (pml_shift == PML2_SHIFT) ||
253                (pml_shift == PML3_SHIFT));
254         __map_segment(pgdir, va, size, pa, perm, pml_shift);
255 }
256
257 /* For every present PTE in [start, start + len), call callback(pte, shift,
258  * etc).  pml_shift is the shift/size of pml.
259  *
260  * This will recurse down into sub PMLs, and perform the CB in a
261  * depth-first-search.  The CB will be told which level of the paging it is at,
262  * via 'shift'.
263  *
264  * The CB will also run on intermediate PTEs: meaning, PTEs that point to page
265  * tables (and not (jumbo) pages) will be executed.  If the CB returns anything
266  * other than 0, we'll abort and propagate that back out from for_each. */
267 static int __pml_for_each(pte_t *pml,  uintptr_t start, size_t len,
268                           pte_cb_t callback, void *arg, int pml_shift)
269 {
270         int ret;
271         bool visited_all_subs;
272         pte_t *pte_s, *pte_e, *pte_i;
273         uintptr_t kva, pgsize = 1UL << pml_shift;
274
275         if (!len)
276                 return 0;
277         pte_s = &pml[PMLx(start, pml_shift)];
278         /* Later, we'll loop up to and including pte_e.  Since start + len might not
279          * be page aligned, we'll need to include the final pte.  If it is aligned,
280          * we don't want to visit, so we subtract one so that the aligned case maps
281          * to the index below it's normal pte. */
282         pte_e = &pml[PMLx(start + len - 1, pml_shift)];
283         /* tracks the virt addr pte_i works on, rounded for this PML */
284         kva = ROUNDDOWN(start, pgsize);
285         printd("PFE, start %p PMLx(S) %d, end-inc %p PMLx(E) %d shift %d, kva %p\n",
286                start, PMLx(start, pml_shift), start + len - 1,
287                PMLx(start + len - 1, pml_shift), pml_shift, kva);
288         for (pte_i = pte_s; pte_i <= pte_e; pte_i++, kva += pgsize) {
289                 if (!(*pte_i & PTE_P))
290                         continue;
291                 visited_all_subs = FALSE;
292                 /* Complete only on the last level (PML1_SHIFT) or on a jumbo */
293                 if (!walk_is_complete(pte_i, pml_shift, PML1_SHIFT)) {
294                         /* only pass truncated end points (e.g. start may not be page
295                          * aligned) when we're on the first (or last) item.  For the middle
296                          * entries, we want the subpmls to process the full range they are
297                          * responsible for: [kva, kva + pgsize). */
298                         uintptr_t sub_start = MAX(kva, start);
299                         size_t sub_len = MIN(start + len, kva + pgsize) - sub_start;
300                         ret = __pml_for_each(pte2pml(*pte_i), sub_start, sub_len, callback,
301                                              arg, pml_shift - BITS_PER_PML);
302                         if (ret)
303                                 return ret;
304                         /* based on sub_{start,end}, we can tell if our sub visited all of
305                          * its PTES. */
306                         if ((sub_start == kva) && (sub_len == pgsize))
307                                 visited_all_subs = TRUE;
308                 }
309                 if ((ret = callback(pte_i, kva, pml_shift, visited_all_subs, arg)))
310                         return ret;
311         }
312         return 0;
313 }
314
315 int pml_for_each(pte_t *pml, uintptr_t start, size_t len, pte_cb_t callback,
316                  void *arg)
317 {
318         return __pml_for_each(pml, start, len, callback, arg, PML4_SHIFT);
319 }
320
321 /* Older interface for page table walks - will return the PTE corresponding to
322  * VA.  If create is 1, it'll create intermediate tables.  This can return jumbo
323  * PTEs, but only if they already exist.  Otherwise, (with create), it'll walk
324  * to the lowest PML.  If the walk fails due to a lack of intermediate tables or
325  * memory, this returns 0. */
326 pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create)
327 {
328         int flags = PML1_SHIFT;
329         if (create == 1)
330                 flags |= PG_WALK_CREATE;
331         return pml_walk(pgdir, (uintptr_t)va, flags);
332 }
333
334 static int pml_perm_walk(pte_t *pml, const void *va, int pml_shift)
335 {
336         pte_t *pte;
337         int perms_here;
338
339         pte = &pml[PMLx(va, pml_shift)];
340         if (!(*pte & PTE_P))
341                 return 0;
342         perms_here = *pte & (PTE_PERM | PTE_P);
343         if (walk_is_complete(pte, pml_shift, PML1_SHIFT))
344                 return perms_here;
345         return pml_perm_walk(pte2pml(*pte), va, pml_shift - BITS_PER_PML) &
346                perms_here;
347 }
348
349 /* Returns the effective permissions for PTE_U, PTE_W, and PTE_P on a given
350  * virtual address.  Note we need to consider the composition of every PTE in
351  * the page table walk (we bit-and all of them together) */
352 int get_va_perms(pde_t *pgdir, const void *va)
353 {
354         return pml_perm_walk(pgdir, va, PML4_SHIFT);
355 }
356
357 #define check_sym_va(sym, addr)                                                \
358 ({                                                                             \
359         if ((sym) != (addr))                                                       \
360                 printk("Error: " #sym " is %p, should be " #addr "\n", sym);           \
361 })
362
363 static void check_syms_va(void)
364 {
365         /* Make sure our symbols are up to date (see arch/ros/mmu64.h) */
366         check_sym_va(KERN_LOAD_ADDR, 0xffffffffc0000000);
367         check_sym_va(LAPIC_BASE,     0xffffffffbffff000);
368         check_sym_va(IOAPIC_BASE,    0xffffffffbfffe000);
369         check_sym_va(VPT_TOP,        0xffffff0000000000);
370         check_sym_va(VPT,            0xfffffe8000000000);
371         check_sym_va(KERN_VMAP_TOP,  0xfffffe8000000000);
372         check_sym_va(KERNBASE,       0xffff800000000000);
373         check_sym_va(ULIM,           0x0000800000000000);
374         check_sym_va(UVPT,           0x00007f8000000000);
375         check_sym_va(UINFO,          0x00007f7fffe00000);
376         check_sym_va(UWLIM,          0x00007f7fffe00000);
377         check_sym_va(UDATA,          0x00007f7fffc00000);
378         check_sym_va(UGDATA,         0x00007f7fffbff000);
379         check_sym_va(UMAPTOP,        0x00007f7fffbff000);
380         check_sym_va(USTACKTOP,      0x00007f7fffbff000);
381         check_sym_va(BRK_END,        0x0000400000000000);
382 }
383
384 /* Initializes anything related to virtual memory.  Paging is already on, but we
385  * have a slimmed down page table. */
386 void vm_init(void)
387 {
388         boot_cr3 = (physaddr_t)boot_pml4;
389         boot_pgdir = KADDR((uintptr_t)boot_pml4);
390         gdt = KADDR((uintptr_t)gdt64);
391         gdt_pd = KADDR((uintptr_t)gdt64desc);
392
393         check_syms_va();
394         /* KERNBASE mapping: we already have 512 GB complete (one full PML3_REACH).
395          * It's okay if we have extra, just need to make sure we reach max_paddr. */
396         if (KERNBASE + PML3_REACH < (uintptr_t)KADDR(max_paddr)) {
397                 map_segment(boot_pgdir, KERNBASE + PML3_REACH,
398                             max_paddr - PML3_REACH, 0x0 + PML3_REACH,
399                             PTE_W | PTE_G, MAX_JUMBO_SHIFT);
400         }
401         /* For the LAPIC and IOAPIC, we use PAT (but not *the* PAT flag) to make
402          * these type UC */
403         map_segment(boot_pgdir, LAPIC_BASE, PGSIZE, LAPIC_PBASE,
404                     PTE_PCD | PTE_PWT | PTE_W | PTE_G, MAX_JUMBO_SHIFT);
405         map_segment(boot_pgdir, IOAPIC_BASE, PGSIZE, IOAPIC_PBASE,
406                     PTE_PCD | PTE_PWT | PTE_W | PTE_G, MAX_JUMBO_SHIFT);
407         /* VPT mapping: recursive PTE inserted at the VPT spot */
408         boot_pgdir[PDX(VPT)] = PADDR(boot_pgdir) | PTE_W | PTE_P | PTE_G;
409         /* same for UVPT, accessible by userspace (RO). */
410         boot_pgdir[PDX(UVPT)] = PADDR(boot_pgdir) | PTE_U | PTE_P | PTE_G;
411         /* set up core0s now (mostly for debugging) */
412         setup_default_mtrrs(0);
413 }
414
415 /* Walks len bytes from start, executing 'callback' on every PTE, passing it a
416  * specific VA and whatever arg is passed in.  Note, this cannot handle jumbo
417  * pages.
418  *
419  * This is just a clumsy wrapper around the more powerful pml_for_each, which
420  * can handle jumbo and intermediate pages. */
421 int env_user_mem_walk(struct proc *p, void *start, size_t len,
422                       mem_walk_callback_t callback, void *arg)
423 {
424         struct tramp_package {
425                 struct proc *p;
426                 mem_walk_callback_t cb;
427                 void *cb_arg;
428         };
429         int trampoline_cb(pte_t *pte, uintptr_t kva, int shift, bool visited_subs,
430                           void *data)
431         {
432                 struct tramp_package *tp = (struct tramp_package*)data;
433                 assert(tp->cb);
434                 /* memwalk CBs don't know how to handle intermediates or jumbos */
435                 if (shift != PML1_SHIFT)
436                         return 0;
437                 return tp->cb(tp->p, pte, (void*)kva, tp->cb_arg);
438         }
439
440         struct tramp_package local_tp;
441         local_tp.p = p;
442         local_tp.cb = callback;
443         local_tp.cb_arg = arg;
444         return pml_for_each(p->env_pgdir, (uintptr_t)start, len, trampoline_cb,
445                             &local_tp);
446 }
447
448 /* Frees (decrefs) all pages of the process's page table, including the page
449  * directory.  Does not free the memory that is actually mapped. */
450 void env_pagetable_free(struct proc *p)
451 {
452         /* callback: given an intermediate pte (not a final one), removes the page
453          * table the PTE points to */
454         int pt_free_cb(pte_t *pte, uintptr_t kva, int shift, bool visited_subs,
455                        void *data)
456         {
457                 if ((shift == PML1_SHIFT) || (*pte * PTE_PS))
458                         return 0;
459                 page_decref(ppn2page(LA2PPN(pte)));
460                 return 0;
461         }
462                 
463         assert(p->env_cr3 != rcr3());
464         pml_for_each(p->env_pgdir, 0, UVPT, pt_free_cb, 0);
465         /* the page directory is not a PTE, so it never was freed */
466         page_decref(pa2page(p->env_cr3));
467         tlbflush();
468 }
469
470 /* Remove the inner page tables along va's walk.  The internals are more
471  * powerful.  We'll eventually want better arch-indep VM functions. */
472 error_t pagetable_remove(pde_t *pgdir, void *va)
473 {
474         int pt_maybe_free_cb(pte_t *pte, uintptr_t kva, int shift,
475                              bool visited_subs, void *data)
476         {
477                 if ((shift == PML1_SHIFT) || (*pte * PTE_PS))
478                         return 0;
479                 pte_t *pte_i = pte2pml(*pte);   /* first pte == pml */
480                 /* make sure we have no PTEs in use */
481                 for (int i = 0; i < NPTENTRIES; i++, pte_i++) {
482                         if (*pte_i & PTE_P)
483                                 return 0;
484                 }
485                 page_decref(ppn2page(LA2PPN(pte)));
486                 return 0;
487         }
488
489         return pml_for_each(pgdir, (uintptr_t)va, PGSIZE, pt_maybe_free_cb, 0);
490 }
491
492 void page_check(void)
493 {
494 }
495
496 /* Debugging */
497 static int print_pte(pte_t *pte, uintptr_t kva, int shift, bool visited_subs,
498                      void *data)
499 {
500         switch (shift) {
501                 case (PML1_SHIFT):
502                         printk("\t");
503                         /* fall-through */
504                 case (PML2_SHIFT):
505                         printk("\t");
506                         /* fall-through */
507                 case (PML3_SHIFT):
508                         printk("\t");
509         }
510         printk("KVA: %p, PTE val %p, shift %d, visit %d\n", kva, *pte, shift,
511                visited_subs);
512         return 0;
513 }
514
515 void debug_print_pgdir(pte_t *pgdir)
516 {
517         printk("Printing the entire page table set for %p, DFS\n", pgdir);
518         /* Need to be careful we avoid VPT/UVPT, o/w we'll recurse */
519         pml_for_each(pgdir, 0, UVPT, print_pte, 0);
520         pml_for_each(pgdir, ULIM, VPT - ULIM, print_pte, 0);
521         pml_for_each(pgdir, VPT_TOP, MAX_VADDR - VPT_TOP, print_pte, 0);
522 }