Hi Carlos,
Thanks for the detailed review you gave the last submission[1], and
apologies for taking so long for this revised patch set. I believe
this one should resolve almost all of the issues you raised in your
review.

As the last submission, there are two parts: this one, the testing patch,
and the actual algorithm changes.

On the testing part here, the dso-ordering-test.py script has had
some pretty significant changes since the last version[2]:

1. For each test, all objects and scripts are now created in an
'$objpfx/elf/<testname>-dir' subdirectory, which should be much tidier
for testcases with a large number of objects.

2. The running and comparing of tests are now all combined into a single test,
executed by the running of a generated <testname>.sh shell script. In the last
version, things like permutations created a large number of individual tests,
which are now all combined as one. Actually another tidying change.

3. Tests can now be specified in description files; all of the
tests that were in the last submission are now placed in elf/dso-sort-tests-1.def.

4. More flexible names, now [a-zA-Z0-9]+ are allowed.

5. Constructor/destructor output adjusted to "name>" and "<name", which
should be better suited for the more general names of objects.

6. Capability to create tests with circularly linked dependencies. This
functionality was actually neglected in the last patch, but can now be created.

7. In the test description files, multiple expected outputs can be specified,
each with a corresponding GLIBC_TUNABLE= string to be used when running the
test (intention is to test the behavior of multiple sorting algorithms, as
you suggested in your review)

In particular, the 3-6 items above now allow to include very large tests,
of which I have included a specific one in elf/dso-sort-tests-2.def, adapted
from the large testcase from Redhat Bugzilla 1162810 that Paulo Andrade provided:
https://bugzilla.redhat.com/show_bug.cgi?id=1162810, attachment "dso_3"

Do note however that, because a complete reproduction also requires how
the objects are linked with the main binary, the information Paulo provided
there is not enough to recreate the 100% exact same scenario, however the
adapted test is still heavy enough to reproduce the slowness of the current
sorting algorithm, taking about 1 minute to run (on my Skylake system), while
the new algorithm is instantaneous. This should be sufficient as the microbenchmark
you mentioned in your review, though I did not undertake any effort to time it in detail.

Thanks,
Chung-Lin

[1] https://sourceware.org/pipermail/libc-alpha/2019-December/109676.html
[2] https://sourceware.org/pipermail/libc-alpha/2019-July/105317.html


2020-05-19  Chung-Lin Tang  <cltang@codesourcery.com>

	[BZ #17645]
	[BZ #15311]
	[BZ #15310]
	* elf/Makefile (include_dsosort_tests): New make function. Use
	to process dso-sort-tests-[12].def files.
	(single_dsosort_test): Likewise.
	* dso-sort-tests-1.def: New file.
	* dso-sort-tests-2.def: New file.
         * scripts/dso-ordering-test.py: New script.