diff --git a/linker/linked_list.h b/linker/linked_list.h
index 72a32b4..4e62e20 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -86,7 +86,7 @@
   }
 
   template<typename F>
-  void for_each(F action) const {
+  void for_each(F action) {
     visit([&] (T* si) {
       action(si);
       return true;
@@ -94,7 +94,7 @@
   }
 
   template<typename F>
-  bool visit(F action) const {
+  bool visit(F action) {
     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
       if (!action(e->element)) {
         return false;
diff --git a/linker/linker.cpp b/linker/linker.cpp
index eb1a483..41557e2 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -415,7 +415,7 @@
   return rv;
 }
 
-static ElfW(Sym)* soinfo_elf_lookup(const soinfo* si, unsigned hash, const char* name) {
+static ElfW(Sym)* soinfo_elf_lookup(soinfo* si, unsigned hash, const char* name) {
   ElfW(Sym)* symtab = si->symtab;
 
   TRACE_TYPE(LOOKUP, "SEARCH %s in %s@%p %x %zd",
@@ -481,7 +481,7 @@
   return h;
 }
 
-static ElfW(Sym)* soinfo_do_lookup(soinfo* si, const char* name, soinfo** lsi, const soinfo::soinfo_list_t& local_group) {
+static ElfW(Sym)* soinfo_do_lookup(soinfo* si, const char* name, soinfo** lsi) {
   unsigned elf_hash = elfhash(name);
   ElfW(Sym)* s = nullptr;
 
@@ -527,21 +527,16 @@
     }
   }
 
-  // 3. Look for it in the local group
-  if (s == nullptr) {
-    local_group.visit([&](soinfo* local_si) {
-      DEBUG("%s: looking up %s in %s (from local group)", si->name, name, local_si->name);
-      s = soinfo_elf_lookup(local_si, elf_hash, name);
-      if (s != nullptr) {
-        *lsi = local_si;
-        return false;
-      }
+  /* Look for symbols in the local scope (the object who is
+   * searching). This happens with C++ templates on x86 for some
+   * reason.
+   *
+   * Notes on weak symbols:
+   * The ELF specs are ambiguous about treatment of weak definitions in
+   * dynamic linking.  Some systems return the first definition found
+   * and some the first non-weak definition.   This is system dependent.
+   * Here we return the first definition found for simplicity.  */
 
-      return true;
-    });
-  }
-
-  // 4. Look for it in this library (unless we already did it because of DT_SYMBOLIC)
   if (s == nullptr && !si->has_DT_SYMBOLIC) {
     DEBUG("%s: looking up %s in local scope", si->name, name);
     s = soinfo_elf_lookup(si, elf_hash, name);
@@ -550,7 +545,6 @@
     }
   }
 
-  // 5. Dependencies
   if (s == nullptr) {
     si->get_children().visit([&](soinfo* child) {
       DEBUG("%s: looking up %s in %s", si->name, name, child->name);
@@ -649,61 +643,33 @@
 typedef linked_list_t<LoadTask> LoadTaskList;
 
 
-// This function walks down the tree of soinfo dependencies
-// in breadth-first order and
-//   * calls action(soinfo* si) for each node, and
-//   * terminates walk if action returns false.
-//
-// walk_dependencies_tree returns false if walk was terminated
-// by the action and true otherwise.
-template<typename F>
-static bool walk_dependencies_tree(soinfo* root_soinfos[], size_t root_soinfos_size, F action) {
+// 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) {
   SoinfoLinkedList visit_list;
   SoinfoLinkedList visited;
 
-  for (size_t i = 0; i < root_soinfos_size; ++i) {
-    visit_list.push_back(root_soinfos[i]);
-  }
-
-  soinfo* si;
-  while ((si = visit_list.pop_front()) != nullptr) {
-    if (visited.contains(si)) {
+  visit_list.push_back(si);
+  soinfo* current_soinfo;
+  while ((current_soinfo = visit_list.pop_front()) != nullptr) {
+    if (visited.contains(current_soinfo)) {
       continue;
     }
 
-    if (!action(si)) {
-      return false;
+    ElfW(Sym)* result = soinfo_elf_lookup(current_soinfo, elfhash(name), name);
+
+    if (result != nullptr) {
+      *found = current_soinfo;
+      return result;
     }
+    visited.push_back(current_soinfo);
 
-    visited.push_back(si);
-
-    si->get_children().for_each([&](soinfo* child) {
+    current_soinfo->get_children().for_each([&](soinfo* child) {
       visit_list.push_back(child);
     });
   }
 
-  return true;
-}
-
-
-// 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) {
-  ElfW(Sym)* result = nullptr;
-  uint32_t elf_hash = elfhash(name);
-
-
-  walk_dependencies_tree(&si, 1, [&](soinfo* current_soinfo) {
-    result = soinfo_elf_lookup(current_soinfo, elf_hash, name);
-    if (result != nullptr) {
-      *found = current_soinfo;
-      return false;
-    }
-
-    return true;
-  });
-
-  return result;
+  return nullptr;
 }
 
 /* This is used by dlsym(3) to performs a global symbol lookup. If the
@@ -933,30 +899,19 @@
   });
 }
 
-static bool find_libraries(soinfo* start_with, const char* const library_names[], size_t library_names_count, soinfo* soinfos[],
-    soinfo* ld_preloads[], size_t ld_preloads_count, int rtld_flags, const android_dlextinfo* extinfo) {
+static bool find_libraries(const char* const library_names[], size_t library_names_size, soinfo* soinfos[],
+    soinfo* ld_preloads[], size_t ld_preloads_size, int rtld_flags, const android_dlextinfo* extinfo) {
   // Step 0: prepare.
   LoadTaskList load_tasks;
-  for (size_t i = 0; i < library_names_count; ++i) {
+  for (size_t i = 0; i < library_names_size; ++i) {
     const char* name = library_names[i];
-    load_tasks.push_back(LoadTask::create(name, start_with));
+    load_tasks.push_back(LoadTask::create(name, nullptr));
   }
 
-  // If soinfos array is null allocate one on stack.
-  // The array is needed in case of failure; for example
-  // when library_names[] = {libone.so, libtwo.so} and libone.so
-  // is loaded correctly but libtwo.so failed for some reason.
-  // In this case libone.so should be unloaded on return.
-  // See also implementation of failure_guard below.
-
-  if (soinfos == nullptr) {
-    size_t soinfos_size = sizeof(soinfo*)*library_names_count;
-    soinfos = reinterpret_cast<soinfo**>(alloca(soinfos_size));
-    memset(soinfos, 0, soinfos_size);
-  }
-
-  // list of libraries to link - see step 2.
-  size_t soinfos_count = 0;
+  // Libraries added to this list in reverse order so that we can
+  // start linking from bottom-up - see step 2.
+  SoinfoLinkedList found_libs;
+  size_t soinfos_size = 0;
 
   auto failure_guard = make_scope_guard([&]() {
     // Housekeeping
@@ -964,7 +919,7 @@
       LoadTask::deleter(t);
     });
 
-    for (size_t i = 0; i<soinfos_count; ++i) {
+    for (size_t i = 0; i<soinfos_size; ++i) {
       soinfo_unload(soinfos[i]);
     }
   });
@@ -986,44 +941,34 @@
     if (needed_by != nullptr) {
       needed_by->add_child(si);
     }
+    found_libs.push_front(si);
 
-    // When ld_preloads is not null, the first
-    // ld_preloads_count libs are in fact ld_preloads.
-    if (ld_preloads != nullptr && soinfos_count < ld_preloads_count) {
-      ld_preloads[soinfos_count] = si;
+    // When ld_preloads is not null first
+    // ld_preloads_size libs are in fact ld_preloads.
+    if (ld_preloads != nullptr && soinfos_size < ld_preloads_size) {
+      ld_preloads[soinfos_size] = si;
     }
 
-    if (soinfos_count < library_names_count) {
-      soinfos[soinfos_count++] = si;
+    if (soinfos_size<library_names_size) {
+      soinfos[soinfos_size++] = si;
     }
   }
 
   // Step 2: link libraries.
-  soinfo::soinfo_list_t local_group;
-  walk_dependencies_tree(
-      start_with == nullptr ? soinfos : &start_with,
-      start_with == nullptr ? soinfos_count : 1,
-      [&] (soinfo* si) {
-    local_group.push_back(si);
-    return true;
-  });
-
-  bool linked = local_group.visit([&](soinfo* si) {
+  soinfo* si;
+  while ((si = found_libs.pop_front()) != nullptr) {
     if ((si->flags & FLAG_LINKED) == 0) {
-      if (!si->LinkImage(local_group, extinfo)) {
+      if (!si->LinkImage(extinfo)) {
         return false;
       }
       si->flags |= FLAG_LINKED;
     }
-
-    return true;
-  });
-
-  if (linked) {
-    failure_guard.disable();
   }
 
-  return linked;
+  // All is well - found_libs and load_tasks are empty at this point
+  // and all libs are successfully linked.
+  failure_guard.disable();
+  return true;
 }
 
 static soinfo* find_library(const char* name, int rtld_flags, const android_dlextinfo* extinfo) {
@@ -1034,7 +979,7 @@
 
   soinfo* si;
 
-  if (!find_libraries(nullptr, &name, 1, &si, nullptr, 0, rtld_flags, extinfo)) {
+  if (!find_libraries(&name, 1, &si, nullptr, 0, rtld_flags, extinfo)) {
     return nullptr;
   }
 
@@ -1145,7 +1090,7 @@
 }
 
 #if defined(USE_RELA)
-int soinfo::Relocate(ElfW(Rela)* rela, unsigned count, const soinfo_list_t& local_group) {
+int soinfo::Relocate(ElfW(Rela)* rela, unsigned count) {
   for (size_t idx = 0; idx < count; ++idx, ++rela) {
     unsigned type = ELFW(R_TYPE)(rela->r_info);
     unsigned sym = ELFW(R_SYM)(rela->r_info);
@@ -1163,7 +1108,7 @@
 
     if (sym != 0) {
       sym_name = get_string(symtab[sym].st_name);
-      s = soinfo_do_lookup(this, sym_name, &lsi, local_group);
+      s = soinfo_do_lookup(this, sym_name, &lsi);
       if (s == nullptr) {
         // We only allow an undefined symbol if this is a weak reference...
         s = &symtab[sym];
@@ -1422,7 +1367,7 @@
 }
 
 #else // REL, not RELA.
-int soinfo::Relocate(ElfW(Rel)* rel, unsigned count, const soinfo_list_t& local_group) {
+int soinfo::Relocate(ElfW(Rel)* rel, unsigned count) {
   for (size_t idx = 0; idx < count; ++idx, ++rel) {
     unsigned type = ELFW(R_TYPE)(rel->r_info);
     // TODO: don't use unsigned for 'sym'. Use uint32_t or ElfW(Addr) instead.
@@ -1441,7 +1386,7 @@
 
     if (sym != 0) {
       sym_name = get_string(symtab[sym].st_name);
-      s = soinfo_do_lookup(this, sym_name, &lsi, local_group);
+      s = soinfo_do_lookup(this, sym_name, &lsi);
       if (s == nullptr) {
         // We only allow an undefined symbol if this is a weak reference...
         s = &symtab[sym];
@@ -1627,7 +1572,7 @@
 #endif
 
 #if defined(__mips__)
-static bool mips_relocate_got(soinfo* si, const soinfo::soinfo_list_t& local_group) {
+static bool mips_relocate_got(soinfo* si) {
   ElfW(Addr)** got = si->plt_got;
   if (got == nullptr) {
     return true;
@@ -1660,7 +1605,7 @@
     // This is an undefined reference... try to locate it.
     const char* sym_name = si->get_string(sym->st_name);
     soinfo* lsi = nullptr;
-    ElfW(Sym)* s = soinfo_do_lookup(si, sym_name, &lsi, local_group);
+    ElfW(Sym)* s = soinfo_do_lookup(si, sym_name, &lsi);
     if (s == nullptr) {
       // We only allow an undefined symbol if this is a weak reference.
       s = &symtab[g];
@@ -2253,7 +2198,7 @@
   return true;
 }
 
-bool soinfo::LinkImage(const soinfo_list_t& local_group, const android_dlextinfo* extinfo) {
+bool soinfo::LinkImage(const android_dlextinfo* extinfo) {
 
 #if !defined(__LP64__)
   if (has_text_relocations) {
@@ -2272,26 +2217,26 @@
 #if defined(USE_RELA)
   if (rela != nullptr) {
     DEBUG("[ relocating %s ]", name);
-    if (Relocate(rela, rela_count, local_group)) {
+    if (Relocate(rela, rela_count)) {
       return false;
     }
   }
   if (plt_rela != nullptr) {
     DEBUG("[ relocating %s plt ]", name);
-    if (Relocate(plt_rela, plt_rela_count, local_group)) {
+    if (Relocate(plt_rela, plt_rela_count)) {
       return false;
     }
   }
 #else
   if (rel != nullptr) {
     DEBUG("[ relocating %s ]", name);
-    if (Relocate(rel, rel_count, local_group)) {
+    if (Relocate(rel, rel_count)) {
       return false;
     }
   }
   if (plt_rel != nullptr) {
     DEBUG("[ relocating %s plt ]", name);
-    if (Relocate(plt_rel, plt_rel_count, local_group)) {
+    if (Relocate(plt_rel, plt_rel_count)) {
       return false;
     }
   }
@@ -2365,7 +2310,7 @@
   si->load_bias = get_elf_exec_load_bias(ehdr_vdso);
 
   si->PrelinkImage();
-  si->LinkImage(g_empty_list, nullptr);
+  si->LinkImage(nullptr);
 #endif
 }
 
@@ -2511,11 +2456,21 @@
   });
 
   const char* needed_library_names[needed_libraries_count];
+  soinfo* needed_library_si[needed_libraries_count];
 
   memset(needed_library_names, 0, sizeof(needed_library_names));
   needed_library_name_list.copy_to_array(needed_library_names, needed_libraries_count);
 
-  if (needed_libraries_count > 0 && !find_libraries(si, needed_library_names, needed_libraries_count, nullptr, g_ld_preloads, ld_preloads_count, RTLD_GLOBAL, nullptr)) {
+  if (needed_libraries_count > 0 && !find_libraries(needed_library_names, needed_libraries_count, needed_library_si, g_ld_preloads, ld_preloads_count, RTLD_GLOBAL, nullptr)) {
+    __libc_format_fd(2, "CANNOT LINK EXECUTABLE DEPENDENCIES: %s\n", linker_get_error_buffer());
+    exit(EXIT_FAILURE);
+  }
+
+  for (size_t i = 0; i<needed_libraries_count; ++i) {
+    si->add_child(needed_library_si[i]);
+  }
+
+  if (!si->LinkImage(nullptr)) {
     __libc_format_fd(2, "CANNOT LINK EXECUTABLE: %s\n", linker_get_error_buffer());
     exit(EXIT_FAILURE);
   }
@@ -2639,7 +2594,7 @@
   linker_so.phnum = elf_hdr->e_phnum;
   linker_so.flags |= FLAG_LINKER;
 
-  if (!(linker_so.PrelinkImage() && linker_so.LinkImage(g_empty_list, nullptr))) {
+  if (!(linker_so.PrelinkImage() && linker_so.LinkImage(nullptr))) {
     // It would be nice to print an error message, but if the linker
     // can't link itself, there's no guarantee that we'll be able to
     // call write() (because it involves a GOT reference). We may as
diff --git a/linker/linker.h b/linker/linker.h
index 222aca1..ebb4793 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -207,7 +207,7 @@
   void CallDestructors();
   void CallPreInitConstructors();
   bool PrelinkImage();
-  bool LinkImage(const soinfo_list_t& local_group, const android_dlextinfo* extinfo);
+  bool LinkImage(const android_dlextinfo* extinfo);
 
   void add_child(soinfo* child);
   void remove_all_links();
@@ -234,9 +234,9 @@
   void CallArray(const char* array_name, linker_function_t* functions, size_t count, bool reverse);
   void CallFunction(const char* function_name, linker_function_t function);
 #if defined(USE_RELA)
-  int Relocate(ElfW(Rela)* rela, unsigned count, const soinfo_list_t& local_group);
+  int Relocate(ElfW(Rela)* rela, unsigned count);
 #else
-  int Relocate(ElfW(Rel)* rel, unsigned count, const soinfo_list_t& local_group);
+  int Relocate(ElfW(Rel)* rel, unsigned count);
 #endif
 
  private: