git: d0fb642b6457 - stable/13 - rb_tree: let insert search start from next node

From: Doug Moore <dougm_at_FreeBSD.org>
Date: Mon, 24 Oct 2022 00:44:03 UTC
The branch stable/13 has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=d0fb642b64571de87ae444c960b3d21c3d0ed79d

commit d0fb642b64571de87ae444c960b3d21c3d0ed79d
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-10-03 03:27:21 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-10-24 00:43:22 +0000

    rb_tree: let insert search start from next node
    
    When the node to insert in the rb_tree is known to precede or follow a
    particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT,
    defined here, allow the search for where to insert the new node begin
    with that particular node, rather than at the root, to save a bit of
    time.
    
    Using those methods, instead of RB_INSERT, in managing a tree in
    iommu_gas.c, saves a little time.
    
    Reviewed by:    kib
    MFC after:      3 weeks
    Differential Revision:  https://reviews.freebsd.org/D35516
    
    (cherry picked from commit 368ee2f86a0f4f60338472be4bfd3c09ab401f87)
---
 share/man/man3/tree.3     |  18 ++++++++
 sys/dev/iommu/iommu_gas.c |  60 +++++++++++++-------------
 sys/sys/tree.h            | 104 +++++++++++++++++++++++++++++++++++++++-------
 3 files changed, 136 insertions(+), 46 deletions(-)

diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
index eaddc9f811c4..cc4c836e8889 100644
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -97,6 +97,8 @@
 .Nm RB_FOREACH_REVERSE_SAFE ,
 .Nm RB_INIT ,
 .Nm RB_INSERT ,
+.Nm RB_INSERT_NEXT ,
+.Nm RB_INSERT_PREV ,
 .Nm RB_REMOVE ,
 .Nm RB_REINSERT ,
 .Nm RB_AUGMENT
@@ -193,6 +195,10 @@
 .Ft "struct TYPE *"
 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
 .Ft "struct TYPE *"
+.Fn RB_INSERT_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *next"
+.Ft "struct TYPE *"
+.Fn RB_INSERT_PREV NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *prev"
+.Ft "struct TYPE *"
 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
 .Ft "struct TYPE *"
 .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
@@ -515,6 +521,18 @@ macro inserts the new element
 into the tree.
 .Pp
 The
+.Fn RB_INSERT_NEXT
+macro inserts the new element
+.Fa elm
+into the tree immediately after a given element.
+.Pp
+The
+.Fn RB_INSERT_PREV
+macro inserts the new element
+.Fa elm
+into the tree immediately before a given element.
+.Pp
+The
 .Fn RB_REMOVE
 macro removes the element
 .Fa elm
diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
index c04edb8451b4..8c8d0e49c378 100644
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -206,15 +206,6 @@ iommu_gas_check_free(struct iommu_domain *domain)
 }
 #endif
 
-static bool
-iommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry)
-{
-	struct iommu_map_entry *found;
-
-	found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry);
-	return (found == NULL);
-}
-
 static void
 iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry)
 {
@@ -255,12 +246,12 @@ iommu_gas_init_domain(struct iommu_domain *domain)
 	end->start = domain->end;
 	end->end = domain->end;
 	end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
-	iommu_gas_rb_insert(domain, end);
+	RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end);
 
 	begin->start = 0;
 	begin->end = IOMMU_PAGE_SIZE;
 	begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
-	iommu_gas_rb_insert(domain, begin);
+	RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);
 
 	domain->first_place = begin;
 	domain->last_place = end;
@@ -283,7 +274,7 @@ iommu_gas_fini_domain(struct iommu_domain *domain)
 	KASSERT(entry->flags ==
 	    (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
 	    ("start entry flags %p", domain));
-	RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
+	iommu_gas_rb_remove(domain, entry);
 	iommu_gas_free_entry(entry);
 
 	entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
@@ -292,15 +283,14 @@ iommu_gas_fini_domain(struct iommu_domain *domain)
 	KASSERT(entry->flags ==
 	    (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
 	    ("end entry flags %p", domain));
-	RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
+	iommu_gas_rb_remove(domain, entry);
 	iommu_gas_free_entry(entry);
 
 	RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
 	    entry1) {
 		KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
 		    ("non-RMRR entry left %p", domain));
-		RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root,
-		    entry);
+		iommu_gas_rb_remove(domain, entry);
 		iommu_gas_free_entry(entry);
 	}
 }
