Skip to contentSkip to conversation

perf tools: Use postorder rbtree iteration when removing symbols

PATCH In review Alex Snast 2 participants 4 messages Sep 19, 2015 – Sep 21, 2015 1 message not in the archive perf events

lore
Share & tools
lore

Alex Snast

author
#0 lore raw

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.

---
 tools/include/linux/rbtree.h | 14 ++++++++++++++
 tools/perf/util/symbol.c     | 11 ++++-------
 2 files changed, 18 insertions(+), 7 deletions(-)
tools/include/linux/rbtree.h +14 -0
index 1125822..14c646d 100644
@@ -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
tools/perf/util/symbol.c +4 -7
index 1f97ffb..8b3608c 100644
@@ -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)
Signature · 1 line
2.1.4
author
#1 lore raw

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

---
 tools/perf/util/symbol.c | 10 ++--------
 1 file changed, 2 insertions(+), 8 deletions(-)
tools/perf/util/symbol.c +2 -8
index 8b3608c..5728121 100644
@@ -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 {
Signature · 1 line
2.1.4
#2 lore raw
In reply to Alex Snast
Quoted 22 lines · Alex Snast

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

---
 tools/include/linux/rbtree.h | 14 ++++++++++++++
 tools/perf/util/symbol.c     | 11 ++++-------
 2 files changed, 18 insertions(+), 7 deletions(-)
tools/include/linux/rbtree.h +4 -0
index 1125822..14c646d 100644
@@ -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
+ *

tools/include/linux/rbtree.h static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, · line 106

Quoted 10 lines
tools/include/linux/rbtree.h +10 -0
+ * @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

A message that is not in the archive (sent off-list or not yet received): CAMqsXBcZAS6hCh8LdHjFGiji8dwHLQus1xf5OnK7CZEjrbx33w@mail.gmail.com

#4 lore raw
Quoted 3 lines · Alex Snast

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.

Quoted 2 lines

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