[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section
- To: Cary Coutant <ccoutant@gmail.com>
- Subject: Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section
- From: "H.J. Lu" <hjl.tools@gmail.com>
- Date: Wed, 26 Apr 2017 09:04:09 -0700
- Authentication-results: sourceware.org; auth=none
- Cc: Sriraman Tallam <tmsriram@google.com>, gnu-gabi@sourceware.org, binutils <binutils@sourceware.org>, Xinliang David Li <davidxl@google.com>, Sterling Augustine <saugustine@google.com>, Paul Pluzhnikov <ppluzhnikov@google.com>, Ian Lance Taylor <iant@google.com>, Rahul Chaudhry <rahulchaudhry@google.com>, Luis Lozano <llozano@google.com>, Rafael Espíndola <rafael.espindola@gmail.com>, Peter Collingbourne <pcc@google.com>, Rui Ueyama <ruiu@google.com>
- Delivered-to: listarch-gnu-gabi@sourceware.org
- Delivered-to: mailing list gnu-gabi@sourceware.org
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=I/kioJ4qQW/pTYsqjVLl1hoRuB0LeAP0pB3LNAYiViM=; b=T2HZD6e47i3Op6+CId4h6TxNcPYNOP8IHCEtNtA7++yd57LX2xKKeq+Q0EIG/dvg7m Aw/BwnEr/fay7P8VztZqLNoYcfqHZUuRURJlcj4QWSgTTDhYedcP6WU5YAdbbh1R0JdQ AmdcZ/XV43dOROQjUXQgsD3Sm92HCI5Dde0vNenU/ErET7XhiN4C2WaoL6vyVB8VVm6/ PaA1pa1H0GWIDGfDT8wK4uXjj9RdOcX04JzI6paYT+la48UOP91rnOYFBkuhZYgamGaQ eZhzDunECSmt1vHyCNrb5apYyc7bTA90F4v1hZEagEz3Dxmbiu3rhqohn+2pkLAGHplQ LRTQ==
- In-reply-to: <CAJimCsFzz1qy9qCcvaMRtgcRv9oNE7C-+3Ku9JcjBGOvqtWrVg@mail.gmail.com>
- List-help: <mailto:gnu-gabi-help@sourceware.org>
- List-id: <gnu-gabi.sourceware.org>
- List-post: <mailto:gnu-gabi@sourceware.org>
- List-subscribe: <mailto:gnu-gabi-subscribe@sourceware.org>
- Mailing-list: contact gnu-gabi-help@sourceware.org; run by ezmlm
- References: <CAAs8HmyKSjqo2GKD0TQy8R80sVcXB3mNORMpXZ_a6sDdmWQOdg@mail.gmail.com> <CAJimCsFzz1qy9qCcvaMRtgcRv9oNE7C-+3Ku9JcjBGOvqtWrVg@mail.gmail.com>
- Sender: gnu-gabi-owner@sourceware.org
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.