linux-kernel - Re: [PATCH] rbtree: fix the red root

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]

Date:   Fri, 11 Jan 2019 07:53:03 -1000
From:   Joey Pabalinas <joeypabalinas@...il.com>
To:     Matthew Wilcox <willy@...radead.org>
Cc:     Qian Cai <cai@....pw>, akpm@...ux-foundation.org,
        esploit@...tonmail.ch, jejb@...ux.ibm.com, dgilbert@...erlog.com,
        martin.petersen@...cle.com, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org,
        Joey Pabalinas <joeypabalinas@...il.com>
Subject: Re: [PATCH] rbtree: fix the red root

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@...tonmail.ch>
> > Signed-off-by: Qian Cai <cai@....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

Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)