Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1228439 > unrolled thread

[PATCH 1/2] perf tools: Use postorder rbtree iteration when removing symbols

Back to article view | Back to linux.kernel

Contents

  [PATCH 1/2] perf tools: Use postorder rbtree iteration when removing symbols Alex Snast <asnast@gmail.com> - 2015-09-19 15:10 +0200
    [PATCH 2/2] perf tools: Use rb_entry_safe on first / next symbol lookup Alex Snast <asnast@gmail.com> - 2015-09-19 15:10 +0200
    Re: [PATCH 1/2] perf tools: Use postorder rbtree iteration when  removing symbols Ingo Molnar <mingo@kernel.org> - 2015-09-20 10:10 +0200
      Re: [PATCH 1/2] perf tools: Use postorder rbtree iteration when  removing symbols Ingo Molnar <mingo@kernel.org> - 2015-09-21 09:20 +0200

#1228439 — [PATCH 1/2] perf tools: Use postorder rbtree iteration when removing symbols

Avoid using rb_erase when removing symbols as it requires rbtree
rebalancing, instead preform a post order iteration when deleting tree
symbols.

Signed-off-by: Alex Snast <asnast@gmail.com>
---
 tools/include/linux/rbtree.h | 14 ++++++++++++++
 tools/perf/util/symbol.c     | 11 ++++-------
 2 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h
index 1125822..14c646d 100644
--- a/tools/include/linux/rbtree.h
+++ b/tools/include/linux/rbtree.h
@@ -90,6 +90,20 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
 	   ____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
+ *
+ * @pos:	the 'type *' to use as a loop cursor.
+ * @n:		another 'type *' to use as temporary storage
+ * @root:	'rb_root *' of the rbtree.
+ * @field:	the name of the rb_node field within 'type'.
+ */
+#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
+	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
+	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
+			typeof(*pos), field); 1; }); \
+	     pos = n)
 
 /*
  * Handy for checking that we are not deleting an entry that is
diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 1f97ffb..8b3608c 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -290,15 +290,12 @@ size_t symbol__fprintf_symname(const struct symbol *sym, FILE *fp)
 
 void symbols__delete(struct rb_root *symbols)
 {
-	struct symbol *pos;
-	struct rb_node *next = rb_first(symbols);
+	struct symbol *pos, *next;
 
-	while (next) {
-		pos = rb_entry(next, struct symbol, rb_node);
-		next = rb_next(&pos->rb_node);
-		rb_erase(&pos->rb_node, symbols);
+	rbtree_postorder_for_each_entry_safe(pos, next, symbols, rb_node)
 		symbol__delete(pos);
-	}
+
+	*symbols = RB_ROOT;
 }
 
 void symbols__insert(struct rb_root *symbols, struct symbol *sym)
-- 
2.1.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1228440 — [PATCH 2/2] perf tools: Use rb_entry_safe on first / next symbol lookup

Signed-off-by: Alex Snast <asnast@gmail.com>
---
 tools/perf/util/symbol.c | 10 ++--------
 1 file changed, 2 insertions(+), 8 deletions(-)

diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 8b3608c..5728121 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -344,20 +344,14 @@ static struct symbol *symbols__first(struct rb_root *symbols)
 {
 	struct rb_node *n = rb_first(symbols);
 
-	if (n)
-		return rb_entry(n, struct symbol, rb_node);
-
-	return NULL;
+	return rb_entry_safe(n, struct symbol, rb_node);
 }
 
 static struct symbol *symbols__next(struct symbol *sym)
 {
 	struct rb_node *n = rb_next(&sym->rb_node);
 
-	if (n)
-		return rb_entry(n, struct symbol, rb_node);
-
-	return NULL;
+	return rb_entry_safe(n, struct symbol, rb_node);
 }
 
 struct symbol_name_rb_node {
-- 
2.1.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1228842 — Re: [PATCH 1/2] perf tools: Use postorder rbtree iteration when removing symbols

* Alex Snast <asnast@gmail.com> wrote:

> Avoid using rb_erase when removing symbols as it requires rbtree
> rebalancing, instead preform a post order iteration when deleting tree
> symbols.
> 
> Signed-off-by: Alex Snast <asnast@gmail.com>
> ---
>  tools/include/linux/rbtree.h | 14 ++++++++++++++
>  tools/perf/util/symbol.c     | 11 ++++-------
>  2 files changed, 18 insertions(+), 7 deletions(-)
> 
> diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h
> index 1125822..14c646d 100644
> --- a/tools/include/linux/rbtree.h
> +++ b/tools/include/linux/rbtree.h
> @@ -90,6 +90,20 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
>  	   ____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
> + *
> + * @pos:	the 'type *' to use as a loop cursor.
> + * @n:		another 'type *' to use as temporary storage
> + * @root:	'rb_root *' of the rbtree.
> + * @field:	the name of the rb_node field within 'type'.
> + */
> +#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
> +	for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
> +	     pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
> +			typeof(*pos), field); 1; }); \
> +	     pos = n)

So looks like this is something that include/linux/rbtree.h already has, right?

I think we should strive to match the two implementations and generate a build 
time warning (but not a build time failure) if the two diverge.

There were checking facilities added recently for another kernel source code file, 
to make sure tools/perf/util/intel-pt-decoder/insn.c matches arch/x86/lib/insn.c.

Btw., side note, regarding insn.c, the remaining delta between the two files:

-#include <asm/inat.h>
-#include <asm/insn.h>
+#include "inat.h"
+#include "insn.h"

should be eliminated too I think, to make it more obvious when the two versions 
match.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1229082 — Re: [PATCH 1/2] perf tools: Use postorder rbtree iteration when removing symbols

* Alex Snast <asnast@gmail.com> wrote:

> What's the benefit of having that diverge check script as on every commit you'll 
> either add the new stuff to tools/include/linux/rbtree.h or add an exception to 
> that script as in rb_link_node_rcu case.

The benefit is that things do not diverge - diff or md5sum is fast enough.

I don't think exceptions should be added, we should find ways to make the files 
100% identical.

> And are you suggesting to check for divergence for everything under tools/ 
> include/linux recursively?

No, on a case by case basis, for bigger 'facility files' we copied from the kernel 
source.

rbtree.h and rbtree.c certainly applies: for example we've got interval rbtree 
additions in -tip that would be nice to merge upstream:

  tools/kvm/include/kvm/rbtree-interval.h
  tools/kvm/util/rbtree-interval.c

... but which have bitrotten meanwhile, making the copy out of sync and harder to 
merge. Making sure the files are properly upstreamed during build time makes sure 
things don't get out of sync.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web