MFamd64

  When a superpage promotion occurs, the page table page that the superpage
  mapping replaces is added to an ordered collection of page table pages.
  Rather than preserving the code that implements the splay tree of pages
  in the pmap for just this one purpose, use the new MI radix tree.  The
  extra overhead of using a radix tree for this purpose is small enough,
  about 4% added run-time to pmap_promote_pde(), that I don't see the point
  of preserving the splay tree code.

Sponsored by:	EMC / Isilon Storage Division

2 files changed, 16 insertions, 120 deletions

diff --git a/sys/i386/i386/pmap.c b/sys/i386/i386/pmap.c
index 8de2f6f..50cd325 100644
--- a/sys/i386/i386/pmap.c
+++ b/sys/i386/i386/pmap.c
@@ -133,6 +133,7 @@ __FBSDID("$FreeBSD$");
 #include <vm/vm_extern.h>
 #include <vm/vm_pageout.h>
 #include <vm/vm_pager.h>
+#include <vm/vm_radix.h>
 #include <vm/vm_reserv.h>
 #include <vm/uma.h>
 
@@ -330,7 +331,6 @@ static boolean_t pmap_try_insert_pv_entry(pmap_t pmap, vm_offset_t va,
 static void pmap_update_pde(pmap_t pmap, vm_offset_t va, pd_entry_t *pde,
     pd_entry_t newpde);
 static void pmap_update_pde_invalidate(vm_offset_t va, pd_entry_t newpde);
-static vm_page_t pmap_vmpage_splay(vm_pindex_t pindex, vm_page_t root);
 
 static vm_page_t pmap_allocpte(pmap_t pmap, vm_offset_t va, int flags);
 
@@ -1604,31 +1604,12 @@ pmap_add_delayed_free_list(vm_page_t m, vm_page_t *free, boolean_t set_PG_ZERO)
  * for mapping a distinct range of virtual addresses.  The pmap's collection is
  * ordered by this virtual address range.
  */
-static void
+static __inline void
 pmap_insert_pt_page(pmap_t pmap, vm_page_t mpte)
 {
-	vm_page_t root;
 
 	PMAP_LOCK_ASSERT(pmap, MA_OWNED);
-	root = pmap->pm_root;
-	if (root == NULL) {
-		mpte->md.pv_left = NULL;
-		mpte->md.pv_right = NULL;
-	} else {
-		root = pmap_vmpage_splay(mpte->pindex, root);
-		if (mpte->pindex < root->pindex) {
-			mpte->md.pv_left = root->md.pv_left;
-			mpte->md.pv_right = root;
-			root->md.pv_left = NULL;
-		} else if (mpte->pindex == root->pindex)
-			panic("pmap_insert_pt_page: pindex already inserted");
-		else {
-			mpte->md.pv_right = root->md.pv_right;
-			mpte->md.pv_left = root;
-			root->md.pv_right = NULL;
-		}
-	}
-	pmap->pm_root = mpte;
+	vm_radix_insert(&pmap->pm_root, mpte->pindex, mpte);
 }
 
 /*
@@ -1636,19 +1617,12 @@ pmap_insert_pt_page(pmap_t pmap, vm_page_t mpte)
  * specified pmap's collection of idle page table pages.  Returns NULL if there
  * is no page table page corresponding to the specified virtual address.
  */
-static vm_page_t
+static __inline vm_page_t
 pmap_lookup_pt_page(pmap_t pmap, vm_offset_t va)
 {
-	vm_page_t mpte;
-	vm_pindex_t pindex = va >> PDRSHIFT;
 
 	PMAP_LOCK_ASSERT(pmap, MA_OWNED);
-	if ((mpte = pmap->pm_root) != NULL && mpte->pindex != pindex) {
-		mpte = pmap_vmpage_splay(pindex, mpte);
-		if ((pmap->pm_root = mpte)->pindex != pindex)
-			mpte = NULL;
-	}
-	return (mpte);
+	return (vm_radix_lookup(&pmap->pm_root, va >> PDRSHIFT));
 }
 
 /*
@@ -1656,27 +1630,12 @@ pmap_lookup_pt_page(pmap_t pmap, vm_offset_t va)
  * of idle page table pages.  The specified page table page must be a member of
  * the pmap's collection.
  */
-static void
+static __inline void
 pmap_remove_pt_page(pmap_t pmap, vm_page_t mpte)
 {
-	vm_page_t root;
 
 	PMAP_LOCK_ASSERT(pmap, MA_OWNED);
-	if (mpte != pmap->pm_root)
-		pmap_vmpage_splay(mpte->pindex, pmap->pm_root);
-	if (mpte->md.pv_left == NULL)
-		root = mpte->md.pv_right;
-	else {
-		root = pmap_vmpage_splay(mpte->pindex, mpte->md.pv_left);
-		root->md.pv_right = mpte->md.pv_right;
-	}
-	pmap->pm_root = root;
-
-	/*
-	 * Reinitialize the pv_list which could be dirty now because of the
-	 * splay tree work.
-	 */
-	TAILQ_INIT(&mpte->md.pv_list);
+	vm_radix_remove(&pmap->pm_root, mpte->pindex);
 }
 
 /*
@@ -1730,61 +1689,6 @@ _pmap_unwire_ptp(pmap_t pmap, vm_page_t m, vm_page_t *free)
 }
 
 /*
- *     Implements Sleator and Tarjan's top-down splay algorithm.  Returns
- *     the vm_page containing the given pindex.  If, however, that
- *     pindex is not found in the pmap, returns a vm_page that is
- *     adjacent to the pindex, coming before or after it.
- */
-static vm_page_t
-pmap_vmpage_splay(vm_pindex_t pindex, vm_page_t root)
-{
-	struct vm_page dummy;
-	vm_page_t lefttreemax, righttreemin, y;
-
-	if (root == NULL)
-		return (root);
-	lefttreemax = righttreemin = &dummy;
-	for (;; root = y) {
-		if (pindex < root->pindex) {
-			if ((y = root->md.pv_left) == NULL)
-				break;
-			if (pindex < y->pindex) {
-				/* Rotate right. */
-				root->md.pv_left = y->md.pv_right;
-				y->md.pv_right = root;
-				root = y;
-				if ((y = root->md.pv_left) == NULL)
-					break;
-			}
-			/* Link into the new root's right tree. */
-			righttreemin->md.pv_left = root;
-			righttreemin = root;
-		} else if (pindex > root->pindex) {
-			if ((y = root->md.pv_right) == NULL)
-				break;
-			if (pindex > y->pindex) {
-				/* Rotate left. */
-				root->md.pv_right = y->md.pv_left;
-				y->md.pv_left = root;
-				root = y;
-				if ((y = root->md.pv_right) == NULL)
-					break;
-			}
-			/* Link into the new root's left tree. */
-			lefttreemax->md.pv_right = root;
-			lefttreemax = root;
-		} else
-			break;
-	}
-	/* Assemble the new root. */
-	lefttreemax->md.pv_right = root->md.pv_left;
-	righttreemin->md.pv_left = root->md.pv_right;
-	root->md.pv_left = dummy.md.pv_right;
-	root->md.pv_right = dummy.md.pv_left;
-	return (root);
-}
-
-/*
  * After removing a page table entry, this routine is used to
  * conditionally free the page, and manage the hold/wire counts.
  */
@@ -1818,7 +1722,7 @@ pmap_pinit0(pmap_t pmap)
 #ifdef PAE
 	pmap->pm_pdpt = (pdpt_entry_t *)(KERNBASE + (vm_offset_t)IdlePDPT);
 #endif
-	pmap->pm_root = NULL;
+	pmap->pm_root.rt_root = 0;
 	CPU_ZERO(&pmap->pm_active);
 	PCPU_SET(curpmap, pmap);
 	TAILQ_INIT(&pmap->pm_pvchunk);
@@ -1857,9 +1761,9 @@ pmap_pinit(pmap_t pmap)
 		KASSERT(pmap_kextract((vm_offset_t)pmap->pm_pdpt) < (4ULL<<30),
 		    ("pmap_pinit: pdpt above 4g"));
 #endif
-		pmap->pm_root = NULL;
+		pmap->pm_root.rt_root = 0;
 	}
