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

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

[Alex Snast]

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

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

[Alex Snast]

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

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

[Ingo Molnar]

* 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

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

[Ingo Molnar]

* 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