linux-kernel - Re: Question regarding Linux implementation of rbtrees

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: <20170414085132.w6vwx6gqwrdrnx3x@hirez.programming.kicks-ass.net>
Date:   Fri, 14 Apr 2017 10:51:32 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Alexandru Moise <00moses.alexander00@...il.com>
Cc:     linux-kernel@...r.kernel.org, akpm@...ux-foundation.org,
        dhowells@...hat.com, keescook@...omium.org, fykcee1@...il.com
Subject: Re: Question regarding Linux implementation of rbtrees

On Fri, Apr 14, 2017 at 12:24:55AM +0200, Alexandru Moise wrote:
> Seeing as RB_RED is defined to be 0 in include/linux/rbtree_augmented.h
> A call of this form: rb_set_parent_color(node, parent, RB_RED);
> as seen in __rb_insert would only end up reassigning the parent "color"
> (which is the parent pointer value cast to unsigned long) OR'd with 0.
> Which would mean that nothing would really change regarding the parent's
> "color". So, that would lead one to think that the diagram at case 2 showing
> the grandparent's color going from black to red could not be completely accurate
> as the Linux implementation presently stands.
> 
> Could the maintainers provide an answer as to why the below patch is the
> __wrong__ thing to do? Apart from the obvious "the values of the macros
> might change in the future".
> 
> Thanks,
> ../Alex
> ---
>  lib/rbtree.c | 4 ----
>  1 file changed, 4 deletions(-)
> 
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index 4ba2828a67c0..6b540be4dda4 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -135,7 +135,6 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
>  				rb_set_parent_color(parent, gparent, RB_BLACK);
>  				node = gparent;
>  				parent = rb_parent(node);
> -				rb_set_parent_color(node, parent, RB_RED);
>  				continue;
>  			}
>  

So who would clear the bit then? The point here is (IIRC) that node is
black and needs to become red.