[PATCH] objtool: fix up st_info in COMDAT group section

[PATCH] objtool: fix up st_info in COMDAT group section

[xur]

From: Rong Xu <xur@google.com>

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.

Signed-off-by: Rong Xu <xur@google.com>
---
 tools/objtool/elf.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 727a3a4fd9d77..8dffe68d705c6 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 	}
 
-- 
2.49.0.850.g28803427d3-goog

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

[tip-bot2 for Rong Xu]

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 <xur@google.com>
AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
Committer:     Peter Zijlstra <peterz@infradead.org>
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.

Signed-off-by: Rong Xu <xur@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/20250425200541.113015-1-xur@google.com
---
 tools/objtool/elf.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 727a3a4..8dffe68 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 	}
 

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

[Josh Poimboeuf]

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 <xur@google.com>
> AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
> Committer:     Peter Zijlstra <peterz@infradead.org>
> 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.
> 
> Signed-off-by: Rong Xu <xur@google.com>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Link: https://lkml.kernel.org/r/20250425200541.113015-1-xur@google.com

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.

-- 
Josh

[PATCH] objtool: Speed up SHT_GROUP reindexing

[Josh Poimboeuf]

From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
From: Josh Poimboeuf <jpoimboe@kernel.org>
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")
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>
---
 tools/objtool/elf.c                 | 47 ++++++++++++++++++-----------
 tools/objtool/include/objtool/elf.h |  1 +
 2 files changed, 30 insertions(+), 18 deletions(-)

diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 8dffe68d705c..ca5d77db692a 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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;
 
diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h
index c7c4e87ebe88..0a2fa3ac0079 100644
--- a/tools/objtool/include/objtool/elf.h
+++ b/tools/objtool/include/objtool/elf.h
@@ -72,6 +72,7 @@ struct symbol {
 	u8 ignore	     : 1;
 	struct list_head pv_target;
 	struct reloc *relocs;
+	struct section *group_sec;
 };
 
 struct reloc {
-- 
2.49.0

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

[Josh Poimboeuf]

On Wed, May 07, 2025 at 05:11:03PM -0700, Josh Poimboeuf wrote:
> From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
> Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
> From: Josh Poimboeuf <jpoimboe@kernel.org>
> 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.

-- 
Josh

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

[Peter Zijlstra]

On Wed, May 07, 2025 at 05:11:53PM -0700, Josh Poimboeuf wrote:
> On Wed, May 07, 2025 at 05:11:03PM -0700, Josh Poimboeuf wrote:
> > From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
> > Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
> > From: Josh Poimboeuf <jpoimboe@kernel.org>
> > 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.

Re: [PATCH] objtool: Speed up SHT_GROUP reindexing

[Rong Xu]

On Thu, May 8, 2025 at 8:27 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Wed, May 07, 2025 at 05:11:53PM -0700, Josh Poimboeuf wrote:
> > On Wed, May 07, 2025 at 05:11:03PM -0700, Josh Poimboeuf wrote:
> > > From 2a33e583c87e3283706f346f9d59aac20653b7fd Mon Sep 17 00:00:00 2001
> > > Message-ID: <2a33e583c87e3283706f346f9d59aac20653b7fd.1746662991.git.jpoimboe@kernel.org>
> > > From: Josh Poimboeuf <jpoimboe@kernel.org>
> > > 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.

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.

Tested-by: Rong Xu <xur@google.com>

Thanks,

-Rong

>

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

[Rong Xu]

On Wed, May 7, 2025 at 4:22 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> 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 <xur@google.com>
> > AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
> > Committer:     Peter Zijlstra <peterz@infradead.org>
> > 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.
> >
> > Signed-off-by: Rong Xu <xur@google.com>
> > Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> > Link: https://lkml.kernel.org/r/20250425200541.113015-1-xur@google.com
>
> 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!
>
> 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

> --
> Josh

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

[Josh Poimboeuf]

On Thu, May 08, 2025 at 05:45:18PM -0700, Rong Xu wrote:
> On Wed, May 7, 2025 at 4:22 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote:
> >
> > 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 <xur@google.com>
> > > AuthorDate:    Fri, 25 Apr 2025 13:05:41 -07:00
> > > Committer:     Peter Zijlstra <peterz@infradead.org>
> > > 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.
> > >
> > > Signed-off-by: Rong Xu <xur@google.com>
> > > Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> > > Link: https://lkml.kernel.org/r/20250425200541.113015-1-xur@google.com
> >
> > 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.

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

> If this is a problem, it needs to be fixed.
> Thanks for working with v2!
> >
> > 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.

I see.  Thanks for the explanation.

-- 
Josh