Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -285,7 +285,7 @@
 static __always_inline void *
 pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t *val,
     uint64_t **found_out, struct pctrie_node **neighbor_out,
-    enum pctrie_insert_neighbor_mode mode)
+    void **parentp_out, enum pctrie_insert_neighbor_mode mode)
 {
 	uint64_t index;
 	struct pctrie_node *node, *parent;
@@ -302,6 +302,11 @@
 	for (;;) {
 		if (pctrie_isleaf(node)) {
 			if (node == PCTRIE_NULL) {
+				if (parentp_out != NULL) {
+					*parentp_out = (parent == NULL) ?
+					    (smr_pctnode_t *)&ptree->pt_root :
+					    &parent->pn_child[slot];
+				}
 				if (parent == NULL)
 					ptree->pt_root = pctrie_toleaf(val);
 				else
@@ -367,7 +372,7 @@
 	uint64_t *found;
 
 	found = NULL;
-	parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
+	parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL, NULL,
 	    PCTRIE_INSERT_NEIGHBOR_NONE);
 	if (__predict_false(found != NULL))
 		panic("%s: key %jx is already present", __func__,
@@ -384,7 +389,7 @@
     uint64_t **found_out)
 {
 	*found_out = NULL;
-	return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
+	return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL, NULL,
 	    PCTRIE_INSERT_NEIGHBOR_NONE));
 }
 
@@ -400,7 +405,7 @@
 	*found_out = NULL;
 	*neighbor_out = NULL;
 	return (pctrie_insert_lookup_compound(ptree, val, found_out,
-	    neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
+	    neighbor_out, NULL, PCTRIE_INSERT_NEIGHBOR_GT));
 }
 
 /*
@@ -415,14 +420,55 @@
 	*found_out = NULL;
 	*neighbor_out = NULL;
 	return (pctrie_insert_lookup_compound(ptree, val, found_out,
-	    neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
+	    neighbor_out, NULL, PCTRIE_INSERT_NEIGHBOR_LT));
+}
+
+/*
+ * Wrap pctrie_insert_lookup_compound to implement find or insert and find next
+ * greater entry.  Find a subtree that contains the next entry greater than the
+ * newly-inserted or to-be-inserted entry, and the address of the pointer to the
+ * newly inserted node.
+ */
+void *
+pctrie_insert_lookup_gt_parent(struct pctrie *ptree, uint64_t *val,
+    uint64_t **found_out, struct pctrie_node **neighbor_out,
+    void **pparent_out)
+{
+	*found_out = NULL;
+	*neighbor_out = NULL;
+	return (pctrie_insert_lookup_compound(ptree, val, found_out,
+	    neighbor_out, pparent_out, PCTRIE_INSERT_NEIGHBOR_GT));
+}
+
+/*
+ * Wrap pctrie_insert_lookup_compound to implement find or insert and find next
+ * lesser entry.  Find a subtree that contains the next entry less than the
+ * newly-inserted or to-be-inserted entry, and the address of the pointer to the
+ * newly inserted node..
+ */
+void *
+pctrie_insert_lookup_lt_parent(struct pctrie *ptree, uint64_t *val,
+    uint64_t **found_out, struct pctrie_node **neighbor_out,
+    void **pparent_out)
+{
+	*found_out = NULL;
+	*neighbor_out = NULL;
+	return (pctrie_insert_lookup_compound(ptree, val, found_out,
+	    neighbor_out, pparent_out, PCTRIE_INSERT_NEIGHBOR_LT));
 }
 
 /*
  * Uses new node to insert key-value pair into the trie at given location.
+ * 
+ * With parentp_out set, store the insertion location in the newly allocated
+ * parent of the newly inserted node.
+ *
+ * This procedure is expected to be inlined into callers with extraneous code
+ * optimized out.
  */
-void
-pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val)
+static __inline void
+pctrie_insert_node_compound(void *parentp, struct pctrie_node *parent,
+    uint64_t *val, void **parentp_out)
 {
 	struct pctrie_node *node;
 	uint64_t index, newind;
@@ -460,7 +506,10 @@
 	parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
 	parent->pn_owner = PCTRIE_COUNT;
 	parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev);
