Consolidate link map sorting

Combine the four places where link maps are sorted into a single function.
This also moves the logic to skip the first map (representing the main
binary) to the callers.

Tested on x86-64 and aarch64.

	* elf/Makefile (dl-routines): Add dl-sort-maps.
	* elf/dl-sort-maps.c: New file.
	* sysdeps/generic/ldsodefs.h (_dl_sort_fini): Don't declare.
	(_dl_sort_maps): Declare.
	* elf/dl-fini.c (_dl_sort_fini): Remove.
	(_dl_fini): Use _dl_sort_maps instead of _dl_sort_fini.
	* elf/dl-close.c (_dl_close_worker): Likewise.
	* elf/dl-deps.c (_dl_map_object_deps): Use _dl_sort_maps instead of
	open-coding it.
	* elf/dl-open.c (dl_open_worker): Likewise.
---
 elf/Makefile               |   2 +-
 elf/dl-close.c             |   6 ++-
 elf/dl-deps.c              |  59 ++--------------------
 elf/dl-fini.c              | 105 ++-------------------------------------
 elf/dl-open.c              |  57 ++--------------------
 elf/dl-sort-maps.c         | 119 +++++++++++++++++++++++++++++++++++++++++++++
 sysdeps/generic/ldsodefs.h |   4 +-
 7 files changed, 137 insertions(+), 215 deletions(-)
 create mode 100644 elf/dl-sort-maps.c

On 11/09/2017 10:45 AM, Andreas Schwab wrote:
> +      /* Do not handle ld.so in secondary namespaces and object which
> +	 are not removed.  */
> +      if (thisp != thisp->l_real || thisp->l_idx == -1)
> +	goto skip;

Is this really safe to include in the processing when called from 
_dl_map_objects?

Then the comment is wrong, it should say:

“Do not handle ld.so in secondary namespaces and objects which are being 
removed.”

I assume thisp->l_idx == -1 means the object is undergoing removal, and 
_dl_new_object initializes l_idx to zero by allocating struct link_map 
using calloc.

Thanks,
Florian

On Nov 11 2017, Florian Weimer <fweimer@redhat.com> wrote:

> On 11/09/2017 10:45 AM, Andreas Schwab wrote:
>> +      /* Do not handle ld.so in secondary namespaces and object which
>> +	 are not removed.  */
>> +      if (thisp != thisp->l_real || thisp->l_idx == -1)
>> +	goto skip;
>
> Is this really safe to include in the processing when called from
> _dl_map_objects?

Good point, I missed that part when comparing the implementations.
Here's an updated patch.

Andreas.

diff --git a/elf/Makefile b/elf/Makefile
index a31fb72498..d49fd4673d 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -32,7 +32,7 @@ dl-routines	= $(addprefix dl-,load lookup object reloc deps hwcaps \
 				  runtime init fini debug misc \
 				  version profile tls origin scope \
 				  execstack caller open close trampoline \
-				  exception)
+				  exception sort-maps)
 ifeq (yes,$(use-ldconfig))
 dl-routines += dl-cache
 endif
diff --git a/elf/dl-close.c b/elf/dl-close.c
index 2b46b7cf8b..3dd75c8725 100644
--- a/elf/dl-close.c
+++ b/elf/dl-close.c
@@ -241,8 +241,10 @@ _dl_close_worker (struct link_map *map, bool force)
 	  }
     }
 
-  /* Sort the entries.  */
-  _dl_sort_fini (maps, nloaded, used, nsid);
+  /* 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 + (nsid == LM_ID_BASE), nloaded - (nsid == LM_ID_BASE),
+		 used + (nsid == LM_ID_BASE), true);
 
   /* Call all termination functions at once.  */
 #ifdef SHARED
diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index 35cad364b7..622331e6e2 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -585,62 +585,9 @@ Filters not supported with LD_TRACE_PRELINKING"));
      itself will always be initialize last.  */
   memcpy (l_initfini, map->l_searchlist.r_list,
 	  nlist * sizeof (struct link_map *));
