Re: [PATCH v3 2/2] elf: Always call destructors in reverse constructor order (bug 30785)

[DJ Delorie <dj@redhat.com>]

I had a question about _dl_call_fini() but the code is technically
correct so LGTM.

Reviewed-by: DJ Delorie <dj@redhat.com>

Florian Weimer via Libc-alpha <libc-alpha@sourceware.org> writes:
> diff --git a/include/link.h b/include/link.h
> index 1d74feb2bd..69bda3ed17 100644
> --- a/include/link.h
> +++ b/include/link.h
> @@ -278,6 +278,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
>        {

So the new technique is to keep a linked list of DSOs built as they're
constructed, so we can traverse it for destructors.  Ok.

> diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
> index e8b7359b04..9ea9389a39 100644
> --- a/sysdeps/generic/ldsodefs.h
> +++ b/sysdeps/generic/ldsodefs.h
> @@ -1037,6 +1037,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;

Ok.

> diff --git a/elf/dl-close.c b/elf/dl-close.c
> index b887a44888..ea62d0e601 100644
> --- a/elf/dl-close.c
> +++ b/elf/dl-close.c
> @@ -138,30 +138,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);

We used to build a sortable list of DSOs but we don't need that any
more, so don't build it.  Ok.

> -  /* 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; )

Iterate the linked list instead of the array, Ok.

>      {
> -      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.  */

Ok.

>        if (l->l_map_done)
> -	/* Already handled.  */
> -	continue;
> +	{
> +	  /* Already handled.  */
> +	  l = next;
> +	  continue;
> +	}

Ok.

>  	     acquire is sufficient and correct.  */
>  	  && atomic_load_acquire (&l->l_tls_dtor_count) == 0
>  	  && !l->l_map_used)
> -	continue;
> +	{
> +	  l = next;
> +	  continue;
> +	}

Ok.

>  			 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;
> +			}

Ok.

>  		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;
> +		      }

Ok.

> -  /* 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);
> +      l = next;
> +    }

Ok.

> -  /* Call all termination functions at once.  */
> +  /* Call the destructors in reverse constructor order, and remove the
> +     closed link maps from the list.  */

Ok.

