From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi1-x234.google.com (mail-oi1-x234.google.com [IPv6:2607:f8b0:4864:20::234]) by sourceware.org (Postfix) with ESMTPS id D6D1A3858D3C for ; Mon, 14 Feb 2022 20:11:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D6D1A3858D3C Received: by mail-oi1-x234.google.com with SMTP id i5so18663251oih.1 for ; Mon, 14 Feb 2022 12:11:22 -0800 (PST) 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=d56ULL0l37cIIFSO1U3eEiDxI7l2Rxw6a7fY4Cxlw5w=; b=lbcxb1cD4j0ymR34T6S8Ol31oBF5D1HvJwAISQQsc5XuFSSKSKR2bSbEjq0RkVhmVO mFDkmSKXsaz09khOXbdyiBNbVgayBdLQLqtVbEyVJzd/X4wH5l3j482lmM1qqdwpKyqL oxO4KwwQ8uz9KWcEW8kA85xllCanpIjEet4tvowSw4RFgvuhHQZprm5Eh3rOqtJx4lu3 /JjXiqNly/vKbcTgFZariBVlWl0JppsxRYSQwAscf2+y7Xkvw+fZHEfw9c1reySbsHH7 Pq8PPScStquO35YoWcXR4ttBW3e/esyOqqNIaHl3j1Kxa7HMdIgeqTbz+hy9EbkNyisc 2vSg== X-Gm-Message-State: AOAM532V5e0KUJR7VIgSqYTyBXWREDH0bciQ+dWQ6XGwMNrK1xKGIAUw 1iLPFRs9CFUVJQVP8IcXo7aCzM4m9gDsPA== X-Google-Smtp-Source: ABdhPJxEcRuMCCv4nCQY767/T/2eZqWYNjjwmV09K/+1LKnwm2zQtAGBJey6Jx1AxHBGDQsYA9eBPQ== X-Received: by 2002:a05:6808:1a17:: with SMTP id bk23mr252715oib.334.1644869480345; Mon, 14 Feb 2022 12:11:20 -0800 (PST) Received: from ?IPV6:2804:431:c7cb:6747:70ce:2039:9f74:f513? ([2804:431:c7cb:6747:70ce:2039:9f74:f513]) by smtp.gmail.com with ESMTPSA id e89sm2781240ote.54.2022.02.14.12.11.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 14 Feb 2022 12:11:20 -0800 (PST) Message-ID: Date: Mon, 14 Feb 2022 17:11:18 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.6.0 Subject: Re: [PATCH v2 1/3] elf: Do not rely on relocation dependencies for destructor sorting Content-Language: en-US To: Florian Weimer , libc-alpha@sourceware.org References: <10bf09764f3a6adfd12db33c5e71fb65452ac338.1643901334.git.fweimer@redhat.com> From: Adhemerval Zanella In-Reply-To: <10bf09764f3a6adfd12db33c5e71fb65452ac338.1643901334.git.fweimer@redhat.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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: Mon, 14 Feb 2022 20:11:26 -0000 On 03/02/2022 12:17, Florian Weimer via Libc-alpha wrote: > The new solution to tst-bz15311 preserves the in both cases, but f and g are not ordered in reverse construction > order yet. This is fine given that the test case is technically > undefined. I am seeing a regression with this patch: $ make test t=elf/order2-cmp [...] FAIL: elf/order2-cmp original exit status 1 /home/azanella/Projects/glibc/build/x86_64-linux-gnu/elf/order2.out - differ: byte 2, line 1 $ cat elf/order2.out 13245 It seems to be the expected out, since: $ ldd elf/order2mod1.so linux-vdso.so.1 (0x00007ffccdb88000) [...]elf/order2mod4.so (0x00007f415e4bd000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f415e278000) [...]order2mod3.so (0x00007f415e273000) /lib64/ld-linux-x86-64.so.2 (0x00007f415e4c9000) $ ldd elf/order2mod4.so linux-vdso.so.1 (0x00007ffdc75fe000) [...]/elf/order2mod3.so (0x00007f2870f30000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f2870ceb000) /lib64/ld-linux-x86-64.so.2 (0x00007f2870f3c000) The full tree is: destructor output elf/order2mod1.so '1' \_ elf/order2mod4.so '3' \_ elf/order2mod3.so '4' \_ elf/order2mod3.so '4' elf/order2mod2.so '2' \_ elf/order2mod3.so '4' So the fini order should be processed as: 1. elf/order2mod1.so 2. elf/order2mod4.so 3. elf/order2mod2.so 4. elf/order2mod3.so 5. application Since now the new algorithm uses a depth breadth search I am not sure why you haven't see this failure. > --- > v2: Rebase. > > elf/dl-close.c | 2 +- > elf/dl-deps.c | 3 +- > elf/dl-fini.c | 2 +- > elf/dl-sort-maps.c | 105 ++++--------------------------------- > elf/dso-sort-tests-1.def | 6 +-- > sysdeps/generic/ldsodefs.h | 2 +- > 6 files changed, 15 insertions(+), 105 deletions(-) > > diff --git a/elf/dl-close.c b/elf/dl-close.c > index bcd6e206e9..a161b95d00 100644 > --- a/elf/dl-close.c > +++ b/elf/dl-close.c > @@ -258,7 +258,7 @@ _dl_close_worker (struct link_map *map, bool force) > > /* 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, nloaded, (nsid == LM_ID_BASE), true); > + _dl_sort_maps (maps, nloaded, (nsid == LM_ID_BASE)); > > /* Call all termination functions at once. */ > bool unload_any = false; > diff --git a/elf/dl-deps.c b/elf/dl-deps.c > index c8bab5cad5..ef19e7c390 100644 > --- a/elf/dl-deps.c > +++ b/elf/dl-deps.c > @@ -614,8 +614,7 @@ Filters not supported with LD_TRACE_PRELINKING")); > /* If libc.so.6 is the main map, it participates in the sort, so > that the relocation order is correct regarding libc.so.6. */ > _dl_sort_maps (l_initfini, nlist, > - (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map), > - false); > + (l_initfini[0] != GL (dl_ns)[l_initfini[0]->l_ns].libc_map)); > > /* Terminate the list of dependencies. */ > l_initfini[nlist] = NULL; > diff --git a/elf/dl-fini.c b/elf/dl-fini.c > index 030b1fcbcd..f841868cdb 100644 > --- a/elf/dl-fini.c > +++ b/elf/dl-fini.c > @@ -96,7 +96,7 @@ _dl_fini (void) > /* 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, nmaps, (ns == LM_ID_BASE), true); > + _dl_sort_maps (maps, nmaps, (ns == LM_ID_BASE)); > > /* 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-sort-maps.c b/elf/dl-sort-maps.c > index 9e9d53ec47..95938c4a52 100644 > --- a/elf/dl-sort-maps.c > +++ b/elf/dl-sort-maps.c > @@ -23,11 +23,10 @@ > /* Note: this is the older, "original" sorting algorithm, being used as > default up to 2.35. > > - Sort array MAPS according to dependencies of the contained objects. > - If FOR_FINI is true, this is called for finishing an object. */ > + Sort array MAPS according to dependencies of the contained objects. */ > static void > _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) > + unsigned int skip) > { > /* Allows caller to do the common optimization of skipping the first map, > usually the main binary. */ > @@ -47,14 +46,6 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, > ++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. */ > @@ -67,7 +58,6 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, > 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], > @@ -87,31 +77,9 @@ _dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, > 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: > @@ -137,8 +105,7 @@ strong_alias (_dl_sort_maps_original, _dl_sort_maps); > decremented before storing the current map at each level. */ > > static void > -dfs_traversal (struct link_map ***rpo, struct link_map *map, > - bool *do_reldeps) > +dfs_traversal (struct link_map ***rpo, struct link_map *map) > { > if (map->l_visited) > return; > @@ -152,22 +119,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, > struct link_map *dep = map->l_initfini[i]; > if (dep->l_visited == 0 > && dep->l_main_map == 0) > - dfs_traversal (rpo, dep, do_reldeps); > - } > - } > - > - if (__glibc_unlikely (do_reldeps != NULL && map->l_reldeps != NULL)) > - { > - /* Indicate that we encountered relocation dependencies during > - traversal. */ > - *do_reldeps = true; > - > - for (int m = map->l_reldeps->act - 1; m >= 0; m--) > - { > - struct link_map *dep = map->l_reldeps->list[m]; > - if (dep->l_visited == 0 > - && dep->l_main_map == 0) > - dfs_traversal (rpo, dep, do_reldeps); > + dfs_traversal (rpo, dep); > } > } > > @@ -180,7 +132,7 @@ dfs_traversal (struct link_map ***rpo, struct link_map *map, > > static void > _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > - unsigned int skip __attribute__ ((unused)), bool for_fini) > + unsigned int skip __attribute__ ((unused))) > { > for (int i = nmaps - 1; i >= 0; i--) > maps[i]->l_visited = 0; > @@ -225,52 +177,15 @@ _dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, > bottom of above dfs_traversal() routine). */ > struct link_map **rpo_head = &rpo[nmaps]; > > - bool do_reldeps = false; > - bool *do_reldeps_ref = (for_fini ? &do_reldeps : NULL); > - > for (int i = nmaps - 1; i >= 0; i--) > { > - dfs_traversal (&rpo_head, maps[i], do_reldeps_ref); > - > + dfs_traversal (&rpo_head, maps[i]); > /* We can break early if all objects are already placed. */ > if (rpo_head == rpo) > - goto end; > + break; > } > assert (rpo_head == rpo); > > - end: > - /* Here we may do a second pass of sorting, using only l_initfini[] > - static dependency links. This is avoided if !FOR_FINI or if we didn't > - find any reldeps in the first DFS traversal. > - > - The reason we do this is: while it is unspecified how circular > - dependencies should be handled, the presumed reasonable behavior is to > - have destructors to respect static dependency links as much as possible, > - overriding reldeps if needed. And the first sorting pass, which takes > - l_initfini/l_reldeps links equally, may not preserve this priority. > - > - Hence we do a 2nd sorting pass, taking only DT_NEEDED links into account > - (see how the do_reldeps argument to dfs_traversal() is NULL below). */ > - if (do_reldeps) > - { > - for (int i = nmaps - 1; i >= 0; i--) > - rpo[i]->l_visited = 0; > - > - struct link_map **maps_head = &maps[nmaps]; > - for (int i = nmaps - 1; i >= 0; i--) > - { > - dfs_traversal (&maps_head, rpo[i], NULL); > - > - /* We can break early if all objects are already placed. > - The below memcpy is not needed in the do_reldeps case here, > - since we wrote back to maps[] during DFS traversal. */ > - if (maps_head == maps) > - return; > - } > - assert (maps_head == maps); > - return; > - } > - > memcpy (maps, rpo, sizeof (struct link_map *) * nmaps); > } > > @@ -284,7 +199,7 @@ _dl_sort_maps_init (void) > > void > _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) > + unsigned int skip) > { > /* It can be tempting to use a static function pointer to store and call > the current selected sorting algorithm routine, but experimentation > @@ -294,9 +209,9 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > input cases. A simple if-case with direct function calls appears to > be the fastest. */ > if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original)) > - _dl_sort_maps_original (maps, nmaps, skip, for_fini); > + _dl_sort_maps_original (maps, nmaps, skip); > else > - _dl_sort_maps_dfs (maps, nmaps, skip, for_fini); > + _dl_sort_maps_dfs (maps, nmaps, skip); > } > > #endif /* HAVE_TUNABLES. */ > diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def > index 5f7f18ef27..c2398408cd 100644 > --- a/elf/dso-sort-tests-1.def > +++ b/elf/dso-sort-tests-1.def > @@ -56,11 +56,7 @@ output: b>a>{} # relocation(dynamic) dependencies. While this is technically unspecified, the > # presumed reasonable practical behavior is for the destructor order to respect > # the static DT_NEEDED links (here this means the a->b->c->d order). > -# The older dynamic_sort=1 algorithm does not achieve this, while the DFS-based > -# dynamic_sort=2 algorithm does, although it is still arguable whether going > -# beyond spec to do this is the right thing to do. > # The below expected outputs are what the two algorithms currently produce > # respectively, for regression testing purposes. > tst-bz15311: {+a;+e;+f;+g;+d;%d;-d;-g;-f;-e;-a};a->b->c->d;d=>[ba];c=>a;b=>e=>a;c=>f=>b;d=>g=>c > -output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[ -output(glibc.rtld.dynamic_sort=2): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[ +output: {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[ diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h > index 2ebe7901c0..4d679510e3 100644 > --- a/sysdeps/generic/ldsodefs.h > +++ b/sysdeps/generic/ldsodefs.h > @@ -1123,7 +1123,7 @@ extern void _dl_fini (void) attribute_hidden; > > /* Sort array MAPS according to dependencies of the contained objects. */ > extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps, > - unsigned int skip, bool for_fini) attribute_hidden; > + unsigned int skip) attribute_hidden; > > /* The dynamic linker calls this function before and having changing > any shared object mappings. The `r_state' member of `struct r_debug'