From af31506c31a59a6edbb13498d6075fa704b801cd Mon Sep 17 00:00:00 2001 From: Michael Matz Date: Thu, 10 Nov 2022 16:06:20 +0100 Subject: [PATCH] Only use wild_sort_fast 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). --- 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 5fc55dcd5dd..336eea913c7 100644 --- a/ld/ldlang.c +++ b/ld/ldlang.c @@ -556,30 +556,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); @@ -590,10 +652,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, @@ -614,9 +676,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. */ @@ -629,7 +695,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) @@ -887,6 +954,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) { @@ -2777,113 +2845,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; @@ -2892,40 +2864,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 @@ -3236,23 +3176,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) @@ -4210,22 +4149,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: @@ -8253,7 +8195,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 @@ -8367,12 +8311,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; } @@ -8388,6 +8335,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.30.2