@@ -326,7 +316,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
 {
 	struct iommu_map_entry *entry;
 	iommu_gaddr_t first, size, start;
-	bool found __diagused;
 	int offset;
 
 	/*
@@ -380,9 +369,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
 	entry->start = start;
 	entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
 	entry->flags = IOMMU_MAP_ENTRY_MAP;
-	found = iommu_gas_rb_insert(a->domain, entry);
-	KASSERT(found, ("found dup %p start %jx size %jx",
-	    a->domain, (uintmax_t)start, (uintmax_t)size));
 	return (true);
 }
 
@@ -431,7 +417,8 @@ iommu_gas_find_space(struct iommu_gas_match_args *a)
 	 * Find the first entry in the lower region that could abut a big-enough
 	 * range.
 	 */
-	curr = RB_ROOT(&a->domain->rb_root);
+	domain = a->domain;
+	curr = RB_ROOT(&domain->rb_root);
 	first = NULL;
 	while (curr != NULL && curr->free_down >= min_free) {
 		first = curr;
@@ -447,16 +434,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a)
 	    curr = iommu_gas_next(curr, min_free)) {
 		if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
 		    iommu_gas_match_one(a, first->last, curr->start,
-		    0, addr))
+		    0, addr)) {
+			RB_INSERT_PREV(iommu_gas_entries_tree,
+			    &domain->rb_root, curr, a->entry);
 			return (0);
+		}
 		if (curr->end >= addr) {
 			/* All remaining ranges >= addr */
 			break;
 		}
 		if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
 		    iommu_gas_match_one(a, curr->end, first->first,
-		    0, addr))
+		    0, addr)) {
+			RB_INSERT_NEXT(iommu_gas_entries_tree,
+			    &domain->rb_root, curr, a->entry);
 			return (0);
+		}
 	}
 
 	/*
@@ -481,17 +474,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a)
 	 * Walk the remaining big-enough ranges until one satisfies alignment
 	 * requirements.
 	 */
-	domain = a->domain;
 	for (curr = first; curr != NULL;
 	    curr = iommu_gas_next(curr, min_free)) {
 		if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
 		    iommu_gas_match_one(a, first->last, curr->start,
-		    addr + 1, domain->end))
+		    addr + 1, domain->end)) {
+			RB_INSERT_PREV(iommu_gas_entries_tree,
+			    &domain->rb_root, curr, a->entry);
 			return (0);
+		}
 		if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
 		    iommu_gas_match_one(a, curr->end, first->first,
-		    addr + 1, domain->end))
+		    addr + 1, domain->end)) {
+			RB_INSERT_NEXT(iommu_gas_entries_tree,
+			    &domain->rb_root, curr, a->entry);
 			return (0);
+		}
 	}
 
 	return (ENOMEM);
@@ -502,7 +500,6 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr
     u_int flags)
 {
 	struct iommu_map_entry *next, *prev;
-	bool found __diagused;
 
 	IOMMU_DOMAIN_ASSERT_LOCKED(domain);
 
@@ -550,14 +547,13 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr
 		iommu_gas_rb_remove(domain, prev);
 		prev = NULL;
 	}
+	RB_INSERT_PREV(iommu_gas_entries_tree,
+	    &domain->rb_root, next, entry);
 	if (next->start < entry->end) {
 		iommu_gas_rb_remove(domain, next);
 		next = NULL;
 	}
 
-	found = iommu_gas_rb_insert(domain, entry);
-	KASSERT(found, ("found RMRR dup %p start %jx end %jx",
-	    domain, (uintmax_t)entry->start, (uintmax_t)entry->end));
 	if ((flags & IOMMU_MF_RMRR) != 0)
 		entry->flags = IOMMU_MAP_ENTRY_RMRR;
 
@@ -647,7 +643,8 @@ iommu_gas_remove_clip_left(struct iommu_domain *domain, iommu_gaddr_t start,
 	*res = *entry;
 	res->start = entry->end = start;
 	RB_UPDATE_AUGMENT(entry, rb_entry);
-	iommu_gas_rb_insert(domain, res);
+	RB_INSERT_NEXT(iommu_gas_entries_tree,
+	    &domain->rb_root, entry, res);
 	return (res);
 }
 
