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>

1 files changed, 8 insertions, 2 deletions

diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index 57e4653f8383..7f3e00a2f907 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);
 };