ld: Fix string merging origin symbol address

  Hi,

This patch fixes ld merge string algorithm to calculate the correct origin address of merged symbols.
The problem is with the current merge string algorithm, it is no longer capable to assign the correct origin
address of a merged string resulting in multiple symbols pointing to the same address. This can be seen in the
generated map file.

The changes include:
-Modifying bfd/merge.c: re-added in struct sec_merge_hash_entry the field
struct sec_merge_sec_info *secinfo to keep track the size of string we are
merging
-testsuite/ld-arm/rodata-merge-map.sym: revert back to the commit 26ec71f5128a as we reintroduced
the old merging mechanism without changing the hash function and power-of-two hash table for speed-up
-testsuite/ld-arm/rodata-merge-map-address.d: related test
-testsuite/ld-arm/rodata-merge-map-address1.s: related test
-testsuite/ld-arm/rodata-merge-map-address2.s: related test
-testsuite/ld-arm/rodata-merge-map-address3.s: related test
-testsuite/ld-arm/rodata-merge-map-address.map: related test

Please review the patch and let me know if there are any issues or suggestions!

Best regards,
Guillaume

--

With the current string merging algorithm we no longer keep the size of each
section symbol of the string we are currently merging. This result in the
generated map file indicating that different symbols are resolved onto the
same address.

* bfd/merge.c: re-added in struct sec_merge_hash_entry the field
struct sec_merge_sec_info *secinfo to keep track the size of string we are
merging.
* testsuite/ld-arm/rodata-merge-map.sym: revert back to the commit 26ec71f5128a
* testsuite/ld-arm/rodata-merge-map-address.d: related test
* testsuite/ld-arm/rodata-merge-map-address1.s: related test
* testsuite/ld-arm/rodata-merge-map-address2.s: related test
* testsuite/ld-arm/rodata-merge-map-address3.s: related test
* testsuite/ld-arm/rodata-merge-map-address.map: related test

Signed-off-by: Guillaume VACHERIAS <guillaume.vacherias@foss.st.com>
---
 bfd/merge.c                                   | 31 ++++++----
 ld/testsuite/ld-arm/arm-elf.exp               |  1 +
 .../ld-arm/rodata-merge-map-address.d         |  6 ++
 .../ld-arm/rodata-merge-map-address.map       | 59 +++++++++++++++++++
 .../ld-arm/rodata-merge-map-address1.s        |  8 +++
 .../ld-arm/rodata-merge-map-address2.s        |  8 +++
 .../ld-arm/rodata-merge-map-address3.s        |  8 +++
 ld/testsuite/ld-arm/rodata-merge-map.sym      |  3 +-
 8 files changed, 113 insertions(+), 11 deletions(-)
 create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address.d
 create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address.map
 create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address1.s
 create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address2.s
 create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address3.s
  

Hello,

On Fri, 4 Apr 2025, Guillaume VACHERIAS - foss wrote:

> This patch fixes ld merge string algorithm to calculate the correct 
> origin address of merged symbols. The problem is with the current merge 
> string algorithm, it is no longer capable to assign the correct origin 
> address of a merged string resulting in multiple symbols pointing to the 
> same address. This can be seen in the generated map file.

It can be seen there.  But why would it matter?  It's an inherent property 
of merged contents that pointers into the original content will possibly 
be, well, merged in the output content and hence may point to the same 
addresses or to different ones with different distances (including being 
put in front of other markers where they normally would be placed after, 
without merging).

E.g. in your testcase if you replace "ghi" in the third file with "def" 
(same as second file), then nothing of the third file will survive, and 
the section anchor '$d' of it will be meaningless.  Why do you think it's 
more meaningful if the contents remain 'ghi' and unmerged?

So, what exactly do you need from the original sections to survive, and 
why, and how does that need change when the contents are partly or 
completely vanishing?


Ciao,
Michael.

