Merge "Add a linker relocation benchmark"
diff --git a/libc/Android.bp b/libc/Android.bp
index 8284174..24cb90c 100644
--- a/libc/Android.bp
+++ b/libc/Android.bp
@@ -94,7 +94,7 @@
 cc_defaults {
     name: "libc_native_allocator_defaults",
 
-    defaults: ["libc_jemalloc5_defaults"],
+    defaults: ["libc_scudo_defaults"],
 }
 
 cc_defaults {
@@ -1812,8 +1812,10 @@
         "//external/perfetto:__subpackages__",
         "//external/scudo:__subpackages__",
         "//system/core/debuggerd:__subpackages__",
+        "//system/memory/libmemunreachable:__subpackages__",
     ],
     host_supported: true,
+    vendor_available: true,
     recovery_available: true,
     native_bridge_supported: true,
     export_include_dirs: [
@@ -2612,7 +2614,6 @@
 
 cc_library_shared {
     name: "libc_scudo",
-    defaults: ["libc_scudo_wrapper_defaults"],
     vendor_available: true,
     stl: "none",
     system_shared_libs: [],
diff --git a/libc/SECCOMP_WHITELIST_APP.TXT b/libc/SECCOMP_WHITELIST_APP.TXT
index 9aa4260..faa2d63 100644
--- a/libc/SECCOMP_WHITELIST_APP.TXT
+++ b/libc/SECCOMP_WHITELIST_APP.TXT
@@ -25,10 +25,17 @@
 #
 # This file is processed by a python script named genseccomp.py.
 
+# Needed for debugging 32-bit Chrome
+int	pipe:pipe(int pipefd[2])	arm,x86,mips
+
 # b/34651972
 int	access:access(const char *pathname, int mode)	arm,x86,mips
 int	stat64:stat64(const char*, struct stat64*)	arm,x86,mips
 
+# b/34813887
+int	open:open(const char *path, int oflag, ... ) arm,x86,x86_64,mips
+int	getdents:getdents(unsigned int fd, struct linux_dirent *dirp, unsigned int count) arm,x86,x86_64,mips
+
 # b/34719286
 int	eventfd:eventfd(unsigned int initval, int flags)	arm,x86,mips
 
diff --git a/libc/SECCOMP_WHITELIST_COMMON.TXT b/libc/SECCOMP_WHITELIST_COMMON.TXT
index 07f84a8..c55d875 100644
--- a/libc/SECCOMP_WHITELIST_COMMON.TXT
+++ b/libc/SECCOMP_WHITELIST_COMMON.TXT
@@ -52,13 +52,6 @@
 # b/34763393
 int	seccomp:seccomp(unsigned int operation, unsigned int flags, void *args)	all
 
-# Needed for debugging 32-bit Chrome
-int	pipe:pipe(int pipefd[2])	arm,x86,mips
-
-# Needed by breakpad (b/34813887).
-int	open:open(const char *path, int oflag, ... ) arm,x86,x86_64,mips
-int	getdents:getdents(unsigned int fd, struct linux_dirent *dirp, unsigned int count) arm,x86,x86_64,mips
-
 # Needed by sanitizers (b/34606909, b/136777266).
 int open:open(const char*, int, ...)  arm,x86,x86_64
 int stat64:stat64(const char*, struct stat64*)  arm,x86
@@ -106,3 +99,5 @@
 int rt_sigtimedwait_time64(const sigset64_t*, siginfo_t*, const timespec64*, size_t) lp32
 int futex_time64(int*, int, int, const timespec64*, int*, int) lp32
 int sched_rr_get_interval_time64(pid_t, timespec64*) lp32
+# Since Linux 5.3, not in glibc.
+int pidfd_open(pid_t pid, unsigned int flags) all
diff --git a/libc/bionic/malloc_common_dynamic.cpp b/libc/bionic/malloc_common_dynamic.cpp
index 8068f4e..a03be50 100644
--- a/libc/bionic/malloc_common_dynamic.cpp
+++ b/libc/bionic/malloc_common_dynamic.cpp
@@ -284,17 +284,10 @@
   return true;
 }
 
-// Note about USE_SCUDO. This file is compiled into libc.so and libc_scudo.so.
-// When compiled into libc_scudo.so, the libc_malloc_* libraries don't need
-// to be loaded from the runtime namespace since libc_scudo.so is not from
-// the runtime APEX, but is copied to any APEX that needs it.
-#ifndef USE_SCUDO
 extern "C" struct android_namespace_t* android_get_exported_namespace(const char* name);
-#endif
 
 void* LoadSharedLibrary(const char* shared_lib, const char* prefix, MallocDispatch* dispatch_table) {
   void* impl_handle = nullptr;
-#ifndef USE_SCUDO
   // Try to load the libc_malloc_* libs from the "runtime" namespace and then
   // fall back to dlopen() to load them from the default namespace.
   //
@@ -313,7 +306,6 @@
     };
     impl_handle = android_dlopen_ext(shared_lib, RTLD_NOW | RTLD_LOCAL, &dlextinfo);
   }
-#endif
 
   if (impl_handle == nullptr) {
     impl_handle = dlopen(shared_lib, RTLD_NOW | RTLD_LOCAL);
diff --git a/libc/include/android/legacy_termios_inlines.h b/libc/include/android/legacy_termios_inlines.h
index 9ea588d..6222786 100644
--- a/libc/include/android/legacy_termios_inlines.h
+++ b/libc/include/android/legacy_termios_inlines.h
@@ -30,7 +30,10 @@
 
 #include <sys/cdefs.h>
 
-#if __ANDROID_API__ < 21
+// The last bugfixes to <bits/termios_inlines.h> were
+// 5da96467a99254c963aef44e75167661d3e02278, so even those these functions were
+// in API level 21, ensure that everyone's using the latest versions.
+#if __ANDROID_API__ < 28
 
 #include <linux/termios.h>
 #include <sys/ioctl.h>
diff --git a/libc/include/termios.h b/libc/include/termios.h
index 8eca96e..e3f388c 100644
--- a/libc/include/termios.h
+++ b/libc/include/termios.h
@@ -40,8 +40,10 @@
 
 __BEGIN_DECLS
 
-#if __ANDROID_API__ >= 21
-// This file is implemented as static inlines before API level 21.
+#if __ANDROID_API__ >= 28
+// This file is implemented as static inlines before API level 28.
+// Strictly these functions were introduced in API level 21, but there were bugs
+// in cfmakeraw() and cfsetspeed() until 28.
 
 /**
  * [cfgetispeed(3)](http://man7.org/linux/man-pages/man3/cfgetispeed.3.html)
diff --git a/linker/Android.bp b/linker/Android.bp
index 8e810d2..e67fca8 100644
--- a/linker/Android.bp
+++ b/linker/Android.bp
@@ -165,6 +165,7 @@
         "linker_logger.cpp",
         "linker_mapped_file_fragment.cpp",
         "linker_phdr.cpp",
+        "linker_relocate.cpp",
         "linker_sdk_versions.cpp",
         "linker_soinfo.cpp",
         "linker_tls.cpp",
diff --git a/linker/linked_list.h b/linker/linked_list.h
index 5473ca0..b8a8f0e 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -253,6 +253,12 @@
     return one_element_list;
   }
 
+  size_t size() const {
+    size_t result = 0;
+    for_each([&](T*) { ++result; });
+    return result;
+  }
+
  private:
   LinkedListEntry<T>* head_;
   LinkedListEntry<T>* tail_;
diff --git a/linker/linker.cpp b/linker/linker.cpp
index 10833be..57554fb 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -63,8 +63,7 @@
 #include "linker_namespaces.h"
 #include "linker_sleb128.h"
 #include "linker_phdr.h"
-#include "linker_relocs.h"
-#include "linker_reloc_iterators.h"
+#include "linker_relocate.h"
 #include "linker_tls.h"
 #include "linker_utils.h"
 
@@ -276,31 +275,6 @@
 
 static std::vector<std::string> g_ld_preload_names;
 
-#if STATS
-struct linker_stats_t {
-  int count[kRelocMax];
-};
-
-static linker_stats_t linker_stats;
-
-void count_relocation(RelocationKind kind) {
-  ++linker_stats.count[kind];
-}
-
-void print_linker_stats() {
-  PRINT("RELO STATS: %s: %d abs, %d rel, %d copy, %d symbol (%d cached)",
-         g_argv[0],
-         linker_stats.count[kRelocAbsolute],
-         linker_stats.count[kRelocRelative],
-         linker_stats.count[kRelocCopy],
-         linker_stats.count[kRelocSymbol],
-         linker_stats.count[kRelocSymbolCached]);
-}
-#else
-void count_relocation(RelocationKind) {
-}
-#endif
-
 static void notify_gdb_of_load(soinfo* info) {
   if (info->is_linker() || info->is_main_executable()) {
     // gdb already knows about the linker and the main executable.
@@ -488,79 +462,6 @@
   return rv;
 }
 
-
-bool soinfo_do_lookup(soinfo* si_from, const char* name, const version_info* vi,
-                      soinfo** si_found_in, const soinfo_list_t& global_group,
-                      const soinfo_list_t& local_group, const ElfW(Sym)** symbol) {
-  SymbolName symbol_name(name);
-  const ElfW(Sym)* s = nullptr;
-
-  /* "This element's presence in a shared object library alters the dynamic linker's
-   * symbol resolution algorithm for references within the library. Instead of starting
-   * a symbol search with the executable file, the dynamic linker starts from the shared
-   * object itself. If the shared object fails to supply the referenced symbol, the
-   * dynamic linker then searches the executable file and other shared objects as usual."
-   *
-   * http://www.sco.com/developers/gabi/2012-12-31/ch5.dynamic.html
-   *
-   * Note that this is unlikely since static linker avoids generating
-   * relocations for -Bsymbolic linked dynamic executables.
-   */
-  if (si_from->has_DT_SYMBOLIC) {
-    DEBUG("%s: looking up %s in local scope (DT_SYMBOLIC)", si_from->get_realpath(), name);
-    s = si_from->find_symbol_by_name(symbol_name, vi);
-    if (s != nullptr) {
-      *si_found_in = si_from;
-    }
-  }
-
-  // 1. Look for it in global_group
-  if (s == nullptr) {
-    global_group.visit([&](soinfo* global_si) {
-      DEBUG("%s: looking up %s in %s (from global group)",
-          si_from->get_realpath(), name, global_si->get_realpath());
-      s = global_si->find_symbol_by_name(symbol_name, vi);
-      if (s != nullptr) {
-        *si_found_in = global_si;
-        return false;
-      }
-
-      return true;
-    });
-  }
-
-  // 2. Look for it in the local group
-  if (s == nullptr) {
-    local_group.visit([&](soinfo* local_si) {
-      if (local_si == si_from && si_from->has_DT_SYMBOLIC) {
-        // we already did this - skip
-        return true;
-      }
-
-      DEBUG("%s: looking up %s in %s (from local group)",
-          si_from->get_realpath(), name, local_si->get_realpath());
-      s = local_si->find_symbol_by_name(symbol_name, vi);
-      if (s != nullptr) {
-        *si_found_in = local_si;
-        return false;
-      }
-
-      return true;
-    });
-  }
-
-  if (s != nullptr) {
-    TRACE_TYPE(LOOKUP, "si %s sym %s s->st_value = %p, "
-               "found in %s, base = %p, load bias = %p",
-               si_from->get_realpath(), name, reinterpret_cast<void*>(s->st_value),
-               (*si_found_in)->get_realpath(), reinterpret_cast<void*>((*si_found_in)->base),
-               reinterpret_cast<void*>((*si_found_in)->load_bias));
-  }
-
-  *symbol = s;
-  return true;
-}
-
 ProtectedDataGuard::ProtectedDataGuard() {
   if (ref_count_++ == 0) {
     protect_data(PROT_READ | PROT_WRITE);
@@ -1906,6 +1807,9 @@
       });
 
     soinfo_list_t global_group = local_group_ns->get_global_group();
