[LLD][ELF] Add InputSectionDescriptions for Orphan Sections

[peter.smith]

Summary

Orphan input sections are sections that do not match any InputSectionDescription, these are either placed in existing OutputSections if their name matches for example

.text : { *(.text) }

will match all orphans with a prefix of .text. However an orphan that does not match the name of an existing OutputSection will have an OutputSection created. The orphan input sections are added to OutputSections, and are handled by the flush() function when doing address assignment. These orphan sections will be invisible to Thunk creation and the ordering of .ARM.exidx sections as they won't appear on any InputSection description.

This change fabricates InputSectionDescriptions to cover the inserted orphan sections. I've checked that this matches the behavior of GNU ld when there is a symbol definition at the end of an existing InputSectionDescription. For example:

.text : { *(.text) SYM = .; }

The orphans are added after SYM is defined.

It will now be possible for createThunks to insert thunks into orphan InputSectionDescriptions and for .ARM.exidx section sorting to work with linker scripts that have orphan Sections. For example the InputSectionDescription:

.ARM.exidx : { *(.ARM.exidx) }

Will only match sections with a name of .ARM.exidx, sections such as .ARM.exidx.text.foo will not match the InputSectionDescription, but will match the OutputSection as an orphan.

Note that the .ARM.exidx ordering code in OutputSections currently works on OutputSections::Sections, so it is likely to be wrong when there is a linker script. I've put a temporary FIXME in that makes the script ordering work. I have a full fix that rewrites the .ARM.exidx ordering code that I'll post in a separate review.

[ruiu]

What this patch does seems logically correct, but I'm not sure if we still want to keep placeOrphanSections as a separate stage as addOrphanSections. If you update Opt.Commands in addOrphanSections, you don't need them to be separated, no?

[peter.smith]

The main difficulty in creating and adding the Orphan OutputSectionCommand in addOrphanSections() is that we don't have a good idea of where in the order of OutputSectionCommands to insert them. The placeOrphanSections() is intentionally run immediately after sortSections() has been called so that it can insert the OutputSectionCommands in the right place. There is a comment in Writer.c in sortSections() that says:

// The way we define an order then is:
// *  First put script sections at the start and sort the script and
//    non-script sections independently.
// *  Move each non-script section to its preferred position. We try
//    to put each section in the last position where it it can share
//    a PT_LOAD.

It may be possible to create the Orphan OutputSectionCommands early and have the comparison routine work out the ordering, although there is a comment in the same block as the one above that claims that coming up with a strict weak ordering to get the desired result is not easy.

I did consider creating the InputSectionDescription commands for pre-existing OutputSections in placeOrphanSections but it seemed easier to reuse the existing lookup of OutputSectionCommand in addOrphanSections().

[peter.smith]

This is no longer required, it was implemented by a series of changes by Rafael starting with I think r303384

ELF/LinkerScript.cpp

void LinkerScript::fabricateDefaultCommands(bool AllocateHeader) {
   }
   // SECTIONS commands run before other non SECTIONS commands
   Commands.insert(Commands.end(), Opt.Commands.begin(), Opt.Commands.end());
   Opt.Commands = std::move(Commands);
 }
 
 // Add sections that didn't match any sections command.
 void LinkerScript::addOrphanSections(OutputSectionFactory &Factory) {
+  std::map<OutputSection *, std::vector<InputSectionBase *>> Orphanage;
   for (InputSectionBase *S : InputSections)
-    if (S->Live && !S->OutSec)
+    if (S->Live && !S->OutSec) {
       Factory.addInputSec(S, getOutputSectionName(S->Name));
+      Orphanage[S->OutSec].push_back(S);
+    }
+
+  // For each OutputSection that already has an OutputSectionCmd, add an
+  // InputSectionDescription at the end for the OrphanSections. This matches
+  // GNU ld behavior for scripts such as .text : { *(.text) SYM = .; } the
+  // orphan sections such as .text.suffix are added after the symbol assignment
+  for (auto &KV : Orphanage) {
+    OutputSection *OS = KV.first;
+    auto Pos = std::find_if(Opt.Commands.begin(), Opt.Commands.end(),
+                            [&](BaseCommand *Base) {
+                              auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
+                              return Cmd && Cmd->Name == OS->Name;
+                            });
+    if (Pos == Opt.Commands.end())
+      // A new OutputSection, we handle this case in placeOrphanSections()
+      continue;
+    auto *OSCmd = cast<OutputSectionCommand>(*Pos);
+    if (KV.second.front()->Name.startswith(".ARM.exidx"))
+      // .ARM.exidx sections must be handled in one InputSectionDescription
+      // FIXME: OutputSections still sorts the OutputSection::Sections so we
+      // can give the wrong answer when the order of the input objects does
+      // not match the address assignment.
+      continue;
+
+    auto *ISD = make<InputSectionDescription>("");
+    OSCmd->Commands.push_back(ISD);
+    ISD->Sections = std::move(KV.second);
+  }
 }
 
 static bool isTbss(OutputSection *Sec) {
   return (Sec->Flags & SHF_TLS) && Sec->Type == SHT_NOBITS;
 }
 
 void LinkerScript::output(InputSection *S) {
   if (!AlreadyOutputIS.insert(S).second)
for (OutputSection *Sec : *OutputSections) {
     auto Pos = std::find_if(CmdIter, E, [&](BaseCommand *Base) {
       auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
       return Cmd && Cmd->Name == Name;
     });
     if (Pos == E) {
       auto *Cmd = make<OutputSectionCommand>(Name);
       Cmd->Sec = Sec;
       Opt.Commands.insert(CmdIter, Cmd);
+
+      // Create an InputSectionDescription for orphan input sections
+      if (!Sec->Sections.empty() && (Sec->Flags & SHF_ALLOC)) {
+        auto *ISD = make<InputSectionDescription>("");
+        Cmd->Commands.push_back(ISD);
+        for (InputSection *ISec : Sec->Sections) {
+          ISD->Sections.push_back(ISec);
+          ISec->Assigned = true;
+        }
+      }
       ++CmdIndex;
       continue;
     }
 
     // Continue from where we found it.
     CmdIndex = (Pos - Opt.Commands.begin()) + 1;
   }
 }