From patchwork Tue Dec 14 21:02:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Florian Weimer X-Patchwork-Id: 48918 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EB7613858423 for ; Tue, 14 Dec 2021 21:03:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EB7613858423 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1639515788; bh=t+7/VuMxqxqpyorCwgw5Vg1UkRGGDxyfI5jYthnN38I=; h=To:Subject:In-Reply-To:References:Date:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=ZxOd9daQUpRxI0XfMfy8nudUdebMgDfu07UkdfmPE3JWieae7ddGUwU2MyXOi1hUW tlc7l5bFEkrN+sPqLc+UVwA4pHxRIpxuKnjgoLvx7UYup01jV5dWE3BPoSxYREmVsE bk8KY89x5pK+ndsR0CCs7zIwg2yIoXMKEo5Yo30s= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 05513385842A for ; Tue, 14 Dec 2021 21:02:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 05513385842A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-363-Kv2h4B4dO7OEIwqlaffDxA-1; Tue, 14 Dec 2021 16:02:08 -0500 X-MC-Unique: Kv2h4B4dO7OEIwqlaffDxA-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A078A81CCB7 for ; Tue, 14 Dec 2021 21:02:07 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.2.17.223]) by smtp.corp.redhat.com (Postfix) with ESMTPS id CB2BE5ED52 for ; Tue, 14 Dec 2021 21:02:06 +0000 (UTC) To: libc-alpha@sourceware.org Subject: [PATCH 1/2] elf: Do not rely on relocation dependencies for destructor sorting In-Reply-To: References: X-From-Line: 89f15608c1b4fd46715357fd108375f1e796e6f4 Mon Sep 17 00:00:00 2001 Message-Id: <89f15608c1b4fd46715357fd108375f1e796e6f4.1639515239.git.fweimer@redhat.com> Date: Tue, 14 Dec 2021 22:02:03 +0100 User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, 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-Patchwork-Original-From: Florian Weimer via Libc-alpha From: Florian Weimer Reply-To: Florian Weimer Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" The new solution to tst-bz15311 preserves the 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 c683884c35..1aa47bc7c5 100644 --- a/elf/dl-fini.c +++ b/elf/dl-fini.c @@ -92,7 +92,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 a274ed66cc..87e63fdb4b 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>{}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[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[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[