-  if (__glibc_likely (nlist > 1))
-    {
-      /* We can skip looking for the binary itself which is at the front
-	 of the search list.  */
-      i = 1;
-      uint16_t seen[nlist];
-      memset (seen, 0, nlist * sizeof (seen[0]));
-      while (1)
-	{
-	  /* Keep track of which object we looked at this round.  */
-	  ++seen[i];
-	  struct link_map *thisp = l_initfini[i];
-
-	  /* 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.  */
-	  unsigned int k = nlist - 1;
-	  while (k > i)
-	    {
-	      struct link_map **runp = l_initfini[k]->l_initfini;
-	      if (runp != NULL)
-		/* Look through the dependencies of the object.  */
-		while (*runp != NULL)
-		  if (__glibc_unlikely (*runp++ == thisp))
-		    {
-		      /* Move the current object to the back past the last
-			 object with it as the dependency.  */
-		      memmove (&l_initfini[i], &l_initfini[i + 1],
-			       (k - i) * sizeof (l_initfini[0]));
-		      l_initfini[k] = thisp;
-
-		      if (seen[i + 1] > nlist - i)
-			{
-			  ++i;
-			  goto next_clear;
-			}
-
-		      uint16_t this_seen = seen[i];
-		      memmove (&seen[i], &seen[i + 1],
-			       (k - i) * sizeof (seen[0]));
-		      seen[k] = this_seen;
-
-		      goto next;
-		    }
-
-	      --k;
-	    }
-
-	  if (++i == nlist)
-	    break;
-	next_clear:
-	  memset (&seen[i], 0, (nlist - i) * sizeof (seen[0]));
-
-	next:;
-	}
-    }
+  /* We can skip looking for the binary itself which is at the front of
+     the search list.  */
+  _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false);
 
   /* Terminate the list of dependencies.  */
   l_initfini[nlist] = NULL;
diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index 71c06fc68b..8421c4fab8 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
@@ -25,104 +25,6 @@
 typedef void (*fini_t) (void);
 
 
