* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
@ 2014-11-25 13:52 ` paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-25 14:10 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (22 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2014-11-25 13:52 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |paulo.cesar.pereira.de.andr
| |ade at gmail dot com
--- Comment #1 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 7972
--> https://sourceware.org/bugzilla/attachment.cgi?id=7972&action=edit
Proposed patch
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.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-25 13:52 ` [Bug dynamic-link/17645] " paulo.cesar.pereira.de.andrade at gmail dot com
@ 2014-11-25 14:10 ` paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-25 14:37 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (21 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2014-11-25 14:10 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #2 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
The change to elf/Makefile is to make the test case have
only one valid result.
The expected result is:
start_a1
start_a2
start_b1
start_b2
start_a3
start_a4
main
finish_a4
finish_a3
finish_b2
finish_b1
finish_a2
finish_a1
but "a1" and "b1" do not have any dependencies, and
without the elf/Makefile patch it would result in:
start_a1
start_b1
start_a2
start_b2
start_a3
start_a4
main
finish_a4
finish_a3
finish_b2
finish_b1
finish_a2
finish_a1
The "input" of that test case, wihtout the patch is:
[0] = "" ()
[1] = a4 (a4 a3 libc.so)
[2] = a1 (a1 libc.so)
[3] = b2 (b2 b1 a2 libc.so)
[4] = libc.so (libc.so ld.so)
[5] = a3 (a3 b2 b1 libc.so)
[6] = b1 (b1 libc.so)
[7] = a2 (a2 a1 libc.so)
[8] = ld.so ()
where items in () are the dependencies of an object,
and [] is the input order.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-25 13:52 ` [Bug dynamic-link/17645] " paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-25 14:10 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2014-11-25 14:37 ` paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-26 16:41 ` carlos at redhat dot com
` (20 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2014-11-25 14:37 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #3 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 7973
--> https://sourceware.org/bugzilla/attachment.cgi?id=7973&action=edit
simple sh based helper script to run the test case
Simple script to make it easier to run the test case.
Just unpack the test case and run sourceme.sh to set
environment variables and have it to echo how to run
the tests. This allows keeping unchanged the test case
(not done by me).
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (2 preceding siblings ...)
2014-11-25 14:37 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2014-11-26 16:41 ` carlos at redhat dot com
2014-11-26 21:56 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (19 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: carlos at redhat dot com @ 2014-11-26 16:41 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Carlos O'Donell <carlos at redhat dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |carlos at redhat dot com
--- Comment #4 from Carlos O'Donell <carlos at redhat dot com> ---
(In reply to Paulo Andrade from comment #1)
> Created attachment 7972 [details]
> Proposed patch
>
> 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.
At the high-level your patch is almost ready.
You refactor the sorting code out into a static function that the compiler can
inline and you use the same pattern in all places where sorting happens. This
is good.
You are missing two important things:
* More code comments. You should comment each sort routine with a high-level
comment about what you're doing and why. This is particularly important for the
weight functions.
* Tests. The existing set of tests are insufficient to cover the changes you
are proposing. While it seems unfair, and I understand that, this kind of
change has not been undertaken because of the lack of testing. You need to add
more tests. The *best* testing is actually a test which deterministically
generates a sequence of permutations of linked objects and verifies they are
sorted correctly by the algorithms in question. This way we can show that the
sorting works for a large set of object dependency orderings. When we get a bug
report, and we will, we can enlarge the set of automated testing to include the
case the bug report claims and see what went wrong.
If you can cover those two things, then you're ready to post the patch to
libc-alpha for more formal review.
This looks really good though and you're making great progress in a difficult
part of the dynamic loader.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (3 preceding siblings ...)
2014-11-26 16:41 ` carlos at redhat dot com
@ 2014-11-26 21:56 ` paulo.cesar.pereira.de.andrade at gmail dot com
2014-11-28 15:51 ` carlos at redhat dot com
` (18 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2014-11-26 21:56 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #5 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
(In reply to Carlos O'Donell from comment #4)
> (In reply to Paulo Andrade from comment #1)
> > Created attachment 7972 [details]
> > Proposed patch
> >
> > 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.
>
> At the high-level your patch is almost ready.
>
> You refactor the sorting code out into a static function that the compiler
> can inline and you use the same pattern in all places where sorting happens.
> This is good.
The code is small enough that this way (static functions) should be
better. But it also cannot be really shared, without extra parameters,
as there are 3 slightly different variants of the loop.
> You are missing two important things:
>
> * More code comments. You should comment each sort routine with a high-level
> comment about what you're doing and why. This is particularly important for
> the weight functions.
Ok. I will work on that. A quick explanation is somewhat like this:
"""
The algorithm implements a simple stable topological sort.
The algorithm is expected to be fast and break cycles in a reasonable
way. If there are no cycles, it does a plain topological sort, that
does not reorder the input, that is, it is stable.
Every link_map instance has a l_idx field, that in special cases,
currently only when a DSO is being unloaded, can be less than zero.
If the l_idx is not less than zero, and not in the dl_sort_fini call
that already initializes the l_idx entries, the sort function initializes
the l_idx field of every link_map pointer to an unique identifier.
The sort is done in-place, by decrementing the insert position (the
"k" variable) in the maps vector. Sorting is done by swapping an entry
with the current insert position, and decrementing the insert position.
The "sort" function allocates in the stack the "seen" vector, that
works as a boolean flag for every link_map, to know if it has been
already moved. Moving, actually swapping, is done at most once, and not
done if it is already in the proper position.
The "sort" function also allocates in stack the "w" vector, that
is a counter of how many, not self and not already "seen" direct
references exist to a link_map entry.
The "weight" function resets the "w" entries at every call. Note
that other than the first call, every call reduces the number of
entries by one, as the last moved link_map pointer does not need
to be verified again.
In the "weight" function, once a link_map entry l_initfini vector
does not find any dependency, either the entry is a self dependency,
the object is being unloaded or the dependency has been moved
(in which case a cyclic dependency was just broken), the "w" entry
for it will be 0.
Note that the "w" vector is indexed by position in the input/output
maps vector, while the "seen" vector is indexed by the "l_idx" field
of the "struct link_map" representing the DSO.
Every loop, after calling the "weight" function, the "sort" searches
all "w" entries for the first entry matching the "c" variable. The "c"
variable is initialized as zero, and reset to zero after an entry
is moved. If it scans all "w" entries and none is equal to "c", it
increments "c"; if "c" is larger than zero it means there is a loop,
in which case it chooses the first one with the lowest weight.
Once an entry is moved, it is marked as "seen", and if it was
part of a cycle, the cycle is now broken, as it will no longer
influence its direct dependencies.
Recognized possible problems:
o The algorithm is not expected to scale well beyond a few thousand
entries, due to the need to reinitialize the "w" vector.
o If there are multiple "solutions", it will frequently not match
sorting done by the previous algorithm. But, it guarantees an
stable sorting, that is, does not change input order.
o It does not attempt to be smart when finding loops, a better solution
probably would be to break the smallest loop first, when there are
multiple entries with the same weight, instead of choosing the first
entry.
"""
> * Tests. The existing set of tests are insufficient to cover the changes you
> are proposing. While it seems unfair, and I understand that, this kind of
> change has not been undertaken because of the lack of testing. You need to
> add more tests. The *best* testing is actually a test which
> deterministically generates a sequence of permutations of linked objects and
> verifies they are sorted correctly by the algorithms in question. This way
> we can show that the sorting works for a large set of object dependency
> orderings. When we get a bug report, and we will, we can enlarge the set of
> automated testing to include the case the bug report claims and see what
> went wrong.
I will work on test cases. So far my tests were glibc "make check" and
running rawhide and rhel-7 with the patch. I am particularly interested
in knowing if there is a test case for this commit:
https://sourceware.org/git/?p=glibc.git;a=blame;f=elf/dl-fini.c;h=c35577565eb66ac241365c05efe7c7fb791e0df2#l102
line 102, because it is another special variant of the loop, and what I
did to address it is to loop over the entries, and increase the "w"
vector of the dependencies, to ensure the dependencies are not moved
before the entry, but on very complex cycles, and if having conflicting
rules, it cannot guarantee it will really " preserve a link time dependency".
But I suspect the same is true for the current algorithm; worse if the
link time dependencies generate conflicting dependencies in cycles.
> If you can cover those two things, then you're ready to post the patch to
> libc-alpha for more formal review.
Ok. I followed wiki instructions and sent the first version to
libc-alpha, but will now wait for a more concrete situation based
on bugzilla.
> This looks really good though and you're making great progress in a
> difficult part of the dynamic loader.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (4 preceding siblings ...)
2014-11-26 21:56 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2014-11-28 15:51 ` carlos at redhat dot com
2014-11-29 22:30 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (17 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: carlos at redhat dot com @ 2014-11-28 15:51 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #6 from Carlos O'Donell <carlos at redhat dot com> ---
> > If you can cover those two things, then you're ready to post the patch to
> > libc-alpha for more formal review.
>
> Ok. I followed wiki instructions and sent the first version to
> libc-alpha, but will now wait for a more concrete situation based
> on bugzilla.
There is nothing wrong with what you did, but you are unlikely to get serious
review until your patch has the kind of quality expected by libc-alpha.
You are making great progress here though, and I appreciate your efforts. It's
not easy to make changes to core runtimes, and as a community we try to hold
ourselves to a high standard.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (5 preceding siblings ...)
2014-11-28 15:51 ` carlos at redhat dot com
@ 2014-11-29 22:30 ` paulo.cesar.pereira.de.andrade at gmail dot com
2015-03-17 22:50 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (16 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2014-11-29 22:30 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #7 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 7977
--> https://sourceware.org/bugzilla/attachment.cgi?id=7977&action=edit
Scratch test case
Carlos, I would appreciate any comments about the scratch test
case as well as suggestions about other patterns to test. There
is a detailed description on how to run the tests in the README
file.
For a quick visualization, the tests with different solutions
(due to cycles or multiple dsos without dependencies) are like
this, (old) means current glibc, (new) means with the proposed
patch:
a -> b
b -> c
c ->
d ->
link old new
------------------------------
abcd dcba_abcd cbad_abcd
abdc cdba_abdc dcba_abdc
acbd dcba_abcd cdba_abcd
acdb cbda_adbc cbad_adbc
adbc cbda_adbc dcba_adbc
adcb cbda_adbc dcba_abcd
bacd dcba_abcd cbda_abcd
badc cdba_abdc dcba_abdc
bcad dcba_abcd cbad_abcd
bcda cbad_dabc cbda_dabc
bdac cbad_dabc dcba_dabc
bdca cbad_dabc dcba_abcd
cabd dcba_abcd cdba_abcd
cadb cbda_adbc cbda_dabc
cbad dcba_abcd cdba_abcd
cbda cbad_dabc cbad_abdc
cdab cbad_dabc cbad_adbc
cdba cbad_dabc cdba_dabc
dabc cbad_dabc dcba_dabc
dacb cbad_dabc dcba_abcd
dbac cbad_dabc dcba_abdc
dbca cbad_dabc dcba_abcd
dcab cbad_dabc dcba_abcd
dcba cbad_dabc dcba_abcd
A -> B
B -> C
C -> D
D -> A
link old new
------------------------------
ABCD DCBA_ABCD ADCB_ABCD
ABDC DCBA_ABCD ADCB_DABC
ACBD BADC_CDAB ADCB_ABCD
ACDB DCBA_ABCD ADCB_CDAB
ADBC DCBA_ABCD ADCB_DABC
ADCB DCBA_ABCD ADCB_CDAB
BACD ADCB_BCDA BADC_ABCD
BADC ADCB_BCDA BADC_DABC
BCAD ADCB_BCDA BADC_ABCD
BCDA ADCB_BCDA BADC_BCDA
BDAC ADCB_BCDA BADC_DABC
BDCA CBAD_DABC BADC_BCDA
CABD BADC_CDAB CBAD_ABCD
CADB DCBA_ABCD CBAD_CDAB
CBAD BADC_CDAB CBAD_ABCD
CBDA BADC_CDAB CBAD_BCDA
CDAB BADC_CDAB CBAD_CDAB
CDBA BADC_CDAB CBAD_BCDA
DABC CBAD_DABC DCBA_DABC
DACB CBAD_DABC DCBA_CDAB
DBAC ADCB_BCDA DCBA_DABC
DBCA CBAD_DABC DCBA_BCDA
DCAB CBAD_DABC DCBA_CDAB
DCBA CBAD_DABC DCBA_BCDA
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (6 preceding siblings ...)
2014-11-29 22:30 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2015-03-17 22:50 ` paulo.cesar.pereira.de.andrade at gmail dot com
2015-03-18 17:21 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (15 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2015-03-17 22:50 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #7972|0 |1
is obsolete| |
--- Comment #8 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8193
--> https://sourceware.org/bugzilla/attachment.cgi?id=8193&action=edit
Proposed patch
Updated proposed patch, without ChangeLog entry,
just for asking for extra comments.
I understand this patch touches a too sensible
part of glibc, and the only reason I wrote it is
due to the test case, where the proposed patch
runs 5+ orders of magnitude faster, and appears to
be fully functional, when tested in fedora and
running very complex applications.
This is basically the same patch, but now it scans
the list in reverse order. This is is actually the
correct way to do it, so that on most common/simple
cases/cycles it outputs the same sorting as current
glibc.
But I would like to have one clarification, that maybe
is being already tested, and the Makefile patch to
have only one result is in fault.
tst-initorder is basically this:
a2 a1 # a2 is linked to a1
b2 b1 a2 # b2 is linked to b1 and a2
a3 b2 b1 # a3 is linked to b2 and b1
a4 a3 # a4 is linked to a3
main a4 a1 b2 # "main" is linked to a4, a1 and b2
this will cause the sort input like this:
[ main a2 a1 b2 b1 a3 a4 ]
My question is, is some documentation that says
that dsos must be kept together in the ordering?
I mean, there are 2 correct results:
main a4 a3 b2 b1 a2 a1
and
main a4 a3 b2 a2 a1 b1
but if there is some specification that says
it should have "b2 b1" together, then the patch
is invalid, because it only breaks cycles and
does ordering, and if there are no dependencies,
it keeps it in the order it received the list
to sort.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (7 preceding siblings ...)
2015-03-17 22:50 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2015-03-18 17:21 ` paulo.cesar.pereira.de.andrade at gmail dot com
2015-03-18 17:26 ` paulo.cesar.pereira.de.andrade at gmail dot com
` (14 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2015-03-18 17:21 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #9 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8194
--> https://sourceware.org/bugzilla/attachment.cgi?id=8194&action=edit
dso_deps.c - simple test implementing standalone propose sort and current glibc
Compile it as gcc -O0 -g3 dso_deps.c -o dso_deps
It accepts a very simple grammar input file, it
outputs "ORG: ..." to show how input was given,
"NEW: ..." as how the proposed patch would sort
it, and "CUR: ..." as the result of current
glibc sort. For example:
---8<---
$ cat dso_1
a b c
b c
c a
$ ./dso_deps -v dso_1
a(b c)
b(c)
c(a)
ORG: a b c
NEW: a b c
Real time: 4e-06 sec
CUR: a b c
Real time: 5e-06 sec
$ cat dso_2
a b c
d
e f
b c d e
$ ./dso_deps -v dso_2
a(b c)
b(c d e)
c()
d()
e(f)
f()
ORG: a b c d e f
NEW: a b c d e f
Real time: 5e-06 sec
CUR: a b c d e f
Real time: 3e-06 sec
$ cat dso_4
a b
b c
c d
d e
e f
$ ./dso_deps -v dso_4
a(b)
b(c)
c(d)
d(e)
e(f)
f()
ORG: a b c d e f
NEW: a b c d e f
Real time: 5e-06 sec
CUR: a b c d e f
Real time: 3e-06 sec
$ cat dso_5
b a
c b
d c
e d
f e
$ ./dso_deps -v dso_5
b(a)
a()
c(b)
d(c)
e(d)
f(e)
ORG: b a c d e f
NEW: f e d c b a
Real time: 5e-06 sec
CUR: f e d c b a
Real time: 6e-06 sec
---8<---
This is an example matching the current glibc build
time test, and that the proposed patch has a different
result from current glibc:
---8<---
$ cat dso_6
a2 a1
b2 b1 a2
a3 b2 b1
a4 a3
main a4 a1 b2
$ ./dso_deps -v dso_6
a2(a1)
a1()
b2(b1 a2)
b1()
a3(b2 b1)
a4(a3)
main(a4 a1 b2)
ORG: a2 a1 b2 b1 a3 a4 main
NEW: main a4 a3 b2 a2 a1 b1
Real time: 6e-06 sec
CUR: main a4 a3 b2 b1 a2 a1
Real time: 7e-06 sec
---8<---
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (8 preceding siblings ...)
2015-03-18 17:21 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2015-03-18 17:26 ` paulo.cesar.pereira.de.andrade at gmail dot com
2020-05-06 16:30 ` romain.geissler at amadeus dot com
` (13 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: paulo.cesar.pereira.de.andrade at gmail dot com @ 2015-03-18 17:26 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #10 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8195
--> https://sourceware.org/bugzilla/attachment.cgi?id=8195&action=edit
dso_3 - Sample input for previous test case, that summarizes the reason of the
bug report
Since output is quite large, just showing the time result.
If built in "debug mode", -O0 -g3:
NEW: Real time: 0.004542 sec
CUR: Real time: 62.1445 sec
If built more close to default glibc, -O3:
NEW: Real time: 0.001232 sec
CUR: Real time: 22.4437 sec
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (9 preceding siblings ...)
2015-03-18 17:26 ` paulo.cesar.pereira.de.andrade at gmail dot com
@ 2020-05-06 16:30 ` romain.geissler at amadeus dot com
2020-05-06 16:54 ` carlos at redhat dot com
` (12 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: romain.geissler at amadeus dot com @ 2020-05-06 16:30 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #13 from Romain Geissler <romain.geissler at amadeus dot com> ---
Hi,
As far as I understand, a patch to fix this bug (and the ones related 15310 and
15311) has been posted on the list last summer:
- The testing framework (which was the reason all past attempt did not
eventually got merged):
https://sourceware.org/pipermail/libc-alpha/2019-July/105199.html
- the actual patch:
https://sourceware.org/pipermail/libc-alpha/2019-July/105200.html
Carlos, I also understood that back then during the 2.31 release period, at
some point you did consider these patches for a review, and potentially a merge
into 2.31. It looks like you lacked time to review this. May I gently ping this
patch for a review again ?
Thanks,
Romain
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (10 preceding siblings ...)
2020-05-06 16:30 ` romain.geissler at amadeus dot com
@ 2020-05-06 16:54 ` carlos at redhat dot com
2020-07-03 16:18 ` carlos at redhat dot com
` (11 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: carlos at redhat dot com @ 2020-05-06 16:54 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #14 from Carlos O'Donell <carlos at redhat dot com> ---
(In reply to Romain Geissler from comment #13)
> Hi,
>
> As far as I understand, a patch to fix this bug (and the ones related 15310
> and 15311) has been posted on the list last summer:
> - The testing framework (which was the reason all past attempt did not
> eventually got merged):
> https://sourceware.org/pipermail/libc-alpha/2019-July/105199.html
> - the actual patch:
> https://sourceware.org/pipermail/libc-alpha/2019-July/105200.html
>
> Carlos, I also understood that back then during the 2.31 release period, at
> some point you did consider these patches for a review, and potentially a
> merge into 2.31. It looks like you lacked time to review this. May I gently
> ping this patch for a review again ?
I reviewed the patches from Chung-Ling Tang here:
https://sourceware.org/pipermail/libc-alpha/2019-December/109676.html
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (11 preceding siblings ...)
2020-05-06 16:54 ` carlos at redhat dot com
@ 2020-07-03 16:18 ` carlos at redhat dot com
2020-07-03 16:18 ` carlos at redhat dot com
` (10 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: carlos at redhat dot com @ 2020-07-03 16:18 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #15 from Carlos O'Donell <carlos at redhat dot com> ---
Reviewed v2.1:
https://sourceware.org/pipermail/libc-alpha/2020-June/115184.html
https://sourceware.org/pipermail/libc-alpha/2020-June/115538.html
Looking like we're almost done, but a few design points need ironing out.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (12 preceding siblings ...)
2020-07-03 16:18 ` carlos at redhat dot com
@ 2020-07-03 16:18 ` carlos at redhat dot com
2020-07-21 14:48 ` s at martinien dot de
` (9 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: carlos at redhat dot com @ 2020-07-03 16:18 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Carlos O'Donell <carlos at redhat dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |andrewjcg at gmail dot com
--- Comment #16 from Carlos O'Donell <carlos at redhat dot com> ---
*** Bug 26179 has been marked as a duplicate of this bug. ***
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (13 preceding siblings ...)
2020-07-03 16:18 ` carlos at redhat dot com
@ 2020-07-21 14:48 ` s at martinien dot de
2020-12-27 18:31 ` romain.geissler at amadeus dot com
` (8 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: s at martinien dot de @ 2020-07-21 14:48 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Martin Richtarsky <s at martinien dot de> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |s at martinien dot de
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (14 preceding siblings ...)
2020-07-21 14:48 ` s at martinien dot de
@ 2020-12-27 18:31 ` romain.geissler at amadeus dot com
2020-12-27 18:33 ` romain.geissler at amadeus dot com
` (7 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: romain.geissler at amadeus dot com @ 2020-12-27 18:31 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #17 from Romain Geissler <romain.geissler at amadeus dot com> ---
Created attachment 13079
--> https://sourceware.org/bugzilla/attachment.cgi?id=13079&action=edit
Proposed patch v3 updated to master branch as of 27th december 2020
Proposed patch v3 written by Chung-Lin Tang and posted in
https://sourceware.org/pipermail/libc-alpha/2020-July/116546.html, updated to
master branch as of 27th december 2020
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (15 preceding siblings ...)
2020-12-27 18:31 ` romain.geissler at amadeus dot com
@ 2020-12-27 18:33 ` romain.geissler at amadeus dot com
2021-03-03 22:29 ` san+sourceware at smederijmerlijn dot nl
` (6 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: romain.geissler at amadeus dot com @ 2020-12-27 18:33 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #18 from Romain Geissler <romain.geissler at amadeus dot com> ---
Hi,
I am not sure if this proposed patch is still being considered for eventual
review/merge.
Anyway, in comment #17 is an updated version of the version 3 patch written by
Chung-Lin Tang and posted on the mailing list here:
https://sourceware.org/pipermail/libc-alpha/2020-July/116546.html (only the
part of the patch adding the code, *NOT* the part of the patch updating the
test suite), as what was posted in July doesn't apply cleanly anymore.
Cheers,
Romain
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (16 preceding siblings ...)
2020-12-27 18:33 ` romain.geissler at amadeus dot com
@ 2021-03-03 22:29 ` san+sourceware at smederijmerlijn dot nl
2021-04-01 21:16 ` hi-angel at yandex dot ru
` (5 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: san+sourceware at smederijmerlijn dot nl @ 2021-03-03 22:29 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
.san <san+sourceware at smederijmerlijn dot nl> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |san+sourceware@smederijmerl
| |ijn.nl
--- Comment #19 from .san <san+sourceware at smederijmerlijn dot nl> ---
Hi all,
It is probably not common knowledge that the Unreal Engine 4, a popular and
very advanced real-time 3D creation tool used for game and other real-time
rendering applications, is affected by the behavior described in this ticket.
The patches, version 4, as provided by Chung-Lin Tang reduce the startup time
of UE4 from 200+ seconds to ~15 seconds.
Not sure if it should affect the priority on this ticket but I wanted to let
you all know that there are real world examples of this issue and having a fix
out would be a very significant improvement for Game Developers on Linux.
Considering an opt-in behavior change, toggle-able with an global/environment
variable, would allow us devs to use upstream glibc again.
Cheers!
.san
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (17 preceding siblings ...)
2021-03-03 22:29 ` san+sourceware at smederijmerlijn dot nl
@ 2021-04-01 21:16 ` hi-angel at yandex dot ru
2021-07-06 11:08 ` marat at slonopotamus dot org
` (4 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: hi-angel at yandex dot ru @ 2021-04-01 21:16 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Hi-Angel <hi-angel at yandex dot ru> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |hi-angel at yandex dot ru
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (18 preceding siblings ...)
2021-04-01 21:16 ` hi-angel at yandex dot ru
@ 2021-07-06 11:08 ` marat at slonopotamus dot org
2021-08-10 13:03 ` romain.geissler at amadeus dot com
` (3 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: marat at slonopotamus dot org @ 2021-07-06 11:08 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #20 from Marat Radchenko <marat at slonopotamus dot org> ---
It looks like Chung-Lin Tang patch (that is currently at V5) got stuck again:
https://patchwork.sourceware.org/project/glibc/list/?q=17645
Meanwhile, there now exist several unofficial sources that provide patched
glibc:
For Arch Linux: https://aur.archlinux.org/packages/glibc-dso/
For Ubuntu Linux: https://launchpad.net/~slonopotamus/+archive/ubuntu/glibc-dso
Gentoo Linux users just put patches into /etc/portage/patches/sys-libs/glibc/
and rebuild glibc.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (19 preceding siblings ...)
2021-07-06 11:08 ` marat at slonopotamus dot org
@ 2021-08-10 13:03 ` romain.geissler at amadeus dot com
2021-10-21 19:21 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
23 siblings, 0 replies; 25+ messages in thread
From: romain.geissler at amadeus dot com @ 2021-08-10 13:03 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #21 from Romain Geissler <romain.geissler at amadeus dot com> ---
Hi,
As stated some months ago on the list, we are using this patch (an earlier
version) in our own glibc and we need that for some specific production
workloads. We will upgrade to the latest patch version with the move to glibc
2.34.
I hope Florian/Carlos will have the time to do another round of review with the
latest v6 patch before the release of glibc 2.35 ;)
Cheers,
Romain
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (20 preceding siblings ...)
2021-08-10 13:03 ` romain.geissler at amadeus dot com
@ 2021-10-21 19:21 ` cvs-commit at gcc dot gnu.org
2021-10-21 19:23 ` adhemerval.zanella at linaro dot org
2023-11-24 7:24 ` fweimer at redhat dot com
23 siblings, 0 replies; 25+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-10-21 19:21 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
--- Comment #22 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Adhemerval Zanella
<azanella@sourceware.org>:
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=e6fd79f3795d46dfb583e124be49fc063bc3d58b
commit e6fd79f3795d46dfb583e124be49fc063bc3d58b
Author: Chung-Lin Tang <cltang@codesourcery.com>
Date: Thu Oct 21 21:41:21 2021 +0800
elf: Testing infrastructure for ld.so DSO sorting (BZ #17645)
This is the first of a 2-part patch set that fixes slow DSO sorting
behavior in
the dynamic loader, as reported in BZ #17645. In order to facilitate such a
large modification to the dynamic loader, this first patch implements a
testing
framework for validating shared object sorting behavior, to enable
comparison
between old/new sorting algorithms, and any later enhancements.
This testing infrastructure consists of a Python script
scripts/dso-ordering-test.py' which takes in a description language,
consisting
of strings that describe a set of link dependency relations between DSOs,
and
generates testcase programs and Makefile fragments to automatically test
the
described situation, for example:
a->b->c->d # four objects linked one after another
a->[bc]->d;b->c # a depends on b and c, which both depend on d,
# b depends on c (b,c linked to object a in fixed
order)
a->b->c;{+a;%a;-a} # a, b, c serially dependent, main program uses
# dlopen/dlsym/dlclose on object a
a->b->c;{}!->[abc] # a, b, c serially dependent; multiple tests
generated
# to test all permutations of a, b, c ordering linked
# to main program
(Above is just a short description of what the script can do, more
documentation is in the script comments.)
Two files containing several new tests, elf/dso-sort-tests-[12].def are
added,
including test scenarios for BZ #15311 and Redhat issue #1162810 [1].
Due to the nature of dynamic loader tests, where the sorting behavior and
test
output occurs before/after main(), generating testcases to use
support/test-driver.c does not suffice to control meaningful timeout for
ld.so.
Therefore a new utility program 'support/test-run-command', based on
test-driver.c/support_test_main.c has been added. This does the same
testcase
control, but for a program specified through a command-line rather than at
the
source code level. This utility is used to run the dynamic loader testcases
generated by dso-ordering-test.py.
[1] https://bugzilla.redhat.com/show_bug.cgi?id=1162810
Signed-off-by: Chung-Lin Tang <cltang@codesourcery.com>
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (21 preceding siblings ...)
2021-10-21 19:21 ` cvs-commit at gcc dot gnu.org
@ 2021-10-21 19:23 ` adhemerval.zanella at linaro dot org
2023-11-24 7:24 ` fweimer at redhat dot com
23 siblings, 0 replies; 25+ messages in thread
From: adhemerval.zanella at linaro dot org @ 2021-10-21 19:23 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Adhemerval Zanella <adhemerval.zanella at linaro dot org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |2.35
Resolution|--- |FIXED
Status|NEW |RESOLVED
CC| |adhemerval.zanella at linaro dot o
| |rg
--- Comment #23 from Adhemerval Zanella <adhemerval.zanella at linaro dot org> ---
A new algorithm based on topologic sort has been added on master
(15a0c5730d1d5aeb95f50c9ec7470640084feae8) and it can be selected throug a new
tunable (glibc.rtld.dynamic_sort). I will close this task and coordenate
upstream when and how to move to this algorithm as the default one.
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.
2014-11-25 13:37 [Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies paulo.cesar.pereira.de.andrade at gmail dot com
` (22 preceding siblings ...)
2021-10-21 19:23 ` adhemerval.zanella at linaro dot org
@ 2023-11-24 7:24 ` fweimer at redhat dot com
23 siblings, 0 replies; 25+ messages in thread
From: fweimer at redhat dot com @ 2023-11-24 7:24 UTC (permalink / raw)
To: glibc-bugs
https://sourceware.org/bugzilla/show_bug.cgi?id=17645
Florian Weimer <fweimer at redhat dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://sourceware.org/bugz
| |illa/show_bug.cgi?id=31083
--
You are receiving this mail because:
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 25+ messages in thread