+    SymbolLookupList lookup_list(global_group, local_group);
+    soinfo* local_group_root = local_group.front();
+
     bool linked = local_group.visit([&](soinfo* si) {
       // Even though local group may contain accessible soinfos from other namespaces
       // we should avoid linking them (because if they are not linked -> they
@@ -1920,7 +1824,8 @@
         if (__libc_shared_globals()->load_hook) {
           __libc_shared_globals()->load_hook(si->load_bias, si->phdr, si->phnum);
         }
-        if (!si->link_image(global_group, local_group, link_extinfo, &relro_fd_offset) ||
+        lookup_list.set_dt_symbolic_lib(si->has_DT_SYMBOLIC ? si : nullptr);
+        if (!si->link_image(lookup_list, local_group_root, link_extinfo, &relro_fd_offset) ||
             !get_cfi_shadow()->AfterLoad(si, solist_get_head())) {
           return false;
         }
@@ -2912,421 +2817,6 @@
   return true;
 }
 
-#if !defined(__mips__)
-#if defined(USE_RELA)
-static ElfW(Addr) get_addend(ElfW(Rela)* rela, ElfW(Addr) reloc_addr __unused) {
-  return rela->r_addend;
-}
-#else
-static ElfW(Addr) get_addend(ElfW(Rel)* rel, ElfW(Addr) reloc_addr) {
-  // The i386 psABI specifies that R_386_GLOB_DAT doesn't have an addend. The ARM ELF ABI document
-  // (IHI0044F) specifies that R_ARM_GLOB_DAT has an addend, but Bionic isn't adding it.
-  if (ELFW(R_TYPE)(rel->r_info) == R_GENERIC_RELATIVE ||
-      ELFW(R_TYPE)(rel->r_info) == R_GENERIC_IRELATIVE ||
-      ELFW(R_TYPE)(rel->r_info) == R_GENERIC_ABSOLUTE ||
-      ELFW(R_TYPE)(rel->r_info) == R_GENERIC_TLS_DTPREL ||
-      ELFW(R_TYPE)(rel->r_info) == R_GENERIC_TLS_TPREL) {
-    return *reinterpret_cast<ElfW(Addr)*>(reloc_addr);
-  }
-  return 0;
-}
-#endif
-
-static bool is_tls_reloc(ElfW(Word) type) {
-  switch (type) {
-    case R_GENERIC_TLS_DTPMOD:
-    case R_GENERIC_TLS_DTPREL:
-    case R_GENERIC_TLS_TPREL:
-    case R_GENERIC_TLSDESC:
-      return true;
-    default:
-      return false;
-  }
-}
-
-template<typename ElfRelIteratorT>
-bool soinfo::relocate(const VersionTracker& version_tracker, ElfRelIteratorT&& rel_iterator,
-                      const soinfo_list_t& global_group, const soinfo_list_t& local_group) {
-  const size_t tls_tp_base = __libc_shared_globals()->static_tls_layout.offset_thread_pointer();
-  std::vector<std::pair<TlsDescriptor*, size_t>> deferred_tlsdesc_relocs;
-
-  struct {
-    // Cache key
-    ElfW(Word) sym;
-
-    // Cache value
-    const ElfW(Sym)* s;
-    soinfo* lsi;
-  } symbol_lookup_cache;
-
-  symbol_lookup_cache.sym = 0;
-
-  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);
-
-    ElfW(Addr) reloc = static_cast<ElfW(Addr)>(rel->r_offset + load_bias);
-    ElfW(Addr) sym_addr = 0;
-    const char* sym_name = nullptr;
-    ElfW(Addr) addend = get_addend(rel, reloc);
-
-    DEBUG("Processing \"%s\" relocation at index %zd", get_realpath(), idx);
-    if (type == R_GENERIC_NONE) {
-      continue;
-    }
-
-    const ElfW(Sym)* s = nullptr;
-    soinfo* lsi = nullptr;
-
-    if (sym == 0) {
-      // By convention in ld.bfd and lld, an omitted symbol on a TLS relocation
-      // is a reference to the current module.
-      if (is_tls_reloc(type)) {
-        lsi = this;
-      }
-    } else if (ELF_ST_BIND(symtab_[sym].st_info) == STB_LOCAL && is_tls_reloc(type)) {
-      // In certain situations, the Gold linker accesses a TLS symbol using a
-      // relocation to an STB_LOCAL symbol in .dynsym of either STT_SECTION or
-      // STT_TLS type. Bionic doesn't support these relocations, so issue an
-      // error. References:
-      //  - https://groups.google.com/d/topic/generic-abi/dJ4_Y78aQ2M/discussion
-      //  - https://sourceware.org/bugzilla/show_bug.cgi?id=17699
-      s = &symtab_[sym];
-      sym_name = get_string(s->st_name);
-      DL_ERR("unexpected TLS reference to local symbol \"%s\": "
-             "sym type %d, rel type %u (idx %zu of \"%s\")",
-             sym_name, ELF_ST_TYPE(s->st_info), type, idx, get_realpath());
-      return false;
-    } else {
-      sym_name = get_string(symtab_[sym].st_name);
-
-      if (sym == symbol_lookup_cache.sym) {
-        s = symbol_lookup_cache.s;
-        lsi = symbol_lookup_cache.lsi;
-        count_relocation(kRelocSymbolCached);
-      } else {
-        const version_info* vi = nullptr;
-
-        if (!lookup_version_info(version_tracker, sym, sym_name, &vi)) {
-          return false;
-        }
-
-        if (!soinfo_do_lookup(this, sym_name, vi, &lsi, global_group, local_group, &s)) {
-          return false;
-        }
-
-        symbol_lookup_cache.sym = sym;
-        symbol_lookup_cache.s = s;
-        symbol_lookup_cache.lsi = lsi;
-      }
-
-      if (s == nullptr) {
-        // We only allow an undefined symbol if this is a weak reference...
-        s = &symtab_[sym];
-        if (ELF_ST_BIND(s->st_info) != STB_WEAK) {
-          DL_ERR("cannot locate symbol \"%s\" referenced by \"%s\"...", sym_name, get_realpath());
-          return false;
-        }
-
-        /* IHI0044C AAELF 4.5.1.1:
-
-           Libraries are not searched to resolve weak references.
-           It is not an error for a weak reference to remain unsatisfied.
-
-           During linking, the value of an undefined weak reference is:
-           - Zero if the relocation type is absolute
-           - The address of the place if the relocation is pc-relative
-           - The address of nominal base address if the relocation
-             type is base-relative.
-         */
-
-        switch (type) {
-          case R_GENERIC_JUMP_SLOT:
-          case R_GENERIC_ABSOLUTE:
-          case R_GENERIC_GLOB_DAT:
-          case R_GENERIC_RELATIVE:
-          case R_GENERIC_IRELATIVE:
-          case R_GENERIC_TLS_DTPMOD:
-          case R_GENERIC_TLS_DTPREL:
-          case R_GENERIC_TLS_TPREL:
-          case R_GENERIC_TLSDESC:
-#if defined(__x86_64__)
-          case R_X86_64_32:
-#endif
-            /*
-             * The sym_addr was initialized to be zero above, or the relocation
-             * code below does not care about value of sym_addr.
-             * No need to do anything.
-             */
-            break;
-#if defined(__x86_64__)
-          case R_X86_64_PC32:
-            sym_addr = reloc;
-            break;
-#elif defined(__i386__)
-          case R_386_PC32:
-            sym_addr = reloc;
-            break;
-#endif
-          default:
-            DL_ERR("unknown weak reloc type %d @ %p (%zu)", type, rel, idx);
-            return false;
-        }
-      } else { // We got a definition.
-#if !defined(__LP64__)
-        // When relocating dso with text_relocation .text segment is
-        // not executable. We need to restore elf flags before resolving
-        // STT_GNU_IFUNC symbol.
-        bool protect_segments = has_text_relocations &&
-                                lsi == this &&
-                                ELF_ST_TYPE(s->st_info) == STT_GNU_IFUNC;
-        if (protect_segments) {
-          if (phdr_table_protect_segments(phdr, phnum, load_bias) < 0) {
-            DL_ERR("can't protect segments for \"%s\": %s",
-                   get_realpath(), strerror(errno));
-            return false;
-          }
-        }
-#endif
-        if (is_tls_reloc(type)) {
-          if (ELF_ST_TYPE(s->st_info) != STT_TLS) {
-            DL_ERR("reference to non-TLS symbol \"%s\" from TLS relocation in \"%s\"",
-                   sym_name, get_realpath());
-            return false;
-          }
-          if (lsi->get_tls() == nullptr) {
-            DL_ERR("TLS relocation refers to symbol \"%s\" in solib \"%s\" with no TLS segment",
-                   sym_name, lsi->get_realpath());
-            return false;
-          }
-          sym_addr = s->st_value;
-        } else {
-          if (ELF_ST_TYPE(s->st_info) == STT_TLS) {
-            DL_ERR("reference to TLS symbol \"%s\" from non-TLS relocation in \"%s\"",
-                   sym_name, get_realpath());
-            return false;
-          }
-          sym_addr = lsi->resolve_symbol_address(s);
-        }
-#if !defined(__LP64__)
-        if (protect_segments) {
-          if (phdr_table_unprotect_segments(phdr, phnum, load_bias) < 0) {
-            DL_ERR("can't unprotect loadable segments for \"%s\": %s",
-                   get_realpath(), strerror(errno));
-            return false;
-          }
-        }
-#endif
-      }
-      count_relocation(kRelocSymbol);
-    }
-
-    switch (type) {
-      case R_GENERIC_JUMP_SLOT:
-        count_relocation(kRelocAbsolute);
-        TRACE_TYPE(RELO, "RELO JMP_SLOT %16p <- %16p %s\n",
-                   reinterpret_cast<void*>(reloc),
-                   reinterpret_cast<void*>(sym_addr + addend), sym_name);
-
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = (sym_addr + addend);
-        break;
-      case R_GENERIC_ABSOLUTE:
-      case R_GENERIC_GLOB_DAT:
-        count_relocation(kRelocAbsolute);
-        TRACE_TYPE(RELO, "RELO ABSOLUTE/GLOB_DAT %16p <- %16p %s\n",
-                   reinterpret_cast<void*>(reloc),
-                   reinterpret_cast<void*>(sym_addr + addend), sym_name);
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = (sym_addr + addend);
-        break;
-      case R_GENERIC_RELATIVE:
-        count_relocation(kRelocRelative);
-        TRACE_TYPE(RELO, "RELO RELATIVE %16p <- %16p\n",
-                   reinterpret_cast<void*>(reloc),
-                   reinterpret_cast<void*>(load_bias + addend));
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = (load_bias + addend);
-        break;
-      case R_GENERIC_IRELATIVE:
-        count_relocation(kRelocRelative);
-        TRACE_TYPE(RELO, "RELO IRELATIVE %16p <- %16p\n",
-                    reinterpret_cast<void*>(reloc),
-                    reinterpret_cast<void*>(load_bias + addend));
-        // In the linker, ifuncs are called as soon as possible so that string functions work.
-        // We must not call them again. (e.g. On arm32, resolving an ifunc changes the meaning of
-        // the addend from a resolver function to the implementation.)
-        if (!is_linker()) {
-#if !defined(__LP64__)
-          // When relocating dso with text_relocation .text segment is
-          // not executable. We need to restore elf flags for this
-          // particular call.
-          if (has_text_relocations) {
-            if (phdr_table_protect_segments(phdr, phnum, load_bias) < 0) {
-              DL_ERR("can't protect segments for \"%s\": %s",
-                     get_realpath(), strerror(errno));
-              return false;
-            }
-          }
-#endif
-          ElfW(Addr) ifunc_addr = call_ifunc_resolver(load_bias + addend);
-#if !defined(__LP64__)
-          // Unprotect it afterwards...
-          if (has_text_relocations) {
-            if (phdr_table_unprotect_segments(phdr, phnum, load_bias) < 0) {
-              DL_ERR("can't unprotect loadable segments for \"%s\": %s",
-                     get_realpath(), strerror(errno));
-              return false;
-            }
-          }
-#endif
-          *reinterpret_cast<ElfW(Addr)*>(reloc) = ifunc_addr;
-        }
-        break;
-      case R_GENERIC_COPY:
-        // Copy relocations allow read-only data or code in a non-PIE executable to access a
-        // variable from a DSO. The executable reserves extra space in its .bss section, and the
-        // linker copies the variable into the extra space. The executable then exports its copy
-        // to interpose the copy in the DSO.
-        //
-        // Bionic only supports PIE executables, so copy relocations aren't supported. The ARM and
-        // AArch64 ABI documents only allow them for ET_EXEC (non-PIE) objects. See IHI0056B and
-        // IHI0044F.
-        DL_ERR("%s COPY relocations are not supported", get_realpath());
-        return false;
-      case R_GENERIC_TLS_TPREL:
-        count_relocation(kRelocRelative);
-        {
-          ElfW(Addr) tpoff = 0;
-          if (lsi == nullptr) {
-            // Unresolved weak relocation. Leave tpoff at 0 to resolve
-            // &weak_tls_symbol to __get_tls().
-          } else {
-            CHECK(lsi->get_tls() != nullptr); // We rejected a missing TLS segment above.
-            const TlsModule& mod = get_tls_module(lsi->get_tls()->module_id);
-            if (mod.static_offset != SIZE_MAX) {
-              tpoff += mod.static_offset - tls_tp_base;
-            } else {
-              DL_ERR("TLS symbol \"%s\" in dlopened \"%s\" referenced from \"%s\" using IE access model",
-                     sym_name, lsi->get_realpath(), get_realpath());
-              return false;
-            }
-          }
-          tpoff += sym_addr + addend;
-          TRACE_TYPE(RELO, "RELO TLS_TPREL %16p <- %16p %s\n",
-                     reinterpret_cast<void*>(reloc),
-                     reinterpret_cast<void*>(tpoff), sym_name);
-          *reinterpret_cast<ElfW(Addr)*>(reloc) = tpoff;
-        }
-        break;
-      case R_GENERIC_TLS_DTPMOD:
-        count_relocation(kRelocRelative);
-        {
-          size_t module_id = 0;
-          if (lsi == nullptr) {
-            // Unresolved weak relocation. Evaluate the module ID to 0.
-          } else {
-            CHECK(lsi->get_tls() != nullptr); // We rejected a missing TLS segment above.
-            module_id = lsi->get_tls()->module_id;
-          }
-          TRACE_TYPE(RELO, "RELO TLS_DTPMOD %16p <- %zu %s\n",
-                     reinterpret_cast<void*>(reloc), module_id, sym_name);
-          *reinterpret_cast<ElfW(Addr)*>(reloc) = module_id;
-        }
-        break;
-      case R_GENERIC_TLS_DTPREL:
-        count_relocation(kRelocRelative);
-        TRACE_TYPE(RELO, "RELO TLS_DTPREL %16p <- %16p %s\n",
-                   reinterpret_cast<void*>(reloc),
-                   reinterpret_cast<void*>(sym_addr + addend), sym_name);
-        *reinterpret_cast<ElfW(Addr)*>(reloc) = sym_addr + addend;
-        break;
-
-#if defined(__aarch64__)
-      // Bionic currently only implements TLSDESC for arm64. This implementation should work with
-      // other architectures, as long as the resolver functions are implemented.
-      case R_GENERIC_TLSDESC:
-        count_relocation(kRelocRelative);
-        {
-          TlsDescriptor* desc = reinterpret_cast<TlsDescriptor*>(reloc);
-          if (lsi == nullptr) {
-            // Unresolved weak relocation.
-            desc->func = tlsdesc_resolver_unresolved_weak;
-            desc->arg = addend;
-            TRACE_TYPE(RELO, "RELO TLSDESC %16p <- unresolved weak 0x%zx %s\n",
-                       reinterpret_cast<void*>(reloc), static_cast<size_t>(addend), sym_name);
-          } else {
-            CHECK(lsi->get_tls() != nullptr); // We rejected a missing TLS segment above.
-            size_t module_id = lsi->get_tls()->module_id;
-            const TlsModule& mod = get_tls_module(module_id);
-            if (mod.static_offset != SIZE_MAX) {
-              desc->func = tlsdesc_resolver_static;
-              desc->arg = mod.static_offset - tls_tp_base + sym_addr + addend;
-              TRACE_TYPE(RELO, "RELO TLSDESC %16p <- static (0x%zx - 0x%zx + 0x%zx + 0x%zx) %s\n",
-                         reinterpret_cast<void*>(reloc), mod.static_offset, tls_tp_base,
-                         static_cast<size_t>(sym_addr), static_cast<size_t>(addend), sym_name);
-            } else {
-              tlsdesc_args_.push_back({
-                .generation = mod.first_generation,
-                .index.module_id = module_id,
-                .index.offset = sym_addr + addend,
-              });
-              // Defer the TLSDESC relocation until the address of the TlsDynamicResolverArg object
-              // is finalized.
-              deferred_tlsdesc_relocs.push_back({ desc, tlsdesc_args_.size() - 1 });
-              const TlsDynamicResolverArg& desc_arg = tlsdesc_args_.back();
-              TRACE_TYPE(RELO, "RELO TLSDESC %16p <- dynamic (gen %zu, mod %zu, off %zu) %s",
-                         reinterpret_cast<void*>(reloc), desc_arg.generation,
-                         desc_arg.index.module_id, desc_arg.index.offset, sym_name);
-            }
-          }
-        }
-        break;
-#endif  // defined(__aarch64__)
-
-#if defined(__x86_64__)
-      case R_X86_64_32:
-        count_relocation(kRelocAbsolute);
-        TRACE_TYPE(RELO, "RELO R_X86_64_32 %08zx <- +%08zx %s", static_cast<size_t>(reloc),
-                   static_cast<size_t>(sym_addr), sym_name);
-        *reinterpret_cast<Elf32_Addr*>(reloc) = sym_addr + addend;
-        break;
-      case R_X86_64_PC32:
-        count_relocation(kRelocRelative);
-        TRACE_TYPE(RELO, "RELO R_X86_64_PC32 %08zx <- +%08zx (%08zx - %08zx) %s",
-                   static_cast<size_t>(reloc), static_cast<size_t>(sym_addr - reloc),
-                   static_cast<size_t>(sym_addr), static_cast<size_t>(reloc), sym_name);
-        *reinterpret_cast<Elf32_Addr*>(reloc) = sym_addr + addend - reloc;
-        break;
-#elif defined(__i386__)
-      case R_386_PC32:
-        count_relocation(kRelocRelative);
-        TRACE_TYPE(RELO, "RELO R_386_PC32 %08x <- +%08x (%08x - %08x) %s",
-                   reloc, (sym_addr - reloc), sym_addr, reloc, sym_name);
-        *reinterpret_cast<ElfW(Addr)*>(reloc) += (sym_addr - reloc);
-        break;
-#endif
-      default:
-        DL_ERR("unknown reloc type %d @ %p (%zu)", type, rel, idx);
-        return false;
-    }
-  }
-
-#if defined(__aarch64__)
-  // Bionic currently only implements TLSDESC for arm64.
-  for (const std::pair<TlsDescriptor*, size_t>& pair : deferred_tlsdesc_relocs) {
-    TlsDescriptor* desc = pair.first;
-    desc->func = tlsdesc_resolver_dynamic;
-    desc->arg = reinterpret_cast<size_t>(&tlsdesc_args_[pair.second]);
-  }
-#endif
-
-  return true;
-}
-#endif  // !defined(__mips__)
-
 // An empty list of soinfos
 static soinfo_list_t g_empty_list;
 
