[PATCH v2 00/11] rbtree: postorder iteration: fix, add tests, and use in various places

[PATCH v2 00/11] rbtree: postorder iteration: fix, add tests, and use in various places

[Cody P Schafer]

New in v2:
1: Jan Kara's fix for rbtree_postorder_for_each_entry_safe() for when gcc tries to optimize it.
2,3: test the above mentioned macro and reorder the test struct to catch anther class of errors.

Unchanged from v1:
4-11: use the postorder_for_each() in various locations.

--
Cody P Schafer (10):
  rbtree/test: move rb_node to the middle of the test struct
  rbtree/test: test rbtree_postorder_for_each_entry_safe()
  net ipset: use rbtree postorder iteration instead of opencoding
  trace/trace_stat: use rbtree postorder iteration helper instead of
    opencoding
  fs/ubifs: use rbtree postorder iteration helper instead of opencoding
  fs/ext4: use rbtree postorder iteration helper instead of opencoding
  fs/jffs2: use rbtree postorder iteration helper instead of opencoding
  fs/ext3: use rbtree postorder iteration helper instead of opencoding
  mtd/ubi: use rbtree postorder iteration helper instead of opencoding
  sh/dwarf: use rbtree postorder iteration helper instead of solution
    using repeated rb_erase()

Jan Kara (1):
  rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

 arch/sh/kernel/dwarf.c                     | 18 +++--------
 drivers/mtd/ubi/attach.c                   | 49 +++++-------------------------
 drivers/mtd/ubi/wl.c                       | 25 ++-------------
 fs/ext3/dir.c                              | 36 +++-------------------
 fs/ext4/block_validity.c                   | 33 +++-----------------
 fs/ext4/dir.c                              | 35 +++------------------
 fs/jffs2/nodelist.c                        | 28 ++---------------
 fs/jffs2/readinode.c                       | 26 ++--------------
 fs/ubifs/debug.c                           | 22 ++------------
 fs/ubifs/log.c                             | 21 ++-----------
 fs/ubifs/orphan.c                          | 21 ++-----------
 fs/ubifs/recovery.c                        | 21 ++-----------
 fs/ubifs/super.c                           | 24 +++------------
 fs/ubifs/tnc.c                             | 22 ++------------
 include/linux/rbtree.h                     | 16 +++++-----
 kernel/trace/trace_stat.c                  | 42 ++++---------------------
 lib/rbtree_test.c                          | 13 +++++++-
 net/netfilter/ipset/ip_set_hash_netiface.c | 27 +++-------------
 18 files changed, 81 insertions(+), 398 deletions(-)

-- 
1.8.4.2

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

[Cody P Schafer]

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

[PATCH v2 02/11] rbtree/test: move rb_node to the middle of the test struct

[Cody P Schafer]

Avoid making the rb_node the first entry to catch some bugs around NULL
checking the rb_node.

Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
---
 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

[PATCH v2 03/11] rbtree/test: test rbtree_postorder_for_each_entry_safe()

[Cody P Schafer]

Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
---
 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

[PATCH v2 04/11] net ipset: use rbtree postorder iteration instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 net/netfilter/ipset/ip_set_hash_netiface.c | 27 ++++-----------------------
 1 file changed, 4 insertions(+), 23 deletions(-)

