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 13/26] objtool: Optimize find_symbol_by_name()
Date: Tue, 24 Mar 2020 16:31:26 +0100
Message-ID: <20200324160924.676865656@infradead.org> (raw)
In-Reply-To: <20200324153113.098167666@infradead.org>

Perf showed that find_symbol_by_name() takes time; add a symbol name
hash.

This shaves another second off of objtool on vmlinux.o runtime, down
to 15 seconds.

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

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -203,13 +203,11 @@ struct symbol *find_func_containing(stru
 
 struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
 {
-	struct section *sec;
 	struct symbol *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;
+	hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+		if (!strcmp(sym->name, name))
+			return sym;
 
 	return NULL;
 }
@@ -386,6 +384,7 @@ static int read_symbols(struct elf *elf)
 			entry = &sym->sec->symbol_list;
 		list_add(&sym->list, entry);
 		hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+		hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
 	}
 
 	if (stats)
@@ -524,6 +523,7 @@ struct elf *elf_read(const char *name, i
 	memset(elf, 0, sizeof(*elf));
 
 	hash_init(elf->symbol_hash);
+	hash_init(elf->symbol_name_hash);
 	hash_init(elf->section_hash);
 	hash_init(elf->section_name_hash);
 	INIT_LIST_HEAD(&elf->sections);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -47,6 +47,7 @@ struct symbol {
 	struct list_head list;
 	struct rb_node node;
 	struct hlist_node hash;
+	struct hlist_node name_hash;
 	GElf_Sym sym;
 	struct section *sec;
 	char *name;
@@ -77,6 +78,7 @@ struct elf {
 	char *name;
 	struct list_head sections;
 	DECLARE_HASHTABLE(symbol_hash, 20);
+	DECLARE_HASHTABLE(symbol_name_hash, 20);
 	DECLARE_HASHTABLE(section_hash, 16);
 	DECLARE_HASHTABLE(section_name_hash, 16);
 };



  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 ` [PATCH v3 06/26] objtool: Optimize find_symbol_by_index() Peter Zijlstra
2020-03-25 10:01   ` 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 ` Peter Zijlstra [this message]
2020-03-25 10:25   ` [PATCH v3 13/26] objtool: Optimize find_symbol_by_name() 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.676865656@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