Date: Fri, 14 Apr 2017 11:34:17 +0200
From: Alexandru Moise <00moses.alexander00@gmail.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: linux-kernel@vger.kernel.org, akpm@linux-foundation.org,
        dhowells@redhat.com, keescook@chromium.org, fykcee1@gmail.com
Subject: Re: Question regarding Linux implementation of rbtrees
Message-ID: <20170414093417.GA8306@gmail.com>
References: <20170413222455.GA15239@gmail.com>
 <20170414085132.w6vwx6gqwrdrnx3x@hirez.programming.kicks-ass.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20170414085132.w6vwx6gqwrdrnx3x@hirez.programming.kicks-ass.net>
User-Agent: Mutt/1.8.1 (2017-04-11)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1839
Lines: 45

On Fri, Apr 14, 2017 at 10:51:32AM +0200, Peter Zijlstra wrote:
> 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.

Now I've read it again and realized that it's actually in rb_parent() that
the bit gets cleared and all rb_set_parent_color() does is assign the new
pointer cast to ulong to the node's color. I was expecting that the bit would be cleared
in rb_set_parent_color().

Sorry for the noise.

../Alex