* [PATCH] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
@ 2014-11-25 14:01 Paulo Andrade
2014-11-25 14:01 ` [PATCH] Improve performance for deeply nested DSO dependencies (bug 17645) Paulo Andrade
0 siblings, 1 reply; 2+ messages in thread
From: Paulo Andrade @ 2014-11-25 14:01 UTC (permalink / raw)
To: libc-alpha; +Cc: Paulo Andrade
This patch implements a simple stable topological sort that moves
an entry at most once, by keeping track of, and resetting the weight
of the entries after every move. It breaks loops by choosing the
ones that appear first with the lowest weight, that is, less
dependencies.
If there is a loop, the "c" variable in the "sort" function will
be larger than 0.
Paulo Andrade (1):
Improve performance for deeply nested DSO dependencies (bug 17645)
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(-)
--
1.8.3.1
^ permalink raw reply [flat|nested] 2+ messages in thread
* [PATCH] Improve performance for deeply nested DSO dependencies (bug 17645)
2014-11-25 14:01 [PATCH] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies Paulo Andrade
@ 2014-11-25 14:01 ` Paulo Andrade
0 siblings, 0 replies; 2+ messages in thread
From: Paulo Andrade @ 2014-11-25 14:01 UTC (permalink / raw)
To: libc-alpha; +Cc: Paulo Andrade
---
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 <pcpa@gnu.org>
+
+ [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 <saugustine@google.com>
* 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;
--
1.8.3.1
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2014-11-25 14:01 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-11-25 14:01 [PATCH] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies Paulo Andrade
2014-11-25 14:01 ` [PATCH] Improve performance for deeply nested DSO dependencies (bug 17645) Paulo Andrade
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).