Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -54,9 +54,6 @@
 #include <sys/kernel.h>
 #include <sys/libkern.h>
 #include <sys/pctrie.h>
-#include <sys/proc.h>	/* smr.h depends on struct thread. */
-#include <sys/smr.h>
-#include <sys/smr_types.h>
 
 #ifdef DDB
 #include <ddb/ddb.h>
@@ -74,9 +71,6 @@
 _Static_assert(sizeof(pn_popmap_t) <= sizeof(int),
     "pn_popmap_t too wide");
 
-struct pctrie_node;
-typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t;
-
 struct pctrie_node {
 	uint64_t	pn_owner;			/* Owner of record. */
 	pn_popmap_t	pn_popmap;			/* Valid children. */
@@ -108,63 +102,12 @@
 }
 
 /*
- * Check radix node.
+ * Get the root address, cast to proper type for load/store.
  */
-static __inline void
-pctrie_node_put(struct pctrie_node *node)
+static __inline smr_pctnode_t *
+pctrie_root(struct pctrie *ptree)
 {
-#ifdef INVARIANTS
-	int slot;
-
-	KASSERT(powerof2(node->pn_popmap),
-	    ("pctrie_node_put: node %p has too many children %04x", node,
-	    node->pn_popmap));
-	for (slot = 0; slot < PCTRIE_COUNT; slot++) {
-		if ((node->pn_popmap & (1 << slot)) != 0)
-			continue;
-		KASSERT(smr_unserialized_load(&node->pn_child[slot], true) ==
-		    PCTRIE_NULL,
-		    ("pctrie_node_put: node %p has a child", node));
-	}
-#endif
-}
-
-enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
-
-/*
- * Fetch a node pointer from a slot.
- */
-static __inline struct pctrie_node *
-pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
-{
-	switch (access) {
-	case PCTRIE_UNSERIALIZED:
-		return (smr_unserialized_load(p, true));
-	case PCTRIE_LOCKED:
-		return (smr_serialized_load(p, true));
-	case PCTRIE_SMR:
-		return (smr_entered_load(p, smr));
-	}
-	__assert_unreachable();
-}
-
-static __inline void
-pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access)
-{
-	switch (access) {
-	case PCTRIE_UNSERIALIZED:
-		smr_unserialized_store(p, v, true);
-		break;
-	case PCTRIE_LOCKED:
-		smr_serialized_store(p, v, true);
-		break;
-	case PCTRIE_SMR:
-		panic("%s: Not supported in SMR section.", __func__);
-		break;
-	default:
-		__assert_unreachable();
-		break;
-	}
+	return ((smr_pctnode_t *)&ptree->pt_root);
 }
 
 /*
@@ -173,17 +116,7 @@
 static __inline struct pctrie_node *
 pctrie_root_load(struct pctrie *ptree, smr_t smr, enum pctrie_access access)
 {
-	return (pctrie_node_load((smr_pctnode_t *)&ptree->pt_root, smr, access));
-}
-
-/*
- * Set the root node for a tree.
- */
-static __inline void
-pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node,
-    enum pctrie_access access)
-{
-	pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access);
+	return (pctrie_node_load(pctrie_root(ptree), smr, access));
 }
 
 /*
@@ -195,15 +128,6 @@
 	return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
 }
 
-/*
- * Returns val with leaf bit set.
- */
-static __inline void *
-pctrie_toleaf(uint64_t *val)
-{
-	return ((void *)((uintptr_t)val | PCTRIE_ISLEAF));
-}
-
 /*
  * Returns the associated val extracted from node.
  */
