LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Michel Lespinasse <walken@google.com>
To: David Lechner <david@lechnology.com>
Cc: Qian Cai <cai@lca.pw>, Andrew Morton <akpm@linux-foundation.org>,
	esploit@protonmail.ch, jejb@linux.ibm.com, dgilbert@interlog.com,
	martin.petersen@oracle.com, joeypabalinas@gmail.com,
	linux-mm <linux-mm@kvack.org>,
	LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] rbtree: fix the red root
Date: Fri, 11 Jan 2019 18:58:33 -0800
Message-ID: <CANN689G0zbk7sMbQ+p9NQGQ=NWq-Q0mQOOjeFkLp19YrTfgcLg@mail.gmail.com> (raw)
In-Reply-To: <a783f23d-77ab-a7d3-39d1-4008d90094c3@lechnology.com>

On Fri, Jan 11, 2019 at 3:47 PM David Lechner <david@lechnology.com> wrote:
>
> On 1/11/19 2:58 PM, Qian Cai wrote:
> > A GPF 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; <-- GPF was 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 (the root can't be red) and need a fix
> > up, and also add a regression test for it. This looks like was
> > introduced by 6d58452dc06 where it no longer always paint the root as
> > black.
> >
> > Fixes: 6d58452dc06 (rbtree: adjust root color in rb_insert_color() only
> > when necessary)
> > Reported-by: Esme <esploit@protonmail.ch>
> > Tested-by: Joey Pabalinas <joeypabalinas@gmail.com>
> > Signed-off-by: Qian Cai <cai@lca.pw>
> > ---
>
> Tested-by: David Lechner <david@lechnology.com>
> FWIW, this fixed the following crash for me:
>
> Unable to handle kernel NULL pointer dereference at virtual address 00000004

Just to clarify, do you have a way to reproduce this crash without the fix ?

I don't think the fix is correct, because it just silently ignores a
corrupted rbtree (red root node). But the code that creates this
situation certainly needs to be fixed - having a reproduceable test
case would certainly help here.

Regarding 6d58452dc06, the reasoning was that this code expects to be
called after inserting a new (red) leaf into an rbtree that had all of
its data structure invariants satisfied. So in this context, it should
not be necessary to always reset the root to black, as this should
already be the case...

  reply index

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <YrcPMrGmYbPe_xgNEV6Q0jqc5XuPYmL2AFSyeNmg1gW531bgZnBGfEUK5_ktqDBaNW37b-NP2VXvlliM7_PsBRhSfB649MaW1Ne7zT9lHc=@protonmail.ch>
2019-01-11 16:51 ` [PATCH] " Qian Cai
2019-01-11 17:17   ` Joey Pabalinas
2019-01-11 17:31   ` Matthew Wilcox
2019-01-11 17:53     ` Joey Pabalinas
2019-01-11 18:12     ` Qian Cai
2019-01-11 18:16       ` Matthew Wilcox
2019-01-11 20:58         ` [PATCH v2] " Qian Cai
2019-01-11 23:16           ` Matthew Wilcox
2019-01-12  0:18             ` Qian Cai
2019-01-12  0:39               ` Esme
2019-01-11 23:47           ` David Lechner
2019-01-12  2:58             ` Michel Lespinasse [this message]
2019-01-14  2:20               ` David Lechner
2019-01-14  2:33                 ` Qian Cai
2019-01-14  3:07                   ` Esme
2019-01-14  3:52                     ` Douglas Gilbert
2019-01-14  3:59                       ` Esme
2019-01-14  4:52                         ` Douglas Gilbert
2019-01-14  6:23                           ` Esme
2019-01-14 15:45                             ` Qian Cai
2019-01-14 15:51                               ` Esme
2019-01-14 17:58                                 ` Qian Cai
2019-01-14 18:26                                   ` Douglas Gilbert
2019-01-15  5:31                             ` Qian Cai
2019-01-16 14:37                               ` Esme
2019-01-18 17:10                                 ` Qian Cai

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CANN689G0zbk7sMbQ+p9NQGQ=NWq-Q0mQOOjeFkLp19YrTfgcLg@mail.gmail.com' \
    --to=walken@google.com \
    --cc=akpm@linux-foundation.org \
    --cc=cai@lca.pw \
    --cc=david@lechnology.com \
    --cc=dgilbert@interlog.com \
    --cc=esploit@protonmail.ch \
    --cc=jejb@linux.ibm.com \
    --cc=joeypabalinas@gmail.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=martin.petersen@oracle.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org linux-kernel@archiver.kernel.org
	public-inbox-index lkml


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/ public-inbox