[ELF] - Get rid of SectionOrder array.

[grimar]

Summary

SectionOrder vector was a part of LinkerScript class.

After commit of D18499 it can be removed because Locations vector
contains the same information and SectiorOrder is just a subset.

[grimar]

ELF/LinkerScript.cpp

172 ↗

(On Diff #53927)

So compareSections() is used to sort OutputSections.
Later linkerscript uses this order in fixupLocations() to add orphans.

Therefore Locations vector is updated at the very end,
before actual address assignment.

Another variant would be to call fixupLocations() earlier, before compareSections().
Then orpan order would be script driven, but will add some code complexity as will need export of
fixupLocations() method.

I like both approach. First (this patch) for simple code, second for giving
all cards to script to control orphans order.

[grimar]

This patch also fixes the section indexes. We should keep OutputSections order the same as Locations order because of code that assigns them:

unsigned I = 1;
for (OutputSectionBase<ELFT> *Sec : OutputSections) {
  Sec->SectionIndex = I++;
  Sec->setSHName(Out<ELFT>::ShStrTab->addString(Sec->getName()));
}

[• rafael]

I think this is fine, but I will let Rui have the final say on liker script stuff.

[ruiu]

LGTM with a nit.

ELF/LinkerScript.cpp

93 ↗

(On Diff #53927)

The return value will never overflow in reality, so let's use just int instead of uint32_t. Then you can report the absent key as just -1 instead of UINT32_MAX.

[grimar]

ELF/LinkerScript.cpp

93 ↗

(On Diff #53927)

Doing that will require changes that might overcomplicate the current
code of compareSections():

uint32_t I = getSectionOrder(A);
uint32_t J = getSectionOrder(B);
if (I == (uint32_t)-1 && J == (uint32_t)-1)
  return 0;
return I < J ? -1 : 1;

For example if I has some order, but J does not then:
Since J is uint32_t (and == UINT32_MAX) then I < J will work as expected, placing A before B.

If we switch to int then I guess something like next should be written
(and it does not seem to worth that):

int I = getSectionOrder(A);
int J = getSectionOrder(B);
if (I == -1 && J == -1)
  return 0;
if (I == -1)
  return 1;
if (J == -1)
  return -1;
return I < J ? -1 : 1;

So I committed without that change for now.

[ruiu]

ELF/LinkerScript.cpp

172 ↗

(On Diff #53927)

Makes sense, but in that case (uint32_t)-1 is not an error code, but it actually mean the sorting order of the given section name (e.g. the lowest priority). In that case (uint32_t)-1 looks odd. Please use UINT32_MAX instead because it's what you really mean. Also it needs a comment about when UINT32_MAX returns.

Also, there's no reason to use uint32_t. I'd use int and INT_MAX.

lld/trunk/ELF/LinkerScript.h

struct SectionsCommand {
   StringRef SectionName;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
-  // Output sections are sorted by this order.
-  std::vector<StringRef> SectionOrder;
-
   // Section fill attribute for each section.
   llvm::StringMap<std::vector<uint8_t>> Filler;
 
   // Used to assign addresses to sections.
   std::vector<SectionsCommand> Commands;
 
   bool DoLayout = false;
 
   llvm::BumpPtrAllocator Alloc;
 };
 
 extern ScriptConfiguration *ScriptConfig;
 
 // This is a runner of the linker script.
 template <class ELFT> class LinkerScript {
 public:
   StringRef getOutputSection(InputSectionBase<ELFT> *S);
   ArrayRef<uint8_t> getFiller(StringRef Name);
   bool isDiscarded(InputSectionBase<ELFT> *S);
   bool shouldKeep(InputSectionBase<ELFT> *S);
   void assignAddresses(std::vector<OutputSectionBase<ELFT> *> &S);
   int compareSections(StringRef A, StringRef B);
+  uint32_t getSectionOrder(StringRef Name);
 
 private:
   SectionRule *find(InputSectionBase<ELFT> *S);
 
   ScriptConfiguration &Opt = *ScriptConfig;
 };
 
 // Variable template is a C++14 feature, so we can't template
 // a global variable. Use a struct to workaround.
 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/LinkerScript.cpp

void LinkerScript<ELFT>::assignAddresses(
 
   // Orphan sections are sections present in the input files which
   // are not explicitly placed into the output file by the linker script.
   // 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.
   for (OutputSectionBase<ELFT> *Sec : Sections) {
     StringRef Name = Sec->getName();
-    auto I = std::find(Opt.SectionOrder.begin(), Opt.SectionOrder.end(), Name);
-    if (I == Opt.SectionOrder.end())
+    if (getSectionOrder(Name) == (uint32_t)-1)
       Opt.Commands.push_back({SectionKind, {}, Name});
   }
 
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   uintX_t ThreadBssOffset = 0;
   uintX_t VA =
       Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
 

 template <class ELFT>
 ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
   auto I = Opt.Filler.find(Name);
   if (I == Opt.Filler.end())
     return {};
   return I->second;
 }
 
-// A compartor to sort output sections. Returns -1 or 1 if both
-// A and B are mentioned in linker scripts. Otherwise, returns 0
-// to use the default rule which is implemented in Writer.cpp.
+template <class ELFT>
+uint32_t LinkerScript<ELFT>::getSectionOrder(StringRef Name) {
+  auto Begin = Opt.Commands.begin();
+  auto End = Opt.Commands.end();
+  auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
+    return N.Kind == SectionKind && N.SectionName == Name;
+  });
+  return I == End ? (uint32_t)-1 : (I - Begin);
+}
+
+// A compartor to sort output sections. Returns -1 or 1 if
+// A or B are mentioned in linker script. Otherwise, returns 0.
 template <class ELFT>
 int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
-  auto E = Opt.SectionOrder.end();
-  auto I = std::find(Opt.SectionOrder.begin(), E, A);
-  auto J = std::find(Opt.SectionOrder.begin(), E, B);
-  if (I == E || J == E)
+  uint32_t I = getSectionOrder(A);
+  uint32_t J = getSectionOrder(B);
+  if (I == (uint32_t)-1 && J == (uint32_t)-1)
     return 0;
   return I < J ? -1 : 1;
 }
 
 // Returns true if S matches T. S can contain glob meta-characters.
 // The asterisk ('*') matches zero or more characacters, and the question
 // mark ('?') matches one character.
 static bool matchStr(StringRef S, StringRef T) {
while (!Error) {
     Cmd.Expr.push_back(Tok);
   }
   if (Cmd.Expr.empty())
     error("error in location counter expression");
 }
 
 void ScriptParser::readOutputSectionDescription() {
   StringRef OutSec = next();
-  Opt.SectionOrder.push_back(OutSec);
   Opt.Commands.push_back({SectionKind, {}, OutSec});
   expect(":");
   expect("{");
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
       readSectionPatterns(OutSec, false);
     } else if (Tok == "KEEP") {

lld/trunk/test/ELF/linkerscript-orphans.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: echo "SECTIONS { .writable : { *(.writable) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -section-headers %t.out | \
+# RUN:   FileCheck -check-prefix=TEXTORPHAN %s
+
+# RUN: echo "SECTIONS { .text : { *(.text) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -section-headers %t.out | \
+# RUN:   FileCheck -check-prefix=WRITABLEORPHAN %s
+
+# TEXTORPHAN:      Sections:
+# TEXTORPHAN-NEXT: Idx Name
+# TEXTORPHAN-NEXT:   0
+# TEXTORPHAN-NEXT:   1 .writable
+# TEXTORPHAN-NEXT:   2 .text
+
+# WRITABLEORPHAN:      Sections:
+# WRITABLEORPHAN-NEXT: Idx Name
+# WRITABLEORPHAN-NEXT:   0
+# WRITABLEORPHAN-NEXT:   1 .text
+# WRITABLEORPHAN-NEXT:   2 .writable
+
+.global _start
+_start:
+ nop
+
+.section .writable,"aw"
+ .zero 4