[ELF] - Linkerscript KEEP command.

[grimar]

Summary

When link-time garbage collection is in use (-gc-sections), it is often useful to mark sections that should not be eliminated. This is accomplished by surrounding an input section's wildcard entry with KEEP().
Patch implements that command.

[ruiu]

What's the performance impact of this change? This change made the linker compare all discarded section names against all rules in linker scripts, which can be expensive. Of course that depends on input, but O(n*m) where n is the number of discarded sections and m is the number of section rules is a bit scary.

ELF/LinkerScript.cpp

46–52

You want to define

template <class ELFT>
SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
  for (SectionRule &R : Sections)
    if (R.match(S))
      return &R;
  return nullptr;
}

and use it both from shouldKeep and from getOutputSection.

384

Why did you change this?

389–396

This should be a regular member function rather than a closure.

413

Please use setError() in the linker script as other code does.

[grimar]

Addressed Rui's comments.

[grimar]

In D17242#353765, @ruiu wrote:

What's the performance impact of this change? This change made the linker compare all discarded section names against all rules in linker scripts, which can be expensive. Of course that depends on input, but O(n*m) where n is the number of discarded sections and m is the number of section rules is a bit scary.

That really depends I guess. Should be tested on real app that uses the features of LS. Currently I think it is not in the state when valid tests can be performed.
There are lot of possible ways to optimize I believe, but for now I suggest to leave this one implementation.

ELF/LinkerScript.cpp

384