@@ -662,7 +659,8 @@ iommu_gas_remove_clip_right(struct iommu_domain *domain,
 	*r = *entry;
 	r->end = entry->start = end;
 	RB_UPDATE_AUGMENT(entry, rb_entry);
-	iommu_gas_rb_insert(domain, r);
+	RB_INSERT_PREV(iommu_gas_entries_tree,
+	    &domain->rb_root, entry, r);
 	return (true);
 }
 
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 47cd14d6691b..7aa00bd53fd7 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -414,12 +414,15 @@ struct {								\
 	RB_PROTOTYPE_RANK(name, type, attr)				\
 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_INSERT_FINISH(name, type, attr);			\
 	RB_PROTOTYPE_INSERT(name, type, attr);				\
 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
 	RB_PROTOTYPE_FIND(name, type, attr);				\
 	RB_PROTOTYPE_NFIND(name, type, attr);				\
 	RB_PROTOTYPE_NEXT(name, type, attr);				\
+	RB_PROTOTYPE_INSERT_NEXT(name, type, attr);			\
 	RB_PROTOTYPE_PREV(name, type, attr);				\
+	RB_PROTOTYPE_INSERT_PREV(name, type, attr);			\
 	RB_PROTOTYPE_MINMAX(name, type, attr);				\
 	RB_PROTOTYPE_REINSERT(name, type, attr);
 #ifdef _RB_DIAGNOSTIC
@@ -436,6 +439,9 @@ struct {								\
 	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\
 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr)			\
+	attr struct type *name##_RB_INSERT_FINISH(struct name *,	\
+	    struct type *, struct type **, struct type *)
 #define RB_PROTOTYPE_INSERT(name, type, attr)				\
 	attr struct type *name##_RB_INSERT(struct name *, struct type *)
 #define RB_PROTOTYPE_FIND(name, type, attr)				\
@@ -444,8 +450,14 @@ struct {								\
 	attr struct type *name##_RB_NFIND(struct name *, struct type *)
 #define RB_PROTOTYPE_NEXT(name, type, attr)				\
 	attr struct type *name##_RB_NEXT(struct type *)
+#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr)			\
+	attr struct type *name##_RB_INSERT_NEXT(struct name *,		\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_PREV(name, type, attr)				\
 	attr struct type *name##_RB_PREV(struct type *)
+#define RB_PROTOTYPE_INSERT_PREV(name, type, attr)			\
+	attr struct type *name##_RB_INSERT_PREV(struct name *,		\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_MINMAX(name, type, attr)				\
 	attr struct type *name##_RB_MINMAX(struct name *, int)
 #define RB_PROTOTYPE_REINSERT(name, type, attr)			\
@@ -462,12 +474,15 @@ struct {								\
 	RB_GENERATE_RANK(name, type, field, attr)			\
 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+	RB_GENERATE_INSERT_FINISH(name, type, field, attr)		\
 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 	RB_GENERATE_REMOVE(name, type, field, attr)			\
 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
 	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
 	RB_GENERATE_NEXT(name, type, field, attr)			\
+	RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)		\
 	RB_GENERATE_PREV(name, type, field, attr)			\
+	RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)		\
 	RB_GENERATE_MINMAX(name, type, field, attr)			\
 	RB_GENERATE_REINSERT(name, type, field, cmp, attr)
 
@@ -556,7 +571,7 @@ name##_RB_INSERT_COLOR(struct name *head,				\
 			 * other edge lengths based on the downward	\
 			 * edges from 'child'.				\
 			 *						\
-			 *	     par		 par		\ 
+			 *	     par		 par		\
 			 *	    /	\		/   \		\
 			 *	  elm	 z	       /     z		\
 			 *	 /  \		     child		\
@@ -587,7 +602,7 @@ name##_RB_INSERT_COLOR(struct name *head,				\
 		 * 'parent' a child of 'child', then make both edges	\
 		 * of 'child' short to rebalance.			\
 		 *							\
-		 *	     par		 child			\ 
+		 *	     par		 child			\
 		 *	    /	\		/     \			\
 		 *	   /	 z	       x       par		\
 		 *	child			      /	  \		\
@@ -800,6 +815,29 @@ name##_RB_REMOVE(struct name *head, struct type *out)			\
 	return (out);							\
 }
 
