Re: [PATCH] elf: Sort only uninitialized objects in _dl_map_object_deps()

[Carlos O'Donell <carlos@redhat.com>]

On 7/25/20 6:52 AM, Xiaoming Ni wrote:
> TIS ELF Version 1.2
> Initialization and Termination Functions:
> 	1. Before the initialization code for any object A is called, the
> 	   initialization code for any other objects that object A depends
> 	   on are called.
> 	2. The order in which the dynamic linker calls termination functions
> 	   is the exact reverse order of their corresponding initialization
> 	   functions.
> 	3. The dynamic linker ensures that it will not execute any
> 	   initialization or termination functions more than once.
> 
> According to 1 and 2: _dl_sort_maps() is used for sorting when dlopen/dlclose.
> According to 3: At dlopen, only the uninitialized objects need to be sorted.

Thank you for posting this. It will take a while to review this, and we're
currently frozen for the release on August 3rd.

> Construct 200 dynamic libraries that depend on each other cyclically.

Once you have a cyclic dependency the order is undefined.

My opinion is that the dynamic linker should break the cycle in a deterministic
fashion.

What do you think?

> Run the dlopen() for each dynamic library.
> Before the patch is installed, it takes 214 seconds.
> After patching, it takes 37 seconds.

Is it still correct?

Do you have a test case you can add?
 
> Signed-off-by: Xiaoming Ni <nixiaoming@huawei.com>

Reviewing this will have to wait until after the release, but this patch is
interesting.

Have you looked at Chung-Ling Tang's most recent work in this area?

https://patchwork.sourceware.org/project/glibc/patch/1427b370-7400-afd0-16e8-55c1072db20e@mentor.com/
https://patchwork.sourceware.org/project/glibc/patch/5de3ab61-3dca-b400-15c6-92ff5ae80877@mentor.com/

Could you use Chung-Ling's test case constructor to write a test case?

> ---
>  elf/dl-deps.c | 40 +++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 39 insertions(+), 1 deletion(-)
> 
> diff --git a/elf/dl-deps.c b/elf/dl-deps.c
> index b5a43232a7..5df1e32156 100644
> --- a/elf/dl-deps.c
> +++ b/elf/dl-deps.c
> @@ -152,6 +152,43 @@ preload (struct list *known, unsigned int *nlist, struct link_map *map)
>    map->l_reserved = 1;
>  }
>  
> +/* TIS  ELF Version 1.2
> + * Initialization and Termination Functions:
> + * 1. Before the initialization code for any object A is called, the
> + *  initialization code for any other objects that object A depends on are called.
> + * 2. The order in which the dynamic linker calls termination functions is the
> + *  exact reverse order of their corresponding initialization functions.
> + * 3. The dynamic linker ensures that it will not execute any initialization
> + *  or termination functions more than once.
> + *
> + * According to 1 and 2, _dl_sort_maps() is used for sorting when dlopen/dlclose.
> + * According to 3, we only need to sort the uninitialized objects.
> + */
> +static void
> +_dl_sort_uninit_maps (struct link_map **maps, unsigned int nmaps)
> +{
> +  unsigned int s = 0;
> +  unsigned int e = nmaps - 1;
> +  struct link_map *tmp;
> +
> +  while (s < e)
> +    {
> +      while ((e > 0) && maps[e]->l_init_called)
> +        e--;
> +      while ((s < nmaps) && maps[s]->l_init_called == 0)
> +        s++;
> +      if (s >= e)
> +        break;
> +      tmp = maps[e];
> +      maps[e] = maps[s];
> +      maps[s] = tmp;
> +      s++;
> +      e--;
> +    }
> +
> +  _dl_sort_maps (maps, s, NULL, false);
> +}
> +
>  void
>  _dl_map_object_deps (struct link_map *map,
>  		     struct link_map **preloads, unsigned int npreloads,
> @@ -611,7 +648,8 @@ Filters not supported with LD_TRACE_PRELINKING"));
>      memcpy (l_initfini, map->l_searchlist.r_list,
>  	    nlist * sizeof (struct link_map *));
>  
> -  _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false);
> +  if (map->l_init_called == 0)
> +    _dl_sort_uninit_maps (&l_initfini[1], nlist - 1);
>  
>    /* Terminate the list of dependencies.  */
>    l_initfini[nlist] = NULL;
> 


-- 
Cheers,
Carlos.