* [PATCH] Only use wild_sort_fast
@ 2022-11-25 16:04 Michael Matz
2022-11-28 2:16 ` Alan Modra
0 siblings, 1 reply; 2+ messages in thread
From: Michael Matz @ 2022-11-25 16:04 UTC (permalink / raw)
To: binutils
there's no reason why the tree-based variant can't always be used
when sorting is required, it merely needs to also support filename
sorting and have a fast path for insertion at end (aka rightmost tree
leaf).
The filename sorting isn't tested anywhere and the only scripttempl
that uses it is avr (for 'SORT(*)(.ctors)'), and I believe even there it
was a mistake. Either way, this adds a testcase for filename sorting as
well.
Then the non-BST based sorting can be simplified to only support
the fast case of no sorting required at all (at the same time renaming
the two variants to _sort and _nosort).
---
Regtested on Alans target-list. It doesn't bring any measurable speedup,
but I like the code better: if sorting is needed there should be a single
reasonably quick sorting method, not two mediocre ones (one incomplete,
the other slow).
Okay for master?
Ciao,
Michael.
ld/ldlang.c | 302 +++++++++++----------------
ld/ldlang.h | 3 +-
ld/testsuite/ld-scripts/sort-file.d | 18 ++
ld/testsuite/ld-scripts/sort-file.t | 6 +
ld/testsuite/ld-scripts/sort-file1.s | 6 +
ld/testsuite/ld-scripts/sort-file2.s | 6 +
6 files changed, 163 insertions(+), 178 deletions(-)
create mode 100644 ld/testsuite/ld-scripts/sort-file.d
create mode 100644 ld/testsuite/ld-scripts/sort-file.t
create mode 100644 ld/testsuite/ld-scripts/sort-file1.s
create mode 100644 ld/testsuite/ld-scripts/sort-file2.s
diff --git a/ld/ldlang.c b/ld/ldlang.c
index 3274659aec4..81a6aeb7a89 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -553,30 +553,92 @@ compare_section (sort_type sort, asection *asec, asection *bsec)
return ret;
}
-/* Build a Binary Search Tree to sort sections, unlike insertion sort
- used in wild_sort(). BST is considerably faster if the number of
- of sections are large. */
+/* PE puts the sort key in the input statement. */
+
+static const char *
+sort_filename (bfd *abfd)
+{
+ lang_input_statement_type *is = bfd_usrdata (abfd);
+ if (is->sort_key)
+ return is->sort_key;
+ return bfd_get_filename (abfd);
+}
+
+/* Handle wildcard sorting. This returns the place in a binary search tree
+ where this FILE:SECTION should be inserted for wild statement WILD where
+ the spec SEC was the matching one. The tree is later linearized. */
static lang_section_bst_type **
-wild_sort_fast (lang_wild_statement_type *wild,
- struct wildcard_list *sec,
- lang_input_statement_type *file ATTRIBUTE_UNUSED,
- asection *section)
+wild_sort (lang_wild_statement_type *wild,
+ struct wildcard_list *sec,
+ lang_input_statement_type *file,
+ asection *section)
{
lang_section_bst_type **tree;
- tree = &wild->tree;
if (!wild->filenames_sorted
- && (sec == NULL || sec->spec.sorted == none))
+ && (sec == NULL || sec->spec.sorted == none
+ || sec->spec.sorted == by_none))
{
- /* Append at the right end of tree. */
- while (*tree)
- tree = &((*tree)->right);
- return tree;
+ /* We might be called even if _this_ spec doesn't need sorting,
+ in which case we simply append at the right end of tree. */
+ return wild->rightmost;
}
+ tree = &wild->tree;
while (*tree)
{
+ /* Sorting by filename takes precedence over sorting by section
+ name. */
+
+ if (wild->filenames_sorted)
+ {
+ const char *fn, *ln;
+ bool fa, la;
+ int i;
+ asection *lsec = (*tree)->section;
+
+ /* The PE support for the .idata section as generated by
+ dlltool assumes that files will be sorted by the name of
+ the archive and then the name of the file within the
+ archive. */
+
+ fa = file->the_bfd->my_archive != NULL;
+ if (fa)
+ fn = sort_filename (file->the_bfd->my_archive);
+ else
+ fn = sort_filename (file->the_bfd);
+
+ la = lsec->owner->my_archive != NULL;
+ if (la)
+ ln = sort_filename (lsec->owner->my_archive);
+ else
+ ln = sort_filename (lsec->owner);
+
+ i = filename_cmp (fn, ln);
+ if (i > 0)
+ { tree = &((*tree)->right); continue; }
+ else if (i < 0)
+ { tree = &((*tree)->left); continue; }
+
+ if (fa || la)
+ {
+ if (fa)
+ fn = sort_filename (file->the_bfd);
+ if (la)
+ ln = sort_filename (lsec->owner);
+
+ i = filename_cmp (fn, ln);
+ if (i > 0)
+ { tree = &((*tree)->right); continue; }
+ else if (i < 0)
+ { tree = &((*tree)->left); continue; }
+ }
+ }
+
+ /* Here either the files are not sorted by name, or we are
+ looking at the sections for this file. */
+
/* Find the correct node to append this section. */
if (compare_section (sec->spec.sorted, section, (*tree)->section) < 0)
tree = &((*tree)->left);
@@ -587,10 +649,10 @@ wild_sort_fast (lang_wild_statement_type *wild,
return tree;
}
-/* Use wild_sort_fast to build a BST to sort sections. */
+/* Use wild_sort to build a BST to sort sections. */
static void
-output_section_callback_fast (lang_wild_statement_type *ptr,
+output_section_callback_sort (lang_wild_statement_type *ptr,
struct wildcard_list *sec,
asection *section,
lang_input_statement_type *file,
@@ -611,9 +673,13 @@ output_section_callback_fast (lang_wild_statement_type *ptr,
node->section = section;
node->pattern = ptr->section_list;
- tree = wild_sort_fast (ptr, sec, file, section);
+ tree = wild_sort (ptr, sec, file, section);
if (tree != NULL)
- *tree = node;
+ {
+ *tree = node;
+ if (tree == ptr->rightmost)
+ ptr->rightmost = &node->right;
+ }
}
/* Convert a sorted sections' BST back to list form. */
@@ -626,7 +692,8 @@ output_section_callback_tree_to_list (lang_wild_statement_type *ptr,
if (tree->left)
output_section_callback_tree_to_list (ptr, tree->left, output);
- lang_add_section (&ptr->children, tree->section, tree->pattern, NULL,
+ lang_add_section (&ptr->children, tree->section, tree->pattern,
+ ptr->section_flag_list,
(lang_output_section_statement_type *) output);
if (tree->right)
@@ -882,6 +949,7 @@ analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
ptr->handler_data[2] = NULL;
ptr->handler_data[3] = NULL;
ptr->tree = NULL;
+ ptr->rightmost = &ptr->tree;
for (sec = ptr->section_list; sec != NULL; sec = sec->next)
{
@@ -2772,113 +2840,17 @@ lang_add_section (lang_statement_list_type *ptr,
new_section->pattern = pattern;
}
-/* PE puts the sort key in the input statement. */
-
-static const char *
-sort_filename (bfd *abfd)
-{
- lang_input_statement_type *is = bfd_usrdata (abfd);
- if (is->sort_key)
- return is->sort_key;
- return bfd_get_filename (abfd);
-}
-
-/* Handle wildcard sorting. This returns the lang_input_section which
- should follow the one we are going to create for SECTION and FILE,
- based on the sorting requirements of WILD. It returns NULL if the
- new section should just go at the end of the current list. */
-
-static lang_statement_union_type *
-wild_sort (lang_wild_statement_type *wild,
- struct wildcard_list *sec,
- lang_input_statement_type *file,
- asection *section)
-{
- lang_statement_union_type *l;
-
- if (!wild->filenames_sorted
- && (sec == NULL || sec->spec.sorted == none))
- return NULL;
-
- for (l = wild->children.head; l != NULL; l = l->header.next)
- {
- lang_input_section_type *ls;
-
- if (l->header.type != lang_input_section_enum)
- continue;
- ls = &l->input_section;
-
- /* Sorting by filename takes precedence over sorting by section
- name. */
-
- if (wild->filenames_sorted)
- {
- const char *fn, *ln;
- bool fa, la;
- int i;
-
- /* The PE support for the .idata section as generated by
- dlltool assumes that files will be sorted by the name of
- the archive and then the name of the file within the
- archive. */
-
- fa = file->the_bfd->my_archive != NULL;
- if (fa)
- fn = sort_filename (file->the_bfd->my_archive);
- else
- fn = sort_filename (file->the_bfd);
-
- la = ls->section->owner->my_archive != NULL;
- if (la)
- ln = sort_filename (ls->section->owner->my_archive);
- else
- ln = sort_filename (ls->section->owner);
-
- i = filename_cmp (fn, ln);
- if (i > 0)
- continue;
- else if (i < 0)
- break;
-
- if (fa || la)
- {
- if (fa)
- fn = sort_filename (file->the_bfd);
- if (la)
- ln = sort_filename (ls->section->owner);
-
- i = filename_cmp (fn, ln);
- if (i > 0)
- continue;
- else if (i < 0)
- break;
- }
- }
-
- /* Here either the files are not sorted by name, or we are
- looking at the sections for this file. */
-
- if (sec != NULL
- && sec->spec.sorted != none
- && sec->spec.sorted != by_none)
- if (compare_section (sec->spec.sorted, section, ls->section) < 0)
- break;
- }
-
- return l;
-}
-
/* Expand a wild statement for a particular FILE. SECTION may be
- NULL, in which case it is a wild card. */
+ NULL, in which case it is a wild card. This assumes that the
+ wild statement doesn't need any sorting (of filenames or sections). */
static void
-output_section_callback (lang_wild_statement_type *ptr,
- struct wildcard_list *sec,
- asection *section,
- lang_input_statement_type *file,
- void *output)
+output_section_callback_nosort (lang_wild_statement_type *ptr,
+ struct wildcard_list *sec ATTRIBUTE_UNUSED,
+ asection *section,
+ lang_input_statement_type *file ATTRIBUTE_UNUSED,
+ void *output)
{
- lang_statement_union_type *before;
lang_output_section_statement_type *os;
os = (lang_output_section_statement_type *) output;
@@ -2887,40 +2859,8 @@ output_section_callback (lang_wild_statement_type *ptr,
if (unique_section_p (section, os))
return;
- before = wild_sort (ptr, sec, file, section);
-
- /* Here BEFORE points to the lang_input_section which
- should follow the one we are about to add. If BEFORE
- is NULL, then the section should just go at the end
- of the current list. */
-
- if (before == NULL)
- lang_add_section (&ptr->children, section, ptr->section_list,
- ptr->section_flag_list, os);
- else
- {
- lang_statement_list_type list;
- lang_statement_union_type **pp;
-
- lang_list_init (&list);
- lang_add_section (&list, section, ptr->section_list,
- ptr->section_flag_list, os);
-
- /* If we are discarding the section, LIST.HEAD will
- be NULL. */
- if (list.head != NULL)
- {
- ASSERT (list.head->header.next == NULL);
-
- for (pp = &ptr->children.head;
- *pp != before;
- pp = &(*pp)->header.next)
- ASSERT (*pp != NULL);
-
- list.head->header.next = *pp;
- *pp = list.head;
- }
- }
+ lang_add_section (&ptr->children, section, ptr->section_list,
+ ptr->section_flag_list, os);
}
/* Check if all sections in a wild statement for a particular FILE
@@ -3231,23 +3171,22 @@ wild (lang_wild_statement_type *s,
{
struct wildcard_list *sec;
- if (s->handler_data[0]
- && s->handler_data[0]->spec.sorted == by_name
- && !s->filenames_sorted)
+ if (s->filenames_sorted || s->any_specs_sorted)
{
lang_section_bst_type *tree;
- walk_wild (s, output_section_callback_fast, output);
+ walk_wild (s, output_section_callback_sort, output);
tree = s->tree;
if (tree)
{
output_section_callback_tree_to_list (s, tree, output);
s->tree = NULL;
+ s->rightmost = &s->tree;
}
}
else
- walk_wild (s, output_section_callback, output);
+ walk_wild (s, output_section_callback_nosort, output);
if (default_common_section == NULL)
for (sec = s->section_list; sec != NULL; sec = sec->next)
@@ -4205,22 +4144,25 @@ update_wild_statements (lang_statement_union_type *s)
/* Don't sort .init/.fini sections. */
if (strcmp (sec->spec.name, ".init") != 0
&& strcmp (sec->spec.name, ".fini") != 0)
- switch (sec->spec.sorted)
- {
- case none:
- sec->spec.sorted = sort_section;
- break;
- case by_name:
- if (sort_section == by_alignment)
- sec->spec.sorted = by_name_alignment;
- break;
- case by_alignment:
- if (sort_section == by_name)
- sec->spec.sorted = by_alignment_name;
- break;
- default:
- break;
- }
+ {
+ switch (sec->spec.sorted)
+ {
+ case none:
+ sec->spec.sorted = sort_section;
+ break;
+ case by_name:
+ if (sort_section == by_alignment)
+ sec->spec.sorted = by_name_alignment;
+ break;
+ case by_alignment:
+ if (sort_section == by_name)
+ sec->spec.sorted = by_alignment_name;
+ break;
+ default:
+ break;
+ }
+ s->wild_statement.any_specs_sorted = true;
+ }
break;
case lang_constructors_statement_enum:
@@ -8248,7 +8190,9 @@ lang_process (void)
ldemul_after_check_relocs ();
- /* Update wild statements. */
+ /* Update wild statements in case the user gave --sort-section.
+ Note how the option might have come after the linker script and
+ so couldn't have been set when the wild statements were created. */
update_wild_statements (statement_list.head);
/* Run through the contours of the script and attach input sections
@@ -8362,12 +8306,15 @@ lang_add_wild (struct wildcard_spec *filespec,
{
struct wildcard_list *curr, *next;
lang_wild_statement_type *new_stmt;
+ bool any_specs_sorted = false;
/* Reverse the list as the parser puts it back to front. */
for (curr = section_list, section_list = NULL;
curr != NULL;
section_list = curr, curr = next)
{
+ if (curr->spec.sorted != none && curr->spec.sorted != by_none)
+ any_specs_sorted = true;
next = curr->next;
curr->next = section_list;
}
@@ -8383,6 +8330,7 @@ lang_add_wild (struct wildcard_spec *filespec,
new_stmt = new_stat (lang_wild_statement, stat_ptr);
new_stmt->filename = NULL;
new_stmt->filenames_sorted = false;
+ new_stmt->any_specs_sorted = any_specs_sorted;
new_stmt->section_flag_list = NULL;
new_stmt->exclude_name_list = NULL;
if (filespec != NULL)
diff --git a/ld/ldlang.h b/ld/ldlang.h
index b853cdbd45f..713c5282b55 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -384,6 +384,7 @@ struct lang_wild_statement_struct
lang_statement_header_type header;
const char *filename;
bool filenames_sorted;
+ bool any_specs_sorted;
struct wildcard_list *section_list;
bool keep_sections;
lang_statement_list_type children;
@@ -391,7 +392,7 @@ struct lang_wild_statement_struct
walk_wild_section_handler_t walk_wild_section_handler;
struct wildcard_list *handler_data[4];
- lang_section_bst_type *tree;
+ lang_section_bst_type *tree, **rightmost;
struct flag_info *section_flag_list;
};
diff --git a/ld/testsuite/ld-scripts/sort-file.d b/ld/testsuite/ld-scripts/sort-file.d
new file mode 100644
index 00000000000..01eb694c63f
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file.d
@@ -0,0 +1,18 @@
+#source: sort-file2.s
+#source: sort-file1.s
+#ld: -T sort-file.t
+#nm: -n
+
+# Check that SORT_BY_NAME on filenames works
+# the text sections should come in sorted order, the data
+# sections in input order. Note how we specifically pass
+# the object filenames in non-alphabetical order
+#...
+0[0-9a-f]* t infile1
+#...
+0[0-9a-f]* t infile2
+#...
+0[0-9a-f]* d data2
+#...
+0[0-9a-f]* d data1
+#pass
diff --git a/ld/testsuite/ld-scripts/sort-file.t b/ld/testsuite/ld-scripts/sort-file.t
new file mode 100644
index 00000000000..559a0009256
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file.t
@@ -0,0 +1,6 @@
+SECTIONS
+{
+ .text : { SORT_BY_NAME(*)(.text*) }
+ .data : { *(.data*) }
+ /DISCARD/ : { *(.*) }
+}
diff --git a/ld/testsuite/ld-scripts/sort-file1.s b/ld/testsuite/ld-scripts/sort-file1.s
new file mode 100644
index 00000000000..23777a8591c
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file1.s
@@ -0,0 +1,6 @@
+ .text
+infile1:
+ .long 0
+ .data
+data1:
+ .long 0
diff --git a/ld/testsuite/ld-scripts/sort-file2.s b/ld/testsuite/ld-scripts/sort-file2.s
new file mode 100644
index 00000000000..cf4bb1f9f1a
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file2.s
@@ -0,0 +1,6 @@
+ .text
+infile2:
+ .long 0
+ .data
+data2:
+ .long 0
--
2.36.1
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Only use wild_sort_fast
2022-11-25 16:04 [PATCH] Only use wild_sort_fast Michael Matz
@ 2022-11-28 2:16 ` Alan Modra
0 siblings, 0 replies; 2+ messages in thread
From: Alan Modra @ 2022-11-28 2:16 UTC (permalink / raw)
To: Michael Matz; +Cc: binutils
On Fri, Nov 25, 2022 at 04:04:51PM +0000, Michael Matz via Binutils wrote:
> there's no reason why the tree-based variant can't always be used
> when sorting is required, it merely needs to also support filename
> sorting and have a fast path for insertion at end (aka rightmost tree
> leaf).
>
> The filename sorting isn't tested anywhere and the only scripttempl
> that uses it is avr (for 'SORT(*)(.ctors)'), and I believe even there it
> was a mistake. Either way, this adds a testcase for filename sorting as
> well.
>
> Then the non-BST based sorting can be simplified to only support
> the fast case of no sorting required at all (at the same time renaming
> the two variants to _sort and _nosort).
> ---
> Regtested on Alans target-list. It doesn't bring any measurable speedup,
> but I like the code better: if sorting is needed there should be a single
> reasonably quick sorting method, not two mediocre ones (one incomplete,
> the other slow).
>
> Okay for master?
OK.
--
Alan Modra
Australia Development Lab, IBM
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-11-28 2:16 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-11-25 16:04 [PATCH] Only use wild_sort_fast Michael Matz
2022-11-28 2:16 ` Alan Modra
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).