9ded4393605dd47b7e6a9bc0fbedca81cec2f07a
[barrelfish] / lib / barrelfish / arch / arm / pmap_arch.c
1 /**
2  * \file
3  * \brief pmap management
4  */
5
6 /*
7  * Copyright (c) 2010-2013 ETH Zurich.
8  * All rights reserved.
9  *
10  * This file is distributed under the terms in the attached LICENSE file.
11  * If you do not find this file, copies can be found by writing to:
12  * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
13  */
14
15 /*
16  * There was some minor difficulty here with mapping the cpus native
17  * page table arrangement onto Barrelfish. The problem lies with
18  * resource bootstrapping. The bootstrap ram allocator allocates pages.
19  *
20  *
21  * The natural division of bits is 12/8/12, corresponding to 4K
22  * L1 entries in the L1 table and 256 L2 entries per L2
23  * table. Unfortunately 256 entries consumes 1KB rather than a
24  * page (4KB) so we pretend here and in the kernel caps page
25  * code that the L1 has 1024 entries and L2 tables are 4KB in
26  * size. The 4KB constraint comes from ram_alloc_fixed
27  * allocating single pages and the difficulty in bootstrapping
28  * cap slots (alloc_node takes a single slot.
29  *
30  * For now this suffices, but might need to be revisited in future.
31  *
32  * An earlier cut at this, used the first 1KB from each
33  * allocation made from ram_alloc_fixed and wasted the remaining
34  * space. Aside from the space wasted it entailed a couple of minor
35  * platform ifdefs to work around the discrepency.
36  *
37  * Alternative fixes discussed include:
38  *
39  * 1. avoid the need to create vnodes before connecting to a
40  *    real allocator (probably not plausible).
41  *
42  * 2. somehow make ram_alloc_fixed handle sub-page allocations
43  *    (it's clunky, but perhaps we can give each domain a separate
44  *     cnode full of 1k- sized RAM caps?)
45  *
46  * 3. handle the problem at the level of vnode_create (can't see how to
47  *    do this)
48  *
49  * 4. waste the space -- doing this cleanly will require a new parameter
50  * to retype to prevent all 4 caps being created
51  *
52  * 5. introduce a new arm-specific version of vnode_create that creates
53  * 4 1k vnodes, and is only called from the ARM VM code.
54  *
55  */
56
57 #include <barrelfish/barrelfish.h>
58 #include <barrelfish/caddr.h>
59 #include <barrelfish/invocations_arch.h>
60 #include <stdio.h>
61
62 // Location of VSpace managed by this system.
63 #ifdef __ARM_ARCH_7M__
64 //virtual section 0x40000000-0x40100000 can not be used as regular memory 
65 //because of "bit-banding".
66 //0x42000000-0x44000000 is also dangerous, so we start after that
67 //XXX: there are more virtual regions we 
68 //are not allowed to use -> find out where to reserve those
69 #define VSPACE_BEGIN   ((lvaddr_t)(1UL*1024*1024*1024 + 64UL*1024*1024))    //0x44000000
70 #else       //"normal" arm architectures
71 #define VSPACE_BEGIN   ((lvaddr_t)1UL*1024*1024*1024)   //0x40000000
72 #endif
73
74
75 // Amount of virtual address space reserved for mapping frames
76 // backing refill_slabs.
77 //#define META_DATA_RESERVED_SPACE (BASE_PAGE_SIZE * 128) // 64
78 #define META_DATA_RESERVED_SPACE (BASE_PAGE_SIZE * 256)
79 // increased above value from 128 for pandaboard port
80
81 // Convenience macros to figure out user space page table indices
82 // we use 10 bits for both L1 and L2 tables in user space, even though
83 // in hardware we use 12 bits for L1 and 8 bits for L2.
84 #define ARM_USER_L1_OFFSET(addr) ((uintptr_t)(addr >> 22) & 0x3ffu)
85 #define ARM_USER_L2_OFFSET(addr) ((uintptr_t)(addr >> 12) & 0x3ffu)
86
87 //flag for large page mapping
88 #define FLAGS_LARGE 0x0100
89
90 static inline uintptr_t
91 vregion_flags_to_kpi_paging_flags(vregion_flags_t flags)
92 {
93     STATIC_ASSERT(0x2f == VREGION_FLAGS_MASK, "");
94     STATIC_ASSERT(0x0f == KPI_PAGING_FLAGS_MASK, "");
95     STATIC_ASSERT(VREGION_FLAGS_READ    == KPI_PAGING_FLAGS_READ,    "");
96     STATIC_ASSERT(VREGION_FLAGS_WRITE   == KPI_PAGING_FLAGS_WRITE,   "");
97     STATIC_ASSERT(VREGION_FLAGS_EXECUTE == KPI_PAGING_FLAGS_EXECUTE, "");
98     STATIC_ASSERT(VREGION_FLAGS_NOCACHE == KPI_PAGING_FLAGS_NOCACHE, "");
99     if ((flags & VREGION_FLAGS_MPB) != 0) {
100         // XXX: ignore MPB flag on ARM, otherwise the assert below fires -AB
101         flags &= ~VREGION_FLAGS_MPB;
102     }
103     if ((flags & VREGION_FLAGS_GUARD) != 0) {
104         flags = 0;
105     }
106     assert(0 == (~KPI_PAGING_FLAGS_MASK & (uintptr_t)flags));
107     return (uintptr_t)flags;
108 }
109
110 /**
111  * \brief Starting at a given root, return the vnode with entry equal to #entry
112  */
113 static struct vnode *find_vnode(struct vnode *root, uint32_t entry)
114 {
115     assert(root != NULL);
116     assert(root->is_vnode);
117     struct vnode *n;
118
119     for(n = root->u.vnode.children; n != NULL; n = n->next) {
120         if(n->entry == entry) {
121             return n;
122         }
123     }
124     return NULL;
125 }
126
127 static bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
128 {
129     assert(root != NULL);
130     assert(root->is_vnode);
131
132     struct vnode *n;
133
134     for (n = root->u.vnode.children; n; n = n->next) {
135         if (!n->is_vnode) {
136             uint16_t end = n->entry + n->u.frame.pte_count;
137             if (n->entry <= entry && entry + npages <= end) {
138                 return true;
139             }
140         }
141     }
142
143     return false;
144 }
145
146 static bool has_vnode(struct vnode *root, uint32_t entry, size_t len)
147 {
148     assert(root != NULL);
149     assert(root->is_vnode);
150     struct vnode *n;
151
152     uint32_t end_entry = entry + len;
153
154     for (n = root->u.vnode.children; n; n = n->next) {
155         if (n->is_vnode && n->entry == entry) {
156             return true;
157         }
158         // n is frame
159         uint32_t end = n->entry + n->u.frame.pte_count;
160         if (n->entry < entry && end > end_entry) {
161             return true;
162         }
163         if (n->entry >= entry && n->entry < end_entry) {
164             return true;
165         }
166     }
167
168     return false;
169 }
170
171 static void remove_vnode(struct vnode *root, struct vnode *item)
172 {
173     assert(root->is_vnode);
174     struct vnode *walk = root->u.vnode.children;
175     struct vnode *prev = NULL;
176     while (walk) {
177         if (walk == item) {
178             if (prev) {
179                 prev->next = walk->next;
180                 return;
181             } else {
182                 root->u.vnode.children = walk->next;
183                 return;
184             }
185         }
186         prev = walk;
187         walk = walk->next;
188     }
189     assert(!"Should not get here");
190 }
191
192 /**
193  * \brief Allocates a new VNode, adding it to the page table and our metadata
194  */
195 static errval_t alloc_vnode(struct pmap_arm *pmap_arm, struct vnode *root,
196                             enum objtype type, uint32_t entry,
197                             struct vnode **retvnode)
198 {
199     assert(root->is_vnode);
200     errval_t err;
201
202     struct vnode *newvnode = slab_alloc(&pmap_arm->slab);
203     if (newvnode == NULL) {
204         return LIB_ERR_SLAB_ALLOC_FAIL;
205     }
206     newvnode->is_vnode = true;
207
208     // The VNode capability
209     err = slot_alloc(&newvnode->u.vnode.cap);
210     if (err_is_fail(err)) {
211         return err_push(err, LIB_ERR_SLOT_ALLOC);
212     }
213
214     err = vnode_create(newvnode->u.vnode.cap, type);
215     if (err_is_fail(err)) {
216         return err_push(err, LIB_ERR_VNODE_CREATE);
217     }
218
219     err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
220                     KPI_PAGING_FLAGS_READ | KPI_PAGING_FLAGS_WRITE, 0, 1);
221
222     if (err_is_fail(err)) {
223         return err_push(err, LIB_ERR_VNODE_MAP);
224     }
225
226     // The VNode meta data
227     newvnode->entry            = entry;
228     newvnode->next             = root->u.vnode.children;
229     root->u.vnode.children     = newvnode;
230     newvnode->u.vnode.children = NULL;
231
232     if (retvnode) {
233         *retvnode = newvnode;
234     }
235     return SYS_ERR_OK;
236 }
237
238 /**
239  * \brief Returns the vnode for the pagetable mapping a given vspace address
240  */
241 static errval_t get_ptable(struct pmap_arm  *pmap,
242                            genvaddr_t        vaddr,
243                            struct vnode    **ptable)
244 {
245     // NB Strictly there are 12 bits in the ARM L1, but allocations unit
246     // of L2 is 1 page of L2 entries (4 tables) so we use 10 bits for the L1
247     // index here
248     uintptr_t index = ARM_USER_L1_OFFSET(vaddr);
249     if ((*ptable = find_vnode(&pmap->root, index)) == NULL)
250     {
251         // L1 table entries point to L2 tables so allocate an L2
252         // table for this L1 entry.
253
254         struct vnode *tmp = NULL; // Tmp variable for passing to alloc_vnode
255
256         errval_t err = alloc_vnode(pmap, &pmap->root, ObjType_VNode_ARM_l2,
257                                    index, &tmp);
258         if (err_is_fail(err)) {
259             DEBUG_ERR(err, "alloc_vnode");
260             return err;
261         }
262         assert(tmp != NULL);
263         *ptable = tmp; // Set argument to received value
264
265
266         if (err_is_fail(err)) {
267             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
268         }
269     }
270
271     return SYS_ERR_OK;
272 }
273 /**
274  * \brief Returns the vnode for the TODO pdir mapping a given vspace address
275  */
276 static errval_t get_pdir(struct pmap_arm  *pmap,
277                            genvaddr_t        vaddr,
278                            struct vnode    **ptable)
279 {
280     // NB Strictly there are 12 bits in the ARM L1, but allocations unit
281     // of L2 is 1 page of L2 entries (4 tables) so we use 10 bits for the L1
282     // index here
283     uintptr_t index = ARM_USER_L1_OFFSET(vaddr);
284     if ((*ptable = find_vnode(&pmap->root, index)) == NULL)
285     {
286         // L1 table entries point to L2 tables so allocate an L2
287         // table for this L1 entry.
288
289         struct vnode *tmp = NULL; // Tmp variable for passing to alloc_vnode
290
291         errval_t err = alloc_vnode(pmap, &pmap->root, ObjType_VNode_ARM_l2,
292                                    index, &tmp);
293         if (err_is_fail(err)) {
294             DEBUG_ERR(err, "alloc_vnode");
295             return err;
296         }
297         assert(tmp != NULL);
298         *ptable = tmp; // Set argument to received value
299
300
301         if (err_is_fail(err)) {
302             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
303         }
304     }
305
306     return SYS_ERR_OK;
307 }
308
309
310 static struct vnode *find_ptable(struct pmap_arm  *pmap,
311                                  genvaddr_t vaddr)
312 {
313     // NB Strictly there are 12 bits in the ARM L1, but allocations unit
314     // of L2 is 1 page of L2 entries (4 tables) so
315     uintptr_t index = ARM_USER_L1_OFFSET(vaddr);
316     return find_vnode(&pmap->root, index);
317 }
318
319 static errval_t do_single_map(struct pmap_arm *pmap, genvaddr_t vaddr, genvaddr_t vend,
320                               struct capref frame, size_t offset, size_t pte_count,
321                               vregion_flags_t flags)
322 {
323     // Get the page table
324     struct vnode *ptable;
325     errval_t err;
326     if (flags&FLAGS_LARGE)
327     {
328         //large page mapping
329         err = get_pdir(pmap, vaddr, &ptable);
330         flags &= ~(FLAGS_LARGE);
331     }
332     else
333     {
334         //normal 4k mapping
335         err = get_ptable(pmap, vaddr, &ptable);
336     }
337     if (err_is_fail(err)) {
338         return err_push(err, LIB_ERR_PMAP_GET_PTABLE);
339     }
340     uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags);
341     // XXX: reassess the following note -SG
342     // NOTE: strictly speaking a l2 entry only has 8 bits, but due to the way
343     // Barrelfish allocates l1 and l2 tables, we use 10 bits for the tracking
344     // index here and in the map syscall
345     uintptr_t index = ARM_USER_L2_OFFSET(vaddr);
346     // Create user level datastructure for the mapping
347     bool has_page = has_vnode(ptable, index, pte_count);
348     assert(!has_page);
349     struct vnode *page = slab_alloc(&pmap->slab);
350     assert(page);
351     page->is_vnode = false;
352     page->entry = index;
353     page->next  = ptable->u.vnode.children;
354     ptable->u.vnode.children = page;
355     page->u.frame.cap = frame;
356     page->u.frame.pte_count = pte_count;
357
358     // Map entry into the page table
359     err = vnode_map(ptable->u.vnode.cap, frame, index,
360                     pmap_flags, offset, pte_count);
361     if (err_is_fail(err)) {
362         return err_push(err, LIB_ERR_VNODE_MAP);
363     }
364     return SYS_ERR_OK;
365 }
366
367 static errval_t do_map(struct pmap_arm *pmap, genvaddr_t vaddr,
368                        struct capref frame, size_t offset, size_t size,
369                        vregion_flags_t flags, size_t *retoff, size_t *retsize)
370 {
371     errval_t err;
372     
373     size_t page_size;
374     if (flags&FLAGS_LARGE)
375     {
376         //L2 mapping
377 //        page_size = LARGE_PAGE_SIZE;
378     }
379     else
380     {
381         //normal 4k mapping
382         page_size = BASE_PAGE_SIZE;
383     }
384     size = ROUND_UP(size, page_size);
385     size_t pte_count = DIVIDE_ROUND_UP(size, page_size);
386
387     genvaddr_t vend = vaddr + size;
388
389     if (ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) {
390         // fast path
391         err = do_single_map(pmap, vaddr, vend, frame, offset, pte_count, flags);
392         if (err_is_fail(err)) {
393             DEBUG_ERR(err, "[do_map] in fast path");
394             return err_push(err, LIB_ERR_PMAP_DO_MAP);
395         }
396     } else { // multiple leaf page tables
397         // first leaf
398         uint32_t c = ARM_L2_MAX_ENTRIES - ARM_L2_OFFSET(vaddr);
399         genvaddr_t temp_end = vaddr + c * page_size;
400         err = do_single_map(pmap, vaddr, temp_end, frame, offset, c, flags);
401         if (err_is_fail(err)) {
402             return err_push(err, LIB_ERR_PMAP_DO_MAP);
403         }
404
405         // map full leaves
406         while (ARM_L1_OFFSET(temp_end) < ARM_L1_OFFSET(vend)) { // update vars
407             vaddr = temp_end;
408             temp_end = vaddr + ARM_L2_MAX_ENTRIES * page_size;
409             offset += c * page_size;
410             c = ARM_L2_MAX_ENTRIES;
411             // copy cap
412             struct capref next;
413             err = slot_alloc(&next);
414             if (err_is_fail(err)) {
415                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
416             }
417             err = cap_copy(next, frame);
418             if (err_is_fail(err)) {
419                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
420             }
421             frame = next;
422
423             // do mapping
424             err = do_single_map(pmap, vaddr, temp_end, frame, offset, ARM_L2_MAX_ENTRIES, flags);
425             if (err_is_fail(err)) {
426                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
427             }
428         }
429
430         // map remaining part
431         offset += c * page_size;
432         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(temp_end);
433         if (c) {
434             // copy cap
435             struct capref next;
436             err = slot_alloc(&next);
437             if (err_is_fail(err)) {
438                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
439             }
440             err = cap_copy(next, frame);
441             if (err_is_fail(err)) {
442                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
443             }
444
445             // do mapping
446             err = do_single_map(pmap, temp_end, vend, next, offset, c, flags);
447             if (err_is_fail(err)) {
448                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
449             }
450         }
451     }
452     if (retoff) {
453         *retoff = offset;
454     }
455     if (retsize) {
456         *retsize = size;
457     }
458     //has_vnode_debug = false;
459     return SYS_ERR_OK;
460 #if 0
461     errval_t err;
462     uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags);
463
464     for (size_t i = offset; i < offset + size; i += BASE_PAGE_SIZE) {
465
466         vaddr += BASE_PAGE_SIZE;
467     }
468
469     if (retoff) {
470         *retoff = offset;
471     }
472     if (retsize) {
473         *retsize = size;
474     }
475     return SYS_ERR_OK;
476 #endif
477 }
478
479 static size_t
480 max_slabs_required(size_t bytes)
481 {
482     // Perform a slab allocation for every page (do_map -> slab_alloc)
483     size_t pages     = DIVIDE_ROUND_UP(bytes, BASE_PAGE_SIZE);
484     // Perform a slab allocation for every L2 (get_ptable -> find_vnode)
485     size_t l2entries = DIVIDE_ROUND_UP(pages, 256 * 4);
486     // Perform a slab allocation for every L1 (do_map -> find_vnode)
487     size_t l1entries = DIVIDE_ROUND_UP(l2entries, 1024);
488     return pages + l2entries + l1entries;
489 }
490
491 /**
492  * \brief Refill slabs used for metadata
493  *
494  * \param pmap     The pmap to refill in
495  * \param request  The number of slabs the allocator must have
496  * when the function returns
497  *
498  * When the current pmap is initialized,
499  * it reserves some virtual address space for metadata.
500  * This reserved address space is used here
501  *
502  * Can only be called for the current pmap
503  * Will recursively call into itself till it has enough slabs
504  */
505 #include <stdio.h>
506 static errval_t refill_slabs(struct pmap_arm *pmap, size_t request)
507 {
508     errval_t err;
509
510     /* Keep looping till we have #request slabs */
511     while (slab_freecount(&pmap->slab) < request) {
512         // Amount of bytes required for #request
513         size_t bytes = SLAB_STATIC_SIZE(request - slab_freecount(&pmap->slab),
514                                         sizeof(struct vnode));
515
516         /* Get a frame of that size */
517         struct capref cap;
518         err = frame_alloc(&cap, bytes, &bytes);
519         if (err_is_fail(err)) {
520             return err_push(err, LIB_ERR_FRAME_ALLOC);
521         }
522
523         /* If we do not have enough slabs to map the frame in, recurse */
524         size_t required_slabs_for_frame = max_slabs_required(bytes);
525         if (slab_freecount(&pmap->slab) < required_slabs_for_frame) {
526             // If we recurse, we require more slabs than to map a single page
527             assert(required_slabs_for_frame > 4);
528
529             err = refill_slabs(pmap, required_slabs_for_frame);
530             if (err_is_fail(err)) {
531                 return err_push(err, LIB_ERR_SLAB_REFILL);
532             }
533         }
534
535         /* Perform mapping */
536         genvaddr_t genvaddr = pmap->vregion_offset;
537         pmap->vregion_offset += (genvaddr_t)bytes;
538
539         // if this assert fires, increase META_DATA_RESERVED_SPACE
540         assert(pmap->vregion_offset < (vregion_get_base_addr(&pmap->vregion) +
541                vregion_get_size(&pmap->vregion)));
542
543         err = do_map(pmap, genvaddr, cap, 0, bytes,
544                      VREGION_FLAGS_READ_WRITE, NULL, NULL);
545         if (err_is_fail(err)) {
546             return err_push(err, LIB_ERR_PMAP_DO_MAP);
547         }
548
549         /* Grow the slab */
550         lvaddr_t buf = vspace_genvaddr_to_lvaddr(genvaddr);
551         slab_grow(&pmap->slab, (void*)buf, bytes);
552     }
553
554     return SYS_ERR_OK;
555 }
556
557 /**
558  * \brief Create page mappings
559  *
560  * \param pmap     The pmap object
561  * \param vaddr    The virtual address to create the mapping for
562  * \param frame    The frame cap to map in
563  * \param offset   Offset into the frame cap
564  * \param size     Size of the mapping
565  * \param flags    Flags for the mapping
566  * \param retoff   If non-NULL, filled in with adjusted offset of mapped region
567  * \param retsize  If non-NULL, filled in with adjusted size of mapped region
568  */
569 static errval_t
570 map(struct pmap     *pmap,
571     genvaddr_t       vaddr,
572     struct capref    frame,
573     size_t           offset,
574     size_t           size,
575     vregion_flags_t  flags,
576     size_t          *retoff,
577     size_t          *retsize)
578 {
579     struct pmap_arm *pmap_arm = (struct pmap_arm *)pmap;
580
581     if(flags&FLAGS_LARGE)
582     {
583         //large page mapping
584         //size += LARGE_PAGE_OFFSET(offset);
585         //size = ROUND_UP(size, LARGE_PAGE_SIZE);
586         //offset -= LARGE_PAGE_OFFSET(offset);
587     }
588     else
589     {
590         //4k mapping
591         size   += BASE_PAGE_OFFSET(offset);
592         size    = ROUND_UP(size, BASE_PAGE_SIZE);
593         offset -= BASE_PAGE_OFFSET(offset);
594     }
595     
596     const size_t slabs_reserve = 3; // == max_slabs_required(1)
597     uint64_t  slabs_free       = slab_freecount(&pmap_arm->slab);
598     size_t    slabs_required   = max_slabs_required(size) + slabs_reserve;
599
600     if (slabs_required > slabs_free) {
601         if (get_current_pmap() == pmap) {
602             errval_t err = refill_slabs(pmap_arm, slabs_required);
603             if (err_is_fail(err)) {
604                 return err_push(err, LIB_ERR_SLAB_REFILL);
605             }
606         }
607         else {
608             size_t bytes = SLAB_STATIC_SIZE(slabs_required - slabs_free,
609                                             sizeof(struct vnode));
610             void *buf = malloc(bytes);
611             if (!buf) {
612                 return LIB_ERR_MALLOC_FAIL;
613             }
614             slab_grow(&pmap_arm->slab, buf, bytes);
615         }
616     }
617
618     return do_map(pmap_arm, vaddr, frame, offset, size, flags,
619                   retoff, retsize);
620 }
621
622 static errval_t do_single_unmap(struct pmap_arm *pmap, genvaddr_t vaddr,
623                                 size_t pte_count, bool delete_cap)
624 {
625     errval_t err;
626     struct vnode *pt = find_ptable(pmap, vaddr);
627     if (pt) {
628         // analog to do_single_map we use 10 bits for tracking pages in user space -SG
629         struct vnode *page = find_vnode(pt, ARM_USER_L2_OFFSET(vaddr));
630         if (page && page->u.frame.pte_count == pte_count) {
631             err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap,
632                               page->entry, page->u.frame.pte_count);
633             if (err_is_fail(err)) {
634                 DEBUG_ERR(err, "vnode_unmap");
635                 return err_push(err, LIB_ERR_VNODE_UNMAP);
636             }
637
638             // Free up the resources
639             if (delete_cap) {
640                 err = cap_destroy(page->u.frame.cap);
641                 if (err_is_fail(err)) {
642                     return err_push(err, LIB_ERR_PMAP_DO_SINGLE_UNMAP);
643                 }
644             }
645             remove_vnode(pt, page);
646             slab_free(&pmap->slab, page);
647         }
648         else {
649             return LIB_ERR_PMAP_FIND_VNODE;
650         }
651     }
652
653     return SYS_ERR_OK;
654 }
655
656 /**
657  * \brief Remove page mappings
658  *
659  * \param pmap     The pmap object
660  * \param vaddr    The start of the virtual addres to remove
661  * \param size     The size of virtual address to remove
662  * \param retsize  If non-NULL, filled in with the actual size removed
663  */
664 static errval_t
665 unmap(struct pmap *pmap,
666       genvaddr_t   vaddr,
667       size_t       size,
668       size_t      *retsize)
669 {
670     errval_t err, ret = SYS_ERR_OK;
671     struct pmap_arm *pmap_arm = (struct pmap_arm*)pmap;
672     size = ROUND_UP(size, BASE_PAGE_SIZE);
673     size_t pte_count = size / BASE_PAGE_SIZE;
674     genvaddr_t vend = vaddr + size;
675
676     if (ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) {
677         // fast path
678         err = do_single_unmap(pmap_arm, vaddr, pte_count, false);
679         if (err_is_fail(err)) {
680             return err_push(err, LIB_ERR_PMAP_UNMAP);
681         }
682     } else { // slow path
683         // unmap first leaf
684         uint32_t c = ARM_L2_MAX_ENTRIES - ARM_L2_OFFSET(vaddr);
685         err = do_single_unmap(pmap_arm, vaddr, c, false);
686         if (err_is_fail(err)) {
687             return err_push(err, LIB_ERR_PMAP_UNMAP);
688         }
689
690         // unmap full leaves
691         vaddr += c * BASE_PAGE_SIZE;
692         while (ARM_L1_OFFSET(vaddr) < ARM_L1_OFFSET(vend)) {
693             c = ARM_L2_MAX_ENTRIES;
694             err = do_single_unmap(pmap_arm, vaddr, c, true);
695             if (err_is_fail(err)) {
696                 return err_push(err, LIB_ERR_PMAP_UNMAP);
697             }
698             vaddr += c * BASE_PAGE_SIZE;
699         }
700
701         // unmap remaining part
702         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(vaddr);
703         if (c) {
704             err = do_single_unmap(pmap_arm, vaddr, c, true);
705             if (err_is_fail(err)) {
706                 return err_push(err, LIB_ERR_PMAP_UNMAP);
707             }
708         }
709     }
710
711     if (retsize) {
712         *retsize = size;
713     }
714
715     return ret;
716 }
717
718 /**
719  * \brief Determine a suitable address for a given memory object
720  *
721  * \param pmap    The pmap object
722  * \param memobj  The memory object to determine the address for
723  * \param alignment Minimum alignment
724  * \param vaddr   Pointer to return the determined address
725  *
726  * Relies on vspace.c code maintaining an ordered list of vregions
727  */
728 static errval_t
729 determine_addr(struct pmap   *pmap,
730                struct memobj *memobj,
731                size_t        alignment,
732                genvaddr_t    *vaddr)
733 {
734     assert(pmap->vspace->head);
735
736     assert(alignment <= BASE_PAGE_SIZE); // NYI
737
738     struct vregion *walk = pmap->vspace->head;
739     while (walk->next) { // Try to insert between existing mappings
740         genvaddr_t walk_base = vregion_get_base_addr(walk);
741         genvaddr_t walk_size = vregion_get_size(walk);
742         genvaddr_t next_base = vregion_get_base_addr(walk->next);
743
744         if (next_base > walk_base + walk_size + memobj->size &&
745             walk_base + walk_size > VSPACE_BEGIN) { // Ensure mappings are larger than VSPACE_BEGIN
746             *vaddr = walk_base + walk_size;
747             return SYS_ERR_OK;
748         }
749         walk = walk->next;
750     }
751
752     *vaddr = vregion_get_base_addr(walk) + vregion_get_size(walk);
753     return SYS_ERR_OK;
754 }
755
756 static errval_t do_single_modify_flags(struct pmap_arm *pmap, genvaddr_t vaddr,
757                                        size_t pages, vregion_flags_t flags)
758 {
759     errval_t err = SYS_ERR_OK;
760     struct vnode *ptable = find_ptable(pmap, vaddr);
761     uint16_t ptentry = ARM_USER_L2_OFFSET(vaddr);
762     if (ptable) {
763         struct vnode *page = find_vnode(ptable, ptentry);
764         if (page) {
765             if (inside_region(ptable, ptentry, pages)) {
766                 // we're modifying part of a valid mapped region
767                 // arguments to invocation: invoke frame cap, first affected
768                 // page (as offset from first page in mapping), #affected
769                 // pages, new flags. Invocation should check compatibility of
770                 // new set of flags with cap permissions.
771                 size_t off = ptentry - page->entry;
772                 uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags);
773                 err = invoke_frame_modify_flags(page->u.frame.cap, off, pages, pmap_flags);
774                 printf("invoke_frame_modify_flags returned error: %s (%"PRIuERRV")\n",
775                         err_getstring(err), err);
776                 return err;
777             } else {
778                 // overlaps some region border
779                 return LIB_ERR_PMAP_EXISTING_MAPPING;
780             }
781         }
782     }
783     return SYS_ERR_OK;
784 }
785
786 /**
787  * \brief Modify page mapping
788  *
789  * \param pmap     The pmap object
790  * \param vaddr    The virtual address to unmap
791  * \param flags    New flags for the mapping
792  * \param retsize  If non-NULL, filled in with the actual size modified
793  */
794 static errval_t
795 modify_flags(struct pmap     *pmap,
796              genvaddr_t       vaddr,
797              size_t           size,
798              vregion_flags_t  flags,
799              size_t          *retsize)
800 {
801     errval_t err, ret = SYS_ERR_OK;
802     struct pmap_arm *pmap_arm = (struct pmap_arm*)pmap;
803     size = ROUND_UP(size, BASE_PAGE_SIZE);
804     size_t pte_count = size / BASE_PAGE_SIZE;
805     genvaddr_t vend = vaddr + size;
806
807     if (ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) {
808         // fast path
809         err = do_single_modify_flags(pmap_arm, vaddr, pte_count, false);
810         if (err_is_fail(err)) {
811             return err_push(err, LIB_ERR_PMAP_UNMAP);
812         }
813     }
814     else { // slow path
815         // unmap first leaf
816         uint32_t c = ARM_L2_MAX_ENTRIES - ARM_L2_OFFSET(vaddr);
817         err = do_single_modify_flags(pmap_arm, vaddr, c, false);
818         if (err_is_fail(err)) {
819             return err_push(err, LIB_ERR_PMAP_UNMAP);
820         }
821
822         // unmap full leaves
823         vaddr += c * BASE_PAGE_SIZE;
824         while (ARM_L1_OFFSET(vaddr) < ARM_L1_OFFSET(vend)) {
825             c = ARM_L2_MAX_ENTRIES;
826             err = do_single_modify_flags(pmap_arm, vaddr, c, true);
827             if (err_is_fail(err)) {
828                 return err_push(err, LIB_ERR_PMAP_UNMAP);
829             }
830             vaddr += c * BASE_PAGE_SIZE;
831         }
832
833         // unmap remaining part
834         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(vaddr);
835         if (c) {
836             err = do_single_modify_flags(pmap_arm, vaddr, c, true);
837             if (err_is_fail(err)) {
838                 return err_push(err, LIB_ERR_PMAP_UNMAP);
839             }
840         }
841     }
842
843     if (retsize) {
844         *retsize = size;
845     }
846
847     return ret;
848 }
849
850 /**
851  * \brief Query existing page mapping
852  *
853  * \param pmap     The pmap object
854  * \param vaddr    The virtual address to query
855  * \param retvaddr Returns the base virtual address of the mapping
856  * \param retsize  Returns the actual size of the mapping
857  * \param retcap   Returns the cap mapped at this address
858  * \param retoffset Returns the offset within the cap that is mapped
859  * \param retflags Returns the flags for this mapping
860  *
861  * All of the ret parameters are optional.
862  */
863 static errval_t lookup(struct pmap *pmap, genvaddr_t vaddr,
864                        genvaddr_t *retvaddr, size_t *retsize,
865                        struct capref *retcap, genvaddr_t *retoffset,
866                        vregion_flags_t *retflags)
867 {
868     USER_PANIC("NYI");
869     return 0;
870 }
871
872
873 static errval_t
874 serialise(struct pmap *pmap, void *buf, size_t buflen)
875 {
876     // Unimplemented: ignored
877     return SYS_ERR_OK;
878 }
879
880 static errval_t
881 deserialise(struct pmap *pmap, void *buf, size_t buflen)
882 {
883     // Unimplemented: we start with an empty pmap, and avoid the bottom of the A/S
884     return SYS_ERR_OK;
885 }
886
887 static struct pmap_funcs pmap_funcs = {
888     .determine_addr = determine_addr,
889     .map = map,
890     .unmap = unmap,
891     .modify_flags = modify_flags,
892     .lookup = lookup,
893     .serialise = serialise,
894     .deserialise = deserialise,
895 };
896
897 /**
898  * \brief Initialize the pmap object
899  */
900 errval_t
901 pmap_init(struct pmap   *pmap,
902           struct vspace *vspace,
903           struct capref  vnode,
904           struct slot_allocator *opt_slot_alloc)
905 {
906     struct pmap_arm* pmap_arm = (struct pmap_arm*)pmap;
907
908     /* Generic portion */
909     pmap->f = pmap_funcs;
910     pmap->vspace = vspace;
911
912     // Slab allocator for vnodes
913     slab_init(&pmap_arm->slab, sizeof(struct vnode), NULL);
914     slab_grow(&pmap_arm->slab,
915               pmap_arm->slab_buffer,
916               sizeof(pmap_arm->slab_buffer));
917
918     pmap_arm->root.is_vnode         = true;
919     pmap_arm->root.u.vnode.cap      = vnode;
920     pmap_arm->root.next             = NULL;
921     pmap_arm->root.u.vnode.children = NULL;
922
923     return SYS_ERR_OK;
924 }
925
926 errval_t pmap_current_init(bool init_domain)
927 {
928     struct pmap_arm *pmap_arm = (struct pmap_arm*)get_current_pmap();
929
930     // To reserve a block of virtual address space,
931     // a vregion representing the address space is required.
932     // We construct a superficial one here and add it to the vregion list.
933     struct vregion *vregion = &pmap_arm->vregion;
934     assert((void*)vregion > (void*)pmap_arm);
935     assert((void*)vregion < (void*)(pmap_arm + 1));
936     vregion->vspace = NULL;
937     vregion->memobj = NULL;
938     vregion->base   = VSPACE_BEGIN;
939     vregion->offset = 0;
940     vregion->size   = META_DATA_RESERVED_SPACE;
941     vregion->flags  = 0;
942     vregion->next = NULL;
943
944     struct vspace *vspace = pmap_arm->p.vspace;
945     assert(!vspace->head);
946     vspace->head = vregion;
947
948     pmap_arm->vregion_offset = pmap_arm->vregion.base;
949
950     return SYS_ERR_OK;
951 }