| Message ID | 20190111165145.23628-1-cai@lca.pw (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | rbtree: fix the red root | expand |
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) >
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.
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);
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/
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?
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 */
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(+)