Add support for packed relocations.

Change-Id: I796a4ce86d3fccb8361c19889419c96147ee3c9f
diff --git a/linker/linker.cpp b/linker/linker.cpp
index ae9df52..87fce95 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -53,6 +53,7 @@
 #include "linker_allocator.h"
 #include "linker_debug.h"
 #include "linker_environ.h"
+#include "linker_leb128.h"
 #include "linker_phdr.h"
 #include "linker_relocs.h"
 #include "linker_reloc_iterators.h"
@@ -1302,6 +1303,10 @@
 bool soinfo::relocate(ElfRelIteratorT&& rel_iterator, const soinfo_list_t& global_group, const soinfo_list_t& local_group) {
   for (size_t idx = 0; rel_iterator.has_next(); ++idx) {
     const auto rel = rel_iterator.next();
+    if (rel == nullptr) {
+      return false;
+    }
+
     ElfW(Word) type = ELFW(R_TYPE)(rel->r_info);
     ElfW(Word) sym = ELFW(R_SYM)(rel->r_info);
 
@@ -1407,16 +1412,16 @@
         MARK(rel->r_offset);
         TRACE_TYPE(RELO, "RELO RELATIVE %16p <- %16p\n",
                    reinterpret_cast<void*>(reloc),
-                   reinterpret_cast<void*>(base + addend));
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = (base + addend);
+                   reinterpret_cast<void*>(load_bias + addend));
+        *reinterpret_cast<ElfW(Addr)*>(reloc) = (load_bias + addend);
         break;
       case R_GENERIC_IRELATIVE:
         count_relocation(kRelocRelative);
         MARK(rel->r_offset);
         TRACE_TYPE(RELO, "RELO IRELATIVE %16p <- %16p\n",
                     reinterpret_cast<void*>(reloc),
-                    reinterpret_cast<void*>(base + addend));
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = call_ifunc_resolver(base + addend);
+                    reinterpret_cast<void*>(load_bias + addend));
+        *reinterpret_cast<ElfW(Addr)*>(reloc) = call_ifunc_resolver(load_bias + addend);
         break;
 
 #if defined(__aarch64__)
@@ -2053,6 +2058,22 @@
         rela_count_ = d->d_un.d_val / sizeof(ElfW(Rela));
         break;
 
+      case DT_ANDROID_RELA:
+        android_relocs_ = reinterpret_cast<uint8_t*>(load_bias + d->d_un.d_ptr);
+        break;
+
+      case DT_ANDROID_RELASZ:
+        android_relocs_size_ = d->d_un.d_val;
+        break;
+
+      case DT_ANDROID_REL:
+        DL_ERR("unsupported DT_ANDROID_REL in \"%s\"", name);
+        return false;
+
+      case DT_ANDROID_RELSZ:
+        DL_ERR("unsupported DT_ANDROID_RELSZ in \"%s\"", name);
+        return false;
+
       case DT_RELAENT:
         if (d->d_un.d_val != sizeof(ElfW(Rela))) {
           DL_ERR("invalid DT_RELAENT: %zd", static_cast<size_t>(d->d_un.d_val));
@@ -2071,6 +2092,7 @@
       case DT_RELSZ:
         DL_ERR("unsupported DT_RELSZ in \"%s\"", name);
         return false;
+
 #else
       case DT_REL:
         rel_ = reinterpret_cast<ElfW(Rel)*>(load_bias + d->d_un.d_ptr);
@@ -2087,6 +2109,22 @@
         }
         break;
 
+      case DT_ANDROID_REL:
+        android_relocs_ = reinterpret_cast<uint8_t*>(load_bias + d->d_un.d_ptr);
+        break;
+
+      case DT_ANDROID_RELSZ:
+        android_relocs_size_ = d->d_un.d_val;
+        break;
+
+      case DT_ANDROID_RELA:
+        DL_ERR("unsupported DT_ANDROID_RELA in \"%s\"", name);
+        return false;
+
+      case DT_ANDROID_RELASZ:
+        DL_ERR("unsupported DT_ANDROID_RELASZ in \"%s\"", name);
+        return false;
+
       // "Indicates that all RELATIVE relocations have been concatenated together,
       // and specifies the RELATIVE relocation count."
       //
