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

["H.J. Lu" <hjl.tools@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, &current, 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.