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,44 +102,6 @@
 	return (false);
 }
 
-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;
-	}
-}
-
 /*
  * Get the root address, cast to proper type for load/store.
  */
@@ -167,6 +123,12 @@
 /*
  * Get the child of a node.
  */
+static __inline smr_pctnode_t *
+pctrie_child_slot(struct pctrie *ptree, struct pctrie_node *node, int slot)
+{
+	return (node == NULL ? pctrie_root(ptree) : &node->pn_child[slot]);
+}
+
 static __inline smr_pctnode_t *
 pctrie_child(struct pctrie *ptree, struct pctrie_node *node, uint64_t index)
 {
@@ -183,15 +145,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,21 +180,29 @@
 {
 	return (pctrie_node_load(&node->pn_parent, NULL, PCTRIE_UNSERIALIZED));
 }
+/*
+ * Change the state of the 'slot'th popmap bit from clear to set.
+ */
+static __inline void
+pctrie_setpop(struct pctrie_node *node, int slot)
+{
+	node->pn_popmap ^= 1 << slot;
+	KASSERT((node->pn_popmap & (1 << slot)) != 0,
+	    ("%s: bad popmap slot %d in node %p", __func__, slot, node));
+}
 
 /*
  * Make 'child' a child of 'node'.
  */
 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);
-	node->pn_popmap ^= 1 << slot;
-	KASSERT((node->pn_popmap & (1 << slot)) != 0,
-	    ("%s: bad popmap slot %d in node %p", __func__, slot, node));
+	pctrie_node_store(&node->pn_child[slot], child, PCTRIE_UNSERIALIZED);
+	pctrie_setpop(node, slot);
 }
 
 /*
@@ -268,22 +229,22 @@
 }
 
 /*
- * Look for where to insert the key-value pair into the trie.  Complete the
- * insertion if it replaces a null leaf.  Return the insertion location if the
- * insertion needs to be completed by the caller; otherwise return NULL.
+ * Look for where to insert the key-value pair into the trie.  Return the
+ * insertion location so that the insertion can be completed by the caller;
+ * otherwise return NULL.
  *
  * If the key is already present in the trie, populate *found_out as if by
  * pctrie_lookup().
  */
