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

  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
---
v2: Added comments and fixed the default tst-trace1 --library-path.
---
 elf/Makefile            | 61 +++++++++++++++++++++++++++++++++
 elf/dl-deps.c           |  2 ++
 elf/dl-sort-maps.c      |  4 ++-
 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 +++++++++++++++++++++++++++++++++++++++++
 15 files changed, 175 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
  

* Adhemerval Zanella via Libc-alpha:

> diff --git a/elf/Makefile b/elf/Makefile
> index b2bd03a9f6..07b27010f6 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

Hmm, the sorting is slightly weird?

> @@ -2733,3 +2740,57 @@ $(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)

This constract is a bit weird.  Why is libtracemod-mv needed as a
separate makefile target?  Why do these stamp files exist?

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

It's surprising that this works because $(objpfx)libtracemod5.stamp are
empty files.  I would expect link failures here.

I must this is all a bit strange to me.  Usually, when we want
particular DT_NEEDED strings, we use stub link objects with the required
soname, I think, along with a regular/direct dependency on the shared
object pathname (no -l, but the $(objpfx) path).

> +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 $(objpfx)..:$(strip $(2)) \
> +	   $(objpfx)libtracemod1.so > $$@T \
> +	  && $(PYTHON) $(..)scripts/tst-ld-trace.py $$@T tst-trace$(1).exp \
> +	) > $$@; $$(evaluate-test)
> +endef

$(objpfx).. is $(objpfx-common).  The empty $(2) evaluates to the
current directory below for case 1.  Is this what we want?  There is
also a divergence between default and hard-coded testing mode here, I
think.

We should probably add something to launch tests using Python, so that
the ld.so invocation can be folded into the Python helper script.

> +$(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 c8bab5cad5..8b39383359 100644
> --- a/elf/dl-deps.c
> +++ b/elf/dl-deps.c
> @@ -489,6 +489,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 save 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..2ed62da7dd 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 filter 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;

Actually code changes look good. 8-)


> diff --git a/scripts/tst-ld-trace.py b/scripts/tst-ld-trace.py
> new file mode 100755
> index 0000000000..b45f406afb
> --- /dev/null
> +++ b/scripts/tst-ld-trace.py
> @@ -0,0 +1,75 @@
> +#!/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 sys
> +
> +
> +def is_vdso(lib):
> +    return lib.startswith('linux-gate') or lib.startswith ('linux-vdso')


Superfluous space: 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)

" could be '.

Thanks,
Florian
  

On 12/02/2022 12:29, Florian Weimer wrote:
> * Adhemerval Zanella via Libc-alpha:
> 
>> diff --git a/elf/Makefile b/elf/Makefile
>> index b2bd03a9f6..07b27010f6 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
> 
> Hmm, the sorting is slightly weird?

Indeed, it was because I rename the modules but I did not changed the position.
I will fix it.

> 
>> @@ -2733,3 +2740,57 @@ $(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)
> 
> This constract is a bit weird.  Why is libtracemod-mv needed as a
> separate makefile target?  Why do these stamp files exist?

The idea is the test checks for some different permutations of missing libraries
by appending paths on the --library-path.

The libtracemodN.stamp is create on the libtracemodN.so is built, and since
libtracemod1.so requires all other libtracemodN.stamps to be built, it means
that the 'mv' to the specific folder can proceed.

The idea is to have the final layout as:

  $(objpfx)libtracemod1.so
  $(objpfx)libtracemod2/libtracemod2.so
  $(objpfx)libtracemod3/libtracemod3.so
  $(objpfx)libtracemod4/libtracemod4.so
  $(objpfx)libtracemod5/libtracemod5.so

> 
>> +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
> 
> It's surprising that this works because $(objpfx)libtracemod5.stamp are
> empty files.  I would expect link failures here.
> 
> I must this is all a bit strange to me.  Usually, when we want
> particular DT_NEEDED strings, we use stub link objects with the required
> soname, I think, along with a regular/direct dependency on the shared
> object pathname (no -l, but the $(objpfx) path).

At least it does work on the architectures I tests, ld simple ignores the
file (not sure if this is what we really want). The problem is the
regule/direct dependency it embedded the pathname on DT_NEEDED, which is
not what I want to test the missing libraries.

I came up with this solution to have only a set of libraries to used with
different tests, otherwise to support parallel makefile we will need 
a different set of libraries for each one.

> 
>> +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 $(objpfx)..:$(strip $(2)) \
>> +	   $(objpfx)libtracemod1.so > $$@T \
>> +	  && $(PYTHON) $(..)scripts/tst-ld-trace.py $$@T tst-trace$(1).exp \
>> +	) > $$@; $$(evaluate-test)
>> +endef
> 
> $(objpfx).. is $(objpfx-common).  The empty $(2) evaluates to the
> current directory below for case 1.  Is this what we want?  There is
> also a divergence between default and hard-coded testing mode here, I
> think.

I think an empty is fine, it will evaluate to '--library-path $(objpfx-common):'.
And I did test for --enable-hardcoded-path-in-tests, since all the links are
done through -l, it will behaves exactly as default configuration.

> 
> We should probably add something to launch tests using Python, so that
> the ld.so invocation can be folded into the Python helper script.

Ok, I think I can change the script to actually do the command issue.

> 
>> +$(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 c8bab5cad5..8b39383359 100644
>> --- a/elf/dl-deps.c
>> +++ b/elf/dl-deps.c
>> @@ -489,6 +489,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 save 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..2ed62da7dd 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 filter 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;
> 
> Actually code changes look good. 8-)
> 
> 
>> diff --git a/scripts/tst-ld-trace.py b/scripts/tst-ld-trace.py
>> new file mode 100755
>> index 0000000000..b45f406afb
>> --- /dev/null
>> +++ b/scripts/tst-ld-trace.py
>> @@ -0,0 +1,75 @@
>> +#!/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 sys
>> +
>> +
>> +def is_vdso(lib):
>> +    return lib.startswith('linux-gate') or lib.startswith ('linux-vdso')
> 
> 
> Superfluous space: lib.startswith  'linux-vdso')

Ack.

> 
>> +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)
> 
> " could be '.

Ack.

> 
> Thanks,
> Florian
>