rbtree: fix the red root
diff mbox series

Message ID 20190111165145.23628-1-cai@lca.pw
State New
Headers show
Series
  • rbtree: fix the red root
Related show

Commit Message

Qian Cai Jan. 11, 2019, 4:51 p.m. UTC
A GFP was reported,

kasan: CONFIG_KASAN_INLINE enabled
kasan: GPF could be caused by NULL-ptr deref or user memory access
general protection fault: 0000 [#1] SMP KASAN
        kasan_die_handler.cold.22+0x11/0x31
        notifier_call_chain+0x17b/0x390
        atomic_notifier_call_chain+0xa7/0x1b0
        notify_die+0x1be/0x2e0
        do_general_protection+0x13e/0x330
        general_protection+0x1e/0x30
        rb_insert_color+0x189/0x1480
        create_object+0x785/0xca0
        kmemleak_alloc+0x2f/0x50
        kmem_cache_alloc+0x1b9/0x3c0
        getname_flags+0xdb/0x5d0
        getname+0x1e/0x20
        do_sys_open+0x3a1/0x7d0
        __x64_sys_open+0x7e/0xc0
        do_syscall_64+0x1b3/0x820
        entry_SYSCALL_64_after_hwframe+0x49/0xbe

It turned out,

gparent = rb_red_parent(parent);
tmp = gparent->rb_right; <-- GFP triggered here.

Apparently, "gparent" is NULL which indicates "parent" is rbtree's root
which is red. Otherwise, it will be treated properly a few lines above.

/*
 * If there is a black parent, we are done.
 * Otherwise, take some corrective action as,
 * per 4), we don't want a red root or two
 * consecutive red nodes.
 */
if(rb_is_black(parent))
	break;

Hence, it violates the rule #1 and need a fix up.

Reported-by: Esme <esploit@protonmail.ch>
Signed-off-by: Qian Cai <cai@lca.pw>
---
 lib/rbtree.c | 7 +++++++
 1 file changed, 7 insertions(+)

Comments

Joey Pabalinas Jan. 11, 2019, 5:17 p.m. UTC | #1
On Fri, Jan 11, 2019 at 11:51:45AM -0500, Qian Cai wrote:
> A GFP was reported,
> 
> kasan: CONFIG_KASAN_INLINE enabled
> kasan: GPF could be caused by NULL-ptr deref or user memory access
> general protection fault: 0000 [#1] SMP KASAN
>         kasan_die_handler.cold.22+0x11/0x31
>         notifier_call_chain+0x17b/0x390
>         atomic_notifier_call_chain+0xa7/0x1b0
>         notify_die+0x1be/0x2e0
>         do_general_protection+0x13e/0x330
>         general_protection+0x1e/0x30
>         rb_insert_color+0x189/0x1480
>         create_object+0x785/0xca0
>         kmemleak_alloc+0x2f/0x50
>         kmem_cache_alloc+0x1b9/0x3c0
>         getname_flags+0xdb/0x5d0
>         getname+0x1e/0x20
>         do_sys_open+0x3a1/0x7d0
>         __x64_sys_open+0x7e/0xc0
>         do_syscall_64+0x1b3/0x820
>         entry_SYSCALL_64_after_hwframe+0x49/0xbe
> 
> It turned out,
> 
> gparent = rb_red_parent(parent);
> tmp = gparent->rb_right; <-- GFP triggered here.
> 
> Apparently, "gparent" is NULL which indicates "parent" is rbtree's root
> which is red. Otherwise, it will be treated properly a few lines above.

Good catch, acked. After thinking through the logic a bit your solution
seems like the simplest fix.

Now, I didn't do _extensive_ testing but a quick compile and bootup of
the patch with CONFIG_KASAN_INLINE enabled has yet to throw any GFPs,
so take that as you will.

Reviewed-by: Joey Pabalinas <joeypabalinas@gmail.com>
Tested-by: Joey Pabalinas <joeypabalinas@gmail.com>

> /*
>  * If there is a black parent, we are done.
>  * Otherwise, take some corrective action as,
>  * per 4), we don't want a red root or two
>  * consecutive red nodes.
>  */
> if(rb_is_black(parent))
> 	break;
> 
> Hence, it violates the rule #1 and need a fix up.
> 
> Reported-by: Esme <esploit@protonmail.ch>
> Signed-off-by: Qian Cai <cai@lca.pw>
> ---
>  lib/rbtree.c | 7 +++++++
>  1 file changed, 7 insertions(+)
> 
> diff --git a/lib/rbtree.c b/lib/rbtree.c
> index d3ff682fd4b8..acc969ad8de9 100644
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -127,6 +127,13 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
>  			break;
>  
>  		gparent = rb_red_parent(parent);
> +		if (unlikely(!gparent)) {
> +			/*
> +			 * The root is red so correct it.
> +			 */
> +			rb_set_parent_color(parent, NULL, RB_BLACK);
> +			break;
> +		}
>  
>  		tmp = gparent->rb_right;
>  		if (parent != tmp) {	/* parent == gparent->rb_left */
> -- 
> 2.17.2 (Apple Git-113)
>
Matthew Wilcox Jan. 11, 2019, 5:31 p.m. UTC | #2
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.
Joey Pabalinas Jan. 11, 2019, 5:53 p.m. UTC | #3
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);
Qian Cai Jan. 11, 2019, 6:12 p.m. UTC | #4
On Fri, 2019-01-11 at 09:31 -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.

It looks like,

Fixes: 6d58452dc06 (rbtree: adjust root color in rb_insert_color() only when
necessary)

where it no longer always paint the root as black.

Also, copying this fix for the original author and reviewer.

https://lore.kernel.org/lkml/20190111165145.23628-1-cai@lca.pw/
Matthew Wilcox Jan. 11, 2019, 6:16 p.m. UTC | #5
On Fri, Jan 11, 2019 at 01:12:36PM -0500, Qian Cai wrote:
> On Fri, 2019-01-11 at 09:31 -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.
> 
> It looks like,
> 
> Fixes: 6d58452dc06 (rbtree: adjust root color in rb_insert_color() only when
> necessary)
> 
> where it no longer always paint the root as black.
> 
> Also, copying this fix for the original author and reviewer.
> 
> https://lore.kernel.org/lkml/20190111165145.23628-1-cai@lca.pw/

Great, thanks!  We have a test-suite (lib/rbtree_test.c); could you add
a test to it that will reproduce this bug without your patch applied?

Patch
diff mbox series

diff --git a/lib/rbtree.c b/lib/rbtree.c
index d3ff682fd4b8..acc969ad8de9 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -127,6 +127,13 @@  __rb_insert(struct rb_node *node, struct rb_root *root,
 			break;
 
 		gparent = rb_red_parent(parent);
+		if (unlikely(!gparent)) {
+			/*
+			 * The root is red so correct it.
+			 */
+			rb_set_parent_color(parent, NULL, RB_BLACK);
+			break;
+		}
 
 		tmp = gparent->rb_right;
 		if (parent != tmp) {	/* parent == gparent->rb_left */