Optimize symbol lookup

 Do not run symbol lookup on already visited soinfos
 Not taking into account already visited libraries
 dramatically slows down dlsym in cases when there
 are multiple occurrences of a large library in
 dependency tree.

Bug: 16977077

(cherry picked from commit 042426ba6375f5c145379e598486ec6d675533c9)

Change-Id: I69d59e395e8112f119343e8a4d72fe31cd449f31

2 files changed, 17 insertions, 0 deletions

diff --git a/linker/linked_list.h b/linker/linked_list.h
index 7f8c901..8096e62 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -100,6 +100,15 @@ class LinkedList {
     }
   }
 
+  bool contains(const T* el) {
+    for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
+      if (e->element != nullptr && e->element == el) {
+        return true;
+      }
+    }
+    return false;
+  }
+
  private:
   LinkedListEntry<T>* head_;
   LinkedListEntry<T>* tail_;
diff --git a/linker/linker.cpp b/linker/linker.cpp
index f8b35d7..77fb70c 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -607,17 +607,24 @@ class SoinfoListAllocatorRW {
 // specified soinfo object and its dependencies in breadth first order.
 ElfW(Sym)* dlsym_handle_lookup(soinfo* si, soinfo** found, const char* name, soinfo* caller) {
   LinkedList<soinfo, SoinfoListAllocatorRW> visit_list;
+  LinkedList<soinfo, SoinfoListAllocatorRW> visited;
   visit_list.push_back(si);
   soinfo* current_soinfo;
   while ((current_soinfo = visit_list.pop_front()) != nullptr) {
+    if (visited.contains(current_soinfo)) {
+      continue;
+    }
+
     ElfW(Sym)* result = soinfo_elf_lookup(current_soinfo, elfhash(name), name,
         caller == current_soinfo ? SymbolLookupScope::kAllowLocal : SymbolLookupScope::kExcludeLocal);
 
     if (result != nullptr) {
       *found = current_soinfo;
       visit_list.clear();
+      visited.clear();
       return result;
     }
+    visited.push_back(current_soinfo);
 
     current_soinfo->get_children().for_each([&](soinfo* child) {
       visit_list.push_back(child);
@@ -625,6 +632,7 @@ ElfW(Sym)* dlsym_handle_lookup(soinfo* si, soinfo** found, const char* name, soi
   }
 
   visit_list.clear();
+  visited.clear();
   return nullptr;
 }