[ELF] Preserve section order within an INSERT AFTER command

[MaskRay]

Summary

For

SECTIONS {
  text.0 : {}
  text.1 : {}
  text.2 : {}
} INSERT AFTER .data;

the current order is .data text.2 text.1 text.0. It makes more sense to
preserve the specified order and thus improve compatibility with GNU ld.

For

SECTIONS { text.0 : {} } INSERT AFTER .data;
SECTIONS { text.3 : {} } INSERT AFTER .data;

GNU ld somehow collects sections with INSERT AFTER .data together (IMO
inconsistent) but I think it makes more sense to execute the commands in order
and get .data text.3 text.0 instead.

[peter.smith]

Change looks sensible to me. One suggestion that might work out better is to use something like:

struct InsertCommand {
  std::vector<StringRef> names;
  bool isAfter;
  StringRef where;
};

Then all OutputSections in a SECTIONS can be added in order to names. This might make it easier to understand the nested loops in processInsertCommands. This is only a weak suggestion though, it may make things worse.

lld/ELF/LinkerScript.h

230

Suggest comment, something like:
// All OutputSections in a SECTIONS get the same commandId;

[MaskRay]

Thanks for the suggestion. Switched to std::vector<StringRef>

If we ever care about insert order of SymbolAssignment's, we can think how to address that in the future.

[peter.smith]

LGTM, thanks for the update.

lld/ELF/LinkerScript.h

struct ByteCommand : BaseCommand {
   // This is just an offset of this assignment command in the output section.
   unsigned offset;
 
   // Size of this data command.
   unsigned size;
 };
 
 struct InsertCommand {
-  StringRef name;
+  std::vector<StringRef> names;
   bool isAfter;
   StringRef where;
 };
 
 struct PhdrsCommand {
   StringRef name;
   unsigned type = llvm::ELF::PT_NULL;
   bool hasFilehdr = false;

lld/ELF/LinkerScript.cpp

if (std::make_pair(sym->section, sym->value) != it.second &&
       changed = sym;
   }
   return changed;
 }
 
 // Process INSERT [AFTER|BEFORE] commands. For each command, we move the
 // specified output section to the designated place.
 void LinkerScript::processInsertCommands() {
+  std::vector<OutputSection *> moves;
   for (const InsertCommand &cmd : insertCommands) {
-    // If cmd.os is empty, it may have been discarded by
+    for (StringRef name : cmd.names) {
+      // If base is empty, it may have been discarded by
       // adjustSectionsBeforeSorting(). We do not handle such output sections.
       auto from = llvm::find_if(sectionCommands, [&](BaseCommand *base) {
         return isa<OutputSection>(base) &&
-             cast<OutputSection>(base)->name == cmd.name;
+               cast<OutputSection>(base)->name == name;
       });
       if (from == sectionCommands.end())
         continue;
-    OutputSection *osec = cast<OutputSection>(*from);
+      moves.push_back(cast<OutputSection>(*from));
       sectionCommands.erase(from);
+    }
 
     auto insertPos = llvm::find_if(sectionCommands, [&cmd](BaseCommand *base) {
       auto *to = dyn_cast<OutputSection>(base);
       return to != nullptr && to->name == cmd.where;
     });
     if (insertPos == sectionCommands.end()) {
-      error("unable to insert " + osec->name +
+      error("unable to insert " + cmd.names[0] +
             (cmd.isAfter ? " after " : " before ") + cmd.where);
     } else {
       if (cmd.isAfter)
         ++insertPos;
-      sectionCommands.insert(insertPos, osec);
+      sectionCommands.insert(insertPos, moves.begin(), moves.end());
     }
+    moves.clear();
   }
 }
 
 // Symbols defined in script should not be inlined by LTO. At the same time
 // we don't know their final values until late stages of link. Here we scan
 // over symbol assignment commands and create placeholder symbols if needed.
 void LinkerScript::declareSymbols() {
   assert(!ctx);

lld/ELF/ScriptParser.cpp

void ScriptParser::readSections() {
   }
 
   bool isAfter = false;
   if (consume("AFTER"))
     isAfter = true;
   else if (!consume("BEFORE"))
     setError("expected AFTER/BEFORE, but got '" + next() + "'");
   StringRef where = next();
+  std::vector<StringRef> names;
   for (BaseCommand *cmd : v)
     if (auto *os = dyn_cast<OutputSection>(cmd))
-      script->insertCommands.push_back({os->name, isAfter, where});
+      names.push_back(os->name);
+  if (!names.empty())
+    script->insertCommands.push_back({std::move(names), isAfter, where});
 }
 
 void ScriptParser::readTarget() {
   // TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
   // we accept only a limited set of BFD names (i.e. "elf" or "binary")
   // for --format. We recognize only /^elf/ and "binary" in the linker
   // script as well.
   expect("(");

lld/test/ELF/linkerscript/insert-multi.test

+# REQUIRES: x86
+## Sections in an INSERT command are in a unit. Their order is preserved.
+
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/a.s -o %t/a.o
+# RUN: ld.lld -T %t/a.lds %t/a.o -o %t1
+# RUN: llvm-readelf -S -l %t1 | FileCheck %s
+
+# CHECK:      Name
+# CHECK-NEXT:        NULL
+# CHECK-NEXT: text.3
+# CHECK-NEXT: text.4
+# CHECK-NEXT: text.5
+# CHECK-NEXT: .text
+# CHECK-NEXT: .data
+# CHECK-NEXT: text.6
+# CHECK-NEXT: text.7
+# CHECK-NEXT: text.8
+# CHECK-NEXT: text.0
+# CHECK-NEXT: text.1
+# CHECK-NEXT: text.2
+
+#--- a.lds
+SECTIONS {
+  text.0 : {}
+  text.1 : {}
+  text.2 : {}
+} INSERT AFTER .data;
+
+SECTIONS {
+  text.3 : {}
+  text.4 : {}
+  text.5 : {}
+} INSERT BEFORE .text;
+
+SECTIONS {
+  text.6 : {}
+  text.7 : {}
+  text.8 : {}
+} INSERT AFTER .data;
+
+#--- a.s
+.text; nop
+.section text.0,"ax"; nop
+.section text.1,"ax"; nop
+.section text.2,"ax"; nop
+.section text.3,"ax"; nop
+.section text.4,"ax"; nop
+.section text.5,"ax"; nop
+.section text.6,"ax"; nop
+.section text.7,"ax"; nop
+.section text.8,"ax"; nop
+.data; .byte 0