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