diff mbox series

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

Message ID 89f15608c1b4fd46715357fd108375f1e796e6f4.1639515239.git.fweimer@redhat.com
State Superseded
Headers show
Series Predictable ELF destructor ordering | expand

Checks

Context Check Description
dj/TryBot-apply_patch success Patch applied to master at the time it was sent

Commit Message

Florian Weimer Dec. 14, 2021, 9:02 p.m. UTC
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 mbox series

Patch

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'