Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -164,6 +164,17 @@
 	return (pctrie_node_load(pctrie_root(ptree), smr, access));
 }
 
+/*
+ * Set the non-NULL root node for a tree.  Assumes that a write lock is held.
+ */
+void
+pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node)
+{
+	if (node != NULL)
+		pctrie_node_store(pctrie_root(ptree), node, PCTRIE_LOCKED);
+}
+
+
 /*
  * Get the child of a node.
  */
@@ -294,9 +305,9 @@
 	struct pctrie_node *parent;
 	int slot;
 
-	parent = node;
-	if (parent == NULL)
+	if (node == NULL)
 		node = pctrie_root_load(ptree, smr, access);
+	parent = pctrie_isleaf(node) ? NULL : node;
 
 	/*
 	 * Climb the search path to find the lowest node from which to start the
@@ -335,6 +346,7 @@
 
 	node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
 	    PCTRIE_LOCKED);
+	pctrie_root_store(ptree, parent);
 	return (pctrie_match_value(node, index));
 }
 
@@ -394,8 +406,8 @@
 			pctrie_node_store(pctrie_root(ptree),
 			    pctrie_toleaf(val), PCTRIE_LOCKED);
 		else
-			pctrie_addnode(*parent_out, *val,
-			    pctrie_toleaf(val), PCTRIE_LOCKED);
+			pctrie_addnode(*parent_out, *val, pctrie_toleaf(val),
+			    PCTRIE_LOCKED);
 		return (NULL);
 	}
 	if (__predict_false(pctrie_match_value(node, *val) != NULL)) {
@@ -408,6 +420,9 @@
 	 * children 'node' and 'val'. Return the place that points to 'node'
 	 * now, and will point to to the new branching node later.
 	 */
+	if (*parent_out == NULL)
+		pctrie_node_store(pctrie_root(ptree), node,
+		    PCTRIE_UNSERIALIZED);
 	return (pctrie_child(ptree, *parent_out, *val));
 }
 
@@ -632,8 +647,12 @@
 pctrie_lookup_range(struct pctrie *ptree, uint64_t index,
     uint64_t *value[], int count)
 {
-	return (_pctrie_lookup_range(ptree, NULL, index, value, count, NULL,
-	    NULL, PCTRIE_LOCKED));
+	struct pctrie_node *parent;
+
+	count = _pctrie_lookup_range(ptree, NULL, index, value, count, &parent,
+	    NULL, PCTRIE_LOCKED);
+	pctrie_root_store(ptree, parent);
+	return (count);
 }
 
 /*
@@ -727,14 +746,43 @@
 	return (m);
 }
 
+/*
+ * Find first leaf >= index, assuming access is externally synchronized by a
+ * lock, and set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
 uint64_t *
 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
 {
-	return (_pctrie_lookup_ge(ptree, NULL, index, NULL, 0));
+	struct pctrie_node *parent;
+	uint64_t *m;
+
+	m = _pctrie_lookup_ge(ptree, NULL, index, &parent, 0);
+	pctrie_root_store(ptree, parent);
+	return (m);
 }
 
 /*
- * Find first leaf >= index, and fill iter with the path to the parent of that
+ * Find next leaf > m, assuming access is externally synchronized by a lock, and
+ * set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
+uint64_t *
+pctrie_lookup_ge_step(struct pctrie *ptree, uint64_t *m)
+{
+	struct pctrie_node *parent;
+
+	if (*m + 1 == 0)
+		return (NULL);
+	m = _pctrie_lookup_ge(ptree, NULL, *m + 1, &parent, 0);
+	pctrie_root_store(ptree, parent);
+	return (m);
+}
+
+/*
+ * Find first leaf >= index, and set iter->node to the parent of that
  * leaf.  Return NULL if there is no such leaf less than limit.
  */
 uint64_t *
@@ -824,10 +872,21 @@
 	return (m);
 }
 
+/*
+ * Find first leaf <= index, assuming access is externally synchronized by a
+ * lock, and set root to the parent of that leaf.
+ *
+ * If no such leaf exists, NULL is returned.
+ */
 uint64_t *
 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
 {
-	return (_pctrie_lookup_le(ptree, NULL, index, NULL, 0));
+	struct pctrie_node *parent;
+	uint64_t *m;
+
+	m = _pctrie_lookup_le(ptree, NULL, index, &parent, 0);
+	pctrie_root_store(ptree, parent);
+	return (m);
 }
 
 uint64_t *
@@ -840,7 +899,7 @@
 }
 
 /*
- * Find first leaf <= index, and fill iter with the path to the parent of that
+ * Find first leaf <= index, and iter->node to the parent of that
  * leaf.  Return NULL if there is no such leaf greater than limit.
  */
 uint64_t *
@@ -925,10 +984,12 @@
 	node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
 	    PCTRIE_LOCKED);
 	m = pctrie_match_value(node, index);
-	if (m != NULL && pctrie_remove(ptree, parent, index))
+	if (m != NULL && pctrie_remove(ptree, parent, index)) {
 		*freenode = parent;
-	else
+		parent = pctrie_parent(*freenode);
+	} else
 		*freenode = NULL;
+	pctrie_root_store(ptree, parent);
 	return (m);
 }
 
