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: "Sriraman Tallam via binutils" <binutils at sourceware dot org>
- To: Florian Weimer <fw at deneb dot enyo dot de>
- Cc: Rahul Chaudhry via gnu-gabi <gnu-gabi at sourceware dot org>, Rahul Chaudhry <rahulchaudhry 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>, Cary Coutant <ccoutant at gmail dot com>, 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: Mon, 11 Dec 2017 10:41:08 -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> <874lozec25.fsf@mid.deneb.enyo.de>
- Reply-to: Sriraman Tallam <tmsriram at google dot com>
On Sat, Dec 9, 2017 at 3:06 PM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * 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).
Yes, we originally investigated RLE style encoding but I guess the key
insight which led us towards the proposed encoding is the following.
The offset addresses which contain the relocations are close but not
necessarily contiguous. We experimented with an encoding strategy
where we would store the initial offset and the number of words after
that which contained dynamic relocations. This gave us good
compression numbers but the proposed scheme was way better. I will
let Rahul say more as he did quite a bit of experiments with different
strategies.
Thanks
Sri