@@ -227,12 +151,12 @@
  */
 static __inline void
 pctrie_addnode(struct pctrie_node *node, uint64_t index,
-    struct pctrie_node *child, enum pctrie_access access)
+    struct pctrie_node *child)
 {
 	int slot;
 
 	slot = pctrie_slot(node, index);
-	pctrie_node_store(&node->pn_child[slot], child, access);
+	pctrie_node_store(&node->pn_child[slot], child, PCTRIE_UNSERIALIZED);
 	node->pn_popmap ^= 1 << slot;
 	KASSERT((node->pn_popmap & (1 << slot)) != 0,
 	    ("%s: bad popmap slot %d in node %p", __func__, slot, node));
@@ -283,16 +207,18 @@
  * Note that mode is expected to be a compile-time constant, and this procedure
  * is expected to be inlined into callers with extraneous code optimized out.
  */
-static __always_inline void *
-pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t *val,
+static __always_inline smr_pctnode_t *
+pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t index,
     uint64_t **found_out, struct pctrie_node **neighbor_out,
     enum pctrie_insert_neighbor_mode mode)
 {
-	uint64_t index;
 	struct pctrie_node *node, *parent;
 	int slot;
 
-	index = *val;
+	if (neighbor_out != NULL)
+		*neighbor_out = NULL;
+	if (found_out != NULL)
+		*found_out = NULL;
 
 	/*
 	 * The owner of record for root is not really important because it
@@ -302,19 +228,13 @@
 	parent = NULL;
 	for (;;) {
 		if (pctrie_isleaf(node)) {
-			if (node == PCTRIE_NULL) {
-				if (parent == NULL)
-					pctrie_root_store(ptree,
-					    pctrie_toleaf(val), PCTRIE_LOCKED);
-				else
-					pctrie_addnode(parent, index,
-					    pctrie_toleaf(val), PCTRIE_LOCKED);
-				return (NULL);
-			}
-			if (*pctrie_toval(node) == index) {
-				*found_out = pctrie_toval(node);
-				return (NULL);
-			}
+			if (node != PCTRIE_NULL) {
+				if (*pctrie_toval(node) == index) {
+					*found_out = pctrie_toval(node);
+					return (NULL);
+				}
+			} else if (parent != NULL)
+				parent->pn_popmap ^= 1 << slot;
 			break;
 		}
 		if (pctrie_keybarr(node, index, &slot))
@@ -337,43 +257,40 @@
 	}
 
 	/*
-	 * The caller will split this node.  If we're tracking the next
-	 * neighbor, record the old node if the old entry is in the right
-	 * direction.
+	 * If we're tracking the next neighbor, and node is not NULL, record
+	 * this future sibling node if it is in the right direction.
 	 */
-	if (mode == PCTRIE_INSERT_NEIGHBOR_LT) {
+	if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_LT) {
 		if (*pctrie_toval(node) < index)
 			*neighbor_out = node;
-	} else if (mode == PCTRIE_INSERT_NEIGHBOR_GT) {
+	} else if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_GT) {
 		if (*pctrie_toval(node) > index)
 			*neighbor_out = node;
 	}
 
 	/*
-	 * 'node' must be replaced in the tree with a new branch node, with
-	 * children 'node' and 'val'. Return the place that points to 'node'
-	 * now, and will point to to the new branching node later.
+	 * 'node' must be replaced in the tree with an index leaf, or with a new
+	 * branch node, with children 'node' and an index leaf. Return the place
+	 * that points to 'node' now, and will point to to the new node later.
 	 */
-	return ((parent != NULL) ? &parent->pn_child[slot]:
-	    (smr_pctnode_t *)&ptree->pt_root);
+	return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]);
 }
 
 /*
  * Wrap pctrie_insert_lookup_compound to implement a strict insertion.  Panic
  * if the key already exists, and do not look for neighboring entries.
  */
-void *
-pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val)
+smr_pctnode_t *
+pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t index)
 {
-	void *parentp;
+	smr_pctnode_t *parentp;
 	uint64_t *found;
 
-	found = NULL;
-	parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
+	parentp = pctrie_insert_lookup_compound(ptree, index, &found, NULL,
 	    PCTRIE_INSERT_NEIGHBOR_NONE);
 	if (__predict_false(found != NULL))
 		panic("%s: key %jx is already present", __func__,
-		    (uintmax_t)*val);
+		    (uintmax_t)index);
 	return (parentp);
 }
 
@@ -381,12 +298,11 @@
  * Wrap pctrie_insert_lookup_compound to implement find-or-insert.  Do not look
  * for neighboring entries.
  */
-void *
-pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t *
+pctrie_insert_lookup(struct pctrie *ptree, uint64_t index,
     uint64_t **found_out)
 {
-	*found_out = NULL;
-	return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
+	return (pctrie_insert_lookup_compound(ptree, index, found_out, NULL,
 	    PCTRIE_INSERT_NEIGHBOR_NONE));
 }
 
@@ -395,13 +311,11 @@
  * greater entry.  Find a subtree that contains the next entry greater than the
  * newly-inserted or to-be-inserted entry.
  */
