[PATCH 0/2] Predictable ELF destructor ordering

[PATCH 0/2] Predictable ELF destructor ordering

[Florian Weimer]

These patches remove the dependency sorting from dlclose and process
shutdown, so that destructor order is the reverse of constructor order
in more cases (always if the process does not call dlclose).

Tested on i686-linux-gnu and x86_64-linux-gnu.

I would like to include this in glibc 2.35 if possible, among the other
dependency sorting changes.

I believe this fixes bugs 15311 and 15903.

Florian Weimer (2):
  elf: Do not rely on relocation dependencies for destructor sorting
  elf: Always call destructors in reverse constructor order

 elf/dl-close.c             | 130 +++++++++++++---------
 elf/dl-deps.c              |   3 +-
 elf/dl-fini.c              | 216 ++++++++++++++-----------------------
 elf/dl-init.c              |  14 +++
 elf/dl-sort-maps.c         | 105 ++----------------
 elf/dso-sort-tests-1.def   |   6 +-
 include/link.h             |   4 +
 sysdeps/generic/ldsodefs.h |   6 +-
 8 files changed, 194 insertions(+), 290 deletions(-)


base-commit: 0884724a95b60452ad483dbe086d237d02ba624d
-- 
2.33.1

[PATCH 1/2] elf: Do not rely on relocation dependencies for destructor sorting

[Florian Weimer]

The new solution to tst-bz15311 preserves the <a<b<c<d<e order
in both cases, but f and g are not ordered in reverse construction
order yet.  This is fine given that the test case is technically
undefined.
---
 elf/dl-close.c             |   2 +-
 elf/dl-deps.c              |   3 +-
 elf/dl-fini.c              |   2 +-
 elf/dl-sort-maps.c         | 105 ++++---------------------------------
 elf/dso-sort-tests-1.def   |   6 +--
 sysdeps/generic/ldsodefs.h |   2 +-
 6 files changed, 15 insertions(+), 105 deletions(-)

diff --git a/elf/dl-close.c b/elf/dl-close.c
index 4f5cfcc1c3..5d31389c91 100644
--- a/elf/dl-close.c
+++ b/elf/dl-close.c
@@ -257,7 +257,7 @@ _dl_close_worker (struct link_map *map, bool force)
 
   /* 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), true);
+  _dl_sort_maps (maps, nloaded, (nsid == LM_ID_BASE));
 
   /* Call all termination functions at once.  */
 #ifdef SHARED
diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index 237d9636c5..c7577d9335 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -614,8 +614,7 @@ Filters not supported with LD_TRACE_PRELINKING"));
   /* If libc.so.6 is the main map, it participates in the sort, so
      that the relocation order is correct regarding libc.so.6.  */
   _dl_sort_maps (l_initfini, nlist,
-		 (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map),
-		 false);
+		 (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map));
 
   /* Terminate the list of dependencies.  */
   l_initfini[nlist] = NULL;
diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index c683884c35..1aa47bc7c5 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
@@ -92,7 +92,7 @@ _dl_fini (void)
 	  /* 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), true);
+	  _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
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
index a274ed66cc..87e63fdb4b 100644
--- a/elf/dl-sort-maps.c
+++ b/elf/dl-sort-maps.c
@@ -23,11 +23,10 @@
 /* Note: this is the older, "original" sorting algorithm, being used as
    default up to 2.35.
 
-   Sort array MAPS according to dependencies of the contained objects.
-   If FOR_FINI is true, this is called for finishing an object.  */
+   Sort array MAPS according to dependencies of the contained objects.  */
 static void
 _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
