From patchwork Tue May 19 13:25:04 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chung-Lin Tang X-Patchwork-Id: 1293341 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces@sourceware.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=mentor.com Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 49RGpS6zVPz9sRK for ; Tue, 19 May 2020 23:25:20 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C66ED3948A6D; Tue, 19 May 2020 13:25:18 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from esa1.mentor.iphmx.com (esa1.mentor.iphmx.com [68.232.129.153]) by sourceware.org (Postfix) with ESMTPS id E5BF43947C3E for ; Tue, 19 May 2020 13:25:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org E5BF43947C3E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=mentor.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=ChungLin_Tang@mentor.com IronPort-SDR: Yu713YyEoHDrtPtllyn9FfRpfupdLn7MZDwYrevSCtJG0i5kqDuI7fXeBv2IklGOFyPcGBIJ4D CFmzRVJdVAKKJaf/HV7X/ujJYpVJMRMxmZtzbtKf07LvJkpLqZ/optvy7tLrHxXt0JvLD8hxxw VkHatHS9RdVWHI3vRRbr+5j07E224u8uvU5b++77JeffDnXbiWHmUBvUErGaRrVGO0+ZW2MwqZ zr69+nrqQrSFoX0PtroX5clSqTMQzoezadLL1uEtpIEO354ZDbVhprYbiic5uweIPuKYqtudNH s+k= X-IronPort-AV: E=Sophos;i="5.73,410,1583222400"; d="scan'208";a="51021133" Received: from orw-gwy-01-in.mentorg.com ([192.94.38.165]) by esa1.mentor.iphmx.com with ESMTP; 19 May 2020 05:25:10 -0800 IronPort-SDR: jLT8fEicOa/nf/OUpIF0QDyl94g9FSHxHN55NJ+ha65UZp1+KeEokrOtJv7KjlLlK5g86v5VK+ VjIiq0f/DJeW2YHJUGZ7C0imQ4COMxx9SawvfQJkURvW4uY/L0gicwsquRCQ6O6ZywmziM6ydK qsN9yyt5zzEyEfBZUG7fPTipu5im/ov/NUuIXgigSX8qVdhSSPZMYXlCtahFDvEdhCdyP8EDIQ zaQs6u0juikY3aMkEceliBkXVItHER1HBP/cc6kbWtaH0twpOTv6iOTsweHNi2E3sMFpK3lvbr Qj4= From: Chung-Lin Tang Subject: [PATCH v2 2/2] BZ #17645, fix slow DSO sorting behavior in dynamic loader To: GNU C Library , Carlos O'Donell Message-ID: <94c168b4-cb25-fd2a-d284-c9fa94b881f7@mentor.com> Date: Tue, 19 May 2020 21:25:04 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:68.0) Gecko/20100101 Thunderbird/68.8.0 MIME-Version: 1.0 Content-Language: en-US X-ClientProxiedBy: svr-orw-mbx-04.mgc.mentorg.com (147.34.90.204) To svr-orw-mbx-02.mgc.mentorg.com (147.34.90.202) X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: , Reply-To: cltang@codesourcery.com Cc: Catherine Moore Errors-To: libc-alpha-bounces@sourceware.org Sender: "Libc-alpha" Hi Carlos, This part is the actual code changes in elf/, changes since the last version[1] are: 1. As you suggested, the use of a glibc tunable (glibc.rtld.dynamic_sort) to allow specifying which sorting algorithm to use. "1" for the current algorithm, "2" for the new DFS based one. The default is 1 to be conservative. I tried a few styles on how this should be best written, and settled for a static function pointer set on the first run of _dl_sort_maps(). I'm open to better suggestions. If glibc is configured with --enable-tunables=no, the behavior is to only use the current old algorithm. 2. Addition of l_map_used/l_map_done bitfields in struct link_map, to be used in _dl_close_worker(), instead of overloading on l_reserved. This has the benefit of not needing to clean up at the end, saving a few CPU cycles. (BTW, 'l_used' was already taken, thus named l_map_*) 3. Now _dl_sort_maps() has the used[] parameter removed, but due to many of the current sorting call-sites skipping the first map, while the new algorithm does not want this kind of +1/-1, a new 'unsigned int skip' argument is added. This is due to both algorithms existing together as an option, and it is a little unclear whether removing "skip-the-first" is detrimental to the current algorithm in practice (and I didn't want to regress it when it is still default), so doing this to be conservative. There was a small change that removed a redundant call of _dl_sort_maps in dl-open.c, which was already accomplished during this time by the fix for #16272, thus of course dropped in this patch. As for the issue of "interleaved scopes" in my algorithm, actually, when I tried comparing the LD_DEBUG output of both algorithms, the scope list appears to be the same, i.e. both have libc.so.6 and ld.so interleaved in the sequence, and the sequences appears to be the same. This is quite easy to test now, using GLIBC_TUNABLES=glibc.rtld.dynamic_sort=[12] to switch in between. I hope this is still in time to be in 2.32, as the non-default option. Thanks, Chung-Lin [1] https://sourceware.org/pipermail/libc-alpha/2019-July/105200.html 2020-05-19 Chung-Lin Tang [BZ #17645] [BZ #15311] [BZ #15310] * elf/dl-close.c (_dl_close_worker): Remove used[], done[] char arrays, use l_map_used/l_map_done bitfields instead. Adjust call to _dl_sort_maps. * elf/dl-deps.c (_dl_map_object_deps): Adjust call to _dl_sort_maps. * elf/dl-fini.c (_dl_fini): Likewise. * elf/dl-sort_maps.c (_dl_sort_maps_original): Adapted from original _dl_sort_maps. (dfs_traversal): New static function. (_dl_sort_maps_dfs): New Reverse-Postorder (RPO) based implementation. (_dl_sort_maps): Select and call either _dl_sort_maps_original or _dl_sort_maps_dfs based on glibc.rtld.dynamic_sort. * elf/dl-tunables.list (rtld): New namespace with tunable 'dynamic_sort'. * include/link.h (struct link_map): Add l_visited:1, l_map_used:1, and l_map_done:1 bitfields. * sysdeps/generic/ldsodefs.h (_dl_sort_maps): Adjust declaration. diff --git a/elf/dl-close.c b/elf/dl-close.c index 73b2817bbf..3d52126200 100644 --- a/elf/dl-close.c +++ b/elf/dl-close.c @@ -164,8 +164,6 @@ _dl_close_worker (struct link_map *map, bool force) bool any_tls = false; const unsigned int nloaded = ns->_ns_nloaded; - char used[nloaded]; - char done[nloaded]; struct link_map *maps[nloaded]; /* Run over the list and assign indexes to the link maps and enter @@ -173,24 +171,21 @@ _dl_close_worker (struct link_map *map, bool force) int idx = 0; for (struct link_map *l = ns->_ns_loaded; l != NULL; l = l->l_next) { + l->l_map_used = 0; + l->l_map_done = 0; l->l_idx = idx; maps[idx] = l; ++idx; - } assert (idx == nloaded); - /* Prepare the bitmaps. */ - memset (used, '\0', sizeof (used)); - memset (done, '\0', sizeof (done)); - /* Keep track of the lowest index link map we have covered already. */ int done_index = -1; while (++done_index < nloaded) { struct link_map *l = maps[done_index]; - if (done[done_index]) + if (l->l_map_done) /* Already handled. */ continue; @@ -201,12 +196,12 @@ _dl_close_worker (struct link_map *map, bool force) /* See CONCURRENCY NOTES in cxa_thread_atexit_impl.c to know why acquire is sufficient and correct. */ && atomic_load_acquire (&l->l_tls_dtor_count) == 0 - && !used[done_index]) + && !l->l_map_used) continue; /* We need this object and we handle it now. */ - done[done_index] = 1; - used[done_index] = 1; + l->l_map_used = 1; + l->l_map_done = 1; /* Signal the object is still needed. */ l->l_idx = IDX_STILL_USED; @@ -222,9 +217,9 @@ _dl_close_worker (struct link_map *map, bool force) { assert ((*lp)->l_idx >= 0 && (*lp)->l_idx < nloaded); - if (!used[(*lp)->l_idx]) + if (!(*lp)->l_map_used) { - used[(*lp)->l_idx] = 1; + (*lp)->l_map_used = 1; /* If we marked a new object as used, and we've already processed it, then we need to go back and process again from that point forward to @@ -247,9 +242,9 @@ _dl_close_worker (struct link_map *map, bool force) { assert (jmap->l_idx >= 0 && jmap->l_idx < nloaded); - if (!used[jmap->l_idx]) + if (!jmap->l_map_used) { - used[jmap->l_idx] = 1; + jmap->l_map_used = 1; if (jmap->l_idx - 1 < done_index) done_index = jmap->l_idx - 1; } @@ -259,8 +254,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 + (nsid == LM_ID_BASE), nloaded - (nsid == LM_ID_BASE), - used + (nsid == LM_ID_BASE), true); + _dl_sort_maps (maps, nloaded, (nsid == LM_ID_BASE), true); /* Call all termination functions at once. */ #ifdef SHARED @@ -277,7 +271,7 @@ _dl_close_worker (struct link_map *map, bool force) /* All elements must be in the same namespace. */ assert (imap->l_ns == nsid); - if (!used[i]) + if (!imap->l_map_used) { assert (imap->l_type == lt_loaded && !imap->l_nodelete_active); @@ -330,7 +324,7 @@ _dl_close_worker (struct link_map *map, bool force) if (i < first_loaded) first_loaded = i; } - /* Else used[i]. */ + /* Else imap->l_map_used. */ else if (imap->l_type == lt_loaded) { struct r_scope_elem *new_list = NULL; @@ -554,7 +548,7 @@ _dl_close_worker (struct link_map *map, bool force) for (unsigned int i = first_loaded; i < nloaded; ++i) { struct link_map *imap = maps[i]; - if (!used[i]) + if (!imap->l_map_used) { assert (imap->l_type == lt_loaded); diff --git a/elf/dl-deps.c b/elf/dl-deps.c index b5a43232a7..0851971dca 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -611,7 +611,7 @@ Filters not supported with LD_TRACE_PRELINKING")); memcpy (l_initfini, map->l_searchlist.r_list, nlist * sizeof (struct link_map *)); - _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false); + _dl_sort_maps (l_initfini, nlist, 1, false); /* Terminate the list of dependencies. */ l_initfini[nlist] = NULL; diff --git a/elf/dl-fini.c b/elf/dl-fini.c index 231db3d66d..5b1bf6371c 100644 --- a/elf/dl-fini.c +++ b/elf/dl-fini.c @@ -92,8 +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 + (ns == LM_ID_BASE), nmaps - (ns == LM_ID_BASE), - NULL, true); + _dl_sort_maps (maps, nmaps, (ns == LM_ID_BASE), true); /* 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 86f1e23c85..7d143cc487 100644 --- a/elf/dl-sort-maps.c +++ b/elf/dl-sort-maps.c @@ -16,16 +16,24 @@ License along with the GNU C Library; if not, see . */ +#include #include +#include +/* Note: this is the older, "original" sorting algorithm, being used as + default up to 2.32. -/* Sort array MAPS according to dependencies of the contained objects. - Array USED, if non-NULL, is permutated along MAPS. If FOR_FINI this is - called for finishing an object. */ -void -_dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used, - bool for_fini) + Sort array MAPS according to dependencies of the contained objects. + If FOR_FINI is true, this is called for finishing an object. */ +static void +_dl_sort_maps_original (struct link_map **maps, unsigned int nmaps, + unsigned int skip, bool for_fini) { + /* Allows caller to do the common optimization of skipping the first map, + usually the main binary. */ + maps += skip; + nmaps -= skip; + /* A list of one element need not be sorted. */ if (nmaps <= 1) return; @@ -66,14 +74,6 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used, (k - i) * sizeof (maps[0])); maps[k] = thisp; - if (used != NULL) - { - char here_used = used[i]; - memmove (&used[i], &used[i + 1], - (k - i) * sizeof (used[0])); - used[k] = here_used; - } - if (seen[i + 1] > nmaps - i) { ++i; @@ -120,3 +120,160 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used, next:; } } + +#if !HAVE_TUNABLES +/* In this case, just default to the original algorithm. */ +strong_alias (_dl_sort_maps_original, _dl_sort_maps); +#else + +/* We use a recursive function due to its better clarity and ease of + implementation, as well as faster execution speed. We already use + alloca() for list allocation during the breadth-first search of + dependencies in _dl_map_object_deps(), and this should be on the + same order of worst-case stack usage. */ + +static void +dfs_traversal (struct link_map ***rpo, struct link_map *map, + bool *do_reldeps) +{ + if (map->l_visited) + return; + + map->l_visited = 1; + + if (map->l_initfini) + { + for (int i = 0; map->l_initfini[i] != NULL; i++) + { + struct link_map *dep = map->l_initfini[i]; + if (dep->l_visited == 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) + dfs_traversal (rpo, dep, do_reldeps); + } + } + + *rpo -= 1; + **rpo = map; +} + +/* Topologically sort array MAPS according to dependencies of the contained + objects. */ + +static void +_dl_sort_maps_dfs (struct link_map **maps, unsigned int nmaps, + unsigned int skip __attribute__ ((unused)), bool for_fini) +{ + for (int i = 0; i < nmaps; i++) + maps[i]->l_visited = 0; + + /* We apply DFS traversal for each of maps[i] until the whole total order + is found and we're at the start of the Reverse-Postorder (RPO) sequence, + which is a topological sort. + + We go from maps[nmaps - 1] backwards towards maps[0] at this level. + Due to the breadth-first search (BFS) ordering we receive, going + backwards usually gives a more shallow depth-first recursion depth, + adding more stack usage safety. Also, combined with the natural + processing order of l_initfini[] at each node during DFS, this maintains + an ordering closer to the original link ordering in the sorting results + under most simpler cases. + + Another reason we order the top level backwards, it that maps[0] is + usually exactly the main object of which we're in the midst of + _dl_map_object_deps() processing, and maps[0]->l_initfini[] is still + blank. If we start the traversal from maps[0], since having no + dependencies yet filled in, maps[0] will always be immediately + incorrectly placed at the last place in the order (first in reverse). + Adjusting the order so that maps[0] is last traversed naturally avoids + this problem. + + Further, the old "optimization" of skipping the main object at maps[0] + from the call-site (i.e. _dl_sort_maps(maps+1,nmaps-1)) is in general + no longer valid, since traversing along object dependency-links + may "find" the main object even when it is not included in the initial + order (e.g. a dlopen()'ed shared object can have circular dependencies + linked back to itself). In such a case, traversing N-1 objects will + create a N-object result, and raise problems. + + To summarize, just passing in the full list, and iterating from back + to front makes things much more straightforward. */ + + struct link_map *rpo[nmaps]; + 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); + + /* We can break early if all objects are already placed. */ + if (rpo_head == rpo) + goto end; + } + assert (rpo_head == rpo); + + end: + /* This is avoided if !FOR_FINI or if we didn't find any reldeps in + the first DFS traversal. */ + if (do_reldeps) + { + for (int i = 0; i < nmaps; 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); +} + +void +_dl_sort_maps (struct link_map **maps, unsigned int nmaps, + unsigned int skip, bool for_fini) +{ + /* Function pointer to sorting algorithm currently in use. */ + static void (*sort_maps) (struct link_map **, unsigned int, + unsigned int, bool) = NULL; + if (__glibc_unlikely (sort_maps == NULL)) + { + /* Select sorting algorithm based on tunable value. */ + int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, + int32_t, NULL); + if (__glibc_likely (algorithm == 1)) + sort_maps = _dl_sort_maps_original; + else if (algorithm == 2) + sort_maps = _dl_sort_maps_dfs; + else + __builtin_unreachable (); + } + + sort_maps (maps, nmaps, skip, for_fini); +} + +#endif /* HAVE_TUNABLES. */ diff --git a/elf/dl-tunables.list b/elf/dl-tunables.list index 0d398dd251..aeeafe704a 100644 --- a/elf/dl-tunables.list +++ b/elf/dl-tunables.list @@ -126,4 +126,13 @@ glibc { default: 3 } } + + rtld { + dynamic_sort { + type: INT_32 + minval: 1 + maxval: 2 + default: 1 + } + } } diff --git a/include/link.h b/include/link.h index aea268439c..48c11c5d68 100644 --- a/include/link.h +++ b/include/link.h @@ -177,6 +177,10 @@ struct link_map unsigned int l_init_called:1; /* Nonzero if DT_INIT function called. */ unsigned int l_global:1; /* Nonzero if object in _dl_global_scope. */ unsigned int l_reserved:2; /* Reserved for internal use. */ + unsigned int l_visited:1; /* Used internally for map dependency + graph traversal. */ + unsigned int l_map_used:1; /* These two bits are used during traversal */ + unsigned int l_map_done:1; /* of maps in _dl_close_worker(). */ unsigned int l_phdr_allocated:1; /* Nonzero if the data structure pointed to by `l_phdr' is allocated. */ unsigned int l_soname_added:1; /* Nonzero if the SONAME is for sure in diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h index 5ff4a2831b..a0f60df81c 100644 --- a/sysdeps/generic/ldsodefs.h +++ b/sysdeps/generic/ldsodefs.h @@ -1017,8 +1017,8 @@ extern void _dl_init (struct link_map *main_map, int argc, char **argv, 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, - char *used, bool for_fini) attribute_hidden; +extern void _dl_sort_maps (struct link_map **, unsigned int, unsigned int, + bool) attribute_hidden; /* The dynamic linker calls this function before and having changing any shared object mappings. The `r_state' member of `struct r_debug'