Skip to contentSkip to conversation

objtool: fix up st_info in COMDAT group section

PATCH Applied [email protected] 4 participants 9 messages Apr 25, 2025 – May 9, 2025 objtool

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 objtool: fix up st_info in COMDAT group section

From: Rong Xu <[email protected]>

When __elf_create_symbol creates a local symbol, it relocates the first global symbol upwards to make space. Subsequently, elf_update_symbol() is called to refresh the symbol table section. However, this isn't sufficient, as other sections might have the reference to the old symbol index, for instance, the sh_info field of an SHT_GROUP section.

This patch updates the sh_info field when necessary. This field serves as the key for the COMDAT group. An incorrect key would prevent the linker's from deduplicating COMDAT symbols, leading to duplicate definitions in the final link.

---
 tools/objtool/elf.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)
tools/objtool/elf.c +26 -1
index 727a3a4fd9d77..8dffe68d705c6 100644
@@ -572,6 +572,30 @@ static int read_symbols(struct elf *elf)
 	return -1;
 }
 
+/*
+ * @sym's idx has changed.  Update the sh_info in group sections.
+ */
+static void elf_update_group_sh_info(struct elf *elf, Elf32_Word symtab_idx,
+				     Elf32_Word new_idx, Elf32_Word old_idx)
+{
+	struct section *sec;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->sh.sh_type != SHT_GROUP)
+			continue;
+		if (sec->sh.sh_link == symtab_idx &&
+		    sec->sh.sh_info == old_idx) {
+			sec->sh.sh_info = new_idx;
+			mark_sec_changed(elf, sec, true);
+			/*
+			 * Each ELF group should have a unique symbol key.
+			 * Return early on match.
+			 */
+			return;
+		}
+	}
+}
+
 /*
  * @sym's idx has changed.  Update the relocs which reference it.
  */
@@ -745,7 +769,7 @@ __elf_create_symbol(struct elf *elf, struct symbol *sym)
 
 	/*
 	 * Move the first global symbol, as per sh_info, into a new, higher
-	 * symbol index. This fees up a spot for a new local symbol.
+	 * symbol index. This frees up a spot for a new local symbol.
 	 */
 	first_non_local = symtab->sh.sh_info;
 	old = find_symbol_by_index(elf, first_non_local);
@@ -763,6 +787,7 @@ __elf_create_symbol(struct elf *elf, struct symbol *sym)
 		if (elf_update_sym_relocs(elf, old))
 			return NULL;
 
+		elf_update_group_sh_info(elf, symtab->idx, new_idx, first_non_local);
 		new_idx = first_non_local;
 	}
 
Signature · 1 line
2.49.0.850.g28803427d3-goog
merge bot Applied
#1 lore raw

[tip: objtool/core] objtool: Fix up st_info in COMDAT group section

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:     2cb291596e2c1837238bc322ae3545dacb99d584
Gitweb:        https://git.kernel.org/tip/2cb291596e2c1837238bc322ae3545dacb99d584
Author:        Rong Xu <[email protected]>
AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 30 Apr 2025 13:58:34 +02:00

objtool: Fix up st_info in COMDAT group section

When __elf_create_symbol creates a local symbol, it relocates the first global symbol upwards to make space. Subsequently, elf_update_symbol() is called to refresh the symbol table section. However, this isn't sufficient, as other sections might have the reference to the old symbol index, for instance, the sh_info field of an SHT_GROUP section.

This patch updates the sh_info field when necessary. This field serves as the key for the COMDAT group. An incorrect key would prevent the linker's from deduplicating COMDAT symbols, leading to duplicate definitions in the final link.

---
 tools/objtool/elf.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)
tools/objtool/elf.c +26 -1
index 727a3a4..8dffe68 100644
@@ -573,6 +573,30 @@ err:
 }
 
 /*
+ * @sym's idx has changed.  Update the sh_info in group sections.
+ */
+static void elf_update_group_sh_info(struct elf *elf, Elf32_Word symtab_idx,
+				     Elf32_Word new_idx, Elf32_Word old_idx)
+{
+	struct section *sec;
+
+	list_for_each_entry(sec, &elf->sections, list) {
+		if (sec->sh.sh_type != SHT_GROUP)
+			continue;
+		if (sec->sh.sh_link == symtab_idx &&
+		    sec->sh.sh_info == old_idx) {
+			sec->sh.sh_info = new_idx;
+			mark_sec_changed(elf, sec, true);
+			/*
+			 * Each ELF group should have a unique symbol key.
+			 * Return early on match.
+			 */
+			return;
+		}
+	}
+}
+
+/*
  * @sym's idx has changed.  Update the relocs which reference it.
  */
 static int elf_update_sym_relocs(struct elf *elf, struct symbol *sym)
