9ns: ensure the parent of a rename target is a directory
[akaros.git] / kern / src / pagemap.c
index 84fab40..836d4c5 100644 (file)
@@ -1,4 +1,4 @@
-/* Copyright (c) 2010 The Regents of the University of California
+/* Copyright (c) 2014 The Regents of the University of California
  * Barret Rhoden <brho@cs.berkeley.edu>
  * See LICENSE for details.
  *
 #include <kref.h>
 #include <assert.h>
 #include <stdio.h>
+#include <pagemap.h>
+#include <rcu.h>
 
-/* Initializes a PM.  Host should be an *inode or a *bdev (doesn't matter).  The
- * reference this stores is uncounted. */
+void pm_add_vmr(struct page_map *pm, struct vm_region *vmr)
+{
+       /* note that the VMR being reverse-mapped by the PM is protected by the
+        * PM's lock.  we clearly need a write lock here, but removal also needs
+        * a write lock, so later when removal holds this, it delays munmaps and
+        * keeps the VMR connected. */
+       spin_lock(&pm->pm_lock);
+       TAILQ_INSERT_TAIL(&pm->pm_vmrs, vmr, vm_pm_link);
+       spin_unlock(&pm->pm_lock);
+}
+
+void pm_remove_vmr(struct page_map *pm, struct vm_region *vmr)
+{
+       spin_lock(&pm->pm_lock);
+       TAILQ_REMOVE(&pm->pm_vmrs, vmr, vm_pm_link);
+       spin_unlock(&pm->pm_lock);
+}
+
+/* PM slot void *s look like this:
+ *
+ * |--11--|--1--|----52 or 20 bits--|
+ * | ref  | flag|    ppn of page    |
+ *              \  <--- meta shift -/
+ *
+ * The setter funcs return the void* that should update slot_val; it doesn't
+ * change slot_val in place (it's a val, not the addr) */
+
+#ifdef CONFIG_64BIT
+# define PM_FLAGS_SHIFT 52
+#else
+# define PM_FLAGS_SHIFT 20
+#endif
+#define PM_REFCNT_SHIFT (PM_FLAGS_SHIFT + 1)
+
+#define PM_UNUSED_FLAG (1UL << PM_FLAGS_SHIFT)
+
+static int pm_slot_check_refcnt(void *slot_val)
+{
+       return (unsigned long)slot_val >> PM_REFCNT_SHIFT;
+}
+
+static void *pm_slot_inc_refcnt(void *slot_val)
+{
+       void *ret;
+
+       ret = (void*)((unsigned long)slot_val + (1UL << PM_REFCNT_SHIFT));
+       /* Catches previously negative refcnts */
+       assert(pm_slot_check_refcnt(ret) > 0);
+       return ret;
+}
+
+static void *pm_slot_dec_refcnt(void *slot_val)
+{
+       assert(pm_slot_check_refcnt(slot_val) > 0);
+       return (void*)((unsigned long)slot_val - (1UL << PM_REFCNT_SHIFT));
+}
+
+static struct page *pm_slot_get_page(void *slot_val)
+{
+       if (!slot_val)
+               return 0;
+       return ppn2page((unsigned long)slot_val & ((1UL << PM_FLAGS_SHIFT) - 1));
+}
+
+static void *pm_slot_set_page(void *slot_val, struct page *pg)
+{
+       assert(pg != pages);    /* we should never alloc page 0, for sanity */
+       return (void*)(page2ppn(pg) | ((unsigned long)slot_val &
+                                      ~((1UL << PM_FLAGS_SHIFT) - 1)));
+}
+
+/* Initializes a PM.  Host should be an fs_file.  The reference this stores is
+ * uncounted. */
 void pm_init(struct page_map *pm, struct page_map_operations *op, void *host)
 {
-       pm->pm_bdev = host;                                             /* note the uncounted ref */
+       pm->pm_file = host;
        radix_tree_init(&pm->pm_tree);
-       spinlock_init(&pm->pm_tree_lock);
-       pm->pm_num_pages = 0;                                   /* no pages in a new pm */
+       pm->pm_num_pages = 0;
        pm->pm_op = op;
-       pm->pm_flags = 0;
+       qlock_init(&pm->pm_qlock);
+       spinlock_init(&pm->pm_lock);
+       TAILQ_INIT(&pm->pm_vmrs);
 }
 
