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