Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section

[Sriraman Tallam <tmsriram@google.com>]

On Tue, Apr 25, 2017 at 9:06 PM, Cary Coutant <ccoutant@gmail.com> wrote:
>> Idea A: Shrinking the size of the dynamic relocations
>
> In a RELATIVE relocation, the r_offset field is really the only field
> of interest. The symbol and addend are not used -- the dynamic loader
> simply adjusts the address at the given offset by the relocation
> factor for the load module. Thus, it truly is possible to reduce these
> relocations to just the one word.
>
> Simon Baldwin did a lot of work on this a few years ago for Chromium,
> writing a post-link utility to extract all the RELATIVE relocations
> and rewrite them to a new section.
>
> When Simon was working on his utility, I decided it wouldn't be too
> difficult to implement it directly in gold, and I toyed around with
> it, but never devoted the time to take all the steps it would take to
> bring this about. (Frankly, I was underwhelmed by the quoted savings,
> but it sounds like I may have underestimated the value of that
> savings. Sorry!)

Ok, here is how I understand the impact of these savings :
* In terms of text size, the size savings on most binaries is equal to
what ICF can offer and is on top of ICF.
* Some of our binaries are forced to disable PIE because they are
stored in space constrained partitions and this will make it possible
to enable PIE again for them.
* Chrome/ChromeOS binaries enable full ICF (not safe) and are willing
to take the debugging nuisance that comes along with it for the
savings, so I am assuming this would interest them.

>
> Anyway, I cleaned up what I had done a bit, and pushed it to a
> personal binutils branch, users/ccoutant/experimental-relr, for your
> consideration. Here's what I did:
>
> 1. Added a new section .relr.dyn, with a new type SHT_RELR, and
> sh_entsize = address size. The contents of this section are (for now)
> a simple list of addresses that require relative relocations.
>
> 2. Added new dynamic table entries, DT_RELR, DT_RELRSZ, and
> DT_RELRENT, which point to the new section.
>
> 3. Added a linker option, --experimental-use-relr, to enable the feature.
>
> 4. Modified the x86-64 target to emit new-style RELR relocations. I
> punted for 64-bit relocations on x32, and for IFUNC relocations --
> those will still be emitted as old-style relative relocations in
> .rela.dyn.
>
> For my experimentation, I picked the next-available values in the
> gABI-reserved range, rather than vendor-specific values, for no good
> reason. They're easy to renumber if we need to experiment with this in
> the wild before standardizing.

Thanks!, you have shown me a clear path forward.

>
> Still to do:
>
> 1. Modify the other targets in gold to support RELR relocations.
>
> 2. Add readelf/objdump support. (You can still use readelf as is --
> it'll just show the section type and dynamic table entries as numbers.
> And you can dump the new section with "readelf -x.relr.dyn".)
>
> 3. Add dynamic loader support.
>
> 4. Evaluate some alternate representations to improve upon the simple
> list of addresses. An idea I've been considering is emitting a bitmap
> -- an alternating series of pairs (starting address, bits), where
> "bits" is just a fixed-size bit vector describing each word starting
> at the given starting address. The "bits" field could be, say, 128 or
> 256 bits in length, or could begin with a byte that defines its
> length. I think this would work well, as the relocations are often
> clustered, but haven't yet done any testing of that hypothesis. A
> simple run-length encoding, as previously suggested, would also work,
> of course. I'm not in favor of using a general-purpose compression
> algorithm on the relocations.
>
> 5. Make a proposal to the gABI to add SHT_RELR and DT_RELR*.

Ok, I guess Step 4 can be done in a later iteration.


Thanks all for the inputs.
Sri

>
> -cary