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

[Alan Modra <amodra@gmail.com>]

On Fri, Apr 28, 2017 at 08:25:04AM +0200, Florian Weimer wrote:
> On 04/26/2017 06:06 AM, Cary Coutant wrote:
> >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.
> 
> It might also be possible to sort the relocated objects so that they are
> more contiguous.

That's true for GOT entry relocations, but difficult for anything not
linker generated.  However, the GOT doesn't tend to have too many
entries with relative relocs.  What's more, it is better to teach the
linker how to edit code using such entries from GOT indirect to GOT
pointer relative and thus eliminate the GOT entry entirely..

I'm in favour of a very simple compression scheme, perhaps just
using a new relocation to adjust an array of words by the base
address.  From looking at a few random binaries it seems that many
relative relocations apply to a run of consecutive words.  Of course,
using such a simple scheme spoils the fun of designing something
entirely new.  ;-)

> It could be beneficial to arrange things so that vector instructions can be
> used for the relocation.  I'm not sure if it is worthwhile to design a
> compression scheme based on bit fiddling for this because those who want
> compression can probably use a compressed file system anyway.
> 
> Thanks,
> Florian

-- 
Alan Modra
Australia Development Lab, IBM