Add a host tool to pack R_ARM_RELATIVE relocations in libchrome.<ver>.so.

tools/relocation_packer/README.TXT

Index: tools/relocation_packer/README.TXT
diff --git a/tools/relocation_packer/README.TXT b/tools/relocation_packer/README.TXT
new file mode 100644
index 0000000000000000000000000000000000000000..6ff1771eb6aff1c7e535f1ca2530cb03a1e21c8a
--- /dev/null
+++ b/tools/relocation_packer/README.TXT
@@ -0,0 +1,100 @@
+Introduction:
+-------------
+
+R_ARM_RELATIVE relocations are the bulk of dynamic relocations (the .rel.dyn
+section) in libchrome.<version>.so.  The ELF standard representation of them
+is wasteful.
+
+Packing uses run length encoding to store them more efficiently.  Packed
+relocations are placed in a new .android.rel.dyn section.  Packing reduces

[rmcilroy, 2014/06/02 15:16:35]

Would it be safer to put this in a section called .crazy.rel.dyn or something
(assuming they are going to be unpacked by the crazy linker), just in case
android decides to add their own section at some point with the name
.android.rel.dyn.

[simonb (inactive), 2014/06/04 16:40:35]

The idea (or at least the hope) is that this will become a part of the standard
android runtime linker, at which point it is no longer 'crazy'.

I don't think a collision with a future real android sections seems likely, but
if we want to rename this then a more descriptive nam could be
'.android.packed.rel.dyn' or similar.

[rmcilroy, 2014/06/07 11:49:06]

Should be fine as is.

[simonb (inactive), 2014/06/09 14:39:19]

Okay.

+the footprint of libchrome.<version>.so in the filesystem, in APK downloads,
+and in memory when loaded on the device.

[rmcilroy, 2014/06/02 15:16:35]

"in memory when loaded on the device" - is this true?  I thought it was unpacked
during loading so would take the same amount of RAM?

[simonb (inactive), 2014/06/04 16:40:35]

This should be true.  The current relocations are part of mapped memory.  Packed
relocations can be read (iterated) out of the .so, processed as each is
generated, and then discarded; no longer needed.  Because we've removed them
from the mapped image this means it gets smaller, and so takes less device ram.

+
+A packed libchrome.<version>.so is designed so that it can be loaded directly
+on Android, but requires the explicit support of a crazy linker that has been
+extended to understand packed relocations.

[rmcilroy, 2014/06/02 15:16:35]

nit - mention there is only Arm support currently

[simonb (inactive), 2014/06/04 16:40:35]

Done.

+
+A packed libchrome.<version>.so cannot currently be used with the standard
+Android runtime linker.
+
+See src/*.h for design and implementation notes.
+
+
+Notes:
+------
+
+Packing does not adjust debug data.  An unstripped libchrome.<version>.so
+can be packed and will run, but may no longer be useful for debugging.
+
+Requires the explicit support of an extended crazy linker.  Adds the

[rmcilroy, 2014/06/02 15:16:35]

nit - Unpacking requires the...

[simonb (inactive), 2014/06/04 16:40:35]

Done.

+following new .dynamic tags, used by the crazy linker to find the packed
+.android.rel.dyn section data:
+
+  DT_ANDROID_ARM_REL_OFFSET = DT_LOPROC    (Processor specific: 0x70000000)
+    - The offset of .android.rel.dyn data in libchrome.<version>.so
+  DT_ANDROID_ARM_REL_SIZE = DT_LOPROC + 1  (Processor Specific: 0x70000001)
+    - The size of .android.rel.dyn data in bytes
+
+The format of .android.rel.dyn data is:
+
+  "APR1" identifier
+  N: the number of count-delta pairs in the encoding
+  A: the initial offset
+  N * C,D: N count-delta pairs
+
+All numbers in the encoding stream are stored as LEB128 values.  For details
+see http://en.wikipedia.org/wiki/LEB128.
+
+The streaming unpacking algorithm is:
+
+  skip over "APR1"
+  pairs, addr = next leb128 value, next leb128 value
+  emit R_ARM_RELATIVE relocation with r_offset = addr
+  while pairs:
+    count, delta = next leb128 value, next leb128 value
+    while count:
+      addr += delta
+      emit R_ARM_RELATIVE relocation with r_offset = addr
+      count--
+    pairs--;
+
+
+Usage instructions:
+-------------------
+
+To pack relocations, add an empty .android.rel.dyn and then run the tool:
+
+    echo -n 'NULL' >/tmp/small
+    arm-linux-gnueabi-objcopy \
+        --add-section .android.rel.dyn=/tmp/small \
+        libchrome.<version>.so libchrome.<version>.so.packed
+    rm /tmp/small
+    pack-relocations libchrome.<version>.so.packed

[rmcilroy, 2014/06/02 15:16:35]

Could the tool do the adding and removing of sections itself, or is that too
much work?

[simonb (inactive), 2014/06/04 16:40:35]

It's icky work that it is better to avoid.  Adding the section means adding a
new string to name the section, which means increasing the size of .shstrtab
which means shuffling a lot of the contents of the file around (again).  Objcopy
can do this part for us, so it seems useful to let it.  Yes, it means that
usability of the tool is a touch more ragged than it might be, but since it
isn't intended to be run by people, only from gunk at the bottom of gyp/ninja
actions, I think it's okay to do it this way.

+
+To unpack and restore the shared library to its original state:
+
+    cp libchrome.<version>.so.packed unpackable
+    pack-relocations -u unpackable

[rmcilroy, 2014/06/02 15:16:35]

From the gyp file, looks like the executable is "relocation_packer" rather than
pack-relocations? 

[simonb (inactive), 2014/06/04 16:40:35]

Done.  (Resulted from a last-minute change to the gyp file.)

[rmcilroy, 2014/06/07 11:49:06]

relocation_packer (not relocations_packer) ;)

[simonb (inactive), 2014/06/09 14:39:19]

Done.

+    arm-linux-gnueabi-objcopy \
+        --remove-section=.android.rel.dyn unpackable libchrome.<version>.so
+    rm unpackable
+
+
+Bugs & TODOs:
+-------------
+
+Currently only supports arm32.  Support for arm64 requires some extension
+and modification.
+
+Expects to find at least two free slots in the .dynamic section.  Uses
+these to add data that tells the crazy linker where to find the packed
+.android.rel.dyn data.

[rmcilroy, 2014/06/02 15:16:35]

What if there are not two free slots?  Can we force there to be enough free
slots?

[simonb (inactive), 2014/06/04 16:40:35]

We can, but... growing the table means resizing its section, and that leads to a
catch-22 where the thing that resizes the section wants change the contents of
this section.  Put differently, the code that writes to these unused slots is
called from stuff already in the middle of resizing a different section.

In practice we can always arrange for the linker to reserve us some slots.  From
gold(1):

  --spare-dynamic-tags COUNT
      Dynamic tag slots to reserve (default 5)

http://permalink.gmane.org/gmane.comp.gnu.binutils/46762

I have updated the code to reference this linker flag.

+
+Requires libelf 0.158 or later.  Earlier libelf releases may be buggy in
+ways that prevent the packer from working correctly.
+
+
+Testing:
+--------
+
+Unittests run under gtest, on the host system.