LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Peter Zijlstra <peterz@infradead.org>
To: tglx@linutronix.de, jpoimboe@redhat.com
Cc: linux-kernel@vger.kernel.org, x86@kernel.org,
	peterz@infradead.org, mhiramat@kernel.org, mbenes@suse.cz,
	brgerst@gmail.com
Subject: [PATCH v3 06/26] objtool: Optimize find_symbol_by_index()
Date: Tue, 24 Mar 2020 16:31:19 +0100
Message-ID: <20200324160924.261852348@infradead.org> (raw)
In-Reply-To: <20200324153113.098167666@infradead.org>

The symbol index is object wide, not per section, so it makes no sense
to have the symbol_hash be part of the section object. By moving it to
the elf object we avoid the linear sections iteration.

This reduces the runtime of objtool on vmlinux.o from over 3 hours (I
gave up) to a few minutes. The defconfig vmlinux.o has around 20k
sections.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Acked-by: Josh Poimboeuf <jpoimboe@redhat.com>
---
 tools/objtool/elf.c |   13 +++++--------
 tools/objtool/elf.h |    3 +--
 2 files changed, 6 insertions(+), 10 deletions(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -46,13 +46,11 @@ static struct section *find_section_by_i
 
 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
 {
-	struct section *sec;
 	struct symbol *sym;
 
-	list_for_each_entry(sec, &elf->sections, list)
-		hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
-			if (sym->idx == idx)
-				return sym;
+	hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+		if (sym->idx == idx)
+			return sym;
 
 	return NULL;
 }
@@ -166,7 +164,6 @@ 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);
 
@@ -299,7 +296,7 @@ static int read_symbols(struct elf *elf)
 		}
 		sym->alias = alias;
 		list_add(&sym->list, entry);
-		hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
 	}
 
 	/* Create parent/child links for any cold subfunctions */
@@ -425,6 +422,7 @@ struct elf *elf_read(const char *name, i
 	}
 	memset(elf, 0, sizeof(*elf));
 
+	hash_init(elf->symbol_hash);
 	INIT_LIST_HEAD(&elf->sections);
 
 	elf->fd = open(name, flags);
@@ -486,7 +484,6 @@ struct section *elf_create_section(struc
 	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);
 
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -27,7 +27,6 @@ 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;
@@ -71,7 +70,7 @@ struct elf {
 	int fd;
 	char *name;
 	struct list_head sections;
-	DECLARE_HASHTABLE(rela_hash, 16);
+	DECLARE_HASHTABLE(symbol_hash, 20);
 };
 
 



  parent reply index

