perf tools: Use postorder rbtree iteration when removing symbols
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
@@ -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
@@ -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
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
@@ -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
Quoted 22 lines · Alex Snast
Avoid using
rb_erasewhen removing symbols as it requires rbtree rebalancing, instead preform a post order iteration when deleting tree symbols.Signed-off-by Alex Snast <[email protected]>--- 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@@ -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
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.hor add an exception to that script as inrb_link_node_rcucase.
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/linuxrecursively?
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