@@ -3835,7 +3325,7 @@
   return true;
 }
 
-bool soinfo::link_image(const soinfo_list_t& global_group, const soinfo_list_t& local_group,
+bool soinfo::link_image(const SymbolLookupList& lookup_list, soinfo* local_group_root,
                         const android_dlextinfo* extinfo, size_t* relro_fd_offset) {
   if (is_image_linked()) {
     // already linked.
@@ -3847,7 +3337,7 @@
                          get_realpath(), reinterpret_cast<void*>(base));
   }
 
-  local_group_root_ = local_group.front();
+  local_group_root_ = local_group_root;
   if (local_group_root_ == nullptr) {
     local_group_root_ = this;
   }
@@ -3856,12 +3346,6 @@
     target_sdk_version_ = get_application_target_sdk_version();
   }
 
-  VersionTracker version_tracker;
-
-  if (!version_tracker.init(this)) {
-    return false;
-  }
-
 #if !defined(__LP64__)
   if (has_text_relocations) {
     // Fail if app is targeting M or above.
@@ -3886,78 +3370,9 @@
   }
 #endif
 
-  if (android_relocs_ != nullptr) {
-    // check signature
-    if (android_relocs_size_ > 3 &&
-        android_relocs_[0] == 'A' &&
-        android_relocs_[1] == 'P' &&
-        android_relocs_[2] == 'S' &&
-        android_relocs_[3] == '2') {
-      DEBUG("[ android relocating %s ]", get_realpath());
-
-      bool relocated = false;
-      const uint8_t* packed_relocs = android_relocs_ + 4;
-      const size_t packed_relocs_size = android_relocs_size_ - 4;
-
-      relocated = relocate(
-          version_tracker,
-          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 (relr_ != nullptr) {
-    DEBUG("[ relocating %s relr ]", get_realpath());
-    if (!relocate_relr()) {
-      return false;
-    }
-  }
-
-#if defined(USE_RELA)
-  if (rela_ != nullptr) {
-    DEBUG("[ relocating %s rela ]", get_realpath());
-    if (!relocate(version_tracker,
-            plain_reloc_iterator(rela_, rela_count_), global_group, local_group)) {
-      return false;
-    }
-  }
-  if (plt_rela_ != nullptr) {
-    DEBUG("[ relocating %s plt rela ]", get_realpath());
-    if (!relocate(version_tracker,
-            plain_reloc_iterator(plt_rela_, plt_rela_count_), global_group, local_group)) {
-      return false;
-    }
-  }
-#else
-  if (rel_ != nullptr) {
-    DEBUG("[ relocating %s rel ]", get_realpath());
-    if (!relocate(version_tracker,
-            plain_reloc_iterator(rel_, rel_count_), global_group, local_group)) {
-      return false;
-    }
-  }
-  if (plt_rel_ != nullptr) {
-    DEBUG("[ relocating %s plt rel ]", get_realpath());
-    if (!relocate(version_tracker,
-            plain_reloc_iterator(plt_rel_, plt_rel_count_), global_group, local_group)) {
-      return false;
-    }
-  }
-#endif
-
-#if defined(__mips__)
-  if (!mips_relocate_got(version_tracker, global_group, local_group)) {
+  if (!relocate(lookup_list)) {
     return false;
   }
-#endif
 
   DEBUG("[ finished linking %s ]", get_realpath());
 
diff --git a/linker/linker.h b/linker/linker.h
index 16c65a1..80c11d0 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -85,23 +85,6 @@
   DISALLOW_COPY_AND_ASSIGN(VersionTracker);
 };
 
-bool soinfo_do_lookup(soinfo* si_from, const char* name, const version_info* vi,
-                      soinfo** si_found_in, const soinfo_list_t& global_group,
-                      const soinfo_list_t& local_group, const ElfW(Sym)** symbol);
-
-enum RelocationKind {
-  kRelocAbsolute = 0,
-  kRelocRelative,
-  kRelocCopy,
-  kRelocSymbol,
-  kRelocSymbolCached,
-  kRelocMax
-};
-
-void count_relocation(RelocationKind kind);
-
-void print_linker_stats();
-
 soinfo* get_libdl_info(const soinfo& linker_si);
 
 soinfo* find_containing_library(const void* p);
@@ -205,4 +188,6 @@
   bool must_use_address = false;
 };
 
+int get_application_target_sdk_version();
 ElfW(Versym) find_verdef_version_index(const soinfo* si, const version_info* vi);
+bool validate_verdef_section(const soinfo* si);
diff --git a/linker/linker_gnu_hash.h b/linker/linker_gnu_hash.h
new file mode 100644
index 0000000..8375743
--- /dev/null
+++ b/linker/linker_gnu_hash.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ * 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.
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <stdint.h>
+
+#include <utility>
+
+static inline std::pair<uint32_t, uint32_t> calculate_gnu_hash(const char* name) {
+  uint32_t h = 5381;
+  const uint8_t* name_bytes = reinterpret_cast<const uint8_t*>(name);
+  #pragma unroll 8
+  while (*name_bytes != 0) {
+    h += (h << 5) + *name_bytes++; // h*33 + c = h + h * 32 + c = h + h << 5 + c
+  }
+  return { h, reinterpret_cast<const char*>(name_bytes) - name };
+}
diff --git a/linker/linker_main.cpp b/linker/linker_main.cpp
index 8ba947f..98af54a 100644
--- a/linker/linker_main.cpp
+++ b/linker/linker_main.cpp
@@ -37,6 +37,7 @@
 #include "linker_gdb_support.h"
 #include "linker_globals.h"
 #include "linker_phdr.h"
+#include "linker_relocate.h"
 #include "linker_tls.h"
 #include "linker_utils.h"
 
@@ -168,7 +169,7 @@
   si->load_bias = get_elf_exec_load_bias(ehdr_vdso);
 
   si->prelink_image();
-  si->link_image(g_empty_list, soinfo_list_t::make_list(si), nullptr, nullptr);
+  si->link_image(SymbolLookupList(si), si, nullptr, nullptr);
   // prevents accidental unloads...
   si->set_dt_flags_1(si->get_dt_flags_1() | DF_1_NODELETE);
   si->set_linked();
@@ -463,7 +464,7 @@
                       &namespaces)) {
     __linker_cannot_link(g_argv[0]);
   } else if (needed_libraries_count == 0) {
-    if (!si->link_image(g_empty_list, soinfo_list_t::make_list(si), nullptr, nullptr)) {
+    if (!si->link_image(SymbolLookupList(si), si, nullptr, nullptr)) {
       __linker_cannot_link(g_argv[0]);
     }
     si->increment_ref_count();
@@ -668,14 +669,7 @@
 
   // Prelink the linker so we can access linker globals.
   if (!tmp_linker_so.prelink_image()) __linker_cannot_link(args.argv[0]);
-
-  // This might not be obvious... The reasons why we pass g_empty_list
-  // in place of local_group here are (1) we do not really need it, because
-  // linker is built with DT_SYMBOLIC and therefore relocates its symbols against
-  // itself without having to look into local_group and (2) allocators
-  // are not yet initialized, and therefore we cannot use linked_list.push_*
-  // functions at this point.
-  if (!tmp_linker_so.link_image(g_empty_list, g_empty_list, nullptr, nullptr)) __linker_cannot_link(args.argv[0]);
+  if (!tmp_linker_so.link_image(SymbolLookupList(&tmp_linker_so), &tmp_linker_so, nullptr, nullptr)) __linker_cannot_link(args.argv[0]);
 
   return __linker_init_post_relocation(args, tmp_linker_so);
 }
diff --git a/linker/linker_reloc_iterators.h b/linker/linker_reloc_iterators.h
index b162684..c6a8cf6 100644
--- a/linker/linker_reloc_iterators.h
+++ b/linker/linker_reloc_iterators.h
@@ -28,147 +28,82 @@
 
 #pragma once
 
-#include "linker.h"
-
 #include <string.h>
 
+#include "linker.h"
+#include "linker_sleb128.h"
+
 const size_t RELOCATION_GROUPED_BY_INFO_FLAG = 1;
 const size_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2;
 const size_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4;
 const size_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8;
 
-class plain_reloc_iterator {
 #if defined(USE_RELA)
-  typedef ElfW(Rela) rel_t;
+typedef ElfW(Rela) rel_t;
 #else
-  typedef ElfW(Rel) rel_t;
+typedef ElfW(Rel) rel_t;
 #endif
- public:
-  plain_reloc_iterator(rel_t* rel_array, size_t count)
-      : begin_(rel_array), end_(begin_ + count), current_(begin_) {}
 
-  bool has_next() {
-    return current_ < end_;
-  }
+template <typename F>
+inline bool for_all_packed_relocs(sleb128_decoder decoder, F&& callback) {
+  const size_t num_relocs = decoder.pop_front();
 
-  rel_t* next() {
-    return current_++;
-  }
- private:
-  rel_t* const begin_;
-  rel_t* const end_;
-  rel_t* current_;
+  rel_t reloc = {
+    .r_offset = decoder.pop_front(),
+  };
 
-  DISALLOW_COPY_AND_ASSIGN(plain_reloc_iterator);
-};
+  for (size_t idx = 0; idx < num_relocs; ) {
+    const size_t group_size = decoder.pop_front();
+    const size_t group_flags = decoder.pop_front();
 
-template <typename decoder_t>
-class packed_reloc_iterator {
+    size_t group_r_offset_delta = 0;
+
+    if (group_flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) {
+      group_r_offset_delta = decoder.pop_front();
+    }
+    if (group_flags & RELOCATION_GROUPED_BY_INFO_FLAG) {
+      reloc.r_info = decoder.pop_front();
+    }
+
 #if defined(USE_RELA)
-  typedef ElfW(Rela) rel_t;
+    const size_t group_flags_reloc = group_flags & (RELOCATION_GROUP_HAS_ADDEND_FLAG |
+                                                    RELOCATION_GROUPED_BY_ADDEND_FLAG);
+    if (group_flags_reloc == RELOCATION_GROUP_HAS_ADDEND_FLAG) {
+      // Each relocation has an addend. This is the default situation with lld's current encoder.
+    } else if (group_flags_reloc == (RELOCATION_GROUP_HAS_ADDEND_FLAG |
+                                     RELOCATION_GROUPED_BY_ADDEND_FLAG)) {
+      reloc.r_addend += decoder.pop_front();
+    } else {
+      reloc.r_addend = 0;
+    }
 #else
-  typedef ElfW(Rel) rel_t;
+    if (__predict_false(group_flags & RELOCATION_GROUP_HAS_ADDEND_FLAG)) {
+      // This platform does not support rela, and yet we have it encoded in android_rel section.
+      async_safe_fatal("unexpected r_addend in android.rel section");
+    }
 #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;
+    for (size_t i = 0; i < group_size; ++i) {
+      if (group_flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) {
+        reloc.r_offset += group_r_offset_delta;
+      } else {
+        reloc.r_offset += decoder.pop_front();
+      }
+      if ((group_flags & RELOCATION_GROUPED_BY_INFO_FLAG) == 0) {
+        reloc.r_info = decoder.pop_front();
+      }
+#if defined(USE_RELA)
+      if (group_flags_reloc == RELOCATION_GROUP_HAS_ADDEND_FLAG) {
+        reloc.r_addend += decoder.pop_front();
+      }
+#endif
+      if (!callback(reloc)) {
+        return false;
       }
     }
 
-    if (is_relocation_grouped_by_offset_delta()) {
-      reloc_.r_offset += group_r_offset_delta_;
-    } else {
-      reloc_.r_offset += decoder_.pop_front();
-    }
-
-    if (!is_relocation_grouped_by_info()) {
-      reloc_.r_info = decoder_.pop_front();
-    }
-
-#if defined(USE_RELA)
-    if (is_relocation_group_has_addend() &&
-        !is_relocation_grouped_by_addend()) {
-      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 (is_relocation_grouped_by_offset_delta()) {
-      group_r_offset_delta_ = decoder_.pop_front();
-    }
-
-    if (is_relocation_grouped_by_info()) {
-      reloc_.r_info = decoder_.pop_front();
-    }
-
-    if (is_relocation_group_has_addend() &&
-        is_relocation_grouped_by_addend()) {
-#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 (!is_relocation_group_has_addend()) {
-      reloc_.r_addend = 0;
-#endif
-    }
-
-    relocation_group_index_ = 0;
-    return true;
+    idx += group_size;
   }
 
-  bool is_relocation_grouped_by_info() {
-    return (group_flags_ & RELOCATION_GROUPED_BY_INFO_FLAG) != 0;
-  }
-
-  bool is_relocation_grouped_by_offset_delta() {
-    return (group_flags_ & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0;
-  }
-
-  bool is_relocation_grouped_by_addend() {
-    return (group_flags_ & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0;
-  }
-
-  bool is_relocation_group_has_addend() {
-    return (group_flags_ & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0;
-  }
-
-  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_;
-};
+  return true;
+}
diff --git a/linker/linker_relocate.cpp b/linker/linker_relocate.cpp
new file mode 100644
index 0000000..7bf12d3
--- /dev/null
+++ b/linker/linker_relocate.cpp
@@ -0,0 +1,658 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ * 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.
+ *
+ * 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.
+ */
+
+#include "linker_relocate.h"
+
+#include <elf.h>
+#include <link.h>
+
+#include <type_traits>
+
+#include "linker.h"
+#include "linker_debug.h"
+#include "linker_globals.h"
+#include "linker_gnu_hash.h"
+#include "linker_phdr.h"
+#include "linker_relocs.h"
+#include "linker_reloc_iterators.h"
+#include "linker_sleb128.h"
+#include "linker_soinfo.h"
+#include "private/bionic_globals.h"
+
+static bool is_tls_reloc(ElfW(Word) type) {
+  switch (type) {
+    case R_GENERIC_TLS_DTPMOD:
+    case R_GENERIC_TLS_DTPREL:
+    case R_GENERIC_TLS_TPREL:
+    case R_GENERIC_TLSDESC:
+      return true;
+    default:
+      return false;
+  }
+}
+
+class Relocator {
+ public:
+  Relocator(const VersionTracker& version_tracker, const SymbolLookupList& lookup_list)
+      : version_tracker(version_tracker), lookup_list(lookup_list)
+  {}
+
+  soinfo* si = nullptr;
+  const char* si_strtab = nullptr;
+  size_t si_strtab_size = 0;
+  ElfW(Sym)* si_symtab = nullptr;
+
+  const VersionTracker& version_tracker;
+  const SymbolLookupList& lookup_list;
+
+  // Cache key
+  ElfW(Word) cache_sym_val = 0;
+  // Cache value
+  const ElfW(Sym)* cache_sym = nullptr;
+  soinfo* cache_si = nullptr;
+
+  std::vector<TlsDynamicResolverArg>* tlsdesc_args;
+  std::vector<std::pair<TlsDescriptor*, size_t>> deferred_tlsdesc_relocs;
+  size_t tls_tp_base = 0;
+
+  __attribute__((always_inline))
+  const char* get_string(ElfW(Word) index) {
+    if (__predict_false(index >= si_strtab_size)) {
+      async_safe_fatal("%s: strtab out of bounds error; STRSZ=%zd, name=%d",
+                       si->get_realpath(), si_strtab_size, index);
+    }
+    return si_strtab + index;
+  }
+};
+
+template <bool DoLogging>
+__attribute__((always_inline))
+static inline bool lookup_symbol(Relocator& relocator, uint32_t r_sym, const char* sym_name,
+                                 soinfo** found_in, const ElfW(Sym)** sym) {
+  if (r_sym == relocator.cache_sym_val) {
+    *found_in = relocator.cache_si;
+    *sym = relocator.cache_sym;
+    count_relocation_if<DoLogging>(kRelocSymbolCached);
+  } else {
+    const version_info* vi = nullptr;
+    if (!relocator.si->lookup_version_info(relocator.version_tracker, r_sym, sym_name, &vi)) {
+      return false;
+    }
+
+    soinfo* local_found_in = nullptr;
+    const ElfW(Sym)* local_sym = soinfo_do_lookup(sym_name, vi, &local_found_in, relocator.lookup_list);
+
+    relocator.cache_sym_val = r_sym;
+    relocator.cache_si = local_found_in;
+    relocator.cache_sym = local_sym;
+    *found_in = local_found_in;
+    *sym = local_sym;
+  }
+
+  if (*sym == nullptr) {
+    if (ELF_ST_BIND(relocator.si_symtab[r_sym].st_info) != STB_WEAK) {
+      DL_ERR("cannot locate symbol \"%s\" referenced by \"%s\"...", sym_name, relocator.si->get_realpath());
+      return false;
+    }
+  }
+
+  count_relocation_if<DoLogging>(kRelocSymbol);
+  return true;
+}
+
+enum class RelocMode {
+  // Fast path for JUMP_SLOT relocations.
+  JumpTable,
+  // Fast path for typical relocations: ABSOLUTE, GLOB_DAT, or RELATIVE.
+  Typical,
+  // Handle all relocation types, relocations in text sections, and statistics/tracing.
+  General,
+};
+
+struct linker_stats_t {
+  int count[kRelocMax];
+};
+
+static linker_stats_t linker_stats;
+
+void count_relocation(RelocationKind kind) {
+  ++linker_stats.count[kind];
+}
+
+void print_linker_stats() {
+  PRINT("RELO STATS: %s: %d abs, %d rel, %d symbol (%d cached)",
+         g_argv[0],
+         linker_stats.count[kRelocAbsolute],
+         linker_stats.count[kRelocRelative],
+         linker_stats.count[kRelocSymbol],
+         linker_stats.count[kRelocSymbolCached]);
+}
+
+static bool process_relocation_general(Relocator& relocator, const rel_t& reloc);
+
+template <RelocMode Mode>
+__attribute__((always_inline))
+static bool process_relocation_impl(Relocator& relocator, const rel_t& reloc) {
+  constexpr bool IsGeneral = Mode == RelocMode::General;
+
+  void* const rel_target = reinterpret_cast<void*>(reloc.r_offset + relocator.si->load_bias);
+  const uint32_t r_type = ELFW(R_TYPE)(reloc.r_info);
+  const uint32_t r_sym = ELFW(R_SYM)(reloc.r_info);
+
+  soinfo* found_in = nullptr;
+  const ElfW(Sym)* sym = nullptr;
+  const char* sym_name = nullptr;
+  ElfW(Addr) sym_addr = 0;
+
+  if (r_sym != 0) {
+    sym_name = relocator.get_string(relocator.si_symtab[r_sym].st_name);
+  }
+
+  // While relocating a DSO with text relocations (obsolete and 32-bit only), the .text segment is
+  // writable (but not executable). To call an ifunc, temporarily remap the segment as executable
+  // (but not writable). Then switch it back to continue applying relocations in the segment.
+#if defined(__LP64__)
+  const bool handle_text_relocs = false;
+  auto protect_segments = []() { return true; };
+  auto unprotect_segments = []() { return true; };
+#else
+  const bool handle_text_relocs = IsGeneral && relocator.si->has_text_relocations;
+  auto protect_segments = [&]() {
+    // Make .text executable.
+    if (phdr_table_protect_segments(relocator.si->phdr, relocator.si->phnum,
+                                    relocator.si->load_bias) < 0) {
+      DL_ERR("can't protect segments for \"%s\": %s",
+             relocator.si->get_realpath(), strerror(errno));
+      return false;
+    }
+    return true;
+  };
+  auto unprotect_segments = [&]() {
+    // Make .text writable.
+    if (phdr_table_unprotect_segments(relocator.si->phdr, relocator.si->phnum,
+                                      relocator.si->load_bias) < 0) {
+      DL_ERR("can't unprotect loadable segments for \"%s\": %s",
+             relocator.si->get_realpath(), strerror(errno));
+      return false;
+    }
+    return true;
+  };
+#endif
+
+  auto trace_reloc = [](const char* fmt, ...) __printflike(2, 3) {
+    if (IsGeneral &&
+        g_ld_debug_verbosity > LINKER_VERBOSITY_TRACE &&
+        DO_TRACE_RELO) {
+      va_list ap;
+      va_start(ap, fmt);
+      linker_log_va_list(LINKER_VERBOSITY_TRACE, fmt, ap);
+      va_end(ap);
+    }
+  };
+
+#if defined(USE_RELA)
+  auto get_addend_rel   = [&]() -> ElfW(Addr) { return reloc.r_addend; };
+  auto get_addend_norel = [&]() -> ElfW(Addr) { return reloc.r_addend; };
+#else
+  auto get_addend_rel   = [&]() -> ElfW(Addr) { return *static_cast<ElfW(Addr)*>(rel_target); };
+  auto get_addend_norel = [&]() -> ElfW(Addr) { return 0; };
+#endif
+
+  if (IsGeneral && is_tls_reloc(r_type)) {
+    if (r_sym == 0) {
+      // By convention in ld.bfd and lld, an omitted symbol on a TLS relocation
+      // is a reference to the current module.
+      found_in = relocator.si;
+    } else if (ELF_ST_BIND(relocator.si_symtab[r_sym].st_info) == STB_LOCAL) {
+      // In certain situations, the Gold linker accesses a TLS symbol using a
+      // relocation to an STB_LOCAL symbol in .dynsym of either STT_SECTION or
+      // STT_TLS type. Bionic doesn't support these relocations, so issue an
+      // error. References:
+      //  - https://groups.google.com/d/topic/generic-abi/dJ4_Y78aQ2M/discussion
+      //  - https://sourceware.org/bugzilla/show_bug.cgi?id=17699
+      sym = &relocator.si_symtab[r_sym];
+      DL_ERR("unexpected TLS reference to local symbol \"%s\" in \"%s\": sym type %d, rel type %u",
+             sym_name, relocator.si->get_realpath(), ELF_ST_TYPE(sym->st_info), r_type);
+      return false;
+    } else if (!lookup_symbol<IsGeneral>(relocator, r_sym, sym_name, &found_in, &sym)) {
+      return false;
+    }
+    if (found_in != nullptr && found_in->get_tls() == nullptr) {
+      // sym_name can be nullptr if r_sym is 0. A linker should never output an ELF file like this.
+      DL_ERR("TLS relocation refers to symbol \"%s\" in solib \"%s\" with no TLS segment",
+             sym_name, found_in->get_realpath());
+      return false;
+    }
+    if (sym != nullptr) {
+      if (ELF_ST_TYPE(sym->st_info) != STT_TLS) {
+        // A toolchain should never output a relocation like this.
+        DL_ERR("reference to non-TLS symbol \"%s\" from TLS relocation in \"%s\"",
+               sym_name, relocator.si->get_realpath());
+        return false;
+      }
+      sym_addr = sym->st_value;
+    }
+  } else {
+    if (r_sym == 0) {
+      // Do nothing.
+    } else {
+      if (!lookup_symbol<IsGeneral>(relocator, r_sym, sym_name, &found_in, &sym)) return false;
+      if (sym != nullptr) {
+        const bool should_protect_segments = handle_text_relocs &&
+                                             found_in == relocator.si &&
+                                             ELF_ST_TYPE(sym->st_info) == STT_GNU_IFUNC;
+        if (should_protect_segments && !protect_segments()) return false;
+        sym_addr = found_in->resolve_symbol_address(sym);
+        if (should_protect_segments && !unprotect_segments()) return false;
+      } else if constexpr (IsGeneral) {
+        // A weak reference to an undefined symbol. We typically use a zero symbol address, but
+        // use the relocation base for PC-relative relocations, so that the value written is zero.
+        switch (r_type) {
+#if defined(__x86_64__)
+          case R_X86_64_PC32:
+            sym_addr = reinterpret_cast<ElfW(Addr)>(rel_target);
+            break;
+#elif defined(__i386__)
+          case R_386_PC32:
+            sym_addr = reinterpret_cast<ElfW(Addr)>(rel_target);
+            break;
+#endif
+        }
+      }
+    }
+  }
+
+  if constexpr (IsGeneral || Mode == RelocMode::JumpTable) {
+    if (r_type == R_GENERIC_JUMP_SLOT) {
+      count_relocation_if<IsGeneral>(kRelocAbsolute);
+      const ElfW(Addr) result = sym_addr + get_addend_norel();
+      trace_reloc("RELO JMP_SLOT %16p <- %16p %s",
+                  rel_target, reinterpret_cast<void*>(result), sym_name);
+      *static_cast<ElfW(Addr)*>(rel_target) = result;
+      return true;
+    }
+  }
+
+  if constexpr (IsGeneral || Mode == RelocMode::Typical) {
+    // Almost all dynamic relocations are of one of these types, and most will be
+    // R_GENERIC_ABSOLUTE. The platform typically uses RELR instead, but R_GENERIC_RELATIVE is
+    // common in non-platform binaries.
+    if (r_type == R_GENERIC_ABSOLUTE) {
+      count_relocation_if<IsGeneral>(kRelocAbsolute);
+      const ElfW(Addr) result = sym_addr + get_addend_rel();
+      trace_reloc("RELO ABSOLUTE %16p <- %16p %s",
+                  rel_target, reinterpret_cast<void*>(result), sym_name);
+      *static_cast<ElfW(Addr)*>(rel_target) = result;
+      return true;
+    } else if (r_type == R_GENERIC_GLOB_DAT) {
+      // The i386 psABI specifies that R_386_GLOB_DAT doesn't have an addend. The ARM ELF ABI
+      // document (IHI0044F) specifies that R_ARM_GLOB_DAT has an addend, but Bionic isn't adding
+      // it.
+      count_relocation_if<IsGeneral>(kRelocAbsolute);
+      const ElfW(Addr) result = sym_addr + get_addend_norel();
+      trace_reloc("RELO GLOB_DAT %16p <- %16p %s",
+                  rel_target, reinterpret_cast<void*>(result), sym_name);
+      *static_cast<ElfW(Addr)*>(rel_target) = result;
+      return true;
+    } else if (r_type == R_GENERIC_RELATIVE) {
+      // In practice, r_sym is always zero, but if it weren't, the linker would still look up the
+      // referenced symbol (and abort if the symbol isn't found), even though it isn't used.
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      const ElfW(Addr) result = relocator.si->load_bias + get_addend_rel();
+      trace_reloc("RELO RELATIVE %16p <- %16p",
+                  rel_target, reinterpret_cast<void*>(result));
+      *static_cast<ElfW(Addr)*>(rel_target) = result;
+      return true;
+    }
+  }
+
+  if constexpr (!IsGeneral) {
+    // Almost all relocations are handled above. Handle the remaining relocations below, in a
+    // separate function call. The symbol lookup will be repeated, but the result should be served
+    // from the 1-symbol lookup cache.
+    return process_relocation_general(relocator, reloc);
+  }
+
+  switch (r_type) {
+    case R_GENERIC_IRELATIVE:
+      // In the linker, ifuncs are called as soon as possible so that string functions work. We must
+      // not call them again. (e.g. On arm32, resolving an ifunc changes the meaning of the addend
+      // from a resolver function to the implementation.)
+      if (!relocator.si->is_linker()) {
+        count_relocation_if<IsGeneral>(kRelocRelative);
+        const ElfW(Addr) ifunc_addr = relocator.si->load_bias + get_addend_rel();
+        trace_reloc("RELO IRELATIVE %16p <- %16p",
+                    rel_target, reinterpret_cast<void*>(ifunc_addr));
+        if (handle_text_relocs && !protect_segments()) return false;
+        const ElfW(Addr) result = call_ifunc_resolver(ifunc_addr);
+        if (handle_text_relocs && !unprotect_segments()) return false;
+        *static_cast<ElfW(Addr)*>(rel_target) = result;
+      }
+      break;
+    case R_GENERIC_COPY:
+      // Copy relocations allow read-only data or code in a non-PIE executable to access a
+      // variable from a DSO. The executable reserves extra space in its .bss section, and the
+      // linker copies the variable into the extra space. The executable then exports its copy
+      // to interpose the copy in the DSO.
+      //
+      // Bionic only supports PIE executables, so copy relocations aren't supported. The ARM and
+      // AArch64 ABI documents only allow them for ET_EXEC (non-PIE) objects. See IHI0056B and
+      // IHI0044F.
+      DL_ERR("%s COPY relocations are not supported", relocator.si->get_realpath());
+      return false;
+    case R_GENERIC_TLS_TPREL:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        ElfW(Addr) tpoff = 0;
+        if (found_in == nullptr) {
+          // Unresolved weak relocation. Leave tpoff at 0 to resolve
+          // &weak_tls_symbol to __get_tls().
+        } else {
+          CHECK(found_in->get_tls() != nullptr); // We rejected a missing TLS segment above.
+          const TlsModule& mod = get_tls_module(found_in->get_tls()->module_id);
+          if (mod.static_offset != SIZE_MAX) {
+            tpoff += mod.static_offset - relocator.tls_tp_base;
+          } else {
+            DL_ERR("TLS symbol \"%s\" in dlopened \"%s\" referenced from \"%s\" using IE access model",
+                   sym_name, found_in->get_realpath(), relocator.si->get_realpath());
+            return false;
+          }
+        }
+        tpoff += sym_addr + get_addend_rel();
+        trace_reloc("RELO TLS_TPREL %16p <- %16p %s",
+                    rel_target, reinterpret_cast<void*>(tpoff), sym_name);
+        *static_cast<ElfW(Addr)*>(rel_target) = tpoff;
+      }
+      break;
+    case R_GENERIC_TLS_DTPMOD:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        size_t module_id = 0;
+        if (found_in == nullptr) {
+          // Unresolved weak relocation. Evaluate the module ID to 0.
+        } else {
+          CHECK(found_in->get_tls() != nullptr); // We rejected a missing TLS segment above.
+          module_id = found_in->get_tls()->module_id;
+        }
+        trace_reloc("RELO TLS_DTPMOD %16p <- %zu %s",
+                    rel_target, module_id, sym_name);
+        *static_cast<ElfW(Addr)*>(rel_target) = module_id;
+      }
+      break;
+    case R_GENERIC_TLS_DTPREL:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        const ElfW(Addr) result = sym_addr + get_addend_rel();
+        trace_reloc("RELO TLS_DTPREL %16p <- %16p %s",
+                    rel_target, reinterpret_cast<void*>(result), sym_name);
+        *static_cast<ElfW(Addr)*>(rel_target) = result;
+      }
+      break;
+
+#if defined(__aarch64__)
+    // Bionic currently only implements TLSDESC for arm64. This implementation should work with
+    // other architectures, as long as the resolver functions are implemented.
+    case R_GENERIC_TLSDESC:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        ElfW(Addr) addend = reloc.r_addend;
+        TlsDescriptor* desc = static_cast<TlsDescriptor*>(rel_target);
+        if (found_in == nullptr) {
+          // Unresolved weak relocation.
+          desc->func = tlsdesc_resolver_unresolved_weak;
+          desc->arg = addend;
+          trace_reloc("RELO TLSDESC %16p <- unresolved weak, addend 0x%zx %s",
+                      rel_target, static_cast<size_t>(addend), sym_name);
+        } else {
+          CHECK(found_in->get_tls() != nullptr); // We rejected a missing TLS segment above.
+          size_t module_id = found_in->get_tls()->module_id;
+          const TlsModule& mod = get_tls_module(module_id);
+          if (mod.static_offset != SIZE_MAX) {
+            desc->func = tlsdesc_resolver_static;
+            desc->arg = mod.static_offset - relocator.tls_tp_base + sym_addr + addend;
+            trace_reloc("RELO TLSDESC %16p <- static (0x%zx - 0x%zx + 0x%zx + 0x%zx) %s",
+                        rel_target, mod.static_offset, relocator.tls_tp_base,
+                        static_cast<size_t>(sym_addr), static_cast<size_t>(addend),
+                        sym_name);
+          } else {
+            relocator.tlsdesc_args->push_back({
+              .generation = mod.first_generation,
+              .index.module_id = module_id,
+              .index.offset = sym_addr + addend,
+            });
+            // Defer the TLSDESC relocation until the address of the TlsDynamicResolverArg object
+            // is finalized.
+            relocator.deferred_tlsdesc_relocs.push_back({
+              desc, relocator.tlsdesc_args->size() - 1
+            });
+            const TlsDynamicResolverArg& desc_arg = relocator.tlsdesc_args->back();
+            trace_reloc("RELO TLSDESC %16p <- dynamic (gen %zu, mod %zu, off %zu) %s",
+                        rel_target, desc_arg.generation, desc_arg.index.module_id,
+                        desc_arg.index.offset, sym_name);
+          }
+        }
+      }
+      break;
+#endif  // defined(__aarch64__)
+
+#if defined(__x86_64__)
+    case R_X86_64_32:
+      count_relocation_if<IsGeneral>(kRelocAbsolute);
+      {
+        const Elf32_Addr result = sym_addr + reloc.r_addend;
+        trace_reloc("RELO R_X86_64_32 %16p <- 0x%08x %s",
+                    rel_target, result, sym_name);
+        *static_cast<Elf32_Addr*>(rel_target) = result;
+      }
+      break;
+    case R_X86_64_PC32:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        const ElfW(Addr) target = sym_addr + reloc.r_addend;
+        const ElfW(Addr) base = reinterpret_cast<ElfW(Addr)>(rel_target);
+        const Elf32_Addr result = target - base;
+        trace_reloc("RELO R_X86_64_PC32 %16p <- 0x%08x (%16p - %16p) %s",
+                    rel_target, result, reinterpret_cast<void*>(target),
+                    reinterpret_cast<void*>(base), sym_name);
+        *static_cast<Elf32_Addr*>(rel_target) = result;
+      }
+      break;
+#elif defined(__i386__)
+    case R_386_PC32:
+      count_relocation_if<IsGeneral>(kRelocRelative);
+      {
+        const ElfW(Addr) target = sym_addr + get_addend_rel();
+        const ElfW(Addr) base = reinterpret_cast<ElfW(Addr)>(rel_target);
+        const ElfW(Addr) result = target - base;
+        trace_reloc("RELO R_386_PC32 %16p <- 0x%08x (%16p - %16p) %s",
+                    rel_target, result, reinterpret_cast<void*>(target),
+                    reinterpret_cast<void*>(base), sym_name);
+        *static_cast<ElfW(Addr)*>(rel_target) = result;
+      }
+      break;
+#endif
+    default:
+      DL_ERR("unknown reloc type %d in \"%s\"", r_type, relocator.si->get_realpath());
+      return false;
+  }
+  return true;
+}
+
+__attribute__((noinline))
+static bool process_relocation_general(Relocator& relocator, const rel_t& reloc) {
+  return process_relocation_impl<RelocMode::General>(relocator, reloc);
+}
+
+template <RelocMode Mode>
+__attribute__((always_inline))
+static inline bool process_relocation(Relocator& relocator, const rel_t& reloc) {
+  return Mode == RelocMode::General ?
+      process_relocation_general(relocator, reloc) :
+      process_relocation_impl<Mode>(relocator, reloc);
+}
+
+template <RelocMode Mode>
+__attribute__((noinline))
+static bool plain_relocate_impl(Relocator& relocator, rel_t* rels, size_t rel_count) {
+  for (size_t i = 0; i < rel_count; ++i) {
+    if (!process_relocation<Mode>(relocator, rels[i])) {
+      return false;
+    }
+  }
+  return true;
+}
+
+template <RelocMode Mode>
+__attribute__((noinline))
+static bool packed_relocate_impl(Relocator& relocator, sleb128_decoder decoder) {
+  return for_all_packed_relocs(decoder, [&](const rel_t& reloc) {
+    return process_relocation<Mode>(relocator, reloc);
+  });
+}
+
+static bool needs_slow_relocate_loop(const Relocator& relocator __unused) {
+#if STATS
+  // TODO: This could become a run-time flag.
+  return true;
+#endif
+#if !defined(__LP64__)
+  if (relocator.si->has_text_relocations) return true;
+#endif
+  if (g_ld_debug_verbosity > LINKER_VERBOSITY_TRACE) {
+    // If linker TRACE() is enabled, then each relocation is logged.
+    return true;
+  }
+  return false;
+}
+
+template <RelocMode OptMode, typename ...Args>
+static bool plain_relocate(Relocator& relocator, Args ...args) {
+  return needs_slow_relocate_loop(relocator) ?
+      plain_relocate_impl<RelocMode::General>(relocator, args...) :
+      plain_relocate_impl<OptMode>(relocator, args...);
+}
+
+template <RelocMode OptMode, typename ...Args>
+static bool packed_relocate(Relocator& relocator, Args ...args) {
+  return needs_slow_relocate_loop(relocator) ?
+      packed_relocate_impl<RelocMode::General>(relocator, args...) :
+      packed_relocate_impl<OptMode>(relocator, args...);
+}
+
+bool soinfo::relocate(const SymbolLookupList& lookup_list) {
+
+  VersionTracker version_tracker;
+
+  if (!version_tracker.init(this)) {
+    return false;
+  }
+
+  Relocator relocator(version_tracker, lookup_list);
+  relocator.si = this;
+  relocator.si_strtab = strtab_;
+  relocator.si_strtab_size = has_min_version(1) ? strtab_size_ : SIZE_MAX;
+  relocator.si_symtab = symtab_;
+  relocator.tlsdesc_args = &tlsdesc_args_;
+  relocator.tls_tp_base = __libc_shared_globals()->static_tls_layout.offset_thread_pointer();
+
+  if (android_relocs_ != nullptr) {
+    // check signature
+    if (android_relocs_size_ > 3 &&
+        android_relocs_[0] == 'A' &&
+        android_relocs_[1] == 'P' &&
+        android_relocs_[2] == 'S' &&
+        android_relocs_[3] == '2') {
+      DEBUG("[ android relocating %s ]", get_realpath());
+
+      const uint8_t* packed_relocs = android_relocs_ + 4;
+      const size_t packed_relocs_size = android_relocs_size_ - 4;
+
+      if (!packed_relocate<RelocMode::Typical>(relocator, sleb128_decoder(packed_relocs, packed_relocs_size))) {
+        return false;
+      }
+    } else {
+      DL_ERR("bad android relocation header.");
+      return false;
+    }
+  }
+
+  if (relr_ != nullptr) {
+    DEBUG("[ relocating %s relr ]", get_realpath());
+    if (!relocate_relr()) {
+      return false;
+    }
+  }
+
+#if defined(USE_RELA)
+  if (rela_ != nullptr) {
+    DEBUG("[ relocating %s rela ]", get_realpath());
+
+    if (!plain_relocate<RelocMode::Typical>(relocator, rela_, rela_count_)) {
+      return false;
+    }
+  }
+  if (plt_rela_ != nullptr) {
+    DEBUG("[ relocating %s plt rela ]", get_realpath());
+    if (!plain_relocate<RelocMode::JumpTable>(relocator, plt_rela_, plt_rela_count_)) {
+      return false;
+    }
+  }
+#else
+  if (rel_ != nullptr) {
+    DEBUG("[ relocating %s rel ]", get_realpath());
+    if (!plain_relocate<RelocMode::Typical>(relocator, rel_, rel_count_)) {
+      return false;
+    }
+  }
+  if (plt_rel_ != nullptr) {
+    DEBUG("[ relocating %s plt rel ]", get_realpath());
+    if (!plain_relocate<RelocMode::JumpTable>(relocator, plt_rel_, plt_rel_count_)) {
+      return false;
+    }
+  }
+#endif
+
+#if defined(__mips__)
+  if (!mips_relocate_got(version_tracker, global_group, local_group)) {
+    return false;
+  }
+#endif
+
+  // Once the tlsdesc_args_ vector's size is finalized, we can write the addresses of its elements
+  // into the TLSDESC relocations.
+#if defined(__aarch64__)
+  // Bionic currently only implements TLSDESC for arm64.
+  for (const std::pair<TlsDescriptor*, size_t>& pair : relocator.deferred_tlsdesc_relocs) {
+    TlsDescriptor* desc = pair.first;
+    desc->func = tlsdesc_resolver_dynamic;
+    desc->arg = reinterpret_cast<size_t>(&tlsdesc_args_[pair.second]);
+  }
+#endif
+
+  return true;
+}
diff --git a/linker/linker_relocate.h b/linker/linker_relocate.h
new file mode 100644
index 0000000..bf2acc9
--- /dev/null
+++ b/linker/linker_relocate.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ * 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.
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <link.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <utility>
+#include <vector>
+
+#include "linker_common_types.h"
+#include "linker_globals.h"
+#include "linker_soinfo.h"
+
+static constexpr ElfW(Versym) kVersymHiddenBit = 0x8000;
+
+enum RelocationKind {
+  kRelocAbsolute = 0,
+  kRelocRelative,
+  kRelocSymbol,
+  kRelocSymbolCached,
+  kRelocMax
+};
+
+void count_relocation(RelocationKind kind);
+
+template <bool Enabled> void count_relocation_if(RelocationKind kind) {
+  if (Enabled) count_relocation(kind);
+}
+
+void print_linker_stats();
+
+inline bool is_symbol_global_and_defined(const soinfo* si, const ElfW(Sym)* s) {
+  if (__predict_true(ELF_ST_BIND(s->st_info) == STB_GLOBAL ||
+                     ELF_ST_BIND(s->st_info) == STB_WEAK)) {
+    return s->st_shndx != SHN_UNDEF;
+  } else if (__predict_false(ELF_ST_BIND(s->st_info) != STB_LOCAL)) {
+    DL_WARN("Warning: unexpected ST_BIND value: %d for \"%s\" in \"%s\" (ignoring)",
+            ELF_ST_BIND(s->st_info), si->get_string(s->st_name), si->get_realpath());
+  }
+  return false;
+}
diff --git a/linker/linker_soinfo.cpp b/linker/linker_soinfo.cpp
index 8efc9fe..4f67003 100644
--- a/linker/linker_soinfo.cpp
+++ b/linker/linker_soinfo.cpp
@@ -40,12 +40,176 @@
 #include "linker_config.h"
 #include "linker_debug.h"
 #include "linker_globals.h"
