Re: [PATCH v4 2/2] BZ #17645, fix slow DSO sorting behavior in dynamic loader -- Algorithm changes

[Florian Weimer <fweimer@redhat.com>]

Chung-Lin,

I have not reviewed the actual sorting algorithm change yet.  I will do
so in a follow-up.

This change should be quite safe as posted, given that the core
behavioral change is hidden behind a tunable setting, and the default is
the old behavior.  But ideally, I think the new behavior should be the
default, so that people can actually experience it.  On the other, if
the old behavior is preserved, we might still include this change in
glibc 2.33.

For glibc 2.34, I plan to work on system-wide tunable settings, without
environment variables.  So it would be possible to flip the default
there, while still providing a way to system administrators to restore
the old behavior.

* Chung-Lin Tang:

> diff --git a/elf/dl-close.c b/elf/dl-close.c
> index c51becd06b..84d25a29d0 100644
> --- a/elf/dl-close.c
> +++ b/elf/dl-close.c
> @@ -164,8 +164,6 @@ _dl_close_worker (struct link_map *map, bool force)
>  
>    bool any_tls = false;
>    const unsigned int nloaded = ns->_ns_nloaded;
> -  char used[nloaded];
> -  char done[nloaded];

This change (moving those arrays into struct link_map) can go in
separately if you want to split it out.

There seems to be some further cleanup potential regarding the use of
IDX_STILL_USED and l_map_done.

> @@ -247,9 +242,9 @@ _dl_close_worker (struct link_map *map, bool force)
>  	      {
>  		assert (jmap->l_idx >= 0 && jmap->l_idx < nloaded);
>  
> -		if (!used[jmap->l_idx])
> +		if (!jmap->l_map_used)
>  		  {
> -		    used[jmap->l_idx] = 1;
> +		    jmap->l_map_used = 1;
>  		    if (jmap->l_idx - 1 < done_index)
>  		      done_index = jmap->l_idx - 1;
>  		  }

The above comes under:

      /* And the same for relocation dependencies.  */
      if (l->l_reldeps != NULL)
        for (unsigned int j = 0; j < l->l_reldeps->act; ++j)

I have a conceptual concern here: I think it is a bug to let relocation
dependencies affect finalizer order.  In order to cut down the sorting
algorithm variations, I would like to suggest not to take relocation
dependencies into account for the new sorting mode.

This way, there will be only one user-visible transition: from the old
sorting to the new sorting.  That's going to be much easier to test.

> diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
> index d21770267a..5aa96f4cc1 100644
> --- a/elf/dl-sort-maps.c
> +++ b/elf/dl-sort-maps.c
> @@ -16,16 +16,24 @@
>     License along with the GNU C Library; if not, see
>     <https://www.gnu.org/licenses/>.  */
>  
> +#include <assert.h>
>  #include <ldsodefs.h>
> +#include <elf/dl-tunables.h>
>  
> +/* Note: this is the older, "original" sorting algorithm, being used as
> +   default up to 2.32.
>  
> -/* Sort array MAPS according to dependencies of the contained objects.
> -   Array USED, if non-NULL, is permutated along MAPS.  If FOR_FINI this is
> -   called for finishing an object.  */
> -void
> -_dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
> -	       bool for_fini)
> +   Sort array MAPS according to dependencies of the contained objects.
> +   If FOR_FINI is true, this is called for finishing an object.  */
> +static void
> +_dl_sort_maps_original (struct link_map **maps, unsigned int nmaps,
> +			unsigned int skip, bool for_fini)
>  {
> +  /* Allows caller to do the common optimization of skipping the first map,
> +     usually the main binary.  */
> +  maps += skip;
> +  nmaps -= skip;

As I mentioned in the test case review, I do not think this is purely an
optimization.  If the main executable has a soname, it participates in
the dependency sort like a shared object, so its constructor might not
come last.  I don't think this is was what programmers expect.

> diff --git a/include/link.h b/include/link.h
> index 4af16cb596..f2dbcbaf77 100644
> --- a/include/link.h
> +++ b/include/link.h
> @@ -181,6 +181,10 @@ struct link_map
>      unsigned int l_init_called:1; /* Nonzero if DT_INIT function called.  */
>      unsigned int l_global:1;	/* Nonzero if object in _dl_global_scope.  */
>      unsigned int l_reserved:2;	/* Reserved for internal use.  */
> +    unsigned int l_visited:1;   /* Used internally for map dependency
> +				   graph traversal.  */
> +    unsigned int l_map_used:1;  /* These two bits are used during traversal */
> +    unsigned int l_map_done:1;  /* of maps in _dl_close_worker(). */
>      unsigned int l_phdr_allocated:1; /* Nonzero if the data structure pointed
>  					to by `l_phdr' is allocated.  */
>      unsigned int l_soname_added:1; /* Nonzero if the SONAME is for sure in

Some style nits: No () after function name, ”.  */” at the end of a
comment.

Thanks,
Florian
-- 
Red Hat GmbH, https://de.redhat.com/ , Registered seat: Grasbrunn,
Commercial register: Amtsgericht Muenchen, HRB 153243,
Managing Directors: Charles Cachera, Brian Klemm, Laurie Krebs, Michael O'Neill