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

1 files changed, 4 insertions, 10 deletions

diff --git a/linker/linker_main.cpp b/linker/linker_main.cpp
index 8ba947f31..98af54ac2 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 @@ static void add_vdso() {
   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 @@ static ElfW(Addr) linker_main(KernelArgumentBlock& args, const char* exe_to_load
                       &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 @@ extern "C" ElfW(Addr) __linker_init(void* raw_args) {
 
   // 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);
 }