[v2,1/3] elf: Do not rely on relocation dependencies for destructor sorting

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.
---
v2: Rebase.

 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(-)

On 03/02/2022 12:17, Florian Weimer via Libc-alpha wrote:
> 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.

I am seeing a regression with this patch:

$ make test t=elf/order2-cmp
[...]
FAIL: elf/order2-cmp
original exit status 1
/home/azanella/Projects/glibc/build/x86_64-linux-gnu/elf/order2.out - differ: byte 2, line 1
$ cat elf/order2.out 
13245

It seems to be the expected out, since:

$ ldd elf/order2mod1.so
        linux-vdso.so.1 (0x00007ffccdb88000)
        [...]elf/order2mod4.so (0x00007f415e4bd000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f415e278000)
        [...]order2mod3.so (0x00007f415e273000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f415e4c9000)
$ ldd elf/order2mod4.so
        linux-vdso.so.1 (0x00007ffdc75fe000)
        [...]/elf/order2mod3.so (0x00007f2870f30000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f2870ceb000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f2870f3c000)

The full tree is:
                             destructor output
  elf/order2mod1.so          '1'
  \_ elf/order2mod4.so       '3'
     \_ elf/order2mod3.so    '4'
  \_ elf/order2mod3.so       '4'

  elf/order2mod2.so          '2'
  \_ elf/order2mod3.so       '4'
  
So the fini order should be processed as:

  1. elf/order2mod1.so
  2. elf/order2mod4.so
  3. elf/order2mod2.so
  4. elf/order2mod3.so
  5. application

Since now the new algorithm uses a depth breadth search

I am not sure why you haven't see this failure.

> ---
> v2: Rebase.
> 
>  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 bcd6e206e9..a161b95d00 100644
> --- a/elf/dl-close.c
> +++ b/elf/dl-close.c
> @@ -258,7 +258,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.  */
>    bool unload_any = false;
> diff --git a/elf/dl-deps.c b/elf/dl-deps.c
> index c8bab5cad5..ef19e7c390 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 030b1fcbcd..f841868cdb 100644
> --- a/elf/dl-fini.c
> +++ b/elf/dl-fini.c
> @@ -96,7 +96,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 9e9d53ec47..95938c4a52 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 2ebe7901c0..4d679510e3 100644
> --- a/sysdeps/generic/ldsodefs.h
> +++ b/sysdeps/generic/ldsodefs.h
> @@ -1123,7 +1123,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'