Refactored pmap code for x86_{64,32}.
authorSimon Gerber <simon.gerber@hp.com>
Wed, 18 Jun 2014 20:02:04 +0000 (13:02 -0700)
committerSimon Gerber <simon.gerber@inf.ethz.ch>
Thu, 30 Apr 2015 19:19:28 +0000 (21:19 +0200)
* factored out common code for vnode manipulation (see pmap_x86.{h,c})
* cleaned up x86_32 pmap implementation

Signed-off-by: Simon Gerber <simon.gerber@hp.com>

lib/barrelfish/include/target/x86/pmap_x86.h
lib/barrelfish/target/x86/pmap_x86.c
lib/barrelfish/target/x86_32/pmap_target.c
lib/barrelfish/target/x86_64/pmap_target.c

index d452874..e5a4daa 100644 (file)
@@ -5,6 +5,7 @@
 
 /*
  * Copyright (c) 2011, ETH Zurich.
+ * Copyright (c) 2014, HP Labs.
  * All rights reserved.
  *
  * This file is distributed under the terms in the attached LICENSE file.
@@ -22,4 +23,45 @@ errval_t pmap_x86_deserialise(struct pmap *pmap, void *buf, size_t buflen);
 errval_t pmap_x86_determine_addr(struct pmap *pmap, struct memobj *memobj,
                                  size_t alignment, genvaddr_t *vaddr);
 
+/**
+ * \brief check whether vnode `root` has children in [entry .. entry+len).
+ * \return * true iff `root` has children in [entry .. entry+len) and
+ *           only_pages false
+ *         * true iff `root` has valid page mappings in [entry .. entry+len)
+ *           and only_pages true
+ */
+bool has_vnode(struct vnode *root, uint32_t entry, size_t len,
+               bool only_pages);
+/**
+ * \return vnode at `entry` in `root`. NULL if no vnode there.
+ */
+struct vnode *find_vnode(struct vnode *root, uint16_t entry);
+
+/**
+ * \return true iff [entry..entry+npages) inside a child of `root`.
+ */
+bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages);
+
+/**
+ * \brief remove vnode `item` from list of children of `root`.
+ */
+void remove_vnode(struct vnode *root, struct vnode *item);
+
+/**
+ * \brief allocate vnode as child of `root` with type `type`. Allocates the
+ * struct vnode with `pmap`'s slab allocator.
+ * \arg entry the entry at which the new vnode is inserted
+ * \arg retvnode pointer to the new vnode.
+ */
+errval_t alloc_vnode(struct pmap_x86 *pmap, struct vnode *root,
+                     enum objtype type, uint32_t entry,
+                     struct vnode **retvnode);
+
+/**
+ * \brief remove vnodes with no leafs in [entry .. entry+len), destroy their
+ * associated capabilities and free their slabs.
+ */
+void remove_empty_vnodes(struct pmap_x86 *pmap, struct vnode *root,
+                         uint32_t entry, size_t len);
+
 #endif // TARGET_X86_BARRELFISH_PMAP_X86_H
