Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Thu, 30 Apr 2020 09:28:47 +0200
From:   Juri Lelli <juri.lelli@redhat.com>
To:     Peter Zijlstra <peterz@infradead.org>
Cc:     linux-kernel@vger.kernel.org, walken@google.com, dave@stgolabs.net,
        mingo@kernel.org, tglx@linutronix.de, oleg@redhat.com,
        irogers@google.com, vincent.guittot@linaro.org
Subject: Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers
Message-ID: <20200430072847.GA68379@localhost.localdomain>
References: <20200429153258.563269446@infradead.org>
 <20200429153549.006661686@infradead.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20200429153549.006661686@infradead.org>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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@infradead.org>
> ---
>  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