Add a host tool to pack R_ARM_RELATIVE relocations in libchrome.<ver>.so.
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
the footprint of libchrome.<version>.so in the filesystem, in APK downloads,
and in memory when loaded on the device.
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.
A packed libchrome.<version>.so cannot currently be used with the standard
Android runtime linker.
See README.TXT and src/*.h for design and implementation notes.
BUG=
Review URL: https://codereview.chromium.org/310483003
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@276043 0039d316-1c4b-4281-b951-d872f2087c98
diff --git a/tools/relocation_packer/LICENSE b/tools/relocation_packer/LICENSE
new file mode 100644
index 0000000..972bb2e
--- /dev/null
+++ b/tools/relocation_packer/LICENSE
@@ -0,0 +1,27 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/tools/relocation_packer/README.TXT b/tools/relocation_packer/README.TXT
new file mode 100644
index 0000000..a81170a
--- /dev/null
+++ b/tools/relocation_packer/README.TXT
@@ -0,0 +1,102 @@
+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
+the footprint of libchrome.<version>.so in the filesystem, in APK downloads,
+and in memory when loaded on the device.
+
+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. Packed relocations are currently
+only supported on ARM.
+
+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.
+
+Unpacking on the device requires the explicit support of an extended crazy
+linker. Adds the 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
+ relocation_packer libchrome.<version>.so.packed
+
+To unpack and restore the shared library to its original state:
+
+ cp libchrome.<version>.so.packed unpackable
+ relocation_packer -u unpackable
+ 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.
+
+Requires 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. Fails
+if insufficient free slots exist (use gold --spare-dynamic-slots to increase
+the allocation).
+
+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.
diff --git a/tools/relocation_packer/relocation_packer.gyp b/tools/relocation_packer/relocation_packer.gyp
new file mode 100644
index 0000000..f74a9e9b
--- /dev/null
+++ b/tools/relocation_packer/relocation_packer.gyp
@@ -0,0 +1,66 @@
+# Copyright 2014 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+{
+ 'targets': [
+ {
+ 'target_name': 'lib_relocation_packer',
+ 'toolsets': ['host'],
+ 'type': 'static_library',
+ 'dependencies': [
+ '../../third_party/elfutils/elfutils.gyp:libelf',
+ ],
+ 'sources': [
+ 'src/debug.cc',
+ 'src/elf_file.cc',
+ 'src/leb128.cc',
+ 'src/packer.cc',
+ 'src/run_length_encoder.cc',
+ ],
+ },
+ {
+ 'target_name': 'relocation_packer',
+ 'toolsets': ['host'],
+ 'type': 'executable',
+ 'dependencies': [
+ '../../third_party/elfutils/elfutils.gyp:libelf',
+ 'lib_relocation_packer',
+ ],
+ 'sources': [
+ 'src/main.cc',
+ ],
+ },
+ {
+ 'target_name': 'relocation_packer_unittests',
+ 'toolsets': ['host'],
+ 'type': 'executable',
+ 'cflags': [
+ '-DINTERMEDIATE_DIR="<(INTERMEDIATE_DIR)"',
+ ],
+ 'dependencies': [
+ '../../testing/gtest.gyp:gtest',
+ 'lib_relocation_packer',
+ ],
+ 'include_dirs': [
+ '../..',
+ ],
+ 'sources': [
+ 'src/elf_file_unittest.cc',
+ 'src/leb128_unittest.cc',
+ 'src/packer_unittest.cc',
+ 'src/run_length_encoder_unittest.cc',
+ 'src/run_all_unittests.cc',
+ ],
+ 'copies': [
+ {
+ 'destination': '<(INTERMEDIATE_DIR)',
+ 'files': [
+ 'test_data/elf_file_unittest_relocs.so',
+ 'test_data/elf_file_unittest_relocs_packed.so',
+ ],
+ },
+ ],
+ },
+ ],
+}
diff --git a/tools/relocation_packer/src/debug.cc b/tools/relocation_packer/src/debug.cc
new file mode 100644
index 0000000..b78e250
--- /dev/null
+++ b/tools/relocation_packer/src/debug.cc
@@ -0,0 +1,44 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <stdarg.h>
+#include <stdio.h>
+
+#include "debug.h"
+
+namespace relocation_packer {
+
+Logger* Logger::instance_ = NULL;
+
+Logger* Logger::GetInstance() {
+ if (instance_ == NULL)
+ instance_ = new Logger;
+ return instance_;
+}
+
+void Logger::Log(const char* format, va_list args) {
+ vfprintf(stdout, format, args);
+}
+
+void Logger::Log(const char* format, ...) {
+ va_list args;
+ va_start(args, format);
+ GetInstance()->Log(format, args);
+ va_end(args);
+}
+
+void Logger::VLog(const char* format, ...) {
+ if (GetInstance()->is_verbose_) {
+ va_list args;
+ va_start(args, format);
+ GetInstance()->Log(format, args);
+ va_end(args);
+ }
+}
+
+void Logger::SetVerbose(bool flag) {
+ GetInstance()->is_verbose_ = flag;
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/debug.h b/tools/relocation_packer/src/debug.h
new file mode 100644
index 0000000..47ee96ae
--- /dev/null
+++ b/tools/relocation_packer/src/debug.h
@@ -0,0 +1,88 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Logging and checks.
+//
+// Log messages to stdout. LOG() prints normal user messages, VLOG()
+// is verbose, for tracing and debugging. SetVerbose() enables/disables
+// VLOG() output.
+//
+// LOG() and VLOG() are printf-like, and arguments are checked by gcc.
+// LOG_IF() and VLOG_IF() call LOG/VLOG if their predicate is true.
+// CHECK() aborts if its predicate is false. NOTREACHED() always aborts.
+// Logging is not thread-safe.
+//
+
+#ifndef TOOLS_RELOCATION_PACKER_SRC_DEBUG_H_
+#define TOOLS_RELOCATION_PACKER_SRC_DEBUG_H_
+
+#ifdef NDEBUG
+#undef NDEBUG
+#include <assert.h>
+#define NDEBUG
+#else
+#include <assert.h>
+#endif
+
+#include <stdarg.h>
+#include <string.h>
+
+namespace relocation_packer {
+
+// If gcc, define PRINTF_ATTRIBUTE so that gcc checks Log() as printf-like.
+#if defined(__GNUC__) && (__GNUC__ >= 3)
+#define PRINTF_ATTRIBUTE(string_index, first_to_check) \
+ __attribute__((__format__(__printf__, string_index, first_to_check)))
+#else
+#define PRINTF_ATTRIBUTE(string_index, first_to_check)
+#endif
+
+// Logging and checking macros.
+#define LOG(...) ::relocation_packer::Logger::Log(__VA_ARGS__)
+#define VLOG(...) ::relocation_packer::Logger::VLog(__VA_ARGS__)
+#define LOG_IF(cond, ...) \
+ do { \
+ if ((cond)) \
+ LOG(__VA_ARGS__); \
+ } while (0)
+#define VLOG_IF(cond, ...) \
+ do { \
+ if ((cond)) \
+ VLOG(__VA_ARGS__); \
+ } while (0)
+
+#define CHECK(expr) assert((expr))
+#define NOTREACHED(_) assert(false)
+
+class Logger {
+ public:
+ // Log and verbose log to stdout.
+ // |format| is a printf format string.
+ static void Log(const char* format, ...) PRINTF_ATTRIBUTE(1, 2);
+ static void VLog(const char* format, ...) PRINTF_ATTRIBUTE(1, 2);
+
+ // Set verbose mode.
+ // |flag| is true to enable verbose logging, false to disable it.
+ static void SetVerbose(bool flag);
+
+ private:
+ Logger() : is_verbose_(false) { }
+ ~Logger() {}
+
+ // Implementation of log to stdout.
+ // |format| is a printf format string.
+ // |args| is a varargs list of printf arguments.
+ void Log(const char* format, va_list args);
+
+ // If set, VLOG is enabled, otherwise it is a no-op.
+ bool is_verbose_;
+
+ // Singleton support. Not thread-safe.
+ static Logger* GetInstance();
+ static Logger* instance_;
+};
+
+} // namespace relocation_packer
+
+#endif // TOOLS_RELOCATION_PACKER_SRC_DEBUG_H_
diff --git a/tools/relocation_packer/src/elf_file.cc b/tools/relocation_packer/src/elf_file.cc
new file mode 100644
index 0000000..103dff7
--- /dev/null
+++ b/tools/relocation_packer/src/elf_file.cc
@@ -0,0 +1,977 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// TODO(simonb): Extend for 64-bit target libraries.
+
+#include "elf_file.h"
+
+#include <stdlib.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <string>
+#include <vector>
+
+#include "debug.h"
+#include "libelf.h"
+#include "packer.h"
+
+namespace relocation_packer {
+
+// Stub identifier written to 'null out' packed data, "NULL".
+static const Elf32_Word kStubIdentifier = 0x4c4c554eu;
+
+// Out-of-band dynamic tags used to indicate the offset and size of the
+// .android.rel.dyn section.
+static const Elf32_Sword DT_ANDROID_ARM_REL_OFFSET = DT_LOPROC;
+static const Elf32_Sword DT_ANDROID_ARM_REL_SIZE = DT_LOPROC + 1;
+
+namespace {
+
+// Get section data. Checks that the section has exactly one data entry,
+// so that the section size and the data size are the same. True in
+// practice for all sections we resize when packing or unpacking. Done
+// by ensuring that a call to elf_getdata(section, data) returns NULL as
+// the next data entry.
+Elf_Data* GetSectionData(Elf_Scn* section) {
+ Elf_Data* data = elf_getdata(section, NULL);
+ CHECK(data && elf_getdata(section, data) == NULL);
+ return data;
+}
+
+// Rewrite section data. Allocates new data and makes it the data element's
+// buffer. Relies on program exit to free allocated data.
+void RewriteSectionData(Elf_Data* data,
+ const void* section_data,
+ size_t size) {
+ CHECK(size == data->d_size);
+ uint8_t* area = new uint8_t[size];
+ memcpy(area, section_data, size);
+ data->d_buf = area;
+}
+
+// Verbose ELF header logging.
+void VerboseLogElfHeader(const Elf32_Ehdr* elf_header) {
+ VLOG("e_phoff = %u\n", elf_header->e_phoff);
+ VLOG("e_shoff = %u\n", elf_header->e_shoff);
+ VLOG("e_ehsize = %u\n", elf_header->e_ehsize);
+ VLOG("e_phentsize = %u\n", elf_header->e_phentsize);
+ VLOG("e_phnum = %u\n", elf_header->e_phnum);
+ VLOG("e_shnum = %u\n", elf_header->e_shnum);
+ VLOG("e_shstrndx = %u\n", elf_header->e_shstrndx);
+}
+
+// Verbose ELF program header logging.
+void VerboseLogProgramHeader(size_t program_header_index,
+ const Elf32_Phdr* program_header) {
+ std::string type;
+ switch (program_header->p_type) {
+ case PT_NULL: type = "NULL"; break;
+ case PT_LOAD: type = "LOAD"; break;
+ case PT_DYNAMIC: type = "DYNAMIC"; break;
+ case PT_INTERP: type = "INTERP"; break;
+ case PT_NOTE: type = "NOTE"; break;
+ case PT_SHLIB: type = "SHLIB"; break;
+ case PT_PHDR: type = "PHDR"; break;
+ case PT_TLS: type = "TLS"; break;
+ default: type = "(OTHER)"; break;
+ }
+ VLOG("phdr %lu : %s\n", program_header_index, type.c_str());
+ VLOG(" p_offset = %u\n", program_header->p_offset);
+ VLOG(" p_vaddr = %u\n", program_header->p_vaddr);
+ VLOG(" p_paddr = %u\n", program_header->p_paddr);
+ VLOG(" p_filesz = %u\n", program_header->p_filesz);
+ VLOG(" p_memsz = %u\n", program_header->p_memsz);
+}
+
+// Verbose ELF section header logging.
+void VerboseLogSectionHeader(const std::string& section_name,
+ const Elf32_Shdr* section_header) {
+ VLOG("section %s\n", section_name.c_str());
+ VLOG(" sh_addr = %u\n", section_header->sh_addr);
+ VLOG(" sh_offset = %u\n", section_header->sh_offset);
+ VLOG(" sh_size = %u\n", section_header->sh_size);
+}
+
+// Verbose ELF section data logging.
+void VerboseLogSectionData(const Elf_Data* data) {
+ VLOG(" data\n");
+ VLOG(" d_buf = %p\n", data->d_buf);
+ VLOG(" d_off = %lu\n", data->d_off);
+ VLOG(" d_size = %lu\n", data->d_size);
+}
+
+} // namespace
+
+// Load the complete ELF file into a memory image in libelf, and identify
+// the .rel.dyn, .dynamic, and .android.rel.dyn sections. No-op if the
+// ELF file has already been loaded.
+bool ElfFile::Load() {
+ if (elf_)
+ return true;
+
+ elf_ = elf_begin(fd_, ELF_C_RDWR, NULL);
+ CHECK(elf_);
+
+ if (elf_kind(elf_) != ELF_K_ELF) {
+ LOG("ERROR: File not in ELF format\n");
+ return false;
+ }
+
+ Elf32_Ehdr* elf_header = elf32_getehdr(elf_);
+ if (!elf_header) {
+ LOG("ERROR: Failed to load ELF header\n");
+ return false;
+ }
+ if (elf_header->e_machine != EM_ARM) {
+ LOG("ERROR: File is not an arm32 ELF file\n");
+ return false;
+ }
+
+ // Require that our endianness matches that of the target, and that both
+ // are little-endian. Safe for all current build/target combinations.
+ const int endian = static_cast<int>(elf_header->e_ident[5]);
+ CHECK(endian == ELFDATA2LSB);
+ CHECK(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__);
+
+ VLOG("endian = %u\n", endian);
+ VerboseLogElfHeader(elf_header);
+
+ const Elf32_Phdr* elf_program_header = elf32_getphdr(elf_);
+ CHECK(elf_program_header);
+
+ const Elf32_Phdr* dynamic_program_header = NULL;
+ for (size_t i = 0; i < elf_header->e_phnum; ++i) {
+ const Elf32_Phdr* program_header = &elf_program_header[i];
+ VerboseLogProgramHeader(i, program_header);
+
+ if (program_header->p_type == PT_DYNAMIC) {
+ CHECK(dynamic_program_header == NULL);
+ dynamic_program_header = program_header;
+ }
+ }
+ CHECK(dynamic_program_header != NULL);
+
+ size_t string_index;
+ elf_getshdrstrndx(elf_, &string_index);
+
+ // Notes of the .rel.dyn, .android.rel.dyn, and .dynamic sections. Found
+ // while iterating sections, and later stored in class attributes.
+ Elf_Scn* found_rel_dyn_section = NULL;
+ Elf_Scn* found_android_rel_dyn_section = NULL;
+ Elf_Scn* found_dynamic_section = NULL;
+
+ // Flag set if we encounter any .debug* section. We do not adjust any
+ // offsets or addresses of any debug data, so if we find one of these then
+ // the resulting output shared object should still run, but might not be
+ // usable for debugging, disassembly, and so on. Provides a warning if
+ // this occurs.
+ bool has_debug_section = false;
+
+ Elf_Scn* section = NULL;
+ while ((section = elf_nextscn(elf_, section)) != NULL) {
+ const Elf32_Shdr* section_header = elf32_getshdr(section);
+ std::string name = elf_strptr(elf_, string_index, section_header->sh_name);
+ VerboseLogSectionHeader(name, section_header);
+
+ // Note special sections as we encounter them.
+ if (name == ".rel.dyn") {
+ found_rel_dyn_section = section;
+ }
+ if (name == ".android.rel.dyn") {
+ found_android_rel_dyn_section = section;
+ }
+ if (section_header->sh_offset == dynamic_program_header->p_offset) {
+ found_dynamic_section = section;
+ }
+
+ // If we find a section named .debug*, set the debug warning flag.
+ if (std::string(name).find(".debug") == 0) {
+ has_debug_section = true;
+ }
+
+ Elf_Data* data = NULL;
+ while ((data = elf_getdata(section, data)) != NULL) {
+ VerboseLogSectionData(data);
+ }
+ }
+
+ // Loading failed if we did not find the required special sections.
+ if (!found_rel_dyn_section) {
+ LOG("ERROR: Missing .rel.dyn section\n");
+ return false;
+ }
+ if (!found_dynamic_section) {
+ LOG("ERROR: Missing .dynamic section\n");
+ return false;
+ }
+ if (!found_android_rel_dyn_section) {
+ LOG("ERROR: Missing .android.rel.dyn section "
+ "(to fix, run with --help and follow the pre-packing instructions)\n");
+ return false;
+ }
+
+ if (has_debug_section) {
+ LOG("WARNING: found .debug section(s), and ignored them\n");
+ }
+
+ rel_dyn_section_ = found_rel_dyn_section;
+ dynamic_section_ = found_dynamic_section;
+ android_rel_dyn_section_ = found_android_rel_dyn_section;
+ return true;
+}
+
+namespace {
+
+// Helper for ResizeSection(). Adjust the main ELF header for the hole.
+void AdjustElfHeaderForHole(Elf32_Ehdr* elf_header,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ if (elf_header->e_phoff > hole_start) {
+ elf_header->e_phoff += hole_size;
+ VLOG("e_phoff adjusted to %u\n", elf_header->e_phoff);
+ }
+ if (elf_header->e_shoff > hole_start) {
+ elf_header->e_shoff += hole_size;
+ VLOG("e_shoff adjusted to %u\n", elf_header->e_shoff);
+ }
+}
+
+// Helper for ResizeSection(). Adjust all program headers for the hole.
+void AdjustProgramHeadersForHole(Elf32_Phdr* elf_program_header,
+ size_t program_header_count,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ for (size_t i = 0; i < program_header_count; ++i) {
+ Elf32_Phdr* program_header = &elf_program_header[i];
+
+ if (program_header->p_offset > hole_start) {
+ // The hole start is past this segment, so adjust offsets and addrs.
+ program_header->p_offset += hole_size;
+ VLOG("phdr %lu p_offset adjusted to %u\n", i, program_header->p_offset);
+
+ // Only adjust vaddr and paddr if this program header has them.
+ if (program_header->p_vaddr != 0) {
+ program_header->p_vaddr += hole_size;
+ VLOG("phdr %lu p_vaddr adjusted to %u\n", i, program_header->p_vaddr);
+ }
+ if (program_header->p_paddr != 0) {
+ program_header->p_paddr += hole_size;
+ VLOG("phdr %lu p_paddr adjusted to %u\n", i, program_header->p_paddr);
+ }
+ } else if (program_header->p_offset +
+ program_header->p_filesz > hole_start) {
+ // The hole start is within this segment, so adjust file and in-memory
+ // sizes, but leave offsets and addrs unchanged.
+ program_header->p_filesz += hole_size;
+ VLOG("phdr %lu p_filesz adjusted to %u\n", i, program_header->p_filesz);
+ program_header->p_memsz += hole_size;
+ VLOG("phdr %lu p_memsz adjusted to %u\n", i, program_header->p_memsz);
+ }
+ }
+}
+
+// Helper for ResizeSection(). Adjust all section headers for the hole.
+void AdjustSectionHeadersForHole(Elf* elf,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ size_t string_index;
+ elf_getshdrstrndx(elf, &string_index);
+
+ Elf_Scn* section = NULL;
+ while ((section = elf_nextscn(elf, section)) != NULL) {
+ Elf32_Shdr* section_header = elf32_getshdr(section);
+ std::string name = elf_strptr(elf, string_index, section_header->sh_name);
+
+ if (section_header->sh_offset > hole_start) {
+ section_header->sh_offset += hole_size;
+ VLOG("section %s sh_offset"
+ " adjusted to %u\n", name.c_str(), section_header->sh_offset);
+ // Only adjust section addr if this section has one.
+ if (section_header->sh_addr != 0) {
+ section_header->sh_addr += hole_size;
+ VLOG("section %s sh_addr"
+ " adjusted to %u\n", name.c_str(), section_header->sh_addr);
+ }
+ }
+ }
+}
+
+// Helper for ResizeSection(). Adjust the .dynamic section for the hole.
+void AdjustDynamicSectionForHole(Elf_Scn* dynamic_section,
+ bool is_rel_dyn_resize,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ Elf_Data* data = GetSectionData(dynamic_section);
+
+ const Elf32_Dyn* dynamic_base = reinterpret_cast<Elf32_Dyn*>(data->d_buf);
+ std::vector<Elf32_Dyn> dynamics(
+ dynamic_base,
+ dynamic_base + data->d_size / sizeof(dynamics[0]));
+
+ for (size_t i = 0; i < dynamics.size(); ++i) {
+ Elf32_Dyn* dynamic = &dynamics[i];
+ const Elf32_Sword tag = dynamic->d_tag;
+ // Any tags that hold offsets are adjustment candidates.
+ const bool is_adjustable = (tag == DT_PLTGOT ||
+ tag == DT_HASH ||
+ tag == DT_STRTAB ||
+ tag == DT_SYMTAB ||
+ tag == DT_RELA ||
+ tag == DT_INIT ||
+ tag == DT_FINI ||
+ tag == DT_REL ||
+ tag == DT_JMPREL ||
+ tag == DT_INIT_ARRAY ||
+ tag == DT_FINI_ARRAY ||
+ tag == DT_ANDROID_ARM_REL_OFFSET);
+ if (is_adjustable && dynamic->d_un.d_ptr > hole_start) {
+ dynamic->d_un.d_ptr += hole_size;
+ VLOG("dynamic[%lu] %u"
+ " d_ptr adjusted to %u\n", i, dynamic->d_tag, dynamic->d_un.d_ptr);
+ }
+
+ // If we are specifically resizing .rel.dyn, we need to make some added
+ // adjustments to tags that indicate the counts of R_ARM_RELATIVE
+ // relocations in the shared object.
+ if (is_rel_dyn_resize) {
+ // DT_RELSZ is the overall size of relocations. Adjust by hole size.
+ if (tag == DT_RELSZ) {
+ dynamic->d_un.d_val += hole_size;
+ VLOG("dynamic[%lu] %u"
+ " d_val adjusted to %u\n", i, dynamic->d_tag, dynamic->d_un.d_val);
+ }
+
+ // The crazy linker does not use DT_RELCOUNT, but we keep it updated
+ // anyway. In practice the section hole is always equal to the size
+ // of R_ARM_RELATIVE relocations, and DT_RELCOUNT is the count of
+ // relative relocations. So closing a hole on packing reduces
+ // DT_RELCOUNT to zero, and opening a hole on unpacking restores it to
+ // its pre-packed value.
+ if (tag == DT_RELCOUNT) {
+ dynamic->d_un.d_val += hole_size / sizeof(Elf32_Rel);
+ VLOG("dynamic[%lu] %u"
+ " d_val adjusted to %u\n", i, dynamic->d_tag, dynamic->d_un.d_val);
+ }
+
+ // DT_RELENT doesn't change, but make sure it is what we expect.
+ if (tag == DT_RELENT) {
+ CHECK(dynamic->d_un.d_val == sizeof(Elf32_Rel));
+ }
+ }
+ }
+
+ void* section_data = &dynamics[0];
+ size_t bytes = dynamics.size() * sizeof(dynamics[0]);
+ RewriteSectionData(data, section_data, bytes);
+}
+
+// Helper for ResizeSection(). Adjust the .dynsym section for the hole.
+// We need to adjust the values for the symbols represented in it.
+void AdjustDynSymSectionForHole(Elf_Scn* dynsym_section,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ Elf_Data* data = GetSectionData(dynsym_section);
+
+ const Elf32_Sym* dynsym_base = reinterpret_cast<Elf32_Sym*>(data->d_buf);
+ std::vector<Elf32_Sym> dynsyms
+ (dynsym_base,
+ dynsym_base + data->d_size / sizeof(dynsyms[0]));
+
+ for (size_t i = 0; i < dynsyms.size(); ++i) {
+ Elf32_Sym* dynsym = &dynsyms[i];
+ const int type = static_cast<int>(ELF32_ST_TYPE(dynsym->st_info));
+ const bool is_adjustable = (type == STT_OBJECT ||
+ type == STT_FUNC ||
+ type == STT_SECTION ||
+ type == STT_FILE ||
+ type == STT_COMMON ||
+ type == STT_TLS);
+ if (is_adjustable && dynsym->st_value > hole_start) {
+ dynsym->st_value += hole_size;
+ VLOG("dynsym[%lu] type=%u"
+ " st_value adjusted to %u\n", i, type, dynsym->st_value);
+ }
+ }
+
+ void* section_data = &dynsyms[0];
+ size_t bytes = dynsyms.size() * sizeof(dynsyms[0]);
+ RewriteSectionData(data, section_data, bytes);
+}
+
+// Helper for ResizeSection(). Adjust the .rel.plt section for the hole.
+// We need to adjust the offset of every relocation inside it that falls
+// beyond the hole start.
+void AdjustRelPltSectionForHole(Elf_Scn* relplt_section,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ Elf_Data* data = GetSectionData(relplt_section);
+
+ const Elf32_Rel* relplt_base = reinterpret_cast<Elf32_Rel*>(data->d_buf);
+ std::vector<Elf32_Rel> relplts(
+ relplt_base,
+ relplt_base + data->d_size / sizeof(relplts[0]));
+
+ for (size_t i = 0; i < relplts.size(); ++i) {
+ Elf32_Rel* relplt = &relplts[i];
+ if (relplt->r_offset > hole_start) {
+ relplt->r_offset += hole_size;
+ VLOG("relplt[%lu] r_offset adjusted to %u\n", i, relplt->r_offset);
+ }
+ }
+
+ void* section_data = &relplts[0];
+ size_t bytes = relplts.size() * sizeof(relplts[0]);
+ RewriteSectionData(data, section_data, bytes);
+}
+
+// Helper for ResizeSection(). Adjust the .symtab section for the hole.
+// We want to adjust the value of every symbol in it that falls beyond
+// the hole start.
+void AdjustSymTabSectionForHole(Elf_Scn* symtab_section,
+ Elf32_Off hole_start,
+ int32_t hole_size) {
+ Elf_Data* data = GetSectionData(symtab_section);
+
+ const Elf32_Sym* symtab_base = reinterpret_cast<Elf32_Sym*>(data->d_buf);
+ std::vector<Elf32_Sym> symtab(
+ symtab_base,
+ symtab_base + data->d_size / sizeof(symtab[0]));
+
+ for (size_t i = 0; i < symtab.size(); ++i) {
+ Elf32_Sym* sym = &symtab[i];
+ if (sym->st_value > hole_start) {
+ sym->st_value += hole_size;
+ VLOG("symtab[%lu] value adjusted to %u\n", i, sym->st_value);
+ }
+ }
+
+ void* section_data = &symtab[0];
+ size_t bytes = symtab.size() * sizeof(symtab[0]);
+ RewriteSectionData(data, section_data, bytes);
+}
+
+// Resize a section. If the new size is larger than the current size, open
+// up a hole by increasing file offsets that come after the hole. If smaller
+// than the current size, remove the hole by decreasing those offsets.
+void ResizeSection(Elf* elf, Elf_Scn* section, size_t new_size) {
+ Elf32_Shdr* section_header = elf32_getshdr(section);
+ if (section_header->sh_size == new_size)
+ return;
+
+ // Note if we are resizing the real .rel.dyn. If yes, then we have to
+ // massage d_un.d_val in the dynamic section where d_tag is DT_RELSZ and
+ // DT_RELCOUNT.
+ size_t string_index;
+ elf_getshdrstrndx(elf, &string_index);
+ const std::string section_name =
+ elf_strptr(elf, string_index, section_header->sh_name);
+ const bool is_rel_dyn_resize = section_name == ".rel.dyn";
+
+ // Require that the section size and the data size are the same. True
+ // in practice for all sections we resize when packing or unpacking.
+ Elf_Data* data = GetSectionData(section);
+ CHECK(data->d_off == 0 && data->d_size == section_header->sh_size);
+
+ // Require that the section is not zero-length (that is, has allocated
+ // data that we can validly expand).
+ CHECK(data->d_size && data->d_buf);
+
+ const Elf32_Off hole_start = section_header->sh_offset;
+ const int32_t hole_size = new_size - data->d_size;
+
+ VLOG_IF(hole_size > 0, "expand section size = %lu\n", data->d_size);
+ VLOG_IF(hole_size < 0, "shrink section size = %lu\n", data->d_size);
+
+ // Resize the data and the section header.
+ data->d_size += hole_size;
+ section_header->sh_size += hole_size;
+
+ Elf32_Ehdr* elf_header = elf32_getehdr(elf);
+ Elf32_Phdr* elf_program_header = elf32_getphdr(elf);
+
+ // Add the hole size to all offsets in the ELF file that are after the
+ // start of the hole. If the hole size is positive we are expanding the
+ // section to create a new hole; if negative, we are closing up a hole.
+
+ // Start with the main ELF header.
+ AdjustElfHeaderForHole(elf_header, hole_start, hole_size);
+
+ // Adjust all program headers.
+ AdjustProgramHeadersForHole(elf_program_header,
+ elf_header->e_phnum,
+ hole_start,
+ hole_size);
+
+ // Adjust all section headers.
+ AdjustSectionHeadersForHole(elf, hole_start, hole_size);
+
+ // We use the dynamic program header entry to locate the dynamic section.
+ const Elf32_Phdr* dynamic_program_header = NULL;
+
+ // Find the dynamic program header entry.
+ for (size_t i = 0; i < elf_header->e_phnum; ++i) {
+ Elf32_Phdr* program_header = &elf_program_header[i];
+
+ if (program_header->p_type == PT_DYNAMIC) {
+ dynamic_program_header = program_header;
+ }
+ }
+ CHECK(dynamic_program_header);
+
+ // Sections requiring special attention, and the .android.rel.dyn offset.
+ Elf_Scn* dynamic_section = NULL;
+ Elf_Scn* dynsym_section = NULL;
+ Elf_Scn* relplt_section = NULL;
+ Elf_Scn* symtab_section = NULL;
+ Elf32_Off android_rel_dyn_offset = 0;
+
+ // Find these sections, and the .android.rel.dyn offset.
+ section = NULL;
+ while ((section = elf_nextscn(elf, section)) != NULL) {
+ Elf32_Shdr* section_header = elf32_getshdr(section);
+ std::string name = elf_strptr(elf, string_index, section_header->sh_name);
+
+ if (section_header->sh_offset == dynamic_program_header->p_offset) {
+ dynamic_section = section;
+ }
+ if (name == ".dynsym") {
+ dynsym_section = section;
+ }
+ if (name == ".rel.plt") {
+ relplt_section = section;
+ }
+ if (name == ".symtab") {
+ symtab_section = section;
+ }
+
+ // Note .android.rel.dyn offset.
+ if (name == ".android.rel.dyn") {
+ android_rel_dyn_offset = section_header->sh_offset;
+ }
+ }
+ CHECK(dynamic_section != NULL);
+ CHECK(dynsym_section != NULL);
+ CHECK(relplt_section != NULL);
+ CHECK(android_rel_dyn_offset != 0);
+
+ // Adjust the .dynamic section for the hole. Because we have to edit the
+ // current contents of .dynamic we disallow resizing it.
+ CHECK(section != dynamic_section);
+ AdjustDynamicSectionForHole(dynamic_section,
+ is_rel_dyn_resize,
+ hole_start,
+ hole_size);
+
+ // Adjust the .dynsym section for the hole.
+ AdjustDynSymSectionForHole(dynsym_section, hole_start, hole_size);
+
+ // Adjust the .rel.plt section for the hole.
+ AdjustRelPltSectionForHole(relplt_section, hole_start, hole_size);
+
+ // If present, adjust the .symtab section for the hole. If the shared
+ // library was stripped then .symtab will be absent.
+ if (symtab_section)
+ AdjustSymTabSectionForHole(symtab_section, hole_start, hole_size);
+}
+
+// Replace the first free (unused) slot in a dynamics vector with the given
+// value. The vector always ends with a free (unused) element, so the slot
+// found cannot be the last one in the vector.
+void AddDynamicEntry(Elf32_Dyn dyn,
+ std::vector<Elf32_Dyn>* dynamics) {
+ // Loop until the penultimate entry. We cannot replace the end sentinel.
+ for (size_t i = 0; i < dynamics->size() - 1; ++i) {
+ Elf32_Dyn &slot = dynamics->at(i);
+ if (slot.d_tag == DT_NULL) {
+ slot = dyn;
+ VLOG("dynamic[%lu] overwritten with %u\n", i, dyn.d_tag);
+ return;
+ }
+ }
+
+ // No free dynamics vector slot was found.
+ LOG("FATAL: No spare dynamic vector slots found "
+ "(to fix, increase gold's --spare-dynamic-tags value)\n");
+ NOTREACHED();
+}
+
+// Remove the element in the dynamics vector that matches the given tag with
+// unused slot data. Shuffle the following elements up, and ensure that the
+// last is the null sentinel.
+void RemoveDynamicEntry(Elf32_Sword tag,
+ std::vector<Elf32_Dyn>* dynamics) {
+ // Loop until the penultimate entry, and never match the end sentinel.
+ for (size_t i = 0; i < dynamics->size() - 1; ++i) {
+ Elf32_Dyn &slot = dynamics->at(i);
+ if (slot.d_tag == tag) {
+ for ( ; i < dynamics->size() - 1; ++i) {
+ dynamics->at(i) = dynamics->at(i + 1);
+ VLOG("dynamic[%lu] overwritten with dynamic[%lu]\n", i, i + 1);
+ }
+ CHECK(dynamics->at(i).d_tag == DT_NULL);
+ return;
+ }
+ }
+
+ // No matching dynamics vector entry was found.
+ NOTREACHED();
+}
+
+// Apply R_ARM_RELATIVE relocations to the file data to which they refer.
+// This relocates data into the area it will occupy after the hole in
+// .rel.dyn is added or removed.
+void AdjustRelocationTargets(Elf* elf,
+ Elf32_Off hole_start,
+ size_t hole_size,
+ const std::vector<Elf32_Rel>& relocations) {
+ Elf_Scn* section = NULL;
+ while ((section = elf_nextscn(elf, section)) != NULL) {
+ const Elf32_Shdr* section_header = elf32_getshdr(section);
+
+ // Identify this section's start and end addresses.
+ const Elf32_Addr section_start = section_header->sh_addr;
+ const Elf32_Addr section_end = section_start + section_header->sh_size;
+
+ Elf_Data* data = GetSectionData(section);
+
+ // Ignore sections with no effective data.
+ if (data->d_buf == NULL)
+ continue;
+
+ // Create a copy-on-write pointer to the section's data.
+ uint8_t* area = reinterpret_cast<uint8_t*>(data->d_buf);
+
+ for (size_t i = 0; i < relocations.size(); ++i) {
+ const Elf32_Rel* relocation = &relocations[i];
+ CHECK(ELF32_R_TYPE(relocation->r_info) == R_ARM_RELATIVE);
+
+ // See if this relocation points into the current section.
+ if (relocation->r_offset >= section_start &&
+ relocation->r_offset < section_end) {
+ Elf32_Addr byte_offset = relocation->r_offset - section_start;
+ Elf32_Off* target = reinterpret_cast<Elf32_Off*>(area + byte_offset);
+
+ // Is the relocation's target after the hole's start?
+ if (*target > hole_start) {
+
+ // Copy on first write. Recompute target to point into the newly
+ // allocated buffer.
+ if (area == data->d_buf) {
+ area = new uint8_t[data->d_size];
+ memcpy(area, data->d_buf, data->d_size);
+ target = reinterpret_cast<Elf32_Off*>(area + byte_offset);
+ }
+
+ *target += hole_size;
+ VLOG("relocation[%lu] target adjusted to %u\n", i, *target);
+ }
+ }
+ }
+
+ // If we applied any relocation to this section, write it back.
+ if (area != data->d_buf) {
+ RewriteSectionData(data, area, data->d_size);
+ delete [] area;
+ }
+ }
+}
+
+// Adjust relocations so that the offset that they indicate will be correct
+// after the hole in .rel.dyn is added or removed (in effect, relocate the
+// relocations).
+void AdjustRelocations(Elf32_Off hole_start,
+ size_t hole_size,
+ std::vector<Elf32_Rel>* relocations) {
+ for (size_t i = 0; i < relocations->size(); ++i) {
+ Elf32_Rel* relocation = &relocations->at(i);
+ if (relocation->r_offset > hole_start) {
+ relocation->r_offset += hole_size;
+ VLOG("relocation[%lu] offset adjusted to %u\n", i, relocation->r_offset);
+ }
+ }
+}
+
+} // namespace
+
+// Remove R_ARM_RELATIVE entries from .rel.dyn and write as packed data
+// into .android.rel.dyn.
+bool ElfFile::PackRelocations() {
+ // Load the ELF file into libelf.
+ if (!Load()) {
+ LOG("ERROR: Failed to load as ELF (elf_error=%d)\n", elf_errno());
+ return false;
+ }
+
+ // Retrieve the current .rel.dyn section data.
+ Elf_Data* data = GetSectionData(rel_dyn_section_);
+
+ // Convert data to a vector of Elf32 relocations.
+ const Elf32_Rel* relocations_base = reinterpret_cast<Elf32_Rel*>(data->d_buf);
+ std::vector<Elf32_Rel> relocations(
+ relocations_base,
+ relocations_base + data->d_size / sizeof(relocations[0]));
+
+ std::vector<Elf32_Rel> relative_relocations;
+ std::vector<Elf32_Rel> other_relocations;
+
+ // Filter relocations into those that are R_ARM_RELATIVE and others.
+ for (size_t i = 0; i < relocations.size(); ++i) {
+ const Elf32_Rel& relocation = relocations[i];
+ if (ELF32_R_TYPE(relocation.r_info) == R_ARM_RELATIVE) {
+ CHECK(ELF32_R_SYM(relocation.r_info) == 0);
+ relative_relocations.push_back(relocation);
+ } else {
+ other_relocations.push_back(relocation);
+ }
+ }
+ VLOG("R_ARM_RELATIVE: %lu entries\n", relative_relocations.size());
+ VLOG("Other : %lu entries\n", other_relocations.size());
+ VLOG("Total : %lu entries\n", relocations.size());
+
+ // If no relative relocations then we have nothing packable. Perhaps
+ // the shared object has already been packed?
+ if (relative_relocations.empty()) {
+ LOG("ERROR: No R_ARM_RELATIVE relocations found (already packed?)\n");
+ return false;
+ }
+
+ // Pre-calculate the size of the hole we will close up when we rewrite
+ // .reldyn. We have to adjust all relocation addresses to account for this.
+ Elf32_Shdr* section_header = elf32_getshdr(rel_dyn_section_);
+ const Elf32_Off hole_start = section_header->sh_offset;
+ const size_t hole_size =
+ relative_relocations.size() * sizeof(relative_relocations[0]);
+
+ // Unless padding, pre-apply R_ARM_RELATIVE relocations to account for the
+ // hole, and pre-adjust all relocation offsets accordingly.
+ if (!is_padding_rel_dyn_) {
+ // Apply relocations to all R_ARM_RELATIVE data to relocate it into the
+ // area it will occupy once the hole in .rel.dyn is removed.
+ AdjustRelocationTargets(elf_, hole_start, -hole_size, relative_relocations);
+ // Relocate the relocations.
+ AdjustRelocations(hole_start, -hole_size, &relative_relocations);
+ AdjustRelocations(hole_start, -hole_size, &other_relocations);
+ }
+
+ // Pack R_ARM_RELATIVE relocations.
+ const size_t initial_bytes =
+ relative_relocations.size() * sizeof(relative_relocations[0]);
+ LOG("Unpacked R_ARM_RELATIVE: %lu bytes\n", initial_bytes);
+ std::vector<uint8_t> packed;
+ RelocationPacker packer;
+ packer.PackRelativeRelocations(relative_relocations, &packed);
+ const void* packed_data = &packed[0];
+ const size_t packed_bytes = packed.size() * sizeof(packed[0]);
+ LOG("Packed R_ARM_RELATIVE: %lu bytes\n", packed_bytes);
+
+ // If we have insufficient R_ARM_RELATIVE relocations to form a run then
+ // packing fails.
+ if (packed.empty()) {
+ LOG("Too few R_ARM_RELATIVE relocations to pack\n");
+ return false;
+ }
+
+ // Run a loopback self-test as a check that packing is lossless.
+ std::vector<Elf32_Rel> unpacked;
+ packer.UnpackRelativeRelocations(packed, &unpacked);
+ CHECK(unpacked.size() == relative_relocations.size());
+ for (size_t i = 0; i < unpacked.size(); ++i) {
+ CHECK(unpacked[i].r_offset == relative_relocations[i].r_offset);
+ CHECK(unpacked[i].r_info == relative_relocations[i].r_info);
+ }
+
+ // Make sure packing saved some space.
+ if (packed_bytes >= initial_bytes) {
+ LOG("Packing R_ARM_RELATIVE relocations saves no space\n");
+ return false;
+ }
+
+ // If padding, add R_ARM_NONE relocations to other_relocations to make it
+ // the same size as the the original relocations we read in. This makes
+ // the ResizeSection() below a no-op.
+ if (is_padding_rel_dyn_) {
+ const Elf32_Rel r_arm_none = {R_ARM_NONE, 0};
+ const size_t required = relocations.size() - other_relocations.size();
+ std::vector<Elf32_Rel> padding(required, r_arm_none);
+ other_relocations.insert(
+ other_relocations.end(), padding.begin(), padding.end());
+ }
+
+ // Rewrite the current .rel.dyn section to be only the non-R_ARM_RELATIVE
+ // relocations, then shrink it to size.
+ const void* section_data = &other_relocations[0];
+ const size_t bytes = other_relocations.size() * sizeof(other_relocations[0]);
+ ResizeSection(elf_, rel_dyn_section_, bytes);
+ RewriteSectionData(data, section_data, bytes);
+
+ // Rewrite the current .android.rel.dyn section to hold the packed
+ // R_ARM_RELATIVE relocations.
+ data = GetSectionData(android_rel_dyn_section_);
+ ResizeSection(elf_, android_rel_dyn_section_, packed_bytes);
+ RewriteSectionData(data, packed_data, packed_bytes);
+
+ // Rewrite .dynamic to include two new tags describing .android.rel.dyn.
+ data = GetSectionData(dynamic_section_);
+ const Elf32_Dyn* dynamic_base = reinterpret_cast<Elf32_Dyn*>(data->d_buf);
+ std::vector<Elf32_Dyn> dynamics(
+ dynamic_base,
+ dynamic_base + data->d_size / sizeof(dynamics[0]));
+ section_header = elf32_getshdr(android_rel_dyn_section_);
+ // Use two of the spare slots to describe the .android.rel.dyn section.
+ const Elf32_Dyn offset_dyn
+ = {DT_ANDROID_ARM_REL_OFFSET, {section_header->sh_offset}};
+ AddDynamicEntry(offset_dyn, &dynamics);
+ const Elf32_Dyn size_dyn
+ = {DT_ANDROID_ARM_REL_SIZE, {section_header->sh_size}};
+ AddDynamicEntry(size_dyn, &dynamics);
+ const void* dynamics_data = &dynamics[0];
+ const size_t dynamics_bytes = dynamics.size() * sizeof(dynamics[0]);
+ RewriteSectionData(data, dynamics_data, dynamics_bytes);
+
+ Flush();
+ return true;
+}
+
+// Find packed R_ARM_RELATIVE relocations in .android.rel.dyn, unpack them,
+// and rewrite the .rel.dyn section in so_file to contain unpacked data.
+bool ElfFile::UnpackRelocations() {
+ // Load the ELF file into libelf.
+ if (!Load()) {
+ LOG("ERROR: Failed to load as ELF (elf_error=%d)\n", elf_errno());
+ return false;
+ }
+
+ // Retrieve the current .android.rel.dyn section data.
+ Elf_Data* data = GetSectionData(android_rel_dyn_section_);
+
+ // Convert data to a vector of bytes.
+ const uint8_t* packed_base = reinterpret_cast<uint8_t*>(data->d_buf);
+ std::vector<uint8_t> packed(
+ packed_base,
+ packed_base + data->d_size / sizeof(packed[0]));
+
+ // Properly packed data must begin with "APR1".
+ if (packed.empty() ||
+ packed[0] != 'A' || packed[1] != 'P' ||
+ packed[2] != 'R' || packed[3] != '1') {
+ LOG("ERROR: Packed R_ARM_RELATIVE relocations not found (not packed?)\n");
+ return false;
+ }
+
+ // Unpack the data to re-materialize the R_ARM_RELATIVE relocations.
+ const size_t packed_bytes = packed.size() * sizeof(packed[0]);
+ LOG("Packed R_ARM_RELATIVE: %lu bytes\n", packed_bytes);
+ std::vector<Elf32_Rel> relative_relocations;
+ RelocationPacker packer;
+ packer.UnpackRelativeRelocations(packed, &relative_relocations);
+ const size_t unpacked_bytes =
+ relative_relocations.size() * sizeof(relative_relocations[0]);
+ LOG("Unpacked R_ARM_RELATIVE: %lu bytes\n", unpacked_bytes);
+
+ // Retrieve the current .rel.dyn section data.
+ data = GetSectionData(rel_dyn_section_);
+
+ // Interpret data as Elf32 relocations.
+ const Elf32_Rel* relocations_base = reinterpret_cast<Elf32_Rel*>(data->d_buf);
+ std::vector<Elf32_Rel> relocations(
+ relocations_base,
+ relocations_base + data->d_size / sizeof(relocations[0]));
+
+ std::vector<Elf32_Rel> other_relocations;
+ size_t padding = 0;
+
+ // Filter relocations to locate any that are R_ARM_NONE. These will occur
+ // if padding was turned on for packing.
+ for (size_t i = 0; i < relocations.size(); ++i) {
+ const Elf32_Rel& relocation = relocations[i];
+ if (ELF32_R_TYPE(relocation.r_info) != R_ARM_NONE) {
+ other_relocations.push_back(relocation);
+ } else {
+ ++padding;
+ }
+ }
+ LOG("R_ARM_RELATIVE: %lu entries\n", relative_relocations.size());
+ LOG("Other : %lu entries\n", other_relocations.size());
+
+ // If we found the same number of R_ARM_NONE entries in .rel.dyn as we
+ // hold as unpacked relative relocations, then this is a padded file.
+ const bool is_padded = padding == relative_relocations.size();
+
+ // Pre-calculate the size of the hole we will open up when we rewrite
+ // .reldyn. We have to adjust all relocation addresses to account for this.
+ Elf32_Shdr* section_header = elf32_getshdr(rel_dyn_section_);
+ const Elf32_Off hole_start = section_header->sh_offset;
+ const size_t hole_size =
+ relative_relocations.size() * sizeof(relative_relocations[0]);
+
+ // Unless padded, pre-apply R_ARM_RELATIVE relocations to account for the
+ // hole, and pre-adjust all relocation offsets accordingly.
+ if (!is_padded) {
+ // Apply relocations to all R_ARM_RELATIVE data to relocate it into the
+ // area it will occupy once the hole in .rel.dyn is opened.
+ AdjustRelocationTargets(elf_, hole_start, hole_size, relative_relocations);
+ // Relocate the relocations.
+ AdjustRelocations(hole_start, hole_size, &relative_relocations);
+ AdjustRelocations(hole_start, hole_size, &other_relocations);
+ }
+
+ // Rewrite the current .rel.dyn section to be the R_ARM_RELATIVE relocations
+ // followed by other relocations. This is the usual order in which we find
+ // them after linking, so this action will normally put the entire .rel.dyn
+ // section back to its pre-split-and-packed state.
+ relocations.assign(relative_relocations.begin(), relative_relocations.end());
+ relocations.insert(relocations.end(),
+ other_relocations.begin(), other_relocations.end());
+ const void* section_data = &relocations[0];
+ const size_t bytes = relocations.size() * sizeof(relocations[0]);
+ LOG("Total : %lu entries\n", relocations.size());
+ ResizeSection(elf_, rel_dyn_section_, bytes);
+ RewriteSectionData(data, section_data, bytes);
+
+ // Nearly empty the current .android.rel.dyn section. Leaves a four-byte
+ // stub so that some data remains allocated to the section. This is a
+ // convenience which allows us to re-pack this file again without
+ // having to remove the section and then add a new small one with objcopy.
+ // The way we resize sections relies on there being some data in a section.
+ data = GetSectionData(android_rel_dyn_section_);
+ ResizeSection(elf_, android_rel_dyn_section_, sizeof(kStubIdentifier));
+ RewriteSectionData(data, &kStubIdentifier, sizeof(kStubIdentifier));
+
+ // Rewrite .dynamic to remove two tags describing .android.rel.dyn.
+ data = GetSectionData(dynamic_section_);
+ const Elf32_Dyn* dynamic_base = reinterpret_cast<Elf32_Dyn*>(data->d_buf);
+ std::vector<Elf32_Dyn> dynamics(
+ dynamic_base,
+ dynamic_base + data->d_size / sizeof(dynamics[0]));
+ RemoveDynamicEntry(DT_ANDROID_ARM_REL_SIZE, &dynamics);
+ RemoveDynamicEntry(DT_ANDROID_ARM_REL_OFFSET, &dynamics);
+ const void* dynamics_data = &dynamics[0];
+ const size_t dynamics_bytes = dynamics.size() * sizeof(dynamics[0]);
+ RewriteSectionData(data, dynamics_data, dynamics_bytes);
+
+ Flush();
+ return true;
+}
+
+// Flush rewritten shared object file data.
+void ElfFile::Flush() {
+ // Flag all ELF data held in memory as needing to be written back to the
+ // file, and tell libelf that we have controlled the file layout.
+ elf_flagelf(elf_, ELF_C_SET, ELF_F_DIRTY);
+ elf_flagelf(elf_, ELF_C_SET, ELF_F_LAYOUT);
+
+ // Write ELF data back to disk.
+ const off_t file_bytes = elf_update(elf_, ELF_C_WRITE);
+ CHECK(file_bytes > 0);
+ VLOG("elf_update returned: %lu\n", file_bytes);
+
+ // Clean up libelf, and truncate the output file to the number of bytes
+ // written by elf_update().
+ elf_end(elf_);
+ elf_ = NULL;
+ const int truncate = ftruncate(fd_, file_bytes);
+ CHECK(truncate == 0);
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/elf_file.h b/tools/relocation_packer/src/elf_file.h
new file mode 100644
index 0000000..6f23c328
--- /dev/null
+++ b/tools/relocation_packer/src/elf_file.h
@@ -0,0 +1,107 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// ELF shared object file updates handler.
+//
+// Provides functions to remove R_ARM_RELATIVE relocations from the .rel.dyn
+// section and pack them in .android.rel.dyn, and unpack to return the file
+// to its pre-packed state.
+//
+// Files to be packed or unpacked must include an existing .android.rel.dyn
+// section. A standard libchrome.<version>.so will not contain this section,
+// so the following can be used to add one:
+//
+// 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
+//
+// To use, open the file and pass the file descriptor to the constructor,
+// then pack or unpack as desired. Packing or unpacking will flush the file
+// descriptor on success. Example:
+//
+// int fd = open(..., O_RDWR);
+// ElfFile elf_file(fd);
+// bool status;
+// if (is_packing)
+// status = elf_file.PackRelocations();
+// else
+// status = elf_file.UnpackRelocations();
+// close(fd);
+//
+// SetPadding() causes PackRelocations() to pad .rel.dyn with R_ARM_NONE
+// entries rather than cutting a hole out of the shared object file. This
+// keeps all load addresses and offsets constant, and enables easier
+// debugging and testing.
+//
+// A packed shared object file has all of its R_ARM_RELATIVE relocations
+// removed from .rel.dyn, and replaced as packed data in .android.rel.dyn.
+// The resulting file is shorter than its non-packed original.
+//
+// Unpacking a packed file restores the file to its non-packed state, by
+// expanding the packed data in android.rel.dyn, combining the R_ARM_RELATIVE
+// relocations with the data already in .rel.dyn, and then writing back the
+// now expanded .rel.dyn section.
+
+#ifndef TOOLS_RELOCATION_PACKER_SRC_ELF_FILE_H_
+#define TOOLS_RELOCATION_PACKER_SRC_ELF_FILE_H_
+
+#include <string.h>
+
+#include "elf.h"
+#include "libelf.h"
+#include "packer.h"
+
+namespace relocation_packer {
+
+// An ElfFile reads shared objects, and shuttles R_ARM_RELATIVE relocations
+// between .rel.dyn and .android.rel.dyn sections.
+class ElfFile {
+ public:
+ explicit ElfFile(int fd) { memset(this, 0, sizeof(*this)); fd_ = fd; }
+ ~ElfFile() {}
+
+ // Set padding mode. When padding, PackRelocations() will not shrink
+ // the .rel.dyn section, but instead replace R_ARM_RELATIVE with
+ // R_ARM_NONE entries.
+ // |flag| is true to pad .rel.dyn, false to shrink it.
+ inline void SetPadding(bool flag) { is_padding_rel_dyn_ = flag; }
+
+ // Transfer R_ARM_RELATIVE relocations from .rel.dyn to a packed
+ // representation in .android.rel.dyn. Returns true on success.
+ bool PackRelocations();
+
+ // Transfer R_ARM_RELATIVE relocations from a packed representation in
+ // .android.rel.dyn to .rel.dyn. Returns true on success.
+ bool UnpackRelocations();
+
+ private:
+ // Load a new ElfFile from a filedescriptor. If flushing, the file must
+ // be open for read/write. Returns true on successful ELF file load.
+ // |fd| is an open file descriptor for the shared object.
+ bool Load();
+
+ // Write ELF file changes.
+ void Flush();
+
+ // If set, pad rather than shrink .rel.dyn. Primarily for debugging,
+ // allows packing to be checked without affecting load addresses.
+ bool is_padding_rel_dyn_;
+
+ // File descriptor opened on the shared object.
+ int fd_;
+
+ // Libelf handle, assigned by Load().
+ Elf* elf_;
+
+ // Sections that we manipulate, assigned by Load().
+ Elf_Scn* rel_dyn_section_;
+ Elf_Scn* dynamic_section_;
+ Elf_Scn* android_rel_dyn_section_;
+};
+
+} // namespace relocation_packer
+
+#endif // TOOLS_RELOCATION_PACKER_SRC_ELF_FILE_H_
diff --git a/tools/relocation_packer/src/elf_file_unittest.cc b/tools/relocation_packer/src/elf_file_unittest.cc
new file mode 100644
index 0000000..d84928e
--- /dev/null
+++ b/tools/relocation_packer/src/elf_file_unittest.cc
@@ -0,0 +1,151 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "elf_file.h"
+
+#include <limits.h>
+#include <stdio.h>
+#include <unistd.h>
+#include <string>
+#include <vector>
+#include "debug.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Macro stringification.
+// https://gcc.gnu.org/onlinedocs/cpp/Stringification.html
+#define XSTR(S) STR(S)
+#define STR(S) #S
+
+namespace {
+
+void GetDataFilePath(const char* name, std::string* path) {
+ std::string data_dir;
+
+ const char* bindir = getenv("bindir");
+ if (bindir) {
+ data_dir = std::string(bindir);
+ } else {
+ // Test data is in the gyp INTERMEDIATE_DIR subdirectory of the directory
+ // that contains the current binary.
+ char path[PATH_MAX];
+ memset(path, 0, sizeof(path));
+ ASSERT_NE(-1, readlink("/proc/self/exe", path, sizeof(path) - 1));
+
+ data_dir = std::string(path);
+ size_t pos = data_dir.rfind('/');
+ ASSERT_NE(std::string::npos, pos);
+
+ data_dir.erase(pos + 1);
+ data_dir += std::string(XSTR(INTERMEDIATE_DIR));
+ }
+
+ *path = data_dir + "/" + name;
+}
+
+void OpenRelocsTestFile(const char* name, FILE** stream) {
+ std::string path;
+ GetDataFilePath(name, &path);
+
+ FILE* testfile = fopen(path.c_str(), "rb");
+ ASSERT_FALSE(testfile == NULL);
+
+ FILE* temporary = tmpfile();
+ ASSERT_FALSE(temporary == NULL);
+
+ static const size_t buffer_size = 4096;
+ unsigned char buffer[buffer_size];
+
+ size_t bytes;
+ do {
+ bytes = fread(buffer, 1, sizeof(buffer), testfile);
+ ASSERT_EQ(bytes, fwrite(buffer, 1, bytes, temporary));
+ } while (bytes > 0);
+
+ ASSERT_EQ(0, fclose(testfile));
+ ASSERT_EQ(0, fseek(temporary, 0, SEEK_SET));
+ ASSERT_EQ(0, lseek(fileno(temporary), 0, SEEK_SET));
+
+ *stream = temporary;
+}
+
+void OpenRelocsTestFiles(FILE** relocs_so, FILE** packed_relocs_so) {
+ OpenRelocsTestFile("elf_file_unittest_relocs.so", relocs_so);
+ OpenRelocsTestFile("elf_file_unittest_relocs_packed.so", packed_relocs_so);
+}
+
+void CloseRelocsTestFile(FILE* temporary) {
+ fclose(temporary);
+}
+
+void CloseRelocsTestFiles(FILE* relocs_so, FILE* packed_relocs_so) {
+ CloseRelocsTestFile(relocs_so);
+ CloseRelocsTestFile(packed_relocs_so);
+}
+
+void CheckFileContentsEqual(FILE* first, FILE* second) {
+ ASSERT_EQ(0, fseek(first, 0, SEEK_SET));
+ ASSERT_EQ(0, fseek(second, 0, SEEK_SET));
+
+ static const size_t buffer_size = 4096;
+ unsigned char first_buffer[buffer_size];
+ unsigned char second_buffer[buffer_size];
+
+ do {
+ size_t first_read = fread(first_buffer, 1, sizeof(first_buffer), first);
+ size_t second_read = fread(second_buffer, 1, sizeof(second_buffer), second);
+
+ EXPECT_EQ(first_read, second_read);
+ EXPECT_EQ(0, memcmp(first_buffer, second_buffer, first_read));
+ } while (!feof(first) && !feof(second));
+
+ EXPECT_TRUE(feof(first) && feof(second));
+}
+
+} // namespace
+
+namespace relocation_packer {
+
+TEST(ElfFile, PackRelocations) {
+ ASSERT_NE(EV_NONE, elf_version(EV_CURRENT));
+
+ FILE* relocs_so = NULL;
+ FILE* packed_relocs_so = NULL;
+ OpenRelocsTestFiles(&relocs_so, &packed_relocs_so);
+ if (HasFatalFailure())
+ return;
+
+ ElfFile elf_file(fileno(relocs_so));
+
+ // Ensure unpacking fails (not packed).
+ EXPECT_FALSE(elf_file.UnpackRelocations());
+
+ // Pack relocations, and check files are now identical.
+ EXPECT_TRUE(elf_file.PackRelocations());
+ CheckFileContentsEqual(relocs_so, packed_relocs_so);
+
+ CloseRelocsTestFiles(relocs_so, packed_relocs_so);
+}
+
+TEST(ElfFile, UnpackRelocations) {
+ ASSERT_NE(EV_NONE, elf_version(EV_CURRENT));
+
+ FILE* relocs_so = NULL;
+ FILE* packed_relocs_so = NULL;
+ OpenRelocsTestFiles(&relocs_so, &packed_relocs_so);
+ if (HasFatalFailure())
+ return;
+
+ ElfFile elf_file(fileno(packed_relocs_so));
+
+ // Ensure packing fails (already packed).
+ EXPECT_FALSE(elf_file.PackRelocations());
+
+ // Unpack golden relocations, and check files are now identical.
+ EXPECT_TRUE(elf_file.UnpackRelocations());
+ CheckFileContentsEqual(packed_relocs_so, relocs_so);
+
+ CloseRelocsTestFiles(relocs_so, packed_relocs_so);
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/leb128.cc b/tools/relocation_packer/src/leb128.cc
new file mode 100644
index 0000000..40b0133
--- /dev/null
+++ b/tools/relocation_packer/src/leb128.cc
@@ -0,0 +1,55 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// TODO(simonb): Extend for 64-bit target libraries.
+
+#include "leb128.h"
+
+#include <stdint.h>
+#include <vector>
+
+namespace relocation_packer {
+
+// Add a single value to the encoding. Values are encoded with variable
+// length. The least significant 7 bits of each byte hold 7 bits of data,
+// and the most significant bit is set on each byte except the last.
+void Leb128Encoder::Enqueue(uint32_t value) {
+ while (value > 127) {
+ encoding_.push_back((1 << 7) | (value & 127));
+ value >>= 7;
+ }
+ encoding_.push_back(value);
+}
+
+// Add a vector of values to the encoding.
+void Leb128Encoder::EnqueueAll(const std::vector<uint32_t>& values) {
+ for (size_t i = 0; i < values.size(); ++i)
+ Enqueue(values[i]);
+}
+
+// Decode and retrieve a single value from the encoding. Read forwards until
+// a byte without its most significant bit is found, then read the 7 bit
+// fields of the bytes spanned to re-form the value.
+uint32_t Leb128Decoder::Dequeue() {
+ size_t extent = cursor_;
+ while (encoding_[extent] >> 7)
+ extent++;
+
+ uint32_t value = 0;
+ for (size_t i = extent; i > cursor_; --i) {
+ value = (value << 7) | (encoding_[i] & 127);
+ }
+ value = (value << 7) | (encoding_[cursor_] & 127);
+
+ cursor_ = extent + 1;
+ return value;
+}
+
+// Decode and retrieve all remaining values from the encoding.
+void Leb128Decoder::DequeueAll(std::vector<uint32_t>* values) {
+ while (cursor_ < encoding_.size())
+ values->push_back(Dequeue());
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/leb128.h b/tools/relocation_packer/src/leb128.h
new file mode 100644
index 0000000..7ae5710
--- /dev/null
+++ b/tools/relocation_packer/src/leb128.h
@@ -0,0 +1,67 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// LEB128 encoder and decoder for packed R_ARM_RELATIVE relocations.
+//
+// Run-length encoded R_ARM_RELATIVE relocations consist of a large number
+// of pairs of relatively small positive integer values. Encoding these as
+// LEB128 saves space.
+//
+// For more on LEB128 see http://en.wikipedia.org/wiki/LEB128.
+
+#ifndef TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
+#define TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
+
+#include <stdint.h>
+#include <unistd.h>
+#include <vector>
+
+namespace relocation_packer {
+
+// Encode packed words as a LEB128 byte stream.
+class Leb128Encoder {
+ public:
+ // Add a value to the encoding stream.
+ // |value| is the unsigned int to add.
+ void Enqueue(uint32_t value);
+
+ // Add a vector of values to the encoding stream.
+ // |values| is the vector of unsigned ints to add.
+ void EnqueueAll(const std::vector<uint32_t>& values);
+
+ // Retrieve the encoded representation of the values.
+ // |encoding| is the returned vector of encoded data.
+ void GetEncoding(std::vector<uint8_t>* encoding) { *encoding = encoding_; }
+
+ private:
+ // Growable vector holding the encoded LEB128 stream.
+ std::vector<uint8_t> encoding_;
+};
+
+// Decode a LEB128 byte stream to produce packed words.
+class Leb128Decoder {
+ public:
+ // Create a new decoder for the given encoded stream.
+ // |encoding| is the vector of encoded data.
+ explicit Leb128Decoder(const std::vector<uint8_t>& encoding)
+ : encoding_(encoding), cursor_(0) { }
+
+ // Retrieve the next value from the encoded stream.
+ uint32_t Dequeue();
+
+ // Retrieve all remaining values from the encoded stream.
+ // |values| is the vector of decoded data.
+ void DequeueAll(std::vector<uint32_t>* values);
+
+ private:
+ // Encoded LEB128 stream.
+ std::vector<uint8_t> encoding_;
+
+ // Cursor indicating the current stream retrieval point.
+ size_t cursor_;
+};
+
+} // namespace relocation_packer
+
+#endif // TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
diff --git a/tools/relocation_packer/src/leb128_unittest.cc b/tools/relocation_packer/src/leb128_unittest.cc
new file mode 100644
index 0000000..62cf2f06
--- /dev/null
+++ b/tools/relocation_packer/src/leb128_unittest.cc
@@ -0,0 +1,92 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "leb128.h"
+
+#include <vector>
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace relocation_packer {
+
+TEST(Leb128, Encoder) {
+ std::vector<uint32_t> values;
+ values.push_back(624485u);
+ values.push_back(0u);
+ values.push_back(1u);
+ values.push_back(127u);
+ values.push_back(128u);
+
+ Leb128Encoder encoder;
+ encoder.EnqueueAll(values);
+
+ std::vector<uint8_t> encoding;
+ encoder.GetEncoding(&encoding);
+
+ EXPECT_EQ(8u, encoding.size());
+ // 624485
+ EXPECT_EQ(0xe5, encoding[0]);
+ EXPECT_EQ(0x8e, encoding[1]);
+ EXPECT_EQ(0x26, encoding[2]);
+ // 0
+ EXPECT_EQ(0x00, encoding[3]);
+ // 1
+ EXPECT_EQ(0x01, encoding[4]);
+ // 127
+ EXPECT_EQ(0x7f, encoding[5]);
+ // 128
+ EXPECT_EQ(0x80, encoding[6]);
+ EXPECT_EQ(0x01, encoding[7]);
+
+ encoder.Enqueue(4294967295u);
+
+ encoding.clear();
+ encoder.GetEncoding(&encoding);
+
+ EXPECT_EQ(13u, encoding.size());
+ // 4294967295
+ EXPECT_EQ(0xff, encoding[8]);
+ EXPECT_EQ(0xff, encoding[9]);
+ EXPECT_EQ(0xff, encoding[10]);
+ EXPECT_EQ(0xff, encoding[11]);
+ EXPECT_EQ(0x0f, encoding[12]);
+}
+
+TEST(Leb128, Decoder) {
+ std::vector<uint8_t> encoding;
+ // 624485
+ encoding.push_back(0xe5);
+ encoding.push_back(0x8e);
+ encoding.push_back(0x26);
+ // 0
+ encoding.push_back(0x00);
+ // 1
+ encoding.push_back(0x01);
+ // 127
+ encoding.push_back(0x7f);
+ // 128
+ encoding.push_back(0x80);
+ encoding.push_back(0x01);
+ // 4294967295
+ encoding.push_back(0xff);
+ encoding.push_back(0xff);
+ encoding.push_back(0xff);
+ encoding.push_back(0xff);
+ encoding.push_back(0x0f);
+
+ Leb128Decoder decoder(encoding);
+
+ EXPECT_EQ(624485u, decoder.Dequeue());
+
+ std::vector<uint32_t> dequeued;
+ decoder.DequeueAll(&dequeued);
+
+ EXPECT_EQ(5u, dequeued.size());
+ EXPECT_EQ(0u, dequeued[0]);
+ EXPECT_EQ(1u, dequeued[1]);
+ EXPECT_EQ(127u, dequeued[2]);
+ EXPECT_EQ(128u, dequeued[3]);
+ EXPECT_EQ(4294967295u, dequeued[4]);
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/main.cc b/tools/relocation_packer/src/main.cc
new file mode 100644
index 0000000..4bc09b6e
--- /dev/null
+++ b/tools/relocation_packer/src/main.cc
@@ -0,0 +1,139 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Tool to pack and unpack R_ARM_RELATIVE relocations in a shared library.
+//
+// Packing removes R_ARM_RELATIVE relocations from .rel.dyn and writes them
+// in a more compact form to .android.rel.dyn. Unpacking does the reverse.
+//
+// Invoke with -v to trace actions taken when packing or unpacking.
+// Invoke with -p to pad removed relocations with R_ARM_NONE. Suppresses
+// shrinking of .rel.dyn.
+// See PrintUsage() below for full usage details.
+//
+// NOTE: Breaks with libelf 0.152, which is buggy. libelf 0.158 works.
+
+// TODO(simonb): Extend for 64-bit target libraries.
+
+#include <errno.h>
+#include <fcntl.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <string>
+
+#include "debug.h"
+#include "elf_file.h"
+#include "libelf.h"
+#include "packer.h"
+
+void PrintUsage(const char* argv0) {
+ std::string temporary = argv0;
+ const size_t last_slash = temporary.find_last_of("/");
+ if (last_slash != temporary.npos) {
+ temporary.erase(0, last_slash + 1);
+ }
+ const char* basename = temporary.c_str();
+
+ printf(
+ "Usage: %s [-u] [-v] [-p] file\n"
+ "Pack or unpack R_ARM_RELATIVE relocations in a shared library.\n\n"
+ " -u, --unpack unpack previously packed R_ARM_RELATIVE relocations\n"
+ " -v, --verbose trace object file modifications (for debugging)\n"
+ " -p, --pad do not shrink .rel.dyn, but pad (for debugging)\n\n"
+ "Extracts R_ARM_RELATIVE relocations from the .rel.dyn section, packs\n"
+ "them into a more compact format, and stores the packed relocations in\n"
+ ".android.rel.dyn. Expands .android.rel.dyn to hold the packed data,\n"
+ "and shrinks .rel.dyn by the amount of unpacked data removed from it.\n\n"
+ "Before being packed, a shared library needs to be prepared by adding\n"
+ "a null .android.rel.dyn section. A complete packing process is:\n\n"
+ " echo -n 'NULL' >/tmp/small\n"
+ " arm-linux-gnueabi-objcopy \\\n"
+ " --add-section .android.rel.dyn=/tmp/small \\\n"
+ " libchrome.<version>.so\n"
+ " rm /tmp/small\n"
+ " %s libchrome.<version>.so\n\n"
+ "To unpack and restore the shared library to its original state:\n\n"
+ " %s -u libchrome.<version>.so\n"
+ " arm-linux-gnueabi-objcopy \\\n"
+ " --remove-section=.android.rel.dyn libchrome.<version>.so\n\n"
+ "Debug sections are not handled, so packing should not be used on\n"
+ "shared libraries compiled for debugging or otherwise unstripped.\n",
+ basename, basename, basename);
+}
+
+int main(int argc, char* argv[]) {
+ bool is_unpacking = false;
+ bool is_verbose = false;
+ bool is_padding = false;
+
+ static const option options[] = {
+ {"unpack", 0, 0, 'u'}, {"verbose", 0, 0, 'v'}, {"pad", 0, 0, 'p'},
+ {"help", 0, 0, 'h'}, {NULL, 0, 0, 0}
+ };
+ bool has_options = true;
+ while (has_options) {
+ int c = getopt_long(argc, argv, "uvph", options, NULL);
+ switch (c) {
+ case 'u':
+ is_unpacking = true;
+ break;
+ case 'v':
+ is_verbose = true;
+ break;
+ case 'p':
+ is_padding = true;
+ break;
+ case 'h':
+ PrintUsage(argv[0]);
+ return 0;
+ case '?':
+ LOG("Try '%s --help' for more information.\n", argv[0]);
+ return 1;
+ case -1:
+ has_options = false;
+ break;
+ default:
+ NOTREACHED();
+ }
+ }
+ if (optind != argc - 1) {
+ LOG("Try '%s --help' for more information.\n", argv[0]);
+ return 1;
+ }
+
+ if (elf_version(EV_CURRENT) == EV_NONE) {
+ LOG("WARNING: Elf Library is out of date!\n");
+ }
+
+ const char* file = argv[argc - 1];
+ const int fd = open(file, O_RDWR);
+ if (fd == -1) {
+ LOG("%s: %s\n", file, strerror(errno));
+ return 1;
+ }
+
+ relocation_packer::Logger::SetVerbose(is_verbose);
+
+ relocation_packer::ElfFile elf_file(fd);
+ elf_file.SetPadding(is_padding);
+
+ bool status;
+ if (is_unpacking)
+ status = elf_file.UnpackRelocations();
+ else
+ status = elf_file.PackRelocations();
+
+ close(fd);
+
+ if (!status) {
+ LOG("ERROR: %s: failed to pack/unpack file\n", file);
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/tools/relocation_packer/src/packer.cc b/tools/relocation_packer/src/packer.cc
new file mode 100644
index 0000000..f856a9b
--- /dev/null
+++ b/tools/relocation_packer/src/packer.cc
@@ -0,0 +1,69 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// TODO(simonb): Extend for 64-bit target libraries.
+
+#include "packer.h"
+
+#include <string.h>
+#include <string>
+#include <vector>
+
+#include "debug.h"
+#include "leb128.h"
+#include "run_length_encoder.h"
+
+namespace relocation_packer {
+
+// Pack R_ARM_RELATIVE relocations into a run-length encoded packed
+// representation.
+void RelocationPacker::PackRelativeRelocations(
+ const std::vector<Elf32_Rel>& relocations,
+ std::vector<uint8_t>* packed) {
+
+ // Run-length encode.
+ std::vector<Elf32_Word> packed_words;
+ RelocationRunLengthCodec codec;
+ codec.Encode(relocations, &packed_words);
+
+ // If insufficient data to run-length encode, do nothing.
+ if (packed_words.empty())
+ return;
+
+ // LEB128 encode, with "APR1" prefix.
+ Leb128Encoder encoder;
+ encoder.Enqueue('A');
+ encoder.Enqueue('P');
+ encoder.Enqueue('R');
+ encoder.Enqueue('1');
+ encoder.EnqueueAll(packed_words);
+
+ encoder.GetEncoding(packed);
+
+ // Pad packed to a whole number of words. This padding will decode as
+ // LEB128 zeroes. Run-length decoding ignores it because encoding
+ // embeds the pairs count in the stream itself.
+ while (packed->size() % sizeof(uint32_t))
+ packed->push_back(0);
+}
+
+// Unpack R_ARM_RELATIVE relocations from a run-length encoded packed
+// representation.
+void RelocationPacker::UnpackRelativeRelocations(
+ const std::vector<uint8_t>& packed,
+ std::vector<Elf32_Rel>* relocations) {
+
+ // LEB128 decode, after checking and stripping "APR1" prefix.
+ std::vector<Elf32_Word> packed_words;
+ Leb128Decoder decoder(packed);
+ CHECK(decoder.Dequeue() == 'A' && decoder.Dequeue() == 'P' &&
+ decoder.Dequeue() == 'R' && decoder.Dequeue() == '1');
+ decoder.DequeueAll(&packed_words);
+
+ // Run-length decode.
+ RelocationRunLengthCodec codec;
+ codec.Decode(packed_words, relocations);
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/packer.h b/tools/relocation_packer/src/packer.h
new file mode 100644
index 0000000..f0342cd
--- /dev/null
+++ b/tools/relocation_packer/src/packer.h
@@ -0,0 +1,51 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Pack R_ARM_RELATIVE relocations into a more compact form.
+//
+// Applies two packing strategies. The first is run-length encoding, which
+// turns a large set of R_ARM_RELATIVE relocations into a much smaller set
+// of delta-count pairs, prefixed with a two-word header comprising the
+// count of pairs and the initial relocation offset. The second is LEB128
+// encoding, which compacts the result of run-length encoding.
+//
+// Once packed, data is prefixed by an identifier that allows for any later
+// versioning of packing strategies.
+//
+// A complete packed stream might look something like:
+//
+// "APR1" pairs init_offset count1 delta1 count2 delta2 ...
+// 41505231 f2b003 b08ac716 e001 04 01 10 ...
+
+#ifndef TOOLS_RELOCATION_PACKER_SRC_PACKER_H_
+#define TOOLS_RELOCATION_PACKER_SRC_PACKER_H_
+
+#include <stdint.h>
+#include <string.h>
+#include <vector>
+
+#include "elf.h"
+
+namespace relocation_packer {
+
+// A RelocationPacker packs vectors of R_ARM_RELATIVE relocations into more
+// compact forms, and unpacks them to reproduce the pre-packed data.
+class RelocationPacker {
+ public:
+ // Pack R_ARM_RELATIVE relocations into a more compact form.
+ // |relocations| is a vector of R_ARM_RELATIVE relocation structs.
+ // |packed| is the vector of packed bytes into which relocations are packed.
+ static void PackRelativeRelocations(const std::vector<Elf32_Rel>& relocations,
+ std::vector<uint8_t>* packed);
+
+ // Unpack R_ARM_RELATIVE relocations from their more compact form.
+ // |packed| is the vector of packed relocations.
+ // |relocations| is a vector of unpacked R_ARM_RELATIVE relocation structs.
+ static void UnpackRelativeRelocations(const std::vector<uint8_t>& packed,
+ std::vector<Elf32_Rel>* relocations);
+};
+
+} // namespace relocation_packer
+
+#endif // TOOLS_RELOCATION_PACKER_SRC_PACKER_H_
diff --git a/tools/relocation_packer/src/packer_unittest.cc b/tools/relocation_packer/src/packer_unittest.cc
new file mode 100644
index 0000000..c917a392
--- /dev/null
+++ b/tools/relocation_packer/src/packer_unittest.cc
@@ -0,0 +1,114 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "packer.h"
+
+#include <vector>
+#include "elf.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+void AddRelocation(Elf32_Addr addr, std::vector<Elf32_Rel>* relocations) {
+ Elf32_Rel relocation = {addr, R_ARM_RELATIVE};
+ relocations->push_back(relocation);
+}
+
+bool CheckRelocation(Elf32_Addr addr, const Elf32_Rel& relocation) {
+ return relocation.r_offset == addr && relocation.r_info == R_ARM_RELATIVE;
+}
+
+} // namespace
+
+namespace relocation_packer {
+
+TEST(Packer, Pack) {
+ std::vector<Elf32_Rel> relocations;
+ std::vector<uint8_t> packed;
+
+ RelocationPacker packer;
+
+ // Initial relocation.
+ AddRelocation(0xd1ce0000, &relocations);
+ // Two more relocations, 4 byte deltas.
+ AddRelocation(0xd1ce0004, &relocations);
+ AddRelocation(0xd1ce0008, &relocations);
+ // Three more relocations, 8 byte deltas.
+ AddRelocation(0xd1ce0010, &relocations);
+ AddRelocation(0xd1ce0018, &relocations);
+ AddRelocation(0xd1ce0020, &relocations);
+
+ packed.clear();
+ packer.PackRelativeRelocations(relocations, &packed);
+
+ EXPECT_EQ(16u, packed.size());
+ // Identifier.
+ EXPECT_EQ('A', packed[0]);
+ EXPECT_EQ('P', packed[1]);
+ EXPECT_EQ('R', packed[2]);
+ EXPECT_EQ('1', packed[3]);
+ // Count-delta pairs count.
+ EXPECT_EQ(2u, packed[4]);
+ // 0xd1ce0000
+ EXPECT_EQ(128u, packed[5]);
+ EXPECT_EQ(128u, packed[6]);
+ EXPECT_EQ(184u, packed[7]);
+ EXPECT_EQ(142u, packed[8]);
+ EXPECT_EQ(13u, packed[9]);
+ // Run of two relocations, 4 byte deltas.
+ EXPECT_EQ(2u, packed[10]);
+ EXPECT_EQ(4u, packed[11]);
+ // Run of three relocations, 8 byte deltas.
+ EXPECT_EQ(3u, packed[12]);
+ EXPECT_EQ(8u, packed[13]);
+ // Padding.
+ EXPECT_EQ(0u, packed[14]);
+ EXPECT_EQ(0u, packed[15]);
+}
+
+TEST(Packer, Unpack) {
+ std::vector<uint8_t> packed;
+ std::vector<Elf32_Rel> relocations;
+
+ RelocationPacker packer;
+
+ // Identifier.
+ packed.push_back('A');
+ packed.push_back('P');
+ packed.push_back('R');
+ packed.push_back('1');
+ // Count-delta pairs count.
+ packed.push_back(2u);
+ // 0xd1ce0000
+ packed.push_back(128u);
+ packed.push_back(128u);
+ packed.push_back(184u);
+ packed.push_back(142u);
+ packed.push_back(13u);
+ // Run of two relocations, 4 byte deltas.
+ packed.push_back(2u);
+ packed.push_back(4u);
+ // Run of three relocations, 8 byte deltas.
+ packed.push_back(3u);
+ packed.push_back(8u);
+ // Padding.
+ packed.push_back(0u);
+ packed.push_back(0u);
+
+ relocations.clear();
+ packer.UnpackRelativeRelocations(packed, &relocations);
+
+ EXPECT_EQ(6u, relocations.size());
+ // Initial relocation.
+ EXPECT_TRUE(CheckRelocation(0xd1ce0000, relocations[0]));
+ // Two relocations, 4 byte deltas.
+ EXPECT_TRUE(CheckRelocation(0xd1ce0004, relocations[1]));
+ EXPECT_TRUE(CheckRelocation(0xd1ce0008, relocations[2]));
+ // Three relocations, 8 byte deltas.
+ EXPECT_TRUE(CheckRelocation(0xd1ce0010, relocations[3]));
+ EXPECT_TRUE(CheckRelocation(0xd1ce0018, relocations[4]));
+ EXPECT_TRUE(CheckRelocation(0xd1ce0020, relocations[5]));
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/run_all_unittests.cc b/tools/relocation_packer/src/run_all_unittests.cc
new file mode 100644
index 0000000..4122be18
--- /dev/null
+++ b/tools/relocation_packer/src/run_all_unittests.cc
@@ -0,0 +1,10 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+int main(int argc, char** argv) {
+ testing::InitGoogleTest(&argc, argv);
+ return RUN_ALL_TESTS();
+}
diff --git a/tools/relocation_packer/src/run_length_encoder.cc b/tools/relocation_packer/src/run_length_encoder.cc
new file mode 100644
index 0000000..78949a9e
--- /dev/null
+++ b/tools/relocation_packer/src/run_length_encoder.cc
@@ -0,0 +1,139 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// TODO(simonb): Extend for 64-bit target libraries.
+
+#include "run_length_encoder.h"
+
+#include <string.h>
+#include <string>
+#include <vector>
+
+#include "debug.h"
+
+namespace relocation_packer {
+
+namespace {
+
+// Generate a vector of deltas between the r_offset fields of adjacent
+// R_ARM_RELATIVE relocations.
+void GetDeltas(const std::vector<Elf32_Rel>& relocations,
+ std::vector<Elf32_Addr>* deltas) {
+ CHECK(relocations.size() >= 2);
+
+ for (size_t i = 0; i < relocations.size() - 1; ++i) {
+ const Elf32_Addr first = relocations[i].r_offset;
+ const Elf32_Addr second = relocations[i + 1].r_offset;
+ // Requires that offsets are 'strictly increasing'. The packing
+ // algorithm fails if this does not hold.
+ CHECK(second > first);
+ deltas->push_back(second - first);
+ }
+}
+
+// Condense a set of r_offset deltas into a run-length encoded packing.
+// Represented as count-delta pairs, where count is the run length and
+// delta the common difference between adjacent r_offsets.
+void Condense(const std::vector<Elf32_Addr>& deltas,
+ std::vector<Elf32_Word>* packed) {
+ CHECK(!deltas.empty());
+ size_t count = 0;
+ Elf32_Addr current = deltas[0];
+
+ // Identify spans of identically valued deltas.
+ for (size_t i = 0; i < deltas.size(); ++i) {
+ const Elf32_Addr delta = deltas[i];
+ if (delta == current) {
+ count++;
+ } else {
+ // We reached the end of a span of identically valued deltas.
+ packed->push_back(count);
+ packed->push_back(current);
+ current = delta;
+ count = 1;
+ }
+ }
+
+ // Write the final span.
+ packed->push_back(count);
+ packed->push_back(current);
+}
+
+// Uncondense a set of r_offset deltas from a run-length encoded packing.
+// The initial address for uncondensing, the start index for the first
+// condensed slot in packed, and the count of pairs are provided.
+void Uncondense(Elf32_Addr addr,
+ const std::vector<Elf32_Word>& packed,
+ size_t start_index,
+ size_t end_index,
+ std::vector<Elf32_Rel>* relocations) {
+ // The first relocation is just one created from the initial address.
+ const Elf32_Rel initial = {addr, R_ARM_RELATIVE};
+ relocations->push_back(initial);
+
+ // Read each count and delta pair, beginning at the start index and
+ // finishing at the end index.
+ for (size_t i = start_index; i < end_index; i += 2) {
+ size_t count = packed[i];
+ const Elf32_Addr delta = packed[i + 1];
+ CHECK(count > 0 && delta > 0);
+
+ // Generate relocations for this count and delta pair.
+ while (count) {
+ addr += delta;
+ const Elf32_Rel relocation = {addr, R_ARM_RELATIVE};
+ relocations->push_back(relocation);
+ count--;
+ }
+ }
+}
+
+} // namespace
+
+// Encode R_ARM_RELATIVE relocations into a run-length encoded (packed)
+// representation.
+void RelocationRunLengthCodec::Encode(const std::vector<Elf32_Rel>& relocations,
+ std::vector<Elf32_Word>* packed) {
+ // If we have zero or one relocation only then there is no packing
+ // possible; a run-length encoding needs a run.
+ if (relocations.size() < 2)
+ return;
+
+ std::vector<Elf32_Addr> deltas;
+ GetDeltas(relocations, &deltas);
+
+ // Reserve space for the element count.
+ packed->push_back(0);
+
+ // Initialize the packed data with the first offset, then follow up with
+ // the condensed deltas vector.
+ packed->push_back(relocations[0].r_offset);
+ Condense(deltas, packed);
+
+ // Fill in the packed pair count.
+ packed->at(0) = (packed->size() - 2) >> 1;
+}
+
+// Decode R_ARM_RELATIVE reloctions from a run-length encoded (packed)
+// representation.
+void RelocationRunLengthCodec::Decode(const std::vector<Elf32_Word>& packed,
+ std::vector<Elf32_Rel>* relocations) {
+ // We need at least one packed pair after the packed pair count to be
+ // able to unpack.
+ if (packed.size() < 3)
+ return;
+
+ // Ensure that the packed data offers enough pairs. There may be zero
+ // padding on it that we ignore.
+ CHECK(packed[0] <= (packed.size() - 2) >> 1);
+
+ // The first packed vector element is the pairs count and the second the
+ // initial address. Start uncondensing pairs at the third, and finish
+ // at the end of the pairs data.
+ const size_t pairs_count = packed[0];
+ const Elf32_Addr addr = packed[1];
+ Uncondense(addr, packed, 2, 2 + (pairs_count << 1), relocations);
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/src/run_length_encoder.h b/tools/relocation_packer/src/run_length_encoder.h
new file mode 100644
index 0000000..85f6740
--- /dev/null
+++ b/tools/relocation_packer/src/run_length_encoder.h
@@ -0,0 +1,81 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Run-length encode and decode R_ARM_RELATIVE relocations.
+//
+// R_ARM_RELATIVE relocations are the bulk of dynamic relocations (the
+// .rel.dyn section) in libchrome<version>.so, and the ELF standard
+// representation of them is wasteful.
+//
+// A relocation is 8 bytes (16 bytes on 64 bit plaforms), split into offset
+// and info fields. Offsets strictly increase, and each is commonly a
+// few bytes different from its predecessor. There are long runs where
+// the difference does not change. The info field is always 0x17. Example,
+// from 'readelf -x4 libchrome.<version>.so':
+//
+// offset info offset info
+// 808fef01 17000000 848fef01 17000000 ................
+// 888fef01 17000000 8c8fef01 17000000 ................
+// 908fef01 17000000 948fef01 17000000 ................
+//
+// Run length encoding packs this data more efficiently, by representing it
+// as a delta and a count of entries each differing from its predecessor
+// by this delta. The above can be represented as a start address followed
+// by an encoded count of 6 and offset difference of 4:
+//
+// start count diff
+// 808fef01 00000006 00000004
+//
+// Because R_ARM_RELATIVE relocation offsets strictly increase, the complete
+// set of R_ARM_RELATIVE relocations in libchrome.<version>.so can be
+// represented by a single start address followed by one or more difference
+// and count encoded word pairs:
+//
+// start run1 count run1 diff run2 count run2 diff
+// 808fef01 00000006 00000004 00000010 00000008 ...
+//
+// Decoding regenerates R_ARM_RELATIVE relocations beginning at address
+// 'start' and for each encoded run, incrementing the address by 'difference'
+// for 'count' iterations and emitting a new R_ARM_RELATIVE relocation.
+//
+// Once encoded, data is prefixed by a single word count of packed delta and
+// count pairs. A final run-length encoded R_ARM_RELATIVE relocations vector
+// might therefore look something like:
+//
+// pairs start run 1 run 2 ... run 15
+// 0000000f 808fef01 00000006 00000004 00000010 00000008 ...
+// Interpreted as:
+// pairs=15 start=.. count=6,delta=4 count=16,delta=8
+
+#ifndef TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
+#define TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
+
+#include <stdint.h>
+#include <string.h>
+#include <vector>
+
+#include "elf.h"
+
+namespace relocation_packer {
+
+// A RelocationRunLengthCodec packs vectors of R_ARM_RELATIVE relocations
+// into more compact forms, and unpacks them to reproduce the pre-packed data.
+class RelocationRunLengthCodec {
+ public:
+ // Encode R_ARM_RELATIVE relocations into a more compact form.
+ // |relocations| is a vector of R_ARM_RELATIVE relocation structs.
+ // |packed| is the vector of packed words into which relocations are packed.
+ static void Encode(const std::vector<Elf32_Rel>& relocations,
+ std::vector<Elf32_Word>* packed);
+
+ // Decode R_ARM_RELATIVE relocations from their more compact form.
+ // |packed| is the vector of packed relocations.
+ // |relocations| is a vector of unpacked R_ARM_RELATIVE relocation structs.
+ static void Decode(const std::vector<Elf32_Word>& packed,
+ std::vector<Elf32_Rel>* relocations);
+};
+
+} // namespace relocation_packer
+
+#endif // TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
diff --git a/tools/relocation_packer/src/run_length_encoder_unittest.cc b/tools/relocation_packer/src/run_length_encoder_unittest.cc
new file mode 100644
index 0000000..d632e88
--- /dev/null
+++ b/tools/relocation_packer/src/run_length_encoder_unittest.cc
@@ -0,0 +1,119 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "run_length_encoder.h"
+
+#include <vector>
+#include "elf.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+void AddRelocation(Elf32_Addr addr, std::vector<Elf32_Rel>* relocations) {
+ Elf32_Rel relocation = {addr, R_ARM_RELATIVE};
+ relocations->push_back(relocation);
+}
+
+bool CheckRelocation(Elf32_Addr addr, const Elf32_Rel& relocation) {
+ return relocation.r_offset == addr && relocation.r_info == R_ARM_RELATIVE;
+}
+
+} // namespace
+
+namespace relocation_packer {
+
+TEST(Rle, Encode) {
+ std::vector<Elf32_Rel> relocations;
+ std::vector<Elf32_Word> packed;
+
+ RelocationRunLengthCodec codec;
+
+ packed.clear();
+ codec.Encode(relocations, &packed);
+
+ EXPECT_EQ(0u, packed.size());
+
+ // Add one relocation (insufficient data to encode).
+ AddRelocation(0xf00d0000, &relocations);
+
+ packed.clear();
+ codec.Encode(relocations, &packed);
+
+ EXPECT_EQ(0u, packed.size());
+
+ // Add a second relocation, 4 byte delta (minimum data to encode).
+ AddRelocation(0xf00d0004, &relocations);
+
+ packed.clear();
+ codec.Encode(relocations, &packed);
+
+ EXPECT_EQ(4u, packed.size());
+ // One count-delta pair present.
+ EXPECT_EQ(1u, packed[0]);
+ // Initial relocation.
+ EXPECT_EQ(0xf00d0000, packed[1]);
+ // Run of a single relocation, 4 byte delta.
+ EXPECT_EQ(1u, packed[2]);
+ EXPECT_EQ(4u, packed[3]);
+
+ // Add a third relocation, 4 byte delta.
+ AddRelocation(0xf00d0008, &relocations);
+
+ // Add three more relocations, 8 byte deltas.
+ AddRelocation(0xf00d0010, &relocations);
+ AddRelocation(0xf00d0018, &relocations);
+ AddRelocation(0xf00d0020, &relocations);
+
+ packed.clear();
+ codec.Encode(relocations, &packed);
+
+ EXPECT_EQ(6u, packed.size());
+ // Two count-delta pairs present.
+ EXPECT_EQ(2u, packed[0]);
+ // Initial relocation.
+ EXPECT_EQ(0xf00d0000, packed[1]);
+ // Run of two relocations, 4 byte deltas.
+ EXPECT_EQ(2u, packed[2]);
+ EXPECT_EQ(4u, packed[3]);
+ // Run of three relocations, 8 byte deltas.
+ EXPECT_EQ(3u, packed[4]);
+ EXPECT_EQ(8u, packed[5]);
+}
+
+TEST(Rle, Decode) {
+ std::vector<Elf32_Word> packed;
+ std::vector<Elf32_Rel> relocations;
+
+ RelocationRunLengthCodec codec;
+ codec.Decode(packed, &relocations);
+
+ EXPECT_EQ(0u, relocations.size());
+
+ // Two count-delta pairs.
+ packed.push_back(2u);
+ // Initial relocation.
+ packed.push_back(0xc0de0000);
+ // Run of two relocations, 4 byte deltas.
+ packed.push_back(2u);
+ packed.push_back(4u);
+ // Run of three relocations, 8 byte deltas.
+ packed.push_back(3u);
+ packed.push_back(8u);
+
+ relocations.clear();
+ codec.Decode(packed, &relocations);
+
+ EXPECT_EQ(6u, relocations.size());
+ // Initial relocation.
+ EXPECT_TRUE(CheckRelocation(0xc0de0000, relocations[0]));
+ // Two relocations, 4 byte deltas.
+ EXPECT_TRUE(CheckRelocation(0xc0de0004, relocations[1]));
+ EXPECT_TRUE(CheckRelocation(0xc0de0008, relocations[2]));
+ // Three relocations, 8 byte deltas.
+ EXPECT_TRUE(CheckRelocation(0xc0de0010, relocations[3]));
+ EXPECT_TRUE(CheckRelocation(0xc0de0018, relocations[4]));
+ EXPECT_TRUE(CheckRelocation(0xc0de0020, relocations[5]));
+}
+
+} // namespace relocation_packer
diff --git a/tools/relocation_packer/test_data/elf_file_unittest_relocs.cc b/tools/relocation_packer/test_data/elf_file_unittest_relocs.cc
new file mode 100644
index 0000000..e6e9f6a
--- /dev/null
+++ b/tools/relocation_packer/test_data/elf_file_unittest_relocs.cc
@@ -0,0 +1,40 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Test data for packing/unpacking. When compiled, creates a run of
+// relative relocations.
+//
+// #!/bin/bash
+//
+// # Compile as an arm shared library.
+// /usr/bin/arm-linux-gnueabi-g++ -shared -o /tmp/testdata.so \
+// elf_file_unittest_relocs.cc
+//
+// # Add a new null .android.rel.dyn section, needed for packing.
+// echo 'NULL' >/tmp/small
+// /usr/bin/arm-linux-gnueabi-objcopy \
+// --add-section .android.rel.dyn=/tmp/small /tmp/testdata.so
+//
+// # Create packed and unpacked reference files.
+// packer="../../../out_android/Debug/relocation_packer"
+// cp /tmp/testdata.so elf_file_unittest_relocs_packed.so
+// $packer elf_file_unittest_relocs_packed.so
+// cp elf_file_unittest_relocs_packed.so elf_file_unittest_relocs.so
+// $packer -u elf_file_unittest_relocs.so
+//
+// # Clean up.
+// rm /tmp/testdata.so /tmp/small
+
+const int i = 0;
+
+const void* pointer_0 = &i;
+const void* pointer_1 = &i;
+const void* pointer_2 = &i;
+const void* pointer_3 = &i;
+const void* pointer_4 = &i;
+const void* pointer_5 = &i;
+const void* pointer_6 = &i;
+const void* pointer_7 = &i;
+const void* pointer_8 = &i;
+const void* pointer_9 = &i;
