[PATCH 1/8] net ipset: use rbtree postorder iteration instead of opencoding

[PATCH 1/8] 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 2/8] 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 3/8] fs/ubifs: use rbtree postorder iteration helper instead of opencoding

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 3/8] 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 4/8] 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 5/8] 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 5/8] 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 6/8] 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 7/8] 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 7/8] 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 8/8] sh/dwarf: use rbtree postorder iteration helper instead of solution using repeated rb_er

[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

[PATCH 8/8] 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 2/8] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding

[Steven Rostedt]

On Fri,  1 Nov 2013 15:38:46 -0700
Cody P Schafer <cody@linux.vnet.ibm.com> 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>
> ---
>  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) {

This is one of those cases that a line break is uglier than keeping it
on the same line. Heck, it's only 4 characters over the 80 char limit.

Other than that, I'm fine with this patch. Want me to take this
separately?

-- Steve


> +		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;
>  }

Re: [PATCH 2/8] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

On 11/01/2013 07:45 PM, Steven Rostedt wrote:
> On Fri,  1 Nov 2013 15:38:46 -0700
> Cody P Schafer <cody@linux.vnet.ibm.com> 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>
>> ---
>>   kernel/trace/trace_stat.c | 42 ++++++------------------------------------
>>   1 file changed, 6 insertions(+), 36 deletions(-)
>>

>> +	rbtree_postorder_for_each_entry_safe(snode, n, &session->stat_root,
>> +			node) {
>
> This is one of those cases that a line break is uglier than keeping it
> on the same line. Heck, it's only 4 characters over the 80 char limit.
>

I'm fine with that being tweaked.

> Other than that, I'm fine with this patch. Want me to take this
> separately?
>

The patches in this patchset are all independent (they just happen to be 
making nearly identical changes throughout the tree), so feel free.

Re: [PATCH 2/8] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding

[Steven Rostedt]

On Mon, 04 Nov 2013 00:49:21 -0800
Cody P Schafer <cody@linux.vnet.ibm.com> wrote:

> On 11/01/2013 07:45 PM, Steven Rostedt wrote:
> > On Fri,  1 Nov 2013 15:38:46 -0700
> > Cody P Schafer <cody@linux.vnet.ibm.com> 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>
> >> ---
> >>   kernel/trace/trace_stat.c | 42 ++++++------------------------------------
> >>   1 file changed, 6 insertions(+), 36 deletions(-)
> >>
> 
> >> +	rbtree_postorder_for_each_entry_safe(snode, n, &session->stat_root,
> >> +			node) {
> >
> > This is one of those cases that a line break is uglier than keeping it
> > on the same line. Heck, it's only 4 characters over the 80 char limit.
> >
> 
> I'm fine with that being tweaked.
> 
> > Other than that, I'm fine with this patch. Want me to take this
> > separately?
> >
> 
> The patches in this patchset are all independent (they just happen to be 
> making nearly identical changes throughout the tree), so feel free.
> 

OK, I'll pull it in and modify the above change too.

Thanks,

-- Steve

Re: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding

[Jan Kara]

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

Re: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding

[Jan Kara]

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

Re: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding

[Cody P Schafer]

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.

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

[Cody P Schafer]

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

[PATCH 2/2] 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

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

[Cody P Schafer]

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?

Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not 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@suse.cz>
SUSE Labs, CR

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

[Jan Kara]

[-- Attachment #1: Type: text/plain, Size: 2250 bytes --]

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

[-- Attachment #2: 0001-rbtree-Fix-rbtree_postorder_for_each_entry_safe-i.patch --]
[-- Type: text/x-patch, Size: 2158 bytes --]

>From d51a16626d241ded8913768d6f24484b1d4335ba Mon Sep 17 00:00:00 2001
From: Jan Kara <jack@suse.cz>
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@suse.cz>
---
 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

Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is 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@suse.cz>
> 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@suse.cz>
> ---
>   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
>

[PATCH] 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

Re: [PATCH] rbtree/test: test rbtree_postorder_for_each_entry_safe()

[Andrew Morton]

On Wed,  6 Nov 2013 13:37:23 -0800 Cody P Schafer <cody@linux.vnet.ibm.com> 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?