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