From patchwork Tue Nov 25 14:01:11 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paulo Andrade X-Patchwork-Id: 3900 Received: (qmail 19003 invoked by alias); 25 Nov 2014 14:01:52 -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 18942 invoked by uid 89); 25 Nov 2014 14:01:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-qg0-f47.google.com X-Received: by 10.224.4.8 with SMTP id 8mr32970408qap.77.1416924105637; Tue, 25 Nov 2014 06:01:45 -0800 (PST) From: Paulo Andrade X-Google-Original-From: Paulo Andrade To: libc-alpha@sourceware.org Cc: Paulo Andrade Subject: [PATCH] Improve performance for deeply nested DSO dependencies (bug 17645) Date: Tue, 25 Nov 2014 12:01:11 -0200 Message-Id: <1416924071-28907-2-git-send-email-pcpa@gnu.org> In-Reply-To: <1416924071-28907-1-git-send-email-pcpa@gnu.org> References: <1416924071-28907-1-git-send-email-pcpa@gnu.org> --- ChangeLog | 10 ++++ elf/Makefile | 1 + elf/dl-deps.c | 125 +++++++++++++++++++++++++-------------------- elf/dl-fini.c | 159 +++++++++++++++++++++++++++------------------------------- elf/dl-open.c | 117 +++++++++++++++++++++++------------------- 5 files changed, 222 insertions(+), 190 deletions(-) diff --git a/ChangeLog b/ChangeLog index e9ce141..5d487b5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2014-11-24 Paulo Andrade + + [BZ #17645] + * elf/dl-fini.c: Implement simple stable topological sorting + for DSO dependencies. + * elf/dl-deps.c: Likewise. + * elf/dl-open.c: Likewise. + * elf/Makefile: Make one of the test cases have only one + valid result. + 2014-11-24 Sterling Augustine * sysdeps/x86_64/start.S (_start): Use ENTRY and END macros. diff --git a/elf/Makefile b/elf/Makefile index 9e07073..f710f69 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -510,6 +510,7 @@ $(objpfx)unload8mod1.so: $(objpfx)unload8mod2.so $(objpfx)unload8mod2.so: $(objpfx)unload8mod3.so $(objpfx)unload8mod3.so: $(libdl) $(objpfx)tst-initordera2.so: $(objpfx)tst-initordera1.so +$(objpfx)tst-initorderb1.so: $(objpfx)tst-initordera2.so $(objpfx)tst-initorderb2.so: $(objpfx)tst-initorderb1.so $(objpfx)tst-initordera2.so $(objpfx)tst-initordera3.so: $(objpfx)tst-initorderb2.so $(objpfx)tst-initorderb1.so $(objpfx)tst-initordera4.so: $(objpfx)tst-initordera3.so diff --git a/elf/dl-deps.c b/elf/dl-deps.c index b34039c..8f3e321 100644 --- a/elf/dl-deps.c +++ b/elf/dl-deps.c @@ -138,6 +138,75 @@ cannot load auxiliary `%s' because of empty dynamic string token " \ \ __result; }) + +static void +weight (struct link_map **maps, size_t nmaps, char *seen, unsigned int *w) +{ + int i, c; + struct link_map *m, **r; + for (i = 1; i < nmaps; ++i) + { + m = maps[i]; + if ((r = m->l_initfini)) + { + c = 0; + while (*r) + { + if (*r != m && (*r)->l_idx >= 0 && !seen[(*r)->l_idx]) + ++c; + ++r; + } + w[i] = c; + } + else + w[i] = 0; + } +} + + +static void +sort (struct link_map **maps, size_t nmaps) +{ + int c, i, k; + unsigned int w[nmaps]; + char seen[nmaps]; + struct link_map *t; + memset(seen, 0, nmaps); + /* l_idx not set or is unreliable at this point */ + for (i = 0; i < nmaps; ++i) + { + if (maps[i]->l_idx >= 0) + maps[i]->l_idx = i; + } + /* We can skip looking for the binary itself which is at the front + of the search list. */ + w[0] = 0; + seen[0] = 1; + weight(maps, k = nmaps, seen, w); + c = 0; + while (k > 2 && c < k) + { + for (i = 1; i < k; ++i) + { + if (w[i] == c && maps[i]->l_idx >= 0) + { + seen[maps[i]->l_idx] = 1; + if (--k != i) + { + t = maps[k]; + maps[k] = maps[i]; + maps[i] = t; + } + weight(maps, k, seen, w); + c = -1; + break; + } + } + ++c; + } +} + + static void preload (struct list *known, unsigned int *nlist, struct link_map *map) { @@ -611,61 +680,7 @@ Filters not supported with LD_TRACE_PRELINKING")); 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:; - } - } + sort (l_initfini, nlist); /* Terminate the list of dependencies. */ l_initfini[nlist] = NULL; diff --git a/elf/dl-fini.c b/elf/dl-fini.c index c355775..f2b4c7d 100644 --- a/elf/dl-fini.c +++ b/elf/dl-fini.c @@ -26,101 +26,92 @@ typedef void (*fini_t) (void); +static void +weight (struct link_map **maps, size_t nmaps, char *seen, unsigned int *w, int from) +{ + int i, c; + struct link_map *m, **r; + for (i = from; i < nmaps; ++i) + { + m = maps[i]; + if ((r = m->l_initfini)) + { + c = 0; + while (*r) + { + if (*r != m && (*r)->l_idx >= 0 && !seen[(*r)->l_idx]) + ++c; + ++r; + } + w[i] = c; + } + else + w[i] = 0; + } + + /* If a cycle exists with a link time dependency, + preserve the latter. */ + for (i = from; i < nmaps; ++i) + { + m = maps[i]; + if (m->l_reldeps) + { + r = &m->l_reldeps->list[0]; + c = m->l_reldeps->act; + while (c-- > 0) + { + if (*r != m && (*r)->l_idx >= 0 && !seen[(*r)->l_idx]) + ++w[i]; + ++r; + } + } + } +} + + void internal_function _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) + int from; + int c, i, k; + unsigned int w[nmaps]; + char seen[nmaps]; + struct link_map *t; + memset(seen, 0, nmaps); + from = ns == LM_ID_BASE; + if (from) { - /* 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)) + w[0] = 0; + seen[0] = 0; + } + weight(maps, k = nmaps, seen, w, from); + c = 0; + while (k > from + 1 && c < k) + { + for (i = from; i < k; ++i) + { + t = maps[i]; + if (w[i] == c && t->l_idx >= 0 && t->l_real == t) + { + seen[t->l_idx] = 1; + if (--k != i) { - 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) + maps[i] = maps[k]; + maps[k] = t; + if (used) { - ++i; - goto next_clear; + char c = used[i]; + used[i] = used[k]; + used[k] = c; } - - 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:; + weight(maps, k, seen, w, from); + c = -1; + break; } - - --k; } - - skip: - if (++i == nmaps) - break; - next_clear: - memset (&seen[i], 0, (nmaps - i) * sizeof (seen[0])); - - next:; + ++c; } } diff --git a/elf/dl-open.c b/elf/dl-open.c index dec3d32..b7fde4f 100644 --- a/elf/dl-open.c +++ b/elf/dl-open.c @@ -181,6 +181,71 @@ _dl_find_dso_for_object (const ElfW(Addr) addr) } rtld_hidden_def (_dl_find_dso_for_object); + +static void +weight (struct link_map **maps, size_t nmaps, char *seen, unsigned int *w) +{ + int i, c; + struct link_map *m, **r; + for (i = 0; i < nmaps; ++i) + { + m = maps[i]; + if ((r = m->l_initfini)) + { + c = 0; + while (*r) + { + if (*r != m && (*r)->l_idx >= 0 && !seen[(*r)->l_idx]) + ++c; + ++r; + } + w[i] = c; + } + else + w[i] = 0; + } +} + + +static void +sort (struct link_map **maps, size_t nmaps) +{ + int c, i, k; + unsigned int w[nmaps]; + char seen[nmaps]; + struct link_map *t; + memset(seen, 0, nmaps); + /* l_idx not set or is unreliable at this point */ + for (i = 0; i < nmaps; ++i) + { + if (maps[i]->l_idx >= 0) + maps[i]->l_idx = i; + } + weight(maps, k = nmaps, seen, w); + c = 0; + while (k > 1 && c < k) + { + for (i = 0; i < k; ++i) + { + if (w[i] == c && maps[i]->l_idx >= 0) + { + seen[maps[i]->l_idx] = 1; + if (--k != i) + { + t = maps[k]; + maps[k] = maps[i]; + maps[i] = t; + } + weight(maps, k, seen, w); + c = -1; + break; + } + } + ++c; + } +} + + static void dl_open_worker (void *a) { @@ -325,57 +390,7 @@ dl_open_worker (void *a) } 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:; - } - } + sort (maps, nmaps); int relocation_in_progress = 0;