[llvm-dev] Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section

[Florian Weimer via llvm-dev]

* Rahul Chaudhry via gnu-gabi:

> The encoding used is a simple combination of delta-encoding and a
> bitmap of offsets. The section consists of 64-bit entries: higher
> 8-bits contain delta since last offset, and lower 56-bits contain a
> bitmap for which words to apply the relocation to. This is best
> described by showing the code for decoding the section:
>
> typedef struct
> {
>   Elf64_Xword  r_data;  /* jump and bitmap for relative relocations */
> } Elf64_Relrz;
>
> #define ELF64_R_JUMP(val)    ((val) >> 56)
> #define ELF64_R_BITS(val)    ((val) & 0xffffffffffffff)
>
> #ifdef DO_RELRZ
>   {
>     ElfW(Addr) offset = 0;
>     for (; relative < end; ++relative)
>       {
>         ElfW(Addr) jump = ELFW(R_JUMP) (relative->r_data);
>         ElfW(Addr) bits = ELFW(R_BITS) (relative->r_data);
>         offset += jump * sizeof(ElfW(Addr));
>         if (jump == 0)
>           {
>             ++relative;
>             offset = relative->r_data;
>           }
>         ElfW(Addr) r_offset = offset;
>         for (; bits != 0; bits >>= 1)
>           {
>             if ((bits&1) != 0)
>               elf_machine_relrz_relative (l_addr, (void *) (l_addr + r_offset));
>             r_offset += sizeof(ElfW(Addr));
>           }
>       }
>   }
> #endif

That data-dependent “if ((bits&1) != 0)” branch looks a bit nasty.

Have you investigated whether some sort of RLE-style encoding would be
beneficial? If there are blocks of relative relocations, it might even
be possible to use vector instructions to process them (although more
than four relocations at a time are probably not achievable in a
power-efficient manner on current x86-64).