-	KASSERT(pmap->pm_root == NULL,
+	KASSERT(vm_radix_is_empty(&pmap->pm_root),
 	    ("pmap_pinit: pmap has reserved page table page(s)"));
 
 	/*
@@ -2123,7 +2027,7 @@ pmap_release(pmap_t pmap)
 	KASSERT(pmap->pm_stats.resident_count == 0,
 	    ("pmap_release: pmap resident count %ld != 0",
 	    pmap->pm_stats.resident_count));
-	KASSERT(pmap->pm_root == NULL,
+	KASSERT(vm_radix_is_empty(&pmap->pm_root),
 	    ("pmap_release: pmap has reserved page table page(s)"));
 
 	pmap_lazyfix(pmap);
diff --git a/sys/i386/include/pmap.h b/sys/i386/include/pmap.h
index 9ba2752..8c20e1b 100644
--- a/sys/i386/include/pmap.h
+++ b/sys/i386/include/pmap.h
@@ -159,6 +159,8 @@
 #include <sys/_lock.h>
 #include <sys/_mutex.h>
 
+#include <vm/_vm_radix.h>
+
 #ifdef PAE
 
 typedef uint64_t pdpt_entry_t;
@@ -426,20 +428,10 @@ struct	pv_entry;
 struct	pv_chunk;
 
 struct md_page {
-	union {
-		TAILQ_HEAD(,pv_entry)	pvi_list;
-		struct {
-			vm_page_t	pii_left;
-			vm_page_t	pii_right;
-		} pvi_siters;
-	} pv_structs;
-	int				pat_mode;
+	TAILQ_HEAD(,pv_entry)	pv_list;
+	int			pat_mode;
 };
 
-#define	pv_list		pv_structs.pvi_list
-#define	pv_left		pv_structs.pvi_siters.pii_left
-#define	pv_right	pv_structs.pvi_siters.pii_right
-
 struct pmap {
 	struct mtx		pm_mtx;
 	pd_entry_t		*pm_pdir;	/* KVA of page directory */
@@ -451,7 +443,7 @@ struct pmap {
 	pdpt_entry_t		*pm_pdpt;	/* KVA of page director pointer
 						   table */
 #endif
-	vm_page_t		pm_root;	/* spare page table pages */
+	struct vm_radix		pm_root;	/* spare page table pages */
 };
 
 typedef struct pmap	*pmap_t;