summarylogtreecommitdiffstats
diff options
context:
space:
mode:
authorMilan Stastny2021-12-12 13:58:33 +0100
committerMilan Stastny2021-12-12 13:58:33 +0100
commitb10b1148ceeb738e85727f1db503f9e61c0adf8d (patch)
tree4a4c9885cc44bb0839841f8f3eb1920e585a2680
parente2bbf6a1fc9d9c280f575d302b6a07bd5f97ed16 (diff)
downloadaur-b10b1148ceeb738e85727f1db503f9e61c0adf8d.tar.gz
Update to the final patch
Diffstat
-rw-r--r--.SRCINFO10
-rw-r--r--PKGBUILD14
-rw-r--r--v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch (renamed from v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch)152
-rw-r--r--v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch (renamed from v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch)183
4 files changed, 233 insertions, 126 deletions
diff --git a/.SRCINFO b/.SRCINFO
index de27adb53f58..51ba73b21e6f 100644
--- a/.SRCINFO
+++ b/.SRCINFO
@@ -1,6 +1,6 @@
pkgbase = glibc-dso
pkgver = 2.33
- pkgrel = 8
+ pkgrel = 9
url = https://www.gnu.org/software/libc
arch = x86_64
license = GPL
@@ -24,8 +24,8 @@ pkgbase = glibc-dso
source = 0001-nptl_db-Support-different-libpthread-ld.so-load-orde.patch
source = 0002-nptl-Check-for-compatible-GDB-in-nptl-tst-pthread-gd.patch
source = 0003-nptl-Do-not-build-nptl-tst-pthread-gdb-attach-as-PIE.patch
- source = v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
- source = v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
+ source = v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
+ source = v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
validpgpkeys = 7273542B39962DF7B299931416792B4EA25340F8
validpgpkeys = BC7C7372637EC10C57D7AA6579C43DFBF1CF2187
md5sums = 390bbd889c7e8e8a7041564cb6b27cca
@@ -39,8 +39,8 @@ pkgbase = glibc-dso
md5sums = 78f041fc66fee4ee372f13b00a99ff72
md5sums = 9e418efa189c20053e887398df2253cf
md5sums = 7a09f1693613897add1791e7aead19c9
- md5sums = c553dbe5e7ae410629ca068d43ab7ebf
- md5sums = b83e5a982dc5ec58c69e30672ca903fe
+ md5sums = 5974b86859dd65c7cfda756a8b2445c2
+ md5sums = 26a619a810de7d296608cc78377bc27c
pkgname = glibc-dso
pkgdesc = GNU C Library - DSO patch
diff --git a/PKGBUILD b/PKGBUILD
index 7b941f1767cf..a830e7b6788c 100644
--- a/PKGBUILD
+++ b/PKGBUILD
@@ -6,7 +6,7 @@
pkgbase=glibc-dso
pkgname=(glibc-dso lib32-glibc-dso)
pkgver=2.33
-pkgrel=8
+pkgrel=9
arch=(x86_64)
url='https://www.gnu.org/software/libc'
license=(GPL LGPL)
@@ -24,8 +24,8 @@ source=(https://ftp.gnu.org/gnu/glibc/glibc-$pkgver.tar.xz{,.sig}
0001-nptl_db-Support-different-libpthread-ld.so-load-orde.patch
0002-nptl-Check-for-compatible-GDB-in-nptl-tst-pthread-gd.patch
0003-nptl-Do-not-build-nptl-tst-pthread-gdb-attach-as-PIE.patch
- v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
- v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch)
+ v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
+ v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch)
validpgpkeys=(7273542B39962DF7B299931416792B4EA25340F8 # Carlos O'Donell
BC7C7372637EC10C57D7AA6579C43DFBF1CF2187) # Siddhesh Poyarekar
md5sums=('390bbd889c7e8e8a7041564cb6b27cca'
@@ -39,8 +39,8 @@ md5sums=('390bbd889c7e8e8a7041564cb6b27cca'
'78f041fc66fee4ee372f13b00a99ff72'
'9e418efa189c20053e887398df2253cf'
'7a09f1693613897add1791e7aead19c9'
- 'c553dbe5e7ae410629ca068d43ab7ebf'
- 'b83e5a982dc5ec58c69e30672ca903fe')
+ '5974b86859dd65c7cfda756a8b2445c2'
+ '26a619a810de7d296608cc78377bc27c')
prepare() {
mkdir -p glibc-build lib32-glibc-build
@@ -59,8 +59,8 @@ prepare() {
# nptl: Do not build nptl/tst-pthread-gdb-attach as PIE
patch -p1 -i "$srcdir"/0003-nptl-Do-not-build-nptl-tst-pthread-gdb-attach-as-PIE.patch
- patch -p1 -i "$srcdir"/v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
- patch -p1 -i "$srcdir"/v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
+ patch -p1 -i "$srcdir"/v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
+ patch -p1 -i "$srcdir"/v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
}
build() {
diff --git a/v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch b/v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
index 7b241a485933..82431bea85a3 100644
--- a/v6-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
+++ b/v8-1-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Testing-infrastructure.patch
@@ -1,8 +1,8 @@
diff --git a/elf/Makefile b/elf/Makefile
-index 4fe60947ad..fe7a8b418f 100644
+index bf45d8ee24..bdcf4cb885 100644
--- a/elf/Makefile
+++ b/elf/Makefile
-@@ -469,6 +469,21 @@ tests-special += $(objpfx)order-cmp.out $(objpfx)tst-array1-cmp.out \
+@@ -477,6 +477,21 @@ tests-special += $(objpfx)order-cmp.out $(objpfx)tst-array1-cmp.out \
$(objpfx)tst-unused-dep-cmp.out
endif
@@ -26,10 +26,10 @@ index 4fe60947ad..fe7a8b418f 100644
update-abi: update-abi-ld
diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def
new file mode 100644
-index 0000000000..51f1d2e158
+index 0000000000..873ddf55d9
--- /dev/null
+++ b/elf/dso-sort-tests-1.def
-@@ -0,0 +1,66 @@
+@@ -0,0 +1,66 @@
+# DSO sorting test descriptions.
+# This file is to be processed by ../scripts/dso-ordering-test.py, see usage
+# in elf/Makefile for how it is executed.
@@ -69,7 +69,7 @@ index 0000000000..51f1d2e158
+output: f>e>d>c>b>a>{}<a<b<c<d<e<f
+
+# Sequence where the DSO c is unerlinked and calls a function in DSO a which
-+# is technically a cycle. The main executable depends on the first two DSOs.
++# is technically a cycle. The main executable depends on the first two DSOs.
+# Note: This test has unspecified behavior.
+tst-dso-ordering8: a->b->c=>a;{}->[ba]
+output: c>b>a>{}<a<b<c
@@ -94,19 +94,19 @@ index 0000000000..51f1d2e158
+# The below expected outputs are what the two algorithms currently produce
+# respectively, for regression testing purposes.
+tst-bz15311: {+a;+e;+f;+g;+d;%d;-d;-g;-f;-e;-a};a->b->c->d;d=>[ba];c=>a;b=>e=>a;c=>f=>b;d=>g=>c
-+output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<a<c<d<g<f<b<e];}
++xfail_output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<a<c<d<g<f<b<e];}
+output(glibc.rtld.dynamic_sort=2): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<g<f<a<b<c<d<e];}
diff --git a/elf/dso-sort-tests-2.def b/elf/dso-sort-tests-2.def
new file mode 100644
-index 0000000000..865f57be04
+index 0000000000..b79e79ecb7
--- /dev/null
+++ b/elf/dso-sort-tests-2.def
-@@ -0,0 +1,614 @@
+@@ -0,0 +1,614 @@
+# Large DSO sorting testcase adapted from Red Hat Bugzilla 1162810
+#
+# Note that below we specify different expected outputs between dynamic_sort=1
+# and dynamic_sort=2 algorithms, due to circular dependencies in the testcase
-+# causing different sorting behavior. These expected outputs are what the two
++# causing different sorting behavior. These expected outputs are what the two
+# algorithms currently produce, and are used for regression comparison tests.
+# They are not "definitively" correct outputs, for circular dependencies
+# inherently have unspecified behavior.
@@ -718,10 +718,10 @@ index 0000000000..865f57be04
+output(glibc.rtld.dynamic_sort=2): M30X19>M30X15>M30X16>M30X11>M30X12>M30X17>M30X13>M30X14>M29X20>M30X23>M30X24>M30X20>M30X18>M29X15>M29X12>M30X22>M30X21>M29X22>M30X25>M29X19>M29X23>M29X16>M29X24>M29X13>M29X17>M29X18>M28X19>M29X21>M29X25>M29X14>M28X20>M28X15>M28X16>M28X21>M27X18>M29X11>M28X17>M28X11>M28X22>M28X24>M28X23>M27X21>M28X13>M27X20>M27X19>M26X14>M27X25>M28X18>M27X11>M28X25>M27X24>M26X24>M27X15>M27X14>M27X13>M26X23>M27X17>M26X22>M25X13>M28X14>M27X16>M26X19>M26X18>M27X23>M27X22>M26X17>M25X18>M26X21>M25X17>M26X20>M26X15>M26X13>M25X19>M24X14>M25X23>M26X11>M26X25>M25X16>M25X15>M24X22>M25X21>M25X20>M24X21>M25X25>M25X24>M24X20>M23X13>M22X15>M25X14>M24X19>M23X17>M24X25>M23X24>M24X13>M23X15>M24X18>M23X14>M22X11>M24X15>M23X22>M24X11>M23X19>M22X21>M24X24>M23X21>M22X20>M23X25>M22X19>M21X24>M20X23>M22X22>M25X11>M23X16>M22X18>M23X20>M22X17>M21X21>M21X20>M20X24>M22X14>M22X13>M21X11>M21X17>M22X23>M21X16>M20X25>M19X23>M18X16>M21X22>M20X20>M20X19>M21X13>M20X18>M19X13>M21X18>M20X21>M19X24>M18X12>M20X14>M20X13>M22X25>M20X12>M20X15>M19X14>M18X22>M19X18>M20X17>M19X17>M19X16>M18X21>M17X20>M19X19>M18X13>M17X11>M18X17>M19X25>M18X15>M17X25>M18X19>M17X24>M16X19>M15X17>M17X21>M16X24>M18X23>M17X16>M16X25>M19X15>M18X25>M17X23>M16X23>M15X23>M18X14>M17X14>M16X14>M17X18>M16X13>M17X22>M16X12>M15X22>M14X16>M17X12>M16X22>M15X12>M16X11>M15X11>M16X15>M15X25>M14X15>M13X14>M15X18>M16X21>M15X16>M14X21>M15X14>M16X20>M15X13>M14X22>M15X20>M14X20>M13X20>M14X11>M15X19>M14X24>M13X19>M14X13>M13X18>M12X13>M15X24>M14X23>M13X12>M14X12>M13X11>M12X11>M11X11>M21X12>M20X11>M19X11>M18X11>M17X15>M16X18>M14X25>M14X19>M13X24>M13X23>M13X22>M12X12>M22X12>M21X15>M19X22>M18X20>M16X17>M14X14>M24X12>M23X23>M22X16>M21X14>M20X22>M18X24>M16X16>M26X12>M24X16>M23X11>M21X23>M19X20>M17X17>M27X12>M26X16>M25X22>M24X17>M23X18>M21X25>M19X12>M17X19>M15X21>M14X18>M13X13>M23X12>M21X19>M19X21>M17X13>M15X15>M25X12>M24X23>M22X24>M20X16>M18X18>M28X12>A150>C158>B112>A112>C167>B146>A146>C180>B180>A180>C143>B143>A115>C126>B126>A126>C190>B190>A190>C138>B138>A138>C174>B174>A102>C122>B122>A122>C162>B162>A162>C142>B142>A142>C102>B102>A174>C176>B176>A176>C115>B115>A143>C172>B172>A172>C187>B187>A187>C130>B130>A130>C118>B118>A118>C184>B184>A184>C171>B171>A171>C168>B182>A182>C182>B168>A168>C109>B109>A109>C159>B159>A159>C134>B134>A134>C146>B167>A167>C140>B140>A140>C163>B163>A163>C112>B158>A158>C164>B164>A164>C131>B131>A131>C188>B188>A188>C199>B199>A199>C114>B114>A114>C106>B106>A106>C200>B200>A200>C183>B183>A183>C152>B152>A152>C147>B147>A147>C150>B150>A198>C144>B144>A144>C191>B191>A191>C108>B108>A108>C139>B139>A139>C194>B194>A194>C166>B166>A166>C120>B120>A120>C123>B123>A123>C132>B132>A132>C107>B107>A107>C170>B170>A170>C198>B198>A156>C125>B125>A125>C121>B121>A121>C193>B193>A193>C197>B197>A197>C175>B175>A175>C196>B196>A196>C105>B105>A105>C181>B181>A181>C113>B113>A113>C137>B137>A137>C155>B155>A155>C156>B156>A110>C128>B128>A128>C179>B179>A179>C124>B124>A124>C151>B151>A151>C178>B178>A178>C104>B104>A104>C111>B111>A111>C148>B148>A148>C169>B169>A169>C129>B129>A129>C149>B149>A149>C189>B189>A189>C119>B119>A119>C154>B154>A154>C136>B136>A136>C135>B135>A135>C116>B116>A116>C145>B145>A145>C161>B161>A161>C173>B173>A173>C157>B157>A157>C195>B195>A195>C186>B186>A186>C160>B160>A160>C153>B153>A153>C117>B117>A117>C165>B165>A165>C101>B101>A101>C103>B103>A103>C192>B192>A192>C177>B177>A177>C185>B185>A185>C141>B141>A141>C133>B133>A133>C127>B127>A127>C110>B110>M14X17>M13X15>M13X16>M13X17>M12X17>M12X21>M12X25>M12X14>M13X25>M12X15>M13X21>M12X16>M12X18>M12X19>M12X20>M12X22>M12X23>M12X24>M11X25>M11X24>M11X23>M11X22>M11X21>M11X20>M11X19>M11X18>M11X17>M11X16>M11X15>M11X14>M11X13>M11X12>{}<M11X12<M11X13<M11X14<M11X15<M11X16<M11X17<M11X18<M11X19<M11X20<M11X21<M11X22<M11X23<M11X24<M11X25<M12X24<M12X23<M12X22<M12X20<M12X19<M12X18<M12X16<M13X21<M12X15<M13X25<M12X14<M12X25<M12X21<M12X17<M13X17<M13X16<M13X15<M14X17<B110<C110<A127<B127<C127<A133<B133<C133<A141<B141<C141<A185<B185<C185<A177<B177<C177<A192<B192<C192<A103<B103<C103<A101<B101<C101<A165<B165<C165<A117<B117<C117<A153<B153<C153<A160<B160<C160<A186<B186<C186<A195<B195<C195<A157<B157<C157<A173<B173<C173<A161<B161<C161<A145<B145<C145<A116<B116<C116<A135<B135<C135<A136<B136<C136<A154<B154<C154<A119<B119<C119<A189<B189<C189<A149<B149<C149<A129<B129<C129<A169<B169<C169<A148<B148<C148<A111<B111<C111<A104<B104<C104<A178<B178<C178<A151<B151<C151<A124<B124<C124<A179<B179<C179<A128<B128<C128<A110<B156<C156<A155<B155<C155<A137<B137<C137<A113<B113<C113<A181<B181<C181<A105<B105<C105<A196<B196<C196<A175<B175<C175<A197<B197<C197<A193<B193<C193<A121<B121<C121<A125<B125<C125<A156<B198<C198<A170<B170<C170<A107<B107<C107<A132<B132<C132<A123<B123<C123<A120<B120<C120<A166<B166<C166<A194<B194<C194<A139<B139<C139<A108<B108<C108<A191<B191<C191<A144<B144<C144<A198<B150<C150<A147<B147<C147<A152<B152<C152<A183<B183<C183<A200<B200<C200<A106<B106<C106<A114<B114<C114<A199<B199<C199<A188<B188<C188<A131<B131<C131<A164<B164<C164<A158<B158<C112<A163<B163<C163<A140<B140<C140<A167<B167<C146<A134<B134<C134<A159<B159<C159<A109<B109<C109<A168<B168<C182<A182<B182<C168<A171<B171<C171<A184<B184<C184<A118<B118<C118<A130<B130<C130<A187<B187<C187<A172<B172<C172<A143<B115<C115<A176<B176<C176<A174<B102<C102<A142<B142<C142<A162<B162<C162<A122<B122<C122<A102<B174<C174<A138<B138<C138<A190<B190<C190<A126<B126<C126<A115<B143<C143<A180<B180<C180<A146<B146<C167<A112<B112<C158<A150<M28X12<M18X18<M20X16<M22X24<M24X23<M25X12<M15X15<M17X13<M19X21<M21X19<M23X12<M13X13<M14X18<M15X21<M17X19<M19X12<M21X25<M23X18<M24X17<M25X22<M26X16<M27X12<M17X17<M19X20<M21X23<M23X11<M24X16<M26X12<M16X16<M18X24<M20X22<M21X14<M22X16<M23X23<M24X12<M14X14<M16X17<M18X20<M19X22<M21X15<M22X12<M12X12<M13X22<M13X23<M13X24<M14X19<M14X25<M16X18<M17X15<M18X11<M19X11<M20X11<M21X12<M11X11<M12X11<M13X11<M14X12<M13X12<M14X23<M15X24<M12X13<M13X18<M14X13<M13X19<M14X24<M15X19<M14X11<M13X20<M14X20<M15X20<M14X22<M15X13<M16X20<M15X14<M14X21<M15X16<M16X21<M15X18<M13X14<M14X15<M15X25<M16X15<M15X11<M16X11<M15X12<M16X22<M17X12<M14X16<M15X22<M16X12<M17X22<M16X13<M17X18<M16X14<M17X14<M18X14<M15X23<M16X23<M17X23<M18X25<M19X15<M16X25<M17X16<M18X23<M16X24<M17X21<M15X17<M16X19<M17X24<M18X19<M17X25<M18X15<M19X25<M18X17<M17X11<M18X13<M19X19<M17X20<M18X21<M19X16<M19X17<M20X17<M19X18<M18X22<M19X14<M20X15<M20X12<M22X25<M20X13<M20X14<M18X12<M19X24<M20X21<M21X18<M19X13<M20X18<M21X13<M20X19<M20X20<M21X22<M18X16<M19X23<M20X25<M21X16<M22X23<M21X17<M21X11<M22X13<M22X14<M20X24<M21X20<M21X21<M22X17<M23X20<M22X18<M23X16<M25X11<M22X22<M20X23<M21X24<M22X19<M23X25<M22X20<M23X21<M24X24<M22X21<M23X19<M24X11<M23X22<M24X15<M22X11<M23X14<M24X18<M23X15<M24X13<M23X24<M24X25<M23X17<M24X19<M25X14<M22X15<M23X13<M24X20<M25X24<M25X25<M24X21<M25X20<M25X21<M24X22<M25X15<M25X16<M26X25<M26X11<M25X23<M24X14<M25X19<M26X13<M26X15<M26X20<M25X17<M26X21<M25X18<M26X17<M27X22<M27X23<M26X18<M26X19<M27X16<M28X14<M25X13<M26X22<M27X17<M26X23<M27X13<M27X14<M27X15<M26X24<M27X24<M28X25<M27X11<M28X18<M27X25<M26X14<M27X19<M27X20<M28X13<M27X21<M28X23<M28X24<M28X22<M28X11<M28X17<M29X11<M27X18<M28X21<M28X16<M28X15<M28X20<M29X14<M29X25<M29X21<M28X19<M29X18<M29X17<M29X13<M29X24<M29X16<M29X23<M29X19<M30X25<M29X22<M30X21<M30X22<M29X12<M29X15<M30X18<M30X20<M30X24<M30X23<M29X20<M30X14<M30X13<M30X17<M30X12<M30X11<M30X16<M30X15<M30X19
diff --git a/scripts/dso-ordering-test.py b/scripts/dso-ordering-test.py
new file mode 100644
-index 0000000000..5dfb3476fa
+index 0000000000..944ee74052
--- /dev/null
+++ b/scripts/dso-ordering-test.py
-@@ -0,0 +1,1150 @@
+@@ -0,0 +1,1144 @@
+#!/usr/bin/python3
+# Generate testcase files and Makefile fragments for DSO sorting test
+# Copyright (C) 2021 Free Software Foundation, Inc.
@@ -755,12 +755,12 @@ index 0000000000..5dfb3476fa
+construction of complex dependency cases, however it must be noted that this
+is only a tool to speed up testcase construction, and thus the generation
+features are largely mechanical in nature; inconsistencies or errors may occur
-+if the input description was itself erroronous or have unforeseen interactions.
++if the input description was itself erroneous or have unforeseen interactions.
+
+The format of the input test description files are:
+
+ # Each test description has a name, lines of description,
-+ # and an expected output specification. Comments use '#'.
++ # and an expected output specification. Comments use '#'.
+ testname1: <test-description-line>
+ output: <expected-output-string>
+
@@ -784,7 +784,7 @@ index 0000000000..5dfb3476fa
+
+ # 'testname3' will be run and compared two times, for both
+ # GLIBC_TUNABLES=<glibc-tunable-string1> and
-+ # GLIBC_TUNABLES=<glibc-tunable-string2>. This can be cleared and reset by the
++ # GLIBC_TUNABLES=<glibc-tunable-string2>. This can be cleared and reset by the
+ # 'clear_tunables' command:
+ clear_tunables
+
@@ -837,15 +837,15 @@ index 0000000000..5dfb3476fa
+e.g. a=>b emits 'a(b())'
+
+For single character object names, square brackets [] in the description
-+allows specifiying multiple objects; e.g. a->[bcd]->e is equivalent to
++allows specifying multiple objects; e.g. a->[bcd]->e is equivalent to
+ a->b->e;a->c->e;a->d->e
+
+The () parenthesis construct with space separated names is also allowed for
-+specifying objects. For names with integer suffixes a range can also be used,
++specifying objects. For names with integer suffixes a range can also be used,
+e.g. (foo1 bar2-5), specifies DSOs foo1, bar2, bar2, bar3, bar4, bar5.
+
+A {} construct specifies the main test program, and its link dependencies
-+are also specified using ->. Inside {}, a few ;-seperated constructs are
++are also specified using ->. Inside {}, a few ;-separated constructs are
+allowed:
+ +a Loads module a using dlopen(RTLD_LAZY|RTLD_GLOBAL)
+ ^a Loads module a using dlopen(RTLD_LAZY)
@@ -854,7 +854,7 @@ index 0000000000..5dfb3476fa
+ -a Unloads module a using dlclose()
+
+The generated main program outputs '{' '}' with all output from above
-+constructs in between. The other output before/after {} are the ordered
++constructs in between. The other output before/after {} are the ordered
+constructor/destructor output.
+
+If no {} construct is present, a default empty main program is linked
@@ -872,7 +872,7 @@ index 0000000000..5dfb3476fa
+ {}->foo,{}->*
+
+Note that '*' works not only on main{}, but can be used as the
-+dependency target of any object. Note that it only works as a target,
++dependency target of any object. Note that it only works as a target,
+not a dependency source.
+
+The '!' operator after object names turns on permutation of its
@@ -880,7 +880,7 @@ index 0000000000..5dfb3476fa
+with 'a.so' built with a link line of "b.so c.so d.so", for a!->[bcd]
+permutations of a's dependencies creates multiple testcases with
+different link line orders: "b.so c.so d.so", "c.so b.so d.so",
-+"b.so d.so c.so", etc. Note that for a <test-name> specified on
++"b.so d.so c.so", etc. Note that for a <test-name> specified on
+the script command-line, multiple <test-name_1>, <test-name_2>, etc.
+tests will be generated (e.g. for a!->[bc]!->[de], eight tests with
+different link orders for a, b, and c will be generated)
@@ -913,10 +913,10 @@ index 0000000000..5dfb3476fa
+its constructor run first, followed by 'b' and then 'a'.
+
+Destructor output for each DSO is a '<' character followed by its name,
-+reflecting its reverse nature of constructors. In the above example, the
++reflecting its reverse nature of constructors. In the above example, the
+destructor output part is "<a<b<c".
+
-+The middle "{}" part is the main program. In this simple example, nothing
++The middle "{}" part is the main program. In this simple example, nothing
+was specified for the main program, so by default it is implicitly linked
+to the DSO 'a' (with no other DSOs depending on it) and only prints the
+brackets {} with no actions inside.
@@ -929,22 +929,21 @@ index 0000000000..5dfb3476fa
+
+The constructor and destructor parts display the a->h dependency as expected.
+Inside the main program, the "+c" action triggers a dlopen() of DSO 'c',
-+causing another chain of constructors "g>c>" to be triggered. Here it is
-+displayed inside [] brackets for each dlopen call. The same is done for "-c",
++causing another chain of constructors "g>c>" to be triggered. Here it is
++displayed inside [] brackets for each dlopen call. The same is done for "-c",
+a dlclose() of 'c'.
+
+The "%c" output is due to calling to fn_c() inside DSO 'c', this comprises
+of two parts: the '%' character is printed by the caller, here it is the main
-+program. The 'c' character is printed from inside fn_c(). The '%' character
-+indicates that this is called by a dlsym() of "fn_c". A '@' character would
-+mean a direct call (with a symbol reference). These can all be controlled
++program. The 'c' character is printed from inside fn_c(). The '%' character
++indicates that this is called by a dlsym() of "fn_c". A '@' character would
++mean a direct call (with a symbol reference). These can all be controlled
+by the main test program constructs documented earlier.
+
+The output strings described here is the exact same form placed in
+test description files' "output: <expected output>" line.
-+
-+
+"""
++
+import sys
+import re
+import os
@@ -959,33 +958,40 @@ index 0000000000..5dfb3476fa
+# and can be changed here to another toolchain path if needed.
+build_gcc = "gcc"
+
-+parser = argparse.ArgumentParser("")
-+parser.add_argument("description",
-+ help="Description string of DSO dependency test to be "
-+ "generated (see script source for documentation of "
-+ "description language), either specified here as "
-+ "command line argument, or by input file using "
-+ "-f/--description-file option",
-+ nargs="?", default="")
-+parser.add_argument("test_name", help="Identifier for testcase being "
-+ "generated", nargs="?", default="")
-+parser.add_argument("--objpfx",
-+ help="Path to place generated files, defaults to "
-+ "current directory if none specified",
-+ nargs="?", default="./")
-+parser.add_argument("-m", "--output-makefile",
-+ help="File to write Makefile fragment to, defaults to "
-+ "stdout when option not present", nargs="?", default="")
-+parser.add_argument("-f", "--description-file",
-+ help="Input file containing testcase descriptions",
-+ nargs="?", default="")
-+parser.add_argument("--build", help="After C testcase generated, build it "
-+ "using gcc (for manual testing purposes)",
-+ action="store_true")
-+parser.add_argument("--debug-output", help="Prints some internal data "
-+ "structures; used for debugging of this script",
-+ action="store_true")
-+cmdlineargs = parser.parse_args()
++def get_parser():
++ parser = argparse.ArgumentParser("")
++ parser.add_argument("description",
++ help="Description string of DSO dependency test to be "
++ "generated (see script source for documentation of "
++ "description language), either specified here as "
++ "command line argument, or by input file using "
++ "-f/--description-file option",
++ nargs="?", default="")
++ parser.add_argument("test_name",
++ help="Identifier for testcase being generated",
++ nargs="?", default="")
++ parser.add_argument("--objpfx",
++ help="Path to place generated files, defaults to "
++ "current directory if none specified",
++ nargs="?", default="./")
++ parser.add_argument("-m", "--output-makefile",
++ help="File to write Makefile fragment to, defaults to "
++ "stdout when option not present",
++ nargs="?", default="")
++ parser.add_argument("-f", "--description-file",
++ help="Input file containing testcase descriptions",
++ nargs="?", default="")
++ parser.add_argument("--build", help="After C testcase generated, build it "
++ "using gcc (for manual testing purposes)",
++ action="store_true")
++ parser.add_argument("--debug-output",
++ help="Prints some internal data "
++ "structures; used for debugging of this script",
++ action="store_true")
++ return parser
++
++# Main script starts here.
++cmdlineargs = get_parser().parse_args()
+test_name = cmdlineargs.test_name
+description = cmdlineargs.description
+objpfx = cmdlineargs.objpfx
@@ -1024,8 +1030,6 @@ index 0000000000..5dfb3476fa
+
+ # list of main program operations
+ self.main_program = []
-+ # set if main program needs -ldl
-+ self.main_program_needs_ldl = False
+ # set if default dependencies added to main
+ self.main_program_default_deps = True
+
@@ -1058,9 +1062,6 @@ index 0000000000..5dfb3476fa
+ if not m:
+ error("'%s' is not recognized main program operation" % (s))
+ opr = m.group(1)
-+ if(opr == '+' or opr == '^' or opr == '%' or opr == '-'):
-+ # Determined the main program needs libdl
-+ test_descr.main_program_needs_ldl = True
+ obj = m.group(2)
+ if not obj in test_descr.objs:
+ test_descr.objs.append(obj)
@@ -1113,7 +1114,6 @@ index 0000000000..5dfb3476fa
+
+# Main line parser of description language
+def parse_description_string(t, descr_str):
-+
+ # State used when parsing dependencies
+ curr_objs = []
+ in_dep = False
@@ -1242,8 +1242,7 @@ index 0000000000..5dfb3476fa
+ error("unknown token '%s'" % (value))
+ return t
+
-+
-+
++# Main routine to process each testcase description
+def process_testcase(t):
+ global objpfx
+ assert t.test_name
@@ -1340,7 +1339,7 @@ index 0000000000..5dfb3476fa
+
+ # Generate link dependencies for all DSOs, done in a DFS fashion.
+ # Usually this doesn't need to be this complex, just listing the direct
-+ # dependencies is enough. However to support creating circular
++ # dependencies is enough. However to support creating circular
+ # dependency situations, traversing it by DFS and tracking processing
+ # status is the natural way to do it.
+ obj_processed = {}
@@ -1359,7 +1358,7 @@ index 0000000000..5dfb3476fa
+ depstr = (" $(objpfx)" + test_subdir + "/"
+ + test_name + "-" + dep + ".FAKE.so")
+ # Create empty C file and Makefile fragments for fake
-+ # object. This only needs to be done at most once for
++ # object. This only needs to be done at most once for
+ # an object name.
+ if not dep in fake_created:
+ f = open(testpfx + test_name + "-" + dep
@@ -1404,8 +1403,6 @@ index 0000000000..5dfb3476fa
+ for o in test_descr.deps['#']:
+ depstr += (" $(objpfx)" + test_subdir + "/"
+ + test_name + "-" + o + ".so")
-+ if test_descr.main_program_needs_ldl:
-+ depstr += " $(libdl)"
+ makefile.write("$(objpfx)%s/%s:%s\n" % (test_subdir, test_name, depstr))
+ ldflags = "-Wl,--no-as-needed"
+ if '#' in test_descr.soname_map:
@@ -1534,10 +1531,9 @@ index 0000000000..5dfb3476fa
+ f = open(testpfx + test_name + ".c", "w")
+
+ # if there are some operations in main(), it means we need -ldl
-+ if test_descr.main_program_needs_ldl:
-+ f.write("#include <dlfcn.h>\n")
+ f.write("#include <stdio.h>\n")
+ f.write("#include <stdlib.h>\n")
++ f.write("#include <dlfcn.h>\n")
+ for s in test_descr.main_program:
+ if s[0] == '@':
+ f.write("extern void fn_%s (void);\n" % (s[1:]));
@@ -1667,8 +1663,6 @@ index 0000000000..5dfb3476fa
+ + test_descr.soname_map['#'] + ".so")
+ cmd += [soname]
+ cmd += list(main_deps)
-+ if test_descr.main_program_needs_ldl:
-+ cmd += ["-ldl"]
+ run_cmd(cmd)
+
+ # Check if we need to enumerate permutations of dependencies
@@ -1877,13 +1871,13 @@ new file mode 100644
index 0000000000..7e7d5dc67c
--- /dev/null
+++ b/support/Depend
-@@ -0,0 +1 @@
+@@ -0,0 +1 @@
+elf
diff --git a/support/Makefile b/support/Makefile
-index a462781718..0da604ade8 100644
+index 7f03950914..984ec02dfe 100644
--- a/support/Makefile
+++ b/support/Makefile
-@@ -252,10 +252,16 @@ others-noinstall += shell-container echo-container true-container
+@@ -257,10 +257,16 @@ others-noinstall += shell-container echo-container true-container
others += $(LINKS_DSO_PROGRAM)
others-noinstall += $(LINKS_DSO_PROGRAM)
@@ -1904,7 +1898,7 @@ diff --git a/support/support_test_main.c b/support/support_test_main.c
index 07e3cdd173..66a754b84f 100644
--- a/support/support_test_main.c
+++ b/support/support_test_main.c
-@@ -228,6 +228,18 @@ run_test_function (int argc, char **argv, const struct test_config *config)
+@@ -228,6 +228,18 @@ run_test_function (int argc, char **argv, const struct test_config *config)
while (wait_for_debugger)
usleep (1000);
@@ -1927,7 +1921,7 @@ diff --git a/support/test-driver.c b/support/test-driver.c
index b0bea46dee..1552f62c9b 100644
--- a/support/test-driver.c
+++ b/support/test-driver.c
-@@ -116,7 +116,9 @@ main (int argc, char **argv)
+@@ -116,7 +116,9 @@ main (int argc, char **argv)
#if defined (TEST_FUNCTION) && defined (TEST_FUNCTON_ARGV)
# error TEST_FUNCTION and TEST_FUNCTION_ARGV cannot be defined at the same time
#endif
@@ -1942,7 +1936,7 @@ diff --git a/support/test-driver.h b/support/test-driver.h
index 8d4f38275d..b44c0ff033 100644
--- a/support/test-driver.h
+++ b/support/test-driver.h
-@@ -36,6 +36,7 @@ struct test_config
+@@ -36,6 +36,7 @@ struct test_config
int expected_signal; /* If non-zero, expect termination by signal. */
char no_mallopt; /* Boolean flag to disable mallopt. */
char no_setvbuf; /* Boolean flag to disable setvbuf. */
@@ -1955,7 +1949,7 @@ new file mode 100644
index 0000000000..61560d7bfb
--- /dev/null
+++ b/support/test-run-command.c
-@@ -0,0 +1,22 @@
+@@ -0,0 +1,22 @@
+/* Main program for test-run-command support utility.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
diff --git a/v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch b/v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
index c83a2fb02c17..8dae228961e2 100644
--- a/v6-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
+++ b/v8-2-2-BZ-17645-fix-slow-DSO-sorting-behavior-in-dynamic-loader----Algorithm-changes.patch
@@ -1,8 +1,28 @@
+diff --git a/NEWS b/NEWS
+index 220d327071..b39b1e5e33 100644
+--- a/NEWS
++++ b/NEWS
+@@ -51,6 +51,15 @@ Major new features:
+
+ * The ISO C2X macro _PRINTF_NAN_LEN_MAX has been added to <stdio.h>.
+
++* A new DSO sorting algorithm has been added in the dynamic linker that uses
++ topological sorting by depth-first search (DFS), solving performance issues
++ of the existing sorting algorithm when encountering particular circular
++ object dependency cases.
++
++* A new tunable, glibc.rtld.dynamic_sort, can be used to select between the two
++ DSO sorting algorithms. The default setting of '1' uses the current existing
++ algorithm, while a value of '2' selects the new DFS-based algorithm.
++
+ Deprecated and removed features, and other changes affecting compatibility:
+
+ * The r_version update in the debugger interface makes the glibc binary
diff --git a/elf/dl-close.c b/elf/dl-close.c
-index f39001cab9..a55b3a00fa 100644
+index cfe0f1c0c9..4f5cfcc1c3 100644
--- a/elf/dl-close.c
+++ b/elf/dl-close.c
-@@ -167,8 +167,6 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -167,8 +167,6 @@ _dl_close_worker (struct link_map *map, bool force)
bool any_tls = false;
const unsigned int nloaded = ns->_ns_nloaded;
@@ -11,7 +31,7 @@ index f39001cab9..a55b3a00fa 100644
struct link_map *maps[nloaded];
/* Run over the list and assign indexes to the link maps and enter
-@@ -176,24 +174,21 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -176,24 +174,21 @@ _dl_close_worker (struct link_map *map, bool force)
int idx = 0;
for (struct link_map *l = ns->_ns_loaded; l != NULL; l = l->l_next)
{
@@ -39,7 +59,7 @@ index f39001cab9..a55b3a00fa 100644
/* Already handled. */
continue;
-@@ -204,12 +199,12 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -204,12 +199,12 @@ _dl_close_worker (struct link_map *map, bool force)
/* See CONCURRENCY NOTES in cxa_thread_atexit_impl.c to know why
acquire is sufficient and correct. */
&& atomic_load_acquire (&l->l_tls_dtor_count) == 0
@@ -55,7 +75,7 @@ index f39001cab9..a55b3a00fa 100644
/* Signal the object is still needed. */
l->l_idx = IDX_STILL_USED;
-@@ -225,9 +220,9 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -225,9 +220,9 @@ _dl_close_worker (struct link_map *map, bool force)
{
assert ((*lp)->l_idx >= 0 && (*lp)->l_idx < nloaded);
@@ -67,7 +87,7 @@ index f39001cab9..a55b3a00fa 100644
/* If we marked a new object as used, and we've
already processed it, then we need to go back
and process again from that point forward to
-@@ -250,9 +245,9 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -250,9 +245,9 @@ _dl_close_worker (struct link_map *map, bool force)
{
assert (jmap->l_idx >= 0 && jmap->l_idx < nloaded);
@@ -79,7 +99,7 @@ index f39001cab9..a55b3a00fa 100644
if (jmap->l_idx - 1 < done_index)
done_index = jmap->l_idx - 1;
}
-@@ -262,8 +257,7 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -262,8 +257,7 @@ _dl_close_worker (struct link_map *map, bool force)
/* Sort the entries. We can skip looking for the binary itself which is
at the front of the search list for the main namespace. */
@@ -89,7 +109,7 @@ index f39001cab9..a55b3a00fa 100644
/* Call all termination functions at once. */
#ifdef SHARED
-@@ -280,7 +274,7 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -280,7 +274,7 @@ _dl_close_worker (struct link_map *map, bool force)
/* All elements must be in the same namespace. */
assert (imap->l_ns == nsid);
@@ -98,7 +118,7 @@ index f39001cab9..a55b3a00fa 100644
{
assert (imap->l_type == lt_loaded && !imap->l_nodelete_active);
-@@ -333,7 +327,7 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -333,7 +327,7 @@ _dl_close_worker (struct link_map *map, bool force)
if (i < first_loaded)
first_loaded = i;
}
@@ -107,7 +127,7 @@ index f39001cab9..a55b3a00fa 100644
else if (imap->l_type == lt_loaded)
{
struct r_scope_elem *new_list = NULL;
-@@ -557,7 +551,7 @@ _dl_close_worker (struct link_map *map, bool force)
+@@ -560,7 +554,7 @@ _dl_close_worker (struct link_map *map, bool force)
for (unsigned int i = first_loaded; i < nloaded; ++i)
{
struct link_map *imap = maps[i];
@@ -120,7 +140,7 @@ diff --git a/elf/dl-deps.c b/elf/dl-deps.c
index 087a49b212..237d9636c5 100644
--- a/elf/dl-deps.c
+++ b/elf/dl-deps.c
-@@ -613,10 +613,9 @@ Filters not supported with LD_TRACE_PRELINKING"));
+@@ -613,10 +613,9 @@ Filters not supported with LD_TRACE_PRELINKING"));
/* If libc.so.6 is the main map, it participates in the sort, so
that the relocation order is correct regarding libc.so.6. */
@@ -138,7 +158,7 @@ diff --git a/elf/dl-fini.c b/elf/dl-fini.c
index 6dbdfe4b3e..c683884c35 100644
--- a/elf/dl-fini.c
+++ b/elf/dl-fini.c
-@@ -92,8 +92,7 @@ _dl_fini (void)
+@@ -92,8 +92,7 @@ _dl_fini (void)
/* Now we have to do the sorting. We can skip looking for the
binary itself which is at the front of the search list for
the main namespace. */
@@ -149,10 +169,10 @@ index 6dbdfe4b3e..c683884c35 100644
/* We do not rely on the linked list of loaded object anymore
from this point on. We have our own list here (maps). The
diff --git a/elf/dl-sort-maps.c b/elf/dl-sort-maps.c
-index d21770267a..91c5009ac4 100644
+index d21770267a..a274ed66cc 100644
--- a/elf/dl-sort-maps.c
+++ b/elf/dl-sort-maps.c
-@@ -16,16 +16,24 @@
+@@ -16,16 +16,24 @@
License along with the GNU C Library; if not, see
<https://www.gnu.org/licenses/>. */
@@ -161,7 +181,7 @@ index d21770267a..91c5009ac4 100644
+#include <elf/dl-tunables.h>
+/* Note: this is the older, "original" sorting algorithm, being used as
-+ default up to 2.32.
++ default up to 2.35.
-/* Sort array MAPS according to dependencies of the contained objects.
- Array USED, if non-NULL, is permutated along MAPS. If FOR_FINI this is
@@ -183,7 +203,7 @@ index d21770267a..91c5009ac4 100644
/* A list of one element need not be sorted. */
if (nmaps <= 1)
return;
-@@ -66,14 +74,6 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
+@@ -66,14 +74,6 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
(k - i) * sizeof (maps[0]));
maps[k] = thisp;
@@ -198,7 +218,7 @@ index d21770267a..91c5009ac4 100644
if (seen[i + 1] > nmaps - i)
{
++i;
-@@ -120,3 +120,183 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
+@@ -120,3 +120,183 @@ _dl_sort_maps (struct link_map **maps, unsigned int nmaps, char *used,
next:;
}
}
@@ -357,15 +377,17 @@ index d21770267a..91c5009ac4 100644
+}
+
+void
++_dl_sort_maps_init (void)
++{
++ int32_t algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort, int32_t, NULL);
++ GLRO(dl_dso_sort_algo) = algorithm == 1 ? dso_sort_algorithm_original
++ : dso_sort_algorithm_dfs;
++}
++
++void
+_dl_sort_maps (struct link_map **maps, unsigned int nmaps,
+ unsigned int skip, bool for_fini)
+{
-+ /* Index code for sorting algorithm currently in use. */
-+ static int32_t algorithm = 0;
-+ if (__glibc_unlikely (algorithm == 0))
-+ algorithm = TUNABLE_GET (glibc, rtld, dynamic_sort,
-+ int32_t, NULL);
-+
+ /* It can be tempting to use a static function pointer to store and call
+ the current selected sorting algorithm routine, but experimentation
+ shows that current processors still do not handle indirect branches
@@ -373,20 +395,45 @@ index d21770267a..91c5009ac4 100644
+ PTR_MANGLE/DEMANGLE, further impairing performance of small, common
+ input cases. A simple if-case with direct function calls appears to
+ be the fastest. */
-+ if (__glibc_likely (algorithm == 1))
++ if (__glibc_likely (GLRO(dl_dso_sort_algo) == dso_sort_algorithm_original))
+ _dl_sort_maps_original (maps, nmaps, skip, for_fini);
-+ else if (algorithm == 2)
-+ _dl_sort_maps_dfs (maps, nmaps, skip, for_fini);
+ else
-+ __builtin_unreachable ();
++ _dl_sort_maps_dfs (maps, nmaps, skip, for_fini);
+}
+
+#endif /* HAVE_TUNABLES. */
+diff --git a/elf/dl-support.c b/elf/dl-support.c
+index d99c1f1d62..98d5d8db5c 100644
+--- a/elf/dl-support.c
++++ b/elf/dl-support.c
+@@ -166,6 +166,8 @@ size_t _dl_phnum;
+ uint64_t _dl_hwcap;
+ uint64_t _dl_hwcap2;
+
++enum dso_sort_algorithm _dl_dso_sort_algo;
++
+ /* The value of the FPU control word the kernel will preset in hardware. */
+ fpu_control_t _dl_fpu_control = _FPU_DEFAULT;
+
+diff --git a/elf/dl-sysdep.c b/elf/dl-sysdep.c
+index 2c684c2db2..4dc366eea4 100644
+--- a/elf/dl-sysdep.c
++++ b/elf/dl-sysdep.c
+@@ -231,6 +231,9 @@ _dl_sysdep_start (void **start_argptr,
+
+ __tunables_init (_environ);
+
++ /* Initialize DSO sorting algorithm after tunables. */
++ _dl_sort_maps_init ();
++
+ #ifdef DL_SYSDEP_INIT
+ DL_SYSDEP_INIT;
+ #endif
diff --git a/elf/dl-tunables.list b/elf/dl-tunables.list
index 8ddd4a2314..46ffb23784 100644
--- a/elf/dl-tunables.list
+++ b/elf/dl-tunables.list
-@@ -156,4 +156,13 @@ glibc {
+@@ -156,4 +156,13 @@ glibc {
security_level: SXID_IGNORE
}
}
@@ -400,11 +447,22 @@ index 8ddd4a2314..46ffb23784 100644
+ }
+ }
}
+diff --git a/elf/dso-sort-tests-1.def b/elf/dso-sort-tests-1.def
+index 873ddf55d9..5f7f18ef27 100644
+--- a/elf/dso-sort-tests-1.def
++++ b/elf/dso-sort-tests-1.def
+@@ -62,5 +62,5 @@ output: b>a>{}<a<b
+ # The below expected outputs are what the two algorithms currently produce
+ # respectively, for regression testing purposes.
+ tst-bz15311: {+a;+e;+f;+g;+d;%d;-d;-g;-f;-e;-a};a->b->c->d;d=>[ba];c=>a;b=>e=>a;c=>f=>b;d=>g=>c
+-xfail_output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<a<c<d<g<f<b<e];}
++output(glibc.rtld.dynamic_sort=1): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<a<c<d<g<f<b<e];}
+ output(glibc.rtld.dynamic_sort=2): {+a[d>c>b>a>];+e[e>];+f[f>];+g[g>];+d[];%d(b(e(a()))a()g(c(a()f(b(e(a()))))));-d[];-g[];-f[];-e[];-a[<g<f<a<b<c<d<e];}
diff --git a/elf/rtld.c b/elf/rtld.c
-index d733359eaf..abdc13c13a 100644
+index b8ba2d8836..be2d5d8e74 100644
--- a/elf/rtld.c
+++ b/elf/rtld.c
-@@ -1389,6 +1389,9 @@ dl_main (const ElfW(Phdr) *phdr,
+@@ -1391,6 +1391,9 @@ dl_main (const ElfW(Phdr) *phdr,
main_map->l_name = (char *) "";
*user_entry = main_map->l_entry;
@@ -418,7 +476,7 @@ diff --git a/elf/tst-rtld-list-tunables.exp b/elf/tst-rtld-list-tunables.exp
index 9f66c52885..9bf572715f 100644
--- a/elf/tst-rtld-list-tunables.exp
+++ b/elf/tst-rtld-list-tunables.exp
-@@ -10,5 +10,6 @@ glibc.malloc.tcache_max: 0x0 (min: 0x0, max: 0x[f]+)
+@@ -10,5 +10,6 @@ glibc.malloc.tcache_max: 0x0 (min: 0x0, max: 0x[f]+)
glibc.malloc.tcache_unsorted_limit: 0x0 (min: 0x0, max: 0x[f]+)
glibc.malloc.top_pad: 0x0 (min: 0x0, max: 0x[f]+)
glibc.malloc.trim_threshold: 0x0 (min: 0x0, max: 0x[f]+)
@@ -426,10 +484,10 @@ index 9f66c52885..9bf572715f 100644
glibc.rtld.nns: 0x4 (min: 0x1, max: 0x10)
glibc.rtld.optional_static_tls: 0x200 (min: 0x0, max: 0x[f]+)
diff --git a/include/link.h b/include/link.h
-index 4af16cb596..50f45db243 100644
+index 484ee6cb1b..c1c382ccfa 100644
--- a/include/link.h
+++ b/include/link.h
-@@ -181,6 +181,11 @@ struct link_map
+@@ -181,6 +181,11 @@ struct link_map
unsigned int l_init_called:1; /* Nonzero if DT_INIT function called. */
unsigned int l_global:1; /* Nonzero if object in _dl_global_scope. */
unsigned int l_reserved:2; /* Reserved for internal use. */
@@ -441,11 +499,56 @@ index 4af16cb596..50f45db243 100644
unsigned int l_phdr_allocated:1; /* Nonzero if the data structure pointed
to by `l_phdr' is allocated. */
unsigned int l_soname_added:1; /* Nonzero if the SONAME is for sure in
+diff --git a/manual/tunables.texi b/manual/tunables.texi
+index 658547c613..10f4d75993 100644
+--- a/manual/tunables.texi
++++ b/manual/tunables.texi
+@@ -309,6 +309,17 @@ changed once allocated at process startup. The default allocation of
+ optional static TLS is 512 bytes and is allocated in every thread.
+ @end deftp
+
++@deftp Tunable glibc.rtld.dynamic_sort
++Sets the algorithm to use for DSO sorting, valid values are @samp{1} and
++@samp{2}. For value of @samp{1}, an older O(n^3) algorithm is used, which is
++long time tested, but may have performance issues when dependencies between
++shared objects contain cycles due to circular dependencies. When set to the
++value of @samp{2}, a different algorithm is used, which implements a
++topological sort through depth-first search, and does not exhibit the
++performance issues of @samp{1}.
++
++The default value of this tunable is @samp{1}.
++@end deftp
+
+ @node Elision Tunables
+ @section Elision Tunables
diff --git a/sysdeps/generic/ldsodefs.h b/sysdeps/generic/ldsodefs.h
-index 9c15259236..ad48a0d7da 100644
+index 0410f777a6..65a6a51633 100644
--- a/sysdeps/generic/ldsodefs.h
+++ b/sysdeps/generic/ldsodefs.h
-@@ -1084,7 +1084,7 @@ extern void _dl_fini (void) attribute_hidden;
+@@ -245,6 +245,13 @@ enum allowmask
+ };
+
+
++/* DSO sort algorithm to use (check dl-sort-maps.c). */
++enum dso_sort_algorithm
++ {
++ dso_sort_algorithm_original,
++ dso_sort_algorithm_dfs
++ };
++
+ struct audit_ifaces
+ {
+ void (*activity) (uintptr_t *, unsigned int);
+@@ -678,6 +685,8 @@ struct rtld_global_ro
+ platforms. */
+ EXTERN uint64_t _dl_hwcap2;
+
++ EXTERN enum dso_sort_algorithm _dl_dso_sort_algo;
++
+ #ifdef SHARED
+ /* We add a function table to _rtld_global which is then used to
+ call the function instead of going through the PLT. The result
+@@ -1104,7 +1113,7 @@ extern void _dl_fini (void) attribute_hidden;
/* Sort array MAPS according to dependencies of the contained objects. */
extern void _dl_sort_maps (struct link_map **maps, unsigned int nmaps,
@@ -454,3 +557,13 @@ index 9c15259236..ad48a0d7da 100644
/* The dynamic linker calls this function before and having changing
any shared object mappings. The `r_state' member of `struct r_debug'
+@@ -1235,6 +1244,9 @@ extern struct link_map * _dl_get_dl_main_map (void)
+ # endif
+ #endif
+
++/* Initialize the DSO sort algorithm to use. */
++extern void _dl_sort_maps_init (void) attribute_hidden;
++
+ /* Initialization of libpthread for statically linked applications.
+ If libpthread is not linked in, this is an empty function. */
+ void __pthread_initialize_minimal (void) weak_function;