@@ -2094,9 +2132,15 @@
       // Not currently used by bionic linker - ignored.
       case DT_RELCOUNT:
         break;
+
       case DT_RELA:
         DL_ERR("unsupported DT_RELA in \"%s\"", name);
         return false;
+
+      case DT_RELASZ:
+        DL_ERR("unsupported DT_RELASZ in \"%s\"", name);
+        return false;
+
 #endif
       case DT_INIT:
         init_func_ = reinterpret_cast<linker_function_t>(load_bias + d->d_un.d_ptr);
@@ -2251,7 +2295,8 @@
   return true;
 }
 
-bool soinfo::link_image(const soinfo_list_t& global_group, const soinfo_list_t& local_group, const android_dlextinfo* extinfo) {
+bool soinfo::link_image(const soinfo_list_t& global_group, const soinfo_list_t& local_group,
+                        const android_dlextinfo* extinfo) {
 
   local_group_root_ = local_group.front();
   if (local_group_root_ == nullptr) {
@@ -2272,6 +2317,40 @@
   }
 #endif
 
+  if (android_relocs_ != nullptr) {
+    // check signature
+    if (android_relocs_size_ > 3 &&
+        android_relocs_[0] == 'A' &&
+        android_relocs_[1] == 'P' &&
+        (android_relocs_[2] == 'U' || android_relocs_[2] == 'S') &&
+        android_relocs_[3] == '2') {
+      DEBUG("[ android relocating %s ]", name);
+
+      bool relocated = false;
+      const uint8_t* packed_relocs = android_relocs_ + 4;
+      const size_t packed_relocs_size = android_relocs_size_ - 4;
+
+      if (android_relocs_[2] == 'U') {
+        relocated = relocate(
+            packed_reloc_iterator<leb128_decoder>(
+              leb128_decoder(packed_relocs, packed_relocs_size)),
+            global_group, local_group);
+      } else { // android_relocs_[2] == 'S'
+        relocated = relocate(
+            packed_reloc_iterator<sleb128_decoder>(
+              sleb128_decoder(packed_relocs, packed_relocs_size)),
+            global_group, local_group);
+      }
+
+      if (!relocated) {
+        return false;
+      }
+    } else {
+      DL_ERR("bad android relocation header.");
+      return false;
+    }
+  }
+
 #if defined(USE_RELA)
   if (rela_ != nullptr) {
     DEBUG("[ relocating %s ]", name);
diff --git a/linker/linker.h b/linker/linker.h
index 222ddbf..f8640a0 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -315,6 +315,9 @@
 
   soinfo* local_group_root_;
 
+  uint8_t* android_relocs_;
+  size_t android_relocs_size_;
+
   friend soinfo* get_libdl_info();
 };
 
diff --git a/linker/linker_leb128.h b/linker/linker_leb128.h
new file mode 100644
index 0000000..d5c6488
--- /dev/null
+++ b/linker/linker_leb128.h
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LINKER_LEB128_H
+#define _LINKER_LEB128_H
+
+#include <stdint.h>
+
+// Helper classes for decoding LEB128, used in packed relocation data.
+// http://en.wikipedia.org/wiki/LEB128
+
+class leb128_decoder {
+ public:
+  leb128_decoder(const uint8_t* buffer, size_t count)
+      : current_(buffer), end_(buffer + count) { }
+
+  size_t pop_front() {
+    size_t value = 0;
+
+    size_t shift = 0;
+    uint8_t byte;
+
+    do {
+      if (current_ >= end_) {
+        __libc_fatal("leb128_decoder ran out of bounds");
+      }
+      byte = *current_++;
+      value |= static_cast<size_t>(byte & 127) << shift;
+      shift += 7;
+    } while (byte & 128);
+
+    return value;
+  }
+
+ private:
+  const uint8_t* current_;
+  const uint8_t* const end_;
+};
+
+class sleb128_decoder {
+ public:
+  sleb128_decoder(const uint8_t* buffer, size_t count)
+      : current_(buffer), end_(buffer+count) { }
+
+  size_t pop_front() {
+    size_t value = 0;
+    static const size_t size = CHAR_BIT * sizeof(value);
+
+    size_t shift = 0;
+    uint8_t byte;
+
+    do {
+      if (current_ >= end_) {
+        __libc_fatal("leb128_decoder ran out of bounds");
+      }
+      byte = *current_++;
+      value |= (static_cast<size_t>(byte & 127) << shift);
+      shift += 7;
+    } while (byte & 128);
+
+    if (shift < size && (byte & 64)) {
+      value |= -(static_cast<size_t>(1) << shift);
+    }
+
+    return value;
+  }
+
+ private:
+  const uint8_t* current_;
+  const uint8_t* const end_;
+};
+
+#endif // __LINKER_LEB128_H
+
diff --git a/linker/linker_mips.cpp b/linker/linker_mips.cpp
index d71659e..f0bde55 100644
--- a/linker/linker_mips.cpp
+++ b/linker/linker_mips.cpp
@@ -30,14 +30,31 @@
 #include "linker_debug.h"
 #include "linker_relocs.h"
 #include "linker_reloc_iterators.h"
+#include "linker_leb128.h"
 
-template bool soinfo::relocate<plain_reloc_iterator>(plain_reloc_iterator&& rel_iterator, const soinfo_list_t& global_group, const soinfo_list_t& local_group);
+template bool soinfo::relocate<plain_reloc_iterator>(plain_reloc_iterator&& rel_iterator,
+                                                     const soinfo_list_t& global_group,
+                                                     const soinfo_list_t& local_group);
+
+template bool soinfo::relocate<packed_reloc_iterator<sleb128_decoder>>(
+    packed_reloc_iterator<sleb128_decoder>&& rel_iterator,
+    const soinfo_list_t& global_group,
+    const soinfo_list_t& local_group);
+
+template bool soinfo::relocate<packed_reloc_iterator<leb128_decoder>>(
+    packed_reloc_iterator<leb128_decoder>&& rel_iterator,
+    const soinfo_list_t& global_group,
+    const soinfo_list_t& local_group);
 
 template <typename ElfRelIteratorT>
 bool soinfo::relocate(ElfRelIteratorT&& rel_iterator, const soinfo_list_t& global_group, const soinfo_list_t& local_group) {
   for (size_t idx = 0; rel_iterator.has_next(); ++idx) {
     const auto rel = rel_iterator.next();
 
+    if (rel == nullptr) {
+      return false;
+    }
+
     ElfW(Word) type = ELFW(R_TYPE)(rel->r_info);
     ElfW(Word) sym = ELFW(R_SYM)(rel->r_info);
 
diff --git a/linker/linker_phdr.cpp b/linker/linker_phdr.cpp
index 91a2fb8..38e6262 100644
--- a/linker/linker_phdr.cpp
+++ b/linker/linker_phdr.cpp
@@ -332,7 +332,7 @@
       return false;
     }
     int mmap_flags = MAP_PRIVATE | MAP_ANONYMOUS;
-    start = mmap(addr, load_size_, PROT_NONE, mmap_flags, -1, 0);
+    start = mmap(nullptr, load_size_, PROT_NONE, mmap_flags, -1, 0);
     if (start == MAP_FAILED) {
       DL_ERR("couldn't reserve %zd bytes of address space for \"%s\"", load_size_, name_);
       return false;
diff --git a/linker/linker_reloc_iterators.h b/linker/linker_reloc_iterators.h
index 6388bb0..5db31f9 100644
--- a/linker/linker_reloc_iterators.h
+++ b/linker/linker_reloc_iterators.h
@@ -19,6 +19,18 @@
 
 #include "linker.h"
 
+#include <string.h>
+
+#define RELOCATION_GROUPED_BY_INFO_FLAG 1
+#define RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG 2
+#define RELOCATION_GROUPED_BY_ADDEND_FLAG 4
+#define RELOCATION_GROUP_HAS_ADDEND_FLAG 8
+
+#define RELOCATION_GROUPED_BY_INFO(flags) (((flags) & RELOCATION_GROUPED_BY_INFO_FLAG) != 0)
+#define RELOCATION_GROUPED_BY_OFFSET_DELTA(flags) (((flags) & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0)
+#define RELOCATION_GROUPED_BY_ADDEND(flags) (((flags) & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0)
+#define RELOCATION_GROUP_HAS_ADDEND(flags) (((flags) & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0)
+
 class plain_reloc_iterator {
 #if defined(USE_RELA)
   typedef ElfW(Rela) rel_t;
@@ -44,4 +56,97 @@
   DISALLOW_COPY_AND_ASSIGN(plain_reloc_iterator);
 };
 
+template <typename decoder_t>
+class packed_reloc_iterator {
+#if defined(USE_RELA)
+  typedef ElfW(Rela) rel_t;
+#else
+  typedef ElfW(Rel) rel_t;
+#endif
+ public:
+  explicit packed_reloc_iterator(decoder_t&& decoder)
+      : decoder_(decoder) {
+    // initialize fields
+    memset(&reloc_, 0, sizeof(reloc_));
+    relocation_count_ = decoder_.pop_front();
+    reloc_.r_offset = decoder_.pop_front();
+    relocation_index_ = 0;
+    relocation_group_index_ = 0;
+    group_size_ = 0;
+  }
+
+  bool has_next() const {
+    return relocation_index_ < relocation_count_;
+  }
+
+  rel_t* next() {
+    if (relocation_group_index_ == group_size_) {
+      if (!read_group_fields()) {
+        // Iterator is inconsistent state; it should not be called again
+        // but in case it is let's make sure has_next() returns false.
+        relocation_index_ = relocation_count_ = 0;
+        return nullptr;
+      }
+    }
+
+    if (RELOCATION_GROUPED_BY_OFFSET_DELTA(group_flags_)) {
+      reloc_.r_offset += group_r_offset_delta_;
+    } else {
+      reloc_.r_offset += decoder_.pop_front();
+    }
+
+    if (!RELOCATION_GROUPED_BY_INFO(group_flags_)) {
+      reloc_.r_info = decoder_.pop_front();
+    }
+
+#if defined(USE_RELA)
+    if (RELOCATION_GROUP_HAS_ADDEND(group_flags_) && !RELOCATION_GROUPED_BY_ADDEND(group_flags_)) {
+      reloc_.r_addend += decoder_.pop_front();
+    }
+#endif
+
+    relocation_index_++;
+    relocation_group_index_++;
+
+    return &reloc_;
+  }
+ private:
+  bool read_group_fields() {
+    group_size_ = decoder_.pop_front();
+    group_flags_ = decoder_.pop_front();
+
+    if (RELOCATION_GROUPED_BY_OFFSET_DELTA(group_flags_)) {
+      group_r_offset_delta_ = decoder_.pop_front();
+    }
+
+    if (RELOCATION_GROUPED_BY_INFO(group_flags_)) {
+      reloc_.r_info = decoder_.pop_front();
+    }
+
+    if (RELOCATION_GROUP_HAS_ADDEND(group_flags_) && RELOCATION_GROUPED_BY_ADDEND(group_flags_)) {
+#if !defined(USE_RELA)
+      // This platform does not support rela, and yet we have it encoded in android_rel section.
+      DL_ERR("unexpected r_addend in android.rel section");
+      return false;
+#else
+      reloc_.r_addend += decoder_.pop_front();
+    } else if (!RELOCATION_GROUP_HAS_ADDEND(group_flags_)) {
+      reloc_.r_addend = 0;
+#endif
+    }
+
+    relocation_group_index_ = 0;
+    return true;
+  }
+
+  decoder_t decoder_;
+  size_t relocation_count_;
+  size_t group_size_;
+  size_t group_flags_;
+  size_t group_r_offset_delta_;
+  size_t relocation_index_;
+  size_t relocation_group_index_;
+  rel_t reloc_;
+};
+
 #endif  // __LINKER_RELOC_ITERATORS_H