This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section
- From: "Rahul Chaudhry via binutils" <binutils at sourceware dot org>
- To: Cary Coutant <ccoutant at gmail dot com>
- Cc: Sriraman Tallam <tmsriram at google dot com>, Suprateeka R Hegde <hegdesmailbox at gmail dot com>, Florian Weimer <fweimer at redhat dot com>, David Edelsohn <dje dot gcc at gmail dot com>, Rafael Avila de Espindola <rafael dot espindola at gmail dot com>, Binutils Development <binutils at sourceware dot org>, Alan Modra <amodra at gmail dot com>, Rahul Chaudhry via gnu-gabi <gnu-gabi at sourceware dot org>, Xinliang David Li <davidxl at google dot com>, Sterling Augustine <saugustine at google dot com>, Paul Pluzhnikov <ppluzhnikov at google dot com>, Ian Lance Taylor <iant at google dot com>, "H.J. Lu" <hjl dot tools at gmail dot com>, Luis Lozano <llozano at google dot com>, Peter Collingbourne <pcc at google dot com>, Rui Ueyama <ruiu at google dot com>, llvm-dev at lists dot llvm dot org
- Date: Tue, 19 Dec 2017 11:40:56 -0800
- Subject: Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section
- Authentication-results: sourceware.org; auth=none
- References: <CAGWvnynFwXFGLj3tAVgDatn0zmuHcWHyRNuDvR+wRZCXLnar_A@mail.gmail.com> <8737cosnym.fsf@localhost.localdomain.i-did-not-set--mail-host-address--so-tickle-me> <CAGWvnynEe3QkhDMGc=Tx8Vr44egtv3xLuh1yiVcAhv+e3GLtZg@mail.gmail.com> <a3e5c76c-8cb9-fc53-a30a-96b2c85079e1@gmail.com> <a68a5d29-09d6-e758-8680-d94f42762adf@redhat.com> <7e698a5f-32d7-6549-7e23-8850b85e6c10@gmail.com> <CAAs8Hmziqc0hebPndiGuZN=buFm=M+O+2fGCfsv_rvDro9zJZA@mail.gmail.com> <CAJRD=ooGubyUOLE6W7LHdeU2ZNDEG1A=84+P=1iOvfmD7-7GNg@mail.gmail.com> <CAJimCsF-JS8CJxamaVWbXmqCxE6PH0gPRufNSCNoghFWT-_=LQ@mail.gmail.com> <CAJRD=or-vgE4B-E2jF8ztTJfu+ise6T2iBanRfbZKNivOoNJUg@mail.gmail.com>
- Reply-to: Rahul Chaudhry <rahulchaudhry at google dot com>
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@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@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@googlegroups.com. Most people who would be interested are
>> already on the gnu-gabi@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