+#include "linker_gnu_hash.h"
 #include "linker_logger.h"
+#include "linker_relocate.h"
 #include "linker_utils.h"
 
-// TODO(dimitry): These functions are currently located in linker.cpp - find a better place for it
-ElfW(Addr) call_ifunc_resolver(ElfW(Addr) resolver_addr);
-int get_application_target_sdk_version();
+// Enable the slow lookup path if symbol lookups should be logged.
+static bool is_lookup_tracing_enabled() {
+  return g_ld_debug_verbosity > LINKER_VERBOSITY_TRACE && DO_TRACE_LOOKUP;
+}
+
+SymbolLookupList::SymbolLookupList(soinfo* si)
+    : sole_lib_(si->get_lookup_lib()), begin_(&sole_lib_), end_(&sole_lib_ + 1) {
+  CHECK(si != nullptr);
+  slow_path_count_ += is_lookup_tracing_enabled();
+  slow_path_count_ += sole_lib_.needs_sysv_lookup();
+}
+
+SymbolLookupList::SymbolLookupList(const soinfo_list_t& global_group, const soinfo_list_t& local_group) {
+  slow_path_count_ += is_lookup_tracing_enabled();
+  libs_.reserve(1 + global_group.size() + local_group.size());
+
+  // Reserve a space in front for DT_SYMBOLIC lookup.
+  libs_.push_back(SymbolLookupLib {});
+
+  global_group.for_each([this](soinfo* si) {
+    libs_.push_back(si->get_lookup_lib());
+    slow_path_count_ += libs_.back().needs_sysv_lookup();
+  });
+
+  local_group.for_each([this](soinfo* si) {
+    libs_.push_back(si->get_lookup_lib());
+    slow_path_count_ += libs_.back().needs_sysv_lookup();
+  });
+
+  begin_ = &libs_[1];
+  end_ = &libs_[0] + libs_.size();
+}
+
+/* "This element's presence in a shared object library alters the dynamic linker's
+ * symbol resolution algorithm for references within the library. Instead of starting
+ * a symbol search with the executable file, the dynamic linker starts from the shared
+ * object itself. If the shared object fails to supply the referenced symbol, the
+ * dynamic linker then searches the executable file and other shared objects as usual."
+ *
+ * http://www.sco.com/developers/gabi/2012-12-31/ch5.dynamic.html
+ *
+ * Note that this is unlikely since static linker avoids generating
+ * relocations for -Bsymbolic linked dynamic executables.
+ */
+void SymbolLookupList::set_dt_symbolic_lib(soinfo* lib) {
+  CHECK(!libs_.empty());
+  slow_path_count_ -= libs_[0].needs_sysv_lookup();
+  libs_[0] = lib ? lib->get_lookup_lib() : SymbolLookupLib();
+  slow_path_count_ += libs_[0].needs_sysv_lookup();
+  begin_ = lib ? &libs_[0] : &libs_[1];
+}
+
+// Check whether a requested version matches the version on a symbol definition. There are a few
+// special cases:
+//  - If the defining DSO has no version info at all, then any version matches.
+//  - If no version is requested (vi==nullptr, verneed==kVersymNotNeeded), then any non-hidden
+//    version matches.
+//  - If the requested version is not defined by the DSO, then verneed is kVersymGlobal, and only
+//    global symbol definitions match. (This special case is handled as part of the ordinary case
+//    where the version must match exactly.)
+static inline bool check_symbol_version(const ElfW(Versym)* ver_table, uint32_t sym_idx,
+                                        const ElfW(Versym) verneed) {
+  if (ver_table == nullptr) return true;
+  const uint32_t verdef = ver_table[sym_idx];
+  return (verneed == kVersymNotNeeded) ?
+      !(verdef & kVersymHiddenBit) :
+      verneed == (verdef & ~kVersymHiddenBit);
+}
+
+template <bool IsGeneral>
+__attribute__((noinline)) static const ElfW(Sym)*
+soinfo_do_lookup_impl(const char* name, const version_info* vi,
+                      soinfo** si_found_in, const SymbolLookupList& lookup_list) {
+  const auto [ hash, name_len ] = calculate_gnu_hash(name);
+  constexpr uint32_t kBloomMaskBits = sizeof(ElfW(Addr)) * 8;
+  SymbolName elf_symbol_name(name);
+
+  const SymbolLookupLib* end = lookup_list.end();
+  const SymbolLookupLib* it = lookup_list.begin();
+
+  while (true) {
+    const SymbolLookupLib* lib;
+    uint32_t sym_idx;
+
+    // Iterate over libraries until we find one whose Bloom filter matches the symbol we're
+    // searching for.
+    while (true) {
+      if (it == end) return nullptr;
+      lib = it++;
+
+      if (IsGeneral && lib->needs_sysv_lookup()) {
+        if (const ElfW(Sym)* sym = lib->si_->find_symbol_by_name(elf_symbol_name, vi)) {
+          *si_found_in = lib->si_;
+          return sym;
+        }
+        continue;
+      }
+
+      if (IsGeneral) {
+        TRACE_TYPE(LOOKUP, "SEARCH %s in %s@%p (gnu)",
+                   name, lib->si_->get_realpath(), reinterpret_cast<void*>(lib->si_->base));
+      }
+
+      const uint32_t word_num = (hash / kBloomMaskBits) & lib->gnu_maskwords_;
+      const ElfW(Addr) bloom_word = lib->gnu_bloom_filter_[word_num];
+      const uint32_t h1 = hash % kBloomMaskBits;
+      const uint32_t h2 = (hash >> lib->gnu_shift2_) % kBloomMaskBits;
+
+      if ((1 & (bloom_word >> h1) & (bloom_word >> h2)) == 1) {
+        sym_idx = lib->gnu_bucket_[hash % lib->gnu_nbucket_];
+        if (sym_idx != 0) {
+          break;
+        }
+      }
+
+      if (IsGeneral) {
+        TRACE_TYPE(LOOKUP, "NOT FOUND %s in %s@%p",
+                   name, lib->si_->get_realpath(), reinterpret_cast<void*>(lib->si_->base));
+      }
+    }
+
+    // Search the library's hash table chain.
+    ElfW(Versym) verneed = kVersymNotNeeded;
+    bool calculated_verneed = false;
+
+    uint32_t chain_value = 0;
+    const ElfW(Sym)* sym = nullptr;
+
+    do {
+      sym = lib->symtab_ + sym_idx;
+      chain_value = lib->gnu_chain_[sym_idx];
+      if ((chain_value >> 1) == (hash >> 1)) {
+        if (vi != nullptr && !calculated_verneed) {
+          calculated_verneed = true;
+          verneed = find_verdef_version_index(lib->si_, vi);
+        }
+        if (check_symbol_version(lib->versym_, sym_idx, verneed) &&
+            static_cast<size_t>(sym->st_name) + name_len + 1 <= lib->strtab_size_ &&
+            memcmp(lib->strtab_ + sym->st_name, name, name_len + 1) == 0 &&
+            is_symbol_global_and_defined(lib->si_, sym)) {
+          *si_found_in = lib->si_;
+          if (IsGeneral) {
+            TRACE_TYPE(LOOKUP, "FOUND %s in %s (%p) %zd",
+                       name, lib->si_->get_realpath(), reinterpret_cast<void*>(sym->st_value),
+                       static_cast<size_t>(sym->st_size));
+          }
+          return sym;
+        }
+      }
+      ++sym_idx;
+    } while ((chain_value & 1) == 0);
+
+    if (IsGeneral) {
+      TRACE_TYPE(LOOKUP, "NOT FOUND %s in %s@%p",
+                 name, lib->si_->get_realpath(), reinterpret_cast<void*>(lib->si_->base));
+    }
+  }
+}
+
+const ElfW(Sym)* soinfo_do_lookup(const char* name, const version_info* vi,
+                                  soinfo** si_found_in, const SymbolLookupList& lookup_list) {
+  return lookup_list.needs_slow_path() ?
+      soinfo_do_lookup_impl<true>(name, vi, si_found_in, lookup_list) :
+      soinfo_do_lookup_impl<false>(name, vi, si_found_in, lookup_list);
+}
 
 soinfo::soinfo(android_namespace_t* ns, const char* realpath,
                const struct stat* file_stat, off64_t file_offset,
@@ -96,11 +260,8 @@
 }
 
 const ElfW(Versym)* soinfo::get_versym(size_t n) const {
-  if (has_min_version(2) && versym_ != nullptr) {
-    return versym_ + n;
-  }
-
-  return nullptr;
+  auto table = get_versym_table();
+  return table ? table + n : nullptr;
 }
 
 ElfW(Addr) soinfo::get_verneed_ptr() const {
@@ -135,30 +296,30 @@
   return 0;
 }
 
