Mapping symbol optimization: implicit one at section beginning

[Fangrui Song]

On Mon, Jul 29, 2024 at 6:06 AM Richard Earnshaw (lists)
<Richard.Earnshaw@arm.com> wrote:
>
> On 22/07/2024 19:37, Fangrui Song wrote:
> > tl;dr Add gas option --[no-]optimize-mapping-symbols
> >
> > Except the trivial cases (e.g. empty section), in all(?) gas ports
> > that support mapping symbols,
> >
> > * A non-text section (data, debug, etc) almost always starts with an initial $d.
> > * A text section almost always starts with an initial $x (or the
> > equivalent for the port, e.g. $a/$t). aaelf32 and aaelf64 requires a
> > mapping symbol at offset 0.
> >
> > This strategy can significantly inflate the symbol table, particularly
> > in 64-bit architectures (sizeof(Elf64_Sym) == 24) with larger
> > programs.
> > This issue becomes more pronounced when using -ffunction-sections
> > -fdata-sections, which generates numerous small sections.
> > An example is provided at the end of this message.
> >
>
> Sorry, this is the wrong way to address this problem as was explained on the ABI ticket relating to this proposal.  At the very least it breaks the ABI rules.
>
> The problem with omitting the symbols is that when you concatenate sections from different object files a missing symbol cannot be automatically inserted to correct an incorrect symbol inherited from the preceding section.  Nor can the first object file guess what a succeeding block will need as its mapping (it would have to define a symbol beyond the scope of its own size, and furthermore you could then end up with conflicts when the guess is wrong).

Why is this a wrong way? While a foolproof system could be desirable,
it's important to consider that a large portion of our user base
doesn't require such strict guarantees.
While eliminating unnecessary mapping symbols at the linker is a
potential solution, it doesn't address the concern of increased
relocatable file sizes.
See below for my analysis of the linker performance.

https://github.com/ARM-software/abi-aa/issues/274#issuecomment-2246782514
has analyzed the `sym.st_value == sec.sh_size` case.

> The right solution to this problem is for a linker to elide duplicate mapping symbols when linking, once it is *known* that the later symbol is redundant.  That is, when the linker concatenates sections such that we have
>
> [input section 1]
> $a
> ...
> $x
> ...
> $a
> ...
> [input section 2]
> $a   // Redundant
> ...
>
>
> This can be simplified to
>
> $a
> ...
> $x
> ...
> $a  // Now covers code from input section 2 as well.
> ...
>
> R.

This would require a smart linker and there is significant performance penalty.

Features such as input section descriptions, --symbol-ordering-file,
and --call-graph-profile-sort can make symbol order not match the
input file order.
I have maded a local change to lld that stable sorts local symbols by address.
This results in a 5% increase in link time, making it impractical for
default on.

In contrast, the assembler option (we can keep it off by default)
offers a more effective solution by reducing both relocatable and
image file sizes.
As I have explained, many users are concerned with these
interoperability issues.

---

It's worth noting that the current toolchain already has limitations.
For instance, data sections without alignment directives (excluding
BSS) might lack '$d' symbols, and mixing data and text sections can
introduce state transition problems.

% cat x.c
char var = 1;
char arr[2] = {1};
% arm-linux-gnueabi-gcc -c -fdata-sections x.c && objdump -t x.o  #
aarch64-linux-gnu-gcc is similar

x.o:     file format elf32-little

SYMBOL TABLE:
00000000 l    df *ABS*  00000000 x.c
00000000 l    d  .text  00000000 .text
00000000 l    d  .data  00000000 .data
00000000 l    d  .bss   00000000 .bss
00000000 l    d  .data.var      00000000 .data.var
00000000 l    d  .data.arr      00000000 .data.arr
00000000 l       .data.arr      00000000 $d
...

LLVM integrated assembler's AArch32 port doesn't insert '$d' unless
code is present, which could lead to similar issues.
(https://reviews.llvm.org/D30724)

% clang -c --target=armv7-linux-gnueabi -fdata-sections x.c && objdump -t x.o

x.o:     file format elf32-little

SYMBOL TABLE:
00000000 l    df *ABS*  00000000 x.c
00000000 g     O .data.var      00000001 var
00000000 g     O .data.arr      00000002 arr