@@ -945,7 +1006,11 @@
 	    (uintmax_t)it->index));
 	if (pctrie_remove(it->ptree, it->node, it->index)) {
 		*freenode = it->node;
-		it->node = pctrie_parent(it->node);
+		it->node = pctrie_parent(*freenode);
+		if (*freenode == pctrie_root_load(it->ptree, NULL,
+		    PCTRIE_LOCKED))
+			pctrie_node_store(pctrie_root(it->ptree), it->node,
+			    PCTRIE_LOCKED);
 	} else
 		*freenode = NULL;
 }
@@ -1028,6 +1093,8 @@
 			callback(pctrie_toptr(node, keyoff), arg);
 		return (NULL);
 	}
+	while (pctrie_parent(node) != NULL)
+		node = pctrie_parent(node);
 	*pnode = node;
 	return (pctrie_reclaim_prune(pnode, NULL, callback, keyoff, arg));
 }
@@ -1076,6 +1143,7 @@
 		panic("%s: original replacing value not found", __func__);
 	pctrie_node_store(pctrie_child(ptree, parent, *newval),
 	    pctrie_toleaf(newval), PCTRIE_LOCKED);
+	pctrie_root_store(ptree, parent);
 	return (m);
 }
 
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -158,10 +158,13 @@
 	void *parentp;							\
 	struct pctrie_node *parent;					\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
+	int retval;							\
 									\
 	parentp = pctrie_insert_lookup_strict(ptree, val, &parent);	\
-	return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,	\
-	    NULL, NULL));						\
+	retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+	    NULL, NULL);						\
+	pctrie_root_store(ptree, parent);				\
+	return (retval);						\
 }									\
 									\
 static __inline __unused int						\
@@ -172,10 +175,13 @@
 	struct pctrie_node *parent;					\
 	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
 	uint64_t *found;						\
+	int retval;							\
 									\
 	parentp = pctrie_insert_lookup(ptree, val, &parent, &found);	\
-	return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,	\
-	    found, found_out_opt));					\
+	retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+	    found, found_out_opt);					\
+	pctrie_root_store(ptree, parent);				\
+	return (retval);						\
 }									\
 									\
 static __inline __unused int						\
@@ -191,6 +197,7 @@
 	parentp = pctrie_insert_lookup(ptree, val, &parent, &found);	\
 	retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
 	    found, found_out);						\
+	pctrie_root_store(ptree, parent);				\
 	if (retval != 0)						\
 		return (retval);					\
 	found = pctrie_subtree_lookup_lt(ptree, parent, *val);		\
@@ -254,6 +261,14 @@
 	return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key));	\
 }									\
 									\
+static __inline __unused struct type *					\
+name##_PCTRIE_LOOKUP_GE_STEP(struct pctrie *ptree, struct type *ptr)	\
+{									\
+									\
+	return name##_PCTRIE_VAL2PTR(					\
+	    pctrie_lookup_ge_step(ptree, name##_PCTRIE_PTR2VAL(ptr)));	\
+}									\
+									\
 static __inline __unused void						\
 name##_PCTRIE_RECLAIM(struct pctrie *ptree)				\
 {									\
@@ -359,23 +374,6 @@
 }									\
 									\
 static __inline __unused void						\
-name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it)			\
-{									\
-	struct pctrie_node *freenode;					\
-									\
-	pctrie_iter_remove(it, &freenode);				\
-	name##_PCTRIE_REMOVE_BASE(it->ptree, freenode);			\
-}									\
-									\
-static __inline __unused struct type *					\
-name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr)		\
-{									\
-									\
-	return name##_PCTRIE_VAL2PTR(					\
-	    pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr)));		\
-}									\
-									\
-static __inline __unused void						\
 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
 {									\
 	uint64_t *val;							\
@@ -396,6 +394,23 @@
 	val = pctrie_remove_lookup(ptree, key, &freenode);		\
 	name##_PCTRIE_REMOVE_BASE(ptree, freenode);			\
 	return name##_PCTRIE_VAL2PTR(val);				\
+}									\
+									\
+static __inline __unused void						\
+name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it)			\
+{									\
+	struct pctrie_node *freenode;					\
+									\
+	pctrie_iter_remove(it, &freenode);				\
+	name##_PCTRIE_REMOVE_BASE(it->ptree, freenode);			\
+}									\
+									\
+static __inline __unused struct type *					\
+name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr)		\
+{									\
+									\
+	return name##_PCTRIE_VAL2PTR(					\
+	    pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr)));		\
 }
 
 struct pctrie_iter;
@@ -421,6 +436,7 @@
 void		*pctrie_iter_insert_lookup(struct pctrie_iter *it,
 		    uint64_t *val);
 uint64_t	*pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
+uint64_t	*pctrie_lookup_ge_step(struct pctrie *ptree, uint64_t *m);
 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);
 uint64_t	*pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
@@ -438,6 +454,8 @@
 		    pctrie_cb_t callback, int keyoff, void *arg);
 uint64_t	*pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
 		    struct pctrie_node **killnode);
+void		pctrie_root_store(struct pctrie *ptree,
+		    struct pctrie_node *node);
 void		pctrie_iter_remove(struct pctrie_iter *it,
 		    struct pctrie_node **freenode);
 uint64_t	*pctrie_iter_value(struct pctrie_iter *it);