-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,
     struct pctrie_node **parent_out, uint64_t **found_out)
 {
-	uint64_t index;
 	struct pctrie_node *node, *parent;
 	int slot;
 
-	index = *val;
+	if (found_out != NULL)
+		*found_out = NULL;
 
 	/*
 	 * The owner of record for root is not really important because it
@@ -291,58 +252,46 @@
 	 */
 	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
 	parent = NULL;
-	for (;;) {
-		if (pctrie_isleaf(node)) {
-			if (node == PCTRIE_NULL) {
-				if (parent == NULL)
-					pctrie_node_store(pctrie_root(ptree),
-					    pctrie_toleaf(val), PCTRIE_LOCKED);
-				else
-					pctrie_addnode(parent, index,
-					    pctrie_toleaf(val), PCTRIE_LOCKED);
-				*parent_out = parent;
-				return (NULL);
-			}
+	while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
+		parent = node;
+		node = pctrie_node_load(&node->pn_child[slot], NULL,
+		    PCTRIE_LOCKED);
+	}
+	if (pctrie_isleaf(node)) {
+		if (node != PCTRIE_NULL) {
 			if (*pctrie_toval(node) == index) {
 				*found_out = pctrie_toval(node);
-				*parent_out = parent;
 				return (NULL);
 			}
-			break;
-		}
-		if (pctrie_keybarr(node, index, &slot))
-			break;
-		parent = node;
-		node = pctrie_node_load(&node->pn_child[slot], NULL,
-		    PCTRIE_LOCKED);
+		} else if (parent != NULL)
+			pctrie_setpop(parent, 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 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.
 	 */
 	*parent_out = parent;
-	return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]);
+	return (pctrie_child_slot(ptree, parent, 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,
     struct pctrie_node **parent_out)
 {
-	void *parentp;
+	smr_pctnode_t *parentp;
 	uint64_t *found;
 
-	found = NULL;
-	parentp = pctrie_insert_lookup_compound(ptree, val, parent_out,
+	parentp = pctrie_insert_lookup_compound(ptree, index, parent_out,
 	    &found);
 	if (__predict_false(found != NULL))
 		panic("%s: key %jx is already present", __func__,
-		    (uintmax_t)*val);
+		    (uintmax_t)index);
 	return (parentp);
 }
 
@@ -350,12 +299,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,
     struct pctrie_node **parent_out, uint64_t **found_out)
 {
-	*found_out = NULL;
-	return (pctrie_insert_lookup_compound(ptree, val, parent_out,
+	return (pctrie_insert_lookup_compound(ptree, index, parent_out,
 	    found_out));
 }
 
@@ -365,10 +313,9 @@
  * was at 'parentp' to begin with.
  */
 void
-pctrie_insert_node(uint64_t *val, struct pctrie_node *parent, void *parentp,
-    struct pctrie_node *child)
+pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
+    struct pctrie_node *node, struct pctrie_node *child)
 {
-	struct pctrie_node *node;
 	uint64_t index, newind;
 
 	/*
@@ -389,7 +336,6 @@
 	 * which must be first in the node.
 	 */
 	index = *val;
-	node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);
 	pctrie_setparent(child, parent);
 	if (!pctrie_isleaf(node))
 		pctrie_setparent(node, child);
@@ -410,10 +356,8 @@
 
 
 	/* These writes are not yet visible due to ordering. */
-	pctrie_addnode(child, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
-	pctrie_addnode(child, newind, node, PCTRIE_UNSERIALIZED);
-	/* Synchronize to make the above visible. */
-	pctrie_node_store(parentp, child, PCTRIE_LOCKED);
+	pctrie_addnode(child, index, pctrie_toleaf(val));
+	pctrie_addnode(child, newind, node);
 }
 
 /*
@@ -548,31 +492,25 @@
  * 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;
 
-	it->index = *val;
-	node = _pctrie_lookup_node(it->ptree, it->node, *val, &it->node,
+	it->index = index;
+	node = _pctrie_lookup_node(it->ptree, it->node, index, &it->node,
 	    NULL, PCTRIE_LOCKED);
-	if (node == PCTRIE_NULL) {
-		if (it->node == NULL)
-			pctrie_node_store(pctrie_root(it->ptree),
-			    pctrie_toleaf(val), PCTRIE_LOCKED);
-		else
-			pctrie_addnode(it->node, it->index,
-			    pctrie_toleaf(val), PCTRIE_LOCKED);
-		return (NULL);
-	}
-	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 (it->node != NULL)
+		pctrie_setpop(it->node, pctrie_slot(it->node, index));
 
 	/*
-	 * '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.
 	 */
 	return (pctrie_child(it->ptree, it->node, it->index));
 }
@@ -826,47 +764,38 @@
 }
 
 /*
- * If 'child', a leaf and a child of 'parent', is not NULL and has key 'index',
- * then remove it from the pctrie and return its value.  If doing so produces an
- * internal node with only one child, purge it from the pctrie and save it in
- * *freenode for later disposal.
+ * Use 'index' to identify a to-be-removed child of 'node' and return the
+ * address of the pointer to that child; set 'child' to the value that will
+ * stored at that address to complete the removal.  If 'child' is an internal
+ * node, reset its parent pointer.
  */
-static uint64_t *
+static smr_pctnode_t *
 pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index,
-    struct pctrie_node *child, struct pctrie_node **freenode)
+    struct pctrie_node **child)
 {
-	uint64_t *m;
 	int slot;
 
-	*freenode = NULL;
-	m = pctrie_match_value(child, index);
-	if (m == NULL)
-		return (m);
-	if (node == NULL) {
-		pctrie_node_store(pctrie_root(ptree),
-		    PCTRIE_NULL, PCTRIE_LOCKED);
-		return (m);
-	}
+	*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 (m);
+		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));
-	*freenode = node;
 	node = pctrie_parent(node);
