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

[Cody P Schafer]

On 11/05/2013 02:56 PM, Jan Kara wrote:
> 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.
> > > > >
> > > > >No, it shouldn't oops because pos won't be NULL, &pos->field will be.
> > > > >
> > >   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

That looks good, thanks.

I've thrown together a basic runtime test for the 
rbtree_postorder_for_each_entry_safe() macro, will send that out shortly.

For the record with my gcc (gcc version 4.6.4 (Ubuntu/Linaro 
4.6.4-1ubuntu1~12.04)) I can't get it to bug out (even when your fix 
_isn't_ applied).

> 0001-rbtree-Fix-rbtree_postorder_for_each_entry_safe-i.patch
>
>
>  From d51a16626d241ded8913768d6f24484b1d4335ba Mon Sep 17 00:00:00 2001
> From: Jan Kara<jack@xxxxxxx>
> Date: Tue, 5 Nov 2013 21:39:48 +0100
> Subject: [PATCH] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator
>
> The iterator rbtree_postorder_for_each_entry_safe() relies on pointer
> underflow behavior when testing for loop termination. In particular
> it expects that
>    &rb_entry(NULL, type, field)->field
> is NULL. But the result of this expression is not defined by a C standard
> and some gcc versions (e.g. 4.3.4) assume the above expression can never
> be equal to NULL. The net result is an oops because the iteration is not
> properly terminated.
>
> Fix the problem by modifying the iterator to avoid pointer underflows.
>
> Signed-off-by: Jan Kara<jack@xxxxxxx>
> ---
>   include/linux/rbtree.h |   16 +++++++++-------
>   1 files changed, 9 insertions(+), 7 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index aa870a4..57e75ae 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -85,6 +85,11 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
>   	*rb_link = node;
>   }
>
> +#define rb_entry_safe(ptr, type, member) \
> +	({ typeof(ptr) ____ptr = (ptr); \
> +	   ____ptr ? rb_entry(____ptr, type, member) : NULL; \
> +	})
> +
>   /**
>    * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of
>    * given type safe against removal of rb_node entry
> @@ -95,12 +100,9 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
>    * @field:	the name of the rb_node field within 'type'.
>    */
>   #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
> -	for (pos = rb_entry(rb_first_postorder(root), typeof(*pos), field),\
> -		n = rb_entry(rb_next_postorder(&pos->field), \
> -			typeof(*pos), field); \
> -	     &pos->field; \
> -	     pos = n, \
> -		n = rb_entry(rb_next_postorder(&pos->field), \
> -			typeof(*pos), field))
> +	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
> +	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
> +			typeof(*pos), field); 1; }); \
> +	     pos = n)
>
>   #endif	/* _LINUX_RBTREE_H */
> -- 1.6.0.2

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