[Bug dynamic-link/17645] New: RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[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]

https://sourceware.org/bugzilla/show_bug.cgi?id=17645

            Bug ID: 17645
           Summary: RFE: Improve performance of dynamic loader for deeply
                    nested DSO dependencies.
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: dynamic-link
          Assignee: unassigned at sourceware dot org
          Reporter: paulo.cesar.pereira.de.andrade at gmail dot com

Created attachment 7970
  --> https://sourceware.org/bugzilla/attachment.cgi?id=7970&action=edit
Sample "redistributable" test case provided by a customer

After glibc-2.11, there are 3 slightly different instances
of a very CPU intensive loop in elf/dl-deps.c, elf/dl-fini.c
and elf/dl-open.c. The loop does not scale well when there
are cyclic dependencies, and may take more than 8 seconds
to sort less than 300 shared objects when there a some
cycles. Most of the time is spent in memmove.

Sample perf output of it taking 8+ secs on a core i5:

 31,24%  timedlopen  ld-2.17.so         [.] _dl_map_object_deps
 18,36%  timedlopen  ld-2.17.so         [.] _wordcopy_fwd_aligned
 16,50%  timedlopen  ld-2.17.so         [.] _dl_sort_fini
 15,47%  timedlopen  ld-2.17.so         [.] dl_open_worker
 13,08%  timedlopen  ld-2.17.so         [.] _wordcopy_fwd_dest_aligned
  4,95%  timedlopen  ld-2.17.so         [.] memmove
  0,07%  timedlopen  ld-2.17.so         [.] do_lookup_x

I have been using a patch for some weeks in rhel-6.3
(for basic tests where the problem was detected/reported),
and my day to day computers, running rhel-7 and fedora
rawhide, and cannot see any problems running kde, gnome,
libreoffice and several other large applications or
environments that load/unload or have large dso dependency
chains.

The proposed patch runs the test case in 10 ms, and a
sample perf output is:

 17,45%  timedlopen  ld-2.17.so         [.] do_lookup_x
  9,54%  timedlopen  ld-2.17.so         [.] strcmp
  6,91%  timedlopen  ld-2.17.so         [.] _dl_map_object_deps
  6,12%  timedlopen  ld-2.17.so         [.] _dl_name_match_p
  4,35%  timedlopen  ld-2.17.so         [.] _dl_sort_fini
  4,33%  timedlopen  ld-2.17.so         [.] dl_open_worker

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[carlos at redhat dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[carlos at redhat dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[paulo.cesar.pereira.de.andrade at gmail dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[romain.geissler at amadeus dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[carlos at redhat dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[carlos at redhat dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[carlos at redhat dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[s at martinien dot de]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[romain.geissler at amadeus dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[romain.geissler at amadeus dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[san+sourceware at smederijmerlijn dot nl]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[hi-angel at yandex dot ru]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[marat at slonopotamus dot org]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[romain.geissler at amadeus dot com]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[cvs-commit at gcc dot gnu.org]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[adhemerval.zanella at linaro dot org]

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.

[Bug dynamic-link/17645] RFE: Improve performance of dynamic loader for deeply nested DSO dependencies.

[fweimer at redhat dot com]

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.