-			unsigned int skip, bool for_fini)
+			unsigned int skip)
 {
   /* Allows caller to do the common optimization of skipping the first map,
      usually the main binary.  */
@@ -47,14 +46,6 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
       ++seen[i];
       struct link_map *thisp = maps[i];
 
-      if (__glibc_unlikely (for_fini))
-	{
-	  /* Do not handle ld.so in secondary namespaces and objects which
-	     are not removed.  */
-	  if (thisp != thisp->l_real || thisp->l_idx == -1)
-	    goto skip;
-	}
-
       /* Find the last object in the list for which the current one is
 	 a dependency and move the current object behind the object
 	 with the dependency.  */
@@ -67,7 +58,6 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
 	    while (*runp != NULL)
 	      if (__glibc_unlikely (*runp++ == thisp))
 		{
-		move:
 		  /* Move the current object to the back past the last
 		     object with it as the dependency.  */
 		  memmove (&maps[i], &maps[i + 1],
@@ -87,31 +77,9 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
 		  goto next;
 		}
 
-	  if (__glibc_unlikely (for_fini && maps[k]->l_reldeps != NULL))
-	    {
-	      unsigned int m = maps[k]->l_reldeps->act;
-	      struct link_map **relmaps = &maps[k]->l_reldeps->list[0];
-
-	      /* Look through the relocation dependencies of the object.  */
-	      while (m-- > 0)
-		if (__glibc_unlikely (relmaps[m] == thisp))
-		  {
-		    /* If a cycle exists with a link time dependency,
-		       preserve the latter.  */
-		    struct link_map **runp = thisp->l_initfini;
-		    if (runp != NULL)
-		      while (*runp != NULL)
-			if (__glibc_unlikely (*runp++ == maps[k]))
-			  goto ignore;
-		    goto move;
-		  }
-	    ignore:;
-	    }
-
 	  --k;
 	}
 
-    skip:
       if (++i == nmaps)
 	break;
     next_clear:
@@ -137,8 +105,7 @@ strong_alias (_dl_sort_maps_original, _dl_sort_maps);
    decremented before storing the current map at each level.  */
 
 static void
-dfs_traversal (struct link_map ***rpo, struct link_map *map,
-	       bool *do_reldeps)
+dfs_traversal (struct link_map ***rpo, struct link_map *map)
 {
   if (map->l_visited)
     return;
@@ -152,22 +119,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map,
 	  struct link_map *dep = map->l_initfini[i];
 	  if (dep->l_visited == 0
 	      && dep->l_main_map == 0)
-	    dfs_traversal (rpo, dep, do_reldeps);
-	}
-    }
-
-  if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL))
-    {
-      /* Indicate that we encountered relocation dependencies during
-	 traversal.  */
-      *do_reldeps = true;
-
-      for (int m = map->l_reldeps->act - 1; m >= 0; m--)
-	{
-	  struct link_map *dep = map->l_reldeps->list[m];
-	  if (dep->l_visited == 0
-	      && dep->l_main_map == 0)
-	    dfs_traversal (rpo, dep, do_reldeps);
+	    dfs_traversal (rpo, dep);
 	}
     }
 
@@ -180,7 +132,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map,
 
 static void
 _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
-		   unsigned int skip __attribute__ ((unused)), bool for_fini)
+		   unsigned int skip __attribute__ ((unused)))
 {
   for (int i = nmaps - 1; i >= 0; i--)
     maps[i]->l_visited = 0;
@@ -225,52 +177,15 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps,
      bottom of above dfs_traversal() routine).  */
   struct link_map **rpo_head = &rpo[nmaps];
 
-  bool do_reldeps = false;
-  bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL);
-
   for (int i = nmaps - 1; i >= 0; i--)
     {
-      dfs_traversal (&rpo_head, maps[i], do_reldeps_ref);
-
+      dfs_traversal (&rpo_head, maps[i]);
       /* We can break early if all objects are already placed.  */
       if (rpo_head == rpo)
-	goto end;
+	break;
     }
   assert (rpo_head == rpo);
 