index 0f7c114..49ec264 100644 (file)
@@ -5,6 +5,7 @@
 
 /*
  * Copyright (c) 2011, ETH Zurich.
+ * Copyright (c) 2014, HP Labs.
  * All rights reserved.
  *
  * This file is distributed under the terms in the attached LICENSE file.
 #include <barrelfish/pmap.h>
 #include "target/x86/pmap_x86.h"
 
+// this should work for x86_64 and x86_32.
+bool has_vnode(struct vnode *root, uint32_t entry, size_t len,
+               bool only_pages)
+{
+    assert(root != NULL);
+    assert(root->is_vnode);
+    struct vnode *n;
+
+    uint32_t end_entry = entry + len;
+
+    // region we check [entry .. end_entry)
+
+    for (n = root->u.vnode.children; n; n = n->next) {
+        // n is page table, we need to check if it's anywhere inside the
+        // region to check [entry .. end_entry)
+        // this amounts to n->entry == entry for len = 1
+        if (n->is_vnode && n->entry >= entry && n->entry < end_entry) {
+            if (only_pages) {
+                return has_vnode(n, 0, PTABLE_SIZE, true);
+            }
+            return true;
+        }
+        // this remains the same regardless of `only_pages`.
+        // n is frame [n->entry .. end)
+        // 3 cases:
+        // 1) entry < n->entry && end_entry >= end --> n is a strict subset of
+        // our region
+        // 2) entry inside n (entry >= n->entry && entry < end)
+        // 3) end_entry inside n (end_entry >= n->entry && end_entry < end)
+        uint32_t end = n->entry + n->u.frame.pte_count;
+        if (entry < n->entry && end_entry >= end) {
+            return true;
+        }
+        if (entry >= n->entry && entry < end) {
+            return true;
+        }
+        if (end_entry > n->entry && end_entry < end) {
+            return true;
+        }
+    }
+
+    return false;
+}
+
+/**
+ * \brief Starting at a given root, return the vnode with entry equal to #entry
+ */
+struct vnode *find_vnode(struct vnode *root, uint16_t entry)
+{
+    assert(root != NULL);
+    assert(root->is_vnode);
+    struct vnode *n;
+
+    for(n = root->u.vnode.children; n != NULL; n = n->next) {
+        if(n->entry == entry) {
+            return n;
+        }
+    }
+    return NULL;
+}
+
+bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
+{
+    assert(root != NULL);
+    assert(root->is_vnode);
+
+    struct vnode *n;
+
+    for (n = root->u.vnode.children; n; n = n->next) {
+        if (!n->is_vnode) {
+            uint16_t end = n->entry + n->u.frame.pte_count;
+            if (n->entry <= entry && entry + npages <= end) {
+                return true;
+            }
+        }
+    }
+
+    return false;
+}
+
+void remove_vnode(struct vnode *root, struct vnode *item)
+{
+    assert(root->is_vnode);
+    struct vnode *walk = root->u.vnode.children;
+    struct vnode *prev = NULL;
+    while (walk) {
+        if (walk == item) {
+            if (prev) {
+                prev->next = walk->next;
+                return;
+            } else {
+                root->u.vnode.children = walk->next;
+                return;
+            }
+        }
+        prev = walk;
+        walk = walk->next;
+    }
+    USER_PANIC("Should not get here");
+}
+
+/**
+ * \brief Allocates a new VNode, adding it to the page table and our metadata
+ */
+errval_t alloc_vnode(struct pmap_x86 *pmap, struct vnode *root,
+                     enum objtype type, uint32_t entry,
+                     struct vnode **retvnode)
+{
+    errval_t err;
+
+    struct vnode *newvnode = slab_alloc(&pmap->slab);
+    if (newvnode == NULL) {
+        return LIB_ERR_SLAB_ALLOC_FAIL;
+    }
+
+    // The VNode capability
+    err = pmap->p.slot_alloc->alloc(pmap->p.slot_alloc, &newvnode->u.vnode.cap);
+    if (err_is_fail(err)) {
+        return err_push(err, LIB_ERR_SLOT_ALLOC);
+    }
+
+    err = vnode_create(newvnode->u.vnode.cap, type);
+    if (err_is_fail(err)) {
+        return err_push(err, LIB_ERR_VNODE_CREATE);
+    }
+
+    // Map it
+    err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
+                    PTABLE_ACCESS_DEFAULT, 0, 1);
+    if (err_is_fail(err)) {
+        return err_push(err, LIB_ERR_VNODE_MAP);
+    }
+
+    // The VNode meta data
+    newvnode->is_vnode  = true;
+    newvnode->entry     = entry;
+    newvnode->next      = root->u.vnode.children;
+    root->u.vnode.children = newvnode;
+    newvnode->u.vnode.children = NULL;
+
+    *retvnode = newvnode;
+    return SYS_ERR_OK;
+}
+
+void remove_empty_vnodes(struct pmap_x86 *pmap, struct vnode *root,
+                         uint32_t entry, size_t len)
+{
+    errval_t err;
+    uint32_t end_entry = entry + len;
+    for (struct vnode *n = root->u.vnode.children; n; n = n->next) {
+        if (n->entry >= entry && n->entry < end_entry) {
+            // here we know that all vnodes we're interested in are
+            // page tables
+            assert(n->is_vnode);
+            if (n->u.vnode.children) {
+                remove_empty_vnodes(pmap, n, 0, PTABLE_SIZE);
+            }
+
+            // unmap
+            err = vnode_unmap(root->u.vnode.cap, n->u.vnode.cap, n->entry, 1);
+            if (err_is_fail(err)) {
+                debug_printf("remove_empty_vnodes: vnode_unmap: %s\n",
+                        err_getstring(err));
+            }
+
+            // delete capability
+            err = cap_destroy(n->u.vnode.cap);
+            if (err_is_fail(err)) {
+                debug_printf("remove_empty_vnodes: cap_destroy: %s\n",
+                        err_getstring(err));
+            }
+
+            // remove vnode from list
+            remove_vnode(root, n);
+            slab_free(&pmap->slab, n);
+        }
+    }
+}
+
+
 /*
  * The serialisation format is depressingly ad-hoc, and assumes a depth-first
  * walk of the tree. Each vnode is encoded as an entry in an array.
index 08d62df..40ec1cf 100644 (file)
@@ -17,6 +17,7 @@
 
 /*
  * Copyright (c) 2010-2013 ETH Zurich.
+ * Copyright (c) 2014, HP Labs.
  * All rights reserved.
  *
  * This file is distributed under the terms in the attached LICENSE file.
@@ -85,128 +86,29 @@ static inline genvaddr_t get_addr_prefix(genvaddr_t va)
 {
     return va >> X86_32_LARGE_PAGE_BITS;
 }
+
 /**
- * \brief Starting at a given root, return the vnode with entry equal to #entry
+ * \brief Returns the vnode for the page directory mapping a given vspace address
  */
-static struct vnode *find_vnode(struct vnode *root, uint16_t entry)
-{
-    assert(root != NULL);
-    assert(root->is_vnode);
-    struct vnode *n;
-
-    for(n = root->u.vnode.children; n != NULL; n = n->next) {
-        if(n->entry == entry) {
-            return n;
-        }
-    }
-    return NULL;
-}
-
-static bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
-{
-    assert(root != NULL);
-    assert(root->is_vnode);
-
-    struct vnode *n;
-
-    for (n = root->u.vnode.children; n; n = n->next) {
-        if (!n->is_vnode) {
-            uint16_t end = n->entry + n->u.frame.pte_count;
-            if (n->entry <= entry && entry + npages <= end) {
-                return true;
-            }
-        }
-    }
-
-    return false;
-}
-
-static bool has_vnode(struct vnode *root, uint32_t entry, size_t len)
+static errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
+                           struct vnode **pdir)
 {
+#ifdef CONFIG_PAE
+    struct vnode *root = &pmap->root;
     assert(root != NULL);
-    assert(root->is_vnode);
-    struct vnode *n;
-
-    uint32_t end_entry = entry + len;
-
-    for (n = root->u.vnode.children; n; n = n->next) {
-        if (n->is_vnode && n->entry == entry) {
-            return true;
-        }
-        // n is frame
-        uint32_t end = n->entry + n->u.frame.pte_count;
-        if (n->entry < entry && end > end_entry) {
-            return true;
-        }
-        if (n->entry >= entry && n->entry < end_entry) {
-            return true;
-        }
-    }
-
-    return false;
-}
 