diff --git a/net/netfilter/ipset/ip_set_hash_netiface.c b/net/netfilter/ipset/ip_set_hash_netiface.c
index 7d798d5..99dba4c 100644
--- a/net/netfilter/ipset/ip_set_hash_netiface.c
+++ b/net/netfilter/ipset/ip_set_hash_netiface.c
@@ -45,31 +45,12 @@ struct iface_node {
 static void
 rbtree_destroy(struct rb_root *root)
 {
-	struct rb_node *p, *n = root->rb_node;
-	struct iface_node *node;
-
-	/* Non-recursive destroy, like in ext3 */
-	while (n) {
-		if (n->rb_left) {
-			n = n->rb_left;
-			continue;
-		}
-		if (n->rb_right) {
-			n = n->rb_right;
-			continue;
-		}
-		p = rb_parent(n);
-		node = rb_entry(n, struct iface_node, node);
-		if (!p)
-			*root = RB_ROOT;
-		else if (p->rb_left == n)
-			p->rb_left = NULL;
-		else if (p->rb_right == n)
-			p->rb_right = NULL;
+	struct iface_node *node, *next;
 
+	rbtree_postorder_for_each_entry_safe(node, next, root, node)
 		kfree(node);
-		n = p;
-	}
+
+	*root = RB_ROOT;
 }
 
 static int
-- 
1.8.4.2

[PATCH v2 05/11] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 kernel/trace/trace_stat.c | 42 ++++++------------------------------------
 1 file changed, 6 insertions(+), 36 deletions(-)

diff --git a/kernel/trace/trace_stat.c b/kernel/trace/trace_stat.c
index 847f88a..fa53acc 100644
--- a/kernel/trace/trace_stat.c
+++ b/kernel/trace/trace_stat.c
@@ -43,46 +43,16 @@ static DEFINE_MUTEX(all_stat_sessions_mutex);
 /* The root directory for all stat files */
 static struct dentry		*stat_dir;
 
-/*
- * Iterate through the rbtree using a post order traversal path
- * to release the next node.
- * It won't necessary release one at each iteration
- * but it will at least advance closer to the next one
- * to be released.
- */
-static struct rb_node *release_next(struct tracer_stat *ts,
-				    struct rb_node *node)
+static void __reset_stat_session(struct stat_session *session)
 {
-	struct stat_node *snode;
-	struct rb_node *parent = rb_parent(node);
-
-	if (node->rb_left)
-		return node->rb_left;
-	else if (node->rb_right)
-		return node->rb_right;
-	else {
-		if (!parent)
-			;
-		else if (parent->rb_left == node)
-			parent->rb_left = NULL;
-		else
-			parent->rb_right = NULL;
+	struct stat_node *snode, *n;
 
-		snode = container_of(node, struct stat_node, node);
-		if (ts->stat_release)
-			ts->stat_release(snode->stat);
+	rbtree_postorder_for_each_entry_safe(snode, n, &session->stat_root,
+			node) {
+		if (session->ts->stat_release)
+			session->ts->stat_release(snode->stat);
 		kfree(snode);
-
-		return parent;
 	}
-}
-
-static void __reset_stat_session(struct stat_session *session)
-{
-	struct rb_node *node = session->stat_root.rb_node;
-
-	while (node)
-		node = release_next(session->ts, node);
 
 	session->stat_root = RB_ROOT;
 }
-- 
1.8.4.2

[PATCH v2 06/11] fs/ubifs: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 fs/ubifs/debug.c    | 22 +++-------------------
 fs/ubifs/log.c      | 21 ++-------------------
 fs/ubifs/orphan.c   | 21 ++-------------------
 fs/ubifs/recovery.c | 21 +++------------------
 fs/ubifs/super.c    | 24 ++++--------------------
 fs/ubifs/tnc.c      | 22 +++-------------------
 6 files changed, 17 insertions(+), 114 deletions(-)

diff --git a/fs/ubifs/debug.c b/fs/ubifs/debug.c
index 6e025e0..378c179 100644
--- a/fs/ubifs/debug.c
+++ b/fs/ubifs/debug.c
@@ -2118,26 +2118,10 @@ out_free:
  */
 static void free_inodes(struct fsck_data *fsckd)
 {
-	struct rb_node *this = fsckd->inodes.rb_node;
-	struct fsck_inode *fscki;
+	struct fsck_inode *fscki, *n;
 
-	while (this) {
-		if (this->rb_left)
-			this = this->rb_left;
-		else if (this->rb_right)
-			this = this->rb_right;
-		else {
-			fscki = rb_entry(this, struct fsck_inode, rb);
-			this = rb_parent(this);
-			if (this) {
-				if (this->rb_left == &fscki->rb)
-					this->rb_left = NULL;
-				else
-					this->rb_right = NULL;
-			}
-			kfree(fscki);
-		}
-	}
+	rbtree_postorder_for_each_entry_safe(fscki, n, &fsckd->inodes, rb)
+		kfree(fscki);
 }
 
 /**
diff --git a/fs/ubifs/log.c b/fs/ubifs/log.c
index 36bd4ef..a902c59 100644
--- a/fs/ubifs/log.c
+++ b/fs/ubifs/log.c
@@ -574,27 +574,10 @@ static int done_already(struct rb_root *done_tree, int lnum)
  */
 static void destroy_done_tree(struct rb_root *done_tree)
 {
-	struct rb_node *this = done_tree->rb_node;
-	struct done_ref *dr;
+	struct done_ref *dr, *n;
 
-	while (this) {
-		if (this->rb_left) {
-			this = this->rb_left;
-			continue;
-		} else if (this->rb_right) {
-			this = this->rb_right;
-			continue;
-		}
-		dr = rb_entry(this, struct done_ref, rb);
-		this = rb_parent(this);
-		if (this) {
-			if (this->rb_left == &dr->rb)
-				this->rb_left = NULL;
-			else
-				this->rb_right = NULL;
-		}
+	rbtree_postorder_for_each_entry_safe(dr, n, done_tree, rb)
 		kfree(dr);
-	}
 }
 
 /**
diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
index ba32da3..f1c3e5a1 100644
--- a/fs/ubifs/orphan.c
+++ b/fs/ubifs/orphan.c
@@ -815,27 +815,10 @@ static int dbg_find_check_orphan(struct rb_root *root, ino_t inum)
 
 static void dbg_free_check_tree(struct rb_root *root)
 {
-	struct rb_node *this = root->rb_node;
-	struct check_orphan *o;
+	struct check_orphan *o, *n;
 
-	while (this) {
-		if (this->rb_left) {
-			this = this->rb_left;
-			continue;
-		} else if (this->rb_right) {
-			this = this->rb_right;
-			continue;
-		}
-		o = rb_entry(this, struct check_orphan, rb);
-		this = rb_parent(this);
-		if (this) {
-			if (this->rb_left == &o->rb)
-				this->rb_left = NULL;
-			else
-				this->rb_right = NULL;
-		}
+	rbtree_postorder_for_each_entry_safe(o, n, root, rb)
 		kfree(o);
-	}
 }
 
 static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr,
diff --git a/fs/ubifs/recovery.c b/fs/ubifs/recovery.c
index 065096e..c14adb2 100644
--- a/fs/ubifs/recovery.c
+++ b/fs/ubifs/recovery.c
@@ -1335,29 +1335,14 @@ static void remove_ino(struct ubifs_info *c, ino_t inum)
  */
 void ubifs_destroy_size_tree(struct ubifs_info *c)
 {
-	struct rb_node *this = c->size_tree.rb_node;
-	struct size_entry *e;
+	struct size_entry *e, *n;
 
-	while (this) {
-		if (this->rb_left) {
-			this = this->rb_left;
-			continue;
-		} else if (this->rb_right) {
-			this = this->rb_right;
-			continue;
-		}
-		e = rb_entry(this, struct size_entry, rb);
+	rbtree_postorder_for_each_entry_safe(e, n, &c->size_tree, rb) {
 		if (e->inode)
 			iput(e->inode);
-		this = rb_parent(this);
-		if (this) {
-			if (this->rb_left == &e->rb)
-				this->rb_left = NULL;
-			else
-				this->rb_right = NULL;
-		}
 		kfree(e);
 	}
+
 	c->size_tree = RB_ROOT;
 }
 
diff --git a/fs/ubifs/super.c b/fs/ubifs/super.c
index 3e4aa72..14a5891 100644
--- a/fs/ubifs/super.c
+++ b/fs/ubifs/super.c
@@ -873,26 +873,10 @@ static void free_orphans(struct ubifs_info *c)
  */
 static void free_buds(struct ubifs_info *c)
 {
-	struct rb_node *this = c->buds.rb_node;
-	struct ubifs_bud *bud;
-
-	while (this) {
-		if (this->rb_left)
-			this = this->rb_left;
-		else if (this->rb_right)
-			this = this->rb_right;
-		else {
-			bud = rb_entry(this, struct ubifs_bud, rb);
-			this = rb_parent(this);
-			if (this) {
-				if (this->rb_left == &bud->rb)
-					this->rb_left = NULL;
-				else
-					this->rb_right = NULL;
-			}
-			kfree(bud);
-		}
-	}
+	struct ubifs_bud *bud, *n;
+
+	rbtree_postorder_for_each_entry_safe(bud, n, &c->buds, rb)
+		kfree(bud);
 }
 
 /**
diff --git a/fs/ubifs/tnc.c b/fs/ubifs/tnc.c
index 349f31a..9083bc7 100644
--- a/fs/ubifs/tnc.c
+++ b/fs/ubifs/tnc.c
@@ -178,27 +178,11 @@ static int ins_clr_old_idx_znode(struct ubifs_info *c,
  */
 void destroy_old_idx(struct ubifs_info *c)
 {
-	struct rb_node *this = c->old_idx.rb_node;
-	struct ubifs_old_idx *old_idx;
+	struct ubifs_old_idx *old_idx, *n;
 
-	while (this) {
-		if (this->rb_left) {
-			this = this->rb_left;
-			continue;
-		} else if (this->rb_right) {
-			this = this->rb_right;
-			continue;
-		}
-		old_idx = rb_entry(this, struct ubifs_old_idx, rb);
-		this = rb_parent(this);
-		if (this) {
-			if (this->rb_left == &old_idx->rb)
-				this->rb_left = NULL;
-			else
-				this->rb_right = NULL;
-		}
+	rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb)
 		kfree(old_idx);
-	}
+
 	c->old_idx = RB_ROOT;
 }
 
-- 
1.8.4.2

[PATCH v2 07/11] fs/ext4: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 fs/ext4/block_validity.c | 33 ++++-----------------------------
 fs/ext4/dir.c            | 35 +++++------------------------------
 2 files changed, 9 insertions(+), 59 deletions(-)

diff --git a/fs/ext4/block_validity.c b/fs/ext4/block_validity.c
index 3f11656..41eb9dc 100644
--- a/fs/ext4/block_validity.c
+++ b/fs/ext4/block_validity.c
@@ -180,37 +180,12 @@ int ext4_setup_system_zone(struct super_block *sb)
 /* Called when the filesystem is unmounted */
 void ext4_release_system_zone(struct super_block *sb)
 {
-	struct rb_node	*n = EXT4_SB(sb)->system_blks.rb_node;
-	struct rb_node	*parent;
-	struct ext4_system_zone	*entry;
+	struct ext4_system_zone	*entry, *n;
 
-	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);
-		entry = rb_entry(n, struct ext4_system_zone, node);
+	rbtree_postorder_for_each_entry_safe(entry, n,
+			&EXT4_SB(sb)->system_blks, node)
 		kmem_cache_free(ext4_system_zone_cachep, entry);
-		if (!parent)
-			EXT4_SB(sb)->system_blks = RB_ROOT;
-		else if (parent->rb_left == n)
-			parent->rb_left = NULL;
-		else if (parent->rb_right == n)
-			parent->rb_right = NULL;
-		n = parent;
-	}
+
 	EXT4_SB(sb)->system_blks = RB_ROOT;
 }
 
