Native Relocations

Information here is mostly Android & Linux-specific and may not be 100% accurate.

What are they?

  • For ELF files, they are sections of type REL, RELA, or RELR. They generally have the name “.rel.dyn” and “.rel.plt”.
  • They tell the runtime linker a list of addresses to post-process after loading the executable into memory.
  • There are several types of relocations, but >99% of them are “relative” relocations and are created any time a global variable or constant is initialized with the address of something.
    • This includes vtables, function pointers, and string literals, but not char[].
  • Each relocation is stored as either 2 or 3 words, based on the architecture.
    • On Android, they are compressed, which trades off runtime performance for smaller file size.
  • As of Oct 2019, Chrome on Android has about 390000 of them.
    • Windows and Mac have them as well, but I don't know how they differ.

Why do they matter?

  • Binary Size: Except on Android, relocations are stored very inefficiently.
    • Chrome on Linux has a .rela.dyn section of more than 14MiB!
    • Android uses a custom compression scheme to shrink them down to ~300kb.
    • There is an even better RELR encoding available on Android P+, but not widely available on Linux yet. It makes relocations ~60kb.
  • Memory Overhead: Symbols with relocations cannot be loaded read-only and result in “dirty” memory. 99% of these symbols live in .data.rel.ro, which as of Oct 2019 is ~6.5MiB on Linux and ~2MiB on Android. .data.rel.ro is data that would have been put into .rodata and mapped read-only if not for the required relocations. It does not get written to after it's relocated, so the linker makes it read-only once relocations are applied (but by that point the damage is done and we have the dirty pages).
    • On Linux, we share this overhead between processes via the zygote.
    • On Android, we share this overhead between processes by loading the shared library at the same address in all processes, and then mremap onto shared memory to dedupe after-the-fact.
  • Start-up Time The runtime linker applies relocations when loading the executable. On low-end Android, it can take ~100ms (measured on a first-gen Android Go devices with APS2 relocations). On Linux, it's closer to 20ms.

How do I see them?

third_party/llvm-build/Release+Asserts/bin/llvm-readelf --relocs out/Release/libmonochrome.so

Can I avoid them?

It's not practical to avoid them altogether, but there are times when you can be smart about them.

For Example:

// Wastes 2 bytes for each smaller string but creates no relocations.
// Total size overhead: 4 * 5 = 20 bytes.
const char kArr[][5] = {"as", "ab", "asdf", "fi"};

// String data stored optimally, but uses 4 relocatable pointers.
// Total size overhead:
//   64-bit: 8 bytes per pointer + 24 bytes per relocation + 14 bytes of char = 142 bytes
//   32-bit: 4 bytes per pointer + 8 bytes per relocation + 14 bytes of char = 62 bytes
const char *kArr2[] = {"as", "ab", "asdf", "fi"};

Note:

  • String literals are de-duped with others in the binary, so it's possible that the second example above might use 14 fewer bytes.
  • Not all string literals require relocations. Only those that are stored into global variables require them.

Another thing to look out for:

  • Large data structures with relocations that you don't need random access to, or which are seldom needed.
    • For such cases, it might be better to store the data encoded and then decode when required.