Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1354056
| From | tip-bot for Josh Poimboeuf <tipbot@zytor.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [tip:core/objtool] objtool: Add several performance improvements |
| Date | 2016-03-09 12:50 +0100 |
| Message-ID | <raKMP-7m0-41@gated-at.bofh.it> (permalink) |
| References | <raFtM-3Rr-21@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
Commit-ID: 042ba73fe7eb63872ee2d6ac86410052210c1f16
Gitweb: http://git.kernel.org/tip/042ba73fe7eb63872ee2d6ac86410052210c1f16
Author: Josh Poimboeuf <jpoimboe@redhat.com>
AuthorDate: Wed, 9 Mar 2016 00:07:00 -0600
Committer: Ingo Molnar <mingo@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 <mingo@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@redhat.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Arnaldo Carvalho de Melo <acme@infradead.org>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Bernd Petrovitsch <bernd@petrovitsch.priv.at>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Chris J Arges <chris.j.arges@canonical.com>
Cc: Jiri Slaby <jslaby@suse.cz>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Pedro Alves <palves@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: live-patching@vger.kernel.org
Link: http://lkml.kernel.org/r/dd0d8e1449506cfa7701b4e7ba73577077c44253.1457502970.git.jpoimboe@redhat.com
Signed-off-by: Ingo Molnar <mingo@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);
};
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH 00/11] Various objtool fixes Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[PATCH 01/11] objtool: Prevent infinite recursion in noreturn detection Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Prevent infinite recursion in noreturn detection tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 05/11] objtool: Add helper macros for traversing instructions Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Add helper macros for traversing instructions tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 10/11] objtool: Add several performance improvements Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Add several performance improvements tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 03/11] objtool: Compile with debugging symbols Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Compile with debugging symbols tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 04/11] objtool: Fix false positive warnings related to sibling calls Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Fix false positive warnings related to sibling calls tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 02/11] objtool: Detect infinite recursion Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:10 +0100
[tip:core/objtool] objtool: Detect infinite recursion tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 06/11] objtool: Remove superflous INIT_LIST_HEAD Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
[tip:core/objtool] objtool: Remove superflous INIT_LIST_HEAD tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 07/11] objtool: Rename some variables and functions Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
[tip:core/objtool] objtool: Rename some variables and functions tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 08/11] objtool: Fix false positive warnings for functions with multiple switch statements Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
[tip:core/objtool] objtool: Fix false positive warnings for functions with multiple switch statements tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
[PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 07:20 +0100
Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory Ingo Molnar <mingo@kernel.org> - 2016-03-09 10:50 +0100
Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory Josh Poimboeuf <jpoimboe@redhat.com> - 2016-03-09 17:10 +0100
Re: [PATCH 09/11] tools/objtool: Copy hashtable.h into tools directory Ingo Molnar <mingo@kernel.org> - 2016-03-09 19:50 +0100
[tip:core/objtool] tools: Copy hashtable.h into tools directory tip-bot for Josh Poimboeuf <tipbot@zytor.com> - 2016-03-09 12:50 +0100
csiph-web