-
+	if (parentp_out != NULL) {
+		int slot = pctrie_slot(parent, index);
+		*parentp_out = &parent->pn_child[slot];
+	}
 
 	/* These writes are not yet visible due to ordering. */
 	pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
@@ -469,6 +518,28 @@
 	pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
 }
 
+/*
+ * Wrap pctrie_insert_node_compound to use a 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_compound(parentp, parent, val, NULL);
+}
+
+/*
+ * Wrap pctrie_insert_node_compound to use a new node to insert key-value pair
+ * into the trie at given location, and recover the address of the pointer
+ * that points to the new node, to allow fast replacement.
+ */
+void
+pctrie_insert_node_parent(void *parentp, struct pctrie_node *parent,
+    uint64_t *val, void **parentp_out)
+{
+	pctrie_insert_node_compound(parentp, parent, val, parentp_out);
+}
+
 /*
  * Returns the value stored at the index.  If the index is not present,
  * NULL is returned.
@@ -897,6 +968,16 @@
 	panic("%s: original replacing value not found", __func__);
 }
 
+/*
+ * Given parentp, the address of a pointer to a leaf in the trie, replace the
+ * value that parentp points to with a new one.
+ */
+void
+pctrie_fast_replace(void *parentp, uint64_t *val)
+{
+	pctrie_node_store(parentp, pctrie_toleaf(val), PCTRIE_LOCKED);
+}
+
 #ifdef DDB
 /*
  * Show details about the given node.
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -186,6 +186,70 @@
 	return (0);							\
 }									\
 									\
+static __inline __unused int						\
+name##_PCTRIE_INSERT_LOOKUP_GE_PARENT(struct pctrie *ptree,		\
+    struct type *ptr, struct type **found_out, void **pparent_out)	\
+{									\
+	struct pctrie_node *parent, *neighbor;				\
+	void *parentp;							\
+	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
+	uint64_t *found;						\
+									\
+	parentp = pctrie_insert_lookup_gt_parent(ptree, val, &found,	\
+	    &neighbor, pparent_out);					\
+	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_parent(parentp, parent, val,		\
+		    pparent_out);					\
+	}								\
+	found = pctrie_subtree_lookup_gt(neighbor, *val);		\
+	*found_out = name##_PCTRIE_VAL2PTR(found);			\
+	pctrie_subtree_lookup_gt_assert(neighbor, *val, ptree, found);	\
+	return (0);							\
+}									\
+									\
+static __inline __unused int						\
+name##_PCTRIE_INSERT_LOOKUP_LE_PARENT(struct pctrie *ptree,		\
+    struct type *ptr, struct type **found_out, void **pparent_out)	\
+{									\
+	struct pctrie_node *parent, *neighbor;				\
+	void *parentp;							\
+	uint64_t *val = name##_PCTRIE_PTR2VAL(ptr);			\
+	uint64_t *found;						\
+									\
+	parentp = pctrie_insert_lookup_lt_parent(ptree, val, &found,	\
+	    &neighbor, pparent_out);					\
+	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_parent(parentp, parent, val,		\
+		    pparent_out);					\
+	}								\
+	found = pctrie_subtree_lookup_lt(neighbor, *val);		\
+	*found_out = name##_PCTRIE_VAL2PTR(found);			\
+	pctrie_subtree_lookup_lt_assert(neighbor, *val, ptree, found);	\
+	return (0);							\
+}									\
+									\
 static __inline __unused struct type *					\
 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key)		\
 {									\
@@ -227,6 +291,13 @@
 }									\
 									\
 static __inline __unused void						\
+name##_PCTRIE_FAST_REPLACE(void *parentp, struct type *ptr)		\
+{									\
+									\
+	pctrie_fast_replace(parentp, name##_PCTRIE_PTR2VAL(ptr));	\
+}									\
+									\
+static __inline __unused void						\
 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
 {									\
 	uint64_t *val;							\
@@ -257,10 +328,21 @@
 		    uint64_t **found_out, struct pctrie_node **neighbor_out);
 void		*pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
 		    uint64_t **found_out, struct pctrie_node **neighbor_out);
+void		*pctrie_insert_lookup_gt_parent(struct pctrie *ptree,
+		    uint64_t *val, uint64_t **found_out,
+		    struct pctrie_node **neighbor_out,
+		    void **pparent_out);
+void		*pctrie_insert_lookup_lt_parent(struct pctrie *ptree,
+                    uint64_t *val, uint64_t **found_out,
+		    struct pctrie_node **neighbor_out,
+		    void **pparent_out);
 void		*pctrie_insert_lookup_strict(struct pctrie *ptree,
 		    uint64_t *val);
 void		pctrie_insert_node(void *parentp,
 		    struct pctrie_node *parent, uint64_t *val);
+void		pctrie_insert_node_parent(void *parentp,
+		    struct pctrie_node *parent, uint64_t *val,
+		    void **parentp_out);
 uint64_t	*pctrie_lookup(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
 uint64_t	*pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
@@ -272,6 +354,7 @@
 uint64_t	*pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
 		    struct pctrie_node **killnode);
 uint64_t	*pctrie_replace(struct pctrie *ptree, uint64_t *newval);
+void		pctrie_fast_replace(void *parentp, uint64_t *val);
 uint64_t	*pctrie_subtree_lookup_gt(struct pctrie_node *node,
 		    uint64_t key);
 uint64_t	*pctrie_subtree_lookup_lt(struct pctrie_node *node,
Index: sys/vm/vm_radix.h
===================================================================
--- sys/vm/vm_radix.h
+++ sys/vm/vm_radix.h
@@ -89,6 +89,30 @@
 	return (error);
 }
 
+/*
+ * Insert the a dummy page into the vm_radix tree with index as the key.
+ * Panic if the pindex already exists.  Return zero on success or a non-zero
+ * error on memory allocation failure.  Set the out parameter mpred to the
+ * previous page in the tree as if found by a previous call to
+ * vm_radix_lookup_le with the new page pindex.  Set the out parameter
+ * pparent_ptr to the address of the pointer to the dummy page, so that the
+ * dummy page can be replaced directly.
+ */
+static __inline int
+vm_radix_insert_lookup_lt_parent(struct vm_radix *rtree, vm_pindex_t index,
+    vm_page_t *mpred, void **pparent_ptr)
+{
+	struct vm_page page = {.pindex = index};
+	int error;
+
+	error = VM_RADIX_PCTRIE_INSERT_LOOKUP_LE_PARENT(&rtree->rt_trie,
+	    &page, mpred, pparent_ptr);
+	if (__predict_false(error == EEXIST))
+		panic("vm_radix_insert_lookup_lt: page already present, %p",
+		    *mpred);
+	return (error);
+}
+
 /*
  * Returns the value stored at the index assuming there is an external lock.
  *
@@ -155,8 +179,8 @@
 }
 
 /*
- * Replace an existing page in the trie with another one.
- * Panics if there is not an old page in the trie at the new page's index.
+ * Replace an existing page in the trie with another one, after searching for
+ * it.  Panics if there is not an old page in the trie at the new page's index.
  */
 static __inline vm_page_t
 vm_radix_replace(struct vm_radix *rtree, vm_page_t newpage)
@@ -164,5 +188,16 @@
 	return (VM_RADIX_PCTRIE_REPLACE(&rtree->rt_trie, newpage));
 }
 
+/*
+ * Replace an existing page in the trie with another one, given the address of
+ * the pointer to the existing page.  Panics if there is not an old page in the
+ * trie at the new page's index.
+ */
+static __inline void
+vm_radix_fast_replace(void *parentp, vm_page_t newpage)
+{
+	VM_RADIX_PCTRIE_FAST_REPLACE(parentp, newpage);
+}
+
 #endif /* _KERNEL */
 #endif /* !_VM_RADIX_H_ */