[ELF] - Support "INSERT AFTER" statement.

[grimar]

Summary

Its PR35877 again.

This implements INSERT AFTER in a following way:

• During reading scripts it collects all insert statements.
• After we done and read all files it inserts statements into script commands list.

With that:

1. Rest of code does know nothing about INSERT.
2. Approach is straightforward and have no visible limitations.
3. It is also easy to support INSERT BEFORE (was seen in clang code once).
4. Should work for PR35877 and similar cases.

cons:

• It assumes we have "main" scripts that describes sections.

So it does not work for case when we would have only script that do INSERT
to patch some "default bfd script" that we do not have in LLD anyways.

[ruiu]

test/ELF/insert-after.s

4–14

We should stop writing linker scripts using "echo". As I did, rewrite this file as a linker script. You could create Inputs/insert-after.s.

[grimar]

test/ELF/insert-after.s

4–14

This patch was posted a few weeks before your change :) I'll update it.

[grimar]

• Rebased.
• Implemented test case as a script.
• Adjusted code slightly.

test/ELF/insert-after.s

4–14

Also, note there are 2 linker scripts required here.

[ruiu]

ELF/LinkerScript.cpp

168

used to -> is used to

175

InsertV is odd too -- maybe just W because it's next to V.

184

SectionCommands = std::move(V) is better I guess?

ELF/LinkerScript.h

292

needs -> need

294

PendingInsert sounds a bit odd. I'd name this InsertAfterCommands.

[ruiu]

With that LGTM

[• rafael]

LGTM

George Rimar via Phabricator via llvm-commits
<[e-mail]> writes:

grimar updated this revision to Diff 136968.
grimar added a comment.

• Rebased.
• Implemented test case as a script.
• Adjusted code slightly.

https://reviews.llvm.org/D43468

Files:

ELF/Driver.cpp
ELF/LinkerScript.cpp
ELF/LinkerScript.h
ELF/ScriptParser.cpp
test/ELF/linkerscript/Inputs/insert-after.s
test/ELF/linkerscript/Inputs/insert-after.script
test/ELF/linkerscript/insert-after.test

Index: test/ELF/linkerscript/insert-after.test

• test/ELF/linkerscript/insert-after.test

+++ test/ELF/linkerscript/insert-after.test
@@ -0,0 +1,29 @@
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/insert-after.s -o %t1.o
+
+ Main linker script contains .text and .data sections. Here + we check that can use INSERT AFTER to insert sections .foo.data
+## and .foo.text at the right places.
+
+SECTIONS {
+ .foo.data : { *(.foo.data) }
+} INSERT AFTER .data;
+
+SECTIONS {
+ .foo.text : { *(.foo.text) }
+} INSERT AFTER .text;
+
+# RUN: ld.lld %t1.o -o %t1 --script %p/Inputs/insert-after.script --script %s
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+# CHECK: Sections:
+# CHECK-NEXT: Idx Name Size Address Type
+# CHECK-NEXT: 0 00000000 0000000000000000
+# CHECK-NEXT: 1 .text 00000008 0000000000000000 TEXT DATA
+# CHECK-NEXT: 2 .foo.text 00000008 0000000000000008 TEXT DATA
+# CHECK-NEXT: 3 .data 00000008 0000000000000010 DATA
+# CHECK-NEXT: 4 .foo.data 00000008 0000000000000018 DATA
+
+# RUN: not ld.lld %t1.o -o %t1 --script %s 2>&1 \
+# RUN: | FileCheck %s --check-prefix=ERR
+# ERR-DAG: error: unable to INSERT AFTER .text: section not defined
+# ERR-DAG: error: unable to INSERT AFTER .data: section not defined

Index: test/ELF/linkerscript/Inputs/insert-after.script

• test/ELF/linkerscript/Inputs/insert-after.script

+++ test/ELF/linkerscript/Inputs/insert-after.script
@@ -0,0 +1,4 @@
+SECTIONS {
+ .text : { *(.text.*) }
+ .data : { *(.data.*) }
+}

Index: test/ELF/linkerscript/Inputs/insert-after.s

• test/ELF/linkerscript/Inputs/insert-after.s

+++ test/ELF/linkerscript/Inputs/insert-after.s
@@ -0,0 +1,11 @@
+.section .foo.text,"ax"
+.quad 0
+
+.section .foo.data,"aw"
+.quad 0
+
+.section .text.1,"ax"
+.quad 0
+
+.section .data.1,"aw"
+.quad 0

Index: ELF/ScriptParser.cpp

• ELF/ScriptParser.cpp

+++ ELF/ScriptParser.cpp
@@ -436,6 +436,7 @@

Config->SingleRoRx = true;
 
expect("{");

