git.barrelfish.org Git - barrelfish/blob - lib/barrelfish/target/x86/pmap_x86.c

   1 /**
   2  * \file
   3  * \brief Pmap code common for x86 archs
   4  */
   5
   6 /*
   7  * Copyright (c) 2011, ETH Zurich.
   8  * Copyright (c) 2014, HP Labs.
   9  * All rights reserved.
  10  *
  11  * This file is distributed under the terms in the attached LICENSE file.
  12  * If you do not find this file, copies can be found by writing to:
  13  * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
  14  */
  15
  16 #include <barrelfish/barrelfish.h>
  17 #include <barrelfish/pmap.h>
  18 #include "target/x86/pmap_x86.h"
  19
  20 // this should work for x86_64 and x86_32.
  21 bool has_vnode(struct vnode *root, uint32_t entry, size_t len,
  22                bool only_pages)
  23 {
  24     assert(root != NULL);
  25     assert(root->is_vnode);
  26     struct vnode *n;
  27
  28     uint32_t end_entry = entry + len;
  29
  30     // region we check [entry .. end_entry)
  31
  32     for (n = root->u.vnode.children; n; n = n->next) {
  33         // n is page table, we need to check if it's anywhere inside the
  34         // region to check [entry .. end_entry)
  35         // this amounts to n->entry == entry for len = 1
  36         if (n->is_vnode && n->entry >= entry && n->entry < end_entry) {
  37             if (only_pages) {
  38                 return has_vnode(n, 0, PTABLE_SIZE, true);
  39             }
  40 #ifdef LIBBARRELFISH_DEBUG_PMAP
  41             debug_printf("1: found page table inside our region\n");
  42 #endif
  43             return true;
  44         } else if (n->is_vnode) {
  45             // all other vnodes do not overlap with us, so go to next
  46             assert(n->entry < entry || n->entry >= end_entry);
  47             continue;
  48         }
  49         // this remains the same regardless of `only_pages`.
  50         // n is frame [n->entry .. end)
  51         // 3 cases:
  52         // 1) entry < n->entry && end_entry >= end --> n is a strict subset of
  53         // our region
  54         // 2) entry inside n (entry >= n->entry && entry < end)
  55         // 3) end_entry inside n (end_entry >= n->entry && end_entry < end)
  56         uint32_t end = n->entry + n->u.frame.pte_count;
  57         if (entry < n->entry && end_entry >= end) {
  58 #ifdef LIBBARRELFISH_DEBUG_PMAP
  59             debug_printf("2: found a strict subset of our region: (%"
  60                     PRIu32"--%"PRIu32") < (%"PRIu32"--%"PRIu32")\n",
  61                     n->entry, end, entry, end_entry);
  62 #endif
  63             return true;
  64         }
  65         if (entry >= n->entry && entry < end) {
  66 #ifdef LIBBARRELFISH_DEBUG_PMAP
  67             debug_printf("3: found a region starting inside our region: (%"
  68                     PRIu32"--%"PRIu32") <> (%"PRIu32"--%"PRIu32")\n",
  69                     n->entry, end, entry, end_entry);
  70 #endif
  71             return true;
  72         }
  73         if (end_entry > n->entry && end_entry < end) {
  74 #ifdef LIBBARRELFISH_DEBUG_PMAP
  75             debug_printf("4: found a region ending inside our region: (%"
  76                     PRIu32"--%"PRIu32") <> (%"PRIu32"--%"PRIu32")\n",
  77                     n->entry, end, entry, end_entry);
  78 #endif
  79             return true;
  80         }
  81     }
  82
  83     return false;
  84 }
  85
  86 /**
  87  * \brief Starting at a given root, return the vnode with entry equal to #entry
  88  */
  89 struct vnode *find_vnode(struct vnode *root, uint16_t entry)
  90 {
  91     assert(root != NULL);
  92     assert(root->is_vnode);
  93     struct vnode *n;
  94
  95     for(n = root->u.vnode.children; n != NULL; n = n->next) {
  96         if(n->entry == entry) {
  97             return n;
  98         }
  99     }
 100     return NULL;
 101 }
 102
 103 bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
 104 {
 105     assert(root != NULL);
 106     assert(root->is_vnode);
 107
 108     struct vnode *n;
 109
 110     for (n = root->u.vnode.children; n; n = n->next) {
 111         if (!n->is_vnode) {
 112             uint16_t end = n->entry + n->u.frame.pte_count;
 113             if (n->entry <= entry && entry + npages <= end) {
 114                 return true;
 115             }
 116         }
 117     }
 118
 119     return false;
 120 }
 121
 122 void remove_vnode(struct vnode *root, struct vnode *item)
 123 {
 124     assert(root->is_vnode);
 125     struct vnode *walk = root->u.vnode.children;
 126     struct vnode *prev = NULL;
 127     while (walk) {
 128         if (walk == item) {
 129             if (prev) {
 130                 prev->next = walk->next;
 131                 return;
 132             } else {
 133                 root->u.vnode.children = walk->next;
 134                 return;
 135             }
 136         }
 137         prev = walk;
 138         walk = walk->next;
 139     }
 140     USER_PANIC("Should not get here");
 141 }
 142
 143 /**
 144  * \brief Allocates a new VNode, adding it to the page table and our metadata
 145  */
 146 errval_t alloc_vnode(struct pmap_x86 *pmap, struct vnode *root,
 147                      enum objtype type, uint32_t entry,
 148                      struct vnode **retvnode)
 149 {
 150     errval_t err;
 151
 152     struct vnode *newvnode = slab_alloc(&pmap->slab);
 153     if (newvnode == NULL) {
 154         return LIB_ERR_SLAB_ALLOC_FAIL;
 155     }
 156
 157     // The VNode capability
 158     err = pmap->p.slot_alloc->alloc(pmap->p.slot_alloc, &newvnode->u.vnode.cap);
 159     if (err_is_fail(err)) {
 160         return err_push(err, LIB_ERR_SLOT_ALLOC);
 161     }
 162
 163     err = vnode_create(newvnode->u.vnode.cap, type);
 164     if (err_is_fail(err)) {
 165         return err_push(err, LIB_ERR_VNODE_CREATE);
 166     }
 167
 168     // Map it
 169     err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
 170                     PTABLE_ACCESS_DEFAULT, 0, 1);
 171     if (err_is_fail(err)) {
 172         return err_push(err, LIB_ERR_VNODE_MAP);
 173     }
 174
 175     // The VNode meta data
 176     newvnode->is_vnode  = true;
 177     newvnode->entry     = entry;
 178     newvnode->next      = root->u.vnode.children;
 179     root->u.vnode.children = newvnode;
 180     newvnode->u.vnode.children = NULL;
 181
 182     *retvnode = newvnode;
 183     return SYS_ERR_OK;
 184 }
 185
 186 void remove_empty_vnodes(struct pmap_x86 *pmap, struct vnode *root,
 187                          uint32_t entry, size_t len)
 188 {
 189     errval_t err;
 190     uint32_t end_entry = entry + len;
 191     for (struct vnode *n = root->u.vnode.children; n; n = n->next) {
 192         if (n->entry >= entry && n->entry < end_entry) {
 193             // sanity check and skip leaf entries
 194             if (!n->is_vnode) {
 195                 continue;
 196             }
 197             // here we know that all vnodes we're interested in are
 198             // page tables
 199             assert(n->is_vnode);
 200             if (n->u.vnode.children) {
 201                 remove_empty_vnodes(pmap, n, 0, PTABLE_SIZE);
 202             }
 203
 204             // unmap
 205             err = vnode_unmap(root->u.vnode.cap, n->u.vnode.cap, n->entry, 1);
 206             if (err_is_fail(err)) {
 207                 debug_printf("remove_empty_vnodes: vnode_unmap: %s\n",
 208                         err_getstring(err));
 209             }
 210
 211             // delete capability
 212             err = cap_destroy(n->u.vnode.cap);
 213             if (err_is_fail(err)) {
 214                 debug_printf("remove_empty_vnodes: cap_destroy: %s\n",
 215                         err_getstring(err));
 216             }
 217
 218             // remove vnode from list
 219             remove_vnode(root, n);
 220             slab_free(&pmap->slab, n);
 221         }
 222     }
 223 }
 224
 225
 226 /*
 227  * The serialisation format is depressingly ad-hoc, and assumes a depth-first
 228  * walk of the tree. Each vnode is encoded as an entry in an array.
 229  *
 230  * We abuse the slot of the first entry, which is the root and thus is always
 231  * zero, to store the number of entries in the array.
 232  */
 233 struct serial_entry {
 234     uint16_t entry;     ///< Entry #
 235     uint8_t depth;      ///< Depth of this node (0 = root)
 236     cslot_t slot;       ///< Slot number (in page cnode) of vnode cap
 237 };
 238
 239 static errval_t serialise_tree(int depth, struct vnode *v,
 240                                struct serial_entry *out,
 241                                size_t outlen, size_t *outpos)
 242 {
 243     assert(v != NULL);
 244     errval_t err;
 245
 246     // don't serialise leaf pages (yet!)
 247     if (!v->is_vnode) {
 248         return SYS_ERR_OK;
 249     }
 250
 251     if (*outpos >= outlen) {
 252         return LIB_ERR_SERIALISE_BUFOVERFLOW;
 253     }
 254
 255     // serialise this node
 256     out[(*outpos)++] = (struct serial_entry) {
 257         .depth = depth,
 258         .entry = v->entry,
 259         .slot = v->u.vnode.cap.slot,
 260     };
 261
 262     // depth-first walk
 263     for (struct vnode *c = v->u.vnode.children; c != NULL; c = c->next) {
 264         err = serialise_tree(depth + 1, c, out, outlen, outpos);
 265         if (err_is_fail(err)) {
 266             return err;
 267         }
 268     }
 269
 270     return SYS_ERR_OK;
 271 }
 272
 273 /**
 274  * \brief Serialise vtree to a flat structure, for passing to another process
 275  *
 276  * This is used by spawn_vspace to communicate the vnode capabilities to the child.
 277  */
 278 errval_t pmap_x86_serialise(struct pmap *pmap, void *buf, size_t buflen)
 279 {
 280     errval_t err;
 281     struct pmap_x86 *pmapx = (struct pmap_x86 *)pmap;
 282
 283     // XXX: check alignment of buffer
 284     assert((uintptr_t)buf % sizeof(uintptr_t) == 0);
 285
 286     struct serial_entry *out = buf;
 287     size_t outlen = buflen / sizeof(struct serial_entry);
 288     size_t outpos = 0;
 289
 290     err = serialise_tree(0, &pmapx->root, out, outlen, &outpos);
 291     if (err_is_ok(err)) {
 292         // store length in first entry's slot number
 293         assert(out[0].slot == 0);
 294         out[0].slot = outpos;
 295     }
 296
 297     return err;
 298 }
 299
 300 static errval_t deserialise_tree(struct pmap *pmap, struct serial_entry **in,
 301                                  size_t *inlen, int depth, struct vnode *parent)
 302 {
 303     errval_t err;
 304     struct pmap_x86 *pmapx = (struct pmap_x86 *)pmap;
 305
 306     if (*inlen == 0) {
 307         return SYS_ERR_OK;
 308     }
 309
 310     while (*inlen > 0 && (*in)->depth == depth) {
 311         // ensure slab allocator has sufficient space
 312         err = pmapx->refill_slabs(pmapx);
 313         if (err_is_fail(err)) {
 314             return err_push(err, LIB_ERR_SLAB_REFILL);
 315         }
 316
 317         // allocate storage for the new vnode
 318         struct vnode *n = slab_alloc(&pmapx->slab);
 319         assert(n != NULL);
 320
 321         // populate it and append to parent's list of children
 322         n->is_vnode  = true;
 323         n->entry     = (*in)->entry;
 324         n->u.vnode.cap.cnode = cnode_page;
 325         n->u.vnode.cap.slot  = (*in)->slot;
 326         n->u.vnode.children  = NULL;
 327         n->next      = parent->u.vnode.children;
 328         parent->u.vnode.children = n;
 329
 330         (*in)++;
 331         (*inlen)--;
 332
 333         // is next entry a child of the last node?
 334         if (*inlen > 0 && (*in)->depth > depth) {
 335             assert((*in)->depth == depth + 1); // depth-first, no missing nodes
 336             err = deserialise_tree(pmap, in, inlen, depth + 1, n);
 337             if (err_is_fail(err)) {
 338                 return err;
 339             }
 340         }
 341     }
 342
 343     assert((*in)->depth < depth);
 344     return SYS_ERR_OK;
 345 }
 346
 347 /**
 348  * \brief Deserialise vtree from a flat structure, for importing from another process
 349  *
 350  * This is used in a newly-spawned child
 351  */
 352 errval_t pmap_x86_deserialise(struct pmap *pmap, void *buf, size_t buflen)
 353 {
 354     struct pmap_x86 *pmapx = (struct pmap_x86 *)pmap;
 355     errval_t err;
 356
 357     // XXX: check alignment of buffer
 358     assert((uintptr_t)buf % sizeof(uintptr_t) == 0);
 359
 360     // extract length and sanity-check
 361     struct serial_entry *in = buf;
 362     assert(buflen > sizeof(struct serial_entry));
 363     size_t inlen = in[0].slot;
 364     assert(inlen * sizeof(struct serial_entry) <= buflen);
 365     in++;
 366     inlen--;
 367
 368     err = deserialise_tree(pmap, &in, &inlen, 1, &pmapx->root);
 369     if (err_is_ok(err)) {
 370         // XXX: now that we know where our vnodes are, we can support mappings
 371         // in the bottom of the address space. However, we still don't know
 372         // exactly where our text and data are mapped (because we don't yet
 373         // serialise vregions or memobjs), so instead we pad _end.
 374         extern char _end;
 375         pmapx->min_mappable_va = ROUND_UP((lvaddr_t)&_end, 64 * 1024)
 376                                    + 64 * 1024;
 377     }
 378
 379     return err;
 380 }
 381
 382
 383
 384 /**
 385  * \brief Determine a suitable address for a given memory object
 386  *
 387  * \param pmap    The pmap object
 388  * \param memobj  The memory object to determine the address for
 389  * \param alignment Minimum alignment
 390  * \param retvaddr Pointer to return the determined address
 391  *
 392  * Relies on vspace.c code maintaining an ordered list of vregions
 393  */
 394 errval_t pmap_x86_determine_addr(struct pmap *pmap, struct memobj *memobj,
 395                                  size_t alignment, genvaddr_t *retvaddr)
 396 {
 397     struct pmap_x86 *pmapx = (struct pmap_x86 *)pmap;
 398     genvaddr_t vaddr;
 399
 400     struct vregion *walk = pmap->vspace->head;
 401     assert(walk != NULL); // assume there's always at least one existing entry
 402
 403     if (alignment == 0) {
 404         alignment = BASE_PAGE_SIZE;
 405     } else {
 406         alignment = ROUND_UP(alignment, BASE_PAGE_SIZE);
 407     }
 408     size_t size = ROUND_UP(memobj->size, alignment);
 409
 410     // if there's space before the first object, map it there
 411     genvaddr_t minva = ROUND_UP(pmapx->min_mappable_va, alignment);
 412     if (minva + size <= vregion_get_base_addr(walk)) {
 413         vaddr = minva;
 414         goto out;
 415     }
 416
 417     while (walk->next) { // Try to insert between existing mappings
 418         genvaddr_t walk_base = vregion_get_base_addr(walk);
 419         genvaddr_t walk_size = ROUND_UP(vregion_get_size(walk), BASE_PAGE_SIZE);
 420         genvaddr_t walk_end = ROUND_UP(walk_base + walk_size, alignment);
 421         genvaddr_t next_base = vregion_get_base_addr(walk->next);
 422
 423         // sanity-check for page alignment
 424         assert(walk_base % BASE_PAGE_SIZE == 0);
 425         assert(next_base % BASE_PAGE_SIZE == 0);
 426
 427         if (next_base > walk_end + size) {
 428             vaddr = walk_end;
 429             goto out;
 430         }
 431
 432         walk = walk->next;
 433     }
 434
 435     // Place beyond last mapping, with alignment
 436     vaddr = ROUND_UP((vregion_get_base_addr(walk)
 437                       + ROUND_UP(vregion_get_size(walk), BASE_PAGE_SIZE)),
 438                      alignment);
 439
 440  out:
 441     // Ensure that we haven't run out of address space
 442     if (vaddr + memobj->size > pmapx->max_mappable_va) {
 443         return LIB_ERR_OUT_OF_VIRTUAL_ADDR;
 444     }
 445
 446     assert(retvaddr != NULL);
 447     *retvaddr = vaddr;
 448
 449     return SYS_ERR_OK;
 450 }