-static bool is_symbol_global_and_defined(const soinfo* si, const ElfW(Sym)* s) {
-  if (ELF_ST_BIND(s->st_info) == STB_GLOBAL ||
-      ELF_ST_BIND(s->st_info) == STB_WEAK) {
-    return s->st_shndx != SHN_UNDEF;
-  } else if (ELF_ST_BIND(s->st_info) != STB_LOCAL) {
-    DL_WARN("Warning: unexpected ST_BIND value: %d for \"%s\" in \"%s\" (ignoring)",
-            ELF_ST_BIND(s->st_info), si->get_string(s->st_name), si->get_realpath());
+SymbolLookupLib soinfo::get_lookup_lib() {
+  SymbolLookupLib result {};
+  result.si_ = this;
+
+  // For libs that only have SysV hashes, leave the gnu_bloom_filter_ field NULL to signal that
+  // the fallback code path is needed.
+  if (!is_gnu_hash()) {
+    return result;
   }
 
-  return false;
-}
+  result.gnu_maskwords_ = gnu_maskwords_;
+  result.gnu_shift2_ = gnu_shift2_;
+  result.gnu_bloom_filter_ = gnu_bloom_filter_;
 
-static const ElfW(Versym) kVersymHiddenBit = 0x8000;
+  result.strtab_ = strtab_;
+  result.strtab_size_ = strtab_size_;
+  result.symtab_ = symtab_;
+  result.versym_ = get_versym_table();
 
-static inline bool is_versym_hidden(const ElfW(Versym)* versym) {
-  // the symbol is hidden if bit 15 of versym is set.
-  return versym != nullptr && (*versym & kVersymHiddenBit) != 0;
-}
+  result.gnu_chain_ = gnu_chain_;
+  result.gnu_nbucket_ = gnu_nbucket_;
+  result.gnu_bucket_ = gnu_bucket_;
 
-static inline bool check_symbol_version(const ElfW(Versym) verneed,
-                                        const ElfW(Versym)* verdef) {
-  return verneed == kVersymNotNeeded ||
-      verdef == nullptr ||
-      verneed == (*verdef & ~kVersymHiddenBit);
+  return result;
 }
 
 const ElfW(Sym)* soinfo::find_symbol_by_name(SymbolName& symbol_name,
@@ -167,18 +328,19 @@
 }
 
 const ElfW(Sym)* soinfo::gnu_lookup(SymbolName& symbol_name, const version_info* vi) const {
-  uint32_t hash = symbol_name.gnu_hash();
-  uint32_t h2 = hash >> gnu_shift2_;
+  const uint32_t hash = symbol_name.gnu_hash();
 
-  uint32_t bloom_mask_bits = sizeof(ElfW(Addr))*8;
-  uint32_t word_num = (hash / bloom_mask_bits) & gnu_maskwords_;
-  ElfW(Addr) bloom_word = gnu_bloom_filter_[word_num];
+  constexpr uint32_t kBloomMaskBits = sizeof(ElfW(Addr)) * 8;
+  const uint32_t word_num = (hash / kBloomMaskBits) & gnu_maskwords_;
+  const ElfW(Addr) bloom_word = gnu_bloom_filter_[word_num];
+  const uint32_t h1 = hash % kBloomMaskBits;
+  const uint32_t h2 = (hash >> gnu_shift2_) % kBloomMaskBits;
 
   TRACE_TYPE(LOOKUP, "SEARCH %s in %s@%p (gnu)",
       symbol_name.get_name(), get_realpath(), reinterpret_cast<void*>(base));
 
   // test against bloom filter
-  if ((1 & (bloom_word >> (hash % bloom_mask_bits)) & (bloom_word >> (h2 % bloom_mask_bits))) == 0) {
+  if ((1 & (bloom_word >> h1) & (bloom_word >> h2)) == 0) {
     TRACE_TYPE(LOOKUP, "NOT FOUND %s in %s@%p",
         symbol_name.get_name(), get_realpath(), reinterpret_cast<void*>(base));
 
@@ -195,23 +357,13 @@
     return nullptr;
   }
 
-  // lookup versym for the version definition in this library
-  // note the difference between "version is not requested" (vi == nullptr)
-  // and "version not found". In the first case verneed is kVersymNotNeeded
-  // which implies that the default version can be accepted; the second case results in
-  // verneed = 1 (kVersymGlobal) and implies that we should ignore versioned symbols
-  // for this library and consider only *global* ones.
   const ElfW(Versym) verneed = find_verdef_version_index(this, vi);
+  const ElfW(Versym)* versym = get_versym_table();
 
   do {
     ElfW(Sym)* s = symtab_ + n;
-    const ElfW(Versym)* verdef = get_versym(n);
-    // skip hidden versions when verneed == kVersymNotNeeded (0)
-    if (verneed == kVersymNotNeeded && is_versym_hidden(verdef)) {
-        continue;
-    }
     if (((gnu_chain_[n] ^ hash) >> 1) == 0 &&
-        check_symbol_version(verneed, verdef) &&
+        check_symbol_version(versym, n, verneed) &&
         strcmp(get_string(s->st_name), symbol_name.get_name()) == 0 &&
         is_symbol_global_and_defined(this, s)) {
       TRACE_TYPE(LOOKUP, "FOUND %s in %s (%p) %zd",
@@ -235,17 +387,12 @@
              reinterpret_cast<void*>(base), hash, hash % nbucket_);
 
   const ElfW(Versym) verneed = find_verdef_version_index(this, vi);
+  const ElfW(Versym)* versym = get_versym_table();
 
   for (uint32_t n = bucket_[hash % nbucket_]; n != 0; n = chain_[n]) {
     ElfW(Sym)* s = symtab_ + n;
-    const ElfW(Versym)* verdef = get_versym(n);
 
-    // skip hidden versions when verneed == 0
-    if (verneed == kVersymNotNeeded && is_versym_hidden(verdef)) {
-        continue;
-    }
-
-    if (check_symbol_version(verneed, verdef) &&
+    if (check_symbol_version(versym, n, verneed) &&
         strcmp(get_string(s->st_name), symbol_name.get_name()) == 0 &&
         is_symbol_global_and_defined(this, s)) {
       TRACE_TYPE(LOOKUP, "FOUND %s in %s (%p) %zd",
@@ -622,14 +769,6 @@
   return secondary_namespaces_;
 }
 
-ElfW(Addr) soinfo::resolve_symbol_address(const ElfW(Sym)* s) const {
-  if (ELF_ST_TYPE(s->st_info) == STT_GNU_IFUNC) {
-    return call_ifunc_resolver(s->st_value + load_bias);
-  }
-
-  return static_cast<ElfW(Addr)>(s->st_value + load_bias);
-}
-
 const char* soinfo::get_string(ElfW(Word) index) const {
   if (has_min_version(1) && (index >= strtab_size_)) {
     async_safe_fatal("%s: strtab out of bounds error; STRSZ=%zd, name=%d",
@@ -788,13 +927,7 @@
 
 uint32_t SymbolName::gnu_hash() {
   if (!has_gnu_hash_) {
-    uint32_t h = 5381;
-    const uint8_t* name = reinterpret_cast<const uint8_t*>(name_);
-    while (*name != 0) {
-      h += (h << 5) + *name++; // h*33 + c = h + h * 32 + c = h + h << 5 + c
-    }
-
-    gnu_hash_ =  h;
+    gnu_hash_ = calculate_gnu_hash(name_).first;
     has_gnu_hash_ = true;
   }
 
diff --git a/linker/linker_soinfo.h b/linker/linker_soinfo.h
index 9ae17ea..3a33949 100644
--- a/linker/linker_soinfo.h
+++ b/linker/linker_soinfo.h
@@ -68,9 +68,49 @@
 
 #define SOINFO_VERSION 5
 
+ElfW(Addr) call_ifunc_resolver(ElfW(Addr) resolver_addr);
+
 typedef void (*linker_dtor_function_t)();
 typedef void (*linker_ctor_function_t)(int, char**, char**);
 
+// An entry within a SymbolLookupList.
+struct SymbolLookupLib {
+  uint32_t gnu_maskwords_ = 0;
+  uint32_t gnu_shift2_ = 0;
+  ElfW(Addr)* gnu_bloom_filter_ = nullptr;
+
+  const char* strtab_;
+  size_t strtab_size_;
+  const ElfW(Sym)* symtab_;
+  const ElfW(Versym)* versym_;
+
+  const uint32_t* gnu_chain_;
+  size_t gnu_nbucket_;
+  uint32_t* gnu_bucket_;
+
+  soinfo* si_ = nullptr;
+
+  bool needs_sysv_lookup() const { return si_ != nullptr && gnu_bloom_filter_ == nullptr; }
+};
+
+// A list of libraries to search for a symbol.
+class SymbolLookupList {
+  std::vector<SymbolLookupLib> libs_;
+  SymbolLookupLib sole_lib_;
+  const SymbolLookupLib* begin_;
+  const SymbolLookupLib* end_;
+  size_t slow_path_count_ = 0;
+
+ public:
+  explicit SymbolLookupList(soinfo* si);
+  SymbolLookupList(const soinfo_list_t& global_group, const soinfo_list_t& local_group);
+  void set_dt_symbolic_lib(soinfo* symbolic_lib);
+
+  const SymbolLookupLib* begin() const { return begin_; }
+  const SymbolLookupLib* end() const { return end_; }
+  bool needs_slow_path() const { return slow_path_count_ > 0; }
+};
+
 class SymbolName {
  public:
   explicit SymbolName(const char* name)
@@ -223,7 +263,7 @@
   void call_destructors();
   void call_pre_init_constructors();
   bool prelink_image();
-  bool link_image(const soinfo_list_t& global_group, const soinfo_list_t& local_group,
+  bool link_image(const SymbolLookupList& lookup_list, soinfo* local_group_root,
                   const android_dlextinfo* extinfo, size_t* relro_fd_offset);
   bool protect_relro();
 
@@ -246,7 +286,14 @@
   const ElfW(Sym)* find_symbol_by_name(SymbolName& symbol_name, const version_info* vi) const;
 
   ElfW(Sym)* find_symbol_by_address(const void* addr);
-  ElfW(Addr) resolve_symbol_address(const ElfW(Sym)* s) const;
+
+  ElfW(Addr) resolve_symbol_address(const ElfW(Sym)* s) const {
+    if (ELF_ST_TYPE(s->st_info) == STT_GNU_IFUNC) {
+      return call_ifunc_resolver(s->st_value + load_bias);
+    }
+
+    return static_cast<ElfW(Addr)>(s->st_value + load_bias);
+  }
 
   const char* get_string(ElfW(Word) index) const;
   bool can_unload() const;
@@ -260,6 +307,10 @@
 #endif
   }
 
+  const ElfW(Versym)* get_versym_table() const {
+    return has_min_version(2) ? versym_ : nullptr;
+  }
+
   bool is_linked() const;
   bool is_linker() const;
   bool is_main_executable() const;
@@ -304,6 +355,8 @@
   void generate_handle();
   void* to_handle();
 
+  SymbolLookupLib get_lookup_lib();
+
  private:
   bool is_image_linked() const;
   void set_image_linked();
@@ -313,16 +366,15 @@
   ElfW(Sym)* gnu_addr_lookup(const void* addr);
   ElfW(Sym)* elf_addr_lookup(const void* addr);
 
+ public:
   bool lookup_version_info(const VersionTracker& version_tracker, ElfW(Word) sym,
                            const char* sym_name, const version_info** vi);
 
-  template<typename ElfRelIteratorT>
-  bool relocate(const VersionTracker& version_tracker, ElfRelIteratorT&& rel_iterator,
-                const soinfo_list_t& global_group, const soinfo_list_t& local_group);
+ private:
+  bool relocate(const SymbolLookupList& lookup_list);
   bool relocate_relr();
   void apply_relr_reloc(ElfW(Addr) offset);
 
- private:
   // This part of the structure is only available
   // when FLAG_NEW_SOINFO is set in this->flags.
   uint32_t version_;
@@ -398,3 +450,6 @@
     }
   }
 }
+
+const ElfW(Sym)* soinfo_do_lookup(const char* name, const version_info* vi,
+                                  soinfo** si_found_in, const SymbolLookupList& lookup_list);
diff --git a/tests/stack_protector_test_helper.cpp b/tests/stack_protector_test_helper.cpp
index 2db4ef1..fd90b93 100644
--- a/tests/stack_protector_test_helper.cpp
+++ b/tests/stack_protector_test_helper.cpp
@@ -16,11 +16,10 @@
 
 // Deliberately overwrite the stack canary.
 __attribute__((noinline)) void modify_stack_protector_test() {
-  char buf[128];
   // We can't use memset here because it's fortified, and we want to test
   // the line of defense *after* that.
   // Without volatile, the generic x86/x86-64 targets don't write to the stack.
-  volatile char* p = buf;
-  int size = static_cast<int>(sizeof(buf) + sizeof(void*));
-  while ((p - buf) < size) *p++ = '\0';
+  volatile char* p;
+  p = reinterpret_cast<volatile char*>(&p + 1);
+  *p = '\0';
 }