Merge large page support code.
[barrelfish] / lib / barrelfish / target / x86_64 / pmap_target.c
1 /**
2  * \file
3  * \brief pmap management
4  *
5  * x86_64 specific management of page tables
6  *
7  * Warning: This code is coupled with the code in slot_alloc/. and pinned.c
8  *
9  * The maximum number of slots required to map a BASE_PAGE_SIZE
10  * sized page is the number of page table levels + 1.
11  * The sum for x86_64 is 4.
12  *
13  * Warning: Additional slots will be required to map a BASE_PAGE_SIZE size page,
14  * if we also track the actual frames that are mapped.
15  * Currently this is not the case.
16  */
17
18 /*
19  * Copyright (c) 2009-2013 ETH Zurich.
20  * Copyright (c) 2014 HP Labs.
21  * All rights reserved.
22  *
23  * This file is distributed under the terms in the attached LICENSE file.
24  * If you do not find this file, copies can be found by writing to:
25  * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
26  */
27
28 #include <barrelfish/barrelfish.h>
29 #include <barrelfish/dispatch.h>
30 #include "target/x86/pmap_x86.h"
31 #include <stdio.h>
32
33 // Size of virtual region mapped by a single PML4 entry
34 #define PML4_MAPPING_SIZE ((genvaddr_t)512*512*512*BASE_PAGE_SIZE)
35
36 // Location and size of virtual address space reserved for mapping
37 // frames backing refill_slabs
38 #define META_DATA_RESERVED_BASE (PML4_MAPPING_SIZE * (disp_get_core_id() + 1))
39 #define META_DATA_RESERVED_SIZE (X86_64_BASE_PAGE_SIZE * 80000)
40
41 /**
42  * \brief Translate generic vregion flags to architecture specific pmap flags
43  */
44 static paging_x86_64_flags_t vregion_to_pmap_flag(vregion_flags_t vregion_flags)
45 {
46     paging_x86_64_flags_t pmap_flags =
47         PTABLE_USER_SUPERVISOR | PTABLE_EXECUTE_DISABLE;
48
49     if (!(vregion_flags & VREGION_FLAGS_GUARD)) {
50         if (vregion_flags & VREGION_FLAGS_WRITE) {
51             pmap_flags |= PTABLE_READ_WRITE;
52         }
53         if (vregion_flags & VREGION_FLAGS_EXECUTE) {
54             pmap_flags &= ~PTABLE_EXECUTE_DISABLE;
55         }
56         if (vregion_flags & VREGION_FLAGS_NOCACHE) {
57             pmap_flags |= PTABLE_CACHE_DISABLED;
58         }
59     }
60
61     return pmap_flags;
62 }
63
64 // returns whether va1 and va2 share a page directory entry
65 // not using X86_64_PDIR_BASE() macro as this would give false positives (same
66 // entry in different directories)
67 static inline bool is_same_pdir(genvaddr_t va1, genvaddr_t va2)
68 {
69     return (va1>>X86_64_LARGE_PAGE_BITS) == ((va2-1)>>X86_64_LARGE_PAGE_BITS);
70 }
71 // returns whether va1 and va2 share a page directory pointer table entry
72 static inline bool is_same_pdpt(genvaddr_t va1, genvaddr_t va2)
73 {
74     return (va1>>X86_64_HUGE_PAGE_BITS) == ((va2-1)>>X86_64_HUGE_PAGE_BITS);
75 }
76 // returns whether va1 and va2 share a page map level 4 entry
77 static inline bool is_same_pml4(genvaddr_t va1, genvaddr_t va2)
78 {
79     // the base macros work here as we only have one pml4.
80     return X86_64_PML4_BASE(va1) == X86_64_PML4_BASE(va2-1);
81 }
82 // size indicates how many bits to shift
83 static inline genvaddr_t get_addr_prefix(genvaddr_t va, uint8_t size)
84 {
85     return va >> size;
86 }
87
88 /**
89  * \brief Returns the vnode for the pdpt mapping a given vspace address
90  */
91 static inline errval_t get_pdpt(struct pmap_x86 *pmap, genvaddr_t base,
92                                 struct vnode **pdpt)
93 {
94     errval_t err;
95     struct vnode *root = &pmap->root;
96     assert(root != NULL);
97
98     // PML4 mapping
99     if((*pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
100         err = alloc_vnode(pmap, root, ObjType_VNode_x86_64_pdpt,
101                             X86_64_PML4_BASE(base), pdpt);
102         if (err_is_fail(err)) {
103             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
104         }
105     }
106
107     return SYS_ERR_OK;
108 }
109
110 /**
111  * \brief Returns the vnode for the page directory mapping a given vspace
112  * address
113  */
114 static inline errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
115                                 struct vnode **pdir)
116 {
117     errval_t err;
118     struct vnode *pdpt;
119     err = get_pdpt(pmap, base, &pdpt);
120     if (err_is_fail(err)) {
121         return err;
122     }
123     assert(pdpt != NULL);
124
125     // PDPT mapping
126     if((*pdir = find_vnode(pdpt, X86_64_PDPT_BASE(base))) == NULL) {
127         err = alloc_vnode(pmap, pdpt, ObjType_VNode_x86_64_pdir,
128                             X86_64_PDPT_BASE(base), pdir);
129         if (err_is_fail(err)) {
130             printf("failure mapping pdpt\n");
131             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
132         }
133     }
134
135     return SYS_ERR_OK;
136 }
137
138 /**
139  * \brief Returns the vnode for the pagetable mapping a given vspace address
140  */
141 static inline errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
142                                   struct vnode **ptable)
143 {
144     errval_t err;
145     struct vnode *pdir;
146     err = get_pdir(pmap, base, &pdir);
147     if (err_is_fail(err)) {
148         return err;
149     }
150     assert(pdir != NULL);
151
152     // PDIR mapping
153     if((*ptable = find_vnode(pdir, X86_64_PDIR_BASE(base))) == NULL) {
154         err = alloc_vnode(pmap, pdir, ObjType_VNode_x86_64_ptable,
155                             X86_64_PDIR_BASE(base), ptable);
156         if (err_is_fail(err)) {
157             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
158         }
159     }
160
161     return SYS_ERR_OK;
162 }
163
164 /**
165  * \brief Returns the vnode for the page directory pointer table mapping for a
166  * given vspace address
167  */
168 static inline struct vnode *find_pdpt(struct pmap_x86 *pmap, genvaddr_t base)
169 {
170     struct vnode *root = &pmap->root;
171     assert(root != NULL);
172
173     // PDPT mapping
174     return find_vnode(root, X86_64_PML4_BASE(base));
175 }
176
177 /**
178  * \brief Returns the vnode for the page directory mapping a given vspace
179  * address, without performing allocations as get_pdir() does
180  */
181 static inline struct vnode *find_pdir(struct pmap_x86 *pmap, genvaddr_t base)
182 {
183     struct vnode *pdpt = find_pdpt(pmap, base);
184
185     if (pdpt) {
186         // PDPT mapping
187         return find_vnode(pdpt, X86_64_PDPT_BASE(base));
188     } else {
189         return NULL;
190     }
191 }
192
193 /**
194  * \brief Returns the vnode for the pagetable mapping a given vspace address,
195  * without performing allocations as get_ptable() does
196  */
197 static inline struct vnode *find_ptable(struct pmap_x86 *pmap, genvaddr_t base)
198 {
199     struct vnode *pdir = find_pdir(pmap, base);
200
201     if (pdir) {
202         // PDIR mapping
203         return find_vnode(pdir, X86_64_PDIR_BASE(base));
204     } else {
205         return NULL;
206     }
207 }
208
209 static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
210                               genvaddr_t vend, struct capref frame,
211                               size_t offset, size_t pte_count,
212                               vregion_flags_t flags)
213 {
214     if (pte_count == 0) {
215         debug_printf("do_single_map: pte_count == 0, called from %p\n",
216                 __builtin_return_address(0));
217         return SYS_ERR_OK;
218     }
219     assert(pte_count > 0);
220     // translate flags
221     paging_x86_64_flags_t pmap_flags = vregion_to_pmap_flag(flags);
222
223     // Get the paging structure and set paging relevant parameters
224     struct vnode *ptable;
225     errval_t err;
226     size_t table_base;
227
228     // get the right paging table and address part
229     if(flags & VREGION_FLAGS_LARGE) {
230         //large 2M pages, mapped into pdir
231         err = get_pdir(pmap, vaddr, &ptable);
232         table_base = X86_64_PDIR_BASE(vaddr);
233     } else if (flags & VREGION_FLAGS_HUGE) {
234         //huge 1GB pages, mapped into pdpt
235         err = get_pdpt(pmap, vaddr, &ptable);
236         table_base = X86_64_PDPT_BASE(vaddr);
237     } else {
238         //normal 4K pages, mapped into ptable
239         err = get_ptable(pmap, vaddr, &ptable);
240         table_base = X86_64_PTABLE_BASE(vaddr);
241     }
242     if (err_is_fail(err)) {
243         return err_push(err, LIB_ERR_PMAP_GET_PTABLE);
244     }
245     assert(ptable->is_vnode);
246
247     // check if there is an overlapping mapping
248     if (has_vnode(ptable, table_base, pte_count, false)) {
249         if (has_vnode(ptable, table_base, pte_count, true)) {
250             printf("page already exists in 0x%"
251                     PRIxGENVADDR"--0x%"PRIxGENVADDR"\n", vaddr, vend);
252             return LIB_ERR_PMAP_EXISTING_MAPPING;
253         } else {
254             // clean out empty page tables. We do this here because we benefit
255             // from having the page tables in place when doing lots of small
256             // mappings
257             remove_empty_vnodes(pmap, ptable, table_base, pte_count);
258         }
259     }
260
261     // setup userspace mapping
262     struct vnode *page = slab_alloc(&pmap->slab);
263     assert(page);
264     page->is_vnode = false;
265     page->entry = table_base;
266     page->next  = ptable->u.vnode.children;
267     ptable->u.vnode.children = page;
268     page->u.frame.cap = frame;
269     page->u.frame.offset = offset;
270     page->u.frame.flags = flags;
271     page->u.frame.pte_count = pte_count;
272
273     // do map
274     err = vnode_map(ptable->u.vnode.cap, frame, table_base,
275                     pmap_flags, offset, pte_count);
276     if (err_is_fail(err)) {
277         return err_push(err, LIB_ERR_VNODE_MAP);
278     }
279
280     return SYS_ERR_OK;
281 }
282
283 /**
284  * \brief Called when enough slabs exist for the given mapping
285  */
286 static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
287                        struct capref frame, size_t offset, size_t size,
288                        vregion_flags_t flags, size_t *retoff, size_t *retsize)
289 {
290     errval_t err;
291
292     // determine page size and relevant address part
293     size_t page_size  = X86_64_BASE_PAGE_SIZE;
294     size_t table_base = X86_64_PTABLE_BASE(vaddr);
295     uint8_t map_bits  = X86_64_BASE_PAGE_BITS + X86_64_PTABLE_BITS;
296     bool debug_out    = false;
297
298     // get base address and size of frame
299     struct frame_identity fi;
300     err = invoke_frame_identify(frame, &fi);
301     if (err_is_fail(err)) {
302         return err_push(err, LIB_ERR_PMAP_DO_MAP);
303     }
304
305     if ((flags & VREGION_FLAGS_HUGE) &&
306         (vaddr & X86_64_HUGE_PAGE_MASK) == 0 &&
307         fi.bits >= X86_64_HUGE_PAGE_BITS &&
308         ((fi.base & X86_64_HUGE_PAGE_MASK) == 0))
309     {
310         // huge page branch (1GB)
311         page_size  = X86_64_HUGE_PAGE_SIZE;
312         table_base = X86_64_PDPT_BASE(vaddr);
313         map_bits   = X86_64_HUGE_PAGE_BITS + X86_64_PTABLE_BITS;
314         debug_out  = false;
315         // remove large flag, if we're doing huge mapping
316         flags     &= ~VREGION_FLAGS_LARGE;
317     } else if ((flags & VREGION_FLAGS_LARGE) &&
318                (vaddr & X86_64_LARGE_PAGE_MASK) == 0 &&
319                fi.bits >= X86_64_LARGE_PAGE_BITS &&
320                ((fi.base & X86_64_LARGE_PAGE_MASK) == 0))
321     {
322         // large page branch (2MB)
323         page_size  = X86_64_LARGE_PAGE_SIZE;
324         table_base = X86_64_PDIR_BASE(vaddr);
325         map_bits   = X86_64_LARGE_PAGE_BITS + X86_64_PTABLE_BITS;
326         debug_out  = false;
327     } else {
328         // remove large/huge flags
329         flags &= ~(VREGION_FLAGS_LARGE|VREGION_FLAGS_HUGE);
330     }
331
332     // round to the next full page and calculate end address and #ptes
333     size = ROUND_UP(size, page_size);
334     size_t pte_count = DIVIDE_ROUND_UP(size, page_size);
335     genvaddr_t vend = vaddr + size;
336
337     if (offset+size > (1ULL<<fi.bits)) {
338         debug_printf("do_map: offset=%zu; size=%zu; frame size=%zu\n",
339                 offset, size, ((size_t)1<<fi.bits));
340         return LIB_ERR_PMAP_FRAME_SIZE;
341     }
342
343 #if 0
344     if (true || debug_out) {
345         genpaddr_t paddr = fi.base + offset;
346
347         debug_printf("do_map: 0x%"
348                 PRIxGENVADDR"--0x%"PRIxGENVADDR" -> 0x%"PRIxGENPADDR
349                 "; pte_count = %zd; frame bits = %zd; page size = 0x%zx\n",
350                 vaddr, vend, paddr, pte_count, (size_t)fi.bits, page_size);
351     }
352 #endif
353
354     // all mapping on one leaf table?
355     if (is_same_pdir(vaddr, vend) ||
356         (flags & VREGION_FLAGS_LARGE && is_same_pdpt(vaddr, vend)) ||
357         (flags & VREGION_FLAGS_HUGE && is_same_pml4(vaddr, vend))) {
358         // fast path
359         if (debug_out) {
360             debug_printf("  do_map: fast path: %zd\n", pte_count);
361         }
362         err = do_single_map(pmap, vaddr, vend, frame, offset, pte_count, flags);
363         if (err_is_fail(err)) {
364             return err_push(err, LIB_ERR_PMAP_DO_MAP);
365         }
366     }
367     else { // multiple leaf page tables
368         // first leaf
369         uint32_t c = X86_64_PTABLE_SIZE - table_base;
370         if (debug_out) {
371             debug_printf("  do_map: slow path: first leaf %"PRIu32"\n", c);
372         }
373         genvaddr_t temp_end = vaddr + c * page_size;
374         err = do_single_map(pmap, vaddr, temp_end, frame, offset, c, flags);
375         if (err_is_fail(err)) {
376             return err_push(err, LIB_ERR_PMAP_DO_MAP);
377         }
378
379         // map full leaves
380         while (get_addr_prefix(temp_end, map_bits) <
381                 get_addr_prefix(vend, map_bits))
382         {
383             // update vars
384             vaddr = temp_end;
385             temp_end = vaddr + X86_64_PTABLE_SIZE * page_size;
386             offset += c * page_size;
387             c = X86_64_PTABLE_SIZE;
388             // copy cap
389             struct capref next;
390             err = slot_alloc(&next);
391             if (err_is_fail(err)) {
392                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
393             }
394             err = cap_copy(next, frame);
395             if (err_is_fail(err)) {
396                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
397             }
398             frame = next;
399
400             // do mapping
401             if (debug_out) {
402                 debug_printf("  do_map: slow path: full leaf\n");
403             }
404             err = do_single_map(pmap, vaddr, temp_end, frame, offset,
405                     X86_64_PTABLE_SIZE, flags);
406             if (err_is_fail(err)) {
407                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
408             }
409         }
410
411         // map remaining part
412         offset += c * page_size;
413
414         // calculate remaining pages (subtract ptable bits from map_bits to
415         // get #ptes of last-level instead of 2nd-to-last).
416         c = get_addr_prefix(vend, map_bits-X86_64_PTABLE_BITS) -
417             get_addr_prefix(temp_end, map_bits-X86_64_PTABLE_BITS);
418
419         if (c) {
420             // copy cap
421             struct capref next;
422             err = slot_alloc(&next);
423             if (err_is_fail(err)) {
424                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
425             }
426             err = cap_copy(next, frame);
427             if (err_is_fail(err)) {
428                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
429             }
430
431             // do mapping
432             if (debug_out) {
433                 debug_printf("do_map: slow path: last leaf %"PRIu32"\n", c);
434             }
435             err = do_single_map(pmap, temp_end, vend, next, offset, c, flags);
436             if (err_is_fail(err)) {
437                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
438             }
439         }
440     }
441
442     if (retoff) {
443         *retoff = offset;
444     }
445     if (retsize) {
446         *retsize = size;
447     }
448     return SYS_ERR_OK;
449 }
450
451 /// Computer upper limit on number of slabs required to perform a mapping
452 static size_t max_slabs_for_mapping(size_t bytes)
453 {
454     size_t max_pages  = DIVIDE_ROUND_UP(bytes, X86_64_BASE_PAGE_SIZE);
455     size_t max_ptable = DIVIDE_ROUND_UP(max_pages, X86_64_PTABLE_SIZE);
456     size_t max_pdir   = DIVIDE_ROUND_UP(max_ptable, X86_64_PTABLE_SIZE);
457     size_t max_pdpt   = DIVIDE_ROUND_UP(max_pdir, X86_64_PTABLE_SIZE);
458     return max_pages + max_ptable + max_pdir + max_pdpt;
459 }
460
461 static size_t max_slabs_for_mapping_large(size_t bytes)
462 {
463     size_t max_pages  = DIVIDE_ROUND_UP(bytes, X86_64_LARGE_PAGE_SIZE);
464     size_t max_pdir   = DIVIDE_ROUND_UP(max_pages, X86_64_PTABLE_SIZE);
465     size_t max_pdpt   = DIVIDE_ROUND_UP(max_pdir, X86_64_PTABLE_SIZE);
466     return max_pages  + max_pdir + max_pdpt;
467 }
468
469 static size_t max_slabs_for_mapping_huge(size_t bytes)
470 {
471     size_t max_pages  = DIVIDE_ROUND_UP(bytes, X86_64_HUGE_PAGE_SIZE);
472     size_t max_pdpt   = DIVIDE_ROUND_UP(max_pages, X86_64_PTABLE_SIZE);
473     return max_pages  + max_pdpt;
474 }
475
476 /**
477  * \brief Refill slabs used for metadata
478  *
479  * \param pmap     The pmap to refill in
480  * \param request  The number of slabs the allocator must have
481  * when the function returns
482  *
483  * When the current pmap is initialized,
484  * it reserves some virtual address space for metadata.
485  * This reserved address space is used here
486  *
487  * Can only be called for the current pmap
488  * Will recursively call into itself till it has enough slabs
489  */
490 static errval_t refill_slabs(struct pmap_x86 *pmap, size_t request)
491 {
492     errval_t err;
493
494     /* Keep looping till we have #request slabs */
495     while (slab_freecount(&pmap->slab) < request) {
496         // Amount of bytes required for #request
497         size_t bytes = SLAB_STATIC_SIZE(request - slab_freecount(&pmap->slab),
498                                         sizeof(struct vnode));
499
500         /* Get a frame of that size */
501         struct capref cap;
502         err = frame_alloc(&cap, bytes, &bytes);
503         if (err_is_fail(err)) {
504             return err_push(err, LIB_ERR_FRAME_ALLOC);
505         }
506
507         /* If we do not have enough slabs to map the frame in, recurse */
508         size_t required_slabs_for_frame = max_slabs_for_mapping(bytes);
509         if (slab_freecount(&pmap->slab) < required_slabs_for_frame) {
510             // If we recurse, we require more slabs than to map a single page
511             assert(required_slabs_for_frame > 4);
512
513             err = refill_slabs(pmap, required_slabs_for_frame);
514             if (err_is_fail(err)) {
515                 return err_push(err, LIB_ERR_SLAB_REFILL);
516             }
517         }
518
519         /* Perform mapping */
520         genvaddr_t genvaddr = pmap->vregion_offset;
521         pmap->vregion_offset += (genvaddr_t)bytes;
522         assert(pmap->vregion_offset < vregion_get_base_addr(&pmap->vregion) +
523                vregion_get_size(&pmap->vregion));
524
525         err = do_map(pmap, genvaddr, cap, 0, bytes,
526                      VREGION_FLAGS_READ_WRITE, NULL, NULL);
527         if (err_is_fail(err)) {
528             return err_push(err, LIB_ERR_PMAP_DO_MAP);
529         }
530
531         /* Grow the slab */
532         lvaddr_t buf = vspace_genvaddr_to_lvaddr(genvaddr);
533         slab_grow(&pmap->slab, (void*)buf, bytes);
534     }
535
536     return SYS_ERR_OK;
537 }
538
539 /// Minimally refill the slab allocator
540 static errval_t min_refill_slabs(struct pmap_x86 *pmap)
541 {
542     return refill_slabs(pmap, 5);
543 }
544
545 /**
546  * \brief Create page mappings
547  *
548  * \param pmap     The pmap object
549  * \param vaddr    The virtual address to create the mapping for
550  * \param frame    The frame cap to map in
551  * \param offset   Offset into the frame cap
552  * \param size     Size of the mapping
553  * \param flags    Flags for the mapping
554  * \param retoff   If non-NULL, filled in with adjusted offset of mapped region
555  * \param retsize  If non-NULL, filled in with adjusted size of mapped region
556  */
557 static errval_t map(struct pmap *pmap, genvaddr_t vaddr, struct capref frame,
558                     size_t offset, size_t size, vregion_flags_t flags,
559                     size_t *retoff, size_t *retsize)
560 {
561     errval_t err;
562     struct pmap_x86 *x86 = (struct pmap_x86*)pmap;
563
564     struct frame_identity fi;
565     err = invoke_frame_identify(frame, &fi);
566     if (err_is_fail(err)) {
567         return err_push(err, LIB_ERR_PMAP_FRAME_IDENTIFY);
568     }
569
570     size_t max_slabs;
571     // Adjust the parameters to page boundaries
572     // TODO: overestimating needed slabs shouldn't hurt much in the long run,
573     // and would keep the code easier to read and possibly faster due to less
574     // branching
575     if ((flags & VREGION_FLAGS_LARGE) &&
576         (vaddr & X86_64_LARGE_PAGE_MASK) == 0 &&
577         (fi.base & X86_64_LARGE_PAGE_MASK) == 0 &&
578         (1UL<<fi.bits) >= offset+size) {
579         //case large pages (2MB)
580         size   += LARGE_PAGE_OFFSET(offset);
581         size    = ROUND_UP(size, LARGE_PAGE_SIZE);
582         offset -= LARGE_PAGE_OFFSET(offset);
583         max_slabs = max_slabs_for_mapping_large(size);
584     } else if ((flags & VREGION_FLAGS_HUGE) &&
585                (vaddr & X86_64_HUGE_PAGE_MASK) == 0 &&
586                (fi.base & X86_64_HUGE_PAGE_MASK) == 0 &&
587                (1UL<<fi.bits) >= offset+size) {
588         // case huge pages (1GB)
589         size   += HUGE_PAGE_OFFSET(offset);
590         size    = ROUND_UP(size, HUGE_PAGE_SIZE);
591         offset -= HUGE_PAGE_OFFSET(offset);
592         max_slabs = max_slabs_for_mapping_huge(size);
593     } else {
594         //case normal pages (4KB)
595         size   += BASE_PAGE_OFFSET(offset);
596         size    = ROUND_UP(size, BASE_PAGE_SIZE);
597         offset -= BASE_PAGE_OFFSET(offset);
598         max_slabs = max_slabs_for_mapping(size);
599     }
600
601     // Refill slab allocator if necessary
602     size_t slabs_free = slab_freecount(&x86->slab);
603
604     max_slabs += 5; // minimum amount required to map a page
605     if (slabs_free < max_slabs) {
606         struct pmap *mypmap = get_current_pmap();
607         if (pmap == mypmap) {
608             err = refill_slabs(x86, max_slabs);
609             if (err_is_fail(err)) {
610                 return err_push(err, LIB_ERR_SLAB_REFILL);
611             }
612         } else {
613             size_t bytes = SLAB_STATIC_SIZE(max_slabs - slabs_free,
614                                             sizeof(struct vnode));
615             void *buf = malloc(bytes);
616             if (!buf) {
617                 return LIB_ERR_MALLOC_FAIL;
618             }
619             slab_grow(&x86->slab, buf, bytes);
620         }
621     }
622
623     err = do_map(x86, vaddr, frame, offset, size, flags, retoff, retsize);
624     return err;
625 }
626
627 /**
628  * \brief Find mapping for `vaddr` in `pmap`.
629  * \arg pmap the pmap to search in
630  * \arg vaddr the virtual address to search for
631  * \arg pt the last-level page table meta-data we found if any
632  * \arg page the page meta-data we found if any
633  * \returns `true` iff we found a mapping for vaddr
634  */
635 static bool find_mapping(struct pmap_x86 *pmap, genvaddr_t vaddr,
636                          struct vnode **outpt, struct vnode **outpage)
637 {
638     struct vnode *pdpt = NULL, *pdir = NULL, *pt = NULL, *page = NULL;
639
640     // find page and last-level page table (can be pdir or pdpt)
641     if ((pdpt = find_pdpt(pmap, vaddr)) != NULL) {
642         page = find_vnode(pdpt, X86_64_PDPT_BASE(vaddr));
643         if (page && page->is_vnode) { // not 1G pages
644             pdir = page;
645             page = find_vnode(pdir, X86_64_PDIR_BASE(vaddr));
646             if (page && page->is_vnode) { // not 2M pages
647                 pt = page;
648                 page = find_vnode(pt, X86_64_PTABLE_BASE(vaddr));
649             } else if (page) {
650                 pt = pdir;
651             }
652         } else if (page) {
653             pt = pdpt;
654         }
655     }
656     if (outpt) {
657         *outpt = pt;
658     }
659     if (outpage) {
660         *outpage = page;
661     }
662     if (pt && page) {
663         return true;
664     } else {
665         return false;
666     }
667 }
668
669 static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr,
670                                 size_t pte_count, bool delete_cap)
671 {
672     errval_t err;
673     struct vnode *pt = NULL, *page = NULL;
674
675     if (!find_mapping(pmap, vaddr, &pt, &page)) {
676         return LIB_ERR_PMAP_FIND_VNODE;
677     }
678     assert(pt && pt->is_vnode && page && !page->is_vnode);
679
680     if (page->u.frame.pte_count == pte_count) {
681         err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap, page->entry,
682                 page->u.frame.pte_count);
683         if (err_is_fail(err)) {
684             printf("vnode_unmap returned error: %s (%d)\n",
685                     err_getstring(err), err_no(err));
686             return err_push(err, LIB_ERR_VNODE_UNMAP);
687         }
688
689         // Free up the resources
690         if (delete_cap) {
691             err = cap_destroy(page->u.frame.cap);
692             if (err_is_fail(err)) {
693                 printf("delete_cap\n");
694                 return err_push(err, LIB_ERR_PMAP_DO_SINGLE_UNMAP);
695             }
696         }
697         remove_vnode(pt, page);
698         slab_free(&pmap->slab, page);
699     }
700
701     return SYS_ERR_OK;
702 }
703
704 static inline bool is_large_page(struct vnode *p)
705 {
706     return !p->is_vnode && p->u.frame.flags & VREGION_FLAGS_LARGE;
707 }
708 static inline bool is_huge_page(struct vnode *p)
709 {
710     return !p->is_vnode && p->u.frame.flags & VREGION_FLAGS_HUGE;
711 }
712
713 /**
714  * \brief Remove page mappings
715  *
716  * \param pmap     The pmap object
717  * \param vaddr    The start of the virtual addres to remove
718  * \param size     The size of virtual address to remove
719  * \param retsize  If non-NULL, filled in with the actual size removed
720  */
721 static errval_t unmap(struct pmap *pmap, genvaddr_t vaddr, size_t size,
722                       size_t *retsize)
723 {
724     //printf("[unmap] 0x%"PRIxGENVADDR", %zu\n", vaddr, size);
725     errval_t err, ret = SYS_ERR_OK;
726     struct pmap_x86 *x86 = (struct pmap_x86*)pmap;
727
728     //determine if we unmap a larger page
729     struct vnode* page = NULL;
730
731     if (!find_mapping(x86, vaddr, NULL, &page)) {
732         //TODO: better error --> LIB_ERR_PMAP_NOT_MAPPED
733         return LIB_ERR_PMAP_UNMAP;
734     }
735
736     assert(!page->is_vnode);
737
738     size_t page_size = X86_64_BASE_PAGE_SIZE;
739     size_t table_base = X86_64_PTABLE_BASE(vaddr);
740     uint8_t map_bits= X86_64_BASE_PAGE_BITS + X86_64_PTABLE_BITS;
741     if (is_large_page(page)) {
742         //large 2M page
743         page_size = X86_64_LARGE_PAGE_SIZE;
744         table_base = X86_64_PDIR_BASE(vaddr);
745         map_bits = X86_64_LARGE_PAGE_BITS + X86_64_PTABLE_BITS;
746     } else if (is_huge_page(page)) {
747         //huge 1GB page
748         page_size = X86_64_HUGE_PAGE_SIZE;
749         table_base = X86_64_PDPT_BASE(vaddr);
750         map_bits = X86_64_HUGE_PAGE_BITS + X86_64_PTABLE_BITS;
751     }
752
753     // TODO: match new policy of map when implemented
754     size = ROUND_UP(size, page_size);
755     genvaddr_t vend = vaddr + size;
756
757     if (is_same_pdir(vaddr, vend) ||
758         (is_same_pdpt(vaddr, vend) && is_large_page(page)) ||
759         (is_same_pml4(vaddr, vend) && is_huge_page(page)))
760     {
761         // fast path
762         err = do_single_unmap(x86, vaddr, size / page_size, false);
763         if (err_is_fail(err) && err_no(err) != LIB_ERR_PMAP_FIND_VNODE) {
764             printf("error fast path\n");
765             return err_push(err, LIB_ERR_PMAP_UNMAP);
766         }
767     }
768     else { // slow path
769         // unmap first leaf
770         uint32_t c = X86_64_PTABLE_SIZE - table_base;
771
772         err = do_single_unmap(x86, vaddr, c, false);
773         if (err_is_fail(err) && err_no(err) != LIB_ERR_PMAP_FIND_VNODE) {
774             printf("error first leaf\n");
775             return err_push(err, LIB_ERR_PMAP_UNMAP);
776         }
777
778         // unmap full leaves
779         vaddr += c * page_size;
780         while (get_addr_prefix(vaddr, map_bits) < get_addr_prefix(vend, map_bits)) {
781             c = X86_64_PTABLE_SIZE;
782             err = do_single_unmap(x86, vaddr, X86_64_PTABLE_SIZE, true);
783             if (err_is_fail(err) && err_no(err) != LIB_ERR_PMAP_FIND_VNODE) {
784                 printf("error while loop\n");
785                 return err_push(err, LIB_ERR_PMAP_UNMAP);
786             }
787             vaddr += c * page_size;
788         }
789
790         // unmap remaining part
791         // subtracting ptable bits from map_bits to get #ptes in last-level table
792         // instead of 2nd-to-last.
793         c = get_addr_prefix(vend, map_bits-X86_64_PTABLE_BITS) -
794             get_addr_prefix(vaddr, map_bits-X86_64_PTABLE_BITS);
795         assert(c < X86_64_PTABLE_SIZE);
796         if (c) {
797             err = do_single_unmap(x86, vaddr, c, true);
798             if (err_is_fail(err) && err_no(err) != LIB_ERR_PMAP_FIND_VNODE) {
799                 printf("error remaining part\n");
800                 return err_push(err, LIB_ERR_PMAP_UNMAP);
801             }
802         }
803     }
804
805     if (retsize) {
806         *retsize = size;
807     }
808
809     //printf("[unmap] exiting\n");
810     return ret;
811 }
812
813 static errval_t do_single_modify_flags(struct pmap_x86 *pmap, genvaddr_t vaddr,
814                                        size_t pages, vregion_flags_t flags)
815 {
816     errval_t err = SYS_ERR_OK;
817     struct vnode *ptable = find_ptable(pmap, vaddr);
818     uint16_t ptentry = X86_64_PTABLE_BASE(vaddr);
819     if (ptable) {
820         struct vnode *page = find_vnode(ptable, ptentry);
821         if (page) {
822             if (inside_region(ptable, ptentry, pages)) {
823                 // we're modifying part of a valid mapped region
824                 // arguments to invocation: invoke frame cap, first affected
825                 // page (as offset from first page in mapping), #affected
826                 // pages, new flags. Invocation mask flags based on capability
827                 // access permissions.
828                 size_t off = ptentry - page->entry;
829                 paging_x86_64_flags_t pmap_flags = vregion_to_pmap_flag(flags);
830                 err = invoke_frame_modify_flags(page->u.frame.cap, off, pages, pmap_flags);
831                 printf("invoke_frame_modify_flags returned error: %s (%"PRIuERRV")\n",
832                         err_getstring(err), err);
833                 return err;
834             } else {
835                 // overlaps some region border
836                 return LIB_ERR_PMAP_EXISTING_MAPPING;
837             }
838         }
839     }
840     return SYS_ERR_OK;
841 }
842
843
844 /**
845  * \brief Modify page mapping
846  *
847  * \param pmap     The pmap object
848  * \param vaddr    The virtual address to unmap
849  * \param flags    New flags for the mapping
850  * \param retsize  If non-NULL, filled in with the actual size modified
851  */
852 static errval_t modify_flags(struct pmap *pmap, genvaddr_t vaddr, size_t size,
853                              vregion_flags_t flags, size_t *retsize)
854 {
855     errval_t err;
856     struct pmap_x86 *x86 = (struct pmap_x86 *)pmap;
857     size = ROUND_UP(size, X86_64_BASE_PAGE_SIZE);
858     size_t pages = size / X86_64_BASE_PAGE_SIZE;
859     genvaddr_t vend = vaddr + size;
860
861     // vaddr and vend specify begin and end of the region (inside a mapping)
862     // that should receive the new set of flags
863     //
864     // TODO: figure out page_size etc of original mapping
865     uint8_t map_bits = X86_64_BASE_PAGE_BITS + X86_64_PTABLE_BITS;
866
867     if (is_same_pdir(vaddr, vend)) {
868         // fast path
869         err = do_single_modify_flags(x86, vaddr, pages, flags);
870         if (err_is_fail(err)) {
871             return err_push(err, LIB_ERR_PMAP_MODIFY_FLAGS);
872         }
873     }
874     else { // slow path
875         // modify first part
876         uint32_t c = X86_64_PTABLE_SIZE - X86_64_PTABLE_BASE(vaddr);
877         err = do_single_modify_flags(x86, vaddr, c, flags);
878         if (err_is_fail(err)) {
879             return err_push(err, LIB_ERR_PMAP_MODIFY_FLAGS);
880         }
881
882         // modify full leaves
883         vaddr += c * X86_64_BASE_PAGE_SIZE;
884         while (get_addr_prefix(vaddr, map_bits) < get_addr_prefix(vend, map_bits)) {
885             c = X86_64_PTABLE_SIZE;
886             err = do_single_modify_flags(x86, vaddr, X86_64_PTABLE_SIZE, flags);
887             if (err_is_fail(err)) {
888                 return err_push(err, LIB_ERR_PMAP_MODIFY_FLAGS);
889             }
890             vaddr += c * X86_64_BASE_PAGE_SIZE;
891         }
892
893         // modify remaining part
894         c = X86_64_PTABLE_BASE(vend) - X86_64_PTABLE_BASE(vaddr);
895         if (c) {
896             err = do_single_modify_flags(x86, vaddr, c, flags);
897             if (err_is_fail(err)) {
898                 return err_push(err, LIB_ERR_PMAP_MODIFY_FLAGS);
899             }
900         }
901     }
902
903     if (retsize) {
904         *retsize = size;
905     }
906
907     //printf("[modify_flags] exiting\n");
908     return SYS_ERR_OK;
909 }
910
911 /**
912  * \brief Query existing page mapping
913  *
914  * \param pmap     The pmap object
915  * \param vaddr    The virtual address to query
916  * \param retvaddr Returns the base virtual address of the mapping
917  * \param retsize  Returns the actual size of the mapping
918  * \param retcap   Returns the cap mapped at this address
919  * \param retoffset Returns the offset within the cap that is mapped
920  * \param retflags Returns the flags for this mapping
921  *
922  * All of the ret parameters are optional.
923  */
924 static errval_t lookup(struct pmap *pmap, genvaddr_t vaddr,
925                        genvaddr_t *retvaddr, size_t *retsize,
926                        struct capref *retcap, genvaddr_t *retoffset,
927                        vregion_flags_t *retflags)
928 {
929     struct pmap_x86 *x86 = (struct pmap_x86 *)pmap;
930
931     uint32_t base = X86_64_PTABLE_BASE(vaddr);
932     // Find the page table
933     struct vnode *ptable = find_ptable(x86, vaddr);
934     if (ptable == NULL) {
935         //mapped in pdir?
936         ptable = find_pdir(x86, vaddr);
937         if (ptable == NULL) {
938             return LIB_ERR_PMAP_FIND_VNODE;
939         }
940         base = X86_64_PDIR_BASE(vaddr);
941     }
942
943     // Find the page
944     struct vnode *vn = find_vnode(ptable, base);
945     if (vn == NULL) {
946         return LIB_ERR_PMAP_FIND_VNODE;
947     }
948
949     if (retvaddr) {
950         *retvaddr = vaddr & ~(genvaddr_t)BASE_PAGE_MASK;
951     }
952
953     if (retsize) {
954         *retsize = BASE_PAGE_SIZE;
955     }
956
957     if (retcap) {
958         *retcap = vn->u.frame.cap;
959     }
960
961     if (retoffset) {
962         *retoffset = vn->u.frame.offset;
963     }
964
965     if (retflags) {
966         *retflags = vn->u.frame.flags;
967     }
968
969     return SYS_ERR_OK;
970 }
971
972
973
974 static errval_t dump(struct pmap *pmap, struct pmap_dump_info *buf, size_t buflen, size_t *items_written)
975 {
976     struct pmap_x86 *x86 = (struct pmap_x86 *)pmap;
977     struct pmap_dump_info *buf_ = buf;
978
979     struct vnode *pml4 = &x86->root;
980     struct vnode *pdpt, *pdir, *pt, *frame;
981     assert(pml4 != NULL);
982
983     *items_written = 0;
984
985     // iterate over PML4 entries
986     size_t pml4_index, pdpt_index, pdir_index;
987     for (pdpt = pml4->u.vnode.children; pdpt != NULL; pdpt = pdpt->next) {
988         pml4_index = pdpt->entry;
989         // iterate over pdpt entries
990         for (pdir = pdpt->u.vnode.children; pdir != NULL; pdir = pdir->next) {
991             pdpt_index = pdir->entry;
992             // iterate over pdir entries
993             for (pt = pdir->u.vnode.children; pt != NULL; pt = pt->next) {
994                 pdir_index = pt->entry;
995                 // iterate over pt entries
996                 for (frame = pt->u.vnode.children; frame != NULL; frame = frame->next) {
997                     if (*items_written < buflen) {
998                         buf_->pml4_index = pml4_index;
999                         buf_->pdpt_index = pdpt_index;
1000                         buf_->pdir_index = pdir_index;
1001                         buf_->pt_index = frame->entry;
1002                         buf_->cap = frame->u.frame.cap;
1003                         buf_->offset = frame->u.frame.offset;
1004                         buf_->flags = frame->u.frame.flags;
1005                         buf_++;
1006                         (*items_written)++;
1007                     }
1008                 }
1009             }
1010         }
1011     }
1012     return SYS_ERR_OK;
1013 }
1014
1015 static errval_t determine_addr_raw(struct pmap *pmap, size_t size,
1016                                    size_t alignment, genvaddr_t *retvaddr)
1017 {
1018     struct pmap_x86 *x86 = (struct pmap_x86 *)pmap;
1019
1020     struct vnode *walk_pml4 = x86->root.u.vnode.children;
1021     assert(walk_pml4 != NULL); // assume there's always at least one existing entry
1022
1023     if (alignment == 0) {
1024         alignment = BASE_PAGE_SIZE;
1025     } else {
1026         alignment = ROUND_UP(alignment, BASE_PAGE_SIZE);
1027     }
1028     size = ROUND_UP(size, alignment);
1029     assert(size < 512ul * 1024 * 1024 * 1024); // pml4 size
1030
1031     // try to find free pml4 entry
1032     bool f[512];
1033     for (int i = 0; i < 512; i++) {
1034         f[i] = true;
1035     }
1036     //debug_printf("entry: %d\n", walk_pml4->entry);
1037     f[walk_pml4->entry] = false;
1038     while (walk_pml4) {
1039         //debug_printf("looping over pml4 entries\n");
1040         assert(walk_pml4->is_vnode);
1041         f[walk_pml4->entry] = false;
1042         walk_pml4 = walk_pml4->next;
1043     }
1044     genvaddr_t first_free = 16;
1045     for (; first_free < 512; first_free++) {
1046         //debug_printf("f[%"PRIuGENVADDR"] = %d\n", first_free, f[first_free]);
1047         if (f[first_free]) {
1048             break;
1049         }
1050     }
1051     //debug_printf("first_free: %"PRIuGENVADDR"\n", first_free);
1052     if (first_free < 512) {
1053         //debug_printf("first_free: %"PRIuGENVADDR"\n", first_free);
1054         *retvaddr = first_free << 39;
1055         return SYS_ERR_OK;
1056     } else {
1057         return LIB_ERR_OUT_OF_VIRTUAL_ADDR;
1058     }
1059 }
1060
1061 static struct pmap_funcs pmap_funcs = {
1062     .determine_addr = pmap_x86_determine_addr,
1063     .determine_addr_raw = determine_addr_raw,
1064     .map = map,
1065     .unmap = unmap,
1066     .lookup = lookup,
1067     .modify_flags = modify_flags,
1068     .serialise = pmap_x86_serialise,
1069     .deserialise = pmap_x86_deserialise,
1070     .dump = dump,
1071 };
1072
1073 /**
1074  * \brief Initialize a x86 pmap object
1075  *
1076  * \param pmap Pmap object of type x86
1077  */
1078 errval_t pmap_x86_64_init(struct pmap *pmap, struct vspace *vspace,
1079                           struct capref vnode,
1080                           struct slot_allocator *opt_slot_alloc)
1081 {
1082     struct pmap_x86 *x86 = (struct pmap_x86*)pmap;
1083
1084     /* Generic portion */
1085     pmap->f = pmap_funcs;
1086     pmap->vspace = vspace;
1087
1088     if (opt_slot_alloc != NULL) {
1089         pmap->slot_alloc = opt_slot_alloc;
1090     } else { /* use default allocator for this dispatcher */
1091         pmap->slot_alloc = get_default_slot_allocator();
1092     }
1093
1094     /* x86 specific portion */
1095     slab_init(&x86->slab, sizeof(struct vnode), NULL);
1096     slab_grow(&x86->slab, x86->slab_buffer,
1097               sizeof(x86->slab_buffer));
1098     x86->refill_slabs = min_refill_slabs;
1099
1100     x86->root.is_vnode          = true;
1101     x86->root.u.vnode.cap       = vnode;
1102     x86->root.u.vnode.children  = NULL;
1103     x86->root.next              = NULL;
1104
1105     // choose a minimum mappable VA for most domains; enough to catch NULL
1106     // pointer derefs with suitably large offsets
1107     x86->min_mappable_va = 64 * 1024;
1108
1109     // maximum mappable VA is derived from X86_64_MEMORY_OFFSET in kernel
1110     x86->max_mappable_va = (genvaddr_t)0xffffff8000000000;
1111
1112     return SYS_ERR_OK;
1113 }
1114
1115 /**
1116  * \brief Initialize the current pmap. Reserve space for metadata
1117  *
1118  * This code is coupled with #vspace_current_init()
1119  */
1120 errval_t pmap_x86_64_current_init(bool init_domain)
1121 {
1122     struct pmap_x86 *x86 = (struct pmap_x86*)get_current_pmap();
1123
1124     // To reserve a block of virtual address space,
1125     // a vregion representing the address space is required.
1126     // We construct a superficial one here and add it to the vregion list.
1127     struct vregion *vregion = &x86->vregion;
1128     vregion->vspace = NULL;
1129     vregion->memobj = NULL;
1130     vregion->base   = META_DATA_RESERVED_BASE;
1131     vregion->offset = 0;
1132     vregion->size   = META_DATA_RESERVED_SIZE;
1133     vregion->flags  = 0;
1134     vregion->next = NULL;
1135
1136     struct vspace *vspace = x86->p.vspace;
1137     assert(!vspace->head);
1138     vspace->head = vregion;
1139
1140     x86->vregion_offset = x86->vregion.base;
1141
1142     // We don't know the vnode layout for the first part of our address space
1143     // (which was setup by the kernel), so we avoid mapping there until told it.
1144     x86->min_mappable_va = META_DATA_RESERVED_BASE;
1145
1146     return SYS_ERR_OK;
1147 }