Fix PR30358, performance with --sort-section
authorMichael Matz <matz@suse.de>
Tue, 25 Apr 2023 15:10:05 +0000 (17:10 +0200)
committerMichael Matz <matz@suse.de>
Thu, 27 Apr 2023 14:15:26 +0000 (16:15 +0200)
commit670c91c0c5eb3fb16d42fe5b2d48a33c64e3ec52
tree1661c3ac47bd758b10659180f510523931a97aaf
parent0d42948f0c822ed3782a45771c8fbc21aa2d6553
Fix PR30358, performance with --sort-section

since af31506c we only use the binary tree when section sorting is
required.  While its unbalanced and hence can degrade to a linear list
it should otherwise have been equivalent to the old code relying on
insertion sort.  Unfortunately it was not.  The old code directly used
lang_add_section to populate the sorted list, the new code first
populates the tree and only then does lang_add_section on the sorted
result.

In the testcase we have very many linkonce section groups, and hence
lang_add_section won't actually insert anything for most of them.  That
limited the to-be-sorted list length previously.  The tree-sorting code
OTOH first created a tree of all candidates sections, including those
that wouldn't be inserted by lang_add_section, hence increasing the size
of the sorting problem.  In the testcase the chain length went from
about 1500 to 106000, and in the degenerated case (as in the testcase)
that goes in quadratically.

This splits out most of the early-out code from lang_add_section to its
own function and uses the latter to avoid inserting into the tree.  This
refactoring slightly changes the order of early-out tests (the ones
based on section flags is now done last, and only in lang_add_section).
The new function is not a pure predicate: it can give warnings and it
might change output_section, like the old early-out code did.  I have
also added a skip-warning case in the first discard case, whose
non-existence seemed to have been an oversight.

PR 30358
* ldlang.c (wont_add_section_p): Split out from ...
(lang_add_section): ... here.
(output_section_callback_sort): Use wont_add_section_p to not
always add sections to the sort tree.
ld/ldlang.c