[LLD] Warn if non-alloc sections occur before alloc sections in linker scripts

[kschwarz]

Summary

The program header creation logic depends on a strict separation of alloc and non-alloc output sections.
Declaring a non-alloc output section in linker scripts has the effect that no PT_LOAD header will be created for alloc sections coming afterwards. We should warn the user if this is detected.

This fixes https://bugs.llvm.org/show_bug.cgi?id=37607

[grimar]

Since it fixes https://bugs.llvm.org/show_bug.cgi?id=37607,
which is about ARM, I added Peter as ARM expert.

Currently, LLD places the sections in the order specified by the script,
what works for most of the cases and sounds simple.
It is perhaps also fine to sort the sections to place allocatable first (this patch),
but looking at the issue I wonder what is the problem to fix the script instead?
I think it is the script issue first of all, would not it be more correct action?

[kschwarz]

The problem was discovered within an ARM specific linker script, however it is target independent (see added testcases)
I think the existing test in test/ELF/linkerscript/sections.s is even incomplete, because it only checks the section order, not the created program headers.
If checked, you will see that there is no PT_LOAD for .data and .text.
I wouldn't say its the issue of the script, I think its an issue of a missing spec. We claim to support the same linker scripts as GNU, but behave differently in certain undocumented situations, which can lead to surprising results.

[peter.smith]

Interesting. This seems to be one of the situations where linker scripts aren't specified well enough to give a definitive answer of what a linker should do.

The approach of sorting non-alloc after alloc matches the linker's implicit rules but is it really respecting the SECTIONS command. ld.bfd appears to keep the order of the section headers, even assigning the non-alloc sections an address as if they were in the same place as given in the linker script. However it gives them 0 size when calculating the address of the next alloc section, and sorts the non alloc sections in the file so that the non-alloc sections don't appear in PT_LOAD program headers. This seems to match the intention of the script more closely but whether this makes any significant difference for a real program to depend on I don't know.

In an ideal world people wouldn't write linker scripts that mix non-alloc with alloc but I think it is probably unavoidable and we should either try and fix by sorting the sections or at least giving a warning/error message if we need scripts to conform to it. I personally think sorting the sections is probably as much code as diagnosing an error and is close enough to gold and bfd behaviour to be good enough.

On the Arm specific side. The SHT_ARM_ATTRIBUTES section was intended only for Objects. The presence or absence of the section in an executable or shared object is at the discretion of the linker, so a portable program should never rely on its presence in the ELF file. Initially LLD just discarded it but I found out that eglibc that was used on Ubuntu Trusty (14.04) scanned shared objects section header table for it in order to determine the float-abi; it really shouldn't have been doing that but if we were to make LLD work on Trusty we'd need to put it in the ELF file.

test/ELF/linkerscript/sections.s

28 ↗

