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