> -  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)
> +  for (struct link_map **init_called_head = &_dl_init_called_list;
> +       *init_called_head != NULL; )
>      {

Ok.

> -      struct link_map *imap = maps[i];
> +      struct link_map *imap = *init_called_head;

Ok.

> -      /* All elements must be in the same namespace.  */
> -      assert (imap->l_ns == nsid);
> -
> -      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

Ok.

>  	{
>  	  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)
> +	  /* _dl_init_called_list is updated at the same time as
> +	     l_init_called.  */
> +	  assert (imap->l_init_called);
> +
> +	  if (imap->l_info[DT_FINI_ARRAY] != NULL
> +	      || imap->l_info[DT_FINI] != NULL)
>  	    _dl_catch_exception (NULL, _dl_call_fini, imap);

Ok.

>  #ifdef SHARED
>  	  /* Auditing checkpoint: we remove an object.  */
>  	  _dl_audit_objclose (imap);
>  #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)
> +	{

We split the loop into two, and restart our iterations.  Ok.

>  	  /* Remember where the first dynamically loaded object is.  */
> -	  if (i < first_loaded)
> -	    first_loaded = i;
> +	  if (first_loaded == NULL)
> +	      first_loaded = imap;

Ok.

>  	  /* Remember where the first dynamically loaded object is.  */
> -	  if (i < first_loaded)
> -	    first_loaded = i;
> +	  if (first_loaded == NULL)
> +	      first_loaded = imap;

Ok.

>    /* 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

Ok.

>  	  if (imap == GL(dl_initfirst))
>  	    GL(dl_initfirst) = NULL;
>  
> +	  struct link_map *next = imap->l_next;
>  	  free (imap);
> +	  imap = next;

Ok.

> diff --git a/elf/dl-fini.c b/elf/dl-fini.c
> index 9acb64f47c..90abee6ada 100644
> --- a/elf/dl-fini.c
> +++ b/elf/dl-fini.c
> @@ -24,116 +24,90 @@
>  void
>  _dl_fini (void)
>  (

This one is almost completely changed, so I'll review the resulting code
instead of the patch...

>   /* 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));

ok.

>   /* Ignore objects which are opened during shutdown.  */
>   struct link_map *local_init_called_list = _dl_init_called_list;

start at the head, which is the last DSO constructed.

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

Mark/lock everything

>   /* 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));

Ok.  We can call dlopen/dlclose after this without deadlocking, but it
won't add to the list we're processing.

>   /* Perform two passes: One for non-audit modules, one for audit
>      modules.  This way, audit modules receive unload notifications
>      for non-audit objects, and the destructors for audit modules
>      still run.  */
> #ifdef SHARED
>   int last_pass = GLRO(dl_naudit) > 0;
>   Lmid_t last_ns = -1;
>   for (int do_audit = 0; do_audit <= last_pass; ++do_audit)
> #endif

Loop for shared, don't loop if not.  Ok.

>     for (struct link_map *l = local_init_called_list; l != NULL;
> 	 l = l->l_init_called_next)
>       {

Loop over DSOs.  Ok.

> #ifdef SHARED
> 	if (GL(dl_ns)[l->l_ns]._ns_loaded->l_auditing != do_audit)
> 	  continue;
> 
> 	/* Avoid back-to-back calls of _dl_audit_activity_nsid for the
> 	   same namespace.  */
> 	if (last_ns != l->l_ns)
> 	  {
> 	    if (last_ns >= 0)
> 	      _dl_audit_activity_nsid (last_ns, LA_ACT_CONSISTENT);
> 	    _dl_audit_activity_nsid (l->l_ns, LA_ACT_DELETE);
> 	    last_ns = l->l_ns;
> 	  }
> #endif

Skip audit modules on the first pass, and skip non-audit modules on the
second pass.  Ok.

> 	/* 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);
> 	  }

Similar to _dl_call_fini(), but... doesn't set map->l_init_called ?  Ok,
but seems repetitive.

> #ifdef SHARED
> 	/* Auditing checkpoint: another object closed.  */
> 	_dl_audit_objclose (l);
> #endif
>       }

Ok.

> #ifdef SHARED
>   if (last_ns >= 0)
>     _dl_audit_activity_nsid (last_ns, LA_ACT_CONSISTENT);

Ok.

> diff --git a/elf/dl-init.c b/elf/dl-init.c
> index fefd471851..98d77d80a5 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;

Ok.

> @@ -42,6 +43,21 @@ 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.  _dl_fini uses this list for audit callbacks, so
> +     register objects on the list even if they do not have a
> +     constructor.  */
> +  l->l_init_called_next = _dl_init_called_list;
> +  _dl_init_called_list = l;
> +

Ok.  Single-linked list, LIFO.

> diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def
> index 4bf9052db1..61dc54f8ae 100644
> --- a/elf/dso-sort-tests-1.def
> +++ b/elf/dso-sort-tests-1.def
> @@ -53,21 +53,14 @@ tst-dso-ordering10: {}->a->b->c;soname({})=c
>  output: b>a>{}<a<b
>  
>  # Complex example from Bugzilla #15311, under-linked and with circular
> -# 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.
> +# relocation(dynamic) dependencies. For both sorting algorithms, the
> +# destruction order is the reverse of the construction order, and
> +# relocation dependencies are not taken into account.
>  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[<g<f<e<a<b<c<d];}

Ok.


>  # Test that even in the presence of dependency loops involving dlopen'ed
>  # object, that object is initialized last (and not unloaded prematurely).
> -# Final destructor order is indeterminate due to the cycle.
> +# Final destructor order is the opposite of constructor order.
>  tst-bz28937: {+a;+b;-b;+c;%c};a->a1;a->a2;a2->a;b->b1;c->a1;c=>a1
> -output(glibc.rtld.dynamic_sort=1): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a<a2<c<a1
> -output(glibc.rtld.dynamic_sort=2): {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<a2<a<c<a1
> +output: {+a[a2>a1>a>];+b[b1>b>];-b[<b<b1];+c[c>];%c(a1());}<c<a<a1<a2

Ok.

> diff --git a/elf/tst-audit23.c b/elf/tst-audit23.c
> index bb7d66c385..503699c36a 100644
> --- a/elf/tst-audit23.c
> +++ b/elf/tst-audit23.c
> @@ -98,6 +98,8 @@ do_test (int argc, char *argv[])
>      char *lname;
>      uintptr_t laddr;
>      Lmid_t lmid;
> +    uintptr_t cookie;
> +    uintptr_t namespace;

Ok.

> @@ -117,6 +119,9 @@ do_test (int argc, char *argv[])
>    size_t buffer_length = 0;
>    while (xgetline (&buffer, &buffer_length, out))
>      {
> +      *strchrnul (buffer, '\n') = '\0';
> +      printf ("info: subprocess output: %s\n", buffer);
> +

Ok.

> @@ -125,29 +130,26 @@ do_test (int argc, char *argv[])
>  			  &cookie);
>  	  TEST_COMPARE (r, 2);
>  
> -	  /* The cookie identifies the object at the head of the link map,
> -	     so we only add a new namespace if it changes from the previous
> -	     one.  This works since dlmopen is the last in the test body.  */
> -	  if (cookie != last_act_cookie && last_act_cookie != -1)
> -	    TEST_COMPARE (last_act, LA_ACT_CONSISTENT);
> -
>  	  if (this_act == LA_ACT_ADD && acts[nacts] != cookie)
>  	    {
> +	      /* The cookie identifies the object at the head of the
> +		 link map, so we only add a new namespace if it
> +		 changes from the previous one.  This works since
> +		 dlmopen is the last in the test body.  */
> +	      if (cookie != last_act_cookie && last_act_cookie != -1)
> +		TEST_COMPARE (last_act, LA_ACT_CONSISTENT);
> +
>  	      acts[nacts++] = cookie;
>  	      last_act_cookie = cookie;

Ok.


> -	  /* The LA_ACT_DELETE is called in the reverse order of LA_ACT_ADD
> -	     at program termination (if the tests adds a dlclose or a library
> -	     with extra dependencies this will need to be adapted).  */
> +	  /* LA_ACT_DELETE is called multiple times for each
> +	     namespace, depending on destruction order.  */

Ok.

>  	  else if (this_act == LA_ACT_DELETE)
> -	    {
> -	      last_act_cookie = acts[--nacts];
> -	      TEST_COMPARE (acts[nacts], cookie);
> -	      acts[nacts] = 0;
> -	    }
> +	    last_act_cookie = cookie;

Ok.

>  	  else if (this_act == LA_ACT_CONSISTENT)
>  	    {
>  	      TEST_COMPARE (cookie, last_act_cookie);
> +	      last_act_cookie = -1;

Ok.

> @@ -179,6 +181,8 @@ do_test (int argc, char *argv[])
>  	  objs[nobjs].lname = lname;
>  	  objs[nobjs].laddr = laddr;
>  	  objs[nobjs].lmid = lmid;
> +	  objs[nobjs].cookie = cookie;
> +	  objs[nobjs].namespace = last_act_cookie;
>  	  objs[nobjs].closed = false;
>  	  nobjs++;
>  
> @@ -201,6 +205,12 @@ do_test (int argc, char *argv[])
>  	      if (strcmp (lname, objs[i].lname) == 0 && lmid == objs[i].lmid)
>  		{
>  		  TEST_COMPARE (objs[i].closed, false);
> +		  TEST_COMPARE (objs[i].cookie, cookie);
> +		  if (objs[i].namespace == -1)
> +		    /* No LA_ACT_ADD before the first la_objopen call.  */
> +		    TEST_COMPARE (acts[0], last_act_cookie);
> +		  else
> +		    TEST_COMPARE (objs[i].namespace, last_act_cookie);
>  		  objs[i].closed = true;
>  		  break;
match closes with opens, ok.

> @@ -209,11 +219,7 @@ do_test (int argc, char *argv[])
>  	  /* la_objclose should be called after la_activity(LA_ACT_DELETE) for
>  	     the closed object's namespace.  */
>  	  TEST_COMPARE (last_act, LA_ACT_DELETE);
> -	  if (!seen_first_objclose)
> -	    {
> -	      TEST_COMPARE (last_act_cookie, cookie);
> -	      seen_first_objclose = true;
> -	    }
> +	  seen_first_objclose = true;
>  	}
>      }
>  

Ok.