+ std::vector<BaseCommand *> V;

while (!errorCount() && !consume("}")) {
  StringRef Tok = next();
  BaseCommand *Cmd = readProvideOrAssignment(Tok);

@@ -445,8 +446,18 @@

  else
    Cmd = readOutputSectionDescription(Tok);
}

• Script->SectionCommands.push_back(Cmd);

+ V.push_back(Cmd);

}

+
+ if (!atEOF() && consume("INSERT")) {
+ consume("AFTER");
+ std::vector<BaseCommand *> &Dest = Script->PendingInserts[next()];
+ Dest.insert(Dest.end(), V.begin(), V.end());
+ return;
+ }
+
+ Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
+ V.end());
}

static int precedence(StringRef Op) {

Index: ELF/LinkerScript.h

• ELF/LinkerScript.h

+++ ELF/LinkerScript.h
@@ -267,6 +267,9 @@

void processSectionCommands();
void declareSymbols();

+ // Used to handle INSERT AFTER statements.
+ void processInsertCommands();
+

// SECTIONS command list.
std::vector<BaseCommand *> SectionCommands;

@@ -285,6 +288,10 @@

// A list of symbols referenced by the script.
std::vector<llvm::StringRef> ReferencedSymbols;

+
+ Used to implement INSERT AFTER. Contains commands that needs
+ to be inserted into SECTIONS commands list.
+ llvm::DenseMap<StringRef, std::vector<BaseCommand *>> PendingInserts;
};

extern LinkerScript *Script;

Index: ELF/LinkerScript.cpp

• ELF/LinkerScript.cpp

+++ ELF/LinkerScript.cpp
@@ -203,6 +203,25 @@

Cmd->Provide = false;

}

+ This method used to handle INSERT AFTER statement. Here we rebuild
+ list of script commands to mix section inserted into.
+void LinkerScript::processInsertCommands() {
+ std::vector<BaseCommand *> V;
+ for (BaseCommand *Base : SectionCommands) {
+ V.push_back(Base);
+ if (auto *Cmd = dyn_cast<OutputSection>(Base)) {
+ std::vector<BaseCommand *> &InsertV = PendingInserts[Cmd->Name];
+ V.insert(V.end(), InsertV.begin(), InsertV.end());
+ InsertV.clear();
+ }
+ }
+ for (std::pair<StringRef, std::vector<BaseCommand *>> &P : PendingInserts)
+ if (!P.second.empty())
+ error("unable to INSERT AFTER " + P.first + ": section not defined");
+
+ SectionCommands.swap(V);
+}
+
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.

Index: ELF/Driver.cpp

• ELF/Driver.cpp

+++ ELF/Driver.cpp
@@ -1081,6 +1081,10 @@

if (errorCount())
  return;

+ Now when we read all script files, we want to finalize order of linker
+ script commands, which can be not yet final because of INSERT commands.
+ Script->processInsertCommands();
+

// We want to declare linker script's symbols early,
// so that we can version them.
// They also might be exported if referenced by DSOs.

---

llvm-commits mailing list
[e-mail]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

ELF/Driver.cpp

template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // addReservedSymbols to mark the created symbols as not absolute.
   Out::ElfHeader = make<OutputSection>("", 0, SHF_ALLOC);
   Out::ElfHeader->Size = sizeof(typename ELFT::Ehdr);
 
   // We need to create some reserved symbols such as _end. Create them.
   if (!Config->Relocatable)
     addReservedSymbols();
 
+  // Now when we read all script files, we want to finalize order of linker
+  // script commands, which can be not yet final because of INSERT commands.
+  Script->processInsertCommands();
+
   // We want to declare linker script's symbols early,
   // so that we can version them.
   Script->declareSymbols();
 
   // Apply version scripts.
   //
   // For a relocatable output, version scripts don't make sense, and
   // parsing a symbol version string (e.g. dropping "@ver1" from a symbol

ELF/LinkerScript.h

public:
   bool needsInterpSection();
 
   bool shouldKeep(InputSectionBase *S);
   void assignAddresses();
   void allocateHeaders(std::vector<PhdrEntry *> &Phdrs);
   void processSectionCommands();
   void declareSymbols();
 
+  // Used to handle INSERT AFTER statements.
+  void processInsertCommands();
+
   // SECTIONS command list.
   std::vector<BaseCommand *> SectionCommands;
 
   // PHDRS command list.
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool HasSectionsCommand = false;
   bool ErrorOnMissingSection = false;
 
   // List of section patterns specified with KEEP commands. They will
   // be kept even if they are unused and --gc-sections is specified.
   std::vector<InputSectionDescription *> KeptSections;
 
   // A map from memory region name to a memory region descriptor.
   llvm::MapVector<llvm::StringRef, MemoryRegion *> MemoryRegions;
 
   // A list of symbols referenced by the script.
   std::vector<llvm::StringRef> ReferencedSymbols;
