From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x32f.google.com (mail-ot1-x32f.google.com [IPv6:2607:f8b0:4864:20::32f]) by sourceware.org (Postfix) with ESMTPS id C6E263858C83 for ; Tue, 26 Apr 2022 19:29:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C6E263858C83 Received: by mail-ot1-x32f.google.com with SMTP id i3-20020a056830010300b00605468119c3so13721685otp.11 for ; Tue, 26 Apr 2022 12:29:40 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:references:from:in-reply-to :content-transfer-encoding; bh=yrSqVnE6xmZah3K6lR0uz7MvQAsMY08D1cTATU4wm8M=; b=YjLHuBeU6ac5DmrVmlfoeXoiPY9vCqImeWxuvDpArgG903qFeI/ihtY1JAFJhbtixd Mc484SMrnEW3SaJRjkU2MF1WA8WtMCbuZ4kIK8mAu56NwjTV5YL1a0vJlLjhJ9S71X65 0KN2aE5l2sGNbH0FsN5H/JqgZ/bXproan3P8eA9oCPFRud/kX4Xyrc+v8Df9o/nLs3O8 m+I4sU2dZe9pbRddX0hUkLSfRcUSN0NE7wr7V6ApIo1lfIQLTvBB6UrmGRucuykw5bZy yfmom/ZjuWYgMbx+mzBL18rv7a5R9CGUcErNugP31B8GnPAcNygWVVEKijLWfH9xUk8q iRLg== X-Gm-Message-State: AOAM532M0l6uQppuT22HG0VYlJOxWuvhFiJ82+U5/0KSTe4W/BOGlSkh jkqJoZ+jp4MP50gAzByP9tmwVA== X-Google-Smtp-Source: ABdhPJzBDiLTZKc485Hlv4dm9YRLib2DBbsrDnRMfYYY2tmNLR6z61qU24DOX0sHnY4KKAjRZJXf3w== X-Received: by 2002:a9d:1b6a:0:b0:605:5d7d:92cd with SMTP id l97-20020a9d1b6a000000b006055d7d92cdmr8841246otl.121.1651001379951; Tue, 26 Apr 2022 12:29:39 -0700 (PDT) Received: from ?IPV6:2804:431:c7ca:4214:745b:d03c:b667:123b? ([2804:431:c7ca:4214:745b:d03c:b667:123b]) by smtp.gmail.com with ESMTPSA id v19-20020a9d6053000000b00605cd5fde04sm926400otj.67.2022.04.26.12.29.38 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 26 Apr 2022 12:29:39 -0700 (PDT) Message-ID: Date: Tue, 26 Apr 2022 16:29:36 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 Subject: Re: [PATCH v5] elf: Fix DFS sorting algorithm for LD_TRACE_LOADED_OBJECTS with missing libraries (BZ #28868) Content-Language: en-US To: Siddhesh Poyarekar , libc-alpha@sourceware.org, Florian Weimer References: <20220304171200.3101821-1-adhemerval.zanella@linaro.org> <594f5e59-699b-627c-5858-68a4fb3ce51d@gotplt.org> From: Adhemerval Zanella In-Reply-To: <594f5e59-699b-627c-5858-68a4fb3ce51d@gotplt.org> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 26 Apr 2022 19:29:43 -0000 On 26/04/2022 15:43, Siddhesh Poyarekar wrote: > The patch doesn't apply anymore (conflict in elf/Makefile), please rebase it and post.  More comments below: > > On 04/03/2022 22:42, Adhemerval Zanella via Libc-alpha wrote: >> The _dl_map_object_deps ignores l_faked objects (set if the underlying >> file can't be opened by _dl_map_object): > > Maybe a more precise description is that the underlying file is not opened by _dl_map_object and the linker is in trace mode?  In other cases where the underlying file can't be opened, _dl_map_object quits with an error. Ack. > >> >> 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. >> --- >> v5: Refactor tests make rules. >> v4: Use --soname to build the libraries, fixed typos. >> v3: Removed stamp files to avoid add them as linker depedencies and >>      moved test evaluation to python script. >> v2: Added comments and fixed the default tst-trace1 --library-path. >> --- >>   elf/Makefile            |  54 ++++++++++++++++++++ >>   elf/dl-deps.c           |   2 + >>   elf/dl-sort-maps.c      |   4 +- >>   elf/libtracemod1-1.c    |   1 + >>   elf/libtracemod2-1.c    |   1 + >>   elf/libtracemod3-1.c    |   1 + >>   elf/libtracemod4-1.c    |   1 + >>   elf/libtracemod5-1.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 | 108 ++++++++++++++++++++++++++++++++++++++++ >>   15 files changed, 201 insertions(+), 1 deletion(-) >>   create mode 100644 elf/libtracemod1-1.c >>   create mode 100644 elf/libtracemod2-1.c >>   create mode 100644 elf/libtracemod3-1.c >>   create mode 100644 elf/libtracemod4-1.c >>   create mode 100644 elf/libtracemod5-1.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 >> >> diff --git a/elf/Makefile b/elf/Makefile >> index c96924e9c2..f30f64991f 100644 >> --- a/elf/Makefile >> +++ b/elf/Makefile >> @@ -617,6 +617,11 @@ modules-names = \ >>     libmarkermod4-2 \ >>     libmarkermod4-3 \ >>     libmarkermod4-4 \ >> +  libtracemod1-1 \ >> +  libtracemod2-1 \ >> +  libtracemod3-1 \ >> +  libtracemod4-1 \ >> +  libtracemod5-1 \ >>     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,47 @@ $(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) >> + >> +LDFLAGS-libtracemod1-1.so += -Wl,-soname,libtracemod1.so >> +LDFLAGS-libtracemod2-1.so += -Wl,-soname,libtracemod2.so >> +LDFLAGS-libtracemod3-1.so += -Wl,-soname,libtracemod3.so >> +LDFLAGS-libtracemod4-1.so += -Wl,-soname,libtracemod4.so >> +LDFLAGS-libtracemod5-1.so += -Wl,-soname,libtracemod5.so >> + >> +$(objpfx)libtracemod1-1.so: $(objpfx)libtracemod2-1.so \ >> +                $(objpfx)libtracemod3-1.so >> +$(objpfx)libtracemod2-1.so: $(objpfx)libtracemod4-1.so \ >> +                $(objpfx)libtracemod5-1.so >> + >> +define libtracemod-x >> +$(objpfx)libtracemod$(1)/libtracemod$(1).so: $(objpfx)libtracemod$(1)-1.so >> +    $$(make-target-directory) >> +    cp $$< $$@ >> +endef >> +libtracemod-suffixes = 1 2 3 4 5 >> +$(foreach i,$(libtracemod-suffixes), $(eval $(call libtracemod-x,$(i)))) >> + >> +define tst-trace-skeleton >> +$(objpfx)tst-trace$(1).out: $(objpfx)libtracemod1/libtracemod1.so \ >> +                $(objpfx)libtracemod2/libtracemod2.so \ >> +                $(objpfx)libtracemod3/libtracemod3.so \ >> +                $(objpfx)libtracemod4/libtracemod4.so \ >> +                $(objpfx)libtracemod5/libtracemod5.so \ >> +                $(..)scripts/tst-ld-trace.py \ >> +                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/libtracemod1.so" tst-trace$(1).exp \ >> +    ) > $$@; $$(evaluate-test) >> +endef > > OK, but would it be possible to not spawn the script as a subprocess? i.e. use {} instead of () for the recipe. > Ack. >> + >> +$(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)) > > OK. > >> 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 > > consider > Ack. >> +     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; > > OK. > >> diff --git a/elf/libtracemod1-1.c b/elf/libtracemod1-1.c >> new file mode 100644 >> index 0000000000..7c89c9a5a4 >> --- /dev/null >> +++ b/elf/libtracemod1-1.c >> @@ -0,0 +1 @@ >> +/* Empty  */ >> diff --git a/elf/libtracemod2-1.c b/elf/libtracemod2-1.c >> new file mode 100644 >> index 0000000000..7c89c9a5a4 >> --- /dev/null >> +++ b/elf/libtracemod2-1.c >> @@ -0,0 +1 @@ >> +/* Empty  */ >> diff --git a/elf/libtracemod3-1.c b/elf/libtracemod3-1.c >> new file mode 100644 >> index 0000000000..7c89c9a5a4 >> --- /dev/null >> +++ b/elf/libtracemod3-1.c >> @@ -0,0 +1 @@ >> +/* Empty  */ >> diff --git a/elf/libtracemod4-1.c b/elf/libtracemod4-1.c >> new file mode 100644 >> index 0000000000..7c89c9a5a4 >> --- /dev/null >> +++ b/elf/libtracemod4-1.c >> @@ -0,0 +1 @@ >> +/* Empty  */ >> diff --git a/elf/libtracemod5-1.c b/elf/libtracemod5-1.c >> new file mode 100644 >> index 0000000000..7c89c9a5a4 >> --- /dev/null >> +++ b/elf/libtracemod5-1.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  */ > > Isn't this unused? > It is, I will remove it. >> 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 > > OK, since libtracemod1.so depends on libtracemod2.so and libtracemod3.so but they're not in path. > >> 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 > > OK, since libtracemod2.so is now in path and libtracemod4.so and libtracemod5.so get pulled in libtracemod2.so. > >> 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 > > OK, since libtracemod3 is also in path. > >> 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 > > OK, since libtracemod4 is also in path. > >> 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 > > OK, since libtracemod5 is also in path. > >> 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 >> +# . >> + >> +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') > > OK. > >> + >> + >> +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) > > OK. > >> + >> + >> +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 >> + > > OK. > >> + >> +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:]) > > OK.