In object files, certain code patterns incorporate data directly within the code or transit between instruction sets. This practice can pose challenges for disassemblers as data might be mistakenly interpreted as code, leading to nonsensical output. In addition, code from instruction set A might be disassembled as instruction set B. To address the issues, some architectures define mapping symbols to describe state transition. Let's explore this concept using an AArch32 code example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

.text
  adr     r0, .LJTI0_0
  vldr    d0, .LCPI0_0
  bl thumb_callee
.LBB0_1:
  nop
.LBB0_2:
  nop

.LCPI0_0:
  .long   3367254360                      @ double 1.234
  .long   1072938614

  nop

.LJTI0_0:
  .long   .LBB0_1
  .long   .LBB0_2

.thumb
.type thumb_callee, %function
thumb_callee:
  bx lr

Jump Tables (.LJTI0_0): Jump tables, like .LJTI0_0, store a list of absolute addresses used for efficient branching. They can reside in either data or text sections, each with its trade-offs.

Jump tables (.LJTI0_0): Jump tables can reside in either data or text sections, each with its trade-offs. Here we see a jump table in the text section, allowing a single instruction to take its address. Other architectures generally prefer to place jump tables in data sections. While avoiding data in code, RISC architectures typically require two instructions to materialize the address, since text/data distance can be pretty large.

Constant pool (.LCPI0_0): The vldr instruction loads a 16-byte floating-point literal to the SIMD&FP register.

ISA transition: This code blends A32 and T32 instructions (the latter used in thumb_callee).

In these cases, a dumb disassembler might treat data as code and try disassembling them as instructions. Assemblers create mapping symbols to assist disassemblers. For this example, the assembled object file looks like the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

$a:
  ...

$d:
  .long   3367254360                      @ double 1.234
  .long   1072938614

$a:
  nop

$d:
  .long   .LBB0_1
  .long   .LBB0_2
  .long   .LBB0_3

$t:
thumb_callee:
  bx lr

Now, let's delve into how mapping symbols are managed within the toolchain.

Disassemblers

llvm-objdump sorts symbols, including mapping symbols, relative to the current section, presenting interleaved labels and instructions. Mapping symbols act as signals for the disassembler to switch states.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

% llvm-objdump -d --triple=armv7 --show-all-symbols a.o

a.o:    file format elf32-littlearm

Disassembly of section .text:

