Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node isnot the first element in an entry

[Jan Kara]

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...

								Honza
-- 
Jan Kara <jack@xxxxxxx>
SUSE Labs, CR
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/