Skip to content

Commit 042ba73

Browse files
jpoimboeIngo Molnar
jpoimboe
authored and
Ingo Molnar
committed
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 parent 1698872 commit 042ba73

File tree

3 files changed

+35
-14
lines changed

3 files changed

+35
-14
lines changed

‎tools/objtool/builtin-check.c

Lines changed: 12 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,8 @@
3434
#include "arch.h"
3535
#include "warn.h"
3636

37+
#include <linux/hashtable.h>
38+
3739
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
3840

3941
#define STATE_FP_SAVED 0x1
@@ -42,6 +44,7 @@
4244

4345
struct instruction {
4446
struct list_head list;
47+
struct hlist_node hash;
4548
struct section *sec;
4649
unsigned long offset;
4750
unsigned int len, state;
@@ -61,7 +64,8 @@ struct alternative {
6164
struct objtool_file {
6265
struct elf *elf;
6366
struct list_head insn_list;
64-
struct section *rodata;
67+
DECLARE_HASHTABLE(insn_hash, 16);
68+
struct section *rodata, *whitelist;
6569
};
6670

6771
const char *objname;
@@ -72,7 +76,7 @@ static struct instruction *find_insn(struct objtool_file *file,
7276
{
7377
struct instruction *insn;
7478

75-
list_for_each_entry(insn, &file->insn_list, list)
79+
hash_for_each_possible(file->insn_hash, insn, hash, offset)
7680
if (insn->sec == sec && insn->offset == offset)
7781
return insn;
7882

@@ -111,14 +115,12 @@ static struct instruction *next_insn_same_sec(struct objtool_file *file,
111115
*/
112116
static bool ignore_func(struct objtool_file *file, struct symbol *func)
113117
{
114-
struct section *macro_sec;
115118
struct rela *rela;
116119
struct instruction *insn;
117120

118121
/* check for STACK_FRAME_NON_STANDARD */
119-
macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
120-
if (macro_sec && macro_sec->rela)
121-
list_for_each_entry(rela, &macro_sec->rela->rela_list, list)
122+
if (file->whitelist && file->whitelist->rela)
123+
list_for_each_entry(rela, &file->whitelist->rela->rela_list, list)
122124
if (rela->sym->sec == func->sec &&
123125
rela->addend == func->offset)
124126
return true;
@@ -276,6 +278,7 @@ static int decode_instructions(struct objtool_file *file)
276278
return -1;
277279
}
278280

281+
hash_add(file->insn_hash, &insn->hash, insn->offset);
279282
list_add_tail(&insn->list, &file->insn_list);
280283
}
281284
}
@@ -729,6 +732,7 @@ static int decode_sections(struct objtool_file *file)
729732
{
730733
int ret;
731734

735+
file->whitelist = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
732736
file->rodata = find_section_by_name(file->elf, ".rodata");
733737

734738
ret = decode_instructions(file);
@@ -1091,6 +1095,7 @@ static void cleanup(struct objtool_file *file)
10911095
free(alt);
10921096
}
10931097
list_del(&insn->list);
1098+
hash_del(&insn->hash);
10941099
free(insn);
10951100
}
10961101
elf_close(file->elf);
@@ -1125,6 +1130,7 @@ int cmd_check(int argc, const char **argv)
11251130
}
11261131

11271132
INIT_LIST_HEAD(&file.insn_list);
1133+
hash_init(file.insn_hash);
11281134

11291135
ret = decode_sections(&file);
11301136
if (ret < 0)

‎tools/objtool/elf.c

Lines changed: 15 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
5959
struct symbol *sym;
6060

6161
list_for_each_entry(sec, &elf->sections, list)
62-
list_for_each_entry(sym, &sec->symbol_list, list)
62+
hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
6363
if (sym->idx == idx)
6464
return sym;
6565

@@ -82,13 +82,15 @@ struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
8282
unsigned int len)
8383
{
8484
struct rela *rela;
85+
unsigned long o;
8586

8687
if (!sec->rela)
8788
return NULL;
8889

89-
list_for_each_entry(rela, &sec->rela->rela_list, list)
90-
if (rela->offset >= offset && rela->offset < offset + len)
91-
return rela;
90+
for (o = offset; o < offset + len; o++)
91+
hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
92+
if (rela->offset == o)
93+
return rela;
9294

9395
return NULL;
9496
}
@@ -137,6 +139,8 @@ static int read_sections(struct elf *elf)
137139

138140
INIT_LIST_HEAD(&sec->symbol_list);
139141
INIT_LIST_HEAD(&sec->rela_list);
142+
hash_init(sec->rela_hash);
143+
hash_init(sec->symbol_hash);
140144

141145
list_add_tail(&sec->list, &elf->sections);
142146

@@ -261,6 +265,7 @@ static int read_symbols(struct elf *elf)
261265
}
262266
}
263267
list_add(&sym->list, entry);
268+
hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
264269
}
265270

266271
return 0;
@@ -298,8 +303,6 @@ static int read_relas(struct elf *elf)
298303
}
299304
memset(rela, 0, sizeof(*rela));
300305

301-
list_add_tail(&rela->list, &sec->rela_list);
302-
303306
if (!gelf_getrela(sec->elf_data, i, &rela->rela)) {
304307
perror("gelf_getrela");
305308
return -1;
@@ -315,6 +318,10 @@ static int read_relas(struct elf *elf)
315318
symndx, sec->name);
316319
return -1;
317320
}
321+
322+
list_add_tail(&rela->list, &sec->rela_list);
323+
hash_add(sec->rela_hash, &rela->hash, rela->offset);
324+
318325
}
319326
}
320327

@@ -384,10 +391,12 @@ void elf_close(struct elf *elf)
384391
list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
385392
list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
386393
list_del(&sym->list);
394+
hash_del(&sym->hash);
387395
free(sym);
388396
}
389397
list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) {
390398
list_del(&rela->list);
399+
hash_del(&rela->hash);
391400
free(rela);
392401
}
393402
list_del(&sec->list);

‎tools/objtool/elf.h

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,12 +21,15 @@
2121
#include <stdio.h>
2222
#include <gelf.h>
2323
#include <linux/list.h>
24+
#include <linux/hashtable.h>
2425

2526
struct section {
2627
struct list_head list;
2728
GElf_Shdr sh;
2829
struct list_head symbol_list;
30+
DECLARE_HASHTABLE(symbol_hash, 8);
2931
struct list_head rela_list;
32+
DECLARE_HASHTABLE(rela_hash, 16);
3033
struct section *base, *rela;
3134
struct symbol *sym;
3235
Elf_Data *elf_data;
@@ -38,21 +41,23 @@ struct section {
3841

3942
struct symbol {
4043
struct list_head list;
44+
struct hlist_node hash;
4145
GElf_Sym sym;
4246
struct section *sec;
4347
char *name;
44-
int idx;
48+
unsigned int idx;
4549
unsigned char bind, type;
4650
unsigned long offset;
4751
unsigned int len;
4852
};
4953

5054
struct rela {
5155
struct list_head list;
56+
struct hlist_node hash;
5257
GElf_Rela rela;
5358
struct symbol *sym;
5459
unsigned int type;
55-
int offset;
60+
unsigned long offset;
5661
int addend;
5762
};
5863

@@ -62,6 +67,7 @@ struct elf {
6267
int fd;
6368
char *name;
6469
struct list_head sections;
70+
DECLARE_HASHTABLE(rela_hash, 16);
6571
};
6672

6773

0 commit comments

Comments
 (0)