Re: [PATCH] rbtree: fix the red root

[Joey Pabalinas <joeypabalinas@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1815 bytes --]

On Fri, Jan 11, 2019 at 09:31:32AM -0800, Matthew Wilcox wrote:
> On Fri, Jan 11, 2019 at 11:51:45AM -0500, Qian Cai wrote:
> > Reported-by: Esme <esploit@protonmail.ch>
> > Signed-off-by: Qian Cai <cai@lca.pw>
> 
> What change introduced this bug?  We need a Fixes: line so the stable
> people know how far to backport this fix.
> 

Breaking commit _might_ be 5bc9188aa207dafd47 (rbtree: low level optimizations in rb_insert_color())

I'm thinking that the when `parent = rb_parent(node);` was
moved from the beginning of the loop to the function initialization
only, somehow parent not being reassigned every loop resulted in
the red root node case.

I'm sort of just guessing here admittedly and I'll do some testing after
breakfast, but nothing else in the `git log` or `git blame` changes really
jumps out at me apart from this one commit.

 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-       struct rb_node *parent, *gparent;
+       struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

        while (true) {
                /*
                 * Loop invariant: node is red
                 *
                 * If there is a black parent, we are done.
                 * Otherwise, take some corrective action as we don't
                 * want a red root or two consecutive red nodes.
                 */
-               parent = rb_parent(node);
                if (!parent) {
-                       rb_set_black(node);
+                       rb_set_parent_color(node, NULL, RB_BLACK);
                        break;
                } else if (rb_is_black(parent))
                        break;

-               gparent = rb_parent(parent);
+               gparent = rb_red_parent(parent);

-- 
Cheers,
Joey Pabalinas

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]