diff --git a/linker/dlfcn.cpp b/linker/dlfcn.cpp
index 2486e02..6aa9cd7 100644
--- a/linker/dlfcn.cpp
+++ b/linker/dlfcn.cpp
@@ -236,16 +236,17 @@
 
 // This is used by the dynamic linker. Every process gets these symbols for free.
 soinfo* get_libdl_info() {
-  if ((__libdl_info.flags & FLAG_LINKED) == 0) {
-    __libdl_info.flags |= FLAG_LINKED;
+  if ((__libdl_info.flags_ & FLAG_LINKED) == 0) {
+    __libdl_info.flags_ |= FLAG_LINKED;
     __libdl_info.strtab_ = ANDROID_LIBDL_STRTAB;
     __libdl_info.symtab_ = g_libdl_symtab;
     __libdl_info.nbucket_ = sizeof(g_libdl_buckets)/sizeof(unsigned);
     __libdl_info.nchain_ = sizeof(g_libdl_chains)/sizeof(unsigned);
     __libdl_info.bucket_ = g_libdl_buckets;
     __libdl_info.chain_ = g_libdl_chains;
-    __libdl_info.ref_count = 1;
+    __libdl_info.ref_count_ = 1;
     __libdl_info.strtab_size_ = sizeof(ANDROID_LIBDL_STRTAB);
+    __libdl_info.local_group_root_ = &__libdl_info;
   }
 
   return &__libdl_info;
diff --git a/linker/linked_list.h b/linker/linked_list.h
index b088061..a72b73c 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -81,6 +81,14 @@
     return element;
   }
 
+  T* front() const {
+    if (head_ == nullptr) {
+      return nullptr;
+    }
+
+    return head_->element;
+  }
+
   void clear() {
     while (head_ != nullptr) {
       LinkedListEntry<T>* p = head_;
diff --git a/linker/linker.cpp b/linker/linker.cpp
index 1d68db5..f2b3d8b 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -230,7 +230,7 @@
 }
 
 static void notify_gdb_of_load(soinfo* info) {
-  if (info->flags & FLAG_EXE) {
+  if (info->is_main_executable()) {
     // GDB already knows about the main executable
     return;
   }
@@ -247,7 +247,7 @@
 }
 
 static void notify_gdb_of_unload(soinfo* info) {
-  if (info->flags & FLAG_EXE) {
+  if (info->is_main_executable()) {
     // GDB already knows about the main executable
     return;
   }
@@ -490,7 +490,7 @@
   memset(this, 0, sizeof(*this));
 
   strlcpy(this->name, name, sizeof(this->name));
-  flags = FLAG_NEW_SOINFO;
+  flags_ = FLAG_NEW_SOINFO;
   version_ = SOINFO_VERSION;
 
   if (file_stat != nullptr) {
@@ -986,21 +986,6 @@
 
 static void soinfo_unload(soinfo* si);
 
-static bool is_recursive(soinfo* si, soinfo* parent) {
-  if (parent == nullptr) {
-    return false;
-  }
-
-  if (si == parent) {
-    DL_ERR("recursive link to \"%s\"", si->name);
-    return true;
-  }
-
-  return !parent->get_parents().visit([&](soinfo* grandparent) {
-    return !is_recursive(si, grandparent);
-  });
-}
-
 // TODO: this is slightly unusual way to construct
 // the global group for relocation. Not every RTLD_GLOBAL
 // library is included in this group for backwards-compatibility
@@ -1067,15 +1052,14 @@
 
     soinfo* needed_by = task->get_needed_by();
 
-    if (is_recursive(si, needed_by)) {
-      return false;
-    }
-
-    si->ref_count++;
     if (needed_by != nullptr) {
       needed_by->add_child(si);
     }
 
+    if (si->is_linked()) {
+      si->increment_ref_count();
+    }
+
     // 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) {
@@ -1102,12 +1086,16 @@
     return true;
   });
 
+  // We need to increment ref_count in case
+  // the root of the local group was not linked.
+  bool was_local_group_root_linked = local_group.front()->is_linked();
+
   bool linked = local_group.visit([&](soinfo* si) {
-    if ((si->flags & FLAG_LINKED) == 0) {
+    if (!si->is_linked()) {
       if (!si->link_image(global_group, local_group, extinfo)) {
         return false;
       }
-      si->flags |= FLAG_LINKED;
+      si->set_linked();
     }
 
     return true;
@@ -1117,72 +1105,101 @@
     failure_guard.disable();
   }
 
+  if (!was_local_group_root_linked) {
+    local_group.front()->increment_ref_count();
+  }
+
   return linked;
 }
 
 static soinfo* find_library(const char* name, int rtld_flags, const android_dlextinfo* extinfo) {
-  if (name == nullptr) {
-    somain->ref_count++;
-    return somain;
-  }
-
   soinfo* si;
 
-  if (!find_libraries(nullptr, &name, 1, &si, nullptr, 0, rtld_flags, extinfo)) {
+  if (name == nullptr) {
+    si = somain;
+  } else if (!find_libraries(nullptr, &name, 1, &si, nullptr, 0, rtld_flags, extinfo)) {
     return nullptr;
   }
 
   return si;
 }
 
-static void soinfo_unload_schedule(soinfo::soinfo_list_t& unload_list, soinfo* si) {
-  if (!si->can_unload()) {
-    TRACE("not unloading '%s' - the binary is flagged with NODELETE", si->name);
+static void soinfo_unload(soinfo* root) {
+  // Note that the library can be loaded but not linked;
+  // in which case there is no root but we still need
+  // to walk the tree and unload soinfos involved.
+  //
+  // This happens on unsuccessful dlopen, when one of
+  // the DT_NEEDED libraries could not be linked/found.
+  if (root->is_linked()) {
+    root = root->get_local_group_root();
+  }
+
+  if (!root->can_unload()) {
+    TRACE("not unloading '%s' - the binary is flagged with NODELETE", root->name);
     return;
   }
 
-  if (si->ref_count == 1) {
-    unload_list.push_back(si);
+  size_t ref_count = root->is_linked() ? root->decrement_ref_count() : 0;
 
-    if (si->has_min_version(0)) {
-      soinfo* child = nullptr;
-      while ((child = si->get_children().pop_front()) != nullptr) {
-        TRACE("%s needs to unload %s", si->name, child->name);
-        soinfo_unload_schedule(unload_list, child);
-      }
-    } else {
-      for_each_dt_needed(si, [&] (const char* library_name) {
-        TRACE("deprecated (old format of soinfo): %s needs to unload %s", si->name, library_name);
-        soinfo* needed = find_library(library_name, RTLD_NOLOAD, nullptr);
-        if (needed != nullptr) {
-          soinfo_unload_schedule(unload_list, needed);
-        } else {
-          // Not found: for example if symlink was deleted between dlopen and dlclose
-          // Since we cannot really handle errors at this point - print and continue.
-          PRINT("warning: couldn't find %s needed by %s on unload.", library_name, si->name);
+  if (ref_count == 0) {
+    soinfo::soinfo_list_t local_unload_list;
+    soinfo::soinfo_list_t external_unload_list;
+    soinfo::soinfo_list_t depth_first_list;
+    depth_first_list.push_back(root);
+    soinfo* si = nullptr;
+
+    while ((si = depth_first_list.pop_front()) != nullptr) {
+      local_unload_list.push_back(si);
+      if (si->has_min_version(0)) {
+        soinfo* child = nullptr;
+        while ((child = si->get_children().pop_front()) != nullptr) {
+          TRACE("%s needs to unload %s", si->name, child->name);
+          if (local_unload_list.contains(child)) {
+            continue;
+          } else if (child->get_local_group_root() != root) {
+            external_unload_list.push_back(child);
+          } else {
+            depth_first_list.push_front(child);
+          }
         }
-      });
+      } else {
+        for_each_dt_needed(si, [&] (const char* library_name) {
+          TRACE("deprecated (old format of soinfo): %s needs to unload %s", si->name, library_name);
+          soinfo* needed = find_library(library_name, RTLD_NOLOAD, nullptr);
+          if (needed != nullptr) {
+            // Not found: for example if symlink was deleted between dlopen and dlclose
+            // Since we cannot really handle errors at this point - print and continue.
+            PRINT("warning: couldn't find %s needed by %s on unload.", library_name, si->name);
+            return;
+          } else if (local_unload_list.contains(needed)) {
+            // already visited
+            return;
+          } else if (needed->get_local_group_root() != root) {
+            // external group
+            external_unload_list.push_back(needed);
+          } else {
+            // local group
+            depth_first_list.push_front(needed);
+          }
+        });
+      }
     }
 
-    si->ref_count = 0;
+    local_unload_list.for_each([](soinfo* si) {
+      si->call_destructors();
+    });
+
+    while ((si = local_unload_list.pop_front()) != nullptr) {
+      notify_gdb_of_unload(si);
+      soinfo_free(si);
+    }
+
+    while ((si = external_unload_list.pop_front()) != nullptr) {
+      soinfo_unload(si);
+    }
   } else {
-    si->ref_count--;
-    TRACE("not unloading '%s', decrementing ref_count to %zd", si->name, si->ref_count);
-  }
-}
-
-static void soinfo_unload(soinfo* root) {
-  soinfo::soinfo_list_t unload_list;
-  soinfo_unload_schedule(unload_list, root);
-  unload_list.for_each([](soinfo* si) {
-    si->call_destructors();
-  });
-
-  soinfo* si = nullptr;
-  while ((si = unload_list.pop_front()) != nullptr) {
-    TRACE("unloading '%s'", si->name);
-    notify_gdb_of_unload(si);
-    soinfo_free(si);
+    TRACE("not unloading '%s' group, decrementing ref_count to %zd", root->name, ref_count);
   }
 }
 
@@ -1838,7 +1855,7 @@
   //    out above, the libc constructor will be called again (recursively!).
   constructors_called = true;
 
-  if ((flags & FLAG_EXE) == 0 && preinit_array_ != nullptr) {
+  if (!is_main_executable() && preinit_array_ != nullptr) {
     // The GNU dynamic linker silently ignores these, but we warn the developer.
     PRINT("\"%s\": ignoring %zd-entry DT_PREINIT_ARRAY in shared library!",
           name, preinit_array_count_);
@@ -1992,13 +2009,45 @@
 }
 
 bool soinfo::is_gnu_hash() const {
-  return (flags & FLAG_GNU_HASH) != 0;
+  return (flags_ & FLAG_GNU_HASH) != 0;
 }
 
 bool soinfo::can_unload() const {
   return (get_rtld_flags() & (RTLD_NODELETE | RTLD_GLOBAL)) == 0;
 }
 
+bool soinfo::is_linked() const {
+  return (flags_ & FLAG_LINKED) != 0;
+}
+
+bool soinfo::is_main_executable() const {
+  return (flags_ & FLAG_EXE) != 0;
+}
+
+void soinfo::set_linked() {
+  flags_ |= FLAG_LINKED;
+}
+
+void soinfo::set_linker_flag() {
+  flags_ |= FLAG_LINKER;
+}
+
+void soinfo::set_main_executable() {
+  flags_ |= FLAG_EXE;
+}
+
+void soinfo::increment_ref_count() {
+  local_group_root_->ref_count_++;
+}
+
+size_t soinfo::decrement_ref_count() {
+  return --local_group_root_->ref_count_;
+}
+
+soinfo* soinfo::get_local_group_root() const {
+  return local_group_root_;
+}
+
 /* Force any of the closed stdin, stdout and stderr to be associated with
    /dev/null. */
 static int nullify_closed_stdio() {
@@ -2066,10 +2115,10 @@
   phdr_table_get_dynamic_section(phdr, phnum, load_bias, &dynamic, &dynamic_flags);
 
   /* We can't log anything until the linker is relocated */
-  bool relocating_linker = (flags & FLAG_LINKER) != 0;
+  bool relocating_linker = (flags_ & FLAG_LINKER) != 0;
   if (!relocating_linker) {
     INFO("[ linking %s ]", name);
-    DEBUG("si->base = %p si->flags = 0x%08x", reinterpret_cast<void*>(base), flags);
+    DEBUG("si->base = %p si->flags = 0x%08x", reinterpret_cast<void*>(base), flags_);
   }
 
   if (dynamic == nullptr) {
@@ -2133,7 +2182,7 @@
         }
         --gnu_maskwords_;
 
-        flags |= FLAG_GNU_HASH;
+        flags_ |= FLAG_GNU_HASH;
         break;
 
       case DT_STRTAB:
@@ -2406,6 +2455,11 @@
 
 bool soinfo::link_image(const soinfo_list_t& global_group, const soinfo_list_t& local_group, const android_dlextinfo* extinfo) {
 
+  local_group_root_ = local_group.front();
+  if (local_group_root_ == nullptr) {
+    local_group_root_ = this;
+  }
+
 #if !defined(__LP64__)
   if (has_text_relocations) {
     // Make segments writable to allow text relocations to work properly. We will later call
@@ -2598,7 +2652,7 @@
   }
 
   /* bootstrap the link map, the main exe always needs to be first */
-  si->flags |= FLAG_EXE;
+  si->set_main_executable();
   link_map* map = &(si->link_map_head);
 
   map->l_addr = 0;
@@ -2631,7 +2685,6 @@
     }
   }
   si->dynamic = nullptr;
-  si->ref_count = 1;
 
   ElfW(Ehdr)* elf_hdr = reinterpret_cast<ElfW(Ehdr)*>(si->base);
   if (elf_hdr->e_type != ET_DYN) {
@@ -2672,6 +2725,12 @@
   if (needed_libraries_count > 0 && !find_libraries(si, needed_library_names, needed_libraries_count, nullptr, g_ld_preloads, ld_preloads_count, RTLD_GLOBAL, nullptr)) {
     __libc_format_fd(2, "CANNOT LINK EXECUTABLE: %s\n", linker_get_error_buffer());
     exit(EXIT_FAILURE);
+  } else if (needed_libraries_count == 0) {
+    if (!si->link_image(g_empty_list, soinfo::soinfo_list_t::make_list(si), nullptr)) {
+      __libc_format_fd(2, "CANNOT LINK EXECUTABLE: %s\n", linker_get_error_buffer());
+      exit(EXIT_FAILURE);
+    }
+    si->increment_ref_count();
   }
 
   add_vdso(args);
@@ -2791,7 +2850,7 @@
   linker_so.dynamic = nullptr;
   linker_so.phdr = phdr;
   linker_so.phnum = elf_hdr->e_phnum;
-  linker_so.flags |= FLAG_LINKER;
+  linker_so.set_linker_flag();
 
   // 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
diff --git a/linker/linker.h b/linker/linker.h
index d28f70e..f7aa11c 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -161,9 +161,9 @@
 #endif
 
   soinfo* next;
-  uint32_t flags;
-
  private:
+  uint32_t flags_;
+
   const char* strtab_;
   ElfW(Sym)* symtab_;
 
@@ -203,22 +203,21 @@
   linker_function_t init_func_;
   linker_function_t fini_func_;
 
- public:
 #if defined(__arm__)
+ public:
   // ARM EABI section used for stack unwinding.
   uint32_t* ARM_exidx;
   size_t ARM_exidx_count;
-#elif defined(__mips__)
  private:
+#elif defined(__mips__)
   uint32_t mips_symtabno_;
   uint32_t mips_local_gotno_;
   uint32_t mips_gotsym_;
   bool mips_relocate_got(const soinfo_list_t& global_group, const soinfo_list_t& local_group);
 
 #endif
-
+  size_t ref_count_;
  public:
-  size_t ref_count;
   link_map link_map_head;
 
   bool constructors_called;
@@ -264,9 +263,21 @@
   bool is_gnu_hash() const;
 
   bool inline has_min_version(uint32_t min_version) const {
-    return (flags & FLAG_NEW_SOINFO) != 0 && version_ >= min_version;
+    return (flags_ & FLAG_NEW_SOINFO) != 0 && version_ >= min_version;
   }
 
+  bool is_linked() const;
+  bool is_main_executable() const;
+
+  void set_linked();
+  void set_linker_flag();
+  void set_main_executable();
+
+  void increment_ref_count();
+  size_t decrement_ref_count();
+
+  soinfo* get_local_group_root() const;
+
  private:
   ElfW(Sym)* elf_lookup(SymbolName& symbol_name);
   ElfW(Sym)* elf_addr_lookup(const void* addr);
@@ -303,9 +314,10 @@
   // version >= 2
   uint32_t gnu_maskwords_;
   uint32_t gnu_shift2_;
-
   ElfW(Addr)* gnu_bloom_filter_;
 
+  soinfo* local_group_root_;
+
   friend soinfo* get_libdl_info();
 };