Thread overview: 89+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-24 15:31 [PATCH v3 00/26] objtool: vmlinux.o and noinstr validation Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 01/26] objtool: Introduce validate_return() Peter Zijlstra
2020-03-25  8:39   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 02/26] objtool: Rename func_for_each_insn() Peter Zijlstra
2020-03-25  8:43   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 03/26] objtool: Rename func_for_each_insn_all() Peter Zijlstra
2020-03-25  8:44   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 04/26] x86/kexec: Use RIP relative addressing Peter Zijlstra
2020-03-25  9:34   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 05/26] x86/kexec: Make relocate_kernel_64.S objtool clean Peter Zijlstra
2020-03-24 20:55   ` Josh Poimboeuf
2020-03-25  9:56   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` Peter Zijlstra [this message]
2020-03-25 10:01   ` [PATCH v3 06/26] objtool: Optimize find_symbol_by_index() Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 07/26] objtool: Add a statistics mode Peter Zijlstra
2020-03-25 10:10   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 08/26] objtool: Optimize find_section_by_index() Peter Zijlstra
2020-03-25 10:12   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 09/26] objtool: Optimize find_section_by_name() Peter Zijlstra
2020-03-25 10:18   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 10/26] objtool: Optimize find_symbol_*() and read_symbols() Peter Zijlstra
2020-03-25 10:20   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 11/26] objtool: Rename find_containing_func() Peter Zijlstra
2020-03-25 10:21   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 12/26] objtool: Resize insn_hash Peter Zijlstra
2020-03-25 10:21   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 13/26] objtool: Optimize find_symbol_by_name() Peter Zijlstra
2020-03-25 10:25   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 14/26] objtool: Optimize read_sections() Peter Zijlstra
2020-03-25 12:10   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-04-21 14:47   ` [PATCH v3 14/26] " youling257
2020-04-21 15:49     ` Peter Zijlstra
2020-04-21 15:57       ` Borislav Petkov
2020-04-21 17:50       ` youling 257
2020-03-24 15:31 ` [PATCH v3 15/26] objtool: Delete cleanup() Peter Zijlstra
2020-03-25 12:11   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 16/26] objtool: Optimize find_rela_by_dest_range() Peter Zijlstra
2020-03-25 12:19   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 17/26] objtool: Re-arrange validate_functions() Peter Zijlstra
2020-03-24 21:10   ` Josh Poimboeuf
2020-03-24 21:15     ` Peter Zijlstra
2020-03-25 12:22   ` Miroslav Benes
2020-03-26 10:08   ` [tip: core/objtool] " tip-bot2 for Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 18/26] objtool: Fix !CFI insn_state propagation Peter Zijlstra
2020-03-24 21:40   ` Josh Poimboeuf
2020-03-24 22:11     ` Peter Zijlstra
2020-03-24 23:00       ` Peter Zijlstra
2020-03-25 14:39         ` Josh Poimboeuf
2020-03-25 14:41   ` [PATCH v3.1 18a/26] objtool: Remove CFI save/restore special case Peter Zijlstra
2020-03-25 14:42   ` [PATCH v3.1 18b/26] objtool: Factor out CFI hints Peter Zijlstra
2020-03-25 14:43   ` [PATCH v3.1 18c/26] objtool: Rename struct cfi_state Peter Zijlstra
2020-03-25 14:43   ` [PATCH v3.1 18d/26] objtool: Fix !CFI insn_state propagation Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 19/26] objtool: Implement noinstr validation Peter Zijlstra
2020-03-24 21:41   ` Josh Poimboeuf
2020-03-25 14:44   ` [PATCH v3.1 " Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 20/26] objtool: Optimize !vmlinux.o again Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 21/26] objtool: Use sec_offset_hash() for insn_hash Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 22/26] objtool: Detect loading function pointers across noinstr Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 23/26] kbuild/objtool: Add objtool-vmlinux.o pass Peter Zijlstra
2020-03-24 22:03   ` Josh Poimboeuf
2020-03-24 22:05     ` Peter Zijlstra
2020-03-24 15:31 ` [PATCH v3 24/26] objtool: Avoid iterating !text section symbols Peter Zijlstra
2020-03-24 22:09   ` Josh Poimboeuf
2020-03-24 15:31 ` [PATCH v3 25/26] objtool: Rearrange validate_section() Peter Zijlstra
2020-03-24 22:10   ` Josh Poimboeuf
2020-03-24 15:31 ` [PATCH v3 26/26] objtool: Add STT_NOTYPE noinstr validation Peter Zijlstra
2020-03-24 22:16   ` Josh Poimboeuf
2020-03-24 22:34     ` Peter Zijlstra
2020-03-25 14:42       ` Josh Poimboeuf
2020-03-25 15:53         ` Peter Zijlstra
2020-03-25 16:40           ` Josh Poimboeuf
2020-03-25 16:50             ` Peter Zijlstra
2020-03-26  8:01               ` Julien Thierry

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200324160924.261852348@infradead.org \
    --to=peterz@infradead.org \
    --cc=brgerst@gmail.com \
    --cc=jpoimboe@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mbenes@suse.cz \
    --cc=mhiramat@kernel.org \
    --cc=tglx@linutronix.de \
    --cc=x86@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git