Commit-ID: 042ba73fe7eb63872ee2d6ac86410052210c1f16 Gitweb: http://git.kernel.org/tip/042ba73fe7eb63872ee2d6ac86410052210c1f16 Author: Josh Poimboeuf <jpoim...@redhat.com> AuthorDate: Wed, 9 Mar 2016 00:07:00 -0600 Committer: Ingo Molnar <mi...@kernel.org> CommitDate: Wed, 9 Mar 2016 10:48:10 +0100
objtool: Add several performance improvements Use hash tables for instruction and rela lookups (and keep the linked lists around for sequential access). Also cache the section struct for the "__func_stack_frame_non_standard" section. With this change, "objtool check net/wireless/nl80211.o" goes from: real 0m1.168s user 0m1.163s sys 0m0.005s to: real 0m0.059s user 0m0.042s sys 0m0.017s for a 20x speedup. With the same object, it should be noted that the memory heap usage grew from 8MB to 62MB. Reducing the memory usage is on the TODO list. Reported-by: Ingo Molnar <mi...@kernel.org> Signed-off-by: Josh Poimboeuf <jpoim...@redhat.com> Cc: Andrew Morton <a...@linux-foundation.org> Cc: Andy Lutomirski <l...@kernel.org> Cc: Arnaldo Carvalho de Melo <a...@infradead.org> Cc: Arnaldo Carvalho de Melo <a...@kernel.org> Cc: Bernd Petrovitsch <be...@petrovitsch.priv.at> Cc: Borislav Petkov <b...@alien8.de> Cc: Chris J Arges <chris.j.ar...@canonical.com> Cc: Jiri Slaby <jsl...@suse.cz> Cc: Linus Torvalds <torva...@linux-foundation.org> Cc: Michal Marek <mma...@suse.cz> Cc: Namhyung Kim <namhy...@gmail.com> Cc: Pedro Alves <pal...@redhat.com> Cc: Peter Zijlstra <pet...@infradead.org> Cc: Thomas Gleixner <t...@linutronix.de> Cc: live-patch...@vger.kernel.org Link: http://lkml.kernel.org/r/dd0d8e1449506cfa7701b4e7ba73577077c44253.1457502970.git.jpoim...@redhat.com Signed-off-by: Ingo Molnar <mi...@kernel.org> --- tools/objtool/builtin-check.c | 18 ++++++++++++------ tools/objtool/elf.c | 21 +++++++++++++++------ tools/objtool/elf.h | 10 ++++++++-- 3 files changed, 35 insertions(+), 14 deletions(-) diff --git a/tools/objtool/builtin-check.c b/tools/objtool/builtin-check.c index cf1e48d..bfeee22 100644 --- a/tools/objtool/builtin-check.c +++ b/tools/objtool/builtin-check.c @@ -34,6 +34,8 @@ #include "arch.h" #include "warn.h" +#include <linux/hashtable.h> + #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) #define STATE_FP_SAVED 0x1 @@ -42,6 +44,7 @@ struct instruction { struct list_head list; + struct hlist_node hash; struct section *sec; unsigned long offset; unsigned int len, state; @@ -61,7 +64,8 @@ struct alternative { struct objtool_file { struct elf *elf; struct list_head insn_list; - struct section *rodata; + DECLARE_HASHTABLE(insn_hash, 16); + struct section *rodata, *whitelist; }; const char *objname; @@ -72,7 +76,7 @@ static struct instruction *find_insn(struct objtool_file *file, { struct instruction *insn; - list_for_each_entry(insn, &file->insn_list, list) + hash_for_each_possible(file->insn_hash, insn, hash, offset) if (insn->sec == sec && insn->offset == offset) return insn; @@ -111,14 +115,12 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file, */ static bool ignore_func(struct objtool_file *file, struct symbol *func) { - struct section *macro_sec; struct rela *rela; struct instruction *insn; /* check for STACK_FRAME_NON_STANDARD */ - macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard"); - if (macro_sec && macro_sec->rela) - list_for_each_entry(rela, ¯o_sec->rela->rela_list, list) + if (file->whitelist && file->whitelist->rela) + list_for_each_entry(rela, &file->whitelist->rela->rela_list, list) if (rela->sym->sec == func->sec && rela->addend == func->offset) return true; @@ -276,6 +278,7 @@ static int decode_instructions(struct objtool_file *file) return -1; } + hash_add(file->insn_hash, &insn->hash, insn->offset); list_add_tail(&insn->list, &file->insn_list); } } @@ -729,6 +732,7 @@ static int decode_sections(struct objtool_file *file) { int ret; + file->whitelist = find_section_by_name(file->elf, "__func_stack_frame_non_standard"); file->rodata = find_section_by_name(file->elf, ".rodata"); ret = decode_instructions(file); @@ -1091,6 +1095,7 @@ static void cleanup(struct objtool_file *file) free(alt); } list_del(&insn->list); + hash_del(&insn->hash); free(insn); } elf_close(file->elf); @@ -1125,6 +1130,7 @@ int cmd_check(int argc, const char **argv) } INIT_LIST_HEAD(&file.insn_list); + hash_init(file.insn_hash); ret = decode_sections(&file); if (ret < 0) diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c index 7de243f..e11f6b6 100644 --- a/tools/objtool/elf.c +++ b/tools/objtool/elf.c @@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx) struct symbol *sym; list_for_each_entry(sec, &elf->sections, list) - list_for_each_entry(sym, &sec->symbol_list, list) + hash_for_each_possible(sec->symbol_hash, sym, hash, idx) if (sym->idx == idx) return sym; @@ -82,13 +82,15 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset, unsigned int len) { struct rela *rela; + unsigned long o; if (!sec->rela) return NULL; - list_for_each_entry(rela, &sec->rela->rela_list, list) - if (rela->offset >= offset && rela->offset < offset + len) - return rela; + for (o = offset; o < offset + len; o++) + hash_for_each_possible(sec->rela->rela_hash, rela, hash, o) + if (rela->offset == o) + return rela; return NULL; } @@ -137,6 +139,8 @@ static int read_sections(struct elf *elf) INIT_LIST_HEAD(&sec->symbol_list); INIT_LIST_HEAD(&sec->rela_list); + hash_init(sec->rela_hash); + hash_init(sec->symbol_hash); list_add_tail(&sec->list, &elf->sections); @@ -261,6 +265,7 @@ static int read_symbols(struct elf *elf) } } list_add(&sym->list, entry); + hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx); } return 0; @@ -298,8 +303,6 @@ static int read_relas(struct elf *elf) } memset(rela, 0, sizeof(*rela)); - list_add_tail(&rela->list, &sec->rela_list); - if (!gelf_getrela(sec->elf_data, i, &rela->rela)) { perror("gelf_getrela"); return -1; @@ -315,6 +318,10 @@ static int read_relas(struct elf *elf) symndx, sec->name); return -1; } + + list_add_tail(&rela->list, &sec->rela_list); + hash_add(sec->rela_hash, &rela->hash, rela->offset); + } } @@ -384,10 +391,12 @@ void elf_close(struct elf *elf) list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) { list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) { list_del(&sym->list); + hash_del(&sym->hash); free(sym); } list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) { list_del(&rela->list); + hash_del(&rela->hash); free(rela); } list_del(&sec->list); diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h index 57e4653..7f3e00a 100644 --- a/tools/objtool/elf.h +++ b/tools/objtool/elf.h @@ -21,12 +21,15 @@ #include <stdio.h> #include <gelf.h> #include <linux/list.h> +#include <linux/hashtable.h> struct section { struct list_head list; GElf_Shdr sh; struct list_head symbol_list; + DECLARE_HASHTABLE(symbol_hash, 8); struct list_head rela_list; + DECLARE_HASHTABLE(rela_hash, 16); struct section *base, *rela; struct symbol *sym; Elf_Data *elf_data; @@ -38,10 +41,11 @@ struct section { struct symbol { struct list_head list; + struct hlist_node hash; GElf_Sym sym; struct section *sec; char *name; - int idx; + unsigned int idx; unsigned char bind, type; unsigned long offset; unsigned int len; @@ -49,10 +53,11 @@ struct symbol { struct rela { struct list_head list; + struct hlist_node hash; GElf_Rela rela; struct symbol *sym; unsigned int type; - int offset; + unsigned long offset; int addend; }; @@ -62,6 +67,7 @@ struct elf { int fd; char *name; struct list_head sections; + DECLARE_HASHTABLE(rela_hash, 16); };
