ELF's design emphasizes naturalsize and alignment guidelines for its control structures. Whileensured efficient processing in the old days, this can lead to largerfile sizes. I propose "Light ELF" (EV_LIGHT, version 2) – awhimsical exploration inspired by Light Elves of Tolkien's legendarium(who had seen the light of the Two Trees in Valinor).

In a light ELF file, the e_version member of the ELFheader is set to 2. EV_CURRENT remains 1 for backwardcompatibility.

1
2
3

#define EV_NONE 0
#define EV_CURRENT 1
#define EV_LIGHT 2

When linking a program, traditional ELF (version 1) and light ELF(version 2) files can be mixed together.

Relocations

Light ELF utilizes CREL forrelocations. RELand RELA from traditional ELF are unused.

Existing lazy binding schemes rely on random access to relocationentries within the DT_JMPREL table. Due to CREL'ssequential nature, keeping lazy binding requires a memory allocationthat holds decoded JUMP_SLOT relocations.

Section header table

Traditional ELF (version 1) sectionheader tables can be large. Light ELF addresses this through acompact section header table format signaled bye_shentsize == 0 in the ELF header.

Acompact section header table for ELF contains the detail. Itscurrent version is copied below for your convenience.

nshdr denotes the number of sections (includingSHN_UNDEF). The section header table (located ate_shoff) begins with nshdrElf_Word values. These values specify the offset of eachsection header relative to e_shoff.

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

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

In traditional ELF, sh_addralign can be 0 or a positiveintegral power of two, where 0 and 1 mean the section has no alignmentconstraints. While the compact encoding cannot encodesh_addralign value of 0, there is no loss ofgenerality.

Example C++ code that decodes a specific 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;

While the current format allows for O(1) in-place random access ofsection headers using offsets at the beginning of the table, this accesspattern seems uncommon in practice. At least, I haven't encountered (orremembered) any instances within the llvm-project codebase. Therefore,I'm considering removing this functionality.

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

Symbol table

Like other sections, symboltable and string table sections (SHT_SYMTAB andSHT_STRTAB) can be compressed throughSHF_COMPRESSED. However, compressing the dynamic symboltable (.dynsym) and its associated string table(.dynstr) is not recommended.

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

The string table, which stores symbol names (also section names inLLVM output), is typically much larger than the symbol table itself. Toreduce its size, we can utilize a text compression algorithm. Whilecompressing the string table, compressing the symbol table along with itmight make sense, but using a compact encoding for the symbol tableitself won't provide significant benefits.

Program headers

Program headers, while individually large (eachElf64_Phdr is 56 bytes) and no random access is needed,typically have a limited quantity within an executable or shared object.Consequently, their overall size contribution is relatively small. LightELF maintains the existing format.

Section compression

Compressed sections face a challenge due to header overheadespecially for ELFCLASS64.

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

typedef struct {
Elf32_Wordch_type;
Elf32_Wordch_size;
Elf32_Wordch_addralign;
} Elf32_Chdr;

typedef struct {
Elf64_Wordch_type;
Elf64_Wordch_reserved;
Elf64_Xwordch_size;
Elf64_Xwordch_addralign;
} Elf64_Chdr;

The overhead and alignmentpadding limit the effectiveness when used with features like-ffunction-sections and -fdata-sections thatgenerate many smaller sections. For example, I have found that the largeElf64_Chdr makes evaluating compressed .rela.*sections difficult. Light ELF addresses this challenge by introducing anheader format of smaller footprint:

• ch_type, ULEB128 encoded
• ch_size, ULEB128 encoded
• ch_addralign, ULEB128 encoded as log2 value

This approach allows Light ELF to represent the header information injust 3 bytes for smaller sections, compared to the 24 bytes required bythe traditional format. T The content is no longer guaranteed to beword-aligned, a property that most compression libraries don't requireanyway.

Furthermore, compressedsections with the SHF_ALLOC flag are allowed. Usingthem outside of relocatable files needs caution, though.

Experiments

I have developed a Clang/lld prototype that implements compactsection header table and CREL (https://github.com/MaskRay/llvm-project/tree/april-2024).

Light ELF: a thoughtexperiment

By now, you might have realized that post is about a joke. Whilebumping e_version and modifying Elf_Chdr mightnot be feasible, it's interesting to consider the possibilities ofcompact section headers and compressed symbol/string tables. Perhapsthis can spark some interesting discussions!