[v4] elf: Fix DFS sorting algorithm for LD_TRACE_LOADED_OBJECTS with missing libraries (BZ #28868)

diff --git a/elf/Makefile b/elf/Makefile
index c96924e9c2..929003fc5d 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -617,6 +617,11 @@  modules-names = \
   libmarkermod4-2 \
   libmarkermod4-3 \
   libmarkermod4-4 \
+  libtracemod1 \
+  libtracemod2 \
+  libtracemod3 \
+  libtracemod4 \
+  libtracemod5 \
   ltglobmod1 \
   ltglobmod2 \
   neededobj1 \
@@ -1079,6 +1084,11 @@  tests-special += \
   $(objpfx)tst-initorder2-cmp.out \
   $(objpfx)tst-unused-dep-cmp.out \
   $(objpfx)tst-unused-dep.out \
+  $(objpfx)tst-trace1.out \
+  $(objpfx)tst-trace2.out \
+  $(objpfx)tst-trace3.out \
+  $(objpfx)tst-trace4.out \
+  $(objpfx)tst-trace5.out \
   # tests-special
 endif
 
@@ -2725,3 +2735,50 @@  $(objpfx)tst-p_align3: $(objpfx)tst-p_alignmod3.so
 $(objpfx)tst-p_align3.out: tst-p_align3.sh $(objpfx)tst-p_align3
 	$(SHELL) $< $(common-objpfx) '$(test-program-prefix)'; \
 	$(evaluate-test)
+
+
+# Move the library to a folder so it can be selected by --library-path
+define libtracemod-mv
+  test -d $(objpfx)libtracemod$(1) || mkdir $(objpfx)libtracemod$(1)
+  test -f $(objpfx)libtracemod$(1).so \
+	  && mv $(objpfx)libtracemod$(1).so $(objpfx)libtracemod$(1)
+endef
+.PHONY: libtracemod-mv
+libtracemod-mv: $(objpfx)libtracemod1.so
+	$(call libtracemod-mv,2)
+	$(call libtracemod-mv,3)
+	$(call libtracemod-mv,4)
+	$(call libtracemod-mv,5)
+
+LDFLAGS-libtracemod1.so += -Wl,-soname,libtracemod1.so
+LDFLAGS-libtracemod2.so += -Wl,-soname,libtracemod2.so
+LDFLAGS-libtracemod3.so += -Wl,-soname,libtracemod3.so
+LDFLAGS-libtracemod4.so += -Wl,-soname,libtracemod4.so
+LDFLAGS-libtracemod5.so += -Wl,-soname,libtracemod5.so
+
+$(objpfx)libtracemod1.so: $(objpfx)libtracemod2.so \
+			  $(objpfx)libtracemod3.so
+$(objpfx)libtracemod2.so: $(objpfx)libtracemod4.so \
+			  $(objpfx)libtracemod5.so
+
+define tst-trace-skeleton
+$(objpfx)tst-trace$(1).out: $(..)scripts/tst-ld-trace.py \
+			    $(objpfx)libtracemod1.so \
+			    libtracemod-mv \
+			    tst-trace$(1).exp
+	( $(PYTHON) $(..)scripts/tst-ld-trace.py \
+	    "$(test-wrapper-env) $(elf-objpfx)$(rtld-installed-name) \
+	    --library-path $(common-objpfx):$(strip $(2)) \
+	    $(objpfx)libtracemod1.so" tst-trace$(1).exp \
+	) > $$@; $$(evaluate-test)
+endef
+
+$(eval $(call tst-trace-skeleton,1,))
+$(eval $(call tst-trace-skeleton,2,\
+	$(objpfx)libtracemod2))
+$(eval $(call tst-trace-skeleton,3,\
+	$(objpfx)libtracemod2:$(objpfx)libtracemod3))
+$(eval $(call tst-trace-skeleton,4,\
+	$(objpfx)libtracemod2:$(objpfx)libtracemod3:$(objpfx)libtracemod4))
+$(eval $(call tst-trace-skeleton,5,\
+	$(objpfx)libtracemod2:$(objpfx)libtracemod3:$(objpfx)libtracemod4:$(objpfx)libtracemod5))
diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index a2fc278256..77ff2b3895 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
@@ -473,6 +473,8 @@  _dl_map_object_deps (struct link_map *map,
 
   for (nlist = 0, runp = known; runp; runp = runp->next)
     {
+      /* _dl_sort_maps ignores l_faked object, so it is safe to not considere
+	 them for nlist.  */
       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
 	/* This can happen when we trace the loading.  */
 	--map->l_searchlist.r_nlist;
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
index 9e9d53ec47..96638d7ed1 100644
--- a/elf/dl-sort-maps.c
+++ b/elf/dl-sort-maps.c
@@ -140,7 +140,9 @@  static void
 dfs_traversal (struct link_map ***rpo, struct link_map *map,
 	       bool *do_reldeps)
 {
-  if (map->l_visited)
+  /* _dl_map_object_deps ignores l_faked objects when calculating the
+     number of maps before calling _dl_sort_maps, ignore them as well.  */
+  if (map->l_visited || map->l_faked)
     return;
 
   map->l_visited = 1;
diff --git a/elf/libtracemod1.c b/elf/libtracemod1.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod1.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/libtracemod2.c b/elf/libtracemod2.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod2.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/libtracemod3.c b/elf/libtracemod3.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod3.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/libtracemod4.c b/elf/libtracemod4.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod4.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/libtracemod5.c b/elf/libtracemod5.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod5.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/libtracemod6.c b/elf/libtracemod6.c
new file mode 100644
index 0000000000..7c89c9a5a4
--- /dev/null
+++ b/elf/libtracemod6.c
@@ -0,0 +1 @@ 
+/* Empty  */
diff --git a/elf/tst-trace1.exp b/elf/tst-trace1.exp
new file mode 100644
index 0000000000..4a6f5211a6
--- /dev/null
+++ b/elf/tst-trace1.exp
@@ -0,0 +1,4 @@ 
+ld 1
+libc 1
+libtracemod2.so 0
+libtracemod3.so 0
diff --git a/elf/tst-trace2.exp b/elf/tst-trace2.exp
new file mode 100644
index 0000000000..e13506e2eb
--- /dev/null
+++ b/elf/tst-trace2.exp
@@ -0,0 +1,6 @@ 
+ld 1
+libc 1
+libtracemod2.so 1
+libtracemod3.so 0
+libtracemod4.so 0
+libtracemod5.so 0
diff --git a/elf/tst-trace3.exp b/elf/tst-trace3.exp
new file mode 100644
index 0000000000..e574549d12
--- /dev/null
+++ b/elf/tst-trace3.exp
@@ -0,0 +1,6 @@ 
+ld 1
+libc 1
+libtracemod2.so 1
+libtracemod3.so 1
+libtracemod4.so 0
+libtracemod5.so 0
diff --git a/elf/tst-trace4.exp b/elf/tst-trace4.exp
new file mode 100644
index 0000000000..31ca97b35b
--- /dev/null
+++ b/elf/tst-trace4.exp
@@ -0,0 +1,6 @@ 
+ld 1
+libc 1
+libtracemod2.so 1
+libtracemod3.so 1
+libtracemod4.so 1
+libtracemod5.so 0
diff --git a/elf/tst-trace5.exp b/elf/tst-trace5.exp
new file mode 100644
index 0000000000..5d7d953726
--- /dev/null
+++ b/elf/tst-trace5.exp
@@ -0,0 +1,6 @@ 
+ld 1
+libc 1
+libtracemod2.so 1
+libtracemod3.so 1
+libtracemod4.so 1
+libtracemod5.so 1
diff --git a/scripts/tst-ld-trace.py b/scripts/tst-ld-trace.py
new file mode 100755
index 0000000000..f5a4028003
--- /dev/null
+++ b/scripts/tst-ld-trace.py
@@ -0,0 +1,108 @@ 
+#!/usr/bin/python3
+# Dump the output of LD_TRACE_LOADED_OBJECTS in architecture neutral format.
+# Copyright (C) 2022 Free Software Foundation, Inc.
+# Copyright The GNU Toolchain Authors.
+# 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
+# <https://www.gnu.org/licenses/>.
+
+import argparse
+import os
+import subprocess
+import sys
+
+try:
+    subprocess.run
+except:
+    class _CompletedProcess:
+        def __init__(self, args, returncode, stdout=None, stderr=None):
+            self.args = args
+            self.returncode = returncode
+            self.stdout = stdout
+            self.stderr = stderr
+
+    def _run(*popenargs, input=None, timeout=None, check=False, **kwargs):
+        assert(timeout is None)
+        with subprocess.Popen(*popenargs, **kwargs) as process:
+            try:
+                stdout, stderr = process.communicate(input)
+            except:
+                process.kill()
+                process.wait()
+                raise
+            returncode = process.poll()
+            if check and returncode:
+                raise subprocess.CalledProcessError(returncode, popenargs)
+        return _CompletedProcess(popenargs, returncode, stdout, stderr)
+
+    subprocess.run = _run
+
+def is_vdso(lib):
+    return lib.startswith('linux-gate') or lib.startswith('linux-vdso')
+
+
+def parse_trace(cmd, fref):
+    new_env = os.environ.copy()
+    new_env['LD_TRACE_LOADED_OBJECTS'] = '1'
+    trace_out = subprocess.run(cmd, stdout=subprocess.PIPE, check=True,
+                               universal_newlines=True, env=new_env).stdout
+    trace = []
+    for line in trace_out.splitlines():
+        line = line.strip()
+        if is_vdso(line):
+            continue
+        fields = line.split('=>' if '=>' in line else ' ')
+        lib = os.path.basename(fields[0].strip())
+        if lib.startswith('ld'):
+            lib = 'ld'
+        elif lib.startswith('libc'):
+            lib = 'libc'
+        found = 1 if fields[1].strip() != 'not found' else 0
+        trace += ['{} {}'.format(lib, found)]
+    trace = sorted(trace)
+
+    reference = sorted(line.replace('\n','') for line in fref.readlines())
+
+    ret = 0 if trace == reference else 1
+    if ret != 0:
+        for i in reference:
+            if i not in trace:
+                print("Only in {}: {}".format(fref.name, i))
+        for i in trace:
+            if i not in reference:
+                print("Only in trace: {}".format(i))
+
+    sys.exit(ret)
+
+
+def get_parser():
+    parser = argparse.ArgumentParser(description=__doc__)
+    parser.add_argument('command',
+                        help='comand to run')
+    parser.add_argument('reference',
+                        help='reference file to compare')
+    return parser
+
+
+def main(argv):
+    parser = get_parser()
+    opts = parser.parse_args(argv)
+    with open(opts.reference, 'r') as fref:
+        # Remove the initial 'env' command.
+        parse_trace(opts.command.split()[1:], fref)
+
+
+if __name__ == '__main__':
+    main(sys.argv[1:])