@@ -745,7 +769,7 @@ __elf_create_symbol(struct elf *elf, struct symbol *sym)
 
 	/*
 	 * Move the first global symbol, as per sh_info, into a new, higher
-	 * symbol index. This fees up a spot for a new local symbol.
+	 * symbol index. This frees up a spot for a new local symbol.
 	 */
 	first_non_local = symtab->sh.sh_info;
 	old = find_symbol_by_index(elf, first_non_local);
@@ -763,6 +787,7 @@ __elf_create_symbol(struct elf *elf, struct symbol *sym)
 		if (elf_update_sym_relocs(elf, old))
 			return NULL;
 
+		elf_update_group_sh_info(elf, symtab->idx, new_idx, first_non_local);
 		new_idx = first_non_local;
 	}
 
maintainer
#2 lore raw

Re: [tip: objtool/core] objtool: Fix up st_info in COMDAT group section

Quoted 17 lines · On Wed, Apr 30, 2025 at 12:29:54PM +0000, tip-bot2 for Rong Xu wrote:

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

Commit-ID:     2cb291596e2c1837238bc322ae3545dacb99d584
Gitweb:        https://git.kernel.org/tip/2cb291596e2c1837238bc322ae3545dacb99d584
Author:        Rong Xu <[email protected]>
AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 30 Apr 2025 13:58:34 +02:00

objtool: Fix up st_info in COMDAT group section

When __elf_create_symbol creates a local symbol, it relocates the first global symbol upwards to make space. Subsequently, elf_update_symbol() is called to refresh the symbol table section. However, this isn't sufficient, as other sections might have the reference to the old symbol index, for instance, the sh_info field of an SHT_GROUP section.

Quoted 8 lines

This patch updates the sh_info field when necessary. This field serves as the key for the COMDAT group. An incorrect key would prevent the linker's from deduplicating COMDAT symbols, leading to duplicate definitions in the final link.

Unfortunately this patch completely destroys performance when adding a bunch of symbols. Which I'm doing in v2 of my klp-build patch set.

What was the use case for this? I don't remember seeing any COMDAT groups in the kernel.

Signature · 1 line
Josh
maintainer
#3 lore raw

PATCH 1/1 objtool: Speed up SHT_GROUP reindexing

From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
From: Josh Poimboeuf <[email protected]>
Date: Wed, 7 May 2025 16:56:55 -0700
Subject: [PATCH] objtool: Speed up SHT_GROUP reindexing

After elf_update_group_sh_info() was introduced, a prototype version of "objtool klp diff" went from taking ~1s to several minutes, due to looping almost endlessly in elf_update_group_sh_info() while creating thousands of local symbols in a file with thousands of sections.

Dramatically improve the performance by marking all symbols' correlated SHT_GROUP sections while reading the object. That way there's no need to search for it every time a symbol gets reindexed.

Fixes 2cb291596e2c ("objtool: Fix up st_info in COMDAT group section")
---
 tools/objtool/elf.c                 | 47 ++++++++++++++++++-----------
 tools/objtool/include/objtool/elf.h |  1 +
 2 files changed, 30 insertions(+), 18 deletions(-)
tools/objtool/elf.c +29 -18
index 8dffe68d705c..ca5d77db692a 100644
@@ -572,28 +572,32 @@ static int read_symbols(struct elf *elf)
 	return -1;
 }
 
