diff --git a/linker/dlfcn.cpp b/linker/dlfcn.cpp
index efb829e..8ebf357 100644
--- a/linker/dlfcn.cpp
+++ b/linker/dlfcn.cpp
@@ -111,8 +111,7 @@
       sym = dlsym_linear_lookup(symbol, &found, caller_si->next, caller_si);
     }
   } else {
-    found = reinterpret_cast<soinfo*>(handle);
-    sym = dlsym_handle_lookup(found, symbol, caller_si);
+    sym = dlsym_handle_lookup(reinterpret_cast<soinfo*>(handle), &found, symbol, caller_si);
   }
 
   if (sym != NULL && sym->st_shndx != 0) {
diff --git a/linker/linked_list.h b/linker/linked_list.h
index 52af0f1..7f8c901 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -31,13 +31,45 @@
 template<typename T, typename Allocator>
 class LinkedList {
  public:
-  LinkedList() : head_(nullptr) {}
+  LinkedList() : head_(nullptr), tail_(nullptr) {}
 
   void push_front(T* const element) {
     LinkedListEntry<T>* new_entry = Allocator::alloc();
     new_entry->next = head_;
     new_entry->element = element;
     head_ = new_entry;
+    if (tail_ == nullptr) {
+      tail_ = new_entry;
+    }
+  }
+
+  void push_back(T* const element) {
+    LinkedListEntry<T>* new_entry = Allocator::alloc();
+    new_entry->next = nullptr;
+    new_entry->element = element;
+    if (tail_ == nullptr) {
+      tail_ = head_ = new_entry;
+    } else {
+      tail_->next = new_entry;
+      tail_ = new_entry;
+    }
+  }
+
+  T* pop_front() {
+    if (head_ == nullptr) {
+      return nullptr;
+    }
+
+    LinkedListEntry<T>* entry = head_;
+    T* element = entry->element;
+    head_ = entry->next;
+    Allocator::free(entry);
+
+    if (head_ == nullptr) {
+      tail_ = nullptr;
+    }
+
+    return element;
   }
 
   void clear() {
@@ -46,6 +78,8 @@
       head_ = head_->next;
       Allocator::free(p);
     }
+
+    tail_ = nullptr;
   }
 
   template<typename F>
@@ -68,6 +102,7 @@
 
  private:
   LinkedListEntry<T>* head_;
+  LinkedListEntry<T>* tail_;
   DISALLOW_COPY_AND_ASSIGN(LinkedList);
 };
 
diff --git a/linker/linker.cpp b/linker/linker.cpp
index 59b9938..f8b35d7 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -469,6 +469,10 @@
     }
   }
 
+  TRACE_TYPE(LOOKUP, "NOT FOUND %s in %s@%p %x %zd",
+             name, si->name, reinterpret_cast<void*>(si->base), hash, hash % si->nbucket);
+
+
   return NULL;
 }
 
@@ -585,18 +589,43 @@
     return NULL;
 }
 
-/* This is used by dlsym(3).  It performs symbol lookup only within the
-   specified soinfo object and not in any of its dependencies.
+// Another soinfo list allocator to use in dlsym. We don't reuse
+// SoinfoListAllocator because it is write-protected most of the time.
+static LinkerAllocator<LinkedListEntry<soinfo>> g_soinfo_list_allocator_rw;
+class SoinfoListAllocatorRW {
+ public:
+  static LinkedListEntry<soinfo>* alloc() {
+    return g_soinfo_list_allocator_rw.alloc();
+  }
 
-   TODO: Only looking in the specified soinfo seems wrong. dlsym(3) says
-   that it should do a breadth first search through the dependency
-   tree. This agrees with the ELF spec (aka System V Application
-   Binary Interface) where in Chapter 5 it discuss resolving "Shared
-   Object Dependencies" in breadth first search order.
- */
-ElfW(Sym)* dlsym_handle_lookup(soinfo* si, const char* name, soinfo* caller) {
-    return soinfo_elf_lookup(si, elfhash(name), name,
-        caller == si ? SymbolLookupScope::kAllowLocal : SymbolLookupScope::kExcludeLocal);
+  static void free(LinkedListEntry<soinfo>* ptr) {
+    g_soinfo_list_allocator_rw.free(ptr);
+  }
+};
+
+// This is used by dlsym(3).  It performs symbol lookup only within the
+// 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;
+  visit_list.push_back(si);
+  soinfo* current_soinfo;
+  while ((current_soinfo = visit_list.pop_front()) != nullptr) {
+    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();
+      return result;
+    }
+
+    current_soinfo->get_children().for_each([&](soinfo* child) {
+      visit_list.push_back(child);
+    });
+  }
+
+  visit_list.clear();
+  return nullptr;
 }
 
 /* This is used by dlsym(3) to performs a global symbol lookup. If the
diff --git a/linker/linker.h b/linker/linker.h
index e1112e6..03672b2 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -238,7 +238,7 @@
 soinfo* find_containing_library(const void* addr);
 
 ElfW(Sym)* dladdr_find_symbol(soinfo* si, const void* addr);
-ElfW(Sym)* dlsym_handle_lookup(soinfo* si, const char* name, soinfo* caller_si);
+ElfW(Sym)* dlsym_handle_lookup(soinfo* si, soinfo** found, const char* name, soinfo* caller_si);
 
 void debuggerd_init();
 extern "C" abort_msg_t* g_abort_message;
diff --git a/linker/tests/linked_list_test.cpp b/linker/tests/linked_list_test.cpp
index 31ec7d5..b9816fa 100644
--- a/linker/tests/linked_list_test.cpp
+++ b/linker/tests/linked_list_test.cpp
@@ -95,3 +95,23 @@
   ASSERT_TRUE(free_called);
   ASSERT_EQ("", test_list_to_string(list));
 }
+
+TEST(linked_list, push_pop) {
+  test_list_t list;
+  list.push_front("b");
+  list.push_front("a");
+  ASSERT_EQ("ab", test_list_to_string(list));
+  list.push_back("c");
+  ASSERT_EQ("abc", test_list_to_string(list));
+  ASSERT_EQ("a", list.pop_front());
+  ASSERT_EQ("bc", test_list_to_string(list));
+  ASSERT_EQ("b", list.pop_front());
+  ASSERT_EQ("c", test_list_to_string(list));
+  ASSERT_EQ("c", list.pop_front());
+  ASSERT_EQ("", test_list_to_string(list));
+  ASSERT_TRUE(list.pop_front() == nullptr);
+  list.push_back("r");
+  ASSERT_EQ("r", test_list_to_string(list));
+  ASSERT_EQ("r", list.pop_front());
+  ASSERT_TRUE(list.pop_front() == nullptr);
+}