Patchwork [v2,01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

login
register
mail settings
Submitter Cody P Schafer
Date Nov. 7, 2013, 1:42 a.m.
Message ID <1383788572-25938-2-git-send-email-cody@linux.vnet.ibm.com>
Download mbox | patch
Permalink /patch/289097/
State Not Applicable
Headers show

Comments

Cody P Schafer - Nov. 7, 2013, 1:42 a.m.
From: Jan Kara <jack@suse.cz>

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@suse.cz>
Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
---
 include/linux/rbtree.h | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)
Michel Lespinasse - Nov. 7, 2013, 11:51 a.m.
On Wed, Nov 6, 2013 at 5:42 PM, Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
> From: Jan Kara <jack@suse.cz>
>
> 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@suse.cz>
> Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
> ---
>  include/linux/rbtree.h | 16 +++++++++-------
>  1 file 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.8.4.2

Well, this really isn't pretty, and I'm not sure that
rbtree_postorder_for_each_entry_safe() is a good idea in the first
place. Note that we have never had or needed such a macro for the
common case of in-order iteration; why would we need it for the
less-common case of postorder iteration ?

I think it's just as well to have clients write something like
struct rb_node *rb_node = rb_first_postorder(root);
while (rb_node) {
    struct rb_node *rb_next_node = rb_next_postorder(rb_node);
    struct mystruct node = rb_entry(rb_node, struct mystruct,
mystruct_rb_field);
    .... do whatever, possibly destroying node ...
    rb_node = rb_next_node;
}

That said, there is some precedent for this kind of API in
hlist_for_each_entry_safe, so I guess that's acceptable if there will
be enough users of this macro - but it seems very strange to me that
we would need it for the postorder traversal while we don't for the
in-order traversal. I would prefer keeping rbtree.h minimal if that is
possible.

Thanks,
Cody P Schafer - Nov. 7, 2013, 6:59 p.m.
On 11/07/2013 03:51 AM, Michel Lespinasse wrote:
> On Wed, Nov 6, 2013 at 5:42 PM, Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
>> From: Jan Kara <jack@suse.cz>

[...]
>>
>> +#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_safe(rb_first_postorder(root), typeof(*pos), field); \
>> +            pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
>> +                       typeof(*pos), field); 1; }); \
>> +            pos = n)

>
> Well, this really isn't pretty, and I'm not sure that
> rbtree_postorder_for_each_entry_safe() is a good idea in the first
> place. Note that we have never had or needed such a macro for the
> common case of in-order iteration; why would we need it for the
> less-common case of postorder iteration ?

Well, maybe we should add a helper for in-order iteration if it 
simplifies the code's appearance significantly. I added this one because 
I think it's highly probable that users of the postorer iteration will 
always want the *_entry_safe() style for_each, meaning I don't have to 
add the other (non-safe, non-entry) variants.

> I think it's just as well to have clients write something like
> struct rb_node *rb_node = rb_first_postorder(root);
> while (rb_node) {
>      struct rb_node *rb_next_node = rb_next_postorder(rb_node);
>      struct mystruct *node = rb_entry(rb_node, struct mystruct,
> mystruct_rb_field);
>      .... do whatever, possibly destroying node ...
>      rb_node = rb_next_node;
> }
>

So, 4 extra lines per usage, an extra variable, and the need to split 
the iteration's logic across the action performed.

> That said, there is some precedent for this kind of API in
> hlist_for_each_entry_safe, so I guess that's acceptable if there will
> be enough users of this macro - but it seems very strange to me that
> we would need it for the postorder traversal while we don't for the
> in-order traversal. I would prefer keeping rbtree.h minimal if that is
> possible.
>

The other patches in this patchset add 16 usages of the for_each macro, 
and these are only conversions of the simple cases I found by grepping 
the kernel for rb_erase() and rb_(left|right) = NULL patterns. I others 
have found other ways to do the same (or similar) things that I haven't 
noticed.

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Andrew Morton - Nov. 7, 2013, 9:38 p.m.
On Wed,  6 Nov 2013 17:42:30 -0800 Cody P Schafer <cody@linux.vnet.ibm.com> wrote:

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

So the sole caller is in zswap.c.  Is that code actually generating oopses?

IOW, is there any need to fix this in 3.12 or earlier?
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Cody P Schafer - Nov. 7, 2013, 9:58 p.m.
On 11/07/2013 01:38 PM, Andrew Morton wrote:
> On Wed,  6 Nov 2013 17:42:30 -0800 Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
>
>> 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.
>
> So the sole caller is in zswap.c.  Is that code actually generating oopses?

I can't reproduce the oopses (at all) with my build/gcc version, but Jan 
has reported seeing them (not in zswap, however).

>
> IOW, is there any need to fix this in 3.12 or earlier?
>

The zswap usage change showed up in 3.12.
In my opinion, it is probably a good idea to apply the fix to 3.12.

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Jan Kara - Nov. 7, 2013, 10:14 p.m.
On Thu 07-11-13 13:38:00, Andrew Morton wrote:
> On Wed,  6 Nov 2013 17:42:30 -0800 Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
> 
> > 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.
> 
> So the sole caller is in zswap.c.  Is that code actually generating oopses?
  Oh, I didn't know there is any user of that iterator already in tree. Let
me check... Umm, looking at the disassembly of
zswap_frontswap_invalidate_aread:
   0xffffffff8112c9a5 <+37>:	mov    %r13,%rdi
   0xffffffff8112c9a8 <+40>:	callq  0xffffffff81227620 <rb_first_postorder>
   0xffffffff8112c9ad <+45>:	mov    %rax,%rdi
   0xffffffff8112c9b0 <+48>:	mov    %rax,%rbx
   0xffffffff8112c9b3 <+51>:	callq  0xffffffff812275d0 <rb_next_postorder>
   0xffffffff8112c9b8 <+56>:	mov    %rax,%r12
   0xffffffff8112c9bb <+59>:	nopl   0x0(%rax,%rax,1)
   0xffffffff8112c9c0 <+64>:	mov    0x28(%rbx),%rsi
   0xffffffff8112c9c4 <+68>:	mov    0x40(%r13),%rdi
   0xffffffff8112c9c8 <+72>:	callq  0xffffffff811352b0 <zbud_free>
   0xffffffff8112c9cd <+77>:	mov    0x1105504(%rip),%rdi
   0xffffffff8112c9d4 <+84>:	mov    %rbx,%rsi
   0xffffffff8112c9d7 <+87>:	callq  0xffffffff81130b80 <kmem_cache_free>
   0xffffffff8112c9dc <+92>:	lock decl 0x110539d(%rip)
   0xffffffff8112c9e3 <+99>:	mov    %r12,%rdi
   0xffffffff8112c9e6 <+102>:	mov    %r12,%rbx
   0xffffffff8112c9e9 <+105>:	callq  0xffffffff812275d0 <rb_next_postorder>
   0xffffffff8112c9ee <+110>:	mov    %rax,%r12
   0xffffffff8112c9f1 <+113>:	jmp 0xffffffff8112c9c0 <zswap_frontswap_invalidate_area+64>

So my gcc helpfully compiled that iterator into an endless loop as well,
although now it is a perfectly valid C code.  According to our gcc guys
that was a bug in some gcc versions which is already fixed.  But anyway
pushing my patch to 3.12 or anything that actually uses that iterator will
probably save us some bug reports.

								Honza

Patch

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