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