Optimize GNU hash linking for large inputs
Symbol lookup is O(L) where L is the number of libraries to search (e.g.
in the global and local lookup groups). Factor out the per-DSO work into
soinfo_do_lookup_impl, and optimize for the situation where all the DSOs
are using DT_GNU_HASH (rather than SysV hashes).
To load a set of libraries, the loader first constructs an auxiliary list
of libraries (SymbolLookupList, containing SymbolLookupLib objects). The
SymbolLookupList is reused for each DSO in a load group. (-Bsymbolic is
accommodated by modifying the SymbolLookupLib at the front of the list.)
To search for a symbol, soinfo_do_lookup_impl has a small loop that first
scans a vector of GNU bloom filters looking for a possible match.
There was a slight improvement from templatizing soinfo_do_lookup_impl
and skipping the does-this-DSO-lack-GNU-hash check.
Rewrite the relocation processing loop to be faster. There are specialized
functions that handle the expected relocation types in normal relocation
sections and in PLT relocation sections.
This CL can reduce the initial link time of large programs by around
40-50% (e.g. audioserver, cameraserver, etc). On the linker relocation
benchmark (64-bit walleye), it reduces the time from 131.6ms to 71.9ms.
Bug: http://b/143577578 (incidentally fixed by this CL)
Test: bionic-unit-tests
Change-Id: If40a42fb6ff566570f7280b71d58f7fa290b9343
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);