-void *
-pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t *
+pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t index,
     uint64_t **found_out, struct pctrie_node **neighbor_out)
 {
-	*found_out = NULL;
-	*neighbor_out = NULL;
-	return (pctrie_insert_lookup_compound(ptree, val, found_out,
+	return (pctrie_insert_lookup_compound(ptree, index, found_out,
 	    neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
 }
 
@@ -410,13 +324,11 @@
  * lesser entry.  Find a subtree that contains the next entry less than the
  * newly-inserted or to-be-inserted entry.
  */
-void *
-pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t *
+pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t index,
     uint64_t **found_out, struct pctrie_node **neighbor_out)
 {
-	*found_out = NULL;
-	*neighbor_out = NULL;
-	return (pctrie_insert_lookup_compound(ptree, val, found_out,
+	return (pctrie_insert_lookup_compound(ptree, index, found_out,
 	    neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
 }
 
@@ -424,7 +336,8 @@
  * Uses new node to insert key-value pair into the trie at given location.
  */
 void
-pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val)
+pctrie_insert_node(smr_pctnode_t *parentp, struct pctrie_node *parent,
+    uint64_t *val)
 {
 	struct pctrie_node *node;
 	uint64_t index, newind;
@@ -465,10 +378,8 @@
 
 
 	/* These writes are not yet visible due to ordering. */
-	pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
-	pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED);
-	/* Synchronize to make the above visible. */
-	pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
+	pctrie_addnode(parent, index, pctrie_toleaf(val));
+	pctrie_addnode(parent, newind, node);
 }
 
 /*
@@ -599,35 +510,35 @@
  * to indicate where a new node must be allocated to complete insertion.
  * Assumes access is externally synchronized by a lock.
  */
-void *
-pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t *val)
+smr_pctnode_t *
+pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t index)
 {
-	struct pctrie_node *node;
+	struct pctrie_node *node, *parent;
+	int slot;
 
-	it->index = *val;
-	node = _pctrie_iter_lookup_node(it, *val, NULL, PCTRIE_LOCKED);
-	if (node == PCTRIE_NULL) {
-		if (it->top == 0)
-			pctrie_root_store(it->ptree,
-			    pctrie_toleaf(val), PCTRIE_LOCKED);
-		else
-			pctrie_addnode(it->path[it->top - 1], it->index,
-			    pctrie_toleaf(val), PCTRIE_LOCKED);
-		return (NULL);
+	it->index = index;
+	node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
+	if (it->top == 0)
+		parent = NULL;
+	else {
+		parent = it->path[it->top -1];
+		slot = pctrie_slot(parent, index);
 	}
-	if (__predict_false(pctrie_match_value(node, it->index) != NULL))
-		panic("%s: key %jx is already present", __func__,
-		    (uintmax_t)it->index);
+	if (node != PCTRIE_NULL) {
+		if (__predict_false(
+		    pctrie_match_value(node, index) != NULL))
+			panic("%s: key %jx is already present", __func__,
+			      (uintmax_t)index);
+	} else if (parent != NULL)
+		parent->pn_popmap ^= 1 << slot;
 
 	/*
-	 * 'node' must be replaced in the tree with a new branch node, with
-	 * children 'node' and 'val'. Return the place that points to 'node'
-	 * now, and will point to to the new branching node later.
+	 * 'node' must be replaced in the tree with a leaf 'val', or with a new
+	 * branch node, with children 'node' and 'val'. Return the place that
+	 * points to 'node' now, and will point to to the new node later.
 	 */
-	if (it->top == 0)
-		return ((smr_pctnode_t *)&it->ptree->pt_root);
-	node = it->path[it->top - 1];
-	return (&node->pn_child[pctrie_slot(node, it->index)]);
+	return (parent == NULL ? pctrie_root(it->ptree) :
+	    &parent->pn_child[slot]);
 }
 
 /*
@@ -1033,46 +944,31 @@
 }
 #endif
 
-static void
+static smr_pctnode_t *
 pctrie_remove(struct pctrie *ptree, uint64_t index, struct pctrie_node *parent,
-    struct pctrie_node *node, struct pctrie_node **freenode)
+    struct pctrie_node *node, struct pctrie_node **child)
 {
-	struct pctrie_node *child;
 	int slot;
 
-	if (node == NULL) {
-		pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_LOCKED);
-		return;
-	}
+	*child = PCTRIE_NULL;
+	if (node == NULL)
+		return (pctrie_root(ptree));
 	slot = pctrie_slot(node, index);
 	KASSERT((node->pn_popmap & (1 << slot)) != 0,
 	    ("%s: bad popmap slot %d in node %p",
 	    __func__, slot, node));
 	node->pn_popmap ^= 1 << slot;
-	pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED);
 	if (!powerof2(node->pn_popmap))
-		return;
+		return (&node->pn_child[slot]);
+	pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
+	    PCTRIE_UNSERIALIZED);
 	KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
 	slot = ffs(node->pn_popmap) - 1;
-	child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
-	KASSERT(child != PCTRIE_NULL,
+	*child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
+	KASSERT(*child != PCTRIE_NULL,
 	    ("%s: bad popmap slot %d in node %p", __func__, slot, node));
-	if (parent == NULL)
-		pctrie_root_store(ptree, child, PCTRIE_LOCKED);
-	else {
-		slot = pctrie_slot(parent, index);
-		KASSERT(node ==
-		    pctrie_node_load(&parent->pn_child[slot], NULL,
-		    PCTRIE_LOCKED), ("%s: invalid child value", __func__));
-		pctrie_node_store(&parent->pn_child[slot], child,
-		    PCTRIE_LOCKED);
-	}
-	/*
-	 * The child is still valid and we can not zero the
-	 * pointer until all SMR references are gone.
-	 */
-	pctrie_node_put(node);
-	*freenode = node;
+	return ((parent == NULL) ? pctrie_root(ptree) :
+	    &parent->pn_child[pctrie_slot(parent, index)]);
 }
 
 /*
@@ -1081,25 +977,24 @@
  */
 uint64_t *
 pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
-    struct pctrie_node **freenode)
+    smr_pctnode_t **parentp, struct pctrie_node **child)
 {
-	struct pctrie_node *child, *node, *parent;
+	struct pctrie_node *next, *node, *parent;
 	uint64_t *m;
 	int slot;
 
 	DEBUG_POISON_POINTER(parent);
-	*freenode = node = NULL;
-	child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
-	while (!pctrie_isleaf(child)) {
+	node = NULL;
+	next = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
+	while (!pctrie_isleaf(next)) {
 		parent = node;
-		node = child;
+		node = next;
 		slot = pctrie_slot(node, index);
-		child = pctrie_node_load(&node->pn_child[slot], NULL,
+		next = pctrie_node_load(&node->pn_child[slot], NULL,
 		    PCTRIE_LOCKED);
 	}
-	m = pctrie_match_value(child, index);
-	if (m != NULL)
-		pctrie_remove(ptree, index, parent, node, freenode);
+	if ((m = pctrie_match_value(next, index)) != NULL)
+		*parentp = pctrie_remove(ptree, index, parent, node, child);
 	return (m);
 }
 
@@ -1108,29 +1003,30 @@
  * adjust the path if it's last member is to be freed.
  */
 uint64_t *
-pctrie_iter_remove(struct pctrie_iter *it, struct pctrie_node **freenode)
+pctrie_iter_remove(struct pctrie_iter *it,
+    smr_pctnode_t **parentp, struct pctrie_node **child)
 {
-	struct pctrie_node *child, *node, *parent;
+	struct pctrie_node *next, *node, *parent;
 	uint64_t *m;
 	int slot;
 
 	DEBUG_POISON_POINTER(parent);
-	*freenode = NULL;
 	if (it->top >= 1) {
 		parent = (it->top >= 2) ? it->path[it->top - 2] : NULL;
 		node = it->path[it->top - 1];
 		slot = pctrie_slot(node, it->index);
-		child = pctrie_node_load(&node->pn_child[slot], NULL,
+		next = pctrie_node_load(&node->pn_child[slot], NULL,
 		    PCTRIE_LOCKED);
 	} else {
 		node = NULL;
-		child = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED);
+		next = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED);
+	}
+	if ((m = pctrie_match_value(next, it->index)) != NULL) {
+		*parentp = pctrie_remove(it->ptree, it->index, parent, node,
+		    child);
+		if (*child != PCTRIE_NULL)
+			--it->top;
 	}
-	m = pctrie_match_value(child, it->index);
-	if (m != NULL)
-		pctrie_remove(it->ptree, it->index, parent, node, freenode);
-	if (*freenode != NULL)
-		--it->top;
 	return (m);
 }
 
@@ -1222,7 +1118,7 @@
 	struct pctrie_node *node;
 
 	node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED);
-	pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
+	pctrie_node_store(pctrie_root(ptree), PCTRIE_NULL, PCTRIE_UNSERIALIZED);
 	if (pctrie_isleaf(node)) {
 		if (callback != NULL && node != PCTRIE_NULL)
 			callback(pctrie_toptr(node, keyoff), arg);
@@ -1264,27 +1160,24 @@
  * Panics if there is not an old value in the trie at the new value's index.
  */
 uint64_t *
-pctrie_replace(struct pctrie *ptree, uint64_t *newval)
+pctrie_replace(struct pctrie *ptree, uint64_t *newval,
+    smr_pctnode_t **parentp, struct pctrie_node **child)
 {
-	struct pctrie_node *leaf, *parent, *node;
+	struct pctrie_node *parent, *node;
 	uint64_t *m;
 	uint64_t index;
 	int slot;
 
-	leaf = pctrie_toleaf(newval);
+	*child = pctrie_toleaf(newval);
 	index = *newval;
 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
 	parent = NULL;
 	for (;;) {
 		if (pctrie_isleaf(node)) {
 			if ((m = pctrie_toval(node)) != NULL && *m == index) {
-				if (parent == NULL)
-					pctrie_root_store(ptree,
-					    leaf, PCTRIE_LOCKED);
-				else
-					pctrie_node_store(
-					    &parent->pn_child[slot], leaf,
-					    PCTRIE_LOCKED);
+				*parentp = (parent == NULL) ?
+				    pctrie_root(ptree):
+				    &parent->pn_child[slot];
 				return (m);
 			}
 			break;
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -33,13 +33,78 @@
 
 #include <sys/_pctrie.h>
 #include <sys/_smr.h>
+#include <sys/proc.h>	/* smr.h depends on struct thread. */
+#include <sys/smr.h>
+#include <sys/smr_types.h>
+struct pctrie_node;
+typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t;
 
 #ifdef _KERNEL
 
 typedef void (*pctrie_cb_t)(void *ptr, void *arg);
 
+/*
+ * Each search path in the trie terminates at a leaf, which is a pointer to a
+ * value marked with a set 1-bit.  A leaf may be associated with a null pointer
+ * to indicate no value there.
+ */
+#define	PCTRIE_ISLEAF	0x1
+#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
+
+enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
+
+/*
+ * Fetch a node pointer from a slot.
+ */
+static __inline struct pctrie_node *
+pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access)
+{
+	switch (access) {
+	case PCTRIE_UNSERIALIZED:
+		return (smr_unserialized_load(p, true));
+	case PCTRIE_LOCKED:
+		return (smr_serialized_load(p, true));
+	case PCTRIE_SMR:
+		return (smr_entered_load(p, smr));
+	}
+	__assert_unreachable();
+}
+
+static __inline void
+pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access)
+{
+	switch (access) {
+	case PCTRIE_UNSERIALIZED:
+		smr_unserialized_store(p, v, true);
+		break;
+	case PCTRIE_LOCKED:
+		smr_serialized_store(p, v, true);
+		break;
+	case PCTRIE_SMR:
+		panic("%s: Not supported in SMR section.", __func__);
+		break;
+	default:
+		__assert_unreachable();
+		break;
+	}
+}
+
+/*
+ * Returns val with leaf bit set.
+ */
+static __inline void *
+pctrie_toleaf(uint64_t *val)
+{
+	return ((void *)((uintptr_t)val | PCTRIE_ISLEAF));
+}
+
+#define	PCTRIE_DEFINE(name, type, field, allocfn, freefn)		\
+    PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn,		\
+	PCTRIE_UNSERIALIZED)
+
 #define	PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr)	\
-    PCTRIE_DEFINE(name, type, field, allocfn, freefn)			\
+    PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn,		\
+	PCTRIE_LOCKED)							\
 									\
 static __inline struct type *						\
 name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key)	\
@@ -47,7 +112,7 @@
 									\
 	return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree,	\
 	    key, (smr)));						\
-}									\
+}
 
 #ifdef INVARIANTS
 void		pctrie_subtree_lookup_gt_assert(struct pctrie_node *node,
@@ -59,14 +124,14 @@
 #define	pctrie_subtree_lookup_lt_assert(node, key, ptree, res)
 #endif
 
-#define	PCTRIE_DEFINE(name, type, field, allocfn, freefn)		\
+#define	PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, access) \
 									\
 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t));	\
 /*									\
  * XXX This assert protects flag bits, it does not enforce natural	\
  * alignment.  32bit architectures do not naturally align 64bit fields.	\
  */									\
-CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
+CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t)-1)) == 0); \
 									\
 static __inline struct type *						\
 name##_PCTRIE_VAL2PTR(uint64_t *val)					\
@@ -86,71 +151,71 @@
 }									\
 									\
 static __inline __unused int						\
+name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, smr_pctnode_t *parentp,	\
+    uint64_t *val, uint64_t *found, struct type **found_out)		\
+{									\
+	struct pctrie_node *child, *node;				\
+									\
+	if (__predict_false(found != NULL)) {				\
+		*found_out = name##_PCTRIE_VAL2PTR(found);		\
+		return (EEXIST);					\
+	}								\
+	node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);	\
+	if (node != PCTRIE_NULL) {					\
+		child = allocfn(ptree);					\
+		if (__predict_false(child == NULL)) {			\
+			if (found_out != NULL)				\
+				*found_out = NULL;			\
+			return (ENOMEM);				\
+		}							\
+		pctrie_insert_node(parentp, child, val);		\
+	} else								\
+		child = pctrie_toleaf(val);				\
+	/* Synchronize to make changes visible. */			\
+	pctrie_node_store(parentp, child, access);			\
+	return (0);							\
+}									\
+									\
+static __inline __unused int						\
 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr)		\
 {									\
-	struct pctrie_node *parent;					\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 									\
-	parentp = pctrie_insert_lookup_strict(ptree, val);		\
-	if (parentp == NULL)						\
-		return (0);						\
-	parent = allocfn(ptree);					\
-	if (__predict_false(parent == NULL))				\
-		return (ENOMEM);					\
-	pctrie_insert_node(parentp, parent, val);			\
-	return (0);							\
+	parentp = pctrie_insert_lookup_strict(ptree, *val);		\
+	return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val,		\
+	    NULL, NULL));						\
 }									\
 									\
 static __inline __unused int						\
 name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr,	\
     struct type **found_out_opt)					\
 {									\
-	struct pctrie_node *parent;					\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
 									\
-	parentp = pctrie_insert_lookup(ptree, val, &found);		\
-	if (found != NULL) {						\
-		if (found_out_opt != NULL)				\
-			*found_out_opt = name##_PCTRIE_VAL2PTR(found);	\
-		return (EEXIST);					\
-	}								\
-	if (parentp == NULL)						\
-		return (0);						\
-	parent = allocfn(ptree);					\
-	if (__predict_false(parent == NULL))				\
-		return (ENOMEM);					\
-	pctrie_insert_node(parentp, parent, val);			\
-	return (0);							\
+	parentp = pctrie_insert_lookup(ptree, *val, &found);		\
+	return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val,		\
+	    found, found_out_opt));					\
 }									\
 									\
 static __inline __unused int						\
 name##_PCTRIE_INSERT_LOOKUP_GE(struct pctrie *ptree, struct type *ptr,	\
     struct type **found_out)						\
 {									\
-	struct pctrie_node *parent, *neighbor;				\
-	void *parentp;							\
+	struct pctrie_node *neighbor;					\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
+	int retval;							\
 									\
-	parentp = pctrie_insert_lookup_gt(ptree, val, &found,		\
+	parentp = pctrie_insert_lookup_gt(ptree, *val, &found,		\
 	    &neighbor);							\
-	if (__predict_false(found != NULL)) {				\
-		*found_out = name##_PCTRIE_VAL2PTR(found);		\
-		return (EEXIST);					\
-	}								\
-	if (parentp != NULL) {						\
-		parent = allocfn(ptree);				\
-		if (__predict_false(parent == NULL)) {			\
-			*found_out = NULL;				\
-			return (ENOMEM);				\
-		}							\
-		if (neighbor == parentp)				\
-			neighbor = parent;				\
-		pctrie_insert_node(parentp, parent, val);		\
-	}								\
+	retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val,		\
+	    found, found_out);						\
+	if (retval != 0)						\
+		return (retval);					\
 	found = pctrie_subtree_lookup_gt(neighbor, *val);		\
 	*found_out = name##_PCTRIE_VAL2PTR(found);			\
 	pctrie_subtree_lookup_gt_assert(neighbor, *val, ptree, found);	\
@@ -161,27 +226,18 @@
 name##_PCTRIE_INSERT_LOOKUP_LE(struct pctrie *ptree, struct type *ptr,	\
     struct type **found_out)						\
 {									\
-	struct pctrie_node *parent, *neighbor;				\
-	void *parentp;							\
+	struct pctrie_node *neighbor;					\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
+	int retval;							\
 									\
-	parentp = pctrie_insert_lookup_lt(ptree, val, &found,		\
+	parentp = pctrie_insert_lookup_lt(ptree, *val, &found,		\
 	    &neighbor);							\
-	if (__predict_false(found != NULL)) {				\
-		*found_out = name##_PCTRIE_VAL2PTR(found);		\
-		return (EEXIST);					\
-	}								\
-	if (parentp != NULL) {						\
-		parent = allocfn(ptree);				\
-		if (__predict_false(parent == NULL)) {			\
-			*found_out = NULL;				\
-			return (ENOMEM);				\
-		}							\
-		if (neighbor == parentp)				\
-			neighbor = parent;				\
-		pctrie_insert_node(parentp, parent, val);		\
-	}								\
+	retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val,		\
+	    found, found_out);						\
+	if (retval != 0)						\
+		return (retval);					\
 	found = pctrie_subtree_lookup_lt(neighbor, *val);		\
 	*found_out = name##_PCTRIE_VAL2PTR(found);			\
 	pctrie_subtree_lookup_lt_assert(neighbor, *val, ptree, found);	\
@@ -242,18 +298,22 @@
 static __inline __unused int						\
 name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr)	\
 {									\
-	struct pctrie_node *parent;					\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
+	struct pctrie_node *node;					\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
-									\
-	parentp = pctrie_iter_insert_lookup(it, val);			\
-	if (parentp == NULL)						\
-		return (0);						\
-	parent = allocfn(it->ptree);					\
-	if (__predict_false(parent == NULL))				\
-		return (ENOMEM);					\
-	pctrie_insert_node(parentp, parent, val);			\
-	it->path[it->top++] = parent;					\
+	int retval;							\
+									\
+	parentp = pctrie_iter_insert_lookup(it, *val);			\
+	node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);	\
+	retval = name##_PCTRIE_INSERT_BASE(it->ptree, parentp, val,	\
+	    NULL, NULL);						\
+	if (retval != 0)						\
+		return (retval);					\
+	if (node != PCTRIE_NULL) {					\
+		node = pctrie_node_load(parentp, NULL,			\
+		    PCTRIE_UNSERIALIZED);				\
+		it->path[it->top++] = node;				\
+	}								\
 	return (0);							\
 }									\
 									\