-void
-_dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns)
-{
-  /* A list of one element need not be sorted.  */
-  if (nmaps == 1)
-    return;
-
-  /* We can skip looking for the binary itself which is at the front
-     of the search list for the main namespace.  */
-  unsigned int i = ns == LM_ID_BASE;
-  uint16_t seen[nmaps];
-  memset (seen, 0, nmaps * sizeof (seen[0]));
-  while (1)
-    {
-      /* Keep track of which object we looked at this round.  */
-      ++seen[i];
-      struct link_map *thisp = maps[i];
-
-      /* Do not handle ld.so in secondary namespaces and object 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.  */
-      unsigned int k = nmaps - 1;
-      while (k > i)
-	{
-	  struct link_map **runp = maps[k]->l_initfini;
-	  if (runp != NULL)
-	    /* Look through the dependencies of the object.  */
-	    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],
-			   (k - i) * sizeof (maps[0]));
-		  maps[k] = thisp;
-
-		  if (used != NULL)
-		    {
-		      char here_used = used[i];
-		      memmove (&used[i], &used[i + 1],
-			       (k - i) * sizeof (used[0]));
-		      used[k] = here_used;
-		    }
-
-		  if (seen[i + 1] > nmaps - i)
-		    {
-		      ++i;
-		      goto next_clear;
-		    }
-
-		  uint16_t this_seen = seen[i];
-		  memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
-		  seen[k] = this_seen;
-
-		  goto next;
-		}
-
-	  if (__glibc_unlikely (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:
-      memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
-
-    next:;
-    }
-}
-
-
 void
 _dl_fini (void)
 {
@@ -186,8 +88,11 @@ _dl_fini (void)
 	  assert (ns == LM_ID_BASE || i == nloaded || i == nloaded - 1);
 	  unsigned int nmaps = i;
 
-	  /* Now we have to do the sorting.  */
-	  _dl_sort_fini (maps, nmaps, NULL, ns);
+	  /* 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 + (ns == LM_ID_BASE), nmaps - (ns == LM_ID_BASE),
+			 NULL, true);
 
 	  /* 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-open.c b/elf/dl-open.c
index c539f10cf3..68907bf532 100644
--- a/elf/dl-open.c
+++ b/elf/dl-open.c
@@ -311,7 +311,7 @@ dl_open_worker (void *a)
   /* Sort the objects by dependency for the relocation process.  This
      allows IFUNC relocations to work and it also means copy
      relocation of dependencies are if necessary overwritten.  */
-  size_t nmaps = 0;
+  unsigned int nmaps = 0;
   struct link_map *l = new;
   do
     {
@@ -330,62 +330,11 @@ dl_open_worker (void *a)
       l = l->l_next;
     }
   while (l != NULL);
-  if (nmaps > 1)
-    {
-      uint16_t seen[nmaps];
-      memset (seen, '\0', sizeof (seen));
-      size_t i = 0;
-      while (1)
-	{
-	  ++seen[i];
-	  struct link_map *thisp = maps[i];
-
-	  /* 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.  */
-	  size_t k = nmaps - 1;
-	  while (k > i)
-	    {
-	      struct link_map **runp = maps[k]->l_initfini;
-	      if (runp != NULL)
-		/* Look through the dependencies of the object.  */
-		while (*runp != NULL)
-		  if (__glibc_unlikely (*runp++ == thisp))
-		    {
-		      /* Move the current object to the back past the last
-			 object with it as the dependency.  */
-		      memmove (&maps[i], &maps[i + 1],
-			       (k - i) * sizeof (maps[0]));
-		      maps[k] = thisp;
-
-		      if (seen[i + 1] > nmaps - i)
-			{
-			  ++i;
-			  goto next_clear;
-			}
-
-		      uint16_t this_seen = seen[i];
-		      memmove (&seen[i], &seen[i + 1],
-			       (k - i) * sizeof (seen[0]));
-		      seen[k] = this_seen;
-
-		      goto next;
-		    }
-
-	      --k;
-	    }
-
-	  if (++i == nmaps)
-	    break;
-	next_clear:
-	  memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
-	next:;
-	}
-    }
+  _dl_sort_maps (maps, nmaps, NULL, false);
 
   int relocation_in_progress = 0;
 
-  for (size_t i = nmaps; i-- > 0; )
+  for (unsigned int i = nmaps; i-- > 0; )
     {
       l = maps[i];
 
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
new file mode 100644
index 0000000000..416e8904ad
--- /dev/null
+++ b/elf/dl-sort-maps.c
@@ -0,0 +1,122 @@
+/* Sort array of link maps according to dependencies.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <ldsodefs.h>
+
+
+/* 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)
+{
+  /* A list of one element need not be sorted.  */
+  if (nmaps <= 1)
+    return;
+
+  unsigned int i = 0;
+  uint16_t seen[nmaps];
+  memset (seen, 0, nmaps * sizeof (seen[0]));
+  while (1)
+    {
+      /* Keep track of which object we looked at this round.  */
+      ++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.  */
+      unsigned int k = nmaps - 1;
+      while (k > i)
+	{
+	  struct link_map **runp = maps[k]->l_initfini;
+	  if (runp != NULL)
+	    /* Look through the dependencies of the object.  */
+	    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],
+			   (k - i) * sizeof (maps[0]));
+		  maps[k] = thisp;
+
+		  if (used != NULL)
+		    {
+		      char here_used = used[i];
+		      memmove (&used[i], &used[i + 1],
+			       (k - i) * sizeof (used[0]));
+		      used[k] = here_used;
+		    }
+
+		  if (seen[i + 1] > nmaps - i)
+		    {
+		      ++i;
+		      goto next_clear;
+		    }
+
+		  uint16_t this_seen = seen[i];
+		  memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0]));
+		  seen[k] = this_seen;
+
+		  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:
+      memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0]));
+
+    next:;
+    }
+}
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
index 5efae2d96d..8e815cb763 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
@@ -957,8 +957,8 @@ extern void _dl_init (struct link_map *main_map, int argc, char **argv,
 extern void _dl_fini (void) attribute_hidden;
 
 /* Sort array MAPS according to dependencies of the contained objects.  */
-extern void _dl_sort_fini (struct link_map **maps, size_t nmaps, char *used,
-			   Lmid_t ns) attribute_hidden;
+extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
+			   char *used, bool for_fini) attribute_hidden;
 
 /* The dynamic linker calls this function before and having changing
    any shared object mappings.  The `r_state' member of `struct r_debug'

On 11/13/2017 04:49 PM, Andreas Schwab wrote:
> +  /* We can skip looking for the binary itself which is at the front of
> +     the search list.  */
> +  _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false);

I'm still reviewing this.  Sorry for taking so long.  The following 
question isn't related to the cleanup as such.

Is the comment really correct?  I wonder if skipping the binary itself 
here causes this bug:

   <https://sourceware.org/bugzilla/show_bug.cgi?id=20972>

Thanks,
Florian

On 11/09/2017 10:45 AM, Andreas Schwab wrote:
> +/* Sort array MAPS according to dependencies of the contained objects.
> +   Array USED, if non-NULL, is permutated along MAPS.  If USE_RELDEPS also
> +   take relocation dependencies into account.  */
> +void
> +_dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
> +	       bool use_reldeps)
> +{
> +  /* A list of one element need not be sorted.  */
> +  if (nmaps <= 1)
> +    return;

We bail out early if we skipped the initial element of the link map 
array.  Previously, we would have sorted the one-element list, which is 
a no-op as well (the “while (k > i)” loop isn't entered), so this should 
be fine.

I didn't find any other differences after comparing the implementations 
line by line, so this is okay.  This is a great cleanup.

Thanks,
Florian