Skip to contentSkip to conversation

objtool: add support for >64k sections

PATCH Superseded Sami Tolvanen 5 participants 20 messages Apr 21, 2020 – May 15, 2020 objtool

lore
Share & tools
lore
#0 lore raw

cover objtool: add support for >64k sections

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

Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
#1 lore raw

PATCH 1/3 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.

---
 tools/objtool/elf.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
tools/objtool/elf.c +17 -7
index 09ddc8f1def3..887445e87380 100644
@@ -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);
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
Reviewed-by on v1 1/3
#2 lore raw

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

Quoted 5 lines · 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.

-Kees

Quoted 68 lines
---
 tools/objtool/elf.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
tools/objtool/elf.c +17 -7
index 09ddc8f1def3..887445e87380 100644
@@ -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);
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
Signature · 1 line
Kees Cook
#3 lore raw

PATCH 2/3 objtool: optimize insn_hash for split sections

In reply to 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.

---
 tools/objtool/check.c | 5 +++--
 tools/objtool/check.h | 5 +++++
 2 files changed, 8 insertions(+), 2 deletions(-)
tools/objtool/check.c +3 -2
index 4b170fd08a28..4770fb07b365 100644
@@ -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++;
 		}
tools/objtool/check.h +5 -0
index f0ce8ffe7135..bc78eca7982e 100644
@@ -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);
 
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
maintainer
#4 lore raw

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

Quoted 7 lines · 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.

I already have this queued:

https://lkml.kernel.org/r/[email protected]

which looks very similar.

Reviewed-by
#5 lore raw

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

Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · 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.

Quoted 7 lines
Quoted 1 line

I already have this queued:

https://lkml.kernel.org/r/[email protected]

which looks very similar.

Ah! Yeah, just no insn-arg helper to do the hash call; cool.

Please consider both:

-Kees

Signature · 1 line
Kees Cook
#6 lore raw

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

In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · 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.

Quoted 7 lines
Quoted 1 line

I already have this queued:

https://lkml.kernel.org/r/[email protected]

which looks very similar.

Great, that works for me. Thanks for the link!

Sami

#7 lore raw

PATCH 3/3 objtool: optimize add_dead_ends for split sections

In reply to 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.

---
 tools/objtool/check.c | 43 ++++++++++++++++++++++++++-----------------
 tools/objtool/check.h |  4 ++++
 tools/objtool/elf.h   |  1 +
 3 files changed, 31 insertions(+), 17 deletions(-)
tools/objtool/check.c +26 -17
index 4770fb07b365..7d4104de0a5e 100644
@@ -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;
tools/objtool/check.h +4 -0
index bc78eca7982e..353677ec85d4 100644
@@ -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;
tools/objtool/elf.h +1 -0
index ebbb10c61e24..98f2b41d18e4 100644
@@ -40,6 +40,7 @@ struct section {
 	int idx;
 	unsigned int len;
 	bool changed, text, rodata;
+	void *section_info;
 };
 
 struct symbol {
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
#8 lore raw

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

Quoted 12 lines · Sami Tolvanen
tools/objtool/check.c +1 -7
@@ -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 *)

tools/objtool/check.c static int add_dead_ends(struct objtool_file *file) · line 363

Quoted 10 lines
tools/objtool/check.c +5 -1
+				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?

Signature · 1 line
Josh
#10 lore raw

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

In reply to Josh Poimboeuf
Quoted 17 lines · Josh Poimboeuf

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;
	}
Quoted 2 lines

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

Reviewed-by on v1 3/3
#11 lore raw

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

In reply to Sami Tolvanen
Quoted 7 lines · 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.

-Kees

Quoted 127 lines
---
 tools/objtool/check.c | 43 ++++++++++++++++++++++++++-----------------
 tools/objtool/check.h |  4 ++++
 tools/objtool/elf.h   |  1 +
 3 files changed, 31 insertions(+), 17 deletions(-)
tools/objtool/check.c +26 -17
index 4770fb07b365..7d4104de0a5e 100644
@@ -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;
tools/objtool/check.h +4 -0
index bc78eca7982e..353677ec85d4 100644
@@ -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;
tools/objtool/elf.h +1 -0
index ebbb10c61e24..98f2b41d18e4 100644
@@ -40,6 +40,7 @@ struct section {
 	int idx;
 	unsigned int len;
 	bool changed, text, rodata;
+	void *section_info;
 };
 
 struct symbol {
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
Signature · 1 line
Kees Cook
#12 lore raw
In reply to Sami Tolvanen
Quoted 9 lines · 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

Quoted 8 lines
 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.

Signature · 1 line
Kees Cook
#13 lore raw

v2 cover objtool: add support for >64k sections

In reply to 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

Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
#14 lore raw

PATCH v2 1/2 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.

---
 tools/objtool/elf.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
tools/objtool/elf.c +17 -7
index 09ddc8f1def3..887445e87380 100644
@@ -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);
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
merge bot Applied
#15 lore raw

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

The following commit has been merged into the objtool/core branch of tip:

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 <[email protected]>
AuthorDate:    Tue, 21 Apr 2020 15:08:42 -07:00
Committer:     Peter Zijlstra <[email protected]>
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.

---
 tools/objtool/elf.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
tools/objtool/elf.c +17 -7
index b6349ca..8422567 100644
@@ -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);
#16 lore raw

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

In reply to 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.

---
 tools/objtool/check.c | 36 +++++++++++++++++-------------------
 1 file changed, 17 insertions(+), 19 deletions(-)
tools/objtool/check.c +17 -19
index 4b170fd08a28..4f1d405420a4 100644
@@ -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;
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
Reviewed-by on v2 2/2
#17 lore raw

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

Quoted 7 lines · 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.

-Kees

Quoted 75 lines
---
 tools/objtool/check.c | 36 +++++++++++++++++-------------------
 1 file changed, 17 insertions(+), 19 deletions(-)
tools/objtool/check.c +17 -19
index 4b170fd08a28..4f1d405420a4 100644
@@ -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;
Signature · 1 line
2.26.1.301.g55bc3eb7cb9-goog
Signature · 1 line
Kees Cook
merge bot Applied
#18 lore raw

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

In reply to Sami Tolvanen
The following commit has been merged into the objtool/core branch of tip:

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 <[email protected]>
AuthorDate:    Tue, 21 Apr 2020 15:08:43 -07:00
Committer:     Peter Zijlstra <[email protected]>
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.

---
 tools/objtool/check.c | 36 +++++++++++++++++-------------------
 1 file changed, 17 insertions(+), 19 deletions(-)
tools/objtool/check.c +17 -19
index 196a551..6b2b458 100644
@@ -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;
#19 lore raw
In reply to Sami Tolvanen
Quoted 15 lines · 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

Quoted 6 lines
 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.

Signature · 1 line
Josh