diff --git a/fs/ext4/dir.c b/fs/ext4/dir.c
index 680bb33..d638c57 100644
--- a/fs/ext4/dir.c
+++ b/fs/ext4/dir.c
@@ -353,41 +353,16 @@ 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;
 }
 
 
-- 
1.8.4.2

[PATCH v2 08/11] fs/jffs2: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 fs/jffs2/nodelist.c  | 28 ++--------------------------
 fs/jffs2/readinode.c | 26 +++-----------------------
 2 files changed, 5 insertions(+), 49 deletions(-)

diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index 975a1f5..9a5449b 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -564,25 +564,10 @@ struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_
    they're killed. */
 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
 {
-	struct jffs2_node_frag *frag;
-	struct jffs2_node_frag *parent;
-
-	if (!root->rb_node)
-		return;
+	struct jffs2_node_frag *frag, *next;
 
 	dbg_fragtree("killing\n");
-
-	frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
-	while(frag) {
-		if (frag->rb.rb_left) {
-			frag = frag_left(frag);
-			continue;
-		}
-		if (frag->rb.rb_right) {
-			frag = frag_right(frag);
-			continue;
-		}
-
+	rbtree_postorder_for_each_entry_safe(frag, next, root, rb) {
 		if (frag->node && !(--frag->node->frags)) {
 			/* Not a hole, and it's the final remaining frag
 			   of this node. Free the node */
@@ -591,17 +576,8 @@ void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
 
 			jffs2_free_full_dnode(frag->node);
 		}
-		parent = frag_parent(frag);
-		if (parent) {
-			if (frag_left(parent) == frag)
-				parent->rb.rb_left = NULL;
-			else
-				parent->rb.rb_right = NULL;
-		}
 
 		jffs2_free_node_frag(frag);
-		frag = parent;
-
 		cond_resched();
 	}
 }
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index ae81b01..386303d 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -543,33 +543,13 @@ static int jffs2_build_inode_fragtree(struct jffs2_sb_info *c,
 
 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
 {
-	struct rb_node *this;
-	struct jffs2_tmp_dnode_info *tn;
-
-	this = list->rb_node;
+	struct jffs2_tmp_dnode_info *tn, *next;
 
-	/* Now at bottom of tree */
-	while (this) {
-		if (this->rb_left)
-			this = this->rb_left;
-		else if (this->rb_right)
-			this = this->rb_right;
-		else {
-			tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
+	rbtree_postorder_for_each_entry_safe(tn, next, list, rb) {
 			jffs2_free_full_dnode(tn->fn);
 			jffs2_free_tmp_dnode_info(tn);
-
-			this = rb_parent(this);
-			if (!this)
-				break;
-
-			if (this->rb_left == &tn->rb)
-				this->rb_left = NULL;
-			else if (this->rb_right == &tn->rb)
-				this->rb_right = NULL;
-			else BUG();
-		}
 	}
+
 	*list = RB_ROOT;
 }
 
-- 
1.8.4.2

[PATCH v2 09/11] fs/ext3: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 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

[PATCH v2 10/11] mtd/ubi: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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 <cody@linux.vnet.ibm.com>
---
 drivers/mtd/ubi/attach.c | 49 +++++++-----------------------------------------
 drivers/mtd/ubi/wl.c     | 25 +++---------------------
 2 files changed, 10 insertions(+), 64 deletions(-)

diff --git a/drivers/mtd/ubi/attach.c b/drivers/mtd/ubi/attach.c
index c071d41..6de0786 100644
--- a/drivers/mtd/ubi/attach.c
+++ b/drivers/mtd/ubi/attach.c
@@ -1133,27 +1133,11 @@ static int late_analysis(struct ubi_device *ubi, struct ubi_attach_info *ai)
  */
 static void destroy_av(struct ubi_attach_info *ai, struct ubi_ainf_volume *av)
 {
-	struct ubi_ainf_peb *aeb;
-	struct rb_node *this = av->root.rb_node;
-
-	while (this) {
-		if (this->rb_left)
-			this = this->rb_left;
-		else if (this->rb_right)
-			this = this->rb_right;
-		else {
-			aeb = rb_entry(this, struct ubi_ainf_peb, u.rb);
-			this = rb_parent(this);
-			if (this) {
-				if (this->rb_left == &aeb->u.rb)
-					this->rb_left = NULL;
-				else
-					this->rb_right = NULL;
-			}
+	struct ubi_ainf_peb *aeb, *next;
+
+	rbtree_postorder_for_each_entry_safe(aeb, next, &av->root, u.rb)
+		kmem_cache_free(ai->aeb_slab_cache, aeb);
 
-			kmem_cache_free(ai->aeb_slab_cache, aeb);
-		}
-	}
 	kfree(av);
 }
 
@@ -1164,8 +1148,7 @@ static void destroy_av(struct ubi_attach_info *ai, struct ubi_ainf_volume *av)
 static void destroy_ai(struct ubi_attach_info *ai)
 {
 	struct ubi_ainf_peb *aeb, *aeb_tmp;
-	struct ubi_ainf_volume *av;
-	struct rb_node *rb;
+	struct ubi_ainf_volume *av, *next;
 
 	list_for_each_entry_safe(aeb, aeb_tmp, &ai->alien, u.list) {
 		list_del(&aeb->u.list);
@@ -1185,26 +1168,8 @@ static void destroy_ai(struct ubi_attach_info *ai)
 	}
 
 	/* Destroy the volume RB-tree */
-	rb = ai->volumes.rb_node;
-	while (rb) {
-		if (rb->rb_left)
-			rb = rb->rb_left;
-		else if (rb->rb_right)
-			rb = rb->rb_right;
-		else {
-			av = rb_entry(rb, struct ubi_ainf_volume, rb);
-
-			rb = rb_parent(rb);
-			if (rb) {
-				if (rb->rb_left == &av->rb)
-					rb->rb_left = NULL;
-				else
-					rb->rb_right = NULL;
-			}
-
-			destroy_av(ai, av);
-		}
-	}
+	rbtree_postorder_for_each_entry_safe(av, next, &ai->volumes, rb)
+		destroy_av(ai, av);
 
 	if (ai->aeb_slab_cache)
 		kmem_cache_destroy(ai->aeb_slab_cache);
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index c95bfb1..1af3899 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -1760,29 +1760,10 @@ int ubi_wl_flush(struct ubi_device *ubi, int vol_id, int lnum)
  */
 static void tree_destroy(struct rb_root *root)
 {
-	struct rb_node *rb;
-	struct ubi_wl_entry *e;
-
-	rb = root->rb_node;
-	while (rb) {
-		if (rb->rb_left)
-			rb = rb->rb_left;
-		else if (rb->rb_right)
-			rb = rb->rb_right;
-		else {
-			e = rb_entry(rb, struct ubi_wl_entry, u.rb);
-
-			rb = rb_parent(rb);
-			if (rb) {
-				if (rb->rb_left == &e->u.rb)
-					rb->rb_left = NULL;
-				else
-					rb->rb_right = NULL;
-			}
+	struct ubi_wl_entry *e, *next;
 
-			kmem_cache_free(ubi_wl_entry_slab, e);
-		}
-	}
+	rbtree_postorder_for_each_entry_safe(e, next, root, u.rb)
+		kmem_cache_free(ubi_wl_entry_slab, e);
 }
 
 /**
-- 
1.8.4.2

[PATCH v2 11/11] sh/dwarf: use rbtree postorder iteration helper instead of solution using repeated rb_erase()

[Cody P Schafer]

Use rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead
of using repeated rb_erase() calls

Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
---
 arch/sh/kernel/dwarf.c | 18 ++++--------------
 1 file changed, 4 insertions(+), 14 deletions(-)

diff --git a/arch/sh/kernel/dwarf.c b/arch/sh/kernel/dwarf.c
index 49c09c7..67a049e 100644
--- a/arch/sh/kernel/dwarf.c
+++ b/arch/sh/kernel/dwarf.c
@@ -995,29 +995,19 @@ static struct unwinder dwarf_unwinder = {
 
 static void dwarf_unwinder_cleanup(void)
 {
-	struct rb_node **fde_rb_node = &fde_root.rb_node;
-	struct rb_node **cie_rb_node = &cie_root.rb_node;
+	struct dwarf_fde *fde, *next_fde;
+	struct dwarf_cie *cie, *next_cie;
 
 	/*
 	 * Deallocate all the memory allocated for the DWARF unwinder.
 	 * Traverse all the FDE/CIE lists and remove and free all the
 	 * memory associated with those data structures.
 	 */
-	while (*fde_rb_node) {
-		struct dwarf_fde *fde;
-
-		fde = rb_entry(*fde_rb_node, struct dwarf_fde, node);
-		rb_erase(*fde_rb_node, &fde_root);
+	rbtree_postorder_for_each_entry_safe(fde, next_fde, &fde_root, node)
 		kfree(fde);
-	}
 
-	while (*cie_rb_node) {
-		struct dwarf_cie *cie;
-
-		cie = rb_entry(*cie_rb_node, struct dwarf_cie, node);
-		rb_erase(*cie_rb_node, &cie_root);
+	rbtree_postorder_for_each_entry_safe(cie, next_cie, &cie_root, node)
 		kfree(cie);
-	}
 
 	kmem_cache_destroy(dwarf_reg_cachep);
 	kmem_cache_destroy(dwarf_frame_cachep);
-- 
1.8.4.2

Re: [PATCH v2 09/11] fs/ext3: use rbtree postorder iteration helper instead of opencoding

[Jan Kara]

On Wed 06-11-13 17:42:38, 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
> 
> Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
  OK, since this patch now depends on rbtree_postorder... fix, I'll just
give you my:

Acked-by: Jan Kara <jack@suse.cz>

and you can merge it with other patches in the series.

								Honza
> ---
>  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 <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v2 07/11] fs/ext4: use rbtree postorder iteration helper instead of opencoding

[Jan Kara]

On Wed 06-11-13 17:42:36, 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
  The patch looks good. You can add:
Reviewed-by: Jan Kara <jack@suse.cz>

								Honza

> 
> Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
> ---
>  fs/ext4/block_validity.c | 33 ++++-----------------------------
>  fs/ext4/dir.c            | 35 +++++------------------------------
>  2 files changed, 9 insertions(+), 59 deletions(-)
> 
> diff --git a/fs/ext4/block_validity.c b/fs/ext4/block_validity.c
> index 3f11656..41eb9dc 100644
> --- a/fs/ext4/block_validity.c
> +++ b/fs/ext4/block_validity.c
> @@ -180,37 +180,12 @@ int ext4_setup_system_zone(struct super_block *sb)
>  /* Called when the filesystem is unmounted */
>  void ext4_release_system_zone(struct super_block *sb)
>  {
> -	struct rb_node	*n = EXT4_SB(sb)->system_blks.rb_node;
> -	struct rb_node	*parent;
> -	struct ext4_system_zone	*entry;
> +	struct ext4_system_zone	*entry, *n;
>  
> -	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);
> -		entry = rb_entry(n, struct ext4_system_zone, node);
> +	rbtree_postorder_for_each_entry_safe(entry, n,
> +			&EXT4_SB(sb)->system_blks, node)
>  		kmem_cache_free(ext4_system_zone_cachep, entry);
> -		if (!parent)
> -			EXT4_SB(sb)->system_blks = RB_ROOT;
> -		else if (parent->rb_left == n)
> -			parent->rb_left = NULL;
> -		else if (parent->rb_right == n)
> -			parent->rb_right = NULL;
> -		n = parent;
> -	}
> +
>  	EXT4_SB(sb)->system_blks = RB_ROOT;
>  }
>  
> diff --git a/fs/ext4/dir.c b/fs/ext4/dir.c
> index 680bb33..d638c57 100644
> --- a/fs/ext4/dir.c
> +++ b/fs/ext4/dir.c
> @@ -353,41 +353,16 @@ 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;
>  }
>  
>  
> -- 
> 1.8.4.2
> 
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH v2 01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

[Michel Lespinasse]

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,

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH v2 02/11] rbtree/test: move rb_node to the middle of the test struct

[Michel Lespinasse]

On Wed, Nov 6, 2013 at 5:42 PM, Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
> Avoid making the rb_node the first entry to catch some bugs around NULL
> checking the rb_node.
>
> Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
> ---
>  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;

Acked-by: Michel Lespinasse <walken@google.com>

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH v2 03/11] rbtree/test: test rbtree_postorder_for_each_entry_safe()

[Michel Lespinasse]

On Wed, Nov 6, 2013 at 5:42 PM, Cody P Schafer <cody@linux.vnet.ibm.com> wrote:
> Signed-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>
> ---
>  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

Looks reasonable if we need the rbtree_postorder_for_each_entry_safe
macro - but as I mentioned in 01/11, I would prefer if we could do
without that API.

Acked-by: Michel Lespinasse <walken@google.com>

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH v2 01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

[Cody P Schafer]

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.

Re: [PATCH v2 01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

[Andrew Morton]

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?

Re: [PATCH v2 01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

[Cody P Schafer]

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.

Re: [PATCH v2 01/11] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator

[Jan Kara]

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

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