Put SHF_ALLOC sections first, even with linker scripts.

This matches gold and bfd, and is pretty much required by some linker
scripts. They end with commands like

foo   0 : { *(bar) }

if we put any SHF_ALLOC sections after they can have an address that
is too low.

llvm-svn: 281778

4 files changed, 54 insertions, 30 deletions

diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index 066c4eb0f8d..30d6a9d819b 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -453,15 +453,42 @@ template <class ELFT> void LinkerScript<ELFT>::assignAddresses() {
   // We place orphan sections at end of file.
   // Other linkers places them using some heuristics as described in
   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
+
+  // The OutputSections are already in the correct order.
+  // This loops creates or moves commands as needed so that they are in the
+  // correct order.
+  int CmdIndex = 0;
   for (OutputSectionBase<ELFT> *Sec : *OutputSections) {
     StringRef Name = Sec->getName();
-    if (getSectionIndex(Name) == INT_MAX)
-      Opt.Commands.push_back(llvm::make_unique<OutputSectionCommand>(Name));
+
+    // Find the last spot where we can insert a command and still get the
+    // correct order.
+    auto CmdIter = Opt.Commands.begin() + CmdIndex;
+    auto E = Opt.Commands.end();
+    while (CmdIter != E && !isa<OutputSectionCommand>(**CmdIter)) {
+      ++CmdIter;
+      ++CmdIndex;
+    }
+
+    auto Pos =
+        std::find_if(CmdIter, E, [&](const std::unique_ptr<BaseCommand> &Base) {
+          auto *Cmd = dyn_cast<OutputSectionCommand>(Base.get());
+          return Cmd && Cmd->Name == Name;
+        });
+    if (Pos == E) {
+      Opt.Commands.insert(CmdIter,
+                          llvm::make_unique<OutputSectionCommand>(Name));
+    } else {
+      // If linker script lists alloc/non-alloc sections is the wrong order,
+      // this does a right rotate to bring the desired command in place.
+      auto RPos = make_reverse_iterator(Pos + 1);
+      std::rotate(RPos, RPos + 1, make_reverse_iterator(CmdIter));
+    }
+    ++CmdIndex;
   }
 
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = getHeaderSize();
-  uintX_t MinVA = std::numeric_limits<uintX_t>::max();
 
   for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get())) {
@@ -483,13 +510,17 @@ template <class ELFT> void LinkerScript<ELFT>::assignAddresses() {
     if (Cmd->AddrExpr)
       Dot = Cmd->AddrExpr(Dot);
 
-    MinVA = std::min(MinVA, Dot);
     assignOffsets(Cmd);
   }
 
-  for (OutputSectionBase<ELFT> *Sec : *OutputSections)
-    if (!(Sec->getFlags() & SHF_ALLOC))
+  uintX_t MinVA = std::numeric_limits<uintX_t>::max();
+  for (OutputSectionBase<ELFT> *Sec : *OutputSections) {
+    if (Sec->getFlags() & SHF_ALLOC)
+      MinVA = std::min(MinVA, Sec->getVA());
+    else
       Sec->setVA(0);
+  }
+
   uintX_t HeaderSize =
       Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
   if (HeaderSize > MinVA)
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 4260e4220e8..e58c4b6707b 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -437,10 +437,6 @@ static bool compareSections(OutputSectionBase<ELFT> *A,
                             OutputSectionBase<ELFT> *B) {
   typedef typename ELFT::uint uintX_t;
 
-  int Comp = Script<ELFT>::X->compareSections(A->getName(), B->getName());
-  if (Comp != 0)
-    return Comp < 0;
-
   uintX_t AFlags = A->getFlags();
   uintX_t BFlags = B->getFlags();
 
@@ -451,6 +447,10 @@ static bool compareSections(OutputSectionBase<ELFT> *A,
   if (AIsAlloc != BIsAlloc)
     return AIsAlloc;
 
+  int Comp = Script<ELFT>::X->compareSections(A->getName(), B->getName());
+  if (Comp != 0)
+    return Comp < 0;
+
   // We don't have any special requirements for the relative order of
   // two non allocatable sections.
   if (!AIsAlloc)
@@ -971,15 +971,8 @@ std::vector<PhdrEntry<ELFT>> Writer<ELFT>::createPhdrs() {
   Phdr RelRo(PT_GNU_RELRO, PF_R);
   Phdr Note(PT_NOTE, PF_R);
   for (OutputSectionBase<ELFT> *Sec : OutputSections) {
-    // Skip non alloc section.
-    // The reason we skip instead of just breaking out of the loop is the way
-    // we implement linker scripts. We always put the linker script sections
-    // first, which means that a non alloc section can be in the middle of the
-    // file. Continuing in here means it will be included in a PT_LOAD anyway.
-    // We should probably sort sections based of SHF_ALLOC even if they are
-    // on linker scripts.
     if (!(Sec->getFlags() & SHF_ALLOC))
-      continue;
+      break;
 
     // If we meet TLS section then we create TLS header
     // and put all TLS sections inside for futher use when
diff --git a/lld/test/ELF/linkerscript/non-alloc.s b/lld/test/ELF/linkerscript/non-alloc.s
index b830c74ea21..0ad1a7470aa 100644
--- a/lld/test/ELF/linkerscript/non-alloc.s
+++ b/lld/test/ELF/linkerscript/non-alloc.s
@@ -1,13 +1,12 @@
 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
 
-# RUN: echo "SECTIONS { .foo : {*(foo)} }" > %t.script
+# RUN: echo "SECTIONS { .foo 0 : {*(foo)} }" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t -shared
 # RUN: llvm-readobj -elf-output-style=GNU -s -l %t1 | FileCheck %s
 
-# Test that we create all necessary PT_LOAD. It is a harmless oddity that
-# foo ends in a PT_LOAD. We use to stop at the first non-alloc, causing
-# us to not create PT_LOAD for linker generated sections.
+# Test that we create all necessary PT_LOAD. We use to stop at the first
+# non-alloc, causing us to not create PT_LOAD for linker generated sections.
 
 # CHECK: Program Headers:
 # CHECK-NEXT:  Type
@@ -19,7 +18,7 @@
 # CHECK:      Section to Segment mapping:
 # CHECK-NEXT:  Segment Sections...
 # CHECK-NEXT:   00
-# CHECK-NEXT:   01     .foo .dynsym .hash .dynstr
+# CHECK-NEXT:   01     .dynsym .hash .dynstr
 # CHECK-NEXT:   02     .text
 # CHECK-NEXT:   03     .dynamic
 
diff --git a/lld/test/ELF/linkerscript/sections.s b/lld/test/ELF/linkerscript/sections.s
index b68dac765a7..d899cf8333a 100644
--- a/lld/test/ELF/linkerscript/sections.s
+++ b/lld/test/ELF/linkerscript/sections.s
@@ -25,7 +25,8 @@
 # SEC-DEFAULT: 7 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-DEFAULT: 8 .strtab       00000008 {{[0-9a-f]*}}
 
-# Sections are put in order specified in linker script.
+# Sections are put in order specified in linker script, other than alloc
+# sections going first.
 # RUN: echo "SECTIONS { \
 # RUN:          .bss : { *(.bss) } \
 # RUN:          other : { *(other) } \
@@ -41,12 +42,12 @@
 #           Idx Name          Size
 # SEC-ORDER: 1 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-ORDER: 2 other         00000003 {{[0-9a-f]*}} DATA
-# SEC-ORDER: 3 .shstrtab     00000002 {{[0-9a-f]*}}
-# SEC-ORDER: 4 .shstrtab     00000032 {{[0-9a-f]*}}
-# SEC-ORDER: 5 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-ORDER: 6 .strtab       00000008 {{[0-9a-f]*}}
-# SEC-ORDER: 7 .data         00000020 {{[0-9a-f]*}} DATA
-# SEC-ORDER: 8 .text         0000000e {{[0-9a-f]*}} TEXT DATA
+# SEC-ORDER: 3 .data         00000020 {{[0-9a-f]*}} DATA
+# SEC-ORDER: 4 .text         0000000e {{[0-9a-f]*}} TEXT DATA
+# SEC-ORDER: 5 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-ORDER: 6 .shstrtab     00000032 {{[0-9a-f]*}}
+# SEC-ORDER: 7 .symtab       00000030 {{[0-9a-f]*}}
+# SEC-ORDER: 8 .strtab       00000008 {{[0-9a-f]*}}
 
 # .text and .data have swapped names but proper sizes and types.
 # RUN: echo "SECTIONS { \