From 2a362ecc3ec9632aeea4b9a9062db91b2bd9975a Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Thu, 12 Mar 2020 09:34:42 +0100 Subject: objtool: Optimize find_symbol_*() and read_symbols() All of: read_symbols(), find_symbol_by_offset(), find_symbol_containing(), find_containing_func() do a linear search of the symbols. Add an RB tree to make it go faster. This about halves objtool runtime on vmlinux.o, from 34s to 18s. Signed-off-by: Peter Zijlstra (Intel) Reviewed-by: Miroslav Benes Acked-by: Josh Poimboeuf Link: https://lkml.kernel.org/r/20200324160924.499016559@infradead.org --- tools/objtool/Build | 5 ++ tools/objtool/elf.c | 194 ++++++++++++++++++++++++++++++++++++---------------- tools/objtool/elf.h | 3 + 3 files changed, 144 insertions(+), 58 deletions(-) (limited to 'tools/objtool') diff --git a/tools/objtool/Build b/tools/objtool/Build index 8dc4f0848362..66f44f5cd2a6 100644 --- a/tools/objtool/Build +++ b/tools/objtool/Build @@ -11,6 +11,7 @@ objtool-y += objtool.o objtool-y += libstring.o objtool-y += libctype.o objtool-y += str_error_r.o +objtool-y += librbtree.o CFLAGS += -I$(srctree)/tools/lib @@ -25,3 +26,7 @@ $(OUTPUT)libctype.o: ../lib/ctype.c FORCE $(OUTPUT)str_error_r.o: ../lib/str_error_r.c FORCE $(call rule_mkdir) $(call if_changed_dep,cc_o_c) + +$(OUTPUT)librbtree.o: ../lib/rbtree.c FORCE + $(call rule_mkdir) + $(call if_changed_dep,cc_o_c) diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c index 20fe40d5101d..3a8b42672655 100644 --- a/tools/objtool/elf.c +++ b/tools/objtool/elf.c @@ -27,6 +27,90 @@ static inline u32 str_hash(const char *str) return jhash(str, strlen(str), 0); } +static void rb_add(struct rb_root *tree, struct rb_node *node, + int (*cmp)(struct rb_node *, const struct rb_node *)) +{ + struct rb_node **link = &tree->rb_node; + struct rb_node *parent = NULL; + + while (*link) { + parent = *link; + if (cmp(node, parent) < 0) + link = &parent->rb_left; + else + link = &parent->rb_right; + } + + rb_link_node(node, parent, link); + rb_insert_color(node, tree); +} + +static struct rb_node *rb_find_first(struct rb_root *tree, const void *key, + int (*cmp)(const void *key, const struct rb_node *)) +{ + struct rb_node *node = tree->rb_node; + struct rb_node *match = NULL; + + while (node) { + int c = cmp(key, node); + if (c <= 0) { + if (!c) + match = node; + node = node->rb_left; + } else if (c > 0) { + node = node->rb_right; + } + } + + return match; +} + +static struct rb_node *rb_next_match(struct rb_node *node, const void *key, + int (*cmp)(const void *key, const struct rb_node *)) +{ + node = rb_next(node); + if (node && cmp(key, node)) + node = NULL; + return node; +} + +#define rb_for_each(tree, node, key, cmp) \ + for ((node) = rb_find_first((tree), (key), (cmp)); \ + (node); (node) = rb_next_match((node), (key), (cmp))) + +static int symbol_to_offset(struct rb_node *a, const struct rb_node *b) +{ + struct symbol *sa = rb_entry(a, struct symbol, node); + struct symbol *sb = rb_entry(b, struct symbol, node); + + if (sa->offset < sb->offset) + return -1; + if (sa->offset > sb->offset) + return 1; + + if (sa->len < sb->len) + return -1; + if (sa->len > sb->len) + return 1; + + sa->alias = sb; + + return 0; +} + +static int symbol_by_offset(const void *key, const struct rb_node *node) +{ + const struct symbol *s = rb_entry(node, struct symbol, node); + const unsigned long *o = key; + + if (*o < s->offset) + return -1; + if (*o > s->offset + s->len) + return 1; + + return 0; +} + struct section *find_section_by_name(struct elf *elf, const char *name) { struct section *sec; @@ -63,47 +147,69 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx) struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset) { - struct symbol *sym; + struct rb_node *node; - list_for_each_entry(sym, &sec->symbol_list, list) - if (sym->type != STT_SECTION && sym->offset == offset) - return sym; + rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { + struct symbol *s = rb_entry(node, struct symbol, node); + + if (s->offset == offset && s->type != STT_SECTION) + return s; + } return NULL; } struct symbol *find_func_by_offset(struct section *sec, unsigned long offset) { - struct symbol *sym; + struct rb_node *node; - list_for_each_entry(sym, &sec->symbol_list, list) - if (sym->type == STT_FUNC && sym->offset == offset) - return sym; + rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { + struct symbol *s = rb_entry(node, struct symbol, node); + + if (s->offset == offset && s->type == STT_FUNC) + return s; + } return NULL; } -struct symbol *find_symbol_by_name(struct elf *elf, const char *name) +struct symbol *find_symbol_containing(struct section *sec, unsigned long offset) { - struct section *sec; - struct symbol *sym; + struct rb_node *node; - list_for_each_entry(sec, &elf->sections, list) - list_for_each_entry(sym, &sec->symbol_list, list) - if (!strcmp(sym->name, name)) - return sym; + rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { + struct symbol *s = rb_entry(node, struct symbol, node); + + if (s->type != STT_SECTION) + return s; + } return NULL; } -struct symbol *find_symbol_containing(struct section *sec, unsigned long offset) +struct symbol *find_containing_func(struct section *sec, unsigned long offset) +{ + struct rb_node *node; + + rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { + struct symbol *s = rb_entry(node, struct symbol, node); + + if (s->type == STT_FUNC) + return s; + } + + return NULL; +} + +struct symbol *find_symbol_by_name(struct elf *elf, const char *name) { + struct section *sec; struct symbol *sym; - list_for_each_entry(sym, &sec->symbol_list, list) - if (sym->type != STT_SECTION && - offset >= sym->offset && offset < sym->offset + sym->len) - return sym; + list_for_each_entry(sec, &elf->sections, list) + list_for_each_entry(sym, &sec->symbol_list, list) + if (!strcmp(sym->name, name)) + return sym; return NULL; } @@ -130,18 +236,6 @@ struct rela *find_rela_by_dest(struct section *sec, unsigned long offset) return find_rela_by_dest_range(sec, offset, 1); } -struct symbol *find_containing_func(struct section *sec, unsigned long offset) -{ - struct symbol *func; - - list_for_each_entry(func, &sec->symbol_list, list) - if (func->type == STT_FUNC && offset >= func->offset && - offset < func->offset + func->len) - return func; - - return NULL; -} - static int read_sections(struct elf *elf) { Elf_Scn *s = NULL; @@ -225,8 +319,9 @@ static int read_sections(struct elf *elf) static int read_symbols(struct elf *elf) { struct section *symtab, *sec; - struct symbol *sym, *pfunc, *alias; - struct list_head *entry, *tmp; + struct symbol *sym, *pfunc; + struct list_head *entry; + struct rb_node *pnode; int symbols_nr, i; char *coldstr; @@ -245,7 +340,7 @@ static int read_symbols(struct elf *elf) return -1; } memset(sym, 0, sizeof(*sym)); - alias = sym; + sym->alias = sym; sym->idx = i; @@ -283,29 +378,12 @@ static int read_symbols(struct elf *elf) sym->offset = sym->sym.st_value; sym->len = sym->sym.st_size; - /* sorted insert into a per-section list */ - entry = &sym->sec->symbol_list; - list_for_each_prev(tmp, &sym->sec->symbol_list) { - struct symbol *s; - - s = list_entry(tmp, struct symbol, list); - - if (sym->offset > s->offset) { - entry = tmp; - break; - } - - if (sym->offset == s->offset) { - if (sym->len && sym->len == s->len && alias == sym) - alias = s; - - if (sym->len >= s->len) { - entry = tmp; - break; - } - } - } - sym->alias = alias; + rb_add(&sym->sec->symbol_tree, &sym->node, symbol_to_offset); + pnode = rb_prev(&sym->node); + if (pnode) + entry = &rb_entry(pnode, struct symbol, node)->list; + else + entry = &sym->sec->symbol_list; list_add(&sym->list, entry); hash_add(elf->symbol_hash, &sym->hash, sym->idx); } diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h index ac7c46f7d9ab..e4a8d68f2ef7 100644 --- a/tools/objtool/elf.h +++ b/tools/objtool/elf.h @@ -10,6 +10,7 @@ #include #include #include +#include #include #ifdef LIBELF_USE_DEPRECATED @@ -29,6 +30,7 @@ struct section { struct hlist_node hash; struct hlist_node name_hash; GElf_Shdr sh; + struct rb_root symbol_tree; struct list_head symbol_list; struct list_head rela_list; DECLARE_HASHTABLE(rela_hash, 16); @@ -43,6 +45,7 @@ struct section { struct symbol { struct list_head list; + struct rb_node node; struct hlist_node hash; GElf_Sym sym; struct section *sec; -- cgit v1.2.3