commit 8a84d383fb74135e928d341baa180c55854f2f42
author Dmitriy Ivanov <dimitry@google.com> Tue Aug 12 21:02:13 2014 -0700
committer Dmitriy Ivanov <dimitry@google.com> Wed Aug 13 09:30:52 2014 -0700
tree 26a9379a7a144f51986d53844f1ee02fcffe9f13
parent d332bc68783b9bdef4ecb38bec4e45765a5e9a94

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

linker/linked_list.h

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 @@
     }
   }
 
+  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_;

linker/linker.cpp

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 @@
 // 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 @@
   }
 
   visit_list.clear();
+  visited.clear();
   return nullptr;
 }