2020-03-12 13:52:36

by Peter Zijlstra

Subject: [RFC][PATCH 08/16] Optimize find_section_by_name()

In order to avoid yet another linear search of (20k) sections, add a
name based hash.

This reduces objtool runtime on vmlinux.o by some 10s to around 35s.

Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
---
tools/objtool/elf.c | 9 ++++++++-
tools/objtool/elf.h | 3 +++
2 files changed, 11 insertions(+), 1 deletion(-)

--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -22,11 +22,16 @@

#define MAX_NAME_LEN 128

+static inline u32 str_hash(const char *str)
+{
+ return jhash(str, strlen(str), 0);
+}
+
struct section *find_section_by_name(struct elf *elf, const char *name)
{
struct section *sec;

- list_for_each_entry(sec, &elf->sections, list)
+ hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
if (!strcmp(sec->name, name))
return sec;

@@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
sec->len = sec->sh.sh_size;

hash_add(elf->section_hash, &sec->hash, sec->idx);
+ hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
}

if (stats)
@@ -433,6 +439,7 @@ struct elf *elf_read(const char *name, i

hash_init(elf->symbol_hash);
hash_init(elf->section_hash);
+ hash_init(elf->section_name_hash);
INIT_LIST_HEAD(&elf->sections);

elf->fd = open(name, flags);
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -10,6 +10,7 @@
#include <gelf.h>
#include <linux/list.h>
#include <linux/hashtable.h>
+#include <linux/jhash.h>

#ifdef LIBELF_USE_DEPRECATED
# define elf_getshdrnum elf_getshnum
@@ -26,6 +27,7 @@
struct section {
struct list_head list;
struct hlist_node hash;
+ struct hlist_node name_hash;
GElf_Shdr sh;
struct list_head symbol_list;
struct list_head rela_list;
@@ -73,6 +75,7 @@ struct elf {
struct list_head sections;
DECLARE_HASHTABLE(symbol_hash, 20);
DECLARE_HASHTABLE(section_hash, 16);
+ DECLARE_HASHTABLE(section_name_hash, 16);
};

2020-03-15 16:26:10

by Josh Poimboeuf

Subject: Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

On Thu, Mar 12, 2020 at 02:41:15PM +0100, Peter Zijlstra wrote:
> In order to avoid yet another linear search of (20k) sections, add a
> name based hash.
>
> This reduces objtool runtime on vmlinux.o by some 10s to around 35s.
>
> Signed-off-by: Peter Zijlstra (Intel) <[email protected]>

$SUBJECT needs "objtool: " prefix.

--
Josh

2020-03-17 12:23:23

by Miroslav Benes

Subject: Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

> @@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
> sec->len = sec->sh.sh_size;
>
> hash_add(elf->section_hash, &sec->hash, sec->idx);
> + hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
> }

Don't you need to the same in elf_create_section()?

Miroslav

2020-03-17 14:10:53

by Peter Zijlstra

Subject: Re: [RFC][PATCH 08/16] Optimize find_section_by_name()

On Tue, Mar 17, 2020 at 01:22:23PM +0100, Miroslav Benes wrote:
> > @@ -193,6 +198,7 @@ static int read_sections(struct elf *elf
> > sec->len = sec->sh.sh_size;
> >
> > hash_add(elf->section_hash, &sec->hash, sec->idx);
> > + hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
> > }
>
> Don't you need to the same in elf_create_section()?

Yes, already fixed. Noticed it yesterday when I was addressing Josh's
comments.