@@ -324,61 +384,87 @@
 }									\
 									\
 static __inline __unused void						\
-name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it)			\
+name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree,				\
+    smr_pctnode_t *parentp, struct pctrie_node *child)			\
 {									\
-	uint64_t *val;							\
 	struct pctrie_node *freenode;					\
 									\
-	val = pctrie_iter_remove(it, &freenode);			\
+	if (child != PCTRIE_NULL) {					\
+		freenode = pctrie_node_load(parentp, NULL,		\
+		    PCTRIE_UNSERIALIZED);				\
+	} else								\
+		freenode = NULL;					\
+	/* Synchronize to make changes visible. */			\
+	pctrie_node_store(parentp, child, access);			\
+	if (freenode != NULL)						\
+		freefn(ptree, freenode);				\
+}									\
+									\
+static __inline __unused void						\
+name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
+{									\
+	uint64_t *val;							\
+	smr_pctnode_t *parentp;						\
+	struct pctrie_node *child;					\
+									\
+	val = pctrie_remove_lookup(ptree, key, &parentp, &child);	\
 	if (val == NULL)						\
 		panic("%s: key not found", __func__);			\
-	if (freenode != NULL)						\
-		freefn(it->ptree, freenode);				\
+	else								\
+		name##_PCTRIE_REMOVE_BASE(ptree, parentp, child);	\
 }									\
 									\
 static __inline __unused struct type *					\