(On Diff #160524)

The comment here implies that LLD used to sort SHF_ALLOC before non SHF_ALLOC. A dig in the logs shows that in r281778 this was the intention but it was later modified, possibly by r302903 but it could have been earlier.

[grimar]

I think I agree with Peter that we either need to report an error or warning or to support this.
Since the complexity is probably the same, I am ok with this patch. (Though I think such scripts are just broken).

ELF/Writer.cpp

1312

The name of variable should be uppercase. I think it should be CompareXXX for consistency with other predicates.

1316

I am not sure the comparator is correct.
It should return true if the first argument is less than second.
But your version would always return false if you have 2 alloc sections.

I think it should be something like:

auto *A = dyn_cast<OutputSection>(ACmd);
auto *B = dyn_cast<OutputSection>(BCmd);
if (!A || !B)
  return false;

bool IsAllocA = A->Flags & SHF_ALLOC;
bool IsAllocB = B->Flags & SHF_ALLOC;
if (IsAllocA != IsAllocB)
  return IsAllocA;

return A->SectionIndex < B->SectionIndex;

test/ELF/linkerscript/Inputs/nonalloc.s

10 ↗

(On Diff #160524)

I think you do not need this input. You can use echo to inline it,
see for example:
https://github.com/llvm-mirror/lld/blob/master/test/ELF/linkerscript/bss-fill.test

I would expect something with less data instructions like
echo '.section .text,"ax"; .quad 0; .section .data,"aw"; .long 0; .section .other,""; .byte 0; '

test/ELF/linkerscript/nonalloc.test

30 ↗

(On Diff #160524)

Please add a new line.

test/ELF/linkerscript/sections.s

29 ↗

(On Diff #160524)

This comment needs an update then.

[grimar]

ELF/Writer.cpp

1316

Please ignore my comment above. Your version should be fine for stable_sort. I would change it a bit though:

if (auto *A = dyn_cast<OutputSection>(ACmd))
  if (auto *B = dyn_cast<OutputSection>(BCmd))
     if ((A->Flags & SHF_ALLOC) != (B->Flags & SHF_ALLOC))
       return ((A->Flags & SHF_ALLOC) != 0)
return false;

[kschwarz]

Issueing a warning in this case would also be fine for me. The problem occured in a much larger context with nested includes of several linker scripts, so it was not obvious which directive was an issue, but the ELF was missing several expected program headers.

I think we do not have to support the exact same linker scripts as GNU, but we should try to inform the user that we do not support specific things (like it is done when setting the location counter backwards).

So would you prefer a warning instead of messing with the order of sections?

test/ELF/linkerscript/Inputs/nonalloc.s

10 ↗

(On Diff #160524)

I thought I read somewhere that echo'ing should be avoided in new tests, but that could be wrong. Will update this test.

[grimar]

In D50688#1198810, @kschwarz wrote:

Issueing a warning in this case would also be fine for me.
...
So would you prefer a warning instead of messing with the order of sections?

I have no strong feeling, but:

Giving a warning is less intrusive and gives a chance to report a possible issue in the script,
so if we have a choice to not support that then I would go this way perhaps.
(I think Writer<ELFT>::checkSections() is probably the right place to do the check)

test/ELF/linkerscript/Inputs/nonalloc.s

10 ↗

(On Diff #160524)

That is true, we are trying to avoid multiple echo'ing, but single line echo is better than additional input file for readability.
Many of our *.test files have it, so it is fine.

[kschwarz]

I updated the patch to warn the user if we detect that alloc/non-alloc sections were mixed in linker scripts.
The newly added test case demonstrates the problem.
If the .text section is not specified in the script, the existing logic would place it before any non-alloc section.

[grimar]

ELF/Writer.cpp

1616

In according to LLD code style, you should add {} here and above, because else below use them.

1621

I think Writer<ELFT>::checkSections() is the correct place for this code. Can it be moved there?

(I also think you'll be able to simplify the conditions a bit, to remove OS->SectionIndex check).

test/ELF/linkerscript/non-alloc.test

12

I would clarify a bit: should be placed -> should be placed in script.

[ruiu]

Sorry for the belated response. This might be a silly question, but if lld creates a broken executable when non-alloc sections are laid out before alloc sections by a linker script, isn't it just a bug?

[kschwarz]

At least it is a restriction of what we support in linker scripts, but I would also consider this a bug.

A solution would be to sort also the linker script supplied sections (as done in the previous version of the patch). However, as pointed out by Peter, its not exactly matching bfd's behaviour.
Keeping the section order given by the linker script and still allow interleaving of alloc/non-alloc sections complicates (at least) the creation of program headers even further.
Would a patch in that direction be acceptable?

ELF/Writer.cpp

1621

In checkSections we do not know anymore which output sections were added via linkerscript and which are synthetic sections. The existing algorithm will group the orphan sections by "category" (in findOrphanPos), which will group all non-alloc synthetic sections behind the first non-alloc linker script section. Thus, we would issue warnings for synthetic instead of user specified sections most of the time.

[bd1976llvm]

Hi. Sorry to be slow to comment on this.

This seems related to D34204 (Allow non-alloc sections to be assigned to segments). You will need to follow the email thread as most of the comments were not on the phabricator review.

I find the gnu linker script docs difficult to read in this area. In some places they use the term segment as an alias for program header. In other places segment seems to indicate a region of process address space. The docs state that certain segments are "segments of memory which the system loader will load from the file" and only SHF_ALLOC sections contribute to these segments. However it does not state which segments these are - apart from that loadable segments (PT_LOAD) are included in the set. This limitation means that you can't define custom PHDR types that are treated as "segments of memory which the system loader will load from the file".

I believe that linker scripts are older than elf and therefore the two do not always fit nicely together. Mixing alloc and non-alloc sections in a PT_LOAD is one of those things that makes sense in linker scripts but not in ELF. Another example is that Linker scripts allow you combine sections by name (ignoring section flags).

I would like to see the simplest approach here. To me the simplest approach is that linker scripts ideally should be as explicit as possible. For example, if you have a linker script that assigns a set of sections to a PHDR:

PHDRS {my_phdr PT_LOAD FLAGS(0x4);}
SECTIONS { .mine : { *(.mine) } : my_phdr }

Then the linker should simply concatenate any matching input sections and assign them to the specified PHDR. This should override any flags of the input sections including SHF_ALLOC. In my opinion it is very confusing to change the behavior of the above script based on whether the input sections are SHF_ALLOC or not. Warning or erroring if any of the input sections were non-shf-alloc would catch any mistakes.

This simple approach is a difference in behavior vs the gnu linkers, but quite possibly there are no real links that would be broken by this difference in behavior as, anecdotally, I think that mixing SHF_ALLOC and non-SHF_ALLOC sections is rare and use of the PHDRS command is also rare.

Wrapping up I suppose the important thing is to see how hard it would be to keep the current easy to understand linker script placement behavior and to fix https://bugs.llvm.org/show_bug.cgi?id=37607 by adjusting PHDR creation to create the appropriate PHDRs for that testcase. If that is easy to do then that would be more appealing to me.

[kschwarz]

Thanks for the link! However, I'm not sure if this is really related. The issue there was that a non-alloc section should be placed into a program header explicitly via PHDRS commands, which might be a valid use case.

In "automatic" program header creation, a non-alloc section will never appear in a program header, but unfortunately the header creation, orphan placement and address assignment all rely on the strict separation of alloc and non-alloc sections and will produce a broken ELF for mixed sections.

Since non-alloc sections can only be put under a program header via PHDRS commands, I think issuing a warning if no PHDRS commands are given and alloc/non-alloc sections are mixed and not touching the rest of the code should be okay.
What do you think?

[bd1976llvm]

In D50688#1207394, @kschwarz wrote:

Thanks for the link! However, I'm not sure if this is really related. The issue there was that a non-alloc section should be placed into a program header explicitly via PHDRS commands, which might be a valid use case.

It is certainly a use case that is important to our customers. As I remember that change resulted in the ability to mix non-alloc and alloc output sections in a PHDR using the PHDRS command. If we are going to fix this bug by moving to compatibility with gnu-ld for non-shf-alloc sections then we shouldn't allow the assignment of non-shf-alloc sections to segments that represent "segments of memory which the system loader will load from the file" e.g. PT_LOAD segments even via the PHDRS command. In other words we should do something like your sorting fix in both the automatic PHDR case and the PHDRS command case.

In "automatic" program header creation, a non-alloc section will never appear in a program header, but unfortunately the header creation, orphan placement and address assignment all rely on the strict separation of alloc and non-alloc sections and will produce a broken ELF for mixed sections.

Since non-alloc sections can only be put under a program header via PHDRS commands, I think issuing a warning if no PHDRS commands are given and alloc/non-alloc sections are mixed and not touching the rest of the code should be okay.
What do you think?

I was (very hopefully) thinking that header creation, orphan placement and address assignment could be adjusted to cope with a mixture of alloc and non-alloc without too much turbulence... but I haven't looked into it so it may be difficult. If we don't change the current code and LLD is going to create a broken elf in these cases then maybe we should actually error rather than warn?

ELF/Writer.cpp

auto NonScriptI = std::find_if(I, E, [](BaseCommand *Base) {
     if (auto *Sec = dyn_cast<OutputSection>(Base))
       return Sec->SectionIndex == UINT32_MAX;
     return false;
   });
 
   // Sort the orphan sections.
   std::stable_sort(NonScriptI, E, compareSections);
 
   // As a horrible special case, skip the first . assignment if it is before any
   // section. We do this because it is common to set a load address by starting
   // the script with ". = 0xabcd" and the expectation is that every section is
   // after that.
   auto FirstSectionOrDotAssignment =
       std::find_if(I, E, [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
   if (FirstSectionOrDotAssignment != E &&
       isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
     ++FirstSectionOrDotAssignment;
   I = FirstSectionOrDotAssignment;
 
   while (NonScriptI != E) {
     auto Pos = findOrphanPos<ELFT>(I, NonScriptI);
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   sortSections();
 
   // Now that we have the final list, create a list of all the
   // OutputSections for convenience.
   for (BaseCommand *Base : Script->SectionCommands)
     if (auto *Sec = dyn_cast<OutputSection>(Base))
       OutputSections.push_back(Sec);
 
+  // Check that no non-alloc sections were specified before any alloc sections
+  // in linker scripts. Otherwise we might have problems creating correct
+  // PT_LOAD headers.
+  OutputSection *NonAllocSec = nullptr;
+  for (OutputSection *OS : OutputSections)
+    if (!(OS->Flags & SHF_ALLOC) && (OS->SectionIndex != UINT32_MAX))
+      NonAllocSec = OS;
+    else if (NonAllocSec && (OS->SectionIndex != UINT32_MAX)) {
+      warn("non-alloc section " + NonAllocSec->Name + " should be specified after "
+           "alloc sections in linker scripts");
+      NonAllocSec = nullptr;
+    }
+
   // Ensure data sections are not mixed with executable sections when
   // -execute-only is used.
   if (Config->ExecuteOnly)
     for (OutputSection *OS : OutputSections)
       if (OS->Flags & SHF_EXECINSTR)
         for (InputSection *IS : getInputSections(OS))
           if (!(IS->Flags & SHF_EXECINSTR))
             error("-execute-only does not support intermingling data and code");

test/ELF/linkerscript/non-alloc.test

+# REQUIRES: x86
+# RUN: echo '.data; .quad 0;.section .other; .short 0; .text; nop' \
+# RUN: | llvm-mc -filetype=obj -triple=x86_64-unknown-linux - -o %t.o
+# RUN: not ld.lld -o %t --script %s %t.o 2>&1 | FileCheck %s
+
+SECTIONS {
+ .data  : { *(.data)  }
+ .other : { *(.other) }
+ .text  : { *(.text)  }
+}
+
+# .other is a non-alloc section and therefore should be placed after .text.
+# Expect a warning for this section as it prevents the creation of correct
+# PT_LOAD headers.
+
+# CHECK: warning: non-alloc section .other should be specified after alloc sections in linker scripts
+# CHECK: error: section .data virtual address range overlaps with .text