00000000 <$a.0>:
       0: e28f0018      add     r0, pc, #24
       4: ed9f0b02      vldr    d0, [pc, #8]            @ 0x14
       8: ebfffffe      bl      0x8                     @ imm = #-0x8
       c: e320f000      hint    #0x0
      10: e320f000      hint    #0x0

00000014 <$d.1>:
      14: 58 39 b4 c8   .word   0xc8b43958
      18: 76 be f3 3f   .word   0x3ff3be76

0000001c <$a.2>:
      1c: e320f000      nop

00000020 <$d.3>:
      20: 0c 00 00 00   .word   0x0000000c
      24: 10 00 00 00   .word   0x00000010

00000028 <$t.4>:
00000028 <thumb_callee>:
      28: 4770          bx      lr

I changed llvm-objdump 18 to not display mapping symbols as labels unless --show-all-symbols is specified.

nm

Both llvm-nm and GNU nm typically conceal mapping symbols alongside STT_FILE and STT_SECTION symbols. However, you can reveal these special symbols using the --special-syms option.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

% cat a.s
foo:
  bl thumb_callee
.long 42
.thumb
thumb_callee:
  bx lr
% clang --target=arm-linux-gnueabi -c a.s
% llvm-nm a.o
00000000 t foo
00000008 t thumb_callee
% llvm-nm --special-syms a.o
00000000 t $a.0
00000004 t $d.1
00000008 t $t.2
00000000 t foo
00000008 t thumb_callee

GNU nm behaves similarly, but with a slight quirk. If the default BFD target isn't AArch32, mapping symbols are displayed even without --special-syms.

1
2
3
4
5
6
7
8
9

% arm-linux-gnueabi-nm a.o
00000000 t foo
00000008 t thumb_callee
% nm a.o
00000000 t $a.0
00000004 t $d.1
00000008 t $t.2
00000000 t foo
00000008 t thumb_callee

Symbolizers

Mapping symbols, being non-unique and lacking descriptive names, are intentionally omitted by symbolizers like addr2line and llvm-symbolizer. Their primary role lies in guiding the disassembly process rather than providing human-readable context.

Size problem: symbol table bloat

While mapping symbols are useful, they 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

% cat a.c
void f0() {}
void f1() {}
void f2() {}
int d1 = 1;
int d2 = 2;
% clang -c --target=aarch64 -ffunction-sections -fdata-sections a.c
% llvm-readelf -sX a.o

Symbol table '.symtab' contains 17 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     3 (.text.f0) .text.f0
     3: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     3 (.text.f0) $x.0
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT     4 (.text.f1) .text.f1
     5: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     4 (.text.f1) $x.1
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT     5 (.text.f2) .text.f2
     7: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     5 (.text.f2) $x.2
     8: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     6 (.data.d1) $d.3
     9: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     7 (.data.d2) $d.4
    10: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT     8 (.comment) $d.5
    11: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    10 (.eh_frame) $d.6
    12: 0000000000000000     4 FUNC    GLOBAL DEFAULT     3 (.text.f0) f0
    13: 0000000000000000     4 FUNC    GLOBAL DEFAULT     4 (.text.f1) f1
    14: 0000000000000000     4 FUNC    GLOBAL DEFAULT     5 (.text.f2) f2
    15: 0000000000000000     4 OBJECT  GLOBAL DEFAULT     6 (.data.d1) d1
    16: 0000000000000000     4 OBJECT  GLOBAL DEFAULT     7 (.data.d2) d2

Except the trivial cases (e.g. empty section), in both GNU assembler and LLVM integrated assembler:

• A non-text section (data, debug, etc) almost always starts with an initial $d.
• A text section almost always starts with an initial $x. ABI requires a mapping symbol at offset 0.

The behaviors ensure that each function or data symbol has a corresponding mapping symbol, while extra mapping symbols might occur in rare cases. Thereore, the number of mapping symbols in the output symbol table usually exceeds 50%.

Most text sections have 2 or 3 symbols:

• A STT_FUNC symbol.
• A STT_SECTION symbol due to a referenced from .eh_frame. This symbol is absent if -fno-asynchronous-unwind-tables.
• A $x mapping symbol.

During the linking process, the linker combines input sections and eliminates STT_SECTION symbols.

Alternative mapping symbol scheme

I have proposed an alternaive 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:

1
2
3
4
5
6
7
8

.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

The ending mapping symbol is to ensure the subsequent section in the linker output starts with the desired state. The data in code case is extremely rare for AArch64 as jump tables are usually placed in .rodata.

Impressive results

Experiments with a Clang build using this alternative scheme have shown impressive results, eliminating over 50% of symbol table entries.

1
2
3
4

.o size   |   build |
261345384 |   a64-0 | standard
260443728 |   a64-1 | optimizing $d
254106784 |   a64-2 | optimizing both $x

1
2
3
4
5
6

% bloaty a64-2/bin/clang -- a64-0/bin/clang
    FILE SIZE        VM SIZE
 --------------  --------------
  -5.4% -1.13Mi  [ = ]       0    .strtab
 -50.9% -4.09Mi  [ = ]       0    .symtab
  -4.0% -5.22Mi  [ = ]       0    TOTAL

However, omitting a mapping symbol at offset 0 for sections with instructions is currently non-conformant. An ABI update has been requested to address this.

Some interoperability issues might arise, but a significant portion of users don't care.

particularly when linking text sections with trailing data assembled using the traditional behavior, or when a linker script combines non-text and text sections. These scenarios could potentially confuse disassemblers.

There are some interop issues that a significant portion of users don't care.

In a text section with trailing data assembled using the traditional behavior, the last mapping symbol will be $d. During the linking process, if the subsequent section lacks an initial $x due to the new behavior, the result could confuse disassemblers.

In addition, a linker script combining non-text sections and text sections might confuse disassemblers.

1
2
3
4

SECTIONS {
  ...
  mix : { *(.data.*) *(.text.foo) }
}

Note: it might be attempting to teach linkers to scan input sections and insert mapping symbols, but that is inelegant.

In conclusion, the proposed alternative scheme solves the symbol table bloat problem, but it requires careful consideration of compliance and interoperability. An opt-in assembler option might be useful. With this optimization in place, the remaining symbols would primarily originate from range extension thunks, prebuilt libraries, or highly specialized assembly implementations.

Mapping symbols for range extension thunks

When lld creates an AArch64 range extension thunk, it defines a $x symbol to signify the A64 state. This symbol is only relevant when the preceding section ends with the data state, a scenario that's only possible with the traditional assembler behavior.

Given the infrequency of range extension thunks, the $x symbol overhead is generally tolerable.

Peculiar alignment behavior in GNU assembler

In contrast to LLVM's integrated assembler, which restricts state transitions to instructions and data commands, GNU assembler introduces additional state transitions for alignments. These alignments can be either implicit (arising from alignment requirements) or explicit (specified through directives). This behavior has led to some interesting edge cases and bug fixes over time. (See related code beside [PATCH][GAS][AARCH64]Fix "align directive causes MAP_DATA symbol to be lost" https://sourceware.org/bugzilla/show_bug.cgi?id=20364)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

.section .foo1,"a"
// no $d
.word 0

.section .foo2,"a"
// $d
.balign 4
.word 0

.section .foo3,"a"
// $d
.word 0
// $a
nop

In the example, .foo1 only contains data directives and there is no $d. However, .foo2 includes an alignment directive, triggering the creation of a $d symbol. Interestingly, .foo3 starts with data but ends with an instruction, necessitating both a $d and an $a mapping symbol.

It's worth noting that DWARF sections, typically generated by the compiler, don't include explicit alignment directives. They behave similarly to the .foo1 example and lack an associated $d mapping symbol.

AArch32 ld --be8

The BE-8 mode (byte-invariant addressing big-endian mode) requires the linker to convert big-endian code to little-endian. This is implemented by scanning mapping symbols. See Linker notes on AArch32#--be8 for context.

RISC-V ISA extension

RISC-V mapping symbols are similar to AArch64, but with a notable extension:

1
2

$x<ISA>       | Start of a sequence of instructions with <ISA> extension.
$x<ISA>.<any>

The alternative scheme for optimizing symbol table size can be adapted to accommodate RISC-V's $x<ISA> symbols. The approach remains the same: add an ending $x<ISA> only if the final data in a text section doesn't belong to the desired ISA.

The alternative scheme can be adapted to work with $x<ISA>: Add an ending $x<ISA> if the final data isn't of the desired ISA.

This adaptation works seamlessly as long as all relocatable files provided to the linker share the same baseline ISA. However, in scenarios where the relocatable files are more heterogeneous, a crucial question arises: which state should be restored at section end? Would the subsequent section in the linker output be compiled with different ISA extensions?

Technically, we could teach linkers to insert $x symbols, but scanning each input text section isn't elegant.

Mach-O LC_DATA_IN_CODE load command

In contrast to ELF's symbol pair approach, Mach-O employs the LC_DATA_IN_CODE load command to store non-instruction ranges within code sections. This method is remarkably compact, with each entry requiring only 8 bytes. ELF, on the other hand, needs two symbols ($d and $x) per data region, consuming 48 bytes (in ELFCLASS64) in the symbol table.

1
2
3
4
5

struct data_in_code_entry {
  uint32_t offset;  
  uint16_t length;  
  uint16_t kind;    
};

In llvm-project, the possible kind values are defined in llvm/include/llvm/BinaryFormat/MachO.h. I recently refactored the generic MCAssembler to place this Mach-O specific thing, alongside others, to MachObjectWriter.

1
2
3
4
5
6
7
8

enum DataRegionType {
  
  DICE_KIND_DATA = 1u,
  DICE_KIND_JUMP_TABLE8 = 2u,
  DICE_KIND_JUMP_TABLE16 = 3u,
  DICE_KIND_JUMP_TABLE32 = 4u,
  DICE_KIND_ABS_JUMP_TABLE32 = 5u
};

Achieving Mach-O's efficiency in ELF

Given ELF's symbol table bloat due to the st_size member (my previous analysis), how can it attain Mach-O's level of efficiency? Instead of introducing a new format, we can leverage the standard ELF feature: SHF_COMPRESSED.

Both .symtab and .strtab lack the SHF_ALLOC flag, making them eligible for compression without requiring any changes to the ELF specification.

• LLVM discussion
• A feature request has already been submitted to binutils to explore this possibility.

The implementation within LLVM shouldn't be overly complex, and I'm more than willing to contribute if there's interest from the community.