Mapping symbol optimization: implicit one at section beginning

[Richard Earnshaw (lists)]

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

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.

> ---
> 
> I have written a detailed analysis at
> https://maskray.me/blog/2024-07-21-mapping-symbols-rethinking-for-efficiency
> and proposed an alternative scheme to address the size concern:
> 
> * Text sections: Assume an implicit $x at offset 0. Add an ending $x
> if the final data isn't instructions.
> * Non-text sections: Assume an implicit $d at offset 0. Add an ending
> $d only if the final data isn't data commands.
> 
> This approach eliminates most mapping symbols while ensuring correct
> disassembly. Here is an illustrated assembler example:
> 
> .section .text.f0,"ax"
>   ret
> // emit $d
>   .long 42
> // emit $x. Without this, .text.f1 might be interpreted as data.
> 
> .section .text.f1,"ax"
>   ret
> 
> However, omitting a mapping symbol at offset 0 for sections with
> instructions is currently non-conformant for Arm. An ABI update has
> been requested to address this
> (https://github.com/ARM-software/abi-aa/issues/274). RISC-V ABI
> doesn't have the requirement.
> 
> **While some interoperability concerns might arise, they're unlikely
> to impact a majority of users.**
> 
> For instance, if a text section with trailing data is assembled using
> the traditional behavior, the last mapping symbol will be $d. When
> linked with another text section assembled using the new behavior
> (lacking an initial $x), disassemblers might misinterpret the start of
> the latter section as data.
> 
> Similarly, linker scripts that combine non-text and text sections
> could lead to text sections appearing in a data state.
> 
> Ultimately, the proposed alternative scheme effectively addresses
> symbol table bloat, but requires careful consideration for compliance
> and interoperability.
> I have thought about **an assembler option
> --[no-]optimize-mapping-symbols**, which can be enabled by GCC as
> -Wa,--optimize-mapping-symbols.
> With this optimization enabled, most mapping symbols will be
> eliminated for architectures that don't often place constant
> pools/jump tables in text sections.
> This optimization works well when there is a single code state (e.g.
> AArch64) and can be extended when there are more states.
> 
> RISC-V $x<isa> poses some challenges:
> https://maskray.me/blog/2024-07-21-mapping-symbols-rethinking-for-efficiency#risc-v-isa-extension
> 
> 
> ---
> 
> % cat a.c
> void f0() {}
> void f1() {}
> void f2() {}
> int d1 = 1;
> int d2 = 2;
> asm(
> ".pushsection .nonalloc,\n"
> ".balign 4\n"
> ".long 0\n"
> ".popsection\n"
> );
> % aarch64-linux-gnu-gcc -ffunction-sections -fdata-sections a.c
> % llvm-objdump -d --show-all-symbols a.o  # GNU --show-all-symbols
> doesn't display mapping symbols
> 
> a.o:    file format elf64-littleaarch64
> 
> Disassembly of section .text.f0:
> 
> 0000000000000000 <$x>:
> 0000000000000000 <f0>:
>        0: d503201f      nop
>        4: d65f03c0      ret
> 
> Disassembly of section .text.f1:
> 
> 0000000000000000 <$x>:
> 0000000000000000 <f1>:
>        0: d503201f      nop
>        4: d65f03c0      ret
> 
> Disassembly of section .text.f2:
> 
> 0000000000000000 <$x>:
> 0000000000000000 <f2>:
>        0: d503201f      nop
>        4: d65f03c0      ret
> % readelf -sX a.o
> 
> Symbol table '.symtab' contains 26 entries:
>    Num:    Value          Size Type    Bind   Vis+Other Ndx(SecName)
> Name [+ Version Info]
>      0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
>      1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS           a.c
>      2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 (.text)   .text
>      3: 0000000000000000     0 SECTION LOCAL  DEFAULT    2 (.data)   .data
>      4: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 (.bss)    .bss
>      5: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 (.text.f0) .text.f0
>      6: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    4 (.text.f0) $x
>      7: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 (.text.f1) .text.f1
>      8: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    5 (.text.f1) $x
>      9: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 (.text.f2) .text.f2
>     10: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    6 (.text.f2) $x
>     11: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 (.data.d1) .data.d1
>     12: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    7 (.data.d1) $d
>     13: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 (.data.d2) .data.d2
>     14: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    8 (.data.d2) $d
>     15: 0000000000000000     0 SECTION LOCAL  DEFAULT    9 (.nonalloc) .nonalloc
>     16: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    9 (.nonalloc) $d
>     17: 0000000000000000     0 SECTION LOCAL  DEFAULT   11
> (.note.GNU-stack) .note.GNU-stack
>     18: 0000000000000014     0 NOTYPE  LOCAL  DEFAULT   12 (.eh_frame) $d
>     19: 0000000000000000     0 SECTION LOCAL  DEFAULT   12 (.eh_frame) .eh_frame
>     20: 0000000000000000     0 SECTION LOCAL  DEFAULT   10 (.comment) .comment
>     21: 0000000000000000     8 FUNC    GLOBAL DEFAULT    4 (.text.f0) f0
>     22: 0000000000000000     8 FUNC    GLOBAL DEFAULT    5 (.text.f1) f1
>     23: 0000000000000000     8 FUNC    GLOBAL DEFAULT    6 (.text.f2) f2
>     24: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    7 (.data.d1) d1
>     25: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    8 (.data.d2) d2