- end:
-  /* Here we may do a second pass of sorting, using only l_initfini[]
-     static dependency links. This is avoided if !FOR_FINI or if we didn't
-     find any reldeps in the first DFS traversal.
-
-     The reason we do this is: while it is unspecified how circular
-     dependencies should be handled, the presumed reasonable behavior is to
-     have destructors to respect static dependency links as much as possible,
-     overriding reldeps if needed. And the first sorting pass, which takes
-     l_initfini/l_reldeps links equally, may not preserve this priority.
-
-     Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account
-     (see how the do_reldeps argument to dfs_traversal() is NULL below).  */
-  if (do_reldeps)
-    {
-      for (int i = nmaps - 1; i >= 0; i--)
-	rpo[i]->l_visited = 0;
-
-      struct link_map **maps_head = &maps[nmaps];
-      for (int i = nmaps - 1; i >= 0; i--)
-	{
-	  dfs_traversal (&maps_head, rpo[i], NULL);
-
-	  /* We can break early if all objects are already placed.
-	     The below memcpy is not needed in the do_reldeps case here,
-	     since we wrote back to maps[] during DFS traversal.  */
-	  if (maps_head == maps)
-	    return;
-	}
-      assert (maps_head == maps);
-      return;
-    }
-
   memcpy (maps, rpo, sizeof (struct link_map *) * nmaps);
 }
 
@@ -284,7 +199,7 @@ _dl_sort_maps_init (void)
 
 void
 _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
-	       unsigned int skip, bool for_fini)
+	       unsigned int skip)
 {
   /* It can be tempting to use a static function pointer to store and call
      the current selected sorting algorithm routine, but experimentation
@@ -294,9 +209,9 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
      input cases. A simple if-case with direct function calls appears to
      be the fastest.  */
   if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
-    _dl_sort_maps_original (maps, nmaps, skip, for_fini);
+    _dl_sort_maps_original (maps, nmaps, skip);
   else
-    _dl_sort_maps_dfs (maps, nmaps, skip, for_fini);
+    _dl_sort_maps_dfs (maps, nmaps, skip);
 }
 
 #endif /* HAVE_TUNABLES.  */
diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def
index 5f7f18ef27..c2398408cd 100644
--- a/elf/dso-sort-tests-1.def
+++ b/elf/dso-sort-tests-1.def
@@ -56,11 +56,7 @@ output: b>a>{}<a<b
 # relocation(dynamic) dependencies. While this is technically unspecified, the
 # presumed reasonable practical behavior is for the destructor order to respect
 # the static DT_NEEDED links (here this means the a->b->c->d order).
-# The older dynamic_sort=1 algorithm does not achieve this, while the DFS-based
-# dynamic_sort=2 algorithm does, although it is still arguable whether going
-# beyond spec to do this is the right thing to do.
 # 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(glibc.rtld.dynamic_sort=1): {+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<c<d<g<f<b<e];}
-output(glibc.rtld.dynamic_sort=2): {+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<a<b<c<d<e];}
+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];}
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
index c26860430c..a66b68eaea 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
@@ -1117,7 +1117,7 @@ extern void _dl_fini (void) attribute_hidden;
 
 /* Sort array MAPS according to dependencies of the contained objects.  */
 extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
