[PATCH 0/3] objtool: add support for >64k sections

[PATCH 0/3] objtool: add support for >64k sections

[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.

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
-- 
2.26.1.301.g55bc3eb7cb9-goog

[PATCH 1/3] objtool: use gelf_getsymshndx to handle >64k sections

[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

[PATCH 2/3] objtool: optimize insn_hash for split sections

[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

[PATCH 3/3] objtool: optimize add_dead_ends for split sections

[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

Re: [PATCH 2/3] objtool: optimize insn_hash for split sections

[Peter Zijlstra]

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.

Re: [PATCH 0/3] objtool: add support for >64k sections

[Kees Cook]

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

Re: [PATCH 1/3] objtool: use gelf_getsymshndx to handle >64k sections

[Kees Cook]

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

Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections

[Josh Poimboeuf]

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

Re: [PATCH 2/3] objtool: optimize insn_hash for split sections

[Kees Cook]

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

Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections

[Kees Cook]

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

Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections

[Kees Cook]

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

Re: [PATCH 2/3] objtool: optimize insn_hash for split sections

[Sami Tolvanen]

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

Re: [PATCH 3/3] objtool: optimize add_dead_ends for split sections

[Sami Tolvanen]

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

[PATCH v2 0/2] objtool: add support for >64k sections

[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

[PATCH v2 1/2] objtool: use gelf_getsymshndx to handle >64k sections

[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

[PATCH v2 2/2] objtool: optimize add_dead_ends for split sections

[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

Re: [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections

[Kees Cook]

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

Re: [PATCH v2 0/2] objtool: add support for >64k sections

[Josh Poimboeuf]

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

[tip: objtool/core] objtool: optimize add_dead_ends for split sections

[tip-bot2 for Sami Tolvanen]

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;

[tip: objtool/core] objtool: use gelf_getsymshndx to handle >64k sections

[tip-bot2 for Sami Tolvanen]

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);