-/*
- * @sym's idx has changed.  Update the sh_info in group sections.
- */
-static void elf_update_group_sh_info(struct elf *elf, Elf32_Word symtab_idx,
-				     Elf32_Word new_idx, Elf32_Word old_idx)
+static int mark_group_syms(struct elf *elf)
 {
-	struct section *sec;
+	struct section *symtab, *sec;
+	struct symbol *sym;
+
+	symtab = find_section_by_name(elf, ".symtab");
+	if (!symtab) {
+		ERROR("no .symtab");
+		return -1;
+	}
 
 	list_for_each_entry(sec, &elf->sections, list) {
-		if (sec->sh.sh_type != SHT_GROUP)
-			continue;
-		if (sec->sh.sh_link == symtab_idx &&
-		    sec->sh.sh_info == old_idx) {
-			sec->sh.sh_info = new_idx;
-			mark_sec_changed(elf, sec, true);
-			/*
-			 * Each ELF group should have a unique symbol key.
-			 * Return early on match.
-			 */
-			return;
+		if (sec->sh.sh_type == SHT_GROUP &&
+		    sec->sh.sh_link == symtab->idx) {
+			sym = find_symbol_by_index(elf, sec->sh.sh_info);
+			if (!sym) {
+				ERROR("%s: can't find SHT_GROUP signature symbol",
+				      sec->name);
+				return -1;
+			}
+
+			sym->group_sec = sec;
 		}
 	}
+
+	return 0;
 }
 
 /*
@@ -787,7 +791,11 @@ __elf_create_symbol(struct elf *elf, struct symbol *sym)
 		if (elf_update_sym_relocs(elf, old))
 			return NULL;
 
-		elf_update_group_sh_info(elf, symtab->idx, new_idx, first_non_local);
+		if (old->group_sec) {
+			old->group_sec->sh.sh_info = new_idx;
+			mark_sec_changed(elf, old->group_sec, true);
+		}
+
 		new_idx = first_non_local;
 	}
 
@@ -1060,6 +1068,9 @@ struct elf *elf_open_read(const char *name, int flags)
 	if (read_symbols(elf))
 		goto err;
 
+	if (mark_group_syms(elf))
+		goto err;
+
 	if (read_relocs(elf))
 		goto err;
 
tools/objtool/include/objtool/elf.h +1 -0
index c7c4e87ebe88..0a2fa3ac0079 100644
@@ -72,6 +72,7 @@ struct symbol {
 	u8 ignore	     : 1;
 	struct list_head pv_target;
 	struct reloc *relocs;
+	struct section *group_sec;
 };
 
 struct reloc {
Signature · 1 line
2.49.0
maintainer
#4 lore raw

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

Quoted 5 lines · Josh Poimboeuf

From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
From: Josh Poimboeuf <[email protected]>
Date: Wed, 7 May 2025 16:56:55 -0700
Subject: [PATCH] objtool: Speed up SHT_GROUP reindexing

Urgh, sorry about the patch formatting, the above can obviously be dropped.

Signature · 1 line
Josh
maintainer
#5 lore raw

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

Quoted 9 lines · Josh Poimboeuf
Quoted 5 lines · Josh Poimboeuf

From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
From: Josh Poimboeuf <[email protected]>
Date: Wed, 7 May 2025 16:56:55 -0700
Subject: [PATCH] objtool: Speed up SHT_GROUP reindexing

Urgh, sorry about the patch formatting, the above can obviously be dropped.

No worries, my script did it almost right :-)

Patch seems sane to me; I'll go stick it into objtool/core. Rong if you could verify your case still work correctly that would be appreciated.

author Tested-by
#6 lore raw

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Josh Poimboeuf
Quoted 5 lines · Josh Poimboeuf

From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
From: Josh Poimboeuf <[email protected]>
Date: Wed, 7 May 2025 16:56:55 -0700
Subject: [PATCH] objtool: Speed up SHT_GROUP reindexing

Quoted 7 lines
Quoted 2 lines

Urgh, sorry about the patch formatting, the above can obviously be dropped.

No worries, my script did it almost right :-)

Patch seems sane to me; I'll go stick it into objtool/core. Rong if you could verify your case still work correctly that would be appreciated.

I tested the patch, and it works for me.

I also looked at the patch. It assumes there is only one .symtab section.
In general, there can be multiple symtab sections in an ELF file. But this
(i.e. one symtab) most likely holds for the kernel.

Thanks,

-Rong

Quoted 1 line
author
#7 lore raw

Re: [tip: objtool/core] objtool: Fix up st_info in COMDAT group section

In reply to Josh Poimboeuf
Quoted 24 lines · Josh Poimboeuf
Quoted 22 lines · On Wed, Apr 30, 2025 at 12:29:54PM +0000, tip-bot2 for Rong Xu wrote:

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

Commit-ID:     2cb291596e2c1837238bc322ae3545dacb99d584
Gitweb:        https://git.kernel.org/tip/2cb291596e2c1837238bc322ae3545dacb99d584
Author:        Rong Xu <[email protected]>
AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 30 Apr 2025 13:58:34 +02:00

objtool: Fix up st_info in COMDAT group section

When __elf_create_symbol creates a local symbol, it relocates the first global symbol upwards to make space. Subsequently, elf_update_symbol() is called to refresh the symbol table section. However, this isn't sufficient, as other sections might have the reference to the old symbol index, for instance, the sh_info field of an SHT_GROUP section.

This patch updates the sh_info field when necessary. This field serves as the key for the COMDAT group. An incorrect key would prevent the linker's from deduplicating COMDAT symbols, leading to duplicate definitions in the final link.

Quoted 6 lines
Quoted 3 lines

Unfortunately this patch completely destroys performance when adding a bunch of symbols. Which I'm doing in v2 of my klp-build patch set.

The patch won't add symbols. Do you mean the updates take too much time when adding symbols? It's probably true as we lookup the sections for every added symbols. I did not notice the compile time issues in my builds. If this is a problem, it needs to be fixed.
Thanks for working with v2!

Quoted 3 lines

What was the use case for this? I don't remember seeing any COMDAT groups in the kernel.

In the PGO or AutoFDO builds, we used many COMDAT variables for counters and control variables. I think the compiler also puts the functions defined in header
as COMDAT.
The issue I encountered was objtool moved the variables for profile_filename and
profile_version, but the comdat keys were not updated.

-Rong

Quoted 2 lines

--
Josh

maintainer
#8 lore raw

Re: [tip: objtool/core] objtool: Fix up st_info in COMDAT group section

Quoted 25 lines · Rong Xu
Quoted 24 lines · Josh Poimboeuf
Quoted 22 lines · On Wed, Apr 30, 2025 at 12:29:54PM +0000, tip-bot2 for Rong Xu wrote:

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

Commit-ID:     2cb291596e2c1837238bc322ae3545dacb99d584
Gitweb:        https://git.kernel.org/tip/2cb291596e2c1837238bc322ae3545dacb99d584
Author:        Rong Xu <[email protected]>
AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 30 Apr 2025 13:58:34 +02:00

objtool: Fix up st_info in COMDAT group section

When __elf_create_symbol creates a local symbol, it relocates the first global symbol upwards to make space. Subsequently, elf_update_symbol() is called to refresh the symbol table section. However, this isn't sufficient, as other sections might have the reference to the old symbol index, for instance, the sh_info field of an SHT_GROUP section.

This patch updates the sh_info field when necessary. This field serves as the key for the COMDAT group. An incorrect key would prevent the linker's from deduplicating COMDAT symbols, leading to duplicate definitions in the final link.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Unfortunately this patch completely destroys performance when adding a bunch of symbols. Which I'm doing in v2 of my klp-build patch set.

The patch won't add symbols. Do you mean the updates take too much time when adding symbols?

Right. I was testing a new feature for generating livepatch modules. I was using objtool to add thousands of local symbols to a binary with -ffunction-sections and -fdata-sections, so it was calling that function in a tight loop.

Quoted 2 lines

It's probably true as we lookup the sections for every added symbols. I did not notice the compile time issues in my builds.

Yeah, I had an extreme test case :-)

Quoted 6 lines

If this is a problem, it needs to be fixed.
Thanks for working with v2!

Quoted 3 lines

What was the use case for this? I don't remember seeing any COMDAT groups in the kernel.

Quoted 7 lines

In the PGO or AutoFDO builds, we used many COMDAT variables for counters and control variables. I think the compiler also puts the functions defined in header
as COMDAT.
The issue I encountered was objtool moved the variables for profile_filename and
profile_version, but the comdat keys were not updated.

I see. Thanks for the explanation.

Signature · 1 line
Josh