+
+  // Used to implement INSERT AFTER. Contains commands that needs
+  // to be inserted into SECTIONS commands list.
+  llvm::DenseMap<StringRef, std::vector<BaseCommand *>> PendingInserts;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/LinkerScript.cpp

void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 
   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
                          STT_NOTYPE, SymValue, 0, Sec);
   Cmd->Sym = cast<Defined>(Sym);
 }
 
+void LinkerScript::processInsertCommands() {
+  std::vector<BaseCommand *> V;
+  for (BaseCommand *Base : SectionCommands) {
+    V.push_back(Base);
+    if (auto *Cmd = dyn_cast<OutputSection>(Base)) {
+      std::vector<BaseCommand *> &InsertV = PendingInserts[Cmd->Name];
+      V.insert(V.end(), InsertV.begin(), InsertV.end());
+      InsertV.clear();
+    }
+  }
+  for (std::pair<StringRef, std::vector<BaseCommand *>> &P : PendingInserts)
+    if (!P.second.empty())
+      error("unable to INSERT AFTER " + P.first + ": section not defined");
+
+  SectionCommands.swap(V);
+}
+
 // 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);
   for (BaseCommand *Base : SectionCommands) {
     auto *Cmd = dyn_cast<SymbolAssignment>(Base);
     if (!Cmd || !shouldDefineSym(Cmd))

ELF/ScriptParser.cpp

void ScriptParser::readSections() {
   Script->HasSectionsCommand = true;
 
   // -no-rosegment is used to avoid placing read only non-executable sections in
   // their own segment. We do the same if SECTIONS command is present in linker
   // script. See comment for computeFlags().
   Config->SingleRoRx = true;
 
   expect("{");
+  std::vector<BaseCommand *> V;
   while (!errorCount() && !consume("}")) {
     StringRef Tok = next();
     BaseCommand *Cmd = readProvideOrAssignment(Tok);
     if (!Cmd) {
       if (Tok == "ASSERT")
         Cmd = readAssert();
       else
         Cmd = readOutputSectionDescription(Tok);
     }
-    Script->SectionCommands.push_back(Cmd);
+    V.push_back(Cmd);
   }
+
+  if (atEOF() || !consume("INSERT")) {
+    Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
+                                   V.end());
+    return;
+  }
+
+  consume("AFTER");
+  std::vector<BaseCommand *> &Dest = Script->PendingInserts[next()];
+  Dest.insert(Dest.end(), V.begin(), V.end());
 }
 
 static int precedence(StringRef Op) {
   return StringSwitch<int>(Op)
       .Cases("*", "/", 5)
       .Cases("+", "-", 4)
       .Cases("<<", ">>", 3)
       .Cases("<", "<=", ">", ">=", "==", "!=", 2)

test/ELF/insert-after.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+
+# RUN: echo "SECTIONS {               \
+# RUN:   .foo.data : { *(.foo.data) } \
+# RUN:  } INSERT AFTER .data;         \
+# RUN:  SECTIONS {                    \
+# RUN:   .foo.text : { *(.foo.text) } \
+# RUN:  } INSERT AFTER .text;" > %tinsert.script
+
+# RUN: echo "SECTIONS {          \
+# RUN:   .text  : { *(.text.*) } \
+# RUN:   .data  : { *(.data.*) } \
+# RUN:  }" > %tmain.script
+
+# RUN: ld.lld %t1.o -o %t1 --script %tinsert.script %tmain.script
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+# CHECK:      Sections:
+# CHECK-NEXT: Idx Name          Size      Address          Type
+# CHECK-NEXT:   0               00000000 0000000000000000
+# CHECK-NEXT:   1 .text         00000008 0000000000000000 TEXT DATA
+# CHECK-NEXT:   2 .foo.text     00000008 0000000000000008 TEXT DATA
+# CHECK-NEXT:   3 .data         00000008 0000000000000010 DATA
+# CHECK-NEXT:   4 .foo.data     00000008 0000000000000018 DATA
+
+# RUN: not ld.lld %t1.o -o %t1 --script %tinsert.script 2>&1 \
+# RUN:   | FileCheck %s --check-prefix=ERR
+# ERR-DAG: error: unable to INSERT AFTER .text: section not defined
+# ERR-DAG: error: unable to INSERT AFTER .data: section not defined
+
+.section .foo.text,"ax"
+.quad 0
+
+.section .foo.data,"aw"
+.quad 0
+
+.section .text.foo,"ax"
+.quad 0
+
+.section .data.foo,"aw"
+.quad 0