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