I changed that when modified readOutputSectionDescription() as well. So this change is to match the style of readOutputSectionDescription() which is called from readSections(). Not sure it is fine for this patch, probably separate patch for both is better.
That`s why it was changed in separate refactoring patch: http://reviews.llvm.org/D17256.
Point was that there is no need to check Error flag here as skip() does that at first line.

I returned that back as mentioned above refactor patch has it.

[ruiu]

ELF/LinkerScript.cpp

49

return R && R->Keep;

390

Did you test this code with an incomplete input? I think this will fall into an infinite loop if you give

SECTIONS { .foo : { KEEP(

391

Why don't you add Keep as a parameter to the constructor?

ELF/LinkerScript.h

58

Remove LinkerScript::.

[grimar]

• Addressed Rui's comments.

ELF/LinkerScript.cpp

390

Hmm you're right, my mistake.

[ruiu]

ELF/LinkerScript.cpp

402–414

s/Cmd/Tok/.

(When we read a token, we don't know if it is a KEEP command or just a regular token.)

ELF/LinkerScript.h

27

Please do not over use friend. No one but LinkerScript should use SectionRule, so you want to make the member public.

[grimar]

• Addressed review comments.
• Updated testcase: added case when section name matches two entries in the SECTIONS directive, the first one doesn't have KEEP, the second one does.

[• rafael]

test/ELF/linkerscript-sections-keep.s

53

Yes, that is the test I had in mind, thanks.

[ruiu]

LGTM

ELF/LinkerScript.h

 namespace lld {
 namespace elf2 {
 
 class ScriptParser;
 template <class ELFT> class InputSectionBase;
 
 // This class represents each rule in SECTIONS command.
 class SectionRule {
 public:
   SectionRule(StringRef D, StringRef S) : Dest(D), SectionPattern(S) {}
 
   // Returns true if S should be in Dest section.
   template <class ELFT> bool match(InputSectionBase<ELFT> *S);
 
   StringRef Dest;
 
+  // KEEP command saves unused sections even if --gc-sections is specified.
+  bool Keep = false;
+
 private:
   StringRef SectionPattern;
 };
 
 // This is a runner of the linker script.
 class LinkerScript {
   friend class ScriptParser;
 
 public:
   // Parses a linker script. Calling this function may update
   // this object and Config.
   void read(MemoryBufferRef MB);
 
   template <class ELFT> StringRef getOutputSection(InputSectionBase<ELFT> *S);
   template <class ELFT> bool isDiscarded(InputSectionBase<ELFT> *S);
+  template <class ELFT> bool shouldKeep(InputSectionBase<ELFT> *S);
   int compareSections(StringRef A, StringRef B);
 
 private:
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
   // Output sections are sorted by this order.
   std::vector<StringRef> SectionOrder;
 
   llvm::BumpPtrAllocator Alloc;
 };
 
 extern LinkerScript *Script;
 
 } // namespace elf2
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
   return "";
 }
 
 template <class ELFT>
 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
   return getOutputSection(S) == "/DISCARD/";
 }
 
+template <class ELFT>
+bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
+  for (SectionRule &R : Sections)
+    if (R.match(S))
+      return R.Keep;
+  return false;
+}
+
 // 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.
 int LinkerScript::compareSections(StringRef A, StringRef B) {
   auto E = SectionOrder.end();
   auto I = std::find(SectionOrder.begin(), E, A);
   auto J = std::find(SectionOrder.begin(), E, B);
   if (I == E || J == E)

 void ScriptParser::readSearchDir() {
   expect("(");
   Config->SearchPaths.push_back(next());
   expect(")");
 }
 
 void ScriptParser::readSections() {
   expect("{");
-  while (!Error && !skip("}"))
+  while (!skip("}"))
     readOutputSectionDescription();
 }
 
 void ScriptParser::readOutputSectionDescription() {
+  auto ReadSections = [this](StringRef OutSec, bool Keep = false) {
+    expect("(");
+    while (!skip(")")) {
+      SectionRule R = { OutSec, next() };
+      R.Keep = Keep;
+      Script->Sections.emplace_back(R);
+    }
+  };
+
   StringRef OutSec = next();
   Script->SectionOrder.push_back(OutSec);
   expect(":");
   expect("{");
-  while (!Error && !skip("}")) {
-    next(); // Skip input file name.
+
+  while (!skip("}")) {
+    StringRef Cmd = next();
+    if (Cmd == "*") {
+      ReadSections(OutSec);
+    } else if (Cmd == "KEEP") {
       expect("(");
-    while (!Error && !skip(")"))
-      Script->Sections.push_back({OutSec, next()});
+      next(); // Skip *
+      ReadSections(OutSec, true);
+      expect(")");
+    } else {
+      error("Unknown command " + Cmd);
+    }
   }
 }
 
 static bool isUnderSysroot(StringRef Path) {
   if (Config->Sysroot == "")
     return false;
   for (; !Path.empty(); Path = sys::path::parent_path(Path))
     if (sys::fs::equivalent(Config->Sysroot, Path))

 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
 template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
 
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
 
+template bool LinkerScript::shouldKeep(InputSectionBase<ELF32LE> *);
+template bool LinkerScript::shouldKeep(InputSectionBase<ELF32BE> *);
+template bool LinkerScript::shouldKeep(InputSectionBase<ELF64LE> *);
+template bool LinkerScript::shouldKeep(InputSectionBase<ELF64BE> *);
+
 template bool SectionRule::match(InputSectionBase<ELF32LE> *);
 template bool SectionRule::match(InputSectionBase<ELF32BE> *);
 template bool SectionRule::match(InputSectionBase<ELF64LE> *);
 template bool SectionRule::match(InputSectionBase<ELF64BE> *);

ELF/MarkLive.cpp

 // by default. Starting with GC-root symbols or sections, markLive function
 // defined in this file visits all reachable sections to set their Live
 // bits. Writer will then ignore sections whose Live bits are off, so that
 // such sections are not included into output.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
+#include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"
 #include <functional>
 #include <vector>
template <class ELFT> void elf2::markLive(SymbolTable<ELFT> *Symtab) {
   if (Config->Shared || Config->ExportDynamic) {
     for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) {
       SymbolBody *B = P.second->Body;
       if (B->getVisibility() == STV_DEFAULT)
         MarkSymbol(B);
     }
   }
 
-  // Preserve special sections.
+  // Preserve special sections and those which are specified in linker
+  // script KEEP command.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles())
     for (InputSectionBase<ELFT> *Sec : F->getSections())
-      if (Sec && Sec != &InputSection<ELFT>::Discarded && isReserved(Sec))
+      if (Sec && Sec != &InputSection<ELFT>::Discarded)
+        if (isReserved(Sec) || Script->shouldKeep<ELFT>(Sec))
           Enqueue(Sec);
 
   // Mark all reachable sections.
   while (!Q.empty())
     forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue);
 }
 
 template void elf2::markLive<ELF32LE>(SymbolTable<ELF32LE> *);
 template void elf2::markLive<ELF32BE>(SymbolTable<ELF32BE> *);
 template void elf2::markLive<ELF64LE>(SymbolTable<ELF64LE> *);
 template void elf2::markLive<ELF64BE>(SymbolTable<ELF64BE> *);

test/ELF/linkerscript-sections-keep.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+## First check that section "keep" is garbage collected without using KEEP
+# RUN: echo "SECTIONS { \
+# RUN:  .text : { *(.text) } \
+# RUN:  .keep : { *(.keep) } \
+# RUN:  .temp : { *(.temp) }}" > %t.script
+# RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | \
+# RUN:   FileCheck -check-prefix=SECGC %s
+# SECGC:      Sections:
+# SECGC-NEXT: Idx Name          Size      Address          Type
+# SECGC-NEXT:   0               00000000 0000000000000000 
+# SECGC-NEXT:   1 .text         00000007 0000000000011000 TEXT DATA
+# SECGC-NEXT:   2 .temp         00000004 0000000000012000 DATA
+
+## Now apply KEEP command to preserve the section.
+# RUN: echo "SECTIONS { \
+# RUN:  .text : { *(.text) } \
+# RUN:  .keep : { KEEP(*(.keep)) } \
+# RUN:  .temp : { *(.temp) }}" > %t.script
+# RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | \
+# RUN:   FileCheck -check-prefix=SECNOGC %s
+# SECNOGC:      Sections:
+# SECNOGC-NEXT: Idx Name          Size      Address          Type
+# SECNOGC-NEXT:   0               00000000 0000000000000000 
+# SECNOGC-NEXT:   1 .text         00000007 0000000000011000 TEXT DATA
+# SECNOGC-NEXT:   2 .keep         00000004 0000000000012000 DATA
+# SECNOGC-NEXT:   3 .temp         00000004 0000000000012004 DATA
+
+.global _start
+_start:
+ mov temp, %eax
+
+.section .keep, "a"
+keep: 
+ .long 1
+
+.section .temp, "a"
+temp:
+ .long 2