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

[Cary Coutant <ccoutant@gmail.com>]

> 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!)

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.

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*.

-cary