-name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr)		\
+name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key)		\
 {									\
+	uint64_t *val;							\
+	smr_pctnode_t *parentp;						\
+	struct pctrie_node *child;					\
 									\
-	return name##_PCTRIE_VAL2PTR(					\
-	    pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr)));		\
+	val = pctrie_remove_lookup(ptree, key, &parentp, &child);	\
+	if (val != NULL)						\
+		name##_PCTRIE_REMOVE_BASE(ptree, parentp, child);	\
+	return (name##_PCTRIE_VAL2PTR(val));				\
 }									\
 									\
 static __inline __unused void						\
-name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
+name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it)			\
 {									\
 	uint64_t *val;							\
-	struct pctrie_node *freenode;					\
+	smr_pctnode_t *parentp;						\
+	struct pctrie_node *child;					\
 									\
-	val = pctrie_remove_lookup(ptree, key, &freenode);		\
+	val = pctrie_iter_remove(it, &parentp, &child);			\
 	if (val == NULL)						\
 		panic("%s: key not found", __func__);			\
-	if (freenode != NULL)						\
-		freefn(ptree, freenode);				\
+	name##_PCTRIE_REMOVE_BASE(it->ptree, parentp, child);		\
 }									\
 									\
 static __inline __unused struct type *					\
-name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key)		\
+name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr)		\
 {									\
-	uint64_t *val;							\
-	struct pctrie_node *freenode;					\
-									\
-	val = pctrie_remove_lookup(ptree, key, &freenode);		\
-	if (freenode != NULL)						\
-		freefn(ptree, freenode);				\
-	return name##_PCTRIE_VAL2PTR(val);				\
+	smr_pctnode_t *parentp;						\
+	struct type *res;						\
+	struct pctrie_node *child;					\
+									\
+	res = name##_PCTRIE_VAL2PTR(					\
+	    pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr),		\
+	    &parentp, &child));						\
+	/* Synchronize to make changes visible. */			\
+	pctrie_node_store(parentp, child, access);			\
+	return (res);							\
 }
 
 struct pctrie_iter;
