Extend the crazy linker for arm64 packed relative relocations.

Add delta decoding for RELA relocations.  Add a signed LEB128
decoder, and move LEB128 helper classes into their own header file.

Select either run length or delta decoding depending on the signature
found in the packed relocations section.

BUG=385553

Review URL: https://codereview.chromium.org/477943002

Cr-Commit-Position: refs/heads/master@{#290542}
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@290542 0039d316-1c4b-4281-b951-d872f2087c98

7 files changed, 234 insertions, 108 deletions

diff --git a/third_party/android_crazy_linker/README.chromium b/third_party/android_crazy_linker/README.chromium
index ef5087d..4153da5 100644
--- a/third_party/android_crazy_linker/README.chromium
+++ b/third_party/android_crazy_linker/README.chromium
@@ -39,3 +39,5 @@ Local Modifications:
 - Speculative fix for crbug/397634.
 
 - Implement LEB128 decoding more efficiently.
+
+- Add support for unpacking relative relocations with addends, for arm64.
diff --git a/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.cpp b/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.cpp
index 33c385a..6b73e87 100644
--- a/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.cpp
+++ b/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.cpp
@@ -10,6 +10,7 @@
 #include "crazy_linker_elf_symbols.h"
 #include "crazy_linker_elf_view.h"
 #include "crazy_linker_error.h"
+#include "crazy_linker_leb128.h"
 #include "crazy_linker_system.h"
 #include "crazy_linker_util.h"
 #include "linker_phdr.h"
@@ -42,6 +43,8 @@
 #define R_ARM_COPY 20
 #define R_ARM_RELATIVE 23
 
+#define RELATIVE_RELOCATION_CODE R_ARM_RELATIVE
+
 #endif  // __arm__
 
 #ifdef __aarch64__
@@ -53,6 +56,8 @@
 #define R_AARCH64_JUMP_SLOT 1026
 #define R_AARCH64_RELATIVE 1027
 
+#define RELATIVE_RELOCATION_CODE R_AARCH64_RELATIVE
+
 #endif  // __aarch64__
 
 #ifdef __i386__
@@ -335,8 +340,8 @@ bool ElfRelocations::ApplyAll(const ElfSymbols* symbols,
       return false;
   }
 
-#ifdef __arm__
-  if (!ApplyArmPackedRelocs(error))
+#if defined(__arm__) || defined(__aarch64__)
+  if (!ApplyPackedRelocations(error))
     return false;
 #endif
 
@@ -356,58 +361,24 @@ bool ElfRelocations::ApplyAll(const ElfSymbols* symbols,
   return true;
 }
 
-#ifdef __arm__
+#if defined(__arm__) || defined(__aarch64__)
 
-void ElfRelocations::RegisterArmPackedRelocs(uint8_t* arm_packed_relocs) {
-  arm_packed_relocs_ = arm_packed_relocs;
+void ElfRelocations::RegisterPackedRelocations(uint8_t* packed_relocations) {
+  packed_relocations_ = packed_relocations;
 }
 
-// Helper class for decoding packed ARM relocation data.
-// http://en.wikipedia.org/wiki/LEB128
-class Leb128Decoder {
- public:
-  explicit Leb128Decoder(const uint8_t* encoding)
-      : encoding_(encoding), cursor_(0) { }
-
-  uint32_t Dequeue() {
-    uint32_t value = 0;
-
-    size_t shift = 0;
-    uint8_t byte;
-
-    do {
-      byte = encoding_[cursor_++];
-      value |= static_cast<uint32_t>(byte & 127) << shift;
-      shift += 7;
-    } while (byte & 128);
-
-    return value;
-  }
-
- private:
-  const uint8_t* encoding_;
-  size_t cursor_;
-};
-
-bool ElfRelocations::ApplyArmPackedRelocs(Error* error) {
-  if (!arm_packed_relocs_)
-    return true;
-
-  Leb128Decoder decoder(arm_packed_relocs_);
-
-  // Check for the initial APR1 header.
-  if (decoder.Dequeue() != 'A' || decoder.Dequeue() != 'P' ||
-      decoder.Dequeue() != 'R' || decoder.Dequeue() != '1') {
-    error->Format("Bad packed relocations ident, expected APR1");
-    return false;
-  }
+bool ElfRelocations::ApplyPackedRel(const uint8_t* packed_relocations,
+                                    Error* error) {
+  Leb128Decoder decoder(packed_relocations);
 
   // Find the count of pairs and the start address.
   size_t pairs = decoder.Dequeue();
-  const Elf32_Addr start_address = decoder.Dequeue();
+  const ELF::Addr start_address = decoder.Dequeue();
 
-  // Emit initial R_ARM_RELATIVE relocation.
-  Elf32_Rel relocation = {start_address, R_ARM_RELATIVE};
+  // Emit initial relative relocation.
+  ELF::Rel relocation;
+  relocation.r_offset = start_address;
+  relocation.r_info = ELF_R_INFO(0, RELATIVE_RELOCATION_CODE);
   const ELF::Addr sym_addr = 0;
   const bool resolved = false;
   if (!ApplyRelReloc(&relocation, sym_addr, resolved, error))
@@ -420,7 +391,7 @@ bool ElfRelocations::ApplyArmPackedRelocs(Error* error) {
     size_t count = decoder.Dequeue();
     const size_t delta = decoder.Dequeue();
 
-    // Emit count R_ARM_RELATIVE relocations with delta offset.
+    // Emit count relative relocations with delta offset.
     while (count) {
       relocation.r_offset += delta;
       if (!ApplyRelReloc(&relocation, sym_addr, resolved, error))
@@ -434,7 +405,65 @@ bool ElfRelocations::ApplyArmPackedRelocs(Error* error) {
   RLOG("%s: unpacked_count=%d\n", __FUNCTION__, unpacked_count);
   return true;
 }
-#endif  // __arm__
+
+bool ElfRelocations::ApplyPackedRela(const uint8_t* packed_relocations,
+                                     Error* error) {
+  Sleb128Decoder decoder(packed_relocations);
+
+  // Find the count of pairs.
+  size_t pairs = decoder.Dequeue();
+
+  ELF::Addr offset = 0;
+  ELF::Sxword addend = 0;
+
+  const ELF::Addr sym_addr = 0;
+  const bool resolved = false;
+
+  size_t unpacked_count = 0;
+
+  // Emit relocations for each deltas pair.
+  while (pairs) {
+    offset += decoder.Dequeue();
+    addend += decoder.Dequeue();
+
+    ELF::Rela relocation;
+    relocation.r_offset = offset;
+    relocation.r_info = ELF_R_INFO(0, RELATIVE_RELOCATION_CODE);
+    relocation.r_addend = addend;
+    if (!ApplyRelaReloc(&relocation, sym_addr, resolved, error))
+      return false;
+    unpacked_count++;
+    pairs--;
+  }
+
+  RLOG("%s: unpacked_count=%d\n", __FUNCTION__, unpacked_count);
+  return true;
+}
+
+bool ElfRelocations::ApplyPackedRelocations(Error* error) {
+  if (!packed_relocations_)
+    return true;
+
+  // Check for an initial APR1 header, packed relocations.
+  if (packed_relocations_[0] == 'A' &&
+      packed_relocations_[1] == 'P' &&
+      packed_relocations_[2] == 'R' &&
+      packed_relocations_[3] == '1') {
+    return ApplyPackedRel(packed_relocations_ + 4, error);
+  }
+
+  // Check for an initial APA1 header, packed relocations with addend.
+  if (packed_relocations_[0] == 'A' &&
+      packed_relocations_[1] == 'P' &&
+      packed_relocations_[2] == 'A' &&
+      packed_relocations_[3] == '1') {
+    return ApplyPackedRela(packed_relocations_ + 4, error);
+  }
+
+  error->Format("Bad packed relocations ident, expected APR1 or APA1");
+  return false;
+}
+#endif  // __arm__ || __aarch64__
 
 bool ElfRelocations::ApplyRelaReloc(const ELF::Rela* rela,
                                     ELF::Addr sym_addr,
diff --git a/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.h b/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.h
index 1be4a20..71ed33b 100644
--- a/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.h
+++ b/third_party/android_crazy_linker/src/src/crazy_linker_elf_relocations.h
@@ -44,10 +44,10 @@ class ElfRelocations {
                 SymbolResolver* resolver,
                 Error* error);
 
-#ifdef __arm__
-  // Register ARM packed relocations to apply.
-  // |arm_packed_relocs| is a pointer to packed relocations data.
-  void RegisterArmPackedRelocs(uint8_t* arm_packed_relocs);
+#if defined(__arm__) || defined(__aarch64__)
+  // Register packed relocations to apply.
+  // |packed_relocs| is a pointer to packed relocations data.
+  void RegisterPackedRelocations(uint8_t* packed_relocations);
 #endif
 
   // This function is used to adjust relocated addresses in a copy of an
@@ -101,11 +101,15 @@ class ElfRelocations {
                    size_t map_addr,
                    size_t size);
 
-#ifdef __arm__
-  // Apply ARM packed relocations.
+#if defined(__arm__) || defined(__aarch64__)
+  // Apply packed rel or rela relocations.  On error, return false.
+  bool ApplyPackedRel(const uint8_t* packed_relocations, Error* error);
+  bool ApplyPackedRela(const uint8_t* packed_relocations, Error* error);
+
+  // Apply packed relocations.
   // On error, return false and set |error| message.  No-op if no packed
   // relocations were registered.
-  bool ApplyArmPackedRelocs(Error* error);
+  bool ApplyPackedRelocations(Error* error);
 #endif
 
 #if defined(__mips__)
@@ -133,8 +137,8 @@ class ElfRelocations {
   ELF::Word mips_gotsym_;
 #endif
 
-#if defined(__arm__)
-  uint8_t* arm_packed_relocs_;
+#if defined(__arm__) || defined(__aarch64__)
+  uint8_t* packed_relocations_;
 #endif
 
   bool has_text_relocations_;
diff --git a/third_party/android_crazy_linker/src/src/crazy_linker_leb128.h b/third_party/android_crazy_linker/src/src/crazy_linker_leb128.h
new file mode 100644
index 0000000..3d0ad8f
--- /dev/null
+++ b/third_party/android_crazy_linker/src/src/crazy_linker_leb128.h
@@ -0,0 +1,71 @@
+// 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.
+
+#ifndef CRAZY_LINKER_LEB128_H
+#define CRAZY_LINKER_LEB128_H
+
+#include <stdint.h>
+
+// Helper classes for decoding LEB128, used in packed relocation data.
+// http://en.wikipedia.org/wiki/LEB128
+
+namespace crazy {
+
+class Leb128Decoder {
+ public:
+  explicit Leb128Decoder(const uint8_t* encoding)
+      : encoding_(encoding), cursor_(0) { }
+
+  size_t Dequeue() {
+    uint32_t value = 0;
+
+    size_t shift = 0;
+    uint8_t byte;
+
+    do {
+      byte = encoding_[cursor_++];
+      value |= static_cast<uint32_t>(byte & 127) << shift;
+      shift += 7;
+    } while (byte & 128);
+
+    return value;
+  }
+
+ private:
+  const uint8_t* encoding_;
+  size_t cursor_;
+};
+
+class Sleb128Decoder {
+ public:
+  explicit Sleb128Decoder(const uint8_t* encoding)
+      : encoding_(encoding), cursor_(0) { }
+
+  ssize_t Dequeue() {
+    ssize_t value = 0;
+    static const size_t size = CHAR_BIT * sizeof(value);
+
+    size_t shift = 0;
+    uint8_t byte;
+
+    do {
+      byte = encoding_[cursor_++];
+      value |= (static_cast<ssize_t>(byte & 127) << shift);
+      shift += 7;
+    } while (byte & 128);
+
+    if (shift < size && (byte & 64))
+      value |= -(static_cast<ssize_t>(1) << shift);
+
+    return value;
+  }
+
+ private:
+  const uint8_t* encoding_;
+  size_t cursor_;
+};
+
+}  // namespace crazy
+
+#endif  // CRAZY_LINKER_LEB128_H
diff --git a/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.cpp b/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.cpp
index 191e5dc..ad725b5 100644
--- a/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.cpp
+++ b/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.cpp
@@ -63,12 +63,12 @@
 #endif
 
 // Extension dynamic tags for packed relocations.
-#ifdef __arm__
+#if defined(__arm__) || defined(__aarch64__)
 
 #define DT_ANDROID_REL_OFFSET (DT_LOOS)
 #define DT_ANDROID_REL_SIZE (DT_LOOS + 1)
 
-#endif  // __arm__
+#endif  // __arm__ || __aarch64__
 
 namespace crazy {
 
@@ -160,7 +160,7 @@ class SharedLibraryResolver : public ElfRelocations::SymbolResolver {
   Vector<LibraryView*>* dependencies_;
 };
 
-#ifdef __arm__
+#if defined(__arm__) || defined(__aarch64__)
 
 // Helper class to provide a simple scoped buffer.  ScopedPtr is not
 // usable here because it calls delete, not delete [].
@@ -181,12 +181,12 @@ class ScopedBuffer {
   uint8_t* buffer_;
 };
 
-// Read an .android.rel.dyn ARM packed relocations section.
+// Read an .android.rel.dyn packed relocations section.
 // Returns an allocated buffer holding the data, or NULL on error.
-uint8_t* ReadArmPackedRelocs(const char* full_path,
-                             off_t offset,
-                             size_t bytes,
-                             Error* error) {
+uint8_t* ReadPackedRelocations(const char* full_path,
+                               off_t offset,
+                               size_t bytes,
+                               Error* error) {
   FileDescriptor fd;
   if (!fd.OpenReadOnly(full_path)) {
     error->Format("Error opening file '%s'", full_path);
@@ -209,7 +209,7 @@ uint8_t* ReadArmPackedRelocs(const char* full_path,
   return packed_data;
 }
 
-#endif  // __arm__
+#endif  // __arm__ || __aarch64__
 
 }  // namespace
 
@@ -220,8 +220,8 @@ SharedLibrary::~SharedLibrary() {
   if (view_.load_address())
     munmap(reinterpret_cast<void*>(view_.load_address()), view_.load_size());
 
-#ifdef __arm__
-  delete [] arm_packed_relocs_;
+#if defined(__arm__) || defined(__aarch64__)
+  delete [] packed_relocations_;
 #endif
 }
 
@@ -276,9 +276,11 @@ bool SharedLibrary::Load(const char* full_path,
   LOG("%s: Extracting ARM.exidx table for %s\n", __FUNCTION__, base_name_);
   (void)phdr_table_get_arm_exidx(
       phdr(), phdr_count(), load_bias(), &arm_exidx_, &arm_exidx_count_);
+#endif
 
-  off_t arm_packed_relocs_offset = 0;
-  size_t arm_packed_relocs_size = 0;
+#if defined(__arm__) || defined(__aarch64__)
+  off_t packed_relocations_offset = 0;
+  size_t packed_relocations_size = 0;
 #endif
 
   LOG("%s: Parsing dynamic table for %s\n", __FUNCTION__, base_name_);
@@ -339,14 +341,14 @@ bool SharedLibrary::Load(const char* full_path,
         if (dyn_value & DF_SYMBOLIC)
           has_DT_SYMBOLIC_ = true;
         break;
-#if defined(__arm__)
+#if defined(__arm__) || defined(__aarch64__)
       case DT_ANDROID_REL_OFFSET:
-        arm_packed_relocs_offset = dyn.GetOffset();
-        LOG("  DT_ANDROID_REL_OFFSET addr=%p\n", arm_packed_relocs_offset);
+        packed_relocations_offset = dyn.GetOffset();
+        LOG("  DT_ANDROID_REL_OFFSET addr=%p\n", packed_relocations_offset);
         break;
       case DT_ANDROID_REL_SIZE:
-        arm_packed_relocs_size = dyn.GetValue();
-        LOG("  DT_ANDROID_REL_SIZE=%d\n", arm_packed_relocs_size);
+        packed_relocations_size = dyn.GetValue();
+        LOG("  DT_ANDROID_REL_SIZE=%d\n", packed_relocations_size);
         break;
 #endif
 #if defined(__mips__)
@@ -360,26 +362,26 @@ bool SharedLibrary::Load(const char* full_path,
     }
   }
 
-#ifdef __arm__
-  // If ARM packed relocations are present in the target library, read the
-  // section data and save it in arm_packed_relocs_.
-  if (arm_packed_relocs_offset && arm_packed_relocs_size) {
-    LOG("%s: ARM packed relocations found at offset %d, %d bytes\n",
+#if defined(__arm__) || defined(__aarch64__)
+  // If packed relocations are present in the target library, read the
+  // section data and save it in packed_relocations_.
+  if (packed_relocations_offset && packed_relocations_size) {
+    LOG("%s: Packed relocations found at offset %d, %d bytes\n",
         __FUNCTION__,
-        arm_packed_relocs_offset,
-        arm_packed_relocs_size);
-
-    arm_packed_relocs_ =
-        ReadArmPackedRelocs(full_path,
-                            arm_packed_relocs_offset + file_offset,
-                            arm_packed_relocs_size,
-                            error);
-    if (!arm_packed_relocs_)
+        packed_relocationss_offset,
+        packed_relocations_size);
+
+    packed_relocations_ =
+        ReadPackedRelocations(full_path,
+                              packed_relocations_offset + file_offset,
+                              packed_relocations_size,
+                              error);
+    if (!packed_relocations_)
       return false;
 
-    LOG("%s: ARM packed relocations stored at %p\n",
+    LOG("%s: Packed relocations stored at %p\n",
         __FUNCTION__,
-        arm_packed_relocs_);
+        packed_relocations_);
   }
 #endif
 
@@ -398,8 +400,8 @@ bool SharedLibrary::Relocate(LibraryList* lib_list,
   if (!relocations.Init(&view_, error))
     return false;
 
-#ifdef __arm__
-  relocations.RegisterArmPackedRelocs(arm_packed_relocs_);
+#if defined(__arm__) || defined(__aarch64__)
+  relocations.RegisterPackedRelocations(packed_relocations_);
 #endif
 
   SharedLibraryResolver resolver(this, lib_list, dependencies);
diff --git a/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.h b/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.h
index 051aa11f..64e51b3 100644
--- a/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.h
+++ b/third_party/android_crazy_linker/src/src/crazy_linker_shared_library.h
@@ -191,9 +191,11 @@ class SharedLibrary {
   // ARM EABI section used for stack unwinding.
   unsigned* arm_exidx_;
   size_t arm_exidx_count_;
+#endif
 
-  // ARM packed relocations data, NULL if absent.
-  uint8_t* arm_packed_relocs_;
+#if defined(__arm__) || defined(__aarch64__)
+  // Packed relocations data, NULL if absent.
+  uint8_t* packed_relocations_;
 #endif
 
   link_map_t link_map_;
diff --git a/third_party/android_crazy_linker/src/src/elf_traits.h b/third_party/android_crazy_linker/src/src/elf_traits.h
index f666b65..6c6e552 100644
--- a/third_party/android_crazy_linker/src/src/elf_traits.h
+++ b/third_party/android_crazy_linker/src/src/elf_traits.h
@@ -17,6 +17,8 @@ struct ELF {
   typedef Elf32_Phdr Phdr;
   typedef Elf32_Word Word;
   typedef Elf32_Sword Sword;
+  // TODO(simonb): Elf32_Sxword missing from the NDK.
+  typedef int64_t Sxword;
   typedef Elf32_Addr Addr;
   typedef Elf32_Dyn Dyn;
   typedef Elf32_Sym Sym;
@@ -27,13 +29,17 @@ struct ELF {
   enum { kElfClass = ELFCLASS32 };
   enum { kElfBits = 32 };
 
-#ifndef ELF_R_TYPE
-#define ELF_R_TYPE ELF32_R_TYPE
-#endif
+# ifndef ELF_R_TYPE
+# define ELF_R_TYPE ELF32_R_TYPE
+# endif
 
-#ifndef ELF_R_SYM
-#define ELF_R_SYM ELF32_R_SYM
-#endif
+# ifndef ELF_R_SYM
+# define ELF_R_SYM ELF32_R_SYM
+# endif
+
+# ifndef ELF_R_INFO
+# define ELF_R_INFO ELF32_R_INFO
+# endif
 };
 #elif __SIZEOF_POINTER__ == 8
 struct ELF {
@@ -41,6 +47,7 @@ struct ELF {
   typedef Elf64_Phdr Phdr;
   typedef Elf64_Word Word;
   typedef Elf64_Sword Sword;
+  typedef Elf64_Sxword Sxword;
   typedef Elf64_Addr Addr;
   typedef Elf64_Dyn Dyn;
   typedef Elf64_Sym Sym;
@@ -51,13 +58,22 @@ struct ELF {
   enum { kElfClass = ELFCLASS64 };
   enum { kElfBits = 64 };
 
-#ifndef ELF_R_TYPE
-#define ELF_R_TYPE ELF64_R_TYPE
-#endif
+# ifndef ELF_R_TYPE
+# define ELF_R_TYPE ELF64_R_TYPE
+# endif
 
-#ifndef ELF_R_SYM
-#define ELF_R_SYM ELF64_R_SYM
-#endif
+# ifndef ELF_R_SYM
+# define ELF_R_SYM ELF64_R_SYM
+# endif
+
+// TODO(simonb): ELF64_R_INFO missing from the NDK.
+# ifndef ELF64_R_INFO
+# define ELF64_R_INFO(sym,type) ((((Elf64_Xword) (sym)) << 32) + (type))
+# endif
+
+# ifndef ELF_R_INFO
+# define ELF_R_INFO ELF64_R_INFO
+# endif
 };
 #else
 #error "Unsupported target CPU bitness"