From patchwork Thu Nov 9 09:45:40 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Schwab X-Patchwork-Id: 24178 Received: (qmail 21466 invoked by alias); 9 Nov 2017 09:45:47 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 18901 invoked by uid 89); 9 Nov 2017 09:45:45 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx2.suse.de From: Andreas Schwab To: libc-alpha@sourceware.org Subject: [PATCH] Consolidate link map sorting X-Yow: An air of FRENCH FRIES permeates my nostrils!! Date: Thu, 09 Nov 2017 10:45:40 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 Combine the four places where link maps are sorted into a single function. This also moves the logic to skip the first map (representing the main binary) to the callers. Tested on x86-64 and aarch64. * elf/Makefile (dl-routines): Add dl-sort-maps. * elf/dl-sort-maps.c: New file. * sysdeps/generic/ldsodefs.h (_dl_sort_fini): Don't declare. (_dl_sort_maps): Declare. * elf/dl-fini.c (_dl_sort_fini): Remove. (_dl_fini): Use _dl_sort_maps instead of _dl_sort_fini. * elf/dl-close.c (_dl_close_worker): Likewise. * elf/dl-deps.c (_dl_map_object_deps): Use _dl_sort_maps instead of open-coding it. * elf/dl-open.c (dl_open_worker): Likewise. --- elf/Makefile | 2 +- elf/dl-close.c | 6 ++- elf/dl-deps.c | 59 ++-------------------- elf/dl-fini.c | 105 ++------------------------------------- elf/dl-open.c | 57 ++-------------------- elf/dl-sort-maps.c | 119 +++++++++++++++++++++++++++++++++++++++++++++ sysdeps/generic/ldsodefs.h | 4 +- 7 files changed, 137 insertions(+), 215 deletions(-) create mode 100644 elf/dl-sort-maps.c diff --git a/elf/Makefile b/elf/Makefile index a31fb72498..d49fd4673d 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -32,7 +32,7 @@ dl-routines = $(addprefix dl-,load lookup object reloc deps hwcaps \ runtime init fini debug misc \ version profile tls origin scope \ execstack caller open close trampoline \ - exception) + exception sort-maps) ifeq (yes,$(use-ldconfig)) dl-routines += dl-cache endif diff --git a/elf/dl-close.c b/elf/dl-close.c index 2b46b7cf8b..3dd75c8725 100644 --- a/elf/dl-close.c +++ b/elf/dl-close.c @@ -241,8 +241,10 @@ _dl_close_worker (struct link_map *map, bool force) } } - /* Sort the entries. */ - _dl_sort_fini (maps, nloaded, used, nsid); + /* 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); /* Call all termination functions at once. */ #ifdef SHARED diff --git a/elf/dl-deps.c b/elf/dl-deps.c index 35cad364b7..622331e6e2 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -585,62 +585,9 @@ Filters not supported with LD_TRACE_PRELINKING")); itself will always be initialize last. */ memcpy (l_initfini, map->l_searchlist.r_list, nlist * sizeof (struct link_map *)); - if (__glibc_likely (nlist > 1)) - { - /* We can skip looking for the binary itself which is at the front - of the search list. */ - i = 1; - uint16_t seen[nlist]; - memset (seen, 0, nlist * sizeof (seen[0])); - while (1) - { - /* Keep track of which object we looked at this round. */ - ++seen[i]; - struct link_map *thisp = l_initfini[i]; - - /* 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. */ - unsigned int k = nlist - 1; - while (k > i) - { - struct link_map **runp = l_initfini[k]->l_initfini; - if (runp != NULL) - /* Look through the dependencies of the object. */ - while (*runp != NULL) - if (__glibc_unlikely (*runp++ == thisp)) - { - /* Move the current object to the back past the last - object with it as the dependency. */ - memmove (&l_initfini[i], &l_initfini[i + 1], - (k - i) * sizeof (l_initfini[0])); - l_initfini[k] = thisp; - - if (seen[i + 1] > nlist - i) - { - ++i; - goto next_clear; - } - - uint16_t this_seen = seen[i]; - memmove (&seen[i], &seen[i + 1], - (k - i) * sizeof (seen[0])); - seen[k] = this_seen; - - goto next; - } - - --k; - } - - if (++i == nlist) - break; - next_clear: - memset (&seen[i], 0, (nlist - i) * sizeof (seen[0])); - - next:; - } - } + /* We can skip looking for the binary itself which is at the front of + the search list. */ + _dl_sort_maps (&l_initfini[1], nlist - 1, NULL, false); /* Terminate the list of dependencies. */ l_initfini[nlist] = NULL; diff --git a/elf/dl-fini.c b/elf/dl-fini.c index 71c06fc68b..8421c4fab8 100644 --- a/elf/dl-fini.c +++ b/elf/dl-fini.c @@ -25,104 +25,6 @@ typedef void (*fini_t) (void); -void -_dl_sort_fini (struct link_map **maps, size_t nmaps, char *used, Lmid_t ns) -{ - /* A list of one element need not be sorted. */ - if (nmaps == 1) - return; - - /* We can skip looking for the binary itself which is at the front - of the search list for the main namespace. */ - unsigned int i = ns == LM_ID_BASE; - uint16_t seen[nmaps]; - memset (seen, 0, nmaps * sizeof (seen[0])); - while (1) - { - /* Keep track of which object we looked at this round. */ - ++seen[i]; - struct link_map *thisp = maps[i]; - - /* Do not handle ld.so in secondary namespaces and object 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. */ - unsigned int k = nmaps - 1; - while (k > i) - { - struct link_map **runp = maps[k]->l_initfini; - if (runp != NULL) - /* Look through the dependencies of the object. */ - 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], - (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; - goto next_clear; - } - - uint16_t this_seen = seen[i]; - memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0])); - seen[k] = this_seen; - - goto next; - } - - if (__glibc_unlikely (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: - memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0])); - - next:; - } -} - - void _dl_fini (void) { @@ -186,8 +88,11 @@ _dl_fini (void) assert (ns == LM_ID_BASE || i == nloaded || i == nloaded - 1); unsigned int nmaps = i; - /* Now we have to do the sorting. */ - _dl_sort_fini (maps, nmaps, NULL, ns); + /* 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); /* 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-open.c b/elf/dl-open.c index c539f10cf3..68907bf532 100644 --- a/elf/dl-open.c +++ b/elf/dl-open.c @@ -311,7 +311,7 @@ dl_open_worker (void *a) /* Sort the objects by dependency for the relocation process. This allows IFUNC relocations to work and it also means copy relocation of dependencies are if necessary overwritten. */ - size_t nmaps = 0; + unsigned int nmaps = 0; struct link_map *l = new; do { @@ -330,62 +330,11 @@ dl_open_worker (void *a) l = l->l_next; } while (l != NULL); - if (nmaps > 1) - { - uint16_t seen[nmaps]; - memset (seen, '\0', sizeof (seen)); - size_t i = 0; - while (1) - { - ++seen[i]; - struct link_map *thisp = maps[i]; - - /* 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. */ - size_t k = nmaps - 1; - while (k > i) - { - struct link_map **runp = maps[k]->l_initfini; - if (runp != NULL) - /* Look through the dependencies of the object. */ - while (*runp != NULL) - if (__glibc_unlikely (*runp++ == thisp)) - { - /* Move the current object to the back past the last - object with it as the dependency. */ - memmove (&maps[i], &maps[i + 1], - (k - i) * sizeof (maps[0])); - maps[k] = thisp; - - if (seen[i + 1] > nmaps - i) - { - ++i; - goto next_clear; - } - - uint16_t this_seen = seen[i]; - memmove (&seen[i], &seen[i + 1], - (k - i) * sizeof (seen[0])); - seen[k] = this_seen; - - goto next; - } - - --k; - } - - if (++i == nmaps) - break; - next_clear: - memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0])); - next:; - } - } + _dl_sort_maps (maps, nmaps, NULL, false); int relocation_in_progress = 0; - for (size_t i = nmaps; i-- > 0; ) + for (unsigned int i = nmaps; i-- > 0; ) { l = maps[i]; diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c new file mode 100644 index 0000000000..f9bf5fbd2f --- /dev/null +++ b/elf/dl-sort-maps.c @@ -0,0 +1,119 @@ +/* Sort array of link maps according to dependencies. + Copyright (C) 2017 Free Software Foundation, Inc. + 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 + . */ + +#include + + +/* Sort array MAPS according to dependencies of the contained objects. + Array USED, if non-NULL, is permutated along MAPS. If USE_RELDEPS also + take relocation dependencies into account. */ +void +_dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used, + bool use_reldeps) +{ + /* A list of one element need not be sorted. */ + if (nmaps <= 1) + return; + + unsigned int i = 0; + uint16_t seen[nmaps]; + memset (seen, 0, nmaps * sizeof (seen[0])); + while (1) + { + /* Keep track of which object we looked at this round. */ + ++seen[i]; + struct link_map *thisp = maps[i]; + + /* Do not handle ld.so in secondary namespaces and object 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. */ + unsigned int k = nmaps - 1; + while (k > i) + { + struct link_map **runp = maps[k]->l_initfini; + if (runp != NULL) + /* Look through the dependencies of the object. */ + 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], + (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; + goto next_clear; + } + + uint16_t this_seen = seen[i]; + memmove (&seen[i], &seen[i + 1], (k - i) * sizeof (seen[0])); + seen[k] = this_seen; + + goto next; + } + + if (__glibc_unlikely (use_reldeps && 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: + memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0])); + + next:; + } +} diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h index 5efae2d96d..6084e3398f 100644 --- a/sysdeps/generic/ldsodefs.h +++ b/sysdeps/generic/ldsodefs.h @@ -957,8 +957,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_fini (struct link_map **maps, size_t nmaps, char *used, - Lmid_t ns) attribute_hidden; +extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps, + char *used, bool use_reldeps) attribute_hidden; /* The dynamic linker calls this function before and having changing any shared object mappings. The `r_state' member of `struct r_debug'