diff mbox series

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

Message ID 20220208183639.2262680-1-adhemerval.zanella@linaro.org
State Superseded
Headers
Series elf: Fix DFS sorting algorithm for LD_TRACE_LOADED_OBJECTS with missing libraries (BZ #28868) |

Checks

Context Check Description
dj/TryBot-apply_patch success Patch applied to master at the time it was sent
dj/TryBot-32bit success Build for i686

Commit Message

Adhemerval Zanella Netto Feb. 8, 2022, 6:36 p.m. UTC 
  The _dl_map_object_deps ignores l_faked objects (set if the underlying
file can't be opened by _dl_map_object):

490   for (nlist = 0, runp = known; runp; runp = runp->next)
491     {
492       if (__builtin_expect (trace_mode, 0) && runp->map->l_faked)
493         /* This can happen when we trace the loading.  */
494         --map->l_searchlist.r_nlist;
495       else
496         {
497           if (runp->map == map)
498             map_index = nlist;
499           map->l_searchlist.r_list[nlist++] = runp->map;
500         }
501
502       /* Now clear all the mark bits we set in the objects on the search list
503          to avoid duplicates, so the next call starts fresh.  */
504       runp->map->l_reserved = 0;
505     }

If there any missing libraries being processed, they will not be
considered on final nlist size passed on _dl_sort_maps later in the
function.  And it is then used on _dl_sort_maps_dfs on the stack
allocated working maps:

222   /* Array to hold RPO sorting results, before we copy back to  maps[].  */
223   struct link_map *rpo[nmaps];
224
225   /* The 'head' position during each DFS iteration. Note that we start at
226      one past the last element due to first-decrement-then-store (see the
227      bottom of above dfs_traversal() routine).  */
228   struct link_map **rpo_head = &rpo[nmaps];

However while transversing the 'l_initfini' on dfs_traversal it will
still considere the l_faked maps and thus update rpo more times than the
allocated working 'rpo', overflowing the stack object.

As suggested in bugzilla, one option would be to avoid sorting the maps
for trace mode.  However I think ignoring l_faked object does make
sense (there is one less constraint to call the sorting function), it
allows a slight less stack usage for trace, and it is slight simpler
solution.

The tests does trigger the stack overflow, however I tried to make
it more generic to check different scenarios or missing objects.

Checked on x86_64-linux-gnu.
---
 elf/Makefile            | 60 +++++++++++++++++++++++++++++++++
 elf/dl-sort-maps.c      |  2 +-
 elf/libtracemod1.c      |  1 +
 elf/libtracemod2.c      |  1 +
 elf/libtracemod3.c      |  1 +
 elf/libtracemod4.c      |  1 +
 elf/libtracemod5.c      |  1 +
 elf/libtracemod6.c      |  1 +
 elf/tst-trace1.exp      |  4 +++
 elf/tst-trace2.exp      |  6 ++++
 elf/tst-trace3.exp      |  6 ++++
 elf/tst-trace4.exp      |  6 ++++
 elf/tst-trace5.exp      |  6 ++++
 scripts/tst-ld-trace.py | 75 +++++++++++++++++++++++++++++++++++++++++
 14 files changed, 170 insertions(+), 1 deletion(-)
 create mode 100644 elf/libtracemod1.c
 create mode 100644 elf/libtracemod2.c
 create mode 100644 elf/libtracemod3.c
 create mode 100644 elf/libtracemod4.c
 create mode 100644 elf/libtracemod5.c
 create mode 100644 elf/libtracemod6.c
 create mode 100644 elf/tst-trace1.exp
 create mode 100644 elf/tst-trace2.exp
 create mode 100644 elf/tst-trace3.exp
 create mode 100644 elf/tst-trace4.exp
 create mode 100644 elf/tst-trace5.exp
 create mode 100755 scripts/tst-ld-trace.py

Comments

Dmitry V. Levin Feb. 8, 2022, 10:48 p.m. UTC | #1 
On Tue, Feb 08, 2022 at 03:36:39PM -0300, Adhemerval Zanella via Libc-alpha wrote:
[...]
> 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  */

I wonder why do you need these empty files.

In the reproducer included in the bug report empty shared libraries
are created without any input files at all:

$ gcc -shared -o missing/libmissing1.so -Wl,-soname,libmissing1.so
$ gcc -shared -o missing/libmissing2.so -Wl,-soname,libmissing2.so
Florian Weimer Feb. 8, 2022, 10:51 p.m. UTC | #2 
* Adhemerval Zanella via Libc-alpha:

> diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
> index 9e9d53ec47..f049178ac3 100644
> --- a/elf/dl-sort-maps.c
> +++ b/elf/dl-sort-maps.c
> @@ -140,7 +140,7 @@ static void
>  dfs_traversal (struct link_map ***rpo, struct link_map *map,
>  	       bool *do_reldeps)
>  {
> -  if (map->l_visited)
> +  if (map->l_visited || map->l_faked)
>      return;
>  
>    map->l_visited = 1;

Sorry, not a full review, but please add a comment why map->l_faked is
needed, referencing _dl_map_object_deps and the l_fake filtering there,
and perhaps also add a comment referencing dfs_traversal in the l_fake
filtering.

Thanks,
Florian
Adhemerval Zanella Netto Feb. 8, 2022, 10:56 p.m. UTC | #3 
On 08/02/2022 19:48, Dmitry V. Levin wrote:
> On Tue, Feb 08, 2022 at 03:36:39PM -0300, Adhemerval Zanella via Libc-alpha wrote:
> [...]
>> 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  */
> 
> I wonder why do you need these empty files.
> 
> In the reproducer included in the bug report empty shared libraries
> are created without any input files at all:
> 
> $ gcc -shared -o missing/libmissing1.so -Wl,-soname,libmissing1.so
> $ gcc -shared -o missing/libmissing2.so -Wl,-soname,libmissing2.so

Maybe because without a file it would require more Makefile tinkering to
add specific rules to build the modules.  Not sure if this would really
be simpler than add the files.
Adhemerval Zanella Netto Feb. 8, 2022, 10:56 p.m. UTC | #4 
On 08/02/2022 19:51, Florian Weimer wrote:
> * Adhemerval Zanella via Libc-alpha:
> 
>> diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
>> index 9e9d53ec47..f049178ac3 100644
>> --- a/elf/dl-sort-maps.c
>> +++ b/elf/dl-sort-maps.c
>> @@ -140,7 +140,7 @@ static void
>>  dfs_traversal (struct link_map ***rpo, struct link_map *map,
>>  	       bool *do_reldeps)
>>  {
>> -  if (map->l_visited)
>> +  if (map->l_visited || map->l_faked)
>>      return;
>>  
>>    map->l_visited = 1;
> 
> Sorry, not a full review, but please add a comment why map->l_faked is
> needed, referencing _dl_map_object_deps and the l_fake filtering there,
> and perhaps also add a comment referencing dfs_traversal in the l_fake
> filtering.

Ok.
Adhemerval Zanella Netto Feb. 9, 2022, 12:15 p.m. UTC | #5 
On 08/02/2022 19:56, Adhemerval Zanella wrote:
> 
> 
> On 08/02/2022 19:48, Dmitry V. Levin wrote:
>> On Tue, Feb 08, 2022 at 03:36:39PM -0300, Adhemerval Zanella via Libc-alpha wrote:
>> [...]
>>> 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  */
>>
>> I wonder why do you need these empty files.
>>
>> In the reproducer included in the bug report empty shared libraries
>> are created without any input files at all:
>>
>> $ gcc -shared -o missing/libmissing1.so -Wl,-soname,libmissing1.so
>> $ gcc -shared -o missing/libmissing2.so -Wl,-soname,libmissing2.so
> 
> Maybe because without a file it would require more Makefile tinkering to

I meant 'Mainly' here, I did not want to sound pedantic here.

> add specific rules to build the modules.  Not sure if this would really
> be simpler than add the files.
diff mbox series

Patch

diff --git a/elf/Makefile b/elf/Makefile
index ac37159b89..fefc000f80 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -819,6 +819,11 @@  modules-names = \
   tst-tlsmod8 \
   tst-tlsmod9 \
   tst-unique1mod1 \
+  libtracemod1 \
+  libtracemod2 \
+  libtracemod3 \
+  libtracemod4 \
+  libtracemod5 \
   tst-unique1mod2 \
   tst-unique2mod1 \
   tst-unique2mod2 \
@@ -1072,6 +1077,8 @@  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 \
   # tests-special
 endif
 
@@ -2733,3 +2740,56 @@  $(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)
+
+
+libtracemod-suffixes = 5 4 3 2 1
+define libtracemod
+$(objpfx)libtracemod$(1).stamp: $(objpfx)libtracemod$(1).so
+	touch $(objpfx)libtracemod$(1).stamp
+endef
+$(foreach s,$(libtracemod-suffixes), $(eval $(call libtracemod,$(s))))
+
+# 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
+libtracemod-mv: $(objpfx)libtracemod1.stamp
+	$(call libtracemod-mv,2)
+	$(call libtracemod-mv,3)
+	$(call libtracemod-mv,4)
+	$(call libtracemod-mv,5)
+
+LDFLAGS-libtracemod1.so = -Wl,--no-as-needed \
+	-L$(objpfx) -ltracemod2 -ltracemod3
+LDFLAGS-libtracemod2.so = -Wl,--no-as-needed \
+	-L$(objpfx) -ltracemod4 -ltracemod5
+$(objpfx)libtracemod2.so: $(objpfx)libtracemod4.stamp \
+			  $(objpfx)libtracemod5.stamp
+$(objpfx)libtracemod1.so: $(objpfx)libtracemod2.stamp \
+			  $(objpfx)libtracemod3.stamp
+
+define tst-trace-skeleton
+$(objpfx)tst-trace$(1).out: $(..)scripts/tst-ld-trace.py \
+			    $(objpfx)libtracemod1.so \
+			    libtracemod-mv \
+			    tst-trace$(1).exp
+	( $(test-wrapper-env) \
+	   LD_TRACE_LOADED_OBJECTS=1 \
+	   $(elf-objpfx)$(rtld-installed-name) \
+	   --library-path $(2) \
+	   $(objpfx)libtracemod1.so > $$@T \
+	  && $(PYTHON) $(..)scripts/tst-ld-trace.py $$@T 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-sort-maps.c b/elf/dl-sort-maps.c
index 9e9d53ec47..f049178ac3 100644
--- a/elf/dl-sort-maps.c
+++ b/elf/dl-sort-maps.c
@@ -140,7 +140,7 @@  static void
 dfs_traversal (struct link_map ***rpo, struct link_map *map,
 	       bool *do_reldeps)
 {
-  if (map->l_visited)
+  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..8283e63cc6
--- /dev/null
+++ b/scripts/tst-ld-trace.py
@@ -0,0 +1,75 @@ 
+#!/usr/bin/python3
+# ELF editor for load align tests.
+# 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 sys
+
+
+def is_vdso(lib):
+    return lib.startswith('linux-gate') or lib.startswith ('linux-vdso')
+
+
+def parse_trace(fin, fref):
+    trace = []
+    for line in fin:
+        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)]
+
+    reference = sorted(line.replace('\n','') for line in fref.readlines())
+
+    ret = 0 if sorted(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 {}: {}".format(fin.name, i))
+    sys.exit (ret)
+
+
+def get_parser():
+    parser = argparse.ArgumentParser(description=__doc__)
+    parser.add_argument('input',
+                        help='LD_TRACE_LOADED_OBJECTS input')
+    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.input, 'r') as fin, open(opts.reference, 'r') as fref:
+        parse_trace(fin, fref)
+
+
+if __name__ == '__main__':
+    main(sys.argv[1:])