Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

[Juri Lelli]

Hi,

On 29/04/20 17:32, Peter Zijlstra wrote:
> I've always been bothered by the endless (fragile) boilerplate for
> rbtree, and I recently wrote some rbtree helpers for objtool and
> figured I should lift them into the kernel and use them more widely.
> 
> Provide:
> 
> partial-order; less() based:
>  - rb_add(): add a new entry to the rbtree
>  - rb_add_cached(): like rb_add(), but for a rb_root_cached
> 
> total-order; cmp() based:
>  - rb_find(): find an entry in an rbtree
>  - rb_find_first(): find the first (leftmost) matching entry
>  - rb_next_match(): continue from rb_find_first()
>  - rb_for_each(): for loop with rb_find_first() / rb_next_match()
> 
> Also make rb_add_cached() / rb_erase_cached() return true when
> leftmost.
> 
> Inlining and constant propagation should see the compiler inline the
> whole thing, including the various compare functions.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
> ---
>  include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
>  tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
>  tools/objtool/elf.c          |   63 ++-------------------
>  3 files changed, 257 insertions(+), 62 deletions(-)
> 
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
>  	rb_insert_color(node, &root->rb_root);
>  }
>  
> -static inline void rb_erase_cached(struct rb_node *node,
> +static inline bool rb_erase_cached(struct rb_node *node,
>  				   struct rb_root_cached *root)
>  {
> -	if (root->rb_leftmost == node)
> +	bool leftmost = false;
> +
> +	if (root->rb_leftmost == node) {
>  		root->rb_leftmost = rb_next(node);

Think we need

 if (root->rb_leftmost)

> +		leftmost = true;

DEADLINE crashes w/o that.

> +	}
>  	rb_erase(node, &root->rb_root);
> +
> +	return leftmost;
>  }

The rest looks good to me.

Thanks,

Juri