> 
> The changes include:
> -Modifying bfd/merge.c: re-added in struct sec_merge_hash_entry the field
> struct sec_merge_sec_info *secinfo to keep track the size of string we are
> merging
> -testsuite/ld-arm/rodata-merge-map.sym: revert back to the commit 26ec71f5128a as we reintroduced
> the old merging mechanism without changing the hash function and power-of-two hash table for speed-up
> -testsuite/ld-arm/rodata-merge-map-address.d: related test
> -testsuite/ld-arm/rodata-merge-map-address1.s: related test
> -testsuite/ld-arm/rodata-merge-map-address2.s: related test
> -testsuite/ld-arm/rodata-merge-map-address3.s: related test
> -testsuite/ld-arm/rodata-merge-map-address.map: related test
> 
> Please review the patch and let me know if there are any issues or suggestions!
> 
> Best regards,
> Guillaume
> 
> --
> 
> With the current string merging algorithm we no longer keep the size of each
> section symbol of the string we are currently merging. This result in the
> generated map file indicating that different symbols are resolved onto the
> same address.
> 
> * bfd/merge.c: re-added in struct sec_merge_hash_entry the field
> struct sec_merge_sec_info *secinfo to keep track the size of string we are
> merging.
> * testsuite/ld-arm/rodata-merge-map.sym: revert back to the commit 26ec71f5128a
> * testsuite/ld-arm/rodata-merge-map-address.d: related test
> * testsuite/ld-arm/rodata-merge-map-address1.s: related test
> * testsuite/ld-arm/rodata-merge-map-address2.s: related test
> * testsuite/ld-arm/rodata-merge-map-address3.s: related test
> * testsuite/ld-arm/rodata-merge-map-address.map: related test
> 
> Signed-off-by: Guillaume VACHERIAS <guillaume.vacherias@foss.st.com>
> ---
>  bfd/merge.c                                   | 31 ++++++----
>  ld/testsuite/ld-arm/arm-elf.exp               |  1 +
>  .../ld-arm/rodata-merge-map-address.d         |  6 ++
>  .../ld-arm/rodata-merge-map-address.map       | 59 +++++++++++++++++++
>  .../ld-arm/rodata-merge-map-address1.s        |  8 +++
>  .../ld-arm/rodata-merge-map-address2.s        |  8 +++
>  .../ld-arm/rodata-merge-map-address3.s        |  8 +++
>  ld/testsuite/ld-arm/rodata-merge-map.sym      |  3 +-
>  8 files changed, 113 insertions(+), 11 deletions(-)
>  create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address.d
>  create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address.map
>  create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address1.s
>  create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address2.s
>  create mode 100644 ld/testsuite/ld-arm/rodata-merge-map-address3.s
> 
> diff --git a/bfd/merge.c b/bfd/merge.c
> index f09078ae31e..d61832de446 100644
> --- a/bfd/merge.c
> +++ b/bfd/merge.c
> @@ -63,6 +63,8 @@ struct sec_merge_hash_entry
>      /* Entry this is a suffix of (if alignment is 0).  */
>      struct sec_merge_hash_entry *suffix;
>    } u;
> +  /* Which section is it in.  */
> +  struct sec_merge_sec_info *secinfo;
>    /* Next entity in the hash table (in order of entering).  */
>    struct sec_merge_hash_entry *next;
>    char str[1];
> @@ -235,7 +237,8 @@ sec_merge_resize (struct sec_merge_hash *table, unsigned added)
>  static struct sec_merge_hash_entry *
>  sec_merge_hash_insert (struct sec_merge_hash *table,
>  		 const char *string,
> -		 uint64_t hash, unsigned int len, unsigned int _index)
> +		 uint64_t hash, unsigned int len, unsigned int _index,
> +		 struct sec_merge_sec_info *secinfo)
>  {
>    struct bfd_hash_table *bfdtab = &table->table;
>    struct sec_merge_hash_entry *hashp;
> @@ -249,6 +252,7 @@ sec_merge_hash_insert (struct sec_merge_hash *table,
>    hashp->len = len;
>    hashp->alignment = 0;
>    hashp->u.suffix = NULL;
> +  hashp->secinfo = secinfo;
>    hashp->next = NULL;
>  
>    if (needs_resize (bfdtab->count, 1, table->nbuckets))
> @@ -395,7 +399,8 @@ hashit (struct sec_merge_hash *table, const char *string, unsigned int *plen)
>  static struct sec_merge_hash_entry *
>  sec_merge_hash_lookup (struct sec_merge_hash *table, const char *string,
>  		       unsigned int len, uint64_t hash,
> -		       unsigned int alignment)
> +		       unsigned int alignment,
> +		       struct sec_merge_sec_info *secinfo)
>  {
>    struct sec_merge_hash_entry *hashp;
>    unsigned int _index;
> @@ -423,7 +428,7 @@ sec_merge_hash_lookup (struct sec_merge_hash *table, const char *string,
>        _index = (_index + 1) & (nbuckets - 1);
>      }
>  
> -  hashp = sec_merge_hash_insert (table, string, hash, len, _index);
> +  hashp = sec_merge_hash_insert (table, string, hash, len, _index, secinfo);
>    if (hashp == NULL)
>      return NULL;
>    hashp->alignment = alignment;
> @@ -551,7 +556,7 @@ sec_merge_emit (bfd *abfd, struct sec_merge_sec_info *secinfo,
>    if (pad == NULL)
>      return false;
>  
> -  for (; entry != NULL; entry = entry->next)
> +  for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next)
>      {
>        const char *str;
>        bfd_size_type len;
> @@ -586,7 +591,6 @@ sec_merge_emit (bfd *abfd, struct sec_merge_sec_info *secinfo,
>  
>        off += len;
>      }
> -  BFD_ASSERT (!entry);
>  
>    /* Trailing alignment needed?  */
>    off = sec->size - off;
> @@ -770,7 +774,7 @@ record_section (struct sec_merge_info *sinfo,
>        if (!eltalign || eltalign > mask)
>  	eltalign = mask + 1;
>        entry = sec_merge_hash_lookup (sinfo->htab, (char *) p, len, hash,
> -				     (unsigned) eltalign);
> +				     (unsigned) eltalign, secinfo);
>        if (! entry)
>  	goto error_return;
>        if (! append_offsetmap (secinfo, ofs, entry))
> @@ -942,8 +946,18 @@ merge_strings (struct sec_merge_info *sinfo)
>    secinfo = sinfo->chain;
>    for (e = sinfo->htab->first; e; e = e->next)
>      {
> +      if (e->secinfo != secinfo)
> +	{
> +	  secinfo->sec->size = size;
> +	  secinfo = e->secinfo;
> +	}
>        if (e->alignment)
>  	{
> +	  if (e->secinfo->first_str == NULL)
> +	{
> +		e->secinfo->first_str = e;
> +		size = 0;
> +	}
>  	  size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1);
>  	  e->u.index = size;
>  	  size += e->len;
> @@ -961,14 +975,12 @@ merge_strings (struct sec_merge_info *sinfo)
>  	*a = e->next;
>  	if (e->len)
>  	  {
> +      e->secinfo = e->u.suffix->secinfo;
>  	    e->alignment = e->u.suffix->alignment;
>  	    e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len);
>  	  }
>        }
>  
> -  BFD_ASSERT (!secinfo->first_str);
> -  secinfo->first_str = sinfo->htab->first;
> -
>    return secinfo;
>  }
>  
> @@ -1095,7 +1107,6 @@ _bfd_write_merged_section (bfd *output_bfd, asection *sec, void *psecinfo)
>      }
>  
>    BFD_ASSERT (sec == secinfo->sec);
> -  BFD_ASSERT (secinfo == secinfo->sinfo->chain);
>    if (! sec_merge_emit (output_bfd, secinfo, contents))
>      return false;
>  
> diff --git a/ld/testsuite/ld-arm/arm-elf.exp b/ld/testsuite/ld-arm/arm-elf.exp
> index cacd3bddfd4..ea1ca2104b5 100644
> --- a/ld/testsuite/ld-arm/arm-elf.exp
> +++ b/ld/testsuite/ld-arm/arm-elf.exp
> @@ -430,6 +430,7 @@ run_dump_test "movw-shared-4"
>  run_dump_test "rel32-reject"
>  run_dump_test "rel32-reject-pie"
>  run_dump_test "pie-bind-locally"
> +run_dump_test "rodata-merge-map-address"
>  
>  # Exclude non-ARM-EABI targets.
>  
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map-address.d b/ld/testsuite/ld-arm/rodata-merge-map-address.d
> new file mode 100644
> index 00000000000..9e79c1f0464
> --- /dev/null
> +++ b/ld/testsuite/ld-arm/rodata-merge-map-address.d
> @@ -0,0 +1,6 @@
> +#name: Data symbol merge address in map file
> +#source: rodata-merge-map-address1.s
> +#source: rodata-merge-map-address2.s
> +#source: rodata-merge-map-address3.s
> +#ld: -T rodata-merge-map.ld
> +#map: rodata-merge-map-address.map
> \ No newline at end of file
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map-address.map b/ld/testsuite/ld-arm/rodata-merge-map-address.map
> new file mode 100644
> index 00000000000..8658fe62a27
> --- /dev/null
> +++ b/ld/testsuite/ld-arm/rodata-merge-map-address.map
> @@ -0,0 +1,59 @@
> +There are no discarded input sections
> +
> +Memory Configuration
> +
> +Name             Origin             Length             Attributes
> +\*default\*        0x00000000         0xffffffff
> +
> +Linker script and memory map
> +
> +
> +\.glue_7         0x00000000        0x0
> + \.glue_7        0x00000000        0x0 linker stubs
> +
> +\.glue_7t        0x00000000        0x0
> + \.glue_7t       0x00000000        0x0 linker stubs
> +
> +\.vfp11_veneer   0x00000000        0x0
> + \.vfp11_veneer  0x00000000        0x0 linker stubs
> +
> +\.v4_bx          0x00000000        0x0
> + \.v4_bx         0x00000000        0x0 linker stubs
> +
> +\.text           0x00000000        0x0
> + \.text          0x00000000        0x0 .*rodata-merge-map-address1\.o
> + \.text          0x00000000        0x0 .*rodata-merge-map-address2\.o
> + \.text          0x00000000        0x0 .*rodata-merge-map-address3\.o
> +
> +\.rodata         0x00000000        0xc
> + \*\(\.rodata\*\)
> + \.rodata\.foo\.str1\.1
> +                0x00000000        0x4 .*rodata-merge-map-address1\.o
> + \.rodata\.bar\.str1\.1
> +                0x00000004        0x4 .*rodata-merge-map-address2\.o
> + \.rodata\.baz\.str1\.1
> +                0x00000008        0x4 .*rodata-merge-map-address3\.o
> +LOAD .*rodata-merge-map-address1\.o
> +LOAD .*rodata-merge-map-address2\.o
> +LOAD .*rodata-merge-map-address3\.o
> +OUTPUT\(.* elf32-littlearm\)
> +LOAD linker stubs
> +
> +\.data           0x0000000c        0x0
> + \.data          0x0000000c        0x0 .*rodata-merge-map-address1\.o
> + \.data          0x0000000c        0x0 .*rodata-merge-map-address2\.o
> + \.data          0x0000000c        0x0 .*rodata-merge-map-address3\.o
> +
> +\.bss            0x0000000c        0x0
> + \.bss           0x0000000c        0x0 .*rodata-merge-map-address1\.o
> + \.bss           0x0000000c        0x0 .*rodata-merge-map-address2\.o
> + \.bss           0x0000000c        0x0 .*rodata-merge-map-address3\.o
> +
> +\.ARM\.attributes
> +                0x00000000       0x14
> + \.ARM\.attributes
> +                0x00000000       0x14 .*rodata-merge-map-address1\.o
> + \.ARM\.attributes
> +                0x00000014       0x14 .*rodata-merge-map-address2\.o
> + \.ARM\.attributes
> +                0x00000028       0x14 .*rodata-merge-map-address3\.o
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map-address1.s b/ld/testsuite/ld-arm/rodata-merge-map-address1.s
> new file mode 100644
> index 00000000000..ccb8ee327b3
> --- /dev/null
> +++ b/ld/testsuite/ld-arm/rodata-merge-map-address1.s
> @@ -0,0 +1,8 @@
> +@ Test to ensure that the origin of symbol address in map file
> +@ won't overlap
> +@ This file contains the 1st contribution, which is expected to
> +@ generate a $d symbol at its beginning.
> +
> +        .section        .rodata.foo.str1.1,"aMS",%progbits,1
> +.LC0:
> +        .string "abc"
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map-address2.s b/ld/testsuite/ld-arm/rodata-merge-map-address2.s
> new file mode 100644
> index 00000000000..af50383d023
> --- /dev/null
> +++ b/ld/testsuite/ld-arm/rodata-merge-map-address2.s
> @@ -0,0 +1,8 @@
> +@ Test to ensure that the origin of symbol address in map file
> +@ won't overlap
> +@ This file contains the 2nd contribution, which is expected to
> +@ generate a $d symbol at its beginning.
> +
> +        .section        .rodata.bar.str1.1,"aMS",%progbits,1
> +.LC0:
> +        .string "def"
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map-address3.s b/ld/testsuite/ld-arm/rodata-merge-map-address3.s
> new file mode 100644
> index 00000000000..28750cfcdb2
> --- /dev/null
> +++ b/ld/testsuite/ld-arm/rodata-merge-map-address3.s
> @@ -0,0 +1,8 @@
> +@ Test to ensure that the origin of symbol address in map file
> +@ won't overlap
> +@ This file contains the 3nd contribution, which is expected to
> +@ generate a $d symbol at its beginning.
> +
> +        .section        .rodata.baz.str1.1,"aMS",%progbits,1
> +.LC0:
> +        .string "ghi"
> diff --git a/ld/testsuite/ld-arm/rodata-merge-map.sym b/ld/testsuite/ld-arm/rodata-merge-map.sym
> index f8edc2e852b..245ce7c3ffa 100644
> --- a/ld/testsuite/ld-arm/rodata-merge-map.sym
> +++ b/ld/testsuite/ld-arm/rodata-merge-map.sym
> @@ -1,7 +1,8 @@
>  
> -Symbol table '.symtab' contains 4 entries:
> +Symbol table '.symtab' contains 5 entries:
>     Num:    Value  Size Type    Bind   Vis      Ndx Name
>       0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
>       1: 00000000     0 SECTION LOCAL  DEFAULT    1.*
>       2: 00000000     0 SECTION LOCAL  DEFAULT    2.*
>       3: 00000000     0 NOTYPE  LOCAL  DEFAULT    1 \$d
> +     4: 0000000c     0 NOTYPE  LOCAL  DEFAULT    1 \$d
>