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

 Hello Doug,

On Wed, 12 Oct 2022 03:00:23 GMT
Doug Moore <dougm@FreeBSD.org> wrote:

> 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);							\
>  }

 This breaks drm-kmod for stable/13
 So it means that drm-kmod compiled for 13.1 will not work (either
won't load or more likely freeze the machine) on stable/13 and more
importantly 13.2
 We've succefully succeeded in keeping compatibility between 13.0 and
13.1 for drm-kmod and I'd really like that it also works on 13.2

 Cheers,

-- 
Emmanuel Vadot <manu@bidouilliste.com> <manu@freebsd.org>