git: deeaf9c4d85d - stable/13 - rb_tree: pass parent to RB_INSERT_COLOR

The branch stable/13 has been updated by dougm:

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

commit deeaf9c4d85d937d3c935291e913ae614a28f824
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-09-13 06:11:47 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-10-12 02:42:55 +0000

    rb_tree: pass parent to RB_INSERT_COLOR
    
    Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up
    a value already available. Make adjustments to a linux rbtree header,
    which invokes it.
    
    Reviewed by:    alc, hselasky
    Differential Revision:  https://reviews.freebsd.org/D36114
    
    (cherry picked from commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f)
---
 sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++++++++---
 sys/sys/tree.h                                    | 18 ++++++++++--------
 2 files changed, 18 insertions(+), 11 deletions(-)

diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
index 1f337d59545c..37537d4b2724 100644
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -74,8 +74,11 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
 #define RB_EMPTY_NODE(node)     (RB_PARENT(node, __entry) == node)
 #define RB_CLEAR_NODE(node)     RB_SET_PARENT(node, node, __entry)
 
-#define	rb_insert_color(node, root)					\
-	linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
+#define rb_insert_color(node, root) do {				\
+	if (rb_parent(node))						\
+		linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \
+		    rb_parent(node), (node));				\
+} while (0)
 #define	rb_erase(node, root)						\
 	linux_root_RB_REMOVE((struct linux_root *)(root), (node))
 #define	rb_next(node)	RB_NEXT(linux_root, NULL, (node))
@@ -145,7 +148,9 @@ static inline void
 rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
     bool leftmost)
 {
-	linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
+	if (rb_parent(node))
+		linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root,
+		    rb_parent(node), node);
 	if (leftmost)
 		root->rb_leftmost = node;
 }
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 6a64498f6deb..c0cd65f41acb 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -422,7 +422,8 @@ struct {								\
 #define RB_PROTOTYPE_RANK(name, type, attr)
 #endif
 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
-	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
+	attr void name##_RB_INSERT_COLOR(struct name *,			\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
 	attr void name##_RB_REMOVE_COLOR(struct name *,			\
 	    struct type *, struct type *)
@@ -491,7 +492,8 @@ name##_RB_RANK(struct type *elm)					\
 
 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 attr void								\
-name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+name##_RB_INSERT_COLOR(struct name *head,				\
+    struct type *parent, struct type *elm)				\
 {									\
 	/*								\
 	 * Initially, elm is a leaf.  Either its parent was previously	\
@@ -503,12 +505,11 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 	 * uninitialized 'child', and a later iteration can only happen \
 	 * when a value has been assigned to 'child' in the previous    \
 	 * one.								\
-	 */							\
-	struct type *child, *child_up, *gpar, *parent;			\
+	 */								\
+	struct type *child, *child_up, *gpar;				\
 	__uintptr_t elmdir, sibdir;					\
 									\
-	gpar = _RB_UP(elm, field);					\
-	while ((parent = gpar) != NULL) {				\
+	do {								\
 		/* the rank of the tree rooted at elm grew */		\
 		gpar = _RB_UP(parent, field);				\
 		elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
@@ -584,7 +585,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 			RB_AUGMENT(elm);				\
 		RB_AUGMENT(parent);					\
 		break;							\
-	}								\
+	} while ((parent = gpar) != NULL);				\
 }
 
 #ifndef RB_STRICT_HST
@@ -774,7 +775,8 @@ name##_RB_INSERT(struct name *head, struct type *elm)			\
 	}								\
 	RB_SET(elm, parent, field);					\
 	*tmpp = elm;							\
-	name##_RB_INSERT_COLOR(head, elm);				\
+	if (parent != NULL)						\
+		name##_RB_INSERT_COLOR(head, parent, elm);		\
 	RB_UPDATE_AUGMENT(elm, field);					\
 	return (NULL);							\
 }