At the cost of an extra pointer, we can avoid the O(logN) cost of finding the first element in the tree (smallest node).
Signed-off-by: Davidlohr Bueso <[email protected]> --- tools/perf/builtin-annotate.c | 2 +- tools/perf/builtin-report.c | 2 +- tools/perf/builtin-top.c | 4 +- tools/perf/tests/vmlinux-kallsyms.c | 3 +- tools/perf/util/dso.c | 5 ++- tools/perf/util/dso.h | 4 +- tools/perf/util/map.c | 8 ++-- tools/perf/util/probe-event.c | 3 +- tools/perf/util/symbol.c | 85 ++++++++++++++++++++----------------- tools/perf/util/symbol.h | 12 +++--- tools/perf/util/symbol_fprintf.c | 3 +- 11 files changed, 71 insertions(+), 60 deletions(-) diff --git a/tools/perf/builtin-annotate.c b/tools/perf/builtin-annotate.c index f15731a3d438..2c2c265a0eb7 100644 --- a/tools/perf/builtin-annotate.c +++ b/tools/perf/builtin-annotate.c @@ -164,7 +164,7 @@ static int perf_evsel__add_sample(struct perf_evsel *evsel, * the DSO? */ if (al->sym != NULL) { - rb_erase(&al->sym->rb_node, + rb_erase_cached(&al->sym->rb_node, &al->map->dso->symbols[al->map->type]); symbol__delete(al->sym); dso__reset_find_symbol_cache(al->map->dso); diff --git a/tools/perf/builtin-report.c b/tools/perf/builtin-report.c index af5dd038195e..713dcadd22b5 100644 --- a/tools/perf/builtin-report.c +++ b/tools/perf/builtin-report.c @@ -454,7 +454,7 @@ static void report__warn_kptr_restrict(const struct report *rep) if (kernel_map) { const struct dso *kdso = kernel_map->dso; - if (!RB_EMPTY_ROOT(&kdso->symbols[MAP__FUNCTION])) { + if (!RB_EMPTY_ROOT(&kdso->symbols[MAP__FUNCTION].rb_root)) { desc = "If some relocation was applied (e.g. " "kexec) symbols may be misresolved."; } diff --git a/tools/perf/builtin-top.c b/tools/perf/builtin-top.c index 0077724fb24f..c3030a05ed77 100644 --- a/tools/perf/builtin-top.c +++ b/tools/perf/builtin-top.c @@ -740,7 +740,7 @@ static void perf_event__process_sample(struct perf_tool *tool, "Kernel address maps (/proc/{kallsyms,modules}) are restricted.\n\n" "Check /proc/sys/kernel/kptr_restrict.\n\n" "Kernel%s samples will not be resolved.\n", - al.map && !RB_EMPTY_ROOT(&al.map->dso->symbols[MAP__FUNCTION]) ? + al.map && !RB_EMPTY_ROOT(&al.map->dso->symbols[MAP__FUNCTION].rb_root) ? " modules" : ""); if (use_browser <= 0) sleep(5); @@ -763,7 +763,7 @@ static void perf_event__process_sample(struct perf_tool *tool, */ if (!machine->kptr_restrict_warned && !top->vmlinux_warned && al.map == machine->vmlinux_maps[MAP__FUNCTION] && - RB_EMPTY_ROOT(&al.map->dso->symbols[MAP__FUNCTION])) { + RB_EMPTY_ROOT(&al.map->dso->symbols[MAP__FUNCTION].rb_root)) { if (symbol_conf.vmlinux_name) { char serr[256]; dso__strerror_load(al.map->dso, serr, sizeof(serr)); diff --git a/tools/perf/tests/vmlinux-kallsyms.c b/tools/perf/tests/vmlinux-kallsyms.c index f6789fb029d6..b90eb714fd18 100644 --- a/tools/perf/tests/vmlinux-kallsyms.c +++ b/tools/perf/tests/vmlinux-kallsyms.c @@ -108,7 +108,8 @@ int test__vmlinux_matches_kallsyms(struct test *test __maybe_unused, int subtest * in the kallsyms dso. For the ones that are in both, check its names and * end addresses too. */ - for (nd = rb_first(&vmlinux_map->dso->symbols[type]); nd; nd = rb_next(nd)) { + for (nd = rb_first_cached(&vmlinux_map->dso->symbols[type]); + nd; nd = rb_next(nd)) { struct symbol *pair, *first_pair; sym = rb_entry(nd, struct symbol, rb_node); diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c index 7b1f56a6d3fd..45d96ef7bbcd 100644 --- a/tools/perf/util/dso.c +++ b/tools/perf/util/dso.c @@ -1201,7 +1201,8 @@ struct dso *dso__new(const char *name) dso__set_long_name(dso, dso->name, false); dso__set_short_name(dso, dso->name, false); for (i = 0; i < MAP__NR_TYPES; ++i) - dso->symbols[i] = dso->symbol_names[i] = RB_ROOT; + dso->symbols[i] = dso->symbol_names[i] = RB_ROOT_CACHED; + dso->data.cache = RB_ROOT; dso->inlined_nodes = RB_ROOT; dso->srclines = RB_ROOT_CACHED; @@ -1478,7 +1479,7 @@ size_t dso__fprintf(struct dso *dso, enum map_type type, FILE *fp) dso__loaded(dso, type) ? "" : "NOT "); ret += dso__fprintf_buildid(dso, fp); ret += fprintf(fp, ")\n"); - for (nd = rb_first(&dso->symbols[type]); nd; nd = rb_next(nd)) { + for (nd = rb_first_cached(&dso->symbols[type]); nd; nd = rb_next(nd)) { struct symbol *pos = rb_entry(nd, struct symbol, rb_node); ret += symbol__fprintf(pos, fp); } diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h index 620b38d763d9..6fa036849b66 100644 --- a/tools/perf/util/dso.h +++ b/tools/perf/util/dso.h @@ -140,8 +140,8 @@ struct dso { struct list_head node; struct rb_node rb_node; /* rbtree node sorted by long name */ struct rb_root *root; /* root of rbtree that rb_node is in */ - struct rb_root symbols[MAP__NR_TYPES]; - struct rb_root symbol_names[MAP__NR_TYPES]; + struct rb_root_cached symbols[MAP__NR_TYPES]; + struct rb_root_cached symbol_names[MAP__NR_TYPES]; struct rb_root inlined_nodes; struct rb_root_cached srclines; struct { diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c index 6d40efd74402..78326bbf5892 100644 --- a/tools/perf/util/map.c +++ b/tools/perf/util/map.c @@ -279,8 +279,8 @@ void map__put(struct map *map) void map__fixup_start(struct map *map) { - struct rb_root *symbols = &map->dso->symbols[map->type]; - struct rb_node *nd = rb_first(symbols); + struct rb_root_cached *symbols = &map->dso->symbols[map->type]; + struct rb_node *nd = rb_first_cached(symbols); if (nd != NULL) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->start = sym->start; @@ -289,8 +289,8 @@ void map__fixup_start(struct map *map) void map__fixup_end(struct map *map) { - struct rb_root *symbols = &map->dso->symbols[map->type]; - struct rb_node *nd = rb_last(symbols); + struct rb_root_cached *symbols = &map->dso->symbols[map->type]; + struct rb_node *nd = rb_last(&symbols->rb_root); if (nd != NULL) { struct symbol *sym = rb_entry(nd, struct symbol, rb_node); map->end = sym->end; diff --git a/tools/perf/util/probe-event.c b/tools/perf/util/probe-event.c index b7aaf9b2294d..3ab084e24265 100644 --- a/tools/perf/util/probe-event.c +++ b/tools/perf/util/probe-event.c @@ -3473,7 +3473,8 @@ int show_available_funcs(const char *target, struct nsinfo *nsi, /* Show all (filtered) symbols */ setup_pager(); - for (nd = rb_first(&map->dso->symbol_names[map->type]); nd; nd = rb_next(nd)) { + for (nd = rb_first_cached(&map->dso->symbol_names[map->type]); + nd; nd = rb_next(nd)) { struct symbol_name_rb_node *pos = rb_entry(nd, struct symbol_name_rb_node, rb_node); if (strfilter__compare(_filter, pos->sym.name)) diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c index 1b67a8639dfe..b5746b76942d 100644 --- a/tools/perf/util/symbol.c +++ b/tools/perf/util/symbol.c @@ -166,7 +166,7 @@ static int choose_best_symbol(struct symbol *syma, struct symbol *symb) return arch__choose_best_symbol(syma, symb); } -void symbols__fixup_duplicate(struct rb_root *symbols) +void symbols__fixup_duplicate(struct rb_root_cached *symbols) { struct rb_node *nd; struct symbol *curr, *next; @@ -174,7 +174,7 @@ void symbols__fixup_duplicate(struct rb_root *symbols) if (symbol_conf.allow_aliases) return; - nd = rb_first(symbols); + nd = rb_first_cached(symbols); while (nd) { curr = rb_entry(nd, struct symbol, rb_node); @@ -189,20 +189,20 @@ void symbols__fixup_duplicate(struct rb_root *symbols) continue; if (choose_best_symbol(curr, next) == SYMBOL_A) { - rb_erase(&next->rb_node, symbols); + rb_erase_cached(&next->rb_node, symbols); symbol__delete(next); goto again; } else { nd = rb_next(&curr->rb_node); - rb_erase(&curr->rb_node, symbols); + rb_erase_cached(&curr->rb_node, symbols); symbol__delete(curr); } } } -void symbols__fixup_end(struct rb_root *symbols) +void symbols__fixup_end(struct rb_root_cached *symbols) { - struct rb_node *nd, *prevnd = rb_first(symbols); + struct rb_node *nd, *prevnd = rb_first_cached(symbols); struct symbol *curr, *prev; if (prevnd == NULL) @@ -284,25 +284,26 @@ void symbol__delete(struct symbol *sym) free(((void *)sym) - symbol_conf.priv_size); } -void symbols__delete(struct rb_root *symbols) +void symbols__delete(struct rb_root_cached *symbols) { struct symbol *pos; - struct rb_node *next = rb_first(symbols); + struct rb_node *next = rb_first_cached(symbols); while (next) { pos = rb_entry(next, struct symbol, rb_node); next = rb_next(&pos->rb_node); - rb_erase(&pos->rb_node, symbols); + rb_erase_cached(&pos->rb_node, symbols); symbol__delete(pos); } } -void __symbols__insert(struct rb_root *symbols, struct symbol *sym, bool kernel) +void __symbols__insert(struct rb_root_cached *symbols, struct symbol *sym, bool kernel) { - struct rb_node **p = &symbols->rb_node; + struct rb_node **p = &symbols->rb_root.rb_node; struct rb_node *parent = NULL; const u64 ip = sym->start; struct symbol *s; + bool leftmost = true; if (kernel) { const char *name = sym->name; @@ -320,26 +321,28 @@ void __symbols__insert(struct rb_root *symbols, struct symbol *sym, bool kernel) s = rb_entry(parent, struct symbol, rb_node); if (ip < s->start) p = &(*p)->rb_left; - else + else { p = &(*p)->rb_right; + leftmost = false; + } } rb_link_node(&sym->rb_node, parent, p); - rb_insert_color(&sym->rb_node, symbols); + rb_insert_color_cached(&sym->rb_node, symbols, leftmost); } -void symbols__insert(struct rb_root *symbols, struct symbol *sym) +void symbols__insert(struct rb_root_cached *symbols, struct symbol *sym) { __symbols__insert(symbols, sym, false); } -static struct symbol *symbols__find(struct rb_root *symbols, u64 ip) +static struct symbol *symbols__find(struct rb_root_cached *symbols, u64 ip) { struct rb_node *n; if (symbols == NULL) return NULL; - n = symbols->rb_node; + n = symbols->rb_root.rb_node; while (n) { struct symbol *s = rb_entry(n, struct symbol, rb_node); @@ -355,9 +358,9 @@ static struct symbol *symbols__find(struct rb_root *symbols, u64 ip) return NULL; } -static struct symbol *symbols__first(struct rb_root *symbols) +static struct symbol *symbols__first(struct rb_root_cached *symbols) { - struct rb_node *n = rb_first(symbols); + struct rb_node *n = rb_first_cached(symbols); if (n) return rb_entry(n, struct symbol, rb_node); @@ -365,9 +368,9 @@ static struct symbol *symbols__first(struct rb_root *symbols) return NULL; } -static struct symbol *symbols__last(struct rb_root *symbols) +static struct symbol *symbols__last(struct rb_root_cached *symbols) { - struct rb_node *n = rb_last(symbols); + struct rb_node *n = rb_last(&symbols->rb_root); if (n) return rb_entry(n, struct symbol, rb_node); @@ -385,11 +388,12 @@ static struct symbol *symbols__next(struct symbol *sym) return NULL; } -static void symbols__insert_by_name(struct rb_root *symbols, struct symbol *sym) +static void symbols__insert_by_name(struct rb_root_cached *symbols, struct symbol *sym) { - struct rb_node **p = &symbols->rb_node; + struct rb_node **p = &symbols->rb_root.rb_node; struct rb_node *parent = NULL; struct symbol_name_rb_node *symn, *s; + bool leftmost = true; symn = container_of(sym, struct symbol_name_rb_node, sym); @@ -398,19 +402,21 @@ static void symbols__insert_by_name(struct rb_root *symbols, struct symbol *sym) s = rb_entry(parent, struct symbol_name_rb_node, rb_node); if (strcmp(sym->name, s->sym.name) < 0) p = &(*p)->rb_left; - else + else { p = &(*p)->rb_right; + leftmost = false; + } } rb_link_node(&symn->rb_node, parent, p); - rb_insert_color(&symn->rb_node, symbols); + rb_insert_color_cached(&symn->rb_node, symbols, leftmost); } -static void symbols__sort_by_name(struct rb_root *symbols, - struct rb_root *source) +static void symbols__sort_by_name(struct rb_root_cached *symbols, + struct rb_root_cached *source) { struct rb_node *nd; - for (nd = rb_first(source); nd; nd = rb_next(nd)) { + for (nd = rb_first_cached(source); nd; nd = rb_next(nd)) { struct symbol *pos = rb_entry(nd, struct symbol, rb_node); symbols__insert_by_name(symbols, pos); } @@ -433,7 +439,7 @@ int symbol__match_symbol_name(const char *name, const char *str, return arch__compare_symbol_names(name, str); } -static struct symbol *symbols__find_by_name(struct rb_root *symbols, +static struct symbol *symbols__find_by_name(struct rb_root_cached *symbols, const char *name, enum symbol_tag_include includes) { @@ -443,7 +449,7 @@ static struct symbol *symbols__find_by_name(struct rb_root *symbols, if (symbols == NULL) return NULL; - n = symbols->rb_node; + n = symbols->rb_root.rb_node; while (n) { int cmp; @@ -657,7 +663,7 @@ static int map__process_kallsym_symbol(void *arg, const char *name, { struct symbol *sym; struct process_kallsyms_args *a = arg; - struct rb_root *root = &a->dso->symbols[a->map->type]; + struct rb_root_cached *root = &a->dso->symbols[a->map->type]; if (!symbol_type__is_a(type, a->map->type)) return 0; @@ -697,14 +703,14 @@ static int dso__split_kallsyms_for_kcore(struct dso *dso, struct map *map) struct map *curr_map; struct symbol *pos; int count = 0; - struct rb_root old_root = dso->symbols[map->type]; - struct rb_root *root = &dso->symbols[map->type]; - struct rb_node *next = rb_first(root); + struct rb_root_cached old_root = dso->symbols[map->type]; + struct rb_root_cached *root = &dso->symbols[map->type]; + struct rb_node *next = rb_first_cached(root); if (!kmaps) return -1; - *root = RB_ROOT; + *root = RB_ROOT_CACHED; while (next) { char *module; @@ -712,7 +718,8 @@ static int dso__split_kallsyms_for_kcore(struct dso *dso, struct map *map) pos = rb_entry(next, struct symbol, rb_node); next = rb_next(&pos->rb_node); - rb_erase_init(&pos->rb_node, &old_root); + rb_erase_cached(&pos->rb_node, &old_root); + RB_CLEAR_NODE(&pos->rb_node); module = strchr(pos->name, '\t'); if (module) @@ -750,8 +757,8 @@ static int dso__split_kallsyms(struct dso *dso, struct map *map, u64 delta) struct map *curr_map = map; struct symbol *pos; int count = 0, moved = 0; - struct rb_root *root = &dso->symbols[map->type]; - struct rb_node *next = rb_first(root); + struct rb_root_cached *root = &dso->symbols[map->type]; + struct rb_node *next = rb_first_cached(root); int kernel_range = 0; if (!kmaps) @@ -854,7 +861,7 @@ static int dso__split_kallsyms(struct dso *dso, struct map *map, u64 delta) } add_symbol: if (curr_map != map) { - rb_erase(&pos->rb_node, root); + rb_erase_cached(&pos->rb_node, root); symbols__insert(&curr_map->dso->symbols[curr_map->type], pos); ++moved; } else @@ -862,7 +869,7 @@ static int dso__split_kallsyms(struct dso *dso, struct map *map, u64 delta) continue; discard_symbol: - rb_erase(&pos->rb_node, root); + rb_erase_cached(&pos->rb_node, root); symbol__delete(pos); } diff --git a/tools/perf/util/symbol.h b/tools/perf/util/symbol.h index a4f0075b4e5c..c066c58bc935 100644 --- a/tools/perf/util/symbol.h +++ b/tools/perf/util/symbol.h @@ -66,7 +66,7 @@ struct symbol { }; void symbol__delete(struct symbol *sym); -void symbols__delete(struct rb_root *symbols); +void symbols__delete(struct rb_root_cached *symbols); /* symbols__for_each_entry - iterate over symbols (rb_root) * @@ -75,7 +75,7 @@ void symbols__delete(struct rb_root *symbols); * @nd: the 'struct rb_node *' to use as a temporary storage */ #define symbols__for_each_entry(symbols, pos, nd) \ - for (nd = rb_first(symbols); \ + for (nd = rb_first_cached(symbols); \ nd && (pos = rb_entry(nd, struct symbol, rb_node)); \ nd = rb_next(nd)) @@ -312,10 +312,10 @@ int dso__synthesize_plt_symbols(struct dso *dso, struct symsrc *ss, char *dso__demangle_sym(struct dso *dso, int kmodule, const char *elf_name); -void __symbols__insert(struct rb_root *symbols, struct symbol *sym, bool kernel); -void symbols__insert(struct rb_root *symbols, struct symbol *sym); -void symbols__fixup_duplicate(struct rb_root *symbols); -void symbols__fixup_end(struct rb_root *symbols); +void __symbols__insert(struct rb_root_cached *symbols, struct symbol *sym, bool kernel); +void symbols__insert(struct rb_root_cached *symbols, struct symbol *sym); +void symbols__fixup_duplicate(struct rb_root_cached *symbols); +void symbols__fixup_end(struct rb_root_cached *symbols); void __map_groups__fixup_end(struct map_groups *mg, enum map_type type); typedef int (*mapfn_t)(u64 start, u64 len, u64 pgoff, void *data); diff --git a/tools/perf/util/symbol_fprintf.c b/tools/perf/util/symbol_fprintf.c index 6dd2cb88ccbe..f4f517cc3c49 100644 --- a/tools/perf/util/symbol_fprintf.c +++ b/tools/perf/util/symbol_fprintf.c @@ -64,7 +64,8 @@ size_t dso__fprintf_symbols_by_name(struct dso *dso, struct rb_node *nd; struct symbol_name_rb_node *pos; - for (nd = rb_first(&dso->symbol_names[type]); nd; nd = rb_next(nd)) { + for (nd = rb_first_cached(&dso->symbol_names[type]); + nd; nd = rb_next(nd)) { pos = rb_entry(nd, struct symbol_name_rb_node, rb_node); fprintf(fp, "%s\n", pos->sym.name); } -- 2.13.6
