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: "H.J. Lu" <hjl dot tools at gmail dot com>
- To: Cary Coutant <ccoutant at gmail dot com>
- Cc: Sriraman Tallam <tmsriram at google dot com>, gnu-gabi at sourceware dot org, binutils <binutils 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>, Rahul Chaudhry <rahulchaudhry at google dot com>, Luis Lozano <llozano at google dot com>, Rafael Espíndola <rafael dot espindola at gmail dot com>, Peter Collingbourne <pcc at google dot com>, Rui Ueyama <ruiu at google dot com>
- Date: Wed, 26 Apr 2017 09:04:09 -0700
- 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: <CAAs8HmyKSjqo2GKD0TQy8R80sVcXB3mNORMpXZ_a6sDdmWQOdg@mail.gmail.com> <CAJimCsFzz1qy9qCcvaMRtgcRv9oNE7C-+3Ku9JcjBGOvqtWrVg@mail.gmail.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
>
> 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.
>
On x86, the last 2/3 bits are always zero. We can use it to encode the
next value. Offsets are represented by
1. A base offset and followed by consecutive deltas.
2. Encode the size of next delta in the unused bits.
static size_t
encode_offsets (uintptr_t *original, char *encoded, size_t n)
{
size_t i;
int current_bytes, next_bytes;
size_t encoded_size;
uintptr_t offset, next, current;
offset = original[0];
if ((offset & (sizeof (uintptr_t) - 1)) != 0)
abort ();
next = original[1] - offset;
if (next == 0)
abort ();
next_bytes = sizeof (uintptr_t) - __builtin_clzl (next) / 8;
if (next_bytes > sizeof (uintptr_t))
abort ();
/* Encode number of bytes of the next delta in the unused bits. */
offset |= next_bytes - 1;
memcpy (encoded, &offset, sizeof (uintptr_t));
encoded_size = sizeof (uintptr_t);
encoded += encoded_size;
for (i = 1; i < n; i++)
{
current = next;
current_bytes = next_bytes;
if ((i + 1) < n)
{
offset = original[i];
if ((offset & (sizeof (uintptr_t) - 1)) != 0)
abort ();
next = original[i + 1] - offset;
if (next == 0)
abort ();
next_bytes = sizeof (uintptr_t) - __builtin_clzl (next) / 8;
if (next_bytes > sizeof (uintptr_t))
abort ();
/* Encode number of bytes of the next delta in the unused bits. */
current |= next_bytes - 1;
}
/* FIXME: Only works for little endian. */
memcpy (encoded, ¤t, current_bytes);
encoded_size += current_bytes;
encoded += current_bytes;
}
return encoded_size;
}
On x86-64, I got
Total : 1471 offsets
Before: 11768 bytes
After : 1479 bytes
--
H.J.