-static void remove_vnode(struct vnode *root, struct vnode *item)
-{
-    assert(root->is_vnode);
-    struct vnode *walk = root->u.vnode.children;
-    struct vnode *prev = NULL;
-    while (walk) {
-        if (walk == item) {
-            if (prev) {
-                prev->next = walk->next;
-                return;
-            } else {
-                root->u.vnode.children = walk->next;
-                return;
-            }
+    // PDPTE mapping
+    if((*pdir = find_vnode(root, X86_32_PDPTE_BASE(base))) == NULL) {
+        errval_t err = alloc_vnode(pmap, root, ObjType_VNode_x86_32_pdir,
+                          X86_32_PDPTE_BASE(base), pdir);
+        if (err_is_fail(err)) {
+            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
         }
-        prev = walk;
-        walk = walk->next;
-    }
-    USER_PANIC("Should not get here");
-}
-
-/**
- * \brief Allocates a new VNode, adding it to the page table and our metadata
- */
-static errval_t alloc_vnode(struct pmap_x86 *pmap, struct vnode *root,
-                            enum objtype type, uint32_t entry,
-                            struct vnode **retvnode)
-{
-    errval_t err;
-
-    struct vnode *newvnode = slab_alloc(&pmap->slab);
-    if (newvnode == NULL) {
-        return LIB_ERR_SLAB_ALLOC_FAIL;
     }
+#else
+    *pdir = &pmap->root;
+#endif
 
-    // The VNode capability
-    err = pmap->p.slot_alloc->alloc(pmap->p.slot_alloc, &newvnode->u.vnode.cap);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_SLOT_ALLOC);
-    }
-
-    err = vnode_create(newvnode->u.vnode.cap, type);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_VNODE_CREATE);
-    }
-
-    // Map it
-    err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
-                    X86_32_PTABLE_ACCESS_DEFAULT, 0, 1);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_VNODE_MAP);
-    }
-
-    // The VNode meta data
-    newvnode->is_vnode  = true;
-    newvnode->entry     = entry;
-    newvnode->next      = root->u.vnode.children;
-    root->u.vnode.children      = newvnode;
-    newvnode->u.vnode.children  = NULL;
-
-    *retvnode = newvnode;
     return SYS_ERR_OK;
 }
 
