Replace the SLB backing store splay tree used on 64-bit PowerPC AIM

hardware with a lockless sparse tree design. This marginally improves
the performance of PMAP and allows copyin()/copyout() to run without
acquiring locks when used on wired mappings.

Submitted by:	mdf

1 files changed, 310 insertions, 121 deletions

diff --git a/sys/powerpc/aim/slb.c b/sys/powerpc/aim/slb.c
index 7ea4593..3d3aecd 100644
--- a/sys/powerpc/aim/slb.c
+++ b/sys/powerpc/aim/slb.c
@@ -32,7 +32,6 @@
 #include <sys/mutex.h>
 #include <sys/proc.h>
 #include <sys/systm.h>
-#include <sys/tree.h>
 
 #include <vm/vm.h>
 #include <vm/pmap.h>
@@ -45,65 +44,212 @@
 
 uintptr_t moea64_get_unique_vsid(void);
 void moea64_release_vsid(uint64_t vsid);
+static void slb_zone_init(void *);
+
+uma_zone_t slbt_zone;
+uma_zone_t slb_cache_zone;
+
+SYSINIT(slb_zone_init, SI_SUB_KMEM, SI_ORDER_ANY, slb_zone_init, NULL);
 
-struct slbcontainer {
-	struct slb slb;
-	SPLAY_ENTRY(slbcontainer) slb_node;
+struct slbtnode {
+	uint16_t	ua_alloc;
+	uint8_t		ua_level;
+	/* Only 36 bits needed for full 64-bit address space. */
+	uint64_t	ua_base;
+	union {
+		struct slbtnode	*ua_child[16];
+		struct slb	slb_entries[16];
+	} u;
 };
 
-static int slb_compare(struct slbcontainer *a, struct slbcontainer *b);
-static void slb_zone_init(void *);
+/*
+ * For a full 64-bit address space, there are 36 bits in play in an
+ * esid, so 8 levels, with the leaf being at level 0.
+ *
+ * |3333|3322|2222|2222|1111|1111|11  |    |    |  esid
+ * |5432|1098|7654|3210|9876|5432|1098|7654|3210|  bits
+ * +----+----+----+----+----+----+----+----+----+--------
+ * | 8  | 7  | 6  | 5  | 4  | 3  | 2  | 1  | 0  | level
+ */
+#define UAD_ROOT_LEVEL  8
+#define UAD_LEAF_LEVEL  0
 
-SPLAY_PROTOTYPE(slb_tree, slbcontainer, slb_node, slb_compare);
-SPLAY_GENERATE(slb_tree, slbcontainer, slb_node, slb_compare);
+static inline int
+esid2idx(uint64_t esid, int level)
+{
+	int shift;
 
-uma_zone_t slb_zone;
-uma_zone_t slb_cache_zone;
+	shift = level * 4;
+	return ((esid >> shift) & 0xF);
+}
+
+/*
+ * The ua_base field should have 0 bits after the first 4*(level+1)
+ * bits; i.e. only
+ */
+#define uad_baseok(ua)                          \
+	(esid2base(ua->ua_base, ua->ua_level) == ua->ua_base)
 
-SYSINIT(slb_zone_init, SI_SUB_KMEM, SI_ORDER_ANY, slb_zone_init, NULL);
 
-int
-va_to_slb_entry(pmap_t pm, vm_offset_t va, struct slb *slb)
+static inline uint64_t
+esid2base(uint64_t esid, int level)
 {
-	struct slbcontainer cont, *found;
-	uint64_t esid;
+	uint64_t mask;
+	int shift;
 
-	esid = (uintptr_t)va >> ADDR_SR_SHFT;
-	slb->slbe = (esid << SLBE_ESID_SHIFT) | SLBE_VALID;
-
-	if (pm == kernel_pmap) {
-		/* Set kernel VSID to deterministic value */
-		slb->slbv = va_to_vsid(kernel_pmap, va) << SLBV_VSID_SHIFT;
-
-		/* Figure out if this is a large-page mapping */
-		if (hw_direct_map && va < VM_MIN_KERNEL_ADDRESS) {
-			/*
-			 * XXX: If we have set up a direct map, assumes
-			 * all physical memory is mapped with large pages.
-			 */
-			if (mem_valid(va, 0) == 0)
-				slb->slbv |= SLBV_L;
-		}
-			
-		return (0);
-	}
+	shift = (level + 1) * 4;
+	mask = ~((1ULL << shift) - 1);
+	return (esid & mask);
+}
 
-	PMAP_LOCK_ASSERT(pm, MA_OWNED);
+/*
+ * Allocate a new leaf node for the specified esid/vmhandle from the
+ * parent node.
+ */
+static struct slb *
+make_new_leaf(uint64_t esid, uint64_t slbv, struct slbtnode *parent)
+{
+	struct slbtnode *child;
+	struct slb *retval;
+	int idx;
+
+	idx = esid2idx(esid, parent->ua_level);
+	KASSERT(parent->u.ua_child[idx] == NULL, ("Child already exists!"));
 
-	cont.slb.slbe = slb->slbe;
-	found = SPLAY_FIND(slb_tree, &pm->pm_slbtree, &cont);
+	/* unlock and M_WAITOK and loop? */
+	child = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
+	KASSERT(child != NULL, ("unhandled NULL case"));
 
-	if (found == NULL)
-		return (-1);
+	child->ua_level = UAD_LEAF_LEVEL;
+	child->ua_base = esid2base(esid, child->ua_level);
+	idx = esid2idx(esid, child->ua_level);
+	child->u.slb_entries[idx].slbv = slbv;
+	child->u.slb_entries[idx].slbe = (esid << SLBE_ESID_SHIFT) | SLBE_VALID;
+	setbit(&child->ua_alloc, idx);
 
-	slb->slbv = found->slb.slbv;
-	return (0);
+	retval = &child->u.slb_entries[idx];
+
+	/*
+	 * The above stores must be visible before the next one, so
+	 * that a lockless searcher always sees a valid path through
+	 * the tree.
+	 */
+	powerpc_sync();
+
+	idx = esid2idx(esid, parent->ua_level);
+	parent->u.ua_child[idx] = child;
+	setbit(&parent->ua_alloc, idx);
+
+	return (retval);
+}
+
+/*
+ * Allocate a new intermediate node to fit between the parent and
+ * esid.
+ */
+static struct slbtnode*
+make_intermediate(uint64_t esid, struct slbtnode *parent)
+{
+	struct slbtnode *child, *inter;
+	int idx, level;
+
+	idx = esid2idx(esid, parent->ua_level);
+	child = parent->u.ua_child[idx];
+	KASSERT(esid2base(esid, child->ua_level) != child->ua_base,
+	    ("No need for an intermediate node?"));
+
+	/*
+	 * Find the level where the existing child and our new esid
+	 * meet.  It must be lower than parent->ua_level or we would
+	 * have chosen a different index in parent.
+	 */
+	level = child->ua_level + 1;
+	while (esid2base(esid, level) !=
+	    esid2base(child->ua_base, level))
+		level++;
+	KASSERT(level < parent->ua_level,
+	    ("Found splitting level %d for %09jx and %09jx, "
+	    "but it's the same as %p's",
+	    level, esid, child->ua_base, parent));
+
+	/* unlock and M_WAITOK and loop? */
+	inter = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
+	KASSERT(inter != NULL, ("unhandled NULL case"));
+
+	/* Set up intermediate node to point to child ... */
+	inter->ua_level = level;
+	inter->ua_base = esid2base(esid, inter->ua_level);
+	idx = esid2idx(child->ua_base, inter->ua_level);
+	inter->u.ua_child[idx] = child;
+	setbit(&inter->ua_alloc, idx);
+	powerpc_sync();
+
+	/* Set up parent to point to intermediate node ... */
+	idx = esid2idx(inter->ua_base, parent->ua_level);
+	parent->u.ua_child[idx] = inter;
+	setbit(&parent->ua_alloc, idx);
+
+	return (inter);
+}
+
+uint64_t
+kernel_va_to_slbv(vm_offset_t va)
+{
+	uint64_t esid, slbv;
+
+	esid = (uintptr_t)va >> ADDR_SR_SHFT;
+
+	/* Set kernel VSID to deterministic value */
+	slbv = va_to_vsid(kernel_pmap, va) << SLBV_VSID_SHIFT;
+
+	/* Figure out if this is a large-page mapping */
+	if (hw_direct_map && va < VM_MIN_KERNEL_ADDRESS) {
+		/*
+		 * XXX: If we have set up a direct map, assumes
+		 * all physical memory is mapped with large pages.
+		 */
+		if (mem_valid(va, 0) == 0)
+			slbv |= SLBV_L;
+	}
+		
+	return (slbv);
+}
+
+struct slb *
+user_va_to_slb_entry(pmap_t pm, vm_offset_t va)
+{
+	uint64_t esid = va >> ADDR_SR_SHFT;
+	struct slbtnode *ua;
+	int idx;
+
+	ua = pm->pm_slb_tree_root;
+
+	for (;;) {
+		KASSERT(uad_baseok(ua), ("uad base %016jx level %d bad!",
+		    ua->ua_base, ua->ua_level));
+		idx = esid2idx(esid, ua->ua_level);
+
+		/*
+		 * This code is specific to ppc64 where a load is
+		 * atomic, so no need for atomic_load macro.
+		 */
+		if (ua->ua_level == UAD_LEAF_LEVEL)
+			return ((ua->u.slb_entries[idx].slbe & SLBE_VALID) ?
+			    &ua->u.slb_entries[idx] : NULL);
+
+		ua = ua->u.ua_child[idx];
+		if (ua == NULL ||
+		    esid2base(esid, ua->ua_level) != ua->ua_base)
+			return (NULL);
+	}
+
+	return (NULL);
 }
 
 uint64_t
 va_to_vsid(pmap_t pm, vm_offset_t va)
 {
-	struct slb entry;
+	struct slb *entry;
 
 	/* Shortcut kernel case */
 	if (pm == kernel_pmap)
@@ -114,56 +260,149 @@ va_to_vsid(pmap_t pm, vm_offset_t va)
 	 * to the PMAP's segment table.
 	 */
 
-	if (va_to_slb_entry(pm, va, &entry) != 0)
+	entry = user_va_to_slb_entry(pm, va);
+
+	if (entry == NULL)
 		return (allocate_vsid(pm, (uintptr_t)va >> ADDR_SR_SHFT, 0));
 
-	return ((entry.slbv & SLBV_VSID_MASK) >> SLBV_VSID_SHIFT);
+	return ((entry->slbv & SLBV_VSID_MASK) >> SLBV_VSID_SHIFT);
 }
 
 uint64_t
 allocate_vsid(pmap_t pm, uint64_t esid, int large)
 {
-	uint64_t vsid;
-	struct slbcontainer *slb_entry, kern_entry;
-	struct slb *prespill;
+	uint64_t vsid, slbv;
+	struct slbtnode *ua, *next, *inter;
+	struct slb *slb;
+	int idx;
 
-	prespill = NULL;
+	KASSERT(pm != kernel_pmap, ("Attempting to allocate a kernel VSID"));
 
-	if (pm == kernel_pmap) {
-		vsid = va_to_vsid(pm, esid << ADDR_SR_SHFT);
-		slb_entry = &kern_entry;
-		prespill = PCPU_GET(slb);
-	} else {
-		vsid = moea64_get_unique_vsid();
-		slb_entry = uma_zalloc(slb_zone, M_NOWAIT);
-
-		if (slb_entry == NULL)
-			panic("Could not allocate SLB mapping!");
-
-		prespill = pm->pm_slb;
-	}
-
-	slb_entry->slb.slbe = (esid << SLBE_ESID_SHIFT) | SLBE_VALID;
-	slb_entry->slb.slbv = vsid << SLBV_VSID_SHIFT;
+	PMAP_LOCK_ASSERT(pm, MA_OWNED);
+	vsid = moea64_get_unique_vsid();
 
+	slbv = vsid << SLBV_VSID_SHIFT;
 	if (large)
-		slb_entry->slb.slbv |= SLBV_L;
+		slbv |= SLBV_L;
+
+	ua = pm->pm_slb_tree_root;
+
+	/* Descend to the correct leaf or NULL pointer. */
+	for (;;) {
+		KASSERT(uad_baseok(ua),
+		   ("uad base %09jx level %d bad!", ua->ua_base, ua->ua_level));
+		idx = esid2idx(esid, ua->ua_level);
+
+		if (ua->ua_level == UAD_LEAF_LEVEL) {
+			ua->u.slb_entries[idx].slbv = slbv;
+			eieio();
+			ua->u.slb_entries[idx].slbe = (esid << SLBE_ESID_SHIFT)
+			    | SLBE_VALID;
+			setbit(&ua->ua_alloc, idx);
+			slb = &ua->u.slb_entries[idx];
+			break;
+		}
 
-	if (pm != kernel_pmap) {
-		PMAP_LOCK_ASSERT(pm, MA_OWNED);
-		SPLAY_INSERT(slb_tree, &pm->pm_slbtree, slb_entry);
+		next = ua->u.ua_child[idx];
+		if (next == NULL) {
+			slb = make_new_leaf(esid, slbv, ua);
+			break;
+                }
+
+		/*
+		 * Check if the next item down has an okay ua_base.
+		 * If not, we need to allocate an intermediate node.
+		 */
+		if (esid2base(esid, next->ua_level) != next->ua_base) {
+			inter = make_intermediate(esid, ua);
+			slb = make_new_leaf(esid, slbv, inter);
+			break;
+		}
+
+		ua = next;
 	}
 
 	/*
 	 * Someone probably wants this soon, and it may be a wired
 	 * SLB mapping, so pre-spill this entry.
 	 */
-	if (prespill != NULL)
-		slb_insert(pm, prespill, &slb_entry->slb);
+	eieio();
+	slb_insert(pm, pm->pm_slb, slb);
 
 	return (vsid);
 }
 
+void
+free_vsid(pmap_t pm, uint64_t esid, int large)
+{
+	struct slbtnode *ua;
+	int idx;
+
+	PMAP_LOCK_ASSERT(pm, MA_OWNED);
+
+	ua = pm->pm_slb_tree_root;
+	/* Descend to the correct leaf. */
+	for (;;) {
+		KASSERT(uad_baseok(ua),
+		   ("uad base %09jx level %d bad!", ua->ua_base, ua->ua_level));
+		
+		idx = esid2idx(esid, ua->ua_level);
+		if (ua->ua_level == UAD_LEAF_LEVEL) {
+			ua->u.slb_entries[idx].slbv = 0;
+			eieio();
+			ua->u.slb_entries[idx].slbe = 0;
+			clrbit(&ua->ua_alloc, idx);
+			return;
+		}
+
+		ua = ua->u.ua_child[idx];
+		if (ua == NULL ||
+		    esid2base(esid, ua->ua_level) != ua->ua_base) {
+			/* Perhaps just return instead of assert? */
+			KASSERT(0,
+			    ("Asked to remove an entry that was never inserted!"));
+			return;
+		}
+	}
+}
+
+static void
+free_slb_tree_node(struct slbtnode *ua)
+{
+	int idx;
+
+	for (idx = 0; idx < 16; idx++) {
+		if (ua->ua_level != UAD_LEAF_LEVEL) {
+			if (ua->u.ua_child[idx] != NULL)
+				free_slb_tree_node(ua->u.ua_child[idx]);
+		} else {
+			if (ua->u.slb_entries[idx].slbv != 0)
+				moea64_release_vsid(ua->u.slb_entries[idx].slbv
+				    >> SLBV_VSID_SHIFT);
+		}
+	}
+
+	uma_zfree(slbt_zone, ua);
+}
+
+void
+slb_free_tree(pmap_t pm)
+{
+
+	free_slb_tree_node(pm->pm_slb_tree_root);
+}
+
+struct slbtnode *
+slb_alloc_tree(void)
+{
+	struct slbtnode *root;
+
+	root = uma_zalloc(slbt_zone, M_NOWAIT | M_ZERO);
+	root->ua_level = UAD_ROOT_LEVEL;
+
+	return (root);
+}
+
 /* Lock entries mapping kernel text and stacks */
 
 #define SLB_SPILLABLE(slbe) \
@@ -222,62 +461,12 @@ slb_insert(pmap_t pm, struct slb *slbcache, struct slb *slb_entry)
 	critical_exit();
 }
 
-int
-vsid_to_esid(pmap_t pm, uint64_t vsid, uint64_t *esid)
-{
-	uint64_t slbv;
-	struct slbcontainer *entry;
-
-#ifdef INVARIANTS
-	if (pm == kernel_pmap)
-		panic("vsid_to_esid only works on user pmaps");
-
-	PMAP_LOCK_ASSERT(pm, MA_OWNED);
-#endif
-
-	slbv = vsid << SLBV_VSID_SHIFT;
-
-	SPLAY_FOREACH(entry, slb_tree, &pm->pm_slbtree) {
-		if (slbv == entry->slb.slbv) {
-			*esid = entry->slb.slbe >> SLBE_ESID_SHIFT;
-			return (0);
-		}
-	}
-
-	return (-1);
-}
-
-void
-free_vsids(pmap_t pm)
-{
-	struct slbcontainer *entry;
-
-	while (!SPLAY_EMPTY(&pm->pm_slbtree)) {
-		entry = SPLAY_MIN(slb_tree, &pm->pm_slbtree);
-
-		SPLAY_REMOVE(slb_tree, &pm->pm_slbtree, entry);
-
-		moea64_release_vsid(entry->slb.slbv >> SLBV_VSID_SHIFT);
-		uma_zfree(slb_zone, entry);
-	}
-}
-
-static int
-slb_compare(struct slbcontainer *a, struct slbcontainer *b)
-{
-	if (a->slb.slbe == b->slb.slbe)
-		return (0);
-	else if (a->slb.slbe < b->slb.slbe)
-		return (-1);
-	else
-		return (1);
-}
 
 static void
 slb_zone_init(void *dummy)
 {
 
-	slb_zone = uma_zcreate("SLB segment", sizeof(struct slbcontainer),
+	slbt_zone = uma_zcreate("SLB tree node", sizeof(struct slbtnode),
 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);
 	slb_cache_zone = uma_zcreate("SLB cache", 64*sizeof(struct slb),
 	    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);