-			   unsigned int skip, bool for_fini) attribute_hidden;
+			   unsigned int skip) attribute_hidden;
 
 /* The dynamic linker calls this function before and having changing
    any shared object mappings.  The `r_state' member of `struct r_debug'
-- 
2.33.1

[PATCH 2/2] elf: Always call destructors in reverse constructor order

[Florian Weimer]

The current implementation of dlclose (and process exit) re-sorts
the link maps before calling ELF destructors.  Destructor order
is not the reverse of the constructor order as a result: The second
sort took relocation dependencies into account until recently, and
other differences can result from ambiguous inputs, such as cycles.
(After the changes in this commit, there is still a required
difference due to dlopen/dlclose ordering by the application,
but the previous discrepancies went beyond that.)

A new global (namespace-spanning) list of link maps,
_dl_init_called_list, is updated right before ELF constructors are
called from _dl_init.

In dl_close_worker, the maps variable, an on-stack variable length
array, is eliminated.  (VLAs are problematic, and dlclose should not
call malloc because it cannot readily deal with malloc failure.)
Marking still-used objects uses the namespace list directly, with
next and next_idx replacing the done_index variable.

After marking, _dl_init_called_list is used to call the destructors
of now-unused maps in reverse destructor order.  These destructors
can call dlopen.  Previously, new objects do not have l_map_used set.
This had to change: There is no copy of the link map list anymore,
so processing would cover newly opened (and unmarked) mappings,
unloading them.  Now, _dl_init (indirectly) sets l_map_used, to.
(dlclose is handled by the existing reentrancy guard.)

After _dl_init_called_list traversal, two more loops follow.  The
processing order changes to the original link map order in the
namespace.  Previously, dependency order was used.  The difference
should not matter because relocation dependencies could already
reorder link maps in the old code.

The changes to _dl_fini remove the sorting step and replace it with
a traversal of the _dl_init_called_list.  The l_direct_opencount
decrement outside the loader lock is removed because it appears
incorrect: the counter manipulation could race with other dynamic
loader operations.

tst-bz15311 is updated: the output now shows the reversed destructor
order compared to construction.
---
 elf/dl-close.c             | 130 +++++++++++++---------
 elf/dl-fini.c              | 216 ++++++++++++++-----------------------
 elf/dl-init.c              |  14 +++
 elf/dso-sort-tests-1.def   |   2 +-
 include/link.h             |   4 +
 sysdeps/generic/ldsodefs.h |   4 +
 6 files changed, 182 insertions(+), 188 deletions(-)

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;
-- 
2.33.1

Re: [PATCH 0/2] Predictable ELF destructor ordering

[Stafford Horne]

On Tue, Dec 14, 2021 at 10:01:57PM +0100, Florian Weimer via Libc-alpha wrote:
> These patches remove the dependency sorting from dlclose and process
> shutdown, so that destructor order is the reverse of constructor order
> in more cases (always if the process does not call dlclose).
> 
> Tested on i686-linux-gnu and x86_64-linux-gnu.
> 
> I would like to include this in glibc 2.35 if possible, among the other
> dependency sorting changes.
> 
> I believe this fixes bugs 15311 and 15903.
> 
> Florian Weimer (2):
>   elf: Do not rely on relocation dependencies for destructor sorting
>   elf: Always call destructors in reverse constructor order
> 
>  elf/dl-close.c             | 130 +++++++++++++---------
>  elf/dl-deps.c              |   3 +-
>  elf/dl-fini.c              | 216 ++++++++++++++-----------------------
>  elf/dl-init.c              |  14 +++
>  elf/dl-sort-maps.c         | 105 ++----------------
>  elf/dso-sort-tests-1.def   |   6 +-
>  include/link.h             |   4 +
>  sysdeps/generic/ldsodefs.h |   6 +-
>  8 files changed, 194 insertions(+), 290 deletions(-)

Hi Florian,

This does seem to fix an issue for me in the OpenRISC port.  Discussed [1] in
the OpenRISC port thread.  It fixes:

  elf/tst-bz15311

Failure details in tst-bz15311.out (fixed with these patches) [2].

However this also seems to break:

  elf/tst-glibc-hwcaps-prepend-cache

I am not able to get much detail from the failure other than a SIGDEGV in fork,
I then bisected it to these patches I have on my branch to fix elf/tst-bz15311.
Let me know if I can help.

-Stafford

[1] https://sourceware.org/pipermail/libc-alpha/2021-December/134184.html
[2] https://gist.github.com/5a5dacaeef1eac1f2f5d89701d14c0ad

Re: [PATCH 0/2] Predictable ELF destructor ordering

[Florian Weimer]

* Stafford Horne:

> On Tue, Dec 14, 2021 at 10:01:57PM +0100, Florian Weimer via Libc-alpha wrote:
>> These patches remove the dependency sorting from dlclose and process
>> shutdown, so that destructor order is the reverse of constructor order
>> in more cases (always if the process does not call dlclose).
>> 
>> Tested on i686-linux-gnu and x86_64-linux-gnu.
>> 
>> I would like to include this in glibc 2.35 if possible, among the other
>> dependency sorting changes.
>> 
>> I believe this fixes bugs 15311 and 15903.
>> 
>> Florian Weimer (2):
>>   elf: Do not rely on relocation dependencies for destructor sorting
>>   elf: Always call destructors in reverse constructor order
>> 
>>  elf/dl-close.c             | 130 +++++++++++++---------
>>  elf/dl-deps.c              |   3 +-
>>  elf/dl-fini.c              | 216 ++++++++++++++-----------------------
>>  elf/dl-init.c              |  14 +++
>>  elf/dl-sort-maps.c         | 105 ++----------------
>>  elf/dso-sort-tests-1.def   |   6 +-
>>  include/link.h             |   4 +
>>  sysdeps/generic/ldsodefs.h |   6 +-
>>  8 files changed, 194 insertions(+), 290 deletions(-)
>
> Hi Florian,
>
> This does seem to fix an issue for me in the OpenRISC port.  Discussed [1] in
> the OpenRISC port thread.  It fixes:
>
>   elf/tst-bz15311
>
> Failure details in tst-bz15311.out (fixed with these patches) [2].
>
> However this also seems to break:
>
>   elf/tst-glibc-hwcaps-prepend-cache
>
> I am not able to get much detail from the failure other than a SIGDEGV
> in fork, I then bisected it to these patches I have on my branch to
> fix elf/tst-bz15311.  Let me know if I can help.

What are the DT_NEEDED entries on the shared objects, and the run-time
relocations?  I suspect you must have some unexpected dependency which
confuses the old sorting code.

The elf/tst-glibc-hwcaps-prepend-cache failure is very suspicious, it
really should not happen.  Would you be able to debug it further?

Thanks,
Florian

Re: [PATCH 0/2] Predictable ELF destructor ordering

[Stafford Horne]

On Mon, Dec 20, 2021, 10:20 PM Florian Weimer <fweimer@redhat.com> wrote:

> * Stafford Horne:
>
> > On Tue, Dec 14, 2021 at 10:01:57PM +0100, Florian Weimer via Libc-alpha
> wrote:
> >> These patches remove the dependency sorting from dlclose and process
> >> shutdown, so that destructor order is the reverse of constructor order
> >> in more cases (always if the process does not call dlclose).
> >>
> >> Tested on i686-linux-gnu and x86_64-linux-gnu.
> >>
> >> I would like to include this in glibc 2.35 if possible, among the other
> >> dependency sorting changes.
> >>
> >> I believe this fixes bugs 15311 and 15903.
> >>
> >> Florian Weimer (2):
> >>   elf: Do not rely on relocation dependencies for destructor sorting
> >>   elf: Always call destructors in reverse constructor order
> >>
> >>  elf/dl-close.c             | 130 +++++++++++++---------
> >>  elf/dl-deps.c              |   3 +-
> >>  elf/dl-fini.c              | 216 ++++++++++++++-----------------------
> >>  elf/dl-init.c              |  14 +++
> >>  elf/dl-sort-maps.c         | 105 ++----------------
> >>  elf/dso-sort-tests-1.def   |   6 +-
> >>  include/link.h             |   4 +
> >>  sysdeps/generic/ldsodefs.h |   6 +-
> >>  8 files changed, 194 insertions(+), 290 deletions(-)
> >
> > Hi Florian,
> >
> > This does seem to fix an issue for me in the OpenRISC port.  Discussed
> [1] in
> > the OpenRISC port thread.  It fixes:
> >
> >   elf/tst-bz15311
> >
> > Failure details in tst-bz15311.out (fixed with these patches) [2].
> >
> > However this also seems to break:
> >
> >   elf/tst-glibc-hwcaps-prepend-cache
> >
> > I am not able to get much detail from the failure other than a SIGDEGV
> > in fork, I then bisected it to these patches I have on my branch to
> > fix elf/tst-bz15311.  Let me know if I can help.
>
> What are the DT_NEEDED entries on the shared objects, and the run-time
> relocations?  I suspect you must have some unexpected dependency which
> confuses the old sorting code.
>
> The elf/tst-glibc-hwcaps-prepend-cache failure is very suspicious, it
> really should not happen.  Would you be able to debug it further?
>


Hi Florian

After further debugging I found i cannot reproduce this after a full
toolchain rebuild.

I will leave this to a bad environment setup on my side. Sorry for the noise

-Stafford