diff --git a/elf/dl-close.c b/elf/dl-close.c
index 5d31389c91..19eadc8ede 100644
--- a/elf/dl-close.c
+++ b/elf/dl-close.c
@@ -167,30 +167,31 @@ _dl_close_worker (struct link_map *map, bool force)
 
   bool any_tls = false;
   const unsigned int nloaded = ns->_ns_nloaded;
-  struct link_map *maps[nloaded];
 
-  /* Run over the list and assign indexes to the link maps and enter
-     them into the MAPS array.  */
+  /* Run over the list and assign indexes to the link maps.  */
   int idx = 0;
   for (struct link_map *l = ns->_ns_loaded; l != NULL; l = l->l_next)
     {
       l->l_map_used = 0;
       l->l_map_done = 0;
       l->l_idx = idx;
-      maps[idx] = l;
       ++idx;
     }
   assert (idx == nloaded);
 
-  /* Keep track of the lowest index link map we have covered already.  */
-  int done_index = -1;
-  while (++done_index < nloaded)
+  /* Keep marking link maps until no new link maps are found.  */
+  for (struct link_map *l = ns->_ns_loaded; l != NULL; )
     {
-      struct link_map *l = maps[done_index];
+      /* next is reset to earlier link maps for remarking.  */
+      struct link_map *next = l->l_next;
+      int next_idx = l->l_idx + 1; /* next->l_idx, but covers next == NULL.  */
 
       if (l->l_map_done)
-	/* Already handled.  */
-	continue;
+	{
+	  /* Already handled.  */
+	  l = next;
+	  continue;
+	}
 
       /* Check whether this object is still used.  */
       if (l->l_type == lt_loaded
@@ -200,7 +201,10 @@ _dl_close_worker (struct link_map *map, bool force)
 	     acquire is sufficient and correct.  */
 	  && atomic_load_acquire (&l->l_tls_dtor_count) == 0
 	  && !l->l_map_used)
-	continue;
+	{
+	  l = next;
+	  continue;
+	}
 
       /* We need this object and we handle it now.  */
       l->l_map_used = 1;
@@ -227,8 +231,11 @@ _dl_close_worker (struct link_map *map, bool force)
 			 already processed it, then we need to go back
 			 and process again from that point forward to
 			 ensure we keep all of its dependencies also.  */
-		      if ((*lp)->l_idx - 1 < done_index)
-			done_index = (*lp)->l_idx - 1;
+		      if ((*lp)->l_idx < next_idx)
+			{
+			  next = *lp;
+			  next_idx = next->l_idx;
+			}
 		    }
 		}
 
@@ -248,51 +255,50 @@ _dl_close_worker (struct link_map *map, bool force)
 		if (!jmap->l_map_used)
 		  {
 		    jmap->l_map_used = 1;
-		    if (jmap->l_idx - 1 < done_index)
-		      done_index = jmap->l_idx - 1;
+		    if (jmap->l_idx < next_idx)
+		      {
+			  next = jmap;
+			  next_idx = next->l_idx;
+		      }
 		  }
 	      }
 	  }
-    }
 
-  /* Sort the entries.  We can skip looking for the binary itself which is
-     at the front of the search list for the main namespace.  */
-  _dl_sort_maps (maps, nloaded, (nsid == LM_ID_BASE));
+      l = next;
+    }
 
   /* Call all termination functions at once.  */
 #ifdef SHARED
   bool do_audit = GLRO(dl_naudit) > 0 && !ns->_ns_loaded->l_auditing;
 #endif
