git.barrelfish.org Git - barrelfish/blob - 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/10/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 //large mapping flags
  88 #define FLAGS_LARGE        0x0100
  89 #define FLAGS_SECTION      0x0200
  90 #define FLAGS_SUPERSECTION 0x0300
  91
  92 static inline uintptr_t
  93 vregion_flags_to_kpi_paging_flags(vregion_flags_t flags)
  94 {
  95     STATIC_ASSERT(0x2f == VREGION_FLAGS_MASK, "");
  96     STATIC_ASSERT(0x0f == KPI_PAGING_FLAGS_MASK, "");
  97     STATIC_ASSERT(VREGION_FLAGS_READ    == KPI_PAGING_FLAGS_READ,    "");
  98     STATIC_ASSERT(VREGION_FLAGS_WRITE   == KPI_PAGING_FLAGS_WRITE,   "");
  99     STATIC_ASSERT(VREGION_FLAGS_EXECUTE == KPI_PAGING_FLAGS_EXECUTE, "");
 100     STATIC_ASSERT(VREGION_FLAGS_NOCACHE == KPI_PAGING_FLAGS_NOCACHE, "");
 101     if ((flags & VREGION_FLAGS_MPB) != 0) {
 102         // XXX: ignore MPB flag on ARM, otherwise the assert below fires -AB
 103         flags &= ~VREGION_FLAGS_MPB;
 104     }
 105     if ((flags & VREGION_FLAGS_GUARD) != 0) {
 106         flags = 0;
 107     }
 108     assert(0 == (~KPI_PAGING_FLAGS_MASK & (uintptr_t)flags));
 109     return (uintptr_t)flags;
 110 }
 111
 112 /**
 113  * \brief Starting at a given root, return the vnode with entry equal to #entry
 114  */
 115 static struct vnode *find_vnode(struct vnode *root, uint32_t entry)
 116 {
 117     assert(root != NULL);
 118     assert(root->is_vnode);
 119     struct vnode *n;
 120
 121     for(n = root->u.vnode.children; n != NULL; n = n->next) {
 122         if(n->entry == entry) {
 123             return n;
 124         }
 125     }
 126     return NULL;
 127 }
 128
 129 static bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
 130 {
 131     assert(root != NULL);
 132     assert(root->is_vnode);
 133
 134     struct vnode *n;
 135
 136     for (n = root->u.vnode.children; n; n = n->next) {
 137         if (!n->is_vnode) {
 138             uint16_t end = n->entry + n->u.frame.pte_count;
 139             if (n->entry <= entry && entry + npages <= end) {
 140                 return true;
 141             }
 142         }
 143     }
 144
 145     return false;
 146 }
 147
 148 static bool has_vnode(struct vnode *root, uint32_t entry, size_t len)
 149 {
 150     assert(root != NULL);
 151     assert(root->is_vnode);
 152     struct vnode *n;
 153
 154     uint32_t end_entry = entry + len;
 155
 156     for (n = root->u.vnode.children; n; n = n->next) {
 157         if (n->is_vnode && n->entry == entry) {
 158             return true;
 159         }
 160         // n is frame
 161         uint32_t end = n->entry + n->u.frame.pte_count;
 162         if (n->entry < entry && end > end_entry) {
 163             return true;
 164         }
 165         if (n->entry >= entry && n->entry < end_entry) {
 166             return true;
 167         }
 168     }
 169
 170     return false;
 171 }
 172
 173 static void remove_vnode(struct vnode *root, struct vnode *item)
 174 {
 175     assert(root->is_vnode);
 176     struct vnode *walk = root->u.vnode.children;
 177     struct vnode *prev = NULL;
 178     while (walk) {
 179         if (walk == item) {
 180             if (prev) {
 181                 prev->next = walk->next;
 182                 return;
 183             } else {
 184                 root->u.vnode.children = walk->next;
 185                 return;
 186             }
 187         }
 188         prev = walk;
 189         walk = walk->next;
 190     }
 191     assert(!"Should not get here");
 192 }
 193
 194 /**
 195  * \brief Allocates a new VNode, adding it to the page table and our metadata
 196  */
 197 static errval_t alloc_vnode(struct pmap_arm *pmap_arm, struct vnode *root,
 198                             enum objtype type, uint32_t entry,
 199                             struct vnode **retvnode)
 200 {
 201     assert(root->is_vnode);
 202     errval_t err;
 203
 204     struct vnode *newvnode = slab_alloc(&pmap_arm->slab);
 205     if (newvnode == NULL) {
 206         return LIB_ERR_SLAB_ALLOC_FAIL;
 207     }
 208     newvnode->is_vnode = true;
 209
 210     // The VNode capability
 211     err = slot_alloc(&newvnode->u.vnode.cap);
 212     if (err_is_fail(err)) {
 213         return err_push(err, LIB_ERR_SLOT_ALLOC);
 214     }
 215
 216     err = vnode_create(newvnode->u.vnode.cap, type);
 217     if (err_is_fail(err)) {
 218         return err_push(err, LIB_ERR_VNODE_CREATE);
 219     }
 220
 221     err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
 222                     KPI_PAGING_FLAGS_READ | KPI_PAGING_FLAGS_WRITE, 0, 1);
 223
 224     if (err_is_fail(err)) {
 225         return err_push(err, LIB_ERR_VNODE_MAP);
 226     }
 227
 228     // The VNode meta data
 229     newvnode->entry            = entry;
 230     newvnode->next             = root->u.vnode.children;
 231     root->u.vnode.children     = newvnode;
 232     newvnode->u.vnode.children = NULL;
 233
 234     if (retvnode) {
 235         *retvnode = newvnode;
 236     }
 237     return SYS_ERR_OK;
 238 }
 239
 240 /**
 241  * \brief Returns the vnode for the pagetable mapping a given vspace address
 242  */
 243 static errval_t get_ptable(struct pmap_arm  *pmap,
 244                            genvaddr_t        vaddr,
 245                            struct vnode    **ptable)
 246 {
 247     // NB Strictly there are 12 bits in the ARM L1, but allocations unit
 248     // of L2 is 1 page of L2 entries (4 tables) so we use 10 bits for the L1
 249     // index here
 250     uintptr_t index = ARM_USER_L1_OFFSET(vaddr);
 251     if ((*ptable = find_vnode(&pmap->root, index)) == NULL)
 252     {
 253         // L1 table entries point to L2 tables so allocate an L2
 254         // table for this L1 entry.
 255
 256         struct vnode *tmp = NULL; // Tmp variable for passing to alloc_vnode
 257
 258         errval_t err = alloc_vnode(pmap, &pmap->root, ObjType_VNode_ARM_l2,
 259                                    index, &tmp);
 260         if (err_is_fail(err)) {
 261             DEBUG_ERR(err, "alloc_vnode");
 262             return err;
 263         }
 264         assert(tmp != NULL);
 265         *ptable = tmp; // Set argument to received value
 266
 267
 268         if (err_is_fail(err)) {
 269             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
 270         }
 271     }
 272
 273     return SYS_ERR_OK;
 274 }
 275
 276 static struct vnode *find_ptable(struct pmap_arm  *pmap,
 277                                  genvaddr_t vaddr)
 278 {
 279     // NB Strictly there are 12 bits in the ARM L1, but allocations unit
 280     // of L2 is 1 page of L2 entries (4 tables) so
 281     uintptr_t index = ARM_USER_L1_OFFSET(vaddr);
 282     return find_vnode(&pmap->root, index);
 283 }
 284
 285 static errval_t do_single_map(struct pmap_arm *pmap, genvaddr_t vaddr, genvaddr_t vend,
 286                               struct capref frame, size_t offset, size_t pte_count,
 287                               vregion_flags_t flags)
 288 {
 289     errval_t err = SYS_ERR_OK;
 290     // Get the page table
 291     struct vnode *ptable;
 292     uintptr_t index;
 293     if (flags&FLAGS_SECTION) {
 294         //section mapping (1MB)
 295         //mapped in the L1 table at root
 296         ptable = &pmap->root;
 297         index = ARM_USER_L1_OFFSET(vaddr);
 298         printf("do_single_map: large path\n");
 299     } else {
 300         //4k mapping
 301         err = get_ptable(pmap, vaddr, &ptable);
 302         index = ARM_USER_L2_OFFSET(vaddr);
 303     }
 304     if (err_is_fail(err)) {
 305         return err_push(err, LIB_ERR_PMAP_GET_PTABLE);
 306     }
 307     uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags&~FLAGS_SUPERSECTION);
 308     // XXX: reassess the following note -SG
 309     // NOTE: strictly speaking a l2 entry only has 8 bits, but due to the way
 310     // Barrelfish allocates l1 and l2 tables, we use 10 bits for the tracking
 311     // index here and in the map syscall
 312     // NOTE: index determined in the pagesize branch -AD
 313     //uintptr_t index = ARM_USER_L2_OFFSET(vaddr);
 314     // Create user level datastructure for the mapping
 315     bool has_page = has_vnode(ptable, index, pte_count);
 316     assert(!has_page);
 317     struct vnode *page = slab_alloc(&pmap->slab);
 318     assert(page);
 319     page->is_vnode = false;
 320     page->entry = index;
 321     page->next  = ptable->u.vnode.children;
 322     ptable->u.vnode.children = page;
 323     page->u.frame.cap = frame;
 324     page->u.frame.flags = flags;
 325     page->u.frame.pte_count = pte_count;
 326
 327     // Map entry into the page table
 328     err = vnode_map(ptable->u.vnode.cap, frame, index,
 329                     pmap_flags, offset, pte_count);
 330     if (err_is_fail(err)) {
 331         return err_push(err, LIB_ERR_VNODE_MAP);
 332     }
 333     return SYS_ERR_OK;
 334 }
 335
 336 static errval_t do_map(struct pmap_arm *pmap, genvaddr_t vaddr,
 337                        struct capref frame, size_t offset, size_t size,
 338                        vregion_flags_t flags, size_t *retoff, size_t *retsize)
 339 {
 340     errval_t err;
 341     size_t page_size;
 342     size_t offset_level;
 343     // determine mapping specific parts
 344     if (flags&FLAGS_SECTION) {
 345         //section mapping (1MB)
 346         page_size = LARGE_PAGE_SIZE;
 347         offset_level = ARM_L1_OFFSET(vaddr);
 348         printf("do_map: large path\n");
 349         printf("page_size: %i, size: %i\n", page_size, size);
 350     } else {
 351         //normal 4k mapping
 352         page_size = BASE_PAGE_SIZE;
 353         offset_level = ARM_L2_OFFSET(vaddr);
 354     }
 355
 356     size = ROUND_UP(size, page_size);
 357     size_t pte_count = DIVIDE_ROUND_UP(size, page_size);
 358     genvaddr_t vend = vaddr + size;
 359
 360     //should be trivially true for section mappings
 361     if ((ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) ||
 362         flags&FLAGS_SECTION) {
 363         // fast path
 364         err = do_single_map(pmap, vaddr, vend, frame, offset, pte_count, flags);
 365         if (err_is_fail(err)) {
 366             DEBUG_ERR(err, "[do_map] in fast path");
 367             return err_push(err, LIB_ERR_PMAP_DO_MAP);
 368         }
 369     } else { // multiple leaf page tables
 370         // first leaf
 371         uint32_t c = ARM_L2_MAX_ENTRIES - offset_level;
 372         genvaddr_t temp_end = vaddr + c * page_size;
 373         err = do_single_map(pmap, vaddr, temp_end, frame, offset, c, flags);
 374         if (err_is_fail(err)) {
 375             return err_push(err, LIB_ERR_PMAP_DO_MAP);
 376         }
 377
 378         // map full leaves
 379         while (ARM_L1_OFFSET(temp_end) < ARM_L1_OFFSET(vend)) { // update vars
 380             vaddr = temp_end;
 381             temp_end = vaddr + ARM_L2_MAX_ENTRIES * page_size;
 382             offset += c * page_size;
 383             c = ARM_L2_MAX_ENTRIES;
 384             // copy cap
 385             struct capref next;
 386             err = slot_alloc(&next);
 387             if (err_is_fail(err)) {
 388                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 389             }
 390             err = cap_copy(next, frame);
 391             if (err_is_fail(err)) {
 392                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 393             }
 394             frame = next;
 395
 396             // do mapping
 397             err = do_single_map(pmap, vaddr, temp_end, frame, offset, ARM_L2_MAX_ENTRIES, flags);
 398             if (err_is_fail(err)) {
 399                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 400             }
 401         }
 402
 403         // map remaining part
 404         offset += c * page_size;
 405         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(temp_end);
 406         if (c) {
 407             // copy cap
 408             struct capref next;
 409             err = slot_alloc(&next);
 410             if (err_is_fail(err)) {
 411                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 412             }
 413             err = cap_copy(next, frame);
 414             if (err_is_fail(err)) {
 415                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 416             }
 417
 418             // do mapping
 419             err = do_single_map(pmap, temp_end, vend, next, offset, c, flags);
 420             if (err_is_fail(err)) {
 421                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
 422             }
 423         }
 424     }
 425     if (retoff) {
 426         *retoff = offset;
 427     }
 428     if (retsize) {
 429         *retsize = size;
 430     }
 431     //has_vnode_debug = false;
 432     return SYS_ERR_OK;
 433 #if 0
 434     errval_t err;
 435     uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags);
 436
 437     for (size_t i = offset; i < offset + size; i += BASE_PAGE_SIZE) {
 438
 439         vaddr += BASE_PAGE_SIZE;
 440     }
 441
 442     if (retoff) {
 443         *retoff = offset;
 444     }
 445     if (retsize) {
 446         *retsize = size;
 447     }
 448     return SYS_ERR_OK;
 449 #endif
 450 }
 451
 452 static size_t
 453 max_slabs_required(size_t bytes)
 454 {
 455     // Perform a slab allocation for every page (do_map -> slab_alloc)
 456     size_t pages     = DIVIDE_ROUND_UP(bytes, BASE_PAGE_SIZE);
 457     // Perform a slab allocation for every L2 (get_ptable -> find_vnode)
 458     size_t l2entries = DIVIDE_ROUND_UP(pages, 256 * 4);
 459     // Perform a slab allocation for every L1 (do_map -> find_vnode)
 460     size_t l1entries = DIVIDE_ROUND_UP(l2entries, 1024);
 461     return pages + l2entries + l1entries;
 462 }
 463 static size_t max_slabs_required_large(size_t bytes)
 464 {
 465     // similar to the above, but larger page size and mapped only in a higher lvl paging structure
 466     size_t pages = DIVIDE_ROUND_UP(bytes, LARGE_PAGE_SIZE);
 467     size_t l1entries = DIVIDE_ROUND_UP(pages, 1024);
 468     return pages + l1entries;
 469 }
 470
 471 /**
 472  * \brief Refill slabs used for metadata
 473  *
 474  * \param pmap     The pmap to refill in
 475  * \param request  The number of slabs the allocator must have
 476  * when the function returns
 477  *
 478  * When the current pmap is initialized,
 479  * it reserves some virtual address space for metadata.
 480  * This reserved address space is used here
 481  *
 482  * Can only be called for the current pmap
 483  * Will recursively call into itself till it has enough slabs
 484  */
 485 #include <stdio.h>
 486 static errval_t refill_slabs(struct pmap_arm *pmap, size_t request)
 487 {
 488     errval_t err;
 489
 490     /* Keep looping till we have #request slabs */
 491     while (slab_freecount(&pmap->slab) < request) {
 492         // Amount of bytes required for #request
 493         size_t bytes = SLAB_STATIC_SIZE(request - slab_freecount(&pmap->slab),
 494                                         sizeof(struct vnode));
 495
 496         /* Get a frame of that size */
 497         struct capref cap;
 498         err = frame_alloc(&cap, bytes, &bytes);
 499         if (err_is_fail(err)) {
 500             return err_push(err, LIB_ERR_FRAME_ALLOC);
 501         }
 502
 503         /* If we do not have enough slabs to map the frame in, recurse */
 504         size_t required_slabs_for_frame = max_slabs_required(bytes);
 505         if (slab_freecount(&pmap->slab) < required_slabs_for_frame) {
 506             // If we recurse, we require more slabs than to map a single page
 507             assert(required_slabs_for_frame > 4);
 508
 509             err = refill_slabs(pmap, required_slabs_for_frame);
 510             if (err_is_fail(err)) {
 511                 return err_push(err, LIB_ERR_SLAB_REFILL);
 512             }
 513         }
 514
 515         /* Perform mapping */
 516         genvaddr_t genvaddr = pmap->vregion_offset;
 517         pmap->vregion_offset += (genvaddr_t)bytes;
 518
 519         // if this assert fires, increase META_DATA_RESERVED_SPACE
 520         assert(pmap->vregion_offset < (vregion_get_base_addr(&pmap->vregion) +
 521                vregion_get_size(&pmap->vregion)));
 522
 523         err = do_map(pmap, genvaddr, cap, 0, bytes,
 524                      VREGION_FLAGS_READ_WRITE, NULL, NULL);
 525         if (err_is_fail(err)) {
 526             return err_push(err, LIB_ERR_PMAP_DO_MAP);
 527         }
 528
 529         /* Grow the slab */
 530         lvaddr_t buf = vspace_genvaddr_to_lvaddr(genvaddr);
 531         slab_grow(&pmap->slab, (void*)buf, bytes);
 532     }
 533
 534     return SYS_ERR_OK;
 535 }
 536
 537 /**
 538  * \brief Create page mappings
 539  *
 540  * \param pmap     The pmap object
 541  * \param vaddr    The virtual address to create the mapping for
 542  * \param frame    The frame cap to map in
 543  * \param offset   Offset into the frame cap
 544  * \param size     Size of the mapping
 545  * \param flags    Flags for the mapping
 546  * \param retoff   If non-NULL, filled in with adjusted offset of mapped region
 547  * \param retsize  If non-NULL, filled in with adjusted size of mapped region
 548  */
 549 static errval_t
 550 map(struct pmap     *pmap,
 551     genvaddr_t       vaddr,
 552     struct capref    frame,
 553     size_t           offset,
 554     size_t           size,
 555     vregion_flags_t  flags,
 556     size_t          *retoff,
 557     size_t          *retsize)
 558 {
 559     struct pmap_arm *pmap_arm = (struct pmap_arm *)pmap;
 560
 561     size_t base;
 562     size_t page_size;
 563     size_t slabs_required;
 564
 565     // adjust the mapping to be on page boundaries
 566     if (flags&FLAGS_SECTION) {
 567         //section mapping (1MB)
 568         base = LARGE_PAGE_OFFSET(offset);
 569         page_size = LARGE_PAGE_SIZE;
 570         slabs_required = max_slabs_required_large(size);
 571         printf("map: large path, page_size: %i, base: %i, slabs: %i, size: %i\n", page_size, base, slabs_required, size);
 572     } else {
 573         //4k mapping
 574         base = BASE_PAGE_OFFSET(offset);
 575         page_size = BASE_PAGE_SIZE;
 576         slabs_required = max_slabs_required(size);
 577     }
 578     size   += base;
 579     size    = ROUND_UP(size, page_size);
 580     offset -= base;
 581
 582     const size_t slabs_reserve = 3; // == max_slabs_required(1)
 583     uint64_t  slabs_free       = slab_freecount(&pmap_arm->slab);
 584
 585     slabs_required += slabs_reserve;
 586
 587     if (slabs_required > slabs_free) {
 588         if (get_current_pmap() == pmap) {
 589             errval_t err = refill_slabs(pmap_arm, slabs_required);
 590             if (err_is_fail(err)) {
 591                 return err_push(err, LIB_ERR_SLAB_REFILL);
 592             }
 593         }
 594         else {
 595             size_t bytes = SLAB_STATIC_SIZE(slabs_required - slabs_free,
 596                                             sizeof(struct vnode));
 597             void *buf = malloc(bytes);
 598             if (!buf) {
 599                 return LIB_ERR_MALLOC_FAIL;
 600             }
 601             slab_grow(&pmap_arm->slab, buf, bytes);
 602         }
 603     }
 604
 605     return do_map(pmap_arm, vaddr, frame, offset, size, flags,
 606                   retoff, retsize);
 607 }
 608
 609 static errval_t do_single_unmap(struct pmap_arm *pmap, genvaddr_t vaddr,
 610                                 size_t pte_count, bool delete_cap)
 611 {
 612     errval_t err;
 613     struct vnode *pt = find_ptable(pmap, vaddr);
 614     if (pt) {
 615         // analog to do_single_map we use 10 bits for tracking pages in user space -SG
 616         struct vnode *page = find_vnode(pt, ARM_USER_L2_OFFSET(vaddr));
 617         if (page && page->u.frame.pte_count == pte_count) {
 618             err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap,
 619                               page->entry, page->u.frame.pte_count);
 620             if (err_is_fail(err)) {
 621                 DEBUG_ERR(err, "vnode_unmap");
 622                 return err_push(err, LIB_ERR_VNODE_UNMAP);
 623             }
 624
 625             // Free up the resources
 626             if (delete_cap) {
 627                 err = cap_destroy(page->u.frame.cap);
 628                 if (err_is_fail(err)) {
 629                     return err_push(err, LIB_ERR_PMAP_DO_SINGLE_UNMAP);
 630                 }
 631             }
 632             remove_vnode(pt, page);
 633             slab_free(&pmap->slab, page);
 634         }
 635         else {
 636             return LIB_ERR_PMAP_FIND_VNODE;
 637         }
 638     }
 639
 640     return SYS_ERR_OK;
 641 }
 642
 643 /**
 644  * \brief Remove page mappings
 645  *
 646  * \param pmap     The pmap object
 647  * \param vaddr    The start of the virtual addres to remove
 648  * \param size     The size of virtual address to remove
 649  * \param retsize  If non-NULL, filled in with the actual size removed
 650  */
 651 static errval_t
 652 unmap(struct pmap *pmap,
 653       genvaddr_t   vaddr,
 654       size_t       size,
 655       size_t      *retsize)
 656 {
 657     errval_t err, ret = SYS_ERR_OK;
 658     struct pmap_arm *pmap_arm = (struct pmap_arm*)pmap;
 659     size = ROUND_UP(size, BASE_PAGE_SIZE);
 660     size_t pte_count = size / BASE_PAGE_SIZE;
 661     genvaddr_t vend = vaddr + size;
 662
 663     if (ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) {
 664         // fast path
 665         err = do_single_unmap(pmap_arm, vaddr, pte_count, false);
 666         if (err_is_fail(err)) {
 667             return err_push(err, LIB_ERR_PMAP_UNMAP);
 668         }
 669     } else { // slow path
 670         // unmap first leaf
 671         uint32_t c = ARM_L2_MAX_ENTRIES - ARM_L2_OFFSET(vaddr);
 672         err = do_single_unmap(pmap_arm, vaddr, c, false);
 673         if (err_is_fail(err)) {
 674             return err_push(err, LIB_ERR_PMAP_UNMAP);
 675         }
 676
 677         // unmap full leaves
 678         vaddr += c * BASE_PAGE_SIZE;
 679         while (ARM_L1_OFFSET(vaddr) < ARM_L1_OFFSET(vend)) {
 680             c = ARM_L2_MAX_ENTRIES;
 681             err = do_single_unmap(pmap_arm, vaddr, c, true);
 682             if (err_is_fail(err)) {
 683                 return err_push(err, LIB_ERR_PMAP_UNMAP);
 684             }
 685             vaddr += c * BASE_PAGE_SIZE;
 686         }
 687
 688         // unmap remaining part
 689         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(vaddr);
 690         if (c) {
 691             err = do_single_unmap(pmap_arm, vaddr, c, true);
 692             if (err_is_fail(err)) {
 693                 return err_push(err, LIB_ERR_PMAP_UNMAP);
 694             }
 695         }
 696     }
 697
 698     if (retsize) {
 699         *retsize = size;
 700     }
 701
 702     return ret;
 703 }
 704
 705 /**
 706  * \brief Determine a suitable address for a given memory object
 707  *
 708  * \param pmap    The pmap object
 709  * \param memobj  The memory object to determine the address for
 710  * \param alignment Minimum alignment
 711  * \param vaddr   Pointer to return the determined address
 712  *
 713  * Relies on vspace.c code maintaining an ordered list of vregions
 714  */
 715 static errval_t
 716 determine_addr(struct pmap   *pmap,
 717                struct memobj *memobj,
 718                size_t        alignment,
 719                genvaddr_t    *vaddr)
 720 {
 721     assert(pmap->vspace->head);
 722
 723     assert(alignment <= BASE_PAGE_SIZE); // NYI
 724
 725     struct vregion *walk = pmap->vspace->head;
 726     while (walk->next) { // Try to insert between existing mappings
 727         genvaddr_t walk_base = vregion_get_base_addr(walk);
 728         genvaddr_t walk_size = vregion_get_size(walk);
 729         genvaddr_t next_base = vregion_get_base_addr(walk->next);
 730
 731         if (next_base > walk_base + walk_size + memobj->size &&
 732             walk_base + walk_size > VSPACE_BEGIN) { // Ensure mappings are larger than VSPACE_BEGIN
 733             *vaddr = walk_base + walk_size;
 734             return SYS_ERR_OK;
 735         }
 736         walk = walk->next;
 737     }
 738
 739     *vaddr = vregion_get_base_addr(walk) + vregion_get_size(walk);
 740     return SYS_ERR_OK;
 741 }
 742
 743 /** \brief Retrieves an address that can currently be used for large mappings
 744   *
 745   */
 746 static errval_t determine_addr_raw(struct pmap *pmap, size_t size,
 747                                    size_t alignment, genvaddr_t *retvaddr)
 748 {
 749     struct pmap_arm *pmap_arm = (struct pmap_arm *)pmap;
 750
 751     struct vnode *walk_pdir = pmap_arm->root.u.vnode.children;
 752     assert(walk_pdir != NULL); // assume there's always at least one existing entry
 753
 754     if (alignment == 0) {
 755         alignment = BASE_PAGE_SIZE;
 756     } else {
 757         alignment = ROUND_UP(alignment, BASE_PAGE_SIZE);
 758     }
 759     size = ROUND_UP(size, alignment);
 760
 761     size_t free_count = DIVIDE_ROUND_UP(size, LARGE_PAGE_SIZE);
 762     //debug_printf("need %zu contiguous free pdirs\n", free_count);
 763
 764     // compile pdir free list
 765     // barrelfish treats L1 as 1024 entries
 766     bool f[1024];
 767     for (int i = 0; i < 1024; i++) {
 768         f[i] = true;
 769     }
 770     f[walk_pdir->entry] = false;
 771     while (walk_pdir) {
 772         assert(walk_pdir->is_vnode);
 773         f[walk_pdir->entry] = false;
 774         walk_pdir = walk_pdir->next;
 775     }
 776     genvaddr_t first_free = 384;
 777     for (; first_free < 512; first_free++) {
 778         if (f[first_free]) {
 779             for (int i = 1; i < free_count; i++) {
 780                 if (!f[first_free + i]) {
 781                     // advance pointer
 782                     first_free = first_free+i;
 783                     goto next;
 784                 }
 785             }
 786             break;
 787         }
 788 next:
 789         assert(1 == 1);// make compiler shut up about label
 790     }
 791     //printf("first free: %li\n", (uint32_t)first_free);
 792     if (first_free + free_count <= 512) {
 793         *retvaddr = first_free << 22;
 794         return SYS_ERR_OK;
 795     } else {
 796         return LIB_ERR_OUT_OF_VIRTUAL_ADDR;
 797     }
 798 }
 799
 800
 801
 802 static errval_t do_single_modify_flags(struct pmap_arm *pmap, genvaddr_t vaddr,
 803                                        size_t pages, vregion_flags_t flags)
 804 {
 805     errval_t err = SYS_ERR_OK;
 806     struct vnode *ptable = find_ptable(pmap, vaddr);
 807     uint16_t ptentry = ARM_USER_L2_OFFSET(vaddr);
 808     if (ptable) {
 809         struct vnode *page = find_vnode(ptable, ptentry);
 810         if (page) {
 811             if (inside_region(ptable, ptentry, pages)) {
 812                 // we're modifying part of a valid mapped region
 813                 // arguments to invocation: invoke frame cap, first affected
 814                 // page (as offset from first page in mapping), #affected
 815                 // pages, new flags. Invocation should check compatibility of
 816                 // new set of flags with cap permissions.
 817                 size_t off = ptentry - page->entry;
 818                 uintptr_t pmap_flags = vregion_flags_to_kpi_paging_flags(flags);
 819                 err = invoke_frame_modify_flags(page->u.frame.cap, off, pages, pmap_flags);
 820                 printf("invoke_frame_modify_flags returned error: %s (%"PRIuERRV")\n",
 821                         err_getstring(err), err);
 822                 return err;
 823             } else {
 824                 // overlaps some region border
 825                 return LIB_ERR_PMAP_EXISTING_MAPPING;
 826             }
 827         }
 828     }
 829     return SYS_ERR_OK;
 830 }
 831
 832 /**
 833  * \brief Modify page mapping
 834  *
 835  * \param pmap     The pmap object
 836  * \param vaddr    The virtual address to unmap
 837  * \param flags    New flags for the mapping
 838  * \param retsize  If non-NULL, filled in with the actual size modified
 839  */
 840 static errval_t
 841 modify_flags(struct pmap     *pmap,
 842              genvaddr_t       vaddr,
 843              size_t           size,
 844              vregion_flags_t  flags,
 845              size_t          *retsize)
 846 {
 847     errval_t err, ret = SYS_ERR_OK;
 848     struct pmap_arm *pmap_arm = (struct pmap_arm*)pmap;
 849     size = ROUND_UP(size, BASE_PAGE_SIZE);
 850     size_t pte_count = size / BASE_PAGE_SIZE;
 851     genvaddr_t vend = vaddr + size;
 852
 853     if (ARM_L1_OFFSET(vaddr) == ARM_L1_OFFSET(vend-1)) {
 854         // fast path
 855         err = do_single_modify_flags(pmap_arm, vaddr, pte_count, false);
 856         if (err_is_fail(err)) {
 857             return err_push(err, LIB_ERR_PMAP_UNMAP);
 858         }
 859     }
 860     else { // slow path
 861         // unmap first leaf
 862         uint32_t c = ARM_L2_MAX_ENTRIES - ARM_L2_OFFSET(vaddr);
 863         err = do_single_modify_flags(pmap_arm, vaddr, c, false);
 864         if (err_is_fail(err)) {
 865             return err_push(err, LIB_ERR_PMAP_UNMAP);
 866         }
 867
 868         // unmap full leaves
 869         vaddr += c * BASE_PAGE_SIZE;
 870         while (ARM_L1_OFFSET(vaddr) < ARM_L1_OFFSET(vend)) {
 871             c = ARM_L2_MAX_ENTRIES;
 872             err = do_single_modify_flags(pmap_arm, vaddr, c, true);
 873             if (err_is_fail(err)) {
 874                 return err_push(err, LIB_ERR_PMAP_UNMAP);
 875             }
 876             vaddr += c * BASE_PAGE_SIZE;
 877         }
 878
 879         // unmap remaining part
 880         c = ARM_L2_OFFSET(vend) - ARM_L2_OFFSET(vaddr);
 881         if (c) {
 882             err = do_single_modify_flags(pmap_arm, vaddr, c, true);
 883             if (err_is_fail(err)) {
 884                 return err_push(err, LIB_ERR_PMAP_UNMAP);
 885             }
 886         }
 887     }
 888
 889     if (retsize) {
 890         *retsize = size;
 891     }
 892
 893     return ret;
 894 }
 895
 896 /**
 897  * \brief Query existing page mapping
 898  *
 899  * \param pmap     The pmap object
 900  * \param vaddr    The virtual address to query
 901  * \param retvaddr Returns the base virtual address of the mapping
 902  * \param retsize  Returns the actual size of the mapping
 903  * \param retcap   Returns the cap mapped at this address
 904  * \param retoffset Returns the offset within the cap that is mapped
 905  * \param retflags Returns the flags for this mapping
 906  *
 907  * All of the ret parameters are optional.
 908  */
 909 static errval_t lookup(struct pmap *pmap, genvaddr_t vaddr,
 910                        genvaddr_t *retvaddr, size_t *retsize,
 911                        struct capref *retcap, genvaddr_t *retoffset,
 912                        vregion_flags_t *retflags)
 913 {
 914     USER_PANIC("NYI");
 915     return 0;
 916 }
 917
 918
 919 static errval_t
 920 serialise(struct pmap *pmap, void *buf, size_t buflen)
 921 {
 922     // Unimplemented: ignored
 923     return SYS_ERR_OK;
 924 }
 925
 926 static errval_t
 927 deserialise(struct pmap *pmap, void *buf, size_t buflen)
 928 {
 929     // Unimplemented: we start with an empty pmap, and avoid the bottom of the A/S
 930     return SYS_ERR_OK;
 931 }
 932
 933 static struct pmap_funcs pmap_funcs = {
 934     .determine_addr = determine_addr,
 935     .determine_addr_raw = determine_addr_raw,
 936     .map = map,
 937     .unmap = unmap,
 938     .modify_flags = modify_flags,
 939     .lookup = lookup,
 940     .serialise = serialise,
 941     .deserialise = deserialise,
 942 };
 943
 944 /**
 945  * \brief Initialize the pmap object
 946  */
 947 errval_t
 948 pmap_init(struct pmap   *pmap,
 949           struct vspace *vspace,
 950           struct capref  vnode,
 951           struct slot_allocator *opt_slot_alloc)
 952 {
 953     struct pmap_arm* pmap_arm = (struct pmap_arm*)pmap;
 954
 955     /* Generic portion */
 956     pmap->f = pmap_funcs;
 957     pmap->vspace = vspace;
 958
 959     // Slab allocator for vnodes
 960     slab_init(&pmap_arm->slab, sizeof(struct vnode), NULL);
 961     slab_grow(&pmap_arm->slab,
 962               pmap_arm->slab_buffer,
 963               sizeof(pmap_arm->slab_buffer));
 964
 965     pmap_arm->root.is_vnode         = true;
 966     pmap_arm->root.u.vnode.cap      = vnode;
 967     pmap_arm->root.next             = NULL;
 968     pmap_arm->root.u.vnode.children = NULL;
 969
 970     return SYS_ERR_OK;
 971 }
 972
 973 errval_t pmap_current_init(bool init_domain)
 974 {
 975     struct pmap_arm *pmap_arm = (struct pmap_arm*)get_current_pmap();
 976
 977     // To reserve a block of virtual address space,
 978     // a vregion representing the address space is required.
 979     // We construct a superficial one here and add it to the vregion list.
 980     struct vregion *vregion = &pmap_arm->vregion;
 981     assert((void*)vregion > (void*)pmap_arm);
 982     assert((void*)vregion < (void*)(pmap_arm + 1));
 983     vregion->vspace = NULL;
 984     vregion->memobj = NULL;
 985     vregion->base   = VSPACE_BEGIN;
 986     vregion->offset = 0;
 987     vregion->size   = META_DATA_RESERVED_SPACE;
 988     vregion->flags  = 0;
 989     vregion->next = NULL;
 990
 991     struct vspace *vspace = pmap_arm->p.vspace;
 992     assert(!vspace->head);
 993     vspace->head = vregion;
 994
 995     pmap_arm->vregion_offset = pmap_arm->vregion.base;
 996
 997     return SYS_ERR_OK;
 998 }