net ipset: use rbtree postorder iteration instead of opencoding
Subsystems (11)
PATCH 1/8 net ipset: use rbtree postorder iteration 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
--- net/netfilter/ipset/ip_set_hash_netiface.c | 27 ++++----------------------- 1 file changed, 4 insertions(+), 23 deletions(-)
net/netfilter/ipset/ip_set_hash_netiface.c +4 -23
@@ -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
Signature · 1 line
1.8.4.2
PATCH 2/8 trace/trace_stat: 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
--- kernel/trace/trace_stat.c | 42 ++++++------------------------------------ 1 file changed, 6 insertions(+), 36 deletions(-)
kernel/trace/trace_stat.c +6 -36
@@ -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 ; }
Signature · 1 line
1.8.4.2
Steven Rostedt
maintainerRe: [PATCH 2/8] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding
Quoted 38 lines · On Fri, 1 Nov 2013 15:38:46 -0700 Cody P Schafer <[email protected]>…
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeSigned-off-by Cody P Schafer <[email protected]>--- kernel/trace/trace_stat.c | 42 ++++++------------------------------------ 1 file changed, 6 insertions(+), 36 deletions(-)kernel/trace/trace_stat.c +1
-20@@ -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)
kernel/trace/trace_stat.c static DEFINE_MUTEX(all_stat_sessions_mutex); · line 51
Quoted 10 lines
kernel/trace/trace_stat.c +3
-6- 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
Quoted 17 lines
kernel/trace/trace_stat.c +2
-10+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
Quoted 12 lines · Steven Rostedt
Quoted 8 lines · On Fri, 1 Nov 2013 15:38:46 -0700 Cody P Schafer <[email protected]>…
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeSigned-off-by Cody P Schafer <[email protected]>--- kernel/trace/trace_stat.c | 42 ++++++------------------------------------ 1 file changed, 6 insertions(+), 36 deletions(-)
Quoted 6 lines
kernel/trace/trace_stat.c static DEFINE_MUTEX(all_stat_sessions_mutex); · line 51
Quoted 2 lines
kernel/trace/trace_stat.c +2
-0+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.
Quoted 3 lines
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.
Steven Rostedt
maintainerRe: [PATCH 2/8] trace/trace_stat: use rbtree postorder iteration helper instead of opencoding
Quoted 20 lines · On Mon, 04 Nov 2013 00:49:21 -0800 Cody P Schafer <[email protected]>…
Quoted 12 lines · Steven Rostedt
Quoted 8 lines · On Fri, 1 Nov 2013 15:38:46 -0700 Cody P Schafer <[email protected]>…
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeSigned-off-by Cody P Schafer <[email protected]>--- kernel/trace/trace_stat.c | 42 ++++++------------------------------------ 1 file changed, 6 insertions(+), 36 deletions(-)Quoted 6 lines
kernel/trace/trace_stat.c static DEFINE_MUTEX(all_stat_sessions_mutex); · line 51
Quoted 2 lines
kernel/trace/trace_stat.c +2
-0+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.
Quoted 9 lines
I'm fine with that being tweaked.
Quoted 3 lines
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
PATCH 3/8 fs/ubifs: use rbtree postorder iteration helper instead of opencoding
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the tree
--- 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(-)
fs/ubifs/debug.c +3 -19
@@ -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); }/**
fs/ubifs/log.c +2 -19
@@ -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); - } }/**
fs/ubifs/orphan.c +2 -19
@@ -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,
fs/ubifs/recovery.c +3 -18
@@ -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 ; }
fs/ubifs/super.c +4 -20
@@ -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); }/**
fs/ubifs/tnc.c +3 -19
@@ -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 ; }
Signature · 1 line
1.8.4.2
PATCH 4/8 fs/ext4: use rbtree postorder iteration helper instead of opencoding
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the tree
--- fs/ext4/block_validity.c | 33 ++++----------------------------- fs/ext4/dir.c | 35 +++++------------------------------ 2 files changed, 9 insertions(+), 59 deletions(-)
fs/ext4/block_validity.c +4 -29
@@ -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 ; }
fs/ext4/dir.c +5 -30
@@ -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 ; }
Signature · 1 line
1.8.4.2
PATCH 5/8 fs/jffs2: use rbtree postorder iteration helper instead of opencoding
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the tree
--- fs/jffs2/nodelist.c | 28 ++-------------------------- fs/jffs2/readinode.c | 26 +++----------------------- 2 files changed, 5 insertions(+), 49 deletions(-)
fs/jffs2/nodelist.c +2 -26
@@ -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 (); } }
fs/jffs2/readinode.c +3 -23
@@ -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 ; }
Signature · 1 line
1.8.4.2
PATCH 6/8 fs/ext3: use rbtree postorder iteration helper instead of opencoding
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the tree
--- fs/ext3/dir.c | 36 +++++------------------------------- 1 file changed, 5 insertions(+), 31 deletions(-)
fs/ext3/dir.c +5 -31
@@ -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)
Signature · 1 line
1.8.4.2
Jan Kara
reviewerRe: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding
Quoted 2 lines · 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
Thanks. I've merged the patch into my tree.
Honza
Quoted 61 lines
Signed-off-by Cody P Schafer <[email protected]>--- fs/ext3/dir.c | 36 +++++------------------------------- 1 file changed, 5 insertions(+), 31 deletions(-)fs/ext3/dir.c +5
-31@@ -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)Signature · 1 line
1.8.4.2
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
reviewerRe: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding
Quoted 4 lines · Jan Kara
Quoted 2 lines · Cody P Schafer
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. 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
Quoted 64 lines
Quoted 61 lines
Signed-off-by Cody P Schafer <[email protected]>--- fs/ext3/dir.c | 36 +++++------------------------------- 1 file changed, 5 insertions(+), 31 deletions(-)fs/ext3/dir.c +5
-31@@ -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)Signature · 1 line
1.8.4.2Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Re: [PATCH 6/8] fs/ext3: use rbtree postorder iteration helper instead of opencoding
Quoted 11 lines · Jan Kara
Quoted 4 lines · Jan Kara
Quoted 2 lines · Cody P Schafer
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. I've merged the patch into my tree.
Hum, except that the kernel oopses with this patch. And I think the
problem is inrbtree_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 callrb_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
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().
--- include/linux/rbtree.h | 20 +++++++++++++++----- lib/rbtree.c | 2 -- 2 files changed, 15 insertions(+), 7 deletions(-)
include/linux/rbtree.h +15 -5
@@ -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 */
lib/rbtree.c +0 -2
@@ -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 */
Signature · 1 line
1.8.4.2
PATCH 2/2 rbtree/test: move rb_node to the middle of the test struct
Avoid making the rb_node the first entry to catch some bugs around NULL checking the rb_node.
--- lib/rbtree_test.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/rbtree_test.c +1 -1
@@ -8,8 +8,8 @@#define CHECK_LOOPS 100struct test_node { -struct rb_node rb;u32 key; +struct rb_node rb;/* following fields used for testing augmented rbtree functionality */ u32 val;
Signature · 1 line
1.8.4.2
Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry
In reply to Cody P SchaferQuoted 4 lines · Cody P Schafer
Provide a new helper called
rb_next_postorder_entry()to perform NULL checks andcontainer_of()coversions and use it inrbtree_for_each_entry_safe()to fix oopses that occur whenrb_nodeis 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.
Quoted 9 lines · Jan Kara
Quoted 4 lines · Cody P Schafer
Quoted 2 lines
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. I've merged the patch into my tree.
Hum, except that the kernel oopses with this patch. And I think the
problem is inrbtree_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 callrb_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?
Jan Kara
reviewerRe: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry
Quoted 19 lines · Cody P Schafer
Quoted 4 lines · Cody P Schafer
Provide a new helper called
rb_next_postorder_entry()to perform NULL checks andcontainer_of()coversions and use it inrbtree_for_each_entry_safe()to fix oopses that occur whenrb_nodeis 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.
Quoted 9 lines · Jan Kara
Quoted 4 lines · Cody P Schafer
Quoted 2 lines
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. I've merged the patch into my tree.
Hum, except that the kernel oopses with this patch. And I think the
problem is inrbtree_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 callrb_next_postorder(&NULL->field)which is pretty much guaranteed to oops if 'field' doesn't have offset 0 in the structure...
Quoted 7 lines
No, it shouldn't oops because pos won't be NULL,
&pos->fieldwill be.pos is only assigned via an rb_entry(rb_first_postorder()) or rb_entry(rb_next_postorder()).
rb_next_postorder()andrb_first_postorder()can return NULL. That NULL then is munged byrb_entryto 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
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Jan Kara
reviewerRe: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry
Quoted 27 lines · Jan Kara
Quoted 19 lines · Cody P Schafer
Quoted 4 lines · Cody P Schafer
Provide a new helper called
rb_next_postorder_entry()to perform NULL checks andcontainer_of()coversions and use it inrbtree_for_each_entry_safe()to fix oopses that occur whenrb_nodeis 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.
Quoted 9 lines · Jan Kara
Quoted 4 lines · Cody P Schafer
Quoted 2 lines
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. I've merged the patch into my tree.
Hum, except that the kernel oopses with this patch. And I think the
problem is inrbtree_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 callrb_next_postorder(&NULL->field)which is pretty much guaranteed to oops if 'field' doesn't have offset 0 in the structure...Quoted 7 lines
No, it shouldn't oops because pos won't be NULL,
&pos->fieldwill be.pos is only assigned via an rb_entry(rb_first_postorder()) or rb_entry(rb_next_postorder()).
rb_next_postorder()andrb_first_postorder()can return NULL. That NULL then is munged byrb_entryto be (NULL -offset_of_field). Causing (&pos->field== NULL == (pos +offset_of_field)).
Quoted 5 lines
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->fieldto 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
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Quoted 1 line
From
d51a16626d241ded8913768d6f24484b1d4335baMon Sep 17 00:00:00 2001
From: Jan Kara <[email protected]>
Date: Tue, 5 Nov 2013 21:39:48 +0100
Subject: [PATCH] rbtree: Fix rbtree_postorder_for_each_entry_safe() iterator
The iterator rbtree_postorder_for_each_entry_safe() relies on pointer underflow behavior when testing for loop termination. In particular it expects that
&rb_entry(NULL, type, field)->field
is NULL. But the result of this expression is not defined by a C standard and some gcc versions (e.g. 4.3.4) assume the above expression can never be equal to NULL. The net result is an oops because the iteration is not properly terminated.
Fix the problem by modifying the iterator to avoid pointer underflows.
--- include/linux/rbtree.h | 16 +++++++++------- 1 files changed, 9 insertions(+), 7 deletions(-)
include/linux/rbtree.h +9 -7
@@ -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 */
Signature · 1 line
1.6.0.2
Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry
Quoted 24 lines · Jan Kara
Quoted 16 lines · Jan Kara
Quoted 16 lines · Cody P Schafer
Quoted 15 lines
Quoted 15 lines · Cody P Schafer
Quoted 4 lines
Quoted 4 lines
Provide a new helper called
rb_next_postorder_entry()to perform NULL checks andcontainer_of()coversions and use it inrbtree_for_each_entry_safe()to fix oopses that occur whenrb_nodeis 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.
Quoted 5 lines · Jan Kara
Quoted 5 lines
Quoted 4 lines
Quoted 4 lines · Cody P Schafer
Quoted 2 lines
Quoted 2 lines
Use
rbtree_postorder_for_each_entry_safe()to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the treeThanks. I've merged the patch into my tree.
Hum, except that the kernel oopses with this patch.
Quoted 7 lines
Quoted 7 lines
Quoted 2 lines
Quoted 2 lines
No, it shouldn't oops because pos won't be NULL,
&pos->fieldwill 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->fieldto 1. I've asked our gcc guys for a definitive answer but clearly your code will need some way to avoid pointer underflows...
Quoted 5 lines
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).
Quoted 60 lines
0001-rbtree-Fix-rbtree_postorder_for_each_entry_safe-i.patch
From
d51a16626d241ded8913768d6f24484b1d4335baMon Sep 17 00:00:00 2001
From: Jan Kara<[email protected]>
Date: Tue, 5 Nov 2013 21:39:48 +0100
Subject: [PATCH] rbtree: Fixrbtree_postorder_for_each_entry_safe()iteratorThe iterator
rbtree_postorder_for_each_entry_safe()relies on pointer underflow behavior when testing for loop termination. In particular it expects that
&rb_entry(NULL, type, field)->field
is NULL. But the result of this expression is not defined by a C standard and some gcc versions (e.g. 4.3.4) assume the above expression can never be equal to NULL. The net result is an oops because the iteration is not properly terminated.Fix the problem by modifying the iterator to avoid pointer underflows.
Signed-off-by Jan Kara<[email protected]>--- include/linux/rbtree.h | 16 +++++++++------- 1 files changed, 9 insertions(+), 7 deletions(-)include/linux/rbtree.h +9
-8@@ -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 1/1 rbtree/test: test rbtree_postorder_for_each_entry_safe()
--- lib/rbtree_test.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
lib/rbtree_test.c +11 -0
@@ -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)
Signature · 1 line
1.8.4.2
Andrew Morton
maintainerRe: [PATCH] rbtree/test: test rbtree_postorder_for_each_entry_safe()
Quoted 22 lines · On Wed, 6 Nov 2013 13:37:23 -0800 Cody P Schafer <[email protected]>…
...
lib/rbtree_test.c +10
-0@@ -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;
lib/rbtree_test.c static void check(int nr_nodes) · line 164
Quoted 7 lines
lib/rbtree_test.c +1
-0@@ -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?
PATCH 7/8 mtd/ubi: use rbtree postorder iteration helper instead of opencoding
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of opencoding an alternate postorder iteration that modifies the tree
--- drivers/mtd/ubi/attach.c | 49 +++++++----------------------------------------- drivers/mtd/ubi/wl.c | 25 +++--------------------- 2 files changed, 10 insertions(+), 64 deletions(-)
drivers/mtd/ubi/attach.c +7 -42
@@ -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);
drivers/mtd/ubi/wl.c +3 -22
@@ -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); }/**
Signature · 1 line
1.8.4.2
PATCH 8/8 sh/dwarf: use rbtree postorder iteration helper instead of solution using repeated rb_erase()
In reply to Cody P SchaferUse rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead of using repeated rb_erase() calls
--- arch/sh/kernel/dwarf.c | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-)
arch/sh/kernel/dwarf.c +4 -14
@@ -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);
Signature · 1 line
1.8.4.2