* [PATCH 1/3] objtool: use gelf_getsymshndx to handle >64k sections
2020-04-21 18:07 [PATCH 0/3] objtool: add support for >64k sections Sami Tolvanen
@ 2020-04-21 18:07 ` Sami Tolvanen
2020-04-21 20:11 ` Kees Cook
2020-04-21 18:07 ` [PATCH 2/3] objtool: optimize insn_hash for split sections Sami Tolvanen
` (3 subsequent siblings)
4 siblings, 1 reply; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 18:07 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra; +Cc: Kees Cook, linux-kernel, Sami Tolvanen
Currently, objtool fails to load the correct section for symbols when
the index is greater than SHN_LORESERVE. Use gelf_getsymshndx instead
of gelf_getsym to handle >64k sections.
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
tools/objtool/elf.c | 24 +++++++++++++++++-------
1 file changed, 17 insertions(+), 7 deletions(-)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 09ddc8f1def3..887445e87380 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -327,12 +327,14 @@ static int read_sections(struct elf *elf)
static int read_symbols(struct elf *elf)
{
- struct section *symtab, *sec;
+ struct section *symtab, *symtab_shndx, *sec;
struct symbol *sym, *pfunc;
struct list_head *entry;
struct rb_node *pnode;
int symbols_nr, i;
char *coldstr;
+ Elf_Data *shndx_data = NULL;
+ Elf32_Word shndx;
symtab = find_section_by_name(elf, ".symtab");
if (!symtab) {
@@ -340,6 +342,10 @@ static int read_symbols(struct elf *elf)
return -1;
}
+ symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
+ if (symtab_shndx)
+ shndx_data = symtab_shndx->data;
+
symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
for (i = 0; i < symbols_nr; i++) {
@@ -353,8 +359,9 @@ static int read_symbols(struct elf *elf)
sym->idx = i;
- if (!gelf_getsym(symtab->data, i, &sym->sym)) {
- WARN_ELF("gelf_getsym");
+ if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
+ &shndx)) {
+ WARN_ELF("gelf_getsymshndx");
goto err;
}
@@ -368,10 +375,13 @@ static int read_symbols(struct elf *elf)
sym->type = GELF_ST_TYPE(sym->sym.st_info);
sym->bind = GELF_ST_BIND(sym->sym.st_info);
- if (sym->sym.st_shndx > SHN_UNDEF &&
- sym->sym.st_shndx < SHN_LORESERVE) {
- sym->sec = find_section_by_index(elf,
- sym->sym.st_shndx);
+ if ((sym->sym.st_shndx > SHN_UNDEF &&
+ sym->sym.st_shndx < SHN_LORESERVE) ||
+ (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
+ if (sym->sym.st_shndx != SHN_XINDEX)
+ shndx = sym->sym.st_shndx;
+
+ sym->sec = find_section_by_index(elf, shndx);
if (!sym->sec) {
WARN("couldn't find section for symbol %s",
sym->name);
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply related [flat|nested] 20+ messages in thread* Re: [PATCH 1/3] objtool: use gelf_getsymshndx to handle >64k sections
2020-04-21 18:07 ` [PATCH 1/3] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
@ 2020-04-21 20:11 ` Kees Cook
0 siblings, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 20:11 UTC (permalink / raw)
To: Sami Tolvanen; +Cc: Josh Poimboeuf, Peter Zijlstra, linux-kernel
On Tue, Apr 21, 2020 at 11:07:22AM -0700, Sami Tolvanen wrote:
> Currently, objtool fails to load the correct section for symbols when
> the index is greater than SHN_LORESERVE. Use gelf_getsymshndx instead
> of gelf_getsym to handle >64k sections.
>
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Reviewed-by: Kees Cook <keescook@chromium.org>
-Kees
> ---
> tools/objtool/elf.c | 24 +++++++++++++++++-------
> 1 file changed, 17 insertions(+), 7 deletions(-)
>
> diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
> index 09ddc8f1def3..887445e87380 100644
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -327,12 +327,14 @@ static int read_sections(struct elf *elf)
>
> static int read_symbols(struct elf *elf)
> {
> - struct section *symtab, *sec;
> + struct section *symtab, *symtab_shndx, *sec;
> struct symbol *sym, *pfunc;
> struct list_head *entry;
> struct rb_node *pnode;
> int symbols_nr, i;
> char *coldstr;
> + Elf_Data *shndx_data = NULL;
> + Elf32_Word shndx;
>
> symtab = find_section_by_name(elf, ".symtab");
> if (!symtab) {
> @@ -340,6 +342,10 @@ static int read_symbols(struct elf *elf)
> return -1;
> }
>
> + symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
> + if (symtab_shndx)
> + shndx_data = symtab_shndx->data;
> +
> symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
>
> for (i = 0; i < symbols_nr; i++) {
> @@ -353,8 +359,9 @@ static int read_symbols(struct elf *elf)
>
> sym->idx = i;
>
> - if (!gelf_getsym(symtab->data, i, &sym->sym)) {
> - WARN_ELF("gelf_getsym");
> + if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
> + &shndx)) {
> + WARN_ELF("gelf_getsymshndx");
> goto err;
> }
>
> @@ -368,10 +375,13 @@ static int read_symbols(struct elf *elf)
> sym->type = GELF_ST_TYPE(sym->sym.st_info);
> sym->bind = GELF_ST_BIND(sym->sym.st_info);
>
> - if (sym->sym.st_shndx > SHN_UNDEF &&
> - sym->sym.st_shndx < SHN_LORESERVE) {
> - sym->sec = find_section_by_index(elf,
> - sym->sym.st_shndx);
> + if ((sym->sym.st_shndx > SHN_UNDEF &&
> + sym->sym.st_shndx < SHN_LORESERVE) ||
> + (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
> + if (sym->sym.st_shndx != SHN_XINDEX)
> + shndx = sym->sym.st_shndx;
> +
> + sym->sec = find_section_by_index(elf, shndx);
> if (!sym->sec) {
> WARN("couldn't find section for symbol %s",
> sym->name);
> --
> 2.26.1.301.g55bc3eb7cb9-goog
>
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH 2/3] objtool: optimize insn_hash for split sections
2020-04-21 18:07 [PATCH 0/3] objtool: add support for >64k sections Sami Tolvanen
2020-04-21 18:07 ` [PATCH 1/3] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
@ 2020-04-21 18:07 ` Sami Tolvanen
2020-04-21 19:47 ` Peter Zijlstra
2020-04-21 18:07 ` [PATCH 3/3] objtool: optimize add_dead_ends " Sami Tolvanen
` (2 subsequent siblings)
4 siblings, 1 reply; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 18:07 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra; +Cc: Kees Cook, linux-kernel, Sami Tolvanen
When running objtool on vmlinux.o compiled with -ffunction-sections,
we end up with a ton of collisions in the insn_hash table as each
function is in its own section. This results in a runtime of minutes
instead of seconds. Use both section index and offset as the key to
avoid this, similarly to rela_hash.
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
tools/objtool/check.c | 5 +++--
tools/objtool/check.h | 5 +++++
2 files changed, 8 insertions(+), 2 deletions(-)
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 4b170fd08a28..4770fb07b365 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -34,7 +34,8 @@ struct instruction *find_insn(struct objtool_file *file,
{
struct instruction *insn;
- hash_for_each_possible(file->insn_hash, insn, hash, offset)
+ hash_for_each_possible(file->insn_hash, insn, hash,
+ sec_offset_hash(sec, offset))
if (insn->sec == sec && insn->offset == offset)
return insn;
@@ -273,7 +274,7 @@ static int decode_instructions(struct objtool_file *file)
if (ret)
goto err;
- hash_add(file->insn_hash, &insn->hash, insn->offset);
+ hash_add(file->insn_hash, &insn->hash, insn_hash(insn));
list_add_tail(&insn->list, &file->insn_list);
nr_insns++;
}
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index f0ce8ffe7135..bc78eca7982e 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -56,6 +56,11 @@ struct objtool_file {
int check(const char *objname, bool orc);
+static inline u32 insn_hash(struct instruction *insn)
+{
+ return sec_offset_hash(insn->sec, insn->offset);
+}
+
struct instruction *find_insn(struct objtool_file *file,
struct section *sec, unsigned long offset);
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply related [flat|nested] 20+ messages in thread* Re: [PATCH 2/3] objtool: optimize insn_hash for split sections
2020-04-21 18:07 ` [PATCH 2/3] objtool: optimize insn_hash for split sections Sami Tolvanen
@ 2020-04-21 19:47 ` Peter Zijlstra
2020-04-21 20:13 ` Kees Cook
2020-04-21 20:20 ` Sami Tolvanen
0 siblings, 2 replies; 20+ messages in thread
From: Peter Zijlstra @ 2020-04-21 19:47 UTC (permalink / raw)
To: Sami Tolvanen; +Cc: Josh Poimboeuf, Kees Cook, linux-kernel
On Tue, Apr 21, 2020 at 11:07:23AM -0700, Sami Tolvanen wrote:
> When running objtool on vmlinux.o compiled with -ffunction-sections,
> we end up with a ton of collisions in the insn_hash table as each
> function is in its own section. This results in a runtime of minutes
> instead of seconds. Use both section index and offset as the key to
> avoid this, similarly to rela_hash.
>
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
I already have this queued:
https://lkml.kernel.org/r/20200416115119.227240432@infradead.org
which looks very similar.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH 2/3] objtool: optimize insn_hash for split sections
2020-04-21 19:47 ` Peter Zijlstra
@ 2020-04-21 20:13 ` Kees Cook
2020-04-21 20:20 ` Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 20:13 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: Sami Tolvanen, Josh Poimboeuf, linux-kernel
On Tue, Apr 21, 2020 at 09:47:49PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 21, 2020 at 11:07:23AM -0700, Sami Tolvanen wrote:
> > When running objtool on vmlinux.o compiled with -ffunction-sections,
> > we end up with a ton of collisions in the insn_hash table as each
> > function is in its own section. This results in a runtime of minutes
> > instead of seconds. Use both section index and offset as the key to
> > avoid this, similarly to rela_hash.
> >
> > Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
>
> I already have this queued:
>
> https://lkml.kernel.org/r/20200416115119.227240432@infradead.org
>
> which looks very similar.
Ah! Yeah, just no insn-arg helper to do the hash call; cool.
Please consider both:
Reviewed-by: Kees Cook <keescook@chromium.org>
-Kees
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH 2/3] objtool: optimize insn_hash for split sections
2020-04-21 19:47 ` Peter Zijlstra
2020-04-21 20:13 ` Kees Cook
@ 2020-04-21 20:20 ` Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 20:20 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: Josh Poimboeuf, Kees Cook, linux-kernel
On Tue, Apr 21, 2020 at 09:47:49PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 21, 2020 at 11:07:23AM -0700, Sami Tolvanen wrote:
> > When running objtool on vmlinux.o compiled with -ffunction-sections,
> > we end up with a ton of collisions in the insn_hash table as each
> > function is in its own section. This results in a runtime of minutes
> > instead of seconds. Use both section index and offset as the key to
> > avoid this, similarly to rela_hash.
> >
> > Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
>
> I already have this queued:
>
> https://lkml.kernel.org/r/20200416115119.227240432@infradead.org
>
> which looks very similar.
Great, that works for me. Thanks for the link!
Sami
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH 3/3] objtool: optimize add_dead_ends for split sections
2020-04-21 18:07 [PATCH 0/3] objtool: add support for >64k sections Sami Tolvanen
2020-04-21 18:07 ` [PATCH 1/3] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
2020-04-21 18:07 ` [PATCH 2/3] objtool: optimize insn_hash for split sections Sami Tolvanen
@ 2020-04-21 18:07 ` Sami Tolvanen
2020-04-21 20:13 ` Josh Poimboeuf
2020-04-21 20:14 ` Kees Cook
2020-04-21 20:11 ` [PATCH 0/3] objtool: add support for >64k sections Kees Cook
2020-04-21 22:08 ` [PATCH v2 0/2] " Sami Tolvanen
4 siblings, 2 replies; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 18:07 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra; +Cc: Kees Cook, linux-kernel, Sami Tolvanen
When running objtool on vmlinux.o compiled with -ffunction-sections,
.rela.discard.(un)reachable often contains relocations that point to
a different section. Instead of iterating through the list of all
instructions each time, store a pointer to the last instruction of
each section when decoding instructions.
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
tools/objtool/check.c | 43 ++++++++++++++++++++++++++-----------------
tools/objtool/check.h | 4 ++++
tools/objtool/elf.h | 1 +
3 files changed, 31 insertions(+), 17 deletions(-)
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 4770fb07b365..7d4104de0a5e 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -237,6 +237,7 @@ static void clear_insn_state(struct insn_state *state)
static int decode_instructions(struct objtool_file *file)
{
struct section *sec;
+ struct section_info *sec_info = NULL;
struct symbol *func;
unsigned long offset;
struct instruction *insn;
@@ -253,6 +254,8 @@ static int decode_instructions(struct objtool_file *file)
strncmp(sec->name, ".discard.", 9))
sec->text = true;
+ insn = NULL;
+
for (offset = 0; offset < sec->len; offset += insn->len) {
insn = malloc(sizeof(*insn));
if (!insn) {
@@ -279,6 +282,17 @@ static int decode_instructions(struct objtool_file *file)
nr_insns++;
}
+ if (insn) {
+ sec_info = malloc(sizeof(*sec_info));
+ if (!sec_info) {
+ WARN("malloc failed");
+ return -1;
+ }
+
+ sec_info->last_insn = insn;
+ sec->section_info = sec_info;
+ }
+
list_for_each_entry(func, &sec->symbol_list, list) {
if (func->type != STT_FUNC || func->alias != func)
continue;
@@ -312,7 +326,6 @@ static int add_dead_ends(struct objtool_file *file)
struct section *sec;
struct rela *rela;
struct instruction *insn;
- bool found;
/*
* By default, "ud2" is a dead end unless otherwise annotated, because
@@ -338,15 +351,13 @@ static int add_dead_ends(struct objtool_file *file)
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
+ struct section_info *sec_info = (struct section_info *)
+ rela->sym->sec->section_info;
+
+ if (sec_info)
+ insn = sec_info->last_insn;
- if (!found) {
+ if (!insn) {
WARN("can't find unreachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
@@ -380,15 +391,13 @@ static int add_dead_ends(struct objtool_file *file)
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
+ struct section_info *sec_info = (struct section_info *)
+ rela->sym->sec->section_info;
+
+ if (sec_info)
+ insn = sec_info->last_insn;
- if (!found) {
+ if (!insn) {
WARN("can't find reachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index bc78eca7982e..353677ec85d4 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -47,6 +47,10 @@ struct instruction {
struct orc_entry orc;
};
+struct section_info {
+ struct instruction *last_insn;
+};
+
struct objtool_file {
struct elf *elf;
struct list_head insn_list;
diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
index ebbb10c61e24..98f2b41d18e4 100644
--- a/tools/objtool/elf.h
+++ b/tools/objtool/elf.h
@@ -40,6 +40,7 @@ struct section {
int idx;
unsigned int len;
bool changed, text, rodata;
+ void *section_info;
};
struct symbol {
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply related [flat|nested] 20+ messages in thread* Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections
2020-04-21 18:07 ` [PATCH 3/3] objtool: optimize add_dead_ends " Sami Tolvanen
@ 2020-04-21 20:13 ` Josh Poimboeuf
2020-04-21 20:17 ` Kees Cook
2020-04-21 22:02 ` Sami Tolvanen
2020-04-21 20:14 ` Kees Cook
1 sibling, 2 replies; 20+ messages in thread
From: Josh Poimboeuf @ 2020-04-21 20:13 UTC (permalink / raw)
To: Sami Tolvanen; +Cc: Peter Zijlstra, Kees Cook, linux-kernel
On Tue, Apr 21, 2020 at 11:07:24AM -0700, Sami Tolvanen wrote:
> @@ -338,15 +351,13 @@ static int add_dead_ends(struct objtool_file *file)
> if (insn)
> insn = list_prev_entry(insn, list);
> else if (rela->addend == rela->sym->sec->len) {
> - found = false;
> - list_for_each_entry_reverse(insn, &file->insn_list, list) {
> - if (insn->sec == rela->sym->sec) {
> - found = true;
> - break;
> - }
> - }
> + struct section_info *sec_info = (struct section_info *)
> + rela->sym->sec->section_info;
> +
> + if (sec_info)
> + insn = sec_info->last_insn;
>
> - if (!found) {
> + if (!insn) {
> WARN("can't find unreachable insn at %s+0x%x",
> rela->sym->sec->name, rela->addend);
> return -1;
Instead of the 'section_info' abstraction I think I'd rather just store
the 'last_insn' pointer directly in the section struct.
Also, the unreachable annotation at the end of a section is really an
edge case. I'm sort of wondering if there's a way to accomplish the
same thing without storing the last_insn.
For example, I wonder if we could use find_insn() for some bytes at the
end of the section. Most of the time I _think_ there will be a two-byte
UD2 instruction there anyway. So maybe we could do something like:
for (offset = rela->sym->sec->len - 1;
offset > rela->sym->sec->len - 10;
offset --) {
insn = find_insn(file, rela->sym->sec, offset);
if (insn)
break;
}
It's kind of ugly, but then we could maybe avoid the need for the
last_insn thing.
BTW, just curious, what's your use case for -ffunction-sections? Is it
for fgkaslr?
--
Josh
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections
2020-04-21 20:13 ` Josh Poimboeuf
@ 2020-04-21 20:17 ` Kees Cook
2020-04-21 22:02 ` Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 20:17 UTC (permalink / raw)
To: Josh Poimboeuf; +Cc: Sami Tolvanen, Peter Zijlstra, linux-kernel
On Tue, Apr 21, 2020 at 03:13:05PM -0500, Josh Poimboeuf wrote:
> BTW, just curious, what's your use case for -ffunction-sections? Is it
> for fgkaslr?
Both Sami's LTO+CFI work[1] and Kristen's FGKASLR series use it.
-Kees
[1] https://github.com/samitolvanen/linux/commits/clang-cfi
https://lwn.net/Articles/810077/
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections
2020-04-21 20:13 ` Josh Poimboeuf
2020-04-21 20:17 ` Kees Cook
@ 2020-04-21 22:02 ` Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 22:02 UTC (permalink / raw)
To: Josh Poimboeuf; +Cc: Peter Zijlstra, Kees Cook, linux-kernel
On Tue, Apr 21, 2020 at 03:13:05PM -0500, Josh Poimboeuf wrote:
> Also, the unreachable annotation at the end of a section is really an
> edge case. I'm sort of wondering if there's a way to accomplish the
> same thing without storing the last_insn.
>
> For example, I wonder if we could use find_insn() for some bytes at the
> end of the section. Most of the time I _think_ there will be a two-byte
> UD2 instruction there anyway. So maybe we could do something like:
>
> for (offset = rela->sym->sec->len - 1;
> offset > rela->sym->sec->len - 10;
> offset --) {
>
> insn = find_insn(file, rela->sym->sec, offset);
> if (insn)
> break;
> }
>
> It's kind of ugly, but then we could maybe avoid the need for the
> last_insn thing.
Sure, that looks fine. I tested this and it looks like the performance
is roughly the same. I'll send v2 shortly.
Sami
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections
2020-04-21 18:07 ` [PATCH 3/3] objtool: optimize add_dead_ends " Sami Tolvanen
2020-04-21 20:13 ` Josh Poimboeuf
@ 2020-04-21 20:14 ` Kees Cook
1 sibling, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 20:14 UTC (permalink / raw)
To: Sami Tolvanen; +Cc: Josh Poimboeuf, Peter Zijlstra, linux-kernel
On Tue, Apr 21, 2020 at 11:07:24AM -0700, Sami Tolvanen wrote:
> When running objtool on vmlinux.o compiled with -ffunction-sections,
> .rela.discard.(un)reachable often contains relocations that point to
> a different section. Instead of iterating through the list of all
> instructions each time, store a pointer to the last instruction of
> each section when decoding instructions.
>
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Reviewed-by: Kees Cook <keescook@chromium.org>
-Kees
> ---
> tools/objtool/check.c | 43 ++++++++++++++++++++++++++-----------------
> tools/objtool/check.h | 4 ++++
> tools/objtool/elf.h | 1 +
> 3 files changed, 31 insertions(+), 17 deletions(-)
>
> diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> index 4770fb07b365..7d4104de0a5e 100644
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -237,6 +237,7 @@ static void clear_insn_state(struct insn_state *state)
> static int decode_instructions(struct objtool_file *file)
> {
> struct section *sec;
> + struct section_info *sec_info = NULL;
> struct symbol *func;
> unsigned long offset;
> struct instruction *insn;
> @@ -253,6 +254,8 @@ static int decode_instructions(struct objtool_file *file)
> strncmp(sec->name, ".discard.", 9))
> sec->text = true;
>
> + insn = NULL;
> +
> for (offset = 0; offset < sec->len; offset += insn->len) {
> insn = malloc(sizeof(*insn));
> if (!insn) {
> @@ -279,6 +282,17 @@ static int decode_instructions(struct objtool_file *file)
> nr_insns++;
> }
>
> + if (insn) {
> + sec_info = malloc(sizeof(*sec_info));
> + if (!sec_info) {
> + WARN("malloc failed");
> + return -1;
> + }
> +
> + sec_info->last_insn = insn;
> + sec->section_info = sec_info;
> + }
> +
> list_for_each_entry(func, &sec->symbol_list, list) {
> if (func->type != STT_FUNC || func->alias != func)
> continue;
> @@ -312,7 +326,6 @@ static int add_dead_ends(struct objtool_file *file)
> struct section *sec;
> struct rela *rela;
> struct instruction *insn;
> - bool found;
>
> /*
> * By default, "ud2" is a dead end unless otherwise annotated, because
> @@ -338,15 +351,13 @@ static int add_dead_ends(struct objtool_file *file)
> if (insn)
> insn = list_prev_entry(insn, list);
> else if (rela->addend == rela->sym->sec->len) {
> - found = false;
> - list_for_each_entry_reverse(insn, &file->insn_list, list) {
> - if (insn->sec == rela->sym->sec) {
> - found = true;
> - break;
> - }
> - }
> + struct section_info *sec_info = (struct section_info *)
> + rela->sym->sec->section_info;
> +
> + if (sec_info)
> + insn = sec_info->last_insn;
>
> - if (!found) {
> + if (!insn) {
> WARN("can't find unreachable insn at %s+0x%x",
> rela->sym->sec->name, rela->addend);
> return -1;
> @@ -380,15 +391,13 @@ static int add_dead_ends(struct objtool_file *file)
> if (insn)
> insn = list_prev_entry(insn, list);
> else if (rela->addend == rela->sym->sec->len) {
> - found = false;
> - list_for_each_entry_reverse(insn, &file->insn_list, list) {
> - if (insn->sec == rela->sym->sec) {
> - found = true;
> - break;
> - }
> - }
> + struct section_info *sec_info = (struct section_info *)
> + rela->sym->sec->section_info;
> +
> + if (sec_info)
> + insn = sec_info->last_insn;
>
> - if (!found) {
> + if (!insn) {
> WARN("can't find reachable insn at %s+0x%x",
> rela->sym->sec->name, rela->addend);
> return -1;
> diff --git a/tools/objtool/check.h b/tools/objtool/check.h
> index bc78eca7982e..353677ec85d4 100644
> --- a/tools/objtool/check.h
> +++ b/tools/objtool/check.h
> @@ -47,6 +47,10 @@ struct instruction {
> struct orc_entry orc;
> };
>
> +struct section_info {
> + struct instruction *last_insn;
> +};
> +
> struct objtool_file {
> struct elf *elf;
> struct list_head insn_list;
> diff --git a/tools/objtool/elf.h b/tools/objtool/elf.h
> index ebbb10c61e24..98f2b41d18e4 100644
> --- a/tools/objtool/elf.h
> +++ b/tools/objtool/elf.h
> @@ -40,6 +40,7 @@ struct section {
> int idx;
> unsigned int len;
> bool changed, text, rodata;
> + void *section_info;
> };
>
> struct symbol {
> --
> 2.26.1.301.g55bc3eb7cb9-goog
>
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH 0/3] objtool: add support for >64k sections
2020-04-21 18:07 [PATCH 0/3] objtool: add support for >64k sections Sami Tolvanen
` (2 preceding siblings ...)
2020-04-21 18:07 ` [PATCH 3/3] objtool: optimize add_dead_ends " Sami Tolvanen
@ 2020-04-21 20:11 ` Kees Cook
2020-04-21 22:08 ` [PATCH v2 0/2] " Sami Tolvanen
4 siblings, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 20:11 UTC (permalink / raw)
To: Sami Tolvanen
Cc: Josh Poimboeuf, Peter Zijlstra, linux-kernel, Kristen Carlson Accardi
On Tue, Apr 21, 2020 at 11:07:21AM -0700, Sami Tolvanen wrote:
> This series fixes objtool for binaries with >64k sections, and
> includes optimizations to reduce the runtime for a binary with
> ~130k sections from >15 minutes to ~4 seconds.
>
> Sami Tolvanen (3):
> objtool: use gelf_getsymshndx to handle >64k sections
> objtool: optimize insn_hash for split sections
> objtool: optimize add_dead_ends for split sections
>
> tools/objtool/check.c | 48 ++++++++++++++++++++++++++-----------------
> tools/objtool/check.h | 9 ++++++++
> tools/objtool/elf.c | 24 +++++++++++++++-------
> tools/objtool/elf.h | 1 +
> 4 files changed, 56 insertions(+), 26 deletions(-)
>
>
> base-commit: ae83d0b416db002fe95601e7f97f64b59514d936
Awesome; thanks for sending these. I suspect they'll help with FGKASLR
as well.
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread* [PATCH v2 0/2] objtool: add support for >64k sections
2020-04-21 18:07 [PATCH 0/3] objtool: add support for >64k sections Sami Tolvanen
` (3 preceding siblings ...)
2020-04-21 20:11 ` [PATCH 0/3] objtool: add support for >64k sections Kees Cook
@ 2020-04-21 22:08 ` Sami Tolvanen
2020-04-21 22:08 ` [PATCH v2 1/2] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
` (2 more replies)
4 siblings, 3 replies; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 22:08 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra
Cc: Kees Cook, Kristen Carlson Accardi, linux-kernel, Sami Tolvanen
This series fixes objtool for binaries with >64k sections, and
includes optimizations to reduce the runtime for a binary with
~130k sections from >15 minutes to ~4 seconds.
Changes in v2:
- Dropped the insn_hash optimization as Peter has a nearly
similar change queued already.
- Instead of storing the last instruction for each section,
use find_insn to locate it.
Sami Tolvanen (2):
objtool: use gelf_getsymshndx to handle >64k sections
objtool: optimize add_dead_ends for split sections
tools/objtool/check.c | 36 +++++++++++++++++-------------------
tools/objtool/elf.c | 24 +++++++++++++++++-------
2 files changed, 34 insertions(+), 26 deletions(-)
base-commit: 18bf34080c4c3beb6699181986cc97dd712498fe
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply [flat|nested] 20+ messages in thread* [PATCH v2 1/2] objtool: use gelf_getsymshndx to handle >64k sections
2020-04-21 22:08 ` [PATCH v2 0/2] " Sami Tolvanen
@ 2020-04-21 22:08 ` Sami Tolvanen
2020-05-15 17:22 ` [tip: objtool/core] " tip-bot2 for Sami Tolvanen
2020-04-21 22:08 ` [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections Sami Tolvanen
2020-04-21 23:52 ` [PATCH v2 0/2] objtool: add support for >64k sections Josh Poimboeuf
2 siblings, 1 reply; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 22:08 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra
Cc: Kees Cook, Kristen Carlson Accardi, linux-kernel, Sami Tolvanen
Currently, objtool fails to load the correct section for symbols when
the index is greater than SHN_LORESERVE. Use gelf_getsymshndx instead
of gelf_getsym to handle >64k sections.
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Reviewed-by: Kees Cook <keescook@chromium.org>
---
tools/objtool/elf.c | 24 +++++++++++++++++-------
1 file changed, 17 insertions(+), 7 deletions(-)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 09ddc8f1def3..887445e87380 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -327,12 +327,14 @@ static int read_sections(struct elf *elf)
static int read_symbols(struct elf *elf)
{
- struct section *symtab, *sec;
+ struct section *symtab, *symtab_shndx, *sec;
struct symbol *sym, *pfunc;
struct list_head *entry;
struct rb_node *pnode;
int symbols_nr, i;
char *coldstr;
+ Elf_Data *shndx_data = NULL;
+ Elf32_Word shndx;
symtab = find_section_by_name(elf, ".symtab");
if (!symtab) {
@@ -340,6 +342,10 @@ static int read_symbols(struct elf *elf)
return -1;
}
+ symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
+ if (symtab_shndx)
+ shndx_data = symtab_shndx->data;
+
symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
for (i = 0; i < symbols_nr; i++) {
@@ -353,8 +359,9 @@ static int read_symbols(struct elf *elf)
sym->idx = i;
- if (!gelf_getsym(symtab->data, i, &sym->sym)) {
- WARN_ELF("gelf_getsym");
+ if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
+ &shndx)) {
+ WARN_ELF("gelf_getsymshndx");
goto err;
}
@@ -368,10 +375,13 @@ static int read_symbols(struct elf *elf)
sym->type = GELF_ST_TYPE(sym->sym.st_info);
sym->bind = GELF_ST_BIND(sym->sym.st_info);
- if (sym->sym.st_shndx > SHN_UNDEF &&
- sym->sym.st_shndx < SHN_LORESERVE) {
- sym->sec = find_section_by_index(elf,
- sym->sym.st_shndx);
+ if ((sym->sym.st_shndx > SHN_UNDEF &&
+ sym->sym.st_shndx < SHN_LORESERVE) ||
+ (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
+ if (sym->sym.st_shndx != SHN_XINDEX)
+ shndx = sym->sym.st_shndx;
+
+ sym->sec = find_section_by_index(elf, shndx);
if (!sym->sec) {
WARN("couldn't find section for symbol %s",
sym->name);
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply related [flat|nested] 20+ messages in thread* [tip: objtool/core] objtool: use gelf_getsymshndx to handle >64k sections
2020-04-21 22:08 ` [PATCH v2 1/2] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
@ 2020-05-15 17:22 ` tip-bot2 for Sami Tolvanen
0 siblings, 0 replies; 20+ messages in thread
From: tip-bot2 for Sami Tolvanen @ 2020-05-15 17:22 UTC (permalink / raw)
To: linux-tip-commits
Cc: Sami Tolvanen, Peter Zijlstra (Intel), Kees Cook, x86, LKML
The following commit has been merged into the objtool/core branch of tip:
Commit-ID: 28fe1d7bf89f8ed5be70b98a33932dbaf99345dd
Gitweb: https://git.kernel.org/tip/28fe1d7bf89f8ed5be70b98a33932dbaf99345dd
Author: Sami Tolvanen <samitolvanen@google.com>
AuthorDate: Tue, 21 Apr 2020 15:08:42 -07:00
Committer: Peter Zijlstra <peterz@infradead.org>
CommitterDate: Fri, 15 May 2020 10:35:13 +02:00
objtool: use gelf_getsymshndx to handle >64k sections
Currently, objtool fails to load the correct section for symbols when
the index is greater than SHN_LORESERVE. Use gelf_getsymshndx instead
of gelf_getsym to handle >64k sections.
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Kees Cook <keescook@chromium.org>
Link: https://lkml.kernel.org/r/20200421220843.188260-2-samitolvanen@google.com
---
tools/objtool/elf.c | 24 +++++++++++++++++-------
1 file changed, 17 insertions(+), 7 deletions(-)
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index b6349ca..8422567 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -343,12 +343,14 @@ static int read_sections(struct elf *elf)
static int read_symbols(struct elf *elf)
{
- struct section *symtab, *sec;
+ struct section *symtab, *symtab_shndx, *sec;
struct symbol *sym, *pfunc;
struct list_head *entry;
struct rb_node *pnode;
int symbols_nr, i;
char *coldstr;
+ Elf_Data *shndx_data = NULL;
+ Elf32_Word shndx;
symtab = find_section_by_name(elf, ".symtab");
if (!symtab) {
@@ -356,6 +358,10 @@ static int read_symbols(struct elf *elf)
return -1;
}
+ symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
+ if (symtab_shndx)
+ shndx_data = symtab_shndx->data;
+
symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
for (i = 0; i < symbols_nr; i++) {
@@ -369,8 +375,9 @@ static int read_symbols(struct elf *elf)
sym->idx = i;
- if (!gelf_getsym(symtab->data, i, &sym->sym)) {
- WARN_ELF("gelf_getsym");
+ if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
+ &shndx)) {
+ WARN_ELF("gelf_getsymshndx");
goto err;
}
@@ -384,10 +391,13 @@ static int read_symbols(struct elf *elf)
sym->type = GELF_ST_TYPE(sym->sym.st_info);
sym->bind = GELF_ST_BIND(sym->sym.st_info);
- if (sym->sym.st_shndx > SHN_UNDEF &&
- sym->sym.st_shndx < SHN_LORESERVE) {
- sym->sec = find_section_by_index(elf,
- sym->sym.st_shndx);
+ if ((sym->sym.st_shndx > SHN_UNDEF &&
+ sym->sym.st_shndx < SHN_LORESERVE) ||
+ (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
+ if (sym->sym.st_shndx != SHN_XINDEX)
+ shndx = sym->sym.st_shndx;
+
+ sym->sec = find_section_by_index(elf, shndx);
if (!sym->sec) {
WARN("couldn't find section for symbol %s",
sym->name);
^ permalink raw reply related [flat|nested] 20+ messages in thread
* [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections
2020-04-21 22:08 ` [PATCH v2 0/2] " Sami Tolvanen
2020-04-21 22:08 ` [PATCH v2 1/2] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
@ 2020-04-21 22:08 ` Sami Tolvanen
2020-04-21 23:43 ` Kees Cook
2020-05-15 17:22 ` [tip: objtool/core] " tip-bot2 for Sami Tolvanen
2020-04-21 23:52 ` [PATCH v2 0/2] objtool: add support for >64k sections Josh Poimboeuf
2 siblings, 2 replies; 20+ messages in thread
From: Sami Tolvanen @ 2020-04-21 22:08 UTC (permalink / raw)
To: Josh Poimboeuf, Peter Zijlstra
Cc: Kees Cook, Kristen Carlson Accardi, linux-kernel, Sami Tolvanen
Instead of iterating through all instructions to find the last
instruction each time .rela.discard.(un)reachable points beyond the
section, use find_insn to locate the last instruction by looking at
the last bytes of the section instead.
Suggested-by: Josh Poimboeuf <jpoimboe@redhat.com>
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
tools/objtool/check.c | 36 +++++++++++++++++-------------------
1 file changed, 17 insertions(+), 19 deletions(-)
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 4b170fd08a28..4f1d405420a4 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -303,6 +303,19 @@ static int decode_instructions(struct objtool_file *file)
return ret;
}
+static struct instruction *find_last_insn(struct objtool_file *file,
+ struct section *sec)
+{
+ struct instruction *insn = NULL;
+ unsigned int offset;
+ unsigned int end = (sec->len > 10) ? sec->len - 10 : 0;
+
+ for (offset = sec->len - 1; offset >= end && !insn; offset--)
+ insn = find_insn(file, sec, offset);
+
+ return insn;
+}
+
/*
* Mark "ud2" instructions and manually annotated dead ends.
*/
@@ -311,7 +324,6 @@ static int add_dead_ends(struct objtool_file *file)
struct section *sec;
struct rela *rela;
struct instruction *insn;
- bool found;
/*
* By default, "ud2" is a dead end unless otherwise annotated, because
@@ -337,15 +349,8 @@ static int add_dead_ends(struct objtool_file *file)
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
-
- if (!found) {
+ insn = find_last_insn(file, rela->sym->sec);
+ if (!insn) {
WARN("can't find unreachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
@@ -379,15 +384,8 @@ static int add_dead_ends(struct objtool_file *file)
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
-
- if (!found) {
+ insn = find_last_insn(file, rela->sym->sec);
+ if (!insn) {
WARN("can't find reachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
--
2.26.1.301.g55bc3eb7cb9-goog
^ permalink raw reply related [flat|nested] 20+ messages in thread* Re: [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections
2020-04-21 22:08 ` [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections Sami Tolvanen
@ 2020-04-21 23:43 ` Kees Cook
2020-05-15 17:22 ` [tip: objtool/core] " tip-bot2 for Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: Kees Cook @ 2020-04-21 23:43 UTC (permalink / raw)
To: Sami Tolvanen
Cc: Josh Poimboeuf, Peter Zijlstra, Kristen Carlson Accardi, linux-kernel
On Tue, Apr 21, 2020 at 03:08:43PM -0700, Sami Tolvanen wrote:
> Instead of iterating through all instructions to find the last
> instruction each time .rela.discard.(un)reachable points beyond the
> section, use find_insn to locate the last instruction by looking at
> the last bytes of the section instead.
>
> Suggested-by: Josh Poimboeuf <jpoimboe@redhat.com>
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Reviewed-by: Kees Cook <keescook@chromium.org>
-Kees
> ---
> tools/objtool/check.c | 36 +++++++++++++++++-------------------
> 1 file changed, 17 insertions(+), 19 deletions(-)
>
> diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> index 4b170fd08a28..4f1d405420a4 100644
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -303,6 +303,19 @@ static int decode_instructions(struct objtool_file *file)
> return ret;
> }
>
> +static struct instruction *find_last_insn(struct objtool_file *file,
> + struct section *sec)
> +{
> + struct instruction *insn = NULL;
> + unsigned int offset;
> + unsigned int end = (sec->len > 10) ? sec->len - 10 : 0;
> +
> + for (offset = sec->len - 1; offset >= end && !insn; offset--)
> + insn = find_insn(file, sec, offset);
> +
> + return insn;
> +}
> +
> /*
> * Mark "ud2" instructions and manually annotated dead ends.
> */
> @@ -311,7 +324,6 @@ static int add_dead_ends(struct objtool_file *file)
> struct section *sec;
> struct rela *rela;
> struct instruction *insn;
> - bool found;
>
> /*
> * By default, "ud2" is a dead end unless otherwise annotated, because
> @@ -337,15 +349,8 @@ static int add_dead_ends(struct objtool_file *file)
> if (insn)
> insn = list_prev_entry(insn, list);
> else if (rela->addend == rela->sym->sec->len) {
> - found = false;
> - list_for_each_entry_reverse(insn, &file->insn_list, list) {
> - if (insn->sec == rela->sym->sec) {
> - found = true;
> - break;
> - }
> - }
> -
> - if (!found) {
> + insn = find_last_insn(file, rela->sym->sec);
> + if (!insn) {
> WARN("can't find unreachable insn at %s+0x%x",
> rela->sym->sec->name, rela->addend);
> return -1;
> @@ -379,15 +384,8 @@ static int add_dead_ends(struct objtool_file *file)
> if (insn)
> insn = list_prev_entry(insn, list);
> else if (rela->addend == rela->sym->sec->len) {
> - found = false;
> - list_for_each_entry_reverse(insn, &file->insn_list, list) {
> - if (insn->sec == rela->sym->sec) {
> - found = true;
> - break;
> - }
> - }
> -
> - if (!found) {
> + insn = find_last_insn(file, rela->sym->sec);
> + if (!insn) {
> WARN("can't find reachable insn at %s+0x%x",
> rela->sym->sec->name, rela->addend);
> return -1;
> --
> 2.26.1.301.g55bc3eb7cb9-goog
>
--
Kees Cook
^ permalink raw reply [flat|nested] 20+ messages in thread* [tip: objtool/core] objtool: optimize add_dead_ends for split sections
2020-04-21 22:08 ` [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections Sami Tolvanen
2020-04-21 23:43 ` Kees Cook
@ 2020-05-15 17:22 ` tip-bot2 for Sami Tolvanen
1 sibling, 0 replies; 20+ messages in thread
From: tip-bot2 for Sami Tolvanen @ 2020-05-15 17:22 UTC (permalink / raw)
To: linux-tip-commits
Cc: Josh Poimboeuf, Sami Tolvanen, Peter Zijlstra (Intel), x86, LKML
The following commit has been merged into the objtool/core branch of tip:
Commit-ID: 6b5dd716da8fc3aba65e6b7d992dea0cee2f9528
Gitweb: https://git.kernel.org/tip/6b5dd716da8fc3aba65e6b7d992dea0cee2f9528
Author: Sami Tolvanen <samitolvanen@google.com>
AuthorDate: Tue, 21 Apr 2020 15:08:43 -07:00
Committer: Peter Zijlstra <peterz@infradead.org>
CommitterDate: Fri, 15 May 2020 10:35:13 +02:00
objtool: optimize add_dead_ends for split sections
Instead of iterating through all instructions to find the last
instruction each time .rela.discard.(un)reachable points beyond the
section, use find_insn to locate the last instruction by looking at
the last bytes of the section instead.
Suggested-by: Josh Poimboeuf <jpoimboe@redhat.com>
Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/20200421220843.188260-3-samitolvanen@google.com
---
tools/objtool/check.c | 36 +++++++++++++++++-------------------
1 file changed, 17 insertions(+), 19 deletions(-)
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 196a551..6b2b458 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -322,6 +322,19 @@ err:
return ret;
}
+static struct instruction *find_last_insn(struct objtool_file *file,
+ struct section *sec)
+{
+ struct instruction *insn = NULL;
+ unsigned int offset;
+ unsigned int end = (sec->len > 10) ? sec->len - 10 : 0;
+
+ for (offset = sec->len - 1; offset >= end && !insn; offset--)
+ insn = find_insn(file, sec, offset);
+
+ return insn;
+}
+
/*
* Mark "ud2" instructions and manually annotated dead ends.
*/
@@ -330,7 +343,6 @@ static int add_dead_ends(struct objtool_file *file)
struct section *sec;
struct rela *rela;
struct instruction *insn;
- bool found;
/*
* By default, "ud2" is a dead end unless otherwise annotated, because
@@ -356,15 +368,8 @@ static int add_dead_ends(struct objtool_file *file)
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
-
- if (!found) {
+ insn = find_last_insn(file, rela->sym->sec);
+ if (!insn) {
WARN("can't find unreachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
@@ -398,15 +403,8 @@ reachable:
if (insn)
insn = list_prev_entry(insn, list);
else if (rela->addend == rela->sym->sec->len) {
- found = false;
- list_for_each_entry_reverse(insn, &file->insn_list, list) {
- if (insn->sec == rela->sym->sec) {
- found = true;
- break;
- }
- }
-
- if (!found) {
+ insn = find_last_insn(file, rela->sym->sec);
+ if (!insn) {
WARN("can't find reachable insn at %s+0x%x",
rela->sym->sec->name, rela->addend);
return -1;
^ permalink raw reply related [flat|nested] 20+ messages in thread
* Re: [PATCH v2 0/2] objtool: add support for >64k sections
2020-04-21 22:08 ` [PATCH v2 0/2] " Sami Tolvanen
2020-04-21 22:08 ` [PATCH v2 1/2] objtool: use gelf_getsymshndx to handle " Sami Tolvanen
2020-04-21 22:08 ` [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections Sami Tolvanen
@ 2020-04-21 23:52 ` Josh Poimboeuf
2 siblings, 0 replies; 20+ messages in thread
From: Josh Poimboeuf @ 2020-04-21 23:52 UTC (permalink / raw)
To: Sami Tolvanen
Cc: Peter Zijlstra, Kees Cook, Kristen Carlson Accardi, linux-kernel
On Tue, Apr 21, 2020 at 03:08:41PM -0700, Sami Tolvanen wrote:
> This series fixes objtool for binaries with >64k sections, and
> includes optimizations to reduce the runtime for a binary with
> ~130k sections from >15 minutes to ~4 seconds.
>
> Changes in v2:
> - Dropped the insn_hash optimization as Peter has a nearly
> similar change queued already.
> - Instead of storing the last instruction for each section,
> use find_insn to locate it.
>
>
> Sami Tolvanen (2):
> objtool: use gelf_getsymshndx to handle >64k sections
> objtool: optimize add_dead_ends for split sections
>
> tools/objtool/check.c | 36 +++++++++++++++++-------------------
> tools/objtool/elf.c | 24 +++++++++++++++++-------
> 2 files changed, 34 insertions(+), 26 deletions(-)
>
>
> base-commit: 18bf34080c4c3beb6699181986cc97dd712498fe
Looks good to me, thanks. I'll add them to the queue for testing, along
with that other patch.
--
Josh
^ permalink raw reply [flat|nested] 20+ messages in thread