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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20131105225619.GC9236@quack.suse.cz>
Date:	Tue, 5 Nov 2013 23:56:19 +0100
From:	Jan Kara <jack@...e.cz>
To:	Cody P Schafer <cody@...ux.vnet.ibm.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>, Jan Kara <jack@...e.cz>,
	Andreas Dilger <adilger.kernel@...ger.ca>,
	LKML <linux-kernel@...r.kernel.org>,
	EXT4 <linux-ext4@...r.kernel.org>
Subject: Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is
 not the first element in an entry

On Tue 05-11-13 22:57:55, Jan Kara wrote:
> On Tue 05-11-13 02:05:44, Cody P Schafer wrote:
> > 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)).
>   OK, so I had a second look. And the compiler thinks differently than you
> :) The thing is that my gcc (4.3.4) apparently assumes pointer underflow is
> undefined and thus optimizes your test &pos->field to 1. I've asked our gcc
> guys for a definitive answer but clearly your code will need some way to
> avoid pointer underflows...
  I've just now checked how e.g. hlist iterators solve similar problem and
modified the rbtree iterator accordingly. The patch is attached and with it
and your ext3 patch my test machine is able to boot again.

								Honza
-- 
Jan Kara <jack@...e.cz>
SUSE Labs, CR

View attachment "0001-rbtree-Fix-rbtree_postorder_for_each_entry_safe-i.patch" of type "text/x-patch" (2159 bytes)