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