LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Joey Pabalinas <joeypabalinas@gmail.com>
To: Matthew Wilcox <willy@infradead.org>
Cc: Qian Cai <cai@lca.pw>,
	akpm@linux-foundation.org, esploit@protonmail.ch,
	jejb@linux.ibm.com, dgilbert@interlog.com,
	martin.petersen@oracle.com, linux-mm@kvack.org,
	linux-kernel@vger.kernel.org,
	Joey Pabalinas <joeypabalinas@gmail.com>
Subject: Re: [PATCH] rbtree: fix the red root
Date: Fri, 11 Jan 2019 07:53:03 -1000
Message-ID: <20190111175303.72a43mdulvfd6wf3@gmail.com> (raw)
In-Reply-To: <20190111173132.GH6310@bombadil.infradead.org>

[-- 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 --]

  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 ` Qian Cai
2019-01-11 17:17   ` Joey Pabalinas
2019-01-11 17:31   ` Matthew Wilcox
2019-01-11 17:53     ` Joey Pabalinas [this message]
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
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=20190111175303.72a43mdulvfd6wf3@gmail.com \
    --to=joeypabalinas@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=cai@lca.pw \
    --cc=dgilbert@interlog.com \
    --cc=esploit@protonmail.ch \
    --cc=jejb@linux.ibm.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=martin.petersen@oracle.com \
    --cc=willy@infradead.org \
    /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