A compact section header table for ELF

ELF's design emphasizes natural size and alignment guidelines for its control structures. However, this approach has substantial size drawbacks.

In a release build of llvm-project (-O3 -ffunction-sections -fdata-sections, the section header tables occupy 13.4% of the .o file size.

I propose an alternative section header table format that is signaled by e_shentsize == 0 in the ELF header. e_shentsize == sizeof(Elf64_Shdr) (or the 32-bit counterpart) selects the traditional section header table format.

nshdr denotes the number of sections (including SHN_UNDEF). The compact section header table (located at e_shoff) begins with nshdr Elf_Word values. These values specify the offset of each section header relative to e_shoff.

Following these offsets, nshdr section headers are encoded. Each header begins with a presence byte indicating which subsequent Elf_Shdr members use explicit values vs. defaults:

  • sh_name, ULEB128 encoded
  • sh_type, ULEB128 encoded (if presence & 1), defaults to SHT_PROGBITS
  • sh_flags, ULEB128 encoded (if presence & 2), defaults to 0
  • sh_addr, ULEB128 encoded (if presence & 4), defaults to 0
  • sh_offset, ULEB128 encoded
  • sh_size, ULEB128 encoded (if presence & 8), defaults to 0
  • sh_link, ULEB128 encoded (if presence & 16), defaults to 0
  • sh_info, ULEB128 encoded (if presence & 32), defaults to 0
  • sh_addralign, ULEB128 encoded as log2 value (if presence & 64), defaults to 1
  • sh_entsize, ULEB128 encoded (if presence & 128), defaults to 0

In traditional ELF, sh_addralign can be 0 or a positive integral power of two, where 0 and 1 mean the section has no alignment constraints. While the compact encoding cannot encode sh_addralign value of 0, there is no loss of generality.

Example C++ code that decodes a section header: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// readULEB128(const uint8_t *&p);

const uint8_t *sht = base + ehdr->e_shoff;
const uint8_t *p = sht + ((Elf_Word*)sht)[i];
uint8_t presence = *p++;
Elf_Shdr shdr = {};
shdr.sh_name = readULEB128(p);
shdr.sh_type = presence & 1 ? readULEB128(p) : ELF::SHT_PROGBITS;
shdr.sh_flags = presence & 2 ? readULEB128(p) : 0;
shdr.sh_addr = presence & 4 ? readULEB128(p) : 0;
shdr.sh_offset = readULEB128(p);
shdr.sh_size = presence & 8 ? readULEB128(p) : 0;
shdr.sh_link = presence & 16 ? readULEB128(p) : 0;
shdr.sh_info = presence & 32 ? readULEB128(p) : 0;
shdr.sh_addralign = presence & 64 ? 1UL << readULEB128(p) : 1;
shdr.sh_entsize = presence & 128 ? readULEB128(p) : 0;

You can still enjoy the advantage of O(1) random access of section headers through the offsets at the beginning of the section header table.

In a release build of llvm-project (-O3 -ffunction-sections -fdata-sections -Wa,--crel, the traditional section header tables occupy 16.4% of the .o file size while the compact section header table drastically reduces the ratio to 4.7%.

Experiments

I have developed a Clang/lld prototype that implements compact section header table and CREL.

.o size sht size build
136012504 18284992 -O3
111583312 18284992 -O3 -Wa,--crel
97976973 4604341 -O3 -Wa,--crel,--cshdr
2174179112 260281280 -g
1763231672 260281280 -g -Wa,--crel
1577187551 74234983 -g -Wa,--crel,--cshdr

More ideas

Like other sections, symbol table and string table sections (SHT_SYMTAB and SHT_STRTAB) can be compressed through SHF_COMPRESSED. However, compressing the dynamic symbol table (.dynsym) and its associated string table (.dynstr) is not recommended.

Symbol table sections have a non-zero sh_entsize, which remains unchanged after compression.

The string table, which stores symbol names (also section names in LLVM output), is typically much larger than the symbol table itself. To reduce its size, we can utilize a text compression algorithm. While compressing the string table, compressing the symbol table along with it might make sense, but using a compact encoding for the symbol table itself won't provide significant benefits.