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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200430072847.GA68379@localhost.localdomain>
Date:   Thu, 30 Apr 2020 09:28:47 +0200
From:   Juri Lelli <juri.lelli@...hat.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, walken@...gle.com, dave@...olabs.net,
        mingo@...nel.org, tglx@...utronix.de, oleg@...hat.com,
        irogers@...gle.com, vincent.guittot@...aro.org
Subject: Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

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@...radead.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