-void		*pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t	*pctrie_insert_lookup(struct pctrie *ptree, uint64_t index,
 		    uint64_t **found_out);
-void		*pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t	*pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t index,
 		    uint64_t **found_out, struct pctrie_node **neighbor_out);
-void		*pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
+smr_pctnode_t	*pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t index,
 		    uint64_t **found_out, struct pctrie_node **neighbor_out);
-void		*pctrie_insert_lookup_strict(struct pctrie *ptree,
-		    uint64_t *val);
-void		pctrie_insert_node(void *parentp,
+smr_pctnode_t	*pctrie_insert_lookup_strict(struct pctrie *ptree,
+		    uint64_t index);
+void		pctrie_insert_node(smr_pctnode_t *parentp,
 		    struct pctrie_node *parent, uint64_t *val);
 uint64_t	*pctrie_lookup(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
@@ -387,8 +473,8 @@
 uint64_t	*pctrie_iter_stride(struct pctrie_iter *it, int stride);
 uint64_t	*pctrie_iter_next(struct pctrie_iter *it);
 uint64_t	*pctrie_iter_prev(struct pctrie_iter *it);
-void		*pctrie_iter_insert_lookup(struct pctrie_iter *it,
-		    uint64_t *val);
+smr_pctnode_t	*pctrie_iter_insert_lookup(struct pctrie_iter *it,
+		    uint64_t index);
 uint64_t	*pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_subtree_lookup_gt(struct pctrie_node *node,
 		    uint64_t key);
@@ -408,22 +494,15 @@
 struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
 		    pctrie_cb_t callback, int keyoff, void *arg);
 uint64_t	*pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
-		    struct pctrie_node **killnode);
+		    smr_pctnode_t **parentp, struct pctrie_node **child);
 uint64_t	*pctrie_iter_remove(struct pctrie_iter *it,
-		    struct pctrie_node **freenode);
+		    smr_pctnode_t **parentp, struct pctrie_node **child);
 uint64_t	*pctrie_iter_value(struct pctrie_iter *it);
-uint64_t	*pctrie_replace(struct pctrie *ptree, uint64_t *newval);
+uint64_t	*pctrie_replace(struct pctrie *ptree, uint64_t *newval,
+		    smr_pctnode_t **parentp, struct pctrie_node **child);
 size_t		pctrie_node_size(void);
 int		pctrie_zone_init(void *mem, int size, int flags);
 
-/*
- * Each search path in the trie terminates at a leaf, which is a pointer to a
- * value marked with a set 1-bit.  A leaf may be associated with a null pointer
- * to indicate no value there.
- */
-#define	PCTRIE_ISLEAF	0x1
-#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
-
 static __inline void
 pctrie_init(struct pctrie *ptree)
 {