-	if (!pctrie_isleaf(child))
-		pctrie_setparent(child, node);
-	pctrie_node_store(pctrie_child(ptree, node, index), child,
-	    PCTRIE_LOCKED);
-	return (m);
+	if (!pctrie_isleaf(*child))
+		pctrie_setparent(*child, node);
+	return (pctrie_child(ptree, node, index));
 }
 
 /*
@@ -875,38 +804,40 @@
  */
 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;
+	struct pctrie_node *next, *node;
+	uint64_t *m;
 	int slot;
 
 	node = NULL;
-	child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
-	while (!pctrie_isleaf(child)) {
-		node = child;
+	next = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
+	while (!pctrie_isleaf(next)) {
+		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);
 	}
-	return (pctrie_remove(ptree, node, index, child, freenode));
+	if ((m = pctrie_match_value(next, index)) != NULL)
+		*parentp = pctrie_remove(ptree, node, index, child);
+	return (m);
 }
 
 /*
  * Remove from the trie the leaf last chosen by the iterator, and
  * 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)
+smr_pctnode_t *
+pctrie_iter_remove(struct pctrie_iter *it, struct pctrie_node **child)
 {
-	struct pctrie_node *child;
-	uint64_t *m;
-
-	child = pctrie_node_load(pctrie_child(it->ptree, it->node, it->index),
-	    NULL, PCTRIE_LOCKED);
-	m = pctrie_remove(it->ptree, it->node, it->index, child, freenode);
-	if (*freenode != NULL)
+	KASSERT(NULL != pctrie_match_value(pctrie_node_load(pctrie_child(
+	    it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index),
+	    ("%s: removing value %lx not at iter", __func__, it->index));
+	smr_pctnode_t *parentp =
+	    pctrie_remove(it->ptree, it->node, it->index, child);
+	if (*child != PCTRIE_NULL)
 		it->node = pctrie_parent(it->node);
-	return (m);
+	return (parentp);
 }
 
 /*
@@ -1023,37 +954,29 @@
  * 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_node_store(pctrie_root(ptree),
-					    leaf, PCTRIE_LOCKED);
-				else
-					pctrie_node_store(
-					    &parent->pn_child[slot], leaf,
-					    PCTRIE_LOCKED);
-				return (m);
-			}
-			break;
-		}
-		if (pctrie_keybarr(node, index, &slot))
-			break;
+	while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
 		parent = node;
 		node = pctrie_node_load(&node->pn_child[slot], NULL,
 		    PCTRIE_LOCKED);
 	}
+	if (pctrie_isleaf(node) &&
+	    (m = pctrie_toval(node)) != NULL && *m == index) {
+		*parentp = pctrie_child_slot(ptree, parent, slot);
+		return (m);
+	}
+
 	panic("%s: original replacing value not found", __func__);
 }
 
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -33,6 +33,11 @@
 
 #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;
 
 struct pctrie_iter {
 	struct pctrie *ptree;
@@ -67,8 +72,69 @@
 
 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)	\
@@ -76,9 +142,9 @@
 									\
 	return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree,	\
 	    key, (smr)));						\
-}									\
+}
 
-#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));	\
 /*									\
@@ -106,35 +172,39 @@
 									\
 static __inline __unused int						\
 name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, uint64_t *val,		\
-    struct pctrie_node *parent, void *parentp,				\
+    struct pctrie_node *parent, smr_pctnode_t *parentp,			\
     uint64_t *found, struct type **found_out)				\
 {									\
-	struct pctrie_node *child;					\
+	struct pctrie_node *child, *node;				\
 									\
 	if (__predict_false(found != NULL)) {				\
 		*found_out = name##_PCTRIE_VAL2PTR(found);		\
 		return (EEXIST);					\
 	}								\
-	if (parentp != NULL) {						\
+	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(val, parent, parentp, child);	\
-	}								\
+		pctrie_insert_node(val, parent, node, child);		\
+	} 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)		\
 {									\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	struct pctrie_node *parent;					\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 									\
-	parentp = pctrie_insert_lookup_strict(ptree, val, &parent);	\
+	parentp = pctrie_insert_lookup_strict(ptree, *val, &parent);	\
 	return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp,	\
 	    NULL, NULL));						\
 }									\
@@ -143,12 +213,12 @@
 name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr,	\
     struct type **found_out_opt)					\
 {									\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	struct pctrie_node *parent;					\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
 									\
-	parentp = pctrie_insert_lookup(ptree, val, &parent, &found);	\
+	parentp = pctrie_insert_lookup(ptree, *val, &parent, &found);	\
 	return (name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp,	\
 	    found, found_out_opt));					\
 }									\
@@ -158,12 +228,12 @@
     struct type **found_out)						\
 {									\
 	struct pctrie_node *parent;					\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
 	int retval;							\
 									\
-	parentp = pctrie_insert_lookup(ptree, val, &parent, &found);	\
+	parentp = pctrie_insert_lookup(ptree, *val, &parent, &found);	\
 	retval = name##_PCTRIE_INSERT_BASE(ptree, val, parent, parentp, \
 	    found, found_out);						\
 	if (retval != 0)						\
@@ -176,10 +246,10 @@
 static __inline __unused int						\
 name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr)	\
 {									\
-	void *parentp;							\
+	smr_pctnode_t *parentp;						\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 									\
-	parentp = pctrie_iter_insert_lookup(it, val);			\
+	parentp = pctrie_iter_insert_lookup(it, *val);			\
 	return (name##_PCTRIE_INSERT_BASE(it->ptree, val, it->node,	\
 	    parentp, NULL, NULL));					\
 }									\
@@ -303,62 +373,78 @@
 									\
 static __inline __unused void						\
 name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree,				\
-    struct pctrie_node *freenode)					\
+    smr_pctnode_t *parentp, struct pctrie_node *child)			\
 {									\
+	struct pctrie_node *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_ITER_REMOVE(struct pctrie_iter *it)			\
+name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
 {									\
 	uint64_t *val;							\
-	struct pctrie_node *freenode;					\
+	smr_pctnode_t *parentp;						\
+	struct pctrie_node *child;					\
 									\
-	val = pctrie_iter_remove(it, &freenode);			\
+	val = pctrie_remove_lookup(ptree, key, &parentp, &child);	\
 	if (val == NULL)						\
 		panic("%s: key not found", __func__);			\
-	name##_PCTRIE_REMOVE_BASE(it->ptree, freenode);			\
+	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);		\
-	if (val == NULL)						\
-		panic("%s: key not found", __func__);			\
-	name##_PCTRIE_REMOVE_BASE(ptree, freenode);			\
+	parentp = pctrie_iter_remove(it, &child);			\
+	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;					\
+	smr_pctnode_t *parentp;						\
+	struct type *res;						\
+	struct pctrie_node *child;					\
 									\
-	val = pctrie_remove_lookup(ptree, key, &freenode);		\
-	name##_PCTRIE_REMOVE_BASE(ptree, freenode);			\
-	return name##_PCTRIE_VAL2PTR(val);				\
+	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,
 		    struct pctrie_node **parent_out, uint64_t **found_out);
-void		*pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val,
-		    struct pctrie_node **parent_out);
+smr_pctnode_t	*pctrie_insert_lookup_strict(struct pctrie *ptree,
+		    uint64_t index, struct pctrie_node **parent_out);
 void		pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
-		    void *parentp, struct pctrie_node *child);
+		    struct pctrie_node *node, struct pctrie_node *child);
 uint64_t	*pctrie_lookup(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
 		    smr_t smr);
@@ -366,8 +452,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_iter_lookup_ge(struct pctrie_iter *it, uint64_t index);
 uint64_t	*pctrie_iter_jump_ge(struct pctrie_iter *it, int64_t jump);
@@ -385,22 +471,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);
-uint64_t	*pctrie_iter_remove(struct pctrie_iter *it,
-		    struct pctrie_node **freenode);
+		    smr_pctnode_t **parentp, struct pctrie_node **child);
+smr_pctnode_t	*pctrie_iter_remove(struct pctrie_iter *it,
+		    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)
 {