linux-kernel - Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry

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: <5278C2F8.3050805@linux.vnet.ibm.com>
Date:	Tue, 05 Nov 2013 02:05:44 -0800
From:	Cody P Schafer <cody@...ux.vnet.ibm.com>
To:	Andrew Morton <akpm@...ux-foundation.org>, Jan Kara <jack@...e.cz>
CC:	Andreas Dilger <adilger.kernel@...ger.ca>,
	LKML <linux-kernel@...r.kernel.org>,
	EXT4 <linux-ext4@...r.kernel.org>,
	Cody P Schafer <cody@...ux.vnet.ibm.com>
Subject: Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node
 is not the first element in an entry

On 11/04/2013 05:40 PM, Cody P Schafer wrote:
> Provide a new helper called rb_next_postorder_entry() to perform NULL
> checks and container_of() coversions and use it in
> rbtree_for_each_entry_safe() to fix oopses that occur when rb_node is
> not the first element in the entry.

On second thought, it appears I was a bit to hasty with this, and this patch actually breaks things.

On 11/04/2013 04:45 PM, Jan Kara wrote:> On Mon 04-11-13 15:26:38, Jan Kara wrote:
>> On Fri 01-11-13 15:38:50, Cody P Schafer wrote:
>>> Use rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead
>>> of opencoding an alternate postorder iteration that modifies the tree
>>    Thanks. I've merged the patch into my tree.
>    Hum, except that the kernel oopses with this patch. And I think the
> problem is in rbtree_postorder_for_each_entry_safe(). How are those tests
> for NULL supposed to work? For example if the tree is empty, 'pos' will be
> NULL and you'll call rb_next_postorder(&NULL->field) which is pretty much
> guaranteed to oops if 'field' doesn't have offset 0 in the structure...

No, it shouldn't oops because pos won't be NULL, &pos->field will be.

pos is only assigned via an rb_entry(rb_first_postorder()) or rb_entry(rb_next_postorder()). rb_next_postorder() and rb_first_postorder() can return NULL. That NULL then is munged by rb_entry to be (NULL - offset_of_field). Causing (&pos->field == NULL == (pos + offset_of_field)).

That is, unless I've screwed something up (very possible, as this overly hurried patchset shows).

I expect it's more likely that my adaptation of this to ext3's usage is buggy. Could you tell me what you did to cause the oops? And/Or post it?

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/