Use rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead
of opencoding an alternate postorder iteration that modifies the tree
Signed-off-by: Cody P Schafer <[email protected]>
---
fs/ext3/dir.c | 36 +++++-------------------------------
1 file changed, 5 insertions(+), 31 deletions(-)
diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
index bafdd48..a331ad1 100644
--- a/fs/ext3/dir.c
+++ b/fs/ext3/dir.c
@@ -309,43 +309,17 @@ struct fname {
*/
static void free_rb_tree_fname(struct rb_root *root)
{
- struct rb_node *n = root->rb_node;
- struct rb_node *parent;
- struct fname *fname;
-
- while (n) {
- /* Do the node's children first */
- if (n->rb_left) {
- n = n->rb_left;
- continue;
- }
- if (n->rb_right) {
- n = n->rb_right;
- continue;
- }
- /*
- * The node has no children; free it, and then zero
- * out parent's link to it. Finally go to the
- * beginning of the loop and try to free the parent
- * node.
- */
- parent = rb_parent(n);
- fname = rb_entry(n, struct fname, rb_hash);
+ struct fname *fname, *next;
+
+ rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)
while (fname) {
struct fname * old = fname;
fname = fname->next;
kfree (old);
}
- if (!parent)
- *root = RB_ROOT;
- else if (parent->rb_left == n)
- parent->rb_left = NULL;
- else if (parent->rb_right == n)
- parent->rb_right = NULL;
- n = parent;
- }
-}
+ *root = RB_ROOT;
+}
static struct dir_private_info *ext3_htree_create_dir_info(struct file *filp,
loff_t pos)
--
1.8.4.2
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.
Honza
> Signed-off-by: Cody P Schafer <[email protected]>
> ---
> fs/ext3/dir.c | 36 +++++-------------------------------
> 1 file changed, 5 insertions(+), 31 deletions(-)
>
> diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
> index bafdd48..a331ad1 100644
> --- a/fs/ext3/dir.c
> +++ b/fs/ext3/dir.c
> @@ -309,43 +309,17 @@ struct fname {
> */
> static void free_rb_tree_fname(struct rb_root *root)
> {
> - struct rb_node *n = root->rb_node;
> - struct rb_node *parent;
> - struct fname *fname;
> -
> - while (n) {
> - /* Do the node's children first */
> - if (n->rb_left) {
> - n = n->rb_left;
> - continue;
> - }
> - if (n->rb_right) {
> - n = n->rb_right;
> - continue;
> - }
> - /*
> - * The node has no children; free it, and then zero
> - * out parent's link to it. Finally go to the
> - * beginning of the loop and try to free the parent
> - * node.
> - */
> - parent = rb_parent(n);
> - fname = rb_entry(n, struct fname, rb_hash);
> + struct fname *fname, *next;
> +
> + rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)
> while (fname) {
> struct fname * old = fname;
> fname = fname->next;
> kfree (old);
> }
> - if (!parent)
> - *root = RB_ROOT;
> - else if (parent->rb_left == n)
> - parent->rb_left = NULL;
> - else if (parent->rb_right == n)
> - parent->rb_right = NULL;
> - n = parent;
> - }
> -}
>
> + *root = RB_ROOT;
> +}
>
> static struct dir_private_info *ext3_htree_create_dir_info(struct file *filp,
> loff_t pos)
> --
> 1.8.4.2
>
--
Jan Kara <[email protected]>
SUSE Labs, CR
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...
Honza
> > Signed-off-by: Cody P Schafer <[email protected]>
> > ---
> > fs/ext3/dir.c | 36 +++++-------------------------------
> > 1 file changed, 5 insertions(+), 31 deletions(-)
> >
> > diff --git a/fs/ext3/dir.c b/fs/ext3/dir.c
> > index bafdd48..a331ad1 100644
> > --- a/fs/ext3/dir.c
> > +++ b/fs/ext3/dir.c
> > @@ -309,43 +309,17 @@ struct fname {
> > */
> > static void free_rb_tree_fname(struct rb_root *root)
> > {
> > - struct rb_node *n = root->rb_node;
> > - struct rb_node *parent;
> > - struct fname *fname;
> > -
> > - while (n) {
> > - /* Do the node's children first */
> > - if (n->rb_left) {
> > - n = n->rb_left;
> > - continue;
> > - }
> > - if (n->rb_right) {
> > - n = n->rb_right;
> > - continue;
> > - }
> > - /*
> > - * The node has no children; free it, and then zero
> > - * out parent's link to it. Finally go to the
> > - * beginning of the loop and try to free the parent
> > - * node.
> > - */
> > - parent = rb_parent(n);
> > - fname = rb_entry(n, struct fname, rb_hash);
> > + struct fname *fname, *next;
> > +
> > + rbtree_postorder_for_each_entry_safe(fname, next, root, rb_hash)
> > while (fname) {
> > struct fname * old = fname;
> > fname = fname->next;
> > kfree (old);
> > }
> > - if (!parent)
> > - *root = RB_ROOT;
> > - else if (parent->rb_left == n)
> > - parent->rb_left = NULL;
> > - else if (parent->rb_right == n)
> > - parent->rb_right = NULL;
> > - n = parent;
> > - }
> > -}
> >
> > + *root = RB_ROOT;
> > +}
> >
> > static struct dir_private_info *ext3_htree_create_dir_info(struct file *filp,
> > loff_t pos)
> > --
> > 1.8.4.2
> >
> --
> Jan Kara <[email protected]>
> SUSE Labs, CR
--
Jan Kara <[email protected]>
SUSE Labs, CR
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...
>
You're absolutely right, those NULL checks are wrong when the rb_node
isn't the first element. Fix incoming shortly.
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.
Additionally, remove the missplaced NULL check from rb_next_postorder().
Signed-off-by: Cody P Schafer <[email protected]>
---
include/linux/rbtree.h | 20 +++++++++++++++-----
lib/rbtree.c | 2 --
2 files changed, 15 insertions(+), 7 deletions(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index aa870a4..630eedb 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -86,6 +86,18 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
}
/**
+ * rb_next_postorder_entry - a helper to check for a NULL entry and advance to
+ * the next element.
+ *
+ * @elem: a 'type *' which is contained in an rbtree
+ * @field: the field in 'type' which contains the struct rb_node.
+ */
+#define rb_next_postorder_entry(elem, field) \
+ ((elem) ? rb_entry(rb_next_postorder(&(elem)->field), \
+ typeof(*(elem)), field) \
+ : NULL)
+
+/**
* rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of
* given type safe against removal of rb_node entry
*
@@ -96,11 +108,9 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
*/
#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; \
+ n = rb_next_postorder_entry(pos, field); \
+ pos; \
pos = n, \
- n = rb_entry(rb_next_postorder(&pos->field), \
- typeof(*pos), field))
+ n = rb_next_postorder_entry(pos, field))
#endif /* _LINUX_RBTREE_H */
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 65f4eff..08168d0 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -534,8 +534,6 @@ static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
struct rb_node *rb_next_postorder(const struct rb_node *node)
{
const struct rb_node *parent;
- if (!node)
- return NULL;
parent = rb_parent(node);
/* If we're sitting on node, we've already seen our children */
--
1.8.4.2
Avoid making the rb_node the first entry to catch some bugs around NULL
checking the rb_node.
Signed-off-by: Cody P Schafer <[email protected]>
---
lib/rbtree_test.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 31dd4cc..df6c125 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -8,8 +8,8 @@
#define CHECK_LOOPS 100
struct test_node {
- struct rb_node rb;
u32 key;
+ struct rb_node rb;
/* following fields used for testing augmented rbtree functionality */
u32 val;
--
1.8.4.2
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?
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 <[email protected]>
SUSE Labs, CR
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 <[email protected]>
SUSE Labs, CR
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<[email protected]>
> 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<[email protected]>
> ---
> 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
>
Signed-off-by: Cody P Schafer <[email protected]>
---
lib/rbtree_test.c | 11 +++++++++++
1 file changed, 11 insertions(+)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index df6c125..8b3c9dc 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -114,6 +114,16 @@ static int black_path_count(struct rb_node *rb)
return count;
}
+static void check_postorder_foreach(int nr_nodes)
+{
+ struct test_node *cur, *n;
+ int count = 0;
+ rbtree_postorder_for_each_entry_safe(cur, n, &root, rb)
+ count++;
+
+ WARN_ON_ONCE(count != nr_nodes);
+}
+
static void check_postorder(int nr_nodes)
{
struct rb_node *rb;
@@ -148,6 +158,7 @@ static void check(int nr_nodes)
WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root))) - 1);
check_postorder(nr_nodes);
+ check_postorder_foreach(nr_nodes);
}
static void check_augmented(int nr_nodes)
--
1.8.4.2
On Wed, 6 Nov 2013 13:37:23 -0800 Cody P Schafer <[email protected]> wrote:
> ...
>
> --- a/lib/rbtree_test.c
> +++ b/lib/rbtree_test.c
> @@ -114,6 +114,16 @@ static int black_path_count(struct rb_node *rb)
> return count;
> }
>
> +static void check_postorder_foreach(int nr_nodes)
> +{
> + struct test_node *cur, *n;
> + int count = 0;
> + rbtree_postorder_for_each_entry_safe(cur, n, &root, rb)
> + count++;
> +
> + WARN_ON_ONCE(count != nr_nodes);
> +}
> +
> static void check_postorder(int nr_nodes)
> {
> struct rb_node *rb;
> @@ -148,6 +158,7 @@ static void check(int nr_nodes)
> WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root))) - 1);
>
> check_postorder(nr_nodes);
> + check_postorder_foreach(nr_nodes);
> }
>
> static void check_augmented(int nr_nodes)
I'm rather confused about where this fits with the other (and
apparently withdrawn) patches.
Please resend everything?