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/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;
}