@@ -218,22 +120,10 @@ static errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
 {
     errval_t err;
     struct vnode *pdir;
-
-#ifdef CONFIG_PAE
-    struct vnode *root = &pmap->root;
-    assert(root != NULL);
-
-    // PDPTE mapping
-    if((pdir = find_vnode(root, X86_32_PDPTE_BASE(base))) == NULL) {
-        err = alloc_vnode(pmap, root, ObjType_VNode_x86_32_pdir,
-                          X86_32_PDPTE_BASE(base), &pdir);
-        if (err_is_fail(err)) {
-            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
-        }
+    err = get_pdir(pmap, base, &pdir);
+    if (err_is_fail(err)) {
+        return err;
     }
-#else
-    pdir = &pmap->root;
-#endif
 
     // PDIR mapping
     if((*ptable = find_vnode(pdir, X86_32_PDIR_BASE(base))) == NULL) {
@@ -246,77 +136,47 @@ static errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
 
     return SYS_ERR_OK;
 }
-/**
- * \brief Returns the vnode for the page directory mapping a given vspace address
- */
-static errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
-                           struct vnode **pdir)
-{
-#ifdef CONFIG_PAE
-    struct vnode *root = &pmap->root;
-    assert(root != NULL);
 
-    // PDPTE mapping
-    if((*pdir = find_vnode(root, X86_32_PDPTE_BASE(base))) == NULL) {
-        errval_t err = alloc_vnode(pmap, root, ObjType_VNode_x86_32_pdir,
-                          X86_32_PDPTE_BASE(base), pdir);
-        if (err_is_fail(err)) {
-            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
-        }
-    }
-#else
-    *pdir = &pmap->root;
-#endif
-
-    return SYS_ERR_OK;
-}
-
-
-static struct vnode *find_ptable(struct pmap_x86 *pmap, genvaddr_t base)
+static struct vnode *find_pdir(struct pmap_x86 *pmap, genvaddr_t base)
 {
     struct vnode *root = &pmap->root;
-    struct vnode *pdir;
     assert(root != NULL);
 
 #ifdef CONFIG_PAE
     // PDPT mapping
-    if((pdir = find_vnode(root, X86_32_PDPT_BASE(base))) == NULL) {
-        return NULL;
-    }
+    return find_vnode(root, X86_32_PDPT_BASE(base));
 #else
-    pdir = root;
+    return root;
 #endif
-
-    // PDIR mapping
-    return find_vnode(pdir, X86_32_PDIR_BASE(base));
 }
 
-static struct vnode *find_pdir(struct pmap_x86 *pmap, genvaddr_t base)
+static struct vnode *find_ptable(struct pmap_x86 *pmap, genvaddr_t base)
 {
-    struct vnode *root = &pmap->root;
-    assert(root != NULL);
+    struct vnode *pdir = find_pdir(pmap, base);
 
-#ifdef CONFIG_PAE
-    // PDPT mapping
-    return find_vnode(root, X86_32_PDPT_BASE(base));
-#else
-    return root;
-#endif
+    if (pdir) {
+        // PDIR mapping
+        return find_vnode(pdir, X86_32_PDIR_BASE(base));
+    } else {
+        return NULL;
+    }
 }
 
-static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr, genvaddr_t vend,
-                              struct capref frame, size_t offset, size_t pte_count,
+static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
+                              genvaddr_t vend, struct capref frame,
+                              size_t offset, size_t pte_count,
                               vregion_flags_t flags)
 {
     //printf("[do_single_map] vaddr = 0x%"PRIxGENVADDR"\n", vaddr);
     // translate flags
-    paging_x86_32_flags_t pmap_flags = vregion_to_pmap_flag(flags &~(FLAGS_LARGE));
+    paging_x86_32_flags_t pmap_flags = vregion_to_pmap_flag(flags);
 
     // Get the page table and do mapping specific alterations
     struct vnode *ptable;
     errval_t err;
     size_t base;
-    if (flags&FLAGS_LARGE) {
+
+    if (flags & VREGION_FLAGS_LARGE) {
         //4M/2M(PAE) mapping
         err = get_pdir(pmap, vaddr, &ptable);
         base = X86_32_PDIR_BASE(vaddr);
@@ -328,11 +188,20 @@ static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr, genvaddr_
     if (err_is_fail(err)) {
         return err_push(err, LIB_ERR_PMAP_GET_PTABLE);
     }
-    
+    assert(ptable->is_vnode);
+
     // check if there is an overlapping mapping
-    if (has_vnode(ptable, base, pte_count)) {
-        printf("page already exists in 0x%"PRIxGENVADDR"--0x%"PRIxGENVADDR"\n", vaddr, vend);
-        return LIB_ERR_PMAP_EXISTING_MAPPING;
+    if (has_vnode(ptable, base, pte_count, false)) {
+        if (has_vnode(ptable, base, pte_count, true)) {
+            printf("page already exists in 0x%"
+                    PRIxGENVADDR"--0x%"PRIxGENVADDR"\n", vaddr, vend);
+            return LIB_ERR_PMAP_EXISTING_MAPPING;
+        } else {
+            // clean out empty page tables. We do this here because we benefit
+            // from having the page tables in place when doing lots of small
+            // mappings
+            remove_empty_vnodes(pmap, ptable, base, pte_count);
+        }
     }
 
     // setup userspace mapping
@@ -365,25 +234,23 @@ static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
     //printf("[do_map] vaddr = 0x%"PRIxGENVADDR", size = %zd\n", vaddr, size);
     errval_t err;
 
-    size_t page_size;
-    size_t base;
-
-    // mapping specific parts
-    if(flags&FLAGS_LARGE) {
+    // figure out mapping parameters
+    size_t page_size = X86_32_BASE_PAGE_SIZE;
+    size_t base = X86_32_PTABLE_BASE(vaddr);
+    if(flags & VREGION_FLAGS_LARGE) {
         //4M/2M (PAE) pages
         page_size = X86_32_LARGE_PAGE_SIZE;
         base = X86_32_PDIR_BASE(vaddr);
-    } else {
-        //4k mapping
-        page_size = X86_32_BASE_PAGE_SIZE;
-        base = X86_32_PTABLE_BASE(vaddr);
     }
 
+    // TODO: needs overhaul for mixed-size mappings
+    // TODO: need to make sure we can map that much
     size = ROUND_UP(size, page_size);
     size_t pte_count = DIVIDE_ROUND_UP(size, page_size);
     genvaddr_t vend = vaddr + size;
 
-    if (is_same_pdir(vaddr, vend) || (is_same_pdpt(vaddr, vend) && flags&FLAGS_LARGE)) {
+    if (is_same_pdir(vaddr, vend) ||
+        (flags & VREGION_FLAGS_LARGE && is_same_pdpt(vaddr, vend))) {
         // fast path
         err = do_single_map(pmap, vaddr, vend, frame, offset, pte_count, flags);
         if (err_is_fail(err)) {
@@ -419,7 +286,8 @@ static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
             frame = next;
 
             // do mapping
-            err = do_single_map(pmap, vaddr, temp_end, frame, offset, X86_32_PTABLE_SIZE, flags);
+            err = do_single_map(pmap, vaddr, temp_end, frame, offset,
+                    X86_32_PTABLE_SIZE, flags);
             if (err_is_fail(err)) {
                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
             }
@@ -427,7 +295,7 @@ static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
 
         // map remaining part
         offset += c * page_size;
-        if(flags&FLAGS_LARGE) {
+        if(flags & VREGION_FLAGS_LARGE) {
             // 4M/2M (PAE) mapping
             c = X86_32_PDIR_BASE(vend) - X86_32_PDIR_BASE(temp_end);
         } else {
@@ -620,37 +488,57 @@ static errval_t map(struct pmap *pmap, genvaddr_t vaddr, struct capref frame,
     return err;
 }
 
-static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr, size_t pte_count, bool delete_cap)
+/**
+ * \brief Find mapping for `vaddr` in `pmap`.
+ * \arg pmap the pmap to search in
+ * \arg vaddr the virtual address to search for
+ * \arg pt the last-level page table meta-data we found if any
+ * \arg page the page meta-data we found if any
+ * \returns `true` iff we found a mapping for vaddr
+ */
+static bool find_mapping(struct pmap_x86 *pmap, genvaddr_t vaddr,
+                         struct vnode **outpt, struct vnode **outpage)
 {
-    errval_t err;
-    bool large_flag = false;
-    struct vnode *page;
-    //determine if we unmap a large page
-    if ((page = find_pdir(pmap, vaddr)) != NULL) {
-#ifdef CONFIG_PAE        
-        if ((page = find_vnode(page, X86_32_PDPT_BASE(vaddr))) != NULL) {
-#else
-        if ((page = find_vnode(page, X86_32_PDIR_BASE(vaddr))) != NULL) {
-#endif
-            large_flag = page->u.frame.flags&FLAGS_LARGE;
+    struct vnode *pdir = NULL, *pt = NULL, *page = NULL;
+
+    // find page and last-level page table (can be pdir or pdpt)
+    if ((pdir = find_pdir(pmap, vaddr)) != NULL) {
+        page = find_vnode(pdir, X86_32_PDIR_BASE(vaddr));
+        if (page && page->is_vnode) { // not 2M/4M pages
+            pt = page;
+            page = find_vnode(pt, X86_32_PTABLE_BASE(vaddr));
+        } else if (page) {
+            pt = pdir;
         }
     }
-    
-    struct vnode *pt;
-    size_t base;
-    if (large_flag) {
-        pt = find_pdir(pmap, vaddr);
-        base = X86_32_PDIR_BASE(vaddr);
+    if (outpt) {
+        *outpt = pt;
+    }
+    if (outpage) {
+        *outpage = page;
+    }
+    if (pt) {
+        return true;
     } else {
-        pt = find_ptable(pmap, vaddr);
-        base = X86_32_PTABLE_BASE(vaddr);
+        return false;
     }
+}
+
+static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr,
+                                size_t pte_count, bool delete_cap)
+{
+    errval_t err;
+    struct vnode *pt = NULL, *page = NULL;
+
+    find_mapping(pmap, vaddr, &pt, &page);
+
     if (pt) {
-        page = find_vnode(pt, base);
         if (page && page->u.frame.pte_count == pte_count) {
-            err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap, page->entry, page->u.frame.pte_count);
+            err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap, page->entry,
+                              page->u.frame.pte_count);
             if (err_is_fail(err)) {
-                printf("vnode_unmap returned error: %s (%d)\n", err_getstring(err), err_no(err));
+                printf("vnode_unmap returned error: %s (%d)\n",
+                        err_getstring(err), err_no(err));
                 return err_push(err, LIB_ERR_VNODE_UNMAP);
             }
 
@@ -673,6 +561,15 @@ static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr, size_t
     return SYS_ERR_OK;
 }
 
+static inline bool is_large_page(struct vnode *p)
+{
+    return !p->is_vnode && p->u.frame.flags & VREGION_FLAGS_LARGE;
+}
+static inline bool is_huge_page(struct vnode *p)
+{
+    return !p->is_vnode && p->u.frame.flags & VREGION_FLAGS_HUGE;
+}
+
 /**
  * \brief Remove page mappings
  *
@@ -690,19 +587,15 @@ static errval_t unmap(struct pmap *pmap, genvaddr_t vaddr, size_t size,
     
     //determine if we unmap a larger page
     struct vnode* page = NULL;
-    bool large_flag = false;
-    //find table, then entry
-    if ((page = find_pdir(x86, vaddr)) != NULL) {
-#ifdef CONFIG_PAE        
-        if ((page = find_vnode(page, X86_32_PDPT_BASE(vaddr))) != NULL) {
-#else
-        if ((page = find_vnode(page, X86_32_PDIR_BASE(vaddr))) != NULL) {
-#endif
-            large_flag = page->u.frame.flags&FLAGS_LARGE;
-        }
+
+    if (!find_mapping(x86, vaddr, NULL, &page)) {
+        // TODO: better error
+        return LIB_ERR_PMAP_UNMAP;
     }
+    assert(!page->is_vnode);
+
     size_t page_size = X86_32_BASE_PAGE_SIZE;
-    if (large_flag) {
+    if (is_large_page(page)) {
         //large 2M page
         page_size = X86_32_LARGE_PAGE_SIZE;
     }
@@ -710,7 +603,8 @@ static errval_t unmap(struct pmap *pmap, genvaddr_t vaddr, size_t size,
     size = ROUND_UP(size, page_size);
     genvaddr_t vend = vaddr + size;
 
-    if (is_same_pdir(vaddr, vend) || (is_same_pdpt(vaddr, vend) && large_flag)) {
+    if (is_same_pdir(vaddr, vend) ||
+        (is_same_pdpt(vaddr, vend) && is_large_page(page))) {
         // fast path
         err = do_single_unmap(x86, vaddr, size / page_size, false);
         if (err_is_fail(err)) {
@@ -798,6 +692,8 @@ static errval_t do_single_modify_flags(struct pmap_x86 *pmap, genvaddr_t vaddr,
  * \param vaddr    The virtual address to unmap
  * \param flags    New flags for the mapping
  * \param retsize  If non-NULL, filled in with the actual size modified
+ *
+ * TODO: fix for large page mappings
  */
 static errval_t modify_flags(struct pmap *pmap, genvaddr_t vaddr, size_t size,
                              vregion_flags_t flags, size_t *retsize)
index 7d6e3e7..9dbc557 100644 (file)
@@ -84,219 +84,21 @@ static inline genvaddr_t get_addr_prefix(genvaddr_t va, uint8_t size)
 {
     return va >> size;
 }
-// only_pages true ==> return true iff there is an actual mapping here, and
-// not just intermediate page tables
-static bool has_vnode(struct vnode *root, uint32_t entry, size_t len, bool only_pages)
-{
-    assert(root != NULL);
-    assert(root->is_vnode);
-    struct vnode *n;
-
-    uint32_t end_entry = entry + len;
-
-    // region we check [entry .. end_entry)
-
-    for (n = root->u.vnode.children; n; n = n->next) {
-        // n is page table, we need to check if it's anywhere inside the
-        // region to check [entry .. end_entry)
-        // this amounts to n->entry == entry for len = 1
-        if (n->is_vnode && n->entry >= entry && n->entry < end_entry) {
-            if (only_pages) {
-                return has_vnode(n, 0, X86_64_PTABLE_SIZE, true);
-            }
-            return true;
-        }
-        // this remains the same regardless of `only_pages`.
-        // n is frame [n->entry .. end)
-        // 3 cases:
-        // 1) entry < n->entry && end_entry >= end --> n is a strict subset of
-        // our region
-        // 2) entry inside n (entry >= n->entry && entry < end)
-        // 3) end_entry inside n (end_entry >= n->entry && end_entry < end)
-        uint32_t end = n->entry + n->u.frame.pte_count;
-        if (entry < n->entry && end_entry >= end) {
-            return true;
-        }
-        if (entry >= n->entry && entry < end) {
-            return true;
-        }
-        if (end_entry > n->entry && end_entry < end) {
-            return true;
-        }
-    }
-
-    return false;
-}
-
-
-/**
- * \brief Starting at a given root, return the vnode with starting entry equal to #entry
- */
-static struct vnode *find_vnode(struct vnode *root, uint32_t entry)
-{
-    assert(root != NULL);
-    assert(root->is_vnode);
-    struct vnode *n;
-
-    for(n = root->u.vnode.children; n != NULL; n = n->next) {
-        if(n->entry == entry) {
-            return n;
-        }
-    }
-    return NULL;
-}
-
-static bool inside_region(struct vnode *root, uint32_t entry, uint32_t npages)
-{
-    assert(root != NULL);
-    assert(root->is_vnode);
-
-    struct vnode *n;
-
-    for (n = root->u.vnode.children; n; n = n->next) {
-        if (!n->is_vnode) {
-            uint16_t end = n->entry + n->u.frame.pte_count;
-            if (n->entry <= entry && entry + npages <= end) {
-                return true;
-            }
-        }
-    }
-
-    return false;
-}
-
-static void remove_vnode(struct vnode *root, struct vnode *item)
-{
-    assert(root->is_vnode);
-    struct vnode *walk = root->u.vnode.children;
-    struct vnode *prev = NULL;
-    while (walk) {
-        if (walk == item) {
-            if (prev) {
-                prev->next = walk->next;
-                return;
-            } else {
-                root->u.vnode.children = walk->next;
-                return;
-            }
-        }
-        prev = walk;
-        walk = walk->next;
-    }
-    assert(!"Should not get here");
-}
-
-static void remove_empty_vnodes(struct pmap_x86 *pmap, struct vnode *root,
-                                uint32_t entry, size_t len)
-{
-    errval_t err;
-    uint32_t end_entry = entry + len;
-    for (struct vnode *n = root->u.vnode.children; n; n = n->next) {
-        if (n->entry >= entry && n->entry < end_entry) {
-            // here we know that all vnodes we're interested in are
-            // page tables
-            assert(n->is_vnode);
-            if (n->u.vnode.children) {
-                remove_empty_vnodes(pmap, n, 0, X86_64_PTABLE_SIZE);
-            }
-
-            // unmap
-            err = vnode_unmap(root->u.vnode.cap, n->u.vnode.cap, n->entry, 1);
-            if (err_is_fail(err)) {
-                debug_printf("remove_empty_vnodes: vnode_unmap: %s\n",
-                        err_getstring(err));
-            }
-
-            // delete capability
-            err = cap_destroy(n->u.vnode.cap);
-            if (err_is_fail(err)) {
-                debug_printf("remove_empty_vnodes: cap_destroy: %s\n",
-                        err_getstring(err));
-            }
-
-            // remove vnode from list
-            remove_vnode(root, n);
-            slab_free(&pmap->slab, n);
-        }
-    }
-}
-
-/**
- * \brief Allocates a new VNode, adding it to the page table and our metadata
- */
-static errval_t alloc_vnode(struct pmap_x86 *pmap, struct vnode *root,
-                            enum objtype type, uint32_t entry,
-                            struct vnode **retvnode)
-{
-    errval_t err;
-
-    struct vnode *newvnode = slab_alloc(&pmap->slab);
-    if (newvnode == NULL) {
-        return LIB_ERR_SLAB_ALLOC_FAIL;
-    }
-
-    // The VNode capability
-    err = pmap->p.slot_alloc->alloc(pmap->p.slot_alloc, &newvnode->u.vnode.cap);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_SLOT_ALLOC);
-    }
-
-    err = vnode_create(newvnode->u.vnode.cap, type);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_VNODE_CREATE);
-    }
-
-    // Map it
-    err = vnode_map(root->u.vnode.cap, newvnode->u.vnode.cap, entry,
-                    PTABLE_ACCESS_DEFAULT, 0, 1);
-    if (err_is_fail(err)) {
-        return err_push(err, LIB_ERR_VNODE_MAP);
-    }
-
-    // The VNode meta data
-    newvnode->is_vnode  = true;
-    newvnode->entry     = entry;
-    newvnode->next      = root->u.vnode.children;
-    root->u.vnode.children = newvnode;
-    newvnode->u.vnode.children = NULL;
-
-    *retvnode = newvnode;
-    return SYS_ERR_OK;
-}
 
 /**
- * \brief Returns the vnode for the pagetable mapping a given vspace address
+ * \brief Returns the vnode for the pdpt mapping a given vspace address
  */
-static errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
-                            struct vnode **ptable)
+static inline errval_t get_pdpt(struct pmap_x86 *pmap, genvaddr_t base,
+                                struct vnode **pdpt)
 {
     errval_t err;
     struct vnode *root = &pmap->root;
-    struct vnode *pdpt, *pdir;
     assert(root != NULL);
 
     // PML4 mapping
-    if((pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
+    if((*pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
         err = alloc_vnode(pmap, root, ObjType_VNode_x86_64_pdpt,
-                            X86_64_PML4_BASE(base), &pdpt);
-        if (err_is_fail(err)) {
-            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
-        }
-    }
-
-    // PDPT mapping
-    if((pdir = find_vnode(pdpt, X86_64_PDPT_BASE(base))) == NULL) {
-        err = alloc_vnode(pmap, pdpt, ObjType_VNode_x86_64_pdir,
-                            X86_64_PDPT_BASE(base), &pdir);
-        if (err_is_fail(err)) {
-            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
-        }
-    }
-
-    // PDIR mapping
-    if((*ptable = find_vnode(pdir, X86_64_PDIR_BASE(base))) == NULL) {
-        err = alloc_vnode(pmap, pdir, ObjType_VNode_x86_64_ptable,
-                            X86_64_PDIR_BASE(base), ptable);
+                            X86_64_PML4_BASE(base), pdpt);
         if (err_is_fail(err)) {
             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
         }
@@ -306,26 +108,19 @@ static errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
 }
 
 /**
- * \brief Returns the vnode for the pagedirectory (for large pages) mapping a given vspace address
- *
+ * \brief Returns the vnode for the page directory mapping a given vspace
+ * address
  */
-static errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
-                            struct vnode **pdir)
+static inline errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
+                                struct vnode **pdir)
 {
     errval_t err;
-    struct vnode *root = &pmap->root;
     struct vnode *pdpt;
-    assert(root != NULL);
-
-    // PML4 mapping
-    if((pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
-        err = alloc_vnode(pmap, root, ObjType_VNode_x86_64_pdpt,
-                            X86_64_PML4_BASE(base), &pdpt);
-        if (err_is_fail(err)) {
-            printf("failure mapping pml4\n");
-            return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
-        }
+    err = get_pdpt(pmap, base, &pdpt);
+    if (err_is_fail(err)) {
+        return err;
     }
+    assert(pdpt != NULL);
 
     // PDPT mapping
     if((*pdir = find_vnode(pdpt, X86_64_PDPT_BASE(base))) == NULL) {
@@ -341,84 +136,76 @@ static errval_t get_pdir(struct pmap_x86 *pmap, genvaddr_t base,
 }
          
 /**
- * \brief Returns the vnode for the pdpt (for huge pages) mapping a given vspace address
- *
+ * \brief Returns the vnode for the pagetable mapping a given vspace address
  */
-static errval_t get_pdpt(struct pmap_x86 *pmap, genvaddr_t base,
-                            struct vnode **pdpt)
+static inline errval_t get_ptable(struct pmap_x86 *pmap, genvaddr_t base,
+                                  struct vnode **ptable)
 {
     errval_t err;
-    struct vnode *root = &pmap->root;
-    assert(root != NULL);
+    struct vnode *pdir;
+    err = get_pdir(pmap, base, &pdir);
+    if (err_is_fail(err)) {
+        return err;
+    }
+    assert(pdir != NULL);
 
-    // PML4 mapping
-    if((*pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
-        err = alloc_vnode(pmap, root, ObjType_VNode_x86_64_pdpt,
-                            X86_64_PML4_BASE(base), pdpt);
+    // PDIR mapping
+    if((*ptable = find_vnode(pdir, X86_64_PDIR_BASE(base))) == NULL) {
+        err = alloc_vnode(pmap, pdir, ObjType_VNode_x86_64_ptable,
+                            X86_64_PDIR_BASE(base), ptable);
         if (err_is_fail(err)) {
             return err_push(err, LIB_ERR_PMAP_ALLOC_VNODE);
         }
     }
 
     return SYS_ERR_OK;
-}                   
-                            
+}
 
 /**
- * \brief Returns the vnode for the pagetable mapping a given vspace address,
- *     without performing allocations as get_ptable() does
+ * \brief Returns the vnode for the page directory pointer table mapping for a
+ * given vspace address
  */
-static struct vnode *find_ptable(struct pmap_x86 *pmap, genvaddr_t base)
+static inline struct vnode *find_pdpt(struct pmap_x86 *pmap, genvaddr_t base)
 {
     struct vnode *root = &pmap->root;
-    struct vnode *pdpt, *pdir;
     assert(root != NULL);
 
-    // PML4 mapping
-    if((pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
-        return NULL;
-    }
-
     // PDPT mapping
-    if((pdir = find_vnode(pdpt, X86_64_PDPT_BASE(base))) == NULL) {
-        return NULL;
-    }
-
-    // PDIR mapping
-    return find_vnode(pdir, X86_64_PDIR_BASE(base));
+    return find_vnode(root, X86_64_PML4_BASE(base));
 }
+
 /**
- * \brief Returns the vnode for the page directory mapping a given vspace address,
- *     without performing allocations as get_pdir() does
+ * \brief Returns the vnode for the page directory mapping a given vspace
+ * address, without performing allocations as get_pdir() does
  */
-static struct vnode *find_pdir(struct pmap_x86 *pmap, genvaddr_t base)
+static inline struct vnode *find_pdir(struct pmap_x86 *pmap, genvaddr_t base)
 {
-    struct vnode *root = &pmap->root;
-    struct vnode *pdpt;
-    assert(root != NULL);
+    struct vnode *pdpt = find_pdpt(pmap, base);
 
-    // PML4 mapping
-    if((pdpt = find_vnode(root, X86_64_PML4_BASE(base))) == NULL) {
+    if (pdpt) {
+        // PDPT mapping
+        return find_vnode(pdpt, X86_64_PDPT_BASE(base));
+    } else {
         return NULL;
     }
-
-    // PDPT mapping
-    return find_vnode(pdpt, X86_64_PDPT_BASE(base));
 }
+
 /**
- * \brief Returns the vnode for the page directory pointer table mapping 
- *     for a given vspace address
+ * \brief Returns the vnode for the pagetable mapping a given vspace address,
+ * without performing allocations as get_ptable() does
  */
-static struct vnode *find_pdpt(struct pmap_x86 *pmap, genvaddr_t base)
+static inline struct vnode *find_ptable(struct pmap_x86 *pmap, genvaddr_t base)
 {
-    struct vnode *root = &pmap->root;
-    assert(root != NULL);
+    struct vnode *pdir = find_pdir(pmap, base);
 
-    // PDPT mapping
-    return find_vnode(root, X86_64_PML4_BASE(base));
+    if (pdir) {
+        // PDIR mapping
+        return find_vnode(pdir, X86_64_PDIR_BASE(base));
+    } else {
+        return NULL;
+    }
 }
 
-
 static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
                               genvaddr_t vend, struct capref frame,
                               size_t offset, size_t pte_count,
@@ -446,16 +233,16 @@ static errval_t do_single_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
         err = get_ptable(pmap, vaddr, &ptable);
         table_base = X86_64_PTABLE_BASE(vaddr);
     }
-    assert(ptable->is_vnode);
-
     if (err_is_fail(err)) {
         return err_push(err, LIB_ERR_PMAP_GET_PTABLE);
     }
+    assert(ptable->is_vnode);
 
     // check if there is an overlapping mapping
     if (has_vnode(ptable, table_base, pte_count, false)) {
         if (has_vnode(ptable, table_base, pte_count, true)) {
-            printf("page already exists in 0x%"PRIxGENVADDR"--0x%"PRIxGENVADDR"\n", vaddr, vend);
+            printf("page already exists in 0x%"
+                    PRIxGENVADDR"--0x%"PRIxGENVADDR"\n", vaddr, vend);
             return LIB_ERR_PMAP_EXISTING_MAPPING;
         } else {
             // clean out empty page tables. We do this here because we benefit
@@ -538,8 +325,8 @@ static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
     // all mapping on one leaf table?
     // TODO: needs some work for mixed-size mappings
     if (is_same_pdir(vaddr, vend) ||
-            (flags & VREGION_FLAGS_LARGE && is_same_pdpt(vaddr, vend)) ||
-            (flags & VREGION_FLAGS_HUGE && is_same_pml4(vaddr, vend))) {
+        (flags & VREGION_FLAGS_LARGE && is_same_pdpt(vaddr, vend)) ||
+        (flags & VREGION_FLAGS_HUGE && is_same_pml4(vaddr, vend))) {
         // fast path
         if (debug_out) {
             debug_printf("  do_map: fast path: %zd\n", pte_count);
@@ -586,7 +373,8 @@ static errval_t do_map(struct pmap_x86 *pmap, genvaddr_t vaddr,
             if (debug_out) {
                 debug_printf("  do_map: slow path: full leaf\n");
             }
-            err = do_single_map(pmap, vaddr, temp_end, frame, offset, X86_64_PTABLE_SIZE, flags);
+            err = do_single_map(pmap, vaddr, temp_end, frame, offset,
+                    X86_64_PTABLE_SIZE, flags);
             if (err_is_fail(err)) {
                 return err_push(err, LIB_ERR_PMAP_DO_MAP);
             }
@@ -840,7 +628,8 @@ static bool find_mapping(struct pmap_x86 *pmap, genvaddr_t vaddr,
     }
 }
 
-static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr, size_t pte_count, bool delete_cap)
+static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr,
+                                size_t pte_count, bool delete_cap)
 {
     errval_t err;
     struct vnode *pt = NULL, *page = NULL;
@@ -851,7 +640,8 @@ static errval_t do_single_unmap(struct pmap_x86 *pmap, genvaddr_t vaddr, size_t
 
     if (pt) {
         if (page && page->u.frame.pte_count == pte_count) {
-            err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap, page->entry, page->u.frame.pte_count);
+            err = vnode_unmap(pt->u.vnode.cap, page->u.frame.cap, page->entry,
+                              page->u.frame.pte_count);
             if (err_is_fail(err)) {
                 printf("vnode_unmap returned error: %s (%d)\n",
                         err_getstring(err), err_no(err));
@@ -915,12 +705,12 @@ static errval_t unmap(struct pmap *pmap, genvaddr_t vaddr, size_t size,
     size_t page_size = X86_64_BASE_PAGE_SIZE;
     size_t table_base = X86_64_PTABLE_BASE(vaddr);
     uint8_t map_bits= X86_64_BASE_PAGE_BITS + 9;
-    if (page->u.frame.flags & VREGION_FLAGS_LARGE) {
+    if (is_large_page(page)) {
         //large 2M page
         page_size = X86_64_LARGE_PAGE_SIZE;
         table_base = X86_64_PDIR_BASE(vaddr);
         map_bits = X86_64_LARGE_PAGE_BITS + 9;
-    } else if (page->u.frame.flags & VREGION_FLAGS_HUGE) {
+    } else if (is_huge_page(page)) {
         //huge 1GB page
         page_size = X86_64_HUGE_PAGE_SIZE;
         table_base = X86_64_PDPT_BASE(vaddr);