linux-kernel - Re: [PATCH v2] 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]

Message-ID: <20190111231652.GN6310@bombadil.infradead.org>
Date:   Fri, 11 Jan 2019 15:16:52 -0800
From:   Matthew Wilcox <willy@...radead.org>
To:     Qian Cai <cai@....pw>
Cc:     akpm@...ux-foundation.org, esploit@...tonmail.ch,
        jejb@...ux.ibm.com, dgilbert@...erlog.com,
        martin.petersen@...cle.com, joeypabalinas@...il.com,
        walken@...gle.com, linux-mm@...ck.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] rbtree: fix the red root

On Fri, Jan 11, 2019 at 03:58:43PM -0500, Qian Cai wrote:
> diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
> index b7055b2a07d3..afad0213a117 100644
> --- a/lib/rbtree_test.c
> +++ b/lib/rbtree_test.c
> @@ -345,6 +345,17 @@ static int __init rbtree_test_init(void)
>  		check(0);
>  	}
>  
> +	/*
> +	 * a little regression test to catch a bug may be introduced by
> +	 * 6d58452dc06 (rbtree: adjust root color in rb_insert_color() only when
> +	 * necessary)
> +	 */
> +	insert(nodes, &root);
> +	nodes->rb.__rb_parent_color = RB_RED;
> +	insert(nodes + 1, &root);
> +	erase(nodes + 1, &root);
> +	erase(nodes, &root);

That's not a fair test!  You're poking around in the data structure to
create the situation.  This test would have failed before 6d58452dc06 too.
How do we create a tree that has a red parent at root, only using insert()
and erase()?