-/* Looks up the index'th page in the page map, returning an incref'd reference,
- * or 0 if it was not in the map. */
-struct page *pm_find_page(struct page_map *pm, unsigned long index)
+/* Looks up the index'th page in the page map, returning a refcnt'd reference
+ * that need to be dropped with pm_put_page, or 0 if it was not in the map. */
+static struct page *pm_find_page(struct page_map *pm, unsigned long index)
 {
-       spin_lock(&pm->pm_tree_lock);
-       struct page *page = (struct page*)radix_lookup(&pm->pm_tree, index);
-       if (page)
-               page_incref(page);
-       spin_unlock(&pm->pm_tree_lock);
+       void **tree_slot;
+       void *old_slot_val, *slot_val;
+       struct page *page = 0;
+
+       /* We use rcu to protect our radix walk, specifically the tree_slot
+        * pointer.  We get our own 'pm refcnt' on the slot itself, which
+        * doesn't need RCU. */
+       rcu_read_lock();
+       /* We're syncing with removal.  The deal is that if we grab the page
+        * (and we'd only do that if the page != 0), we up the slot ref and
+        * clear removal.  A remover will only remove it if removal is still
+        * set.  If we grab and release while removal is in progress, even
+        * though we no longer hold the ref, we have unset removal.  Also, to
+        * prevent removal where we get a page well before the removal process,
+        * the removal won't even bother when the slot refcnt is upped. */
+       tree_slot = radix_lookup_slot(&pm->pm_tree, index);
+       if (!tree_slot)
+               goto out;
+       do {
+               old_slot_val = ACCESS_ONCE(*tree_slot);
+               slot_val = old_slot_val;
+               page = pm_slot_get_page(slot_val);
+               if (!page)
+                       goto out;
+               slot_val = pm_slot_inc_refcnt(slot_val); /* not a page kref */
+       } while (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val));
+       assert(page->pg_tree_slot == tree_slot);
+out:
+       rcu_read_unlock();
        return page;
 }
 
 /* Attempts to insert the page into the page_map, returns 0 for success, or an
  * error code if there was one already (EEXIST) or we ran out of memory
- * (ENOMEM).  On success, this will preemptively lock the page, and will also
- * store a reference to the page in the pm. */
-int pm_insert_page(struct page_map *pm, unsigned long index, struct page *page)
-{
-       int error = 0;
-       spin_lock(&pm->pm_tree_lock);
-       error = radix_insert(&pm->pm_tree, index, page);
-       if (!error) {
-               page_incref(page);
-               page->pg_flags |= PG_LOCKED | PG_BUFFER;
-               page->pg_sem.nr_signals = 0;            /* ensure others will block */
-               page->pg_mapping = pm;
-               page->pg_index = index;
-               pm->pm_num_pages++;
-       }
-       spin_unlock(&pm->pm_tree_lock);
-       return error;
-}
-
-/* Removes the page, including its reference.  Not sure yet what interface we
- * want to this (pm and index or page), and this has never been used.  There are
- * also issues with when you want to call this, since a page in the cache may be
- * mmap'd by someone else. */
-int pm_remove_page(struct page_map *pm, struct page *page)
-{
-       void *retval;
-       warn("pm_remove_page() hasn't been thought through or tested.");
-       /* TODO: check for dirty pages, don't let them be removed right away.  Need
-        * to schedule them for writeback, and then remove them later (callback).
-        * Also, need to be careful - anyone holding a reference to a page can dirty
-        * it concurrently. */
-       spin_lock(&pm->pm_tree_lock);
-       retval = radix_delete(&pm->pm_tree, page->pg_index);
-       spin_unlock(&pm->pm_tree_lock);
-       assert(retval == (void*)page);
-       page_decref(page);
-       pm->pm_num_pages--;
+ * (ENOMEM).
+ *
+ * On success, callers *lose* their page ref, but get a PM slot ref.  This slot
+ * ref is sufficient to keep the page alive (slot ref protects the page ref)..
+ *
+ * Makes no assumptions about the quality of the data loaded, that's up to the
+ * caller. */
+static int pm_insert_page(struct page_map *pm, unsigned long index,
+                          struct page *page)
+{
+       int ret;
+       void **tree_slot;
+       void *slot_val = 0;
+
+       page->pg_mapping = pm;  /* debugging */
+       page->pg_index = index;
+       /* no one should be looking at the tree slot til we stop write locking.
+        * the only other one who looks is removal, who requires a PM write
+        * lock. */
+       page->pg_tree_slot = (void*)0xdeadbeef; /* poison */
+       slot_val = pm_slot_inc_refcnt(slot_val);
+       /* passing the page ref from the caller to the slot */
+       slot_val = pm_slot_set_page(slot_val, page);
+       qlock(&pm->pm_qlock);
+       ret = radix_insert(&pm->pm_tree, index, slot_val, &tree_slot);
+       if (ret) {
+               qunlock(&pm->pm_qlock);
+               return ret;
+       }
+       page->pg_tree_slot = tree_slot;
+       pm->pm_num_pages++;
+       qunlock(&pm->pm_qlock);
        return 0;
 }
 
+/* Decrefs the PM slot ref (usage of a PM page).  The PM's page ref remains. */
+void pm_put_page(struct page *page)
+{
+       void **tree_slot = page->pg_tree_slot;
+
+       assert(tree_slot);
+       assert(pm_slot_get_page(*tree_slot) == page);
+       assert(pm_slot_check_refcnt(*tree_slot) > 0);
+       /* decref, don't care about CASing */
+       atomic_add((atomic_t*)tree_slot, -(1UL << PM_REFCNT_SHIFT));
+}
+
 /* Makes sure the index'th page of the mapped object is loaded in the page cache
- * and returns its location via **pp.  Note this will give you a refcnt'd
- * reference to the page.  This may block! TODO: (BLK) */
+ * and returns its location via **pp.
+ *
+ * You'll get a pm-slot refcnt back, which you need to put when you're done. */
 int pm_load_page(struct page_map *pm, unsigned long index, struct page **pp)
 {
        struct page *page;
        int error;
-       bool page_was_mapped = TRUE;
 
        page = pm_find_page(pm, index);
        while (!page) {
-               /* kpage_alloc, since we want the page to persist after the proc
-                * dies (can be used by others, until the inode shuts down). */
                if (kpage_alloc(&page))
                        return -ENOMEM;
-               /* might want to initialize other things, perhaps in page_alloc() */
-               page->pg_flags = 0;
+               /* important that UP_TO_DATE is not set.  once we put it in the
+                * PM, others can find it, and we still need to fill it. */
+               atomic_set(&page->pg_flags, PG_LOCKED | PG_PAGEMAP);
+               /* The sem needs to be initted before anyone can try to lock it,
+                * meaning before it is in the page cache.  We also want it
+                * locked preemptively, by setting signals = 0. */
+               sem_init(&page->pg_sem, 0);
                error = pm_insert_page(pm, index, page);
                switch (error) {
-                       case 0:
-                               page_was_mapped = FALSE;
-                               break;
-                       case -EEXIST:
-                               /* the page was mapped already (benign race), just get rid of
-                                * our page and try again (the only case that uses the while) */
-                               page_decref(page);
-                               page = pm_find_page(pm, index);
-                               break;
-                       default:
-                               /* something is wrong, bail out! */
-                               page_decref(page);
-                               return error;
+               case 0:
+                       goto load_locked_page;
+                       break;
+               case -EEXIST:
+                       /* the page was mapped already (benign race), just get
+                        * rid of our page and try again (the only case that
+                        * uses the while) */
+                       atomic_set(&page->pg_flags, 0);
+                       page_decref(page);
+                       page = pm_find_page(pm, index);
+                       break;
+               default:
+                       atomic_set(&page->pg_flags, 0);
+                       page_decref(page);
+                       return error;
                }
        }
-       assert(page && kref_refcnt(&page->pg_kref));
-       /* At this point, page is a refcnt'd page, and we return the reference.
-        * Also, there's an unlikely race where we're not in the page cache anymore,
-        * and this all is useless work. */
-       *pp = page;
-       /* if the page was in the map, we need to do some checks, and might have to
-        * read in the page later.  If the page was freshly inserted to the pm by
-        * us, we skip this since we are the one doing the readpage(). */
-       if (page_was_mapped) {
-               /* is it already here and up to date?  if so, we're done */
-               if (page->pg_flags & PG_UPTODATE)
-                       return 0;
-               /* if not, try to lock the page (could BLOCK) */
-               lock_page(page);
-               /* we got it, is our page still in the cache?  check the mapping.  if
-                * not, start over, perhaps with EAGAIN and outside support */
-               if (!page->pg_mapping)
-                       panic("Page is not in the mapping!  Haven't implemented this!");
-               /* double check, are we up to date?  if so, we're done */
-               if (page->pg_flags & PG_UPTODATE) {
-                       unlock_page(page);
-                       return 0;
-               }
+       assert(page);
+       assert(pm_slot_check_refcnt(*page->pg_tree_slot));
+       assert(pm_slot_get_page(*page->pg_tree_slot) == page);
+       if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
+               *pp = page;
+               printd("pm %p FOUND page %p, addr %p, idx %d\n", pm, page,
+                      page2kva(page), index);
+               return 0;
+       }
+       lock_page(page);
+       /* double-check.  if we we blocked on lock_page, it was probably for
+        * someone else loading.  plus, we can't load a page more than once (it
+        * could clobber newer writes) */
+       if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
+               unlock_page(page);
+               *pp = page;
+               return 0;
        }
-       /* if we're here, the page is locked by us, and it needs to be read in */
-       assert(page->pg_mapping == pm);
-       /* Readpage will block internally, returning when it is done */
+       /* fall through */
+load_locked_page:
        error = pm->pm_op->readpage(pm, page);
        assert(!error);
-       /* Unlock, since we're done with the page and it is up to date */
+       assert(atomic_read(&page->pg_flags) & PG_UPTODATE);
        unlock_page(page);
-       assert(page->pg_flags & PG_UPTODATE);
+       *pp = page;
+       printd("pm %p LOADS page %p, addr %p, idx %d\n", pm, page,
+              page2kva(page), index);
        return 0;
 }