-  bool unload_any = false;
-  bool scope_mem_left = false;
-  unsigned int unload_global = 0;
-  unsigned int first_loaded = ~0;
-  for (unsigned int i = 0; i < nloaded; ++i)
-    {
-      struct link_map *imap = maps[i];
 
-      /* All elements must be in the same namespace.  */
-      assert (imap->l_ns == nsid);
+  /* Call the destructors in reverse constructor order, and remove the
+     closed link maps from the list.  */
+  for (struct link_map **init_called_head = &_dl_init_called_list;
+       *init_called_head != NULL; )
+    {
+      struct link_map *imap = *init_called_head;
 
-      if (!imap->l_map_used)
+      /* _dl_init_called_list is global, to produce a global odering.
+	 Ignore the other namespaces (and link maps that are still used).  */
+      if (imap->l_ns != nsid || imap->l_map_used)
+	init_called_head = &imap->l_init_called_next;
+      else
 	{
 	  assert (imap->l_type == lt_loaded && !imap->l_nodelete_active);
 
-	  /* Call its termination function.  Do not do it for
-	     half-cooked objects.  Temporarily disable exception
-	     handling, so that errors are fatal.  */
-	  if (imap->l_init_called)
-	    {
-	      /* When debugging print a message first.  */
-	      if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_IMPCALLS,
-				    0))
-		_dl_debug_printf ("\ncalling fini: %s [%lu]\n\n",
-				  imap->l_name, nsid);
-
-	      if (imap->l_info[DT_FINI_ARRAY] != NULL
-		  || imap->l_info[DT_FINI] != NULL)
-		_dl_catch_exception (NULL, call_destructors, imap);
-	    }
+	  /* _dl_init_called_list is updated at the same time as
+	     l_init_called.  */
+	  assert (imap->l_init_called);
+
+	  /* When debugging print a message first.  */
+	  if (__builtin_expect (GLRO(dl_debug_mask) & DL_DEBUG_IMPCALLS, 0))
+	    _dl_debug_printf ("\ncalling fini: %s [%lu]\n\n",
+			      imap->l_name, nsid);
+
+	  if (imap->l_info[DT_FINI_ARRAY] != NULL
+	      || imap->l_info[DT_FINI] != NULL)
+	    _dl_catch_exception (NULL, call_destructors, imap);
 
 #ifdef SHARED
 	  /* Auditing checkpoint: we remove an object.  */
@@ -313,7 +319,26 @@ _dl_close_worker (struct link_map *map, bool force)
 		}
 	    }
 #endif
+	  /* Unlink this link map.  */
+	  *init_called_head = imap->l_init_called_next;
+	}
+    }
+
+
+  bool unload_any = false;
+  bool scope_mem_left = false;
+  unsigned int unload_global = 0;
 
+  /* For skipping un-unloadable link maps in the second loop.  */
+  struct link_map *first_loaded = ns->_ns_loaded;
+
+  /* Iterate over the namespace to find objects to unload.  Some
+     unloadable objects may not be on _dl_init_called_list due to
+     dlopen failure.  */
+  for (struct link_map *imap = first_loaded; imap != NULL; imap = imap->l_next)
+    {
+      if (!imap->l_map_used)
+	{
 	  /* This object must not be used anymore.  */
 	  imap->l_removed = 1;
 
@@ -324,8 +349,8 @@ _dl_close_worker (struct link_map *map, bool force)
 	    ++unload_global;
 
 	  /* Remember where the first dynamically loaded object is.  */
-	  if (i < first_loaded)
-	    first_loaded = i;
+	  if (first_loaded == NULL)
+	      first_loaded = imap;
 	}
       /* Else imap->l_map_used.  */
       else if (imap->l_type == lt_loaded)
@@ -461,8 +486,8 @@ _dl_close_worker (struct link_map *map, bool force)
 	    imap->l_loader = NULL;
 
 	  /* Remember where the first dynamically loaded object is.  */
-	  if (i < first_loaded)
-	    first_loaded = i;
+	  if (first_loaded == NULL)
+	      first_loaded = imap;
 	}
     }
 
@@ -551,10 +576,11 @@ _dl_close_worker (struct link_map *map, bool force)
 
   /* Check each element of the search list to see if all references to
      it are gone.  */
-  for (unsigned int i = first_loaded; i < nloaded; ++i)
+  for (struct link_map *imap = first_loaded; imap != NULL; )
     {
-      struct link_map *imap = maps[i];
-      if (!imap->l_map_used)
+      if (imap->l_map_used)
+	imap = imap->l_next;
+      else
 	{
 	  assert (imap->l_type == lt_loaded);
 
@@ -762,7 +788,9 @@ _dl_close_worker (struct link_map *map, bool force)
 	  if (imap == GL(dl_initfirst))
 	    GL(dl_initfirst) = NULL;
 
+	  struct link_map *next = imap->l_next;
 	  free (imap);
+	  imap = next;
 	}
     }
 
diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index 1aa47bc7c5..bb76bea27f 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
@@ -29,154 +29,98 @@ typedef void (*fini_t) (void);
 void
 _dl_fini (void)
 {
-  /* Lots of fun ahead.  We have to call the destructors for all still
-     loaded objects, in all namespaces.  The problem is that the ELF
-     specification now demands that dependencies between the modules
-     are taken into account.  I.e., the destructor for a module is
-     called before the ones for any of its dependencies.
-
-     To make things more complicated, we cannot simply use the reverse
-     order of the constructors.  Since the user might have loaded objects
-     using `dlopen' there are possibly several other modules with its
-     dependencies to be taken into account.  Therefore we have to start
-     determining the order of the modules once again from the beginning.  */
-
-  /* We run the destructors of the main namespaces last.  As for the
-     other namespaces, we pick run the destructors in them in reverse
-     order of the namespace ID.  */
+  /* Call destructors strictly in the reverse order of constructors.
+     This causes fewer surprises than some arbitrary reordering based
+     on new (relocation) dependencies.  None of the objects are
+     unmapped, so applications can deal with this if their DSOs remain
+     in a consistent state after destructors have run.  */
+
+  /* Protect against concurrent loads and unloads.  */
+  __rtld_lock_lock_recursive (GL(dl_load_lock));
+
+  /* Ignore objects which are opened during shutdown.  */
+  struct link_map *local_init_called_list = _dl_init_called_list;
+
+  for (struct link_map *l = local_init_called_list; l != NULL;
+       l = l->l_init_called_next)
+      /* Bump l_direct_opencount of all objects so that they
+	 are not dlclose()ed from underneath us.  */
+      ++l->l_direct_opencount;
+
+  /* After this point, Everything linked from local_init_called_list
+     cannot be unloaded because of the reference counter update.  */
+  __rtld_lock_unlock_recursive (GL(dl_load_lock));
+
+  /* Perform two passes: One for non-audit modules, one for audit
+     modules.  */
 #ifdef SHARED
-  int do_audit = 0;
- again:
+  int last_pass = GLRO(dl_naudit) > 0;
+  for (int do_audit = 0; do_audit <= last_pass; ++do_audit)
 #endif
-  for (Lmid_t ns = GL(dl_nns) - 1; ns >= 0; --ns)
-    {
-      /* Protect against concurrent loads and unloads.  */
-      __rtld_lock_lock_recursive (GL(dl_load_lock));
-
-      unsigned int nloaded = GL(dl_ns)[ns]._ns_nloaded;
-      /* No need to do anything for empty namespaces or those used for
-	 auditing DSOs.  */
-      if (nloaded == 0
+    for (struct link_map *l = local_init_called_list; l != NULL;
+	 l = l->l_init_called_next)
+      {
 #ifdef SHARED
-	  || GL(dl_ns)[ns]._ns_loaded->l_auditing != do_audit
+	if (GL(dl_ns)[l->l_ns]._ns_loaded->l_auditing != do_audit)
+	  continue;
 #endif
-	  )
-	__rtld_lock_unlock_recursive (GL(dl_load_lock));
-      else
-	{
-	  /* Now we can allocate an array to hold all the pointers and
-	     copy the pointers in.  */
-	  struct link_map *maps[nloaded];
-
-	  unsigned int i;
-	  struct link_map *l;
-	  assert (nloaded != 0 || GL(dl_ns)[ns]._ns_loaded == NULL);
-	  for (l = GL(dl_ns)[ns]._ns_loaded, i = 0; l != NULL; l = l->l_next)
-	    /* Do not handle ld.so in secondary namespaces.  */
-	    if (l == l->l_real)
-	      {
-		assert (i < nloaded);
 
-		maps[i] = l;
-		l->l_idx = i;
-		++i;
+	if (l->l_init_called)
+	  {
+	    /* Make sure nothing happens if we are called twice.  */
+	    l->l_init_called = 0;
 
-		/* Bump l_direct_opencount of all objects so that they
-		   are not dlclose()ed from underneath us.  */
-		++l->l_direct_opencount;
+	    /* Is there a destructor function?  */
+	    if (l->l_info[DT_FINI_ARRAY] != NULL
+		|| (ELF_INITFINI && l->l_info[DT_FINI] != NULL))
+	      {
+		/* When debugging print a message first.  */
+		if (__builtin_expect (GLRO(dl_debug_mask)
+				      & DL_DEBUG_IMPCALLS, 0))
+		  _dl_debug_printf ("\ncalling fini: %s [%lu]\n\n",
+				    DSO_FILENAME (l->l_name),
+				    l->l_ns);
+
+		/* First see whether an array is given.  */
+		if (l->l_info[DT_FINI_ARRAY] != NULL)
+		  {
+		    ElfW(Addr) *array =
+		      (ElfW(Addr) *) (l->l_addr
+				      + l->l_info[DT_FINI_ARRAY]->d_un.d_ptr);
+		    unsigned int i = (l->l_info[DT_FINI_ARRAYSZ]->d_un.d_val
+				      / sizeof (ElfW(Addr)));
+		    while (i-- > 0)
+		      ((fini_t) array[i]) ();
+		  }
+
+		/* Next try the old-style destructor.  */
+		if (ELF_INITFINI && l->l_info[DT_FINI] != NULL)
+		  DL_CALL_DT_FINI
+		    (l, l->l_addr + l->l_info[DT_FINI]->d_un.d_ptr);
 	      }
-	  assert (ns != LM_ID_BASE || i == nloaded);
-	  assert (ns == LM_ID_BASE || i == nloaded || i == nloaded - 1);
-	  unsigned int nmaps = i;
-
-	  /* Now we have to do the sorting.  We can skip looking for the
-	     binary itself which is at the front of the search list for
-	     the main namespace.  */
-	  _dl_sort_maps (maps, nmaps, (ns == LM_ID_BASE));
-
-	  /* We do not rely on the linked list of loaded object anymore
-	     from this point on.  We have our own list here (maps).  The
-	     various members of this list cannot vanish since the open
-	     count is too high and will be decremented in this loop.  So
-	     we release the lock so that some code which might be called
-	     from a destructor can directly or indirectly access the
-	     lock.  */
-	  __rtld_lock_unlock_recursive (GL(dl_load_lock));
-
-	  /* 'maps' now contains the objects in the right order.  Now
-	     call the destructors.  We have to process this array from
-	     the front.  */
-	  for (i = 0; i < nmaps; ++i)
-	    {
-	      struct link_map *l = maps[i];
-
-	      if (l->l_init_called)
-		{
-		  /* Make sure nothing happens if we are called twice.  */
-		  l->l_init_called = 0;
-
-		  /* Is there a destructor function?  */
-		  if (l->l_info[DT_FINI_ARRAY] != NULL
-		      || (ELF_INITFINI && l->l_info[DT_FINI] != NULL))
-		    {
-		      /* When debugging print a message first.  */
-		      if (__builtin_expect (GLRO(dl_debug_mask)
-					    & DL_DEBUG_IMPCALLS, 0))
-			_dl_debug_printf ("\ncalling fini: %s [%lu]\n\n",
-					  DSO_FILENAME (l->l_name),
-					  ns);
-
-		      /* First see whether an array is given.  */
-		      if (l->l_info[DT_FINI_ARRAY] != NULL)
-			{
-			  ElfW(Addr) *array =
-			    (ElfW(Addr) *) (l->l_addr
-					    + l->l_info[DT_FINI_ARRAY]->d_un.d_ptr);
-			  unsigned int i = (l->l_info[DT_FINI_ARRAYSZ]->d_un.d_val
-					    / sizeof (ElfW(Addr)));
-			  while (i-- > 0)
-			    ((fini_t) array[i]) ();
-			}
-
-		      /* Next try the old-style destructor.  */
-		      if (ELF_INITFINI && l->l_info[DT_FINI] != NULL)
-			DL_CALL_DT_FINI
-			  (l, l->l_addr + l->l_info[DT_FINI]->d_un.d_ptr);
-		    }
 
 #ifdef SHARED
-		  /* Auditing checkpoint: another object closed.  */
-		  if (!do_audit && __builtin_expect (GLRO(dl_naudit) > 0, 0))
-		    {
-		      struct audit_ifaces *afct = GLRO(dl_audit);
-		      for (unsigned int cnt = 0; cnt < GLRO(dl_naudit); ++cnt)
-			{
-			  if (afct->objclose != NULL)
-			    {
-			      struct auditstate *state
-				= link_map_audit_state (l, cnt);
-			      /* Return value is ignored.  */
-			      (void) afct->objclose (&state->cookie);
-			    }
-			  afct = afct->next;
-			}
-		    }
+	    /* Auditing checkpoint: another object closed.  */
+	    if (!do_audit && __builtin_expect (GLRO(dl_naudit) > 0, 0))
+	      {
+		struct audit_ifaces *afct = GLRO(dl_audit);
+		for (unsigned int cnt = 0; cnt < GLRO(dl_naudit); ++cnt)
+		  {
+		    if (afct->objclose != NULL)
+		      {
+			struct auditstate *state
+			  = link_map_audit_state (l, cnt);
+			/* Return value is ignored.  */
+			(void) afct->objclose (&state->cookie);
+		      }
+		    afct = afct->next;
+		  }
+	      }
 #endif
-		}
-
-	      /* Correct the previous increment.  */
-	      --l->l_direct_opencount;
-	    }
-	}
-    }
+	  }
+      }
 
 #ifdef SHARED
-  if (! do_audit && GLRO(dl_naudit) > 0)
-    {
-      do_audit = 1;
-      goto again;
-    }
-
   if (__glibc_unlikely (GLRO(dl_debug_mask) & DL_DEBUG_STATISTICS))
     _dl_debug_printf ("\nruntime linker statistics:\n"
 		      "           final number of relocations: %lu\n"
diff --git a/elf/dl-init.c b/elf/dl-init.c
index f924d26642..a6dcfdb25d 100644
--- a/elf/dl-init.c
+++ b/elf/dl-init.c
@@ -21,6 +21,7 @@
 #include <ldsodefs.h>
 #include <elf-initfini.h>
 
+struct link_map *_dl_init_called_list;
 
 static void
 call_init (struct link_map *l, int argc, char **argv, char **env)
@@ -38,6 +39,19 @@ call_init (struct link_map *l, int argc, char **argv, char **env)
      dependency.  */
   l->l_init_called = 1;
 
+  /* Help an already-running dlclose: The just-loaded object must not
+     be removed during the current pass.  (No effect if no dlclose in
+     progress.)  */
+  l->l_map_used = 1;
+
+  /* Record execution before starting any initializers.  This way, if
+     the initializers themselves call dlopen, their ELF destructors
+     will eventually be run before this object is destructed, matching
+     that their ELF constructors have run before this object was
+     constructed.  */
+  l->l_init_called_next = _dl_init_called_list;
+  _dl_init_called_list = l;
+
   /* Check for object which constructors we do not run here.  */
   if (__builtin_expect (l->l_name[0], 'a') == '\0'
       && l->l_type == lt_executable)
diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def
index c2398408cd..96c4533c3b 100644
--- a/elf/dso-sort-tests-1.def
+++ b/elf/dso-sort-tests-1.def
@@ -59,4 +59,4 @@ output: b>a>{}<a<b
 # The below expected outputs are what the two algorithms currently produce
 # respectively, for regression testing purposes.
 tst-bz15311: {+a;+e;+f;+g;+d;%d;-d;-g;-f;-e;-a};a->b->c->d;d=>[ba];c=>a;b=>e=>a;c=>f=>b;d=>g=>c
-output: {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<a<b<c<d<e<f<g];}
+output: {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<g<f<e<a<b<c<d];}
diff --git a/include/link.h b/include/link.h
index c1c382ccfa..ce2b000dcd 100644
--- a/include/link.h
+++ b/include/link.h
@@ -277,6 +277,10 @@ struct link_map
     /* List of object in order of the init and fini calls.  */
     struct link_map **l_initfini;
 
+    /* Linked list of objects in reverse ELF constructor execution
+       order.  Head of list is stored in _dl_init_called_list.  */
+    struct link_map *l_init_called_next;
+
     /* List of the dependencies introduced through symbol binding.  */
     struct link_map_reldeps
       {
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
index a66b68eaea..fd591cf280 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
@@ -1111,6 +1111,10 @@ extern int _dl_check_map_versions (struct link_map *map, int verbose,
 extern void _dl_init (struct link_map *main_map, int argc, char **argv,
 		      char **env) attribute_hidden;
 
+/* List of ELF objects in reverse order of their constructor
+   invocation.  */
+extern struct link_map *_dl_init_called_list attribute_hidden;
+
 /* Call the finalizer functions of all shared objects whose
    initializer functions have completed.  */
 extern void _dl_fini (void) attribute_hidden;