+#define RB_GENERATE_INSERT_FINISH(name, type, field, attr)		\
+/* Inserts a node into the RB tree */					\
+attr struct type *							\
+name##_RB_INSERT_FINISH(struct name *head, struct type *parent,		\
+    struct type **pptr, struct type *elm)				\
+{									\
+	struct type *tmp = NULL;					\
+									\
+	RB_SET(elm, parent, field);					\
+	*pptr = elm;							\
+	if (parent != NULL)						\
+		tmp = name##_RB_INSERT_COLOR(head, parent, elm);	\
+	_RB_AUGMENT_WALK(elm, tmp, field);				\
+	if (tmp != NULL)						\
+		/*							\
+		 * An element rotated into the search path has a	\
+		 * changed subtree, so update augmentation for it if	\
+		 * AUGMENT_WALK didn't.					\
+		 */							\
+		(void)RB_AUGMENT_CHECK(tmp);				\
+	return (NULL);							\
+}
+
 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 /* Inserts a node into the RB tree */					\
 attr struct type *							\
@@ -819,19 +857,7 @@ name##_RB_INSERT(struct name *head, struct type *elm)			\
 		else							\
 			return (parent);				\
 	}								\
-	RB_SET(elm, parent, field);					\
-	*tmpp = elm;							\
-	if (parent != NULL)						\
-		tmp = name##_RB_INSERT_COLOR(head, parent, elm);	\
-	_RB_AUGMENT_WALK(elm, tmp, field);				\
-	if (tmp != NULL)						\
-		/*							\
-		 * An element rotated into the search path has a	\
-		 * changed subtree, so update augmentation for it if	\
-		 * AUGMENT_WALK didn't.					\
-		 */							\
-		(void)RB_AUGMENT_CHECK(tmp);				\
-	return (NULL);							\
+	return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm));	\
 }
 
 #define RB_GENERATE_FIND(name, type, field, cmp, attr)			\
@@ -893,6 +919,33 @@ name##_RB_NEXT(struct type *elm)					\
 	return (elm);							\
 }
 
+#if defined(_KERNEL) && defined(DIAGNOSTIC)
+#define _RB_ORDER_CHECK(lo, hi) do {					\
+	KASSERT(cmp(lo, hi) < 0, "out of order insertion");		\
+} while (0)
+#else
+#define _RB_ORDER_CHECK(elm, next) do {} while (0)
+#endif
+
+#define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)		\
+/* Inserts a node into the next position in the RB tree */		\
+attr struct type *							\
+name##_RB_INSERT_NEXT(struct name *head,				\
+    struct type *elm, struct type *next)				\
+{									\
+	struct type *tmp;						\
+	struct type **tmpp = &RB_RIGHT(elm, field);			\
+									\
+	_RB_ORDER_CHECK(elm, next);					\
+	if (name##_RB_NEXT(elm) != NULL)				\
+		_RB_ORDER_CHECK(next, name##_RB_NEXT(elm));		\
+	while ((tmp = *tmpp) != NULL) {					\
+		elm = tmp;						\
+		tmpp = &RB_LEFT(elm, field);				\
+	}								\
+	return (name##_RB_INSERT_FINISH(head, elm, tmpp, next));	\
+}
+
 #define RB_GENERATE_PREV(name, type, field, attr)			\
 /* ARGSUSED */								\
 attr struct type *							\
@@ -911,6 +964,25 @@ name##_RB_PREV(struct type *elm)					\
 	return (elm);							\
 }
 
+#define RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)		\
+/* Inserts a node into the prev position in the RB tree */		\
+attr struct type *							\
+name##_RB_INSERT_PREV(struct name *head,				\
+    struct type *elm, struct type *prev)				\
+{									\
+	struct type *tmp;						\
+	struct type **tmpp = &RB_LEFT(elm, field);			\
+									\
+	_RB_ORDER_CHECK(prev, elm);					\
+	if (name##_RB_PREV(elm) != NULL)				\
+		_RB_ORDER_CHECK(name##_RB_PREV(elm), prev);		\
+	while ((tmp = *tmpp) != NULL) {					\
+		elm = tmp;						\
+		tmpp = &RB_RIGHT(elm, field);				\
+	}								\
+	return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev));	\
+}
+
 #define RB_GENERATE_MINMAX(name, type, field, attr)			\
 attr struct type *							\
 name##_RB_MINMAX(struct name *head, int val)				\
@@ -947,6 +1019,8 @@ name##_RB_REINSERT(struct name *head, struct type *elm)			\
 #define RB_INF	1
 
 #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
+#define RB_INSERT_NEXT(name, x, y, z)	name##_RB_INSERT_NEXT(x, y, z)
+#define RB_INSERT_PREV(name, x, y, z)	name##_RB_INSERT_PREV(x, y, z)
 #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
 #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
 #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)