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