+
+int pm_load_page_nowait(struct page_map *pm, unsigned long index,
+                        struct page **pp)
+{
+       struct page *page = pm_find_page(pm, index);
+
+       if (!page)
+               return -EAGAIN;
+       if (!(atomic_read(&page->pg_flags) & PG_UPTODATE)) {
+               /* TODO: could have a read_nowait pm_op */
+               pm_put_page(page);
+               return -EAGAIN;
+       }
+       *pp = page;
+       return 0;
+}
+
+static bool vmr_has_page_idx(struct vm_region *vmr, unsigned long pg_idx)
+{
+       unsigned long nr_pgs = (vmr->vm_end - vmr->vm_base) >> PGSHIFT;
+       unsigned long start_pg = vmr->vm_foff >> PGSHIFT;
+
+       if (!vmr->vm_ready)
+               return false;
+       return ((start_pg <= pg_idx) && (pg_idx < start_pg + nr_pgs));
+}
+
+/* Runs CB on every PTE in the VMR that corresponds to the file's pg_idx, for up
+ * to max_nr_pgs. */
+static void vmr_for_each(struct vm_region *vmr, unsigned long pg_idx,
+                         unsigned long max_nr_pgs, mem_walk_callback_t callback)
+{
+       uintptr_t start_va;
+       off64_t file_off = pg_idx << PGSHIFT;
+       size_t len = max_nr_pgs << PGSHIFT;
+
+       if (file_off < vmr->vm_foff) {
+               len -= vmr->vm_foff - file_off;
+               file_off = vmr->vm_foff;
+       }
+
+       start_va = vmr->vm_base + (file_off - vmr->vm_foff);
+       if (start_va < vmr->vm_base) {
+               warn("wraparound! %p %p %p %p", start_va, vmr->vm_base,
+                    vmr->vm_foff, pg_idx);
+               return;
+       }
+       if (start_va >= vmr->vm_end)
+               return;
+
+       len = MIN(len, vmr->vm_end - start_va);
+       if (!len)
+               return;
+       env_user_mem_walk(vmr->vm_proc, (void*)start_va, len, callback, vmr);
+}
+
+static bool pm_has_vmr_with_page(struct page_map *pm, unsigned long pg_idx)
+{
+       struct vm_region *vmr_i;
+
+       spin_lock(&pm->pm_lock);
+       TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
+               if (vmr_has_page_idx(vmr_i, pg_idx)) {
+                       spin_unlock(&pm->pm_lock);
+                       return true;
+               }
+       }
+       spin_unlock(&pm->pm_lock);
+       return false;
+}
+
+static bool __remove_or_zero_cb(void **slot, unsigned long tree_idx, void *arg)
+{
+       struct page_map *pm = arg;
+       struct page *page;
+       void *old_slot_val, *slot_val;
+
+       old_slot_val = ACCESS_ONCE(*slot);
+       slot_val = old_slot_val;
+       page = pm_slot_get_page(slot_val);
+       /* We shouldn't have an item in the tree without a page, unless there's
+        * another removal.  Currently, this CB is called with a qlock. */
+       assert(page);
+       /* Don't even bother with VMRs that might have faulted in the page */
+       if (pm_has_vmr_with_page(pm, tree_idx)) {
+               memset(page2kva(page), 0, PGSIZE);
+               return false;
+       }
+       /* syncing with lookups, writebacks, etc - anyone who gets a ref on a PM
+        * leaf/page (e.g. pm_load_page / pm_find_page. */
+       slot_val = pm_slot_set_page(slot_val, NULL);
+       if (pm_slot_check_refcnt(slot_val) ||
+               !atomic_cas_ptr(slot, old_slot_val, slot_val)) {
+               memset(page2kva(page), 0, PGSIZE);
+               return false;
+       }
+       /* We yanked the page out.  The radix tree still has an item until we
+        * return true, but this is fine.  Future lock-free lookups will now
+        * fail (since the page is 0), and insertions will block on the write
+        * lock. */
+       atomic_set(&page->pg_flags, 0); /* cause/catch bugs */
+       page_decref(page);
+       return true;
+}
+
+void pm_remove_or_zero_pages(struct page_map *pm, unsigned long start_idx,
+                             unsigned long nr_pgs)
+{
+       unsigned long end_idx = start_idx + nr_pgs;
+
+       assert(end_idx > start_idx);
+       qlock(&pm->pm_qlock);
+       radix_for_each_slot_in_range(&pm->pm_tree, start_idx, end_idx,
+                                    __remove_or_zero_cb, pm);
+       qunlock(&pm->pm_qlock);
+}
+
+static int __pm_mark_and_clear_dirty(struct proc *p, pte_t pte, void *va,
+                                     void *arg)
+{
+       struct page *page = pa2page(pte_get_paddr(pte));
+       struct vm_region *vmr = arg;
+
+       if (!pte_is_present(pte) || !pte_is_dirty(pte))
+               return 0;
+       if (!(atomic_read(&page->pg_flags) & PG_DIRTY))
+               atomic_or(&page->pg_flags, PG_DIRTY);
+       pte_clear_dirty(pte);
+       vmr->vm_shootdown_needed = true;
+       return 0;
+}
+
+/* Dirty PTE bits will get marked to the struct page itself, and the PTEs will
+ * have the dirty bit cleared.  VMRs that need a shootdown are marked.  Note
+ * this only marks PTEs and VMRs if they were the one to do some of the
+ * dirtying. */
+static void mark_and_clear_dirty_ptes(struct page_map *pm)
+{
+       struct vm_region *vmr_i;
+       pte_t pte;
+
+       spin_lock(&pm->pm_lock);
+       TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
+               if (!(vmr_i->vm_prot & PROT_WRITE))
+                       continue;
+               /* Only care about shared mappings, not private.  Private
+                * mappings have a reference to the file, but the pages are not
+                * in the page cache - they hang directly off the PTEs (for
+                * now). */
+               if (!(vmr_i->vm_flags & MAP_SHARED))
+                       continue;
+               spin_lock(&vmr_i->vm_proc->pte_lock);
+               vmr_for_each(vmr_i, 0, ULONG_MAX, __pm_mark_and_clear_dirty);
+               spin_unlock(&vmr_i->vm_proc->pte_lock);
+       }
+       spin_unlock(&pm->pm_lock);
+}
+
+static void shootdown_vmrs(struct page_map *pm)
+{
+       struct vm_region *vmr_i;
+
+       /* The VMR flag shootdown_needed is owned by the PM.  Each VMR is hooked
+        * to at most one file, so there's no issue there.  We might have a proc
+        * that has multiple non-private VMRs in the same file, but it shouldn't
+        * be a big enough issue to worry about. */
+       spin_lock(&pm->pm_lock);
+       TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
+               if (vmr_i->vm_shootdown_needed) {
+                       vmr_i->vm_shootdown_needed = false;
+                       proc_tlbshootdown(vmr_i->vm_proc, 0, 0);
+               }
+       }
+       spin_unlock(&pm->pm_lock);
+}
+
+/* Send any queued WBs that haven't been sent yet. */
+static void flush_queued_writebacks(struct page_map *pm)
+{
+       /* TODO (WB) */
+}
+
+/* Batches up pages to be written back, preferably as one big op.  If we have a
+ * bunch outstanding, we'll send them. */
+static void queue_writeback(struct page_map *pm, struct page *page)
+{
+       /* TODO (WB): add a bulk op (instead of only writepage()), collect
+        * extents, and send them to the device.  Probably do something similar
+        * for reads. */
+       pm->pm_op->writepage(pm, page);
+}
+
+static bool __writeback_cb(void **slot, unsigned long tree_idx, void *arg)
+{
+       struct page_map *pm = arg;
+       struct page *page = pm_slot_get_page(*slot);
+
+       /* We're qlocked, so all items should have pages. */
+       assert(page);
+       if (atomic_read(&page->pg_flags) & PG_DIRTY) {
+               atomic_and(&page->pg_flags, ~PG_DIRTY);
+               queue_writeback(pm, page);
+       }
+       return false;
+}
+
+/* Every dirty page gets written back, regardless of whether it's in a VMR or
+ * not.  All the dirty bits get cleared too, before writing back. */
+void pm_writeback_pages(struct page_map *pm)
+{
+       qlock(&pm->pm_qlock);
+       mark_and_clear_dirty_ptes(pm);
+       shootdown_vmrs(pm);
+       radix_for_each_slot(&pm->pm_tree, __writeback_cb, pm);
+       flush_queued_writebacks(pm);
+       qunlock(&pm->pm_qlock);
+}
+
+static bool __flush_unused_cb(void **slot, unsigned long tree_idx, void *arg)
+{
+       struct page_map *pm = arg;
+       struct page *page = pm_slot_get_page(*slot);
+       void *old_slot_val, *slot_val;
+
+       /* We're qlocked, so all items should have pages. */
+       assert(page);
+       old_slot_val = ACCESS_ONCE(*slot);
+       slot_val = old_slot_val;
+       /* Under any contention, we just skip it */
+       if (pm_slot_check_refcnt(slot_val))
+               return false;
+       assert(pm_slot_get_page(slot_val) == page);
+       slot_val = pm_slot_set_page(slot_val, NULL);
+       if (!atomic_cas_ptr(slot, old_slot_val, slot_val))
+               return false;
+       /* At this point, we yanked the page.  any concurrent wait-free users
+        * that want to get this page will fail (pm_find_page /
+        * pm_load_page_nowait).  They will block on the qlock that we hold when
+        * they try to insert a page (as part of pm_load_page, for both reading
+        * or writing).  We can still bail out and everything will be fine, so
+        * long as we put the page back.
+        *
+        * We can't tell from looking at the page if it was actually faulted
+        * into the VMR; we just know it was possible.  (currently).  Also, we
+        * need to do this check after removing the page from the PM slot, since
+        * the mm faulting code (hpf) will attempt a non-blocking PM lookup. */
+       if (pm_has_vmr_with_page(pm, tree_idx)) {
+               slot_val = pm_slot_set_page(slot_val, page);
+               /* No one should be writing to it.  We hold the qlock, and any
+                * readers should not have increffed while the page was NULL. */
+               WRITE_ONCE(*slot, slot_val);
+               return false;
+       }
+       /* Need to check PG_DIRTY *after* checking VMRs.  o/w we could check,
+        * PAUSE, see no VMRs.  But in the meantime, we had a VMR that munmapped
+        * and wrote-back the dirty flag. */
+       if (atomic_read(&page->pg_flags) & PG_DIRTY) {
+               /* If we want to batch these, we'll also have to batch the
+                * freeing, which isn't a big deal.  Just do it before freeing
+                * and before unlocking the PM; we don't want someone to load
+                * the page from the backing store and get an old value. */
+               pm->pm_op->writepage(pm, page);
+       }
+       /* All clear - the page is unused and (now) clean. */
+       atomic_set(&page->pg_flags, 0); /* catch bugs */
+       page_decref(page);
+       return true;
+}
+
+/* Unused pages (not currently involved in a read, write, or mmap) are pruned.
+ * Dirty pages are written back first.
+ *
+ * We ignore anything mapped in a VMR.  Not bothering with unmapping or
+ * shootdowns or anything.  At least for now. */
+void pm_free_unused_pages(struct page_map *pm)
+{
+       qlock(&pm->pm_qlock);
+       radix_for_each_slot(&pm->pm_tree, __flush_unused_cb, pm);
+       qunlock(&pm->pm_qlock);
+}
+
+static bool __destroy_cb(void **slot, unsigned long tree_idx, void *arg)
+{
+       struct page *page = pm_slot_get_page(*slot);
+
+       /* Should be no users or need to sync */
+       assert(pm_slot_check_refcnt(*slot) == 0);
+       atomic_set(&page->pg_flags, 0); /* catch bugs */
+       page_decref(page);
+       return true;
+}
+
+void pm_destroy(struct page_map *pm)
+{
+       radix_for_each_slot(&pm->pm_tree, __destroy_cb, pm);
+       radix_tree_destroy(&pm->pm_tree);
+}
+
+void print_page_map_info(struct page_map *pm)
+{
+       struct vm_region *vmr_i;
+       printk("Page Map %p\n", pm);
+       printk("\tNum pages: %lu\n", pm->pm_num_pages);
+       spin_lock(&pm->pm_lock);
+       TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
+               printk("\tVMR proc %d: (%p - %p): 0x%08x, 0x%08x, %p, %p\n",
+                      vmr_i->vm_proc->pid, vmr_i->vm_base, vmr_i->vm_end,
+                      vmr_i->vm_prot, vmr_i->vm_flags,
+                      foc_pointer(vmr_i->__vm_foc), vmr_i->vm_foff);
+       }
+       spin_unlock(&pm->pm_lock);
+}
+
+void pm_page_asserter(struct page *page, char *str)
+{
+       void **tree_slot = page->pg_tree_slot;
+
+       if (!page_is_pagemap(page))
+               return;
+       assert(tree_slot);
+       assert(pm_slot_get_page(*tree_slot) == page);
+       assert(pm_slot_check_refcnt(*tree_slot) > 0);
+}