SORT and multiple patterns in an input section description

[Alan Modra]

On Tue, Nov 10, 2020 at 10:44:44PM -0800, Fangrui Song wrote:
> On 2020-11-11, Alan Modra wrote:
> > On Mon, Nov 09, 2020 at 08:16:55PM -0800, Fangrui Song wrote:
> > > I am trying to understand the order of input sections within an input
> > > section description.
> > > 
> > > For .foo : { *(.a .b .c) }
> > > the order in the output section matches the input order. If
> > > file1 has .c .b .a, the order will be .c .b .a
> > > 
> > > 
> > > For .abc : { *(SORT(.foo.*) .bar.*) } and
> > > 
> > >   .section .bar.4,"a"
> > >    .quad 4
> > >   .section .foo.2,"a"
> > >    .quad 2
> > >   .section .foo.3,"a"
> > >    .quad 3
> > >   .section .bar.6,"a"
> > >    .quad 6
> > >   .section .bar.5,"a"
> > >    .quad 5
> > >   .section .foo.1,"a"
> > >    .quad 1
> > > 
> > > the order is 412365, i.e. ld apparently moves .foo.1 with the .foo.2/.foo.3 group.
> > > This is sorta surprising. Is there a rule explaining this behavior?
> > 
> > No, and I don't want to try to explain it, except to say that "*(A B)"
> > is quite deliberately different from "*(A) *(B)", and that difference
> > is explained in the ld info doc.  Use the source if you want more
> > detail.
> 
> :(

It's not that I don't want to say, it's that I'm not sure myself
without looking at the code in detail.  And this code is quite tricky
even ignoring the fast sorting functions.

> > > A more complex example is
> > > .init_array : { KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*) SORT_BY_INIT_PRIORITY(.ctors.*))) }
> > > 
> > > I expected that all .init_array.* precede all .ctors.*
> > 
> > If that was your expectation, then you would write
> > 
> > .init_array : { KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*)))
> >                KEEP (*(SORT_BY_INIT_PRIORITY(.ctors.*))) }
> 
> My current observation for the section patterns:
> 
> * The first SORT* is respected.
> * Other SORT* are as if merged with the first SORT* (ok, I can accept this, though not too happy with the peculiarity..)
> * Other SORT*'s sorting methods are ignored (this is very confusing)
> 
> So
> KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*)
> SORT_BY_INIT_PRIORITY(.ctors.*))) conceptually may work like
> KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*))) (the syntax is not accepted)

Yes, that sounds about right.

> KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*) SORT_BY_ALIGNMENT(.ctors.*)))
> and
> KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*) SORT(.ctors.*))) have the same
> effect...

No, I don't think that is true.  I think you'll see some really weird
sorting if you try that out with enough variations.

Here's what I think happens, but bear in mind that I may be wrong as
I'm writing this mostly by recollection from figuring out the linker
code a long time ago:

For each filename(section_list) pattern the linker builds a list of
matching sections.  So for
  *(SORT_BY_INIT_PRIORITY(.init_array.*) SORT_BY_ALIGNMENT(.ctors.*))
we'll build a list of sections that match either .init_array.* or
.ctors.* by examining object files in linker command line order.
Sections will be added to the list under control of their sorting
function.  That works by traversing the current list of sections to
find the first one that sorts after the new section under
consideration.  The new section is then inserted before it, or if no
section sorts after the new section, at the end of the list.

-- 
Alan Modra
Australia Development Lab, IBM