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

> We've taken the '.relr.dyn' section from Cary's prototype,
and implemented a
> custom encoding to compactly represent the list of offsets. We're
calling the
> new compressed section '.relrz.dyn' (for
relocations-relative-compressed).
I'd suggest just using .relr.dyn -- your encoding is straightforward
enough that I'd just make that the standard representation for this
section type.
> 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:
>
> ...
>
> The above code is the entirety of the implementation for decoding and
> processing '.relrz.dyn' sections in glibc dynamic loader.
>
> This encoding can represent up to 56 relocation offsets in a single 64-bit
> word. For many of the binaries we tested, this encoding provides >40x
> compression for storing offsets over the original `.relr.dyn` section.
>
> For 32-bit targets, we use 32-bit entries: 8-bits for 'jump' and
24-bits for
> the bitmap.
Very nice! Simple and effective.
> Here are three real world examples that demonstrate the savings:
Impressive numbers. I've gotta admit, the savings are better than I
expected.
> However, before that can happen, we need agreement on the ABI side for the
new
> section type and the encoding. We haven't worked on a change of this
magnitude
> before that touches so many different pieces from the linker, elf tools,
and
> the dynamic loader. Specifically, we need agreement and/or guidance on
where
> and how should the new section type and its encoding be documented.
We're
> proposing adding new defines for SHT_RELRZ, DT_RELRZ, DT_RELRZSZ,
DT_RELRZENT,
> and DT_RELRZCOUNT that all the different parts of the toolchains can agree
on.
Yes, as Ian mentioned, the generic ABI discussion is at
generic-abi at googlegroups.com. Most people who would be interested are
already on the gnu-gabi at sourceware.org list, but there are a few who
are not, and who may not yet have seen this discussion. I'll support
the proposal.

Thanks for taking this idea the extra mile!

-cary

Thanks for your encouraging words, Ian and Cary.

We're drafting a more detailed proposal and would post it on the generic-abi
list this week. I'll also post a link here for cross-reference.

Based on Cary's suggestion here, we're renaming '.relrz.dyn' to
'.relr.dyn' in the
proposal.

Rahul


On Fri, Dec 8, 2017 at 10:36 PM, Cary Coutant <ccoutant at gmail.com>
wrote:
>> We've taken the '.relr.dyn' section from Cary's
prototype, and implemented a
>> custom encoding to compactly represent the list of offsets. We're
calling the
>> new compressed section '.relrz.dyn' (for
relocations-relative-compressed).
>
> I'd suggest just using .relr.dyn -- your encoding is straightforward
> enough that I'd just make that the standard representation for this
> section type.
>
>> 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:
>>
>> ...
>>
>> The above code is the entirety of the implementation for decoding and
>> processing '.relrz.dyn' sections in glibc dynamic loader.
>>
>> This encoding can represent up to 56 relocation offsets in a single
64-bit
>> word. For many of the binaries we tested, this encoding provides
>40x
>> compression for storing offsets over the original `.relr.dyn` section.
>>
>> For 32-bit targets, we use 32-bit entries: 8-bits for 'jump'
and 24-bits for
>> the bitmap.
>
> Very nice! Simple and effective.
>
>> Here are three real world examples that demonstrate the savings:
>
> Impressive numbers. I've gotta admit, the savings are better than I
expected.
>
>> However, before that can happen, we need agreement on the ABI side for
the new
>> section type and the encoding. We haven't worked on a change of
this magnitude
>> before that touches so many different pieces from the linker, elf
tools, and
>> the dynamic loader. Specifically, we need agreement and/or guidance on
where
>> and how should the new section type and its encoding be documented.
We're
>> proposing adding new defines for SHT_RELRZ, DT_RELRZ, DT_RELRZSZ,
DT_RELRZENT,
>> and DT_RELRZCOUNT that all the different parts of the toolchains can
agree on.
>
> Yes, as Ian mentioned, the generic ABI discussion is at
> generic-abi at googlegroups.com. Most people who would be interested are
> already on the gnu-gabi at sourceware.org list, but there are a few who
> are not, and who may not yet have seen this discussion. I'll support
> the proposal.
>
> Thanks for taking this idea the extra mile!
>
> -cary

We sent a proposal to generic-abi last week.
Here's the link for cross-reference, as promised:
https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg

Rahul


On Mon, Dec 11, 2017 at 4:05 PM, Rahul Chaudhry
<rahulchaudhry at google.com> wrote:
> Thanks for your encouraging words, Ian and Cary.
>
> We're drafting a more detailed proposal and would post it on the
generic-abi
> list this week. I'll also post a link here for cross-reference.
>
> Based on Cary's suggestion here, we're renaming
'.relrz.dyn' to
> '.relr.dyn' in the
> proposal.
>
> Rahul
>
>
> On Fri, Dec 8, 2017 at 10:36 PM, Cary Coutant <ccoutant at gmail.com>
wrote:
>>> We've taken the '.relr.dyn' section from Cary's
prototype, and implemented a
>>> custom encoding to compactly represent the list of offsets.
We're calling the
>>> new compressed section '.relrz.dyn' (for
relocations-relative-compressed).
>>
>> I'd suggest just using .relr.dyn -- your encoding is
straightforward
>> enough that I'd just make that the standard representation for this
>> section type.
>>
>>> 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:
>>>
>>> ...
>>>
>>> The above code is the entirety of the implementation for decoding
and
>>> processing '.relrz.dyn' sections in glibc dynamic loader.
>>>
>>> This encoding can represent up to 56 relocation offsets in a single
64-bit
>>> word. For many of the binaries we tested, this encoding provides
>40x
>>> compression for storing offsets over the original `.relr.dyn`
section.
>>>
>>> For 32-bit targets, we use 32-bit entries: 8-bits for
'jump' and 24-bits for
>>> the bitmap.
>>
>> Very nice! Simple and effective.
>>
>>> Here are three real world examples that demonstrate the savings:
>>
>> Impressive numbers. I've gotta admit, the savings are better than I
expected.
>>
>>> However, before that can happen, we need agreement on the ABI side
for the new
>>> section type and the encoding. We haven't worked on a change of
this magnitude
>>> before that touches so many different pieces from the linker, elf
tools, and
>>> the dynamic loader. Specifically, we need agreement and/or guidance
on where
>>> and how should the new section type and its encoding be documented.
We're
>>> proposing adding new defines for SHT_RELRZ, DT_RELRZ, DT_RELRZSZ,
DT_RELRZENT,
>>> and DT_RELRZCOUNT that all the different parts of the toolchains
can agree on.
>>
>> Yes, as Ian mentioned, the generic ABI discussion is at
>> generic-abi at googlegroups.com. Most people who would be interested
are
>> already on the gnu-gabi at sourceware.org list, but there are a few who
>> are not, and who may not yet have seen this discussion. I'll
support
>> the proposal.
>>
>> Thanks for taking this idea the extra mile!
>>
>> -cary