[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

52–58

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.

388

Why did you change this?

399–406

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

415

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

388

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

55

return R && R->Keep;

394

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

SECTIONS { .foo : { KEEP(

395

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

ELF/LinkerScript.h

59

Remove LinkerScript::.

[grimar]

• Addressed Rui's comments.

ELF/LinkerScript.cpp

394

Hmm you're right, my mistake.

[ruiu]

ELF/LinkerScript.cpp

404–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

52

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) {}
+  SectionRule(StringRef D, StringRef S, bool Keep)
+      : Dest(D), SectionPattern(S), Keep(Keep) {}
 
   // 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:
+  template <class ELFT> SectionRule *find(InputSectionBase<ELFT> *S);
+
   // 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

 using namespace llvm;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::elf2;
 
 LinkerScript *elf2::Script;
 
 template <class ELFT>
-StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
+SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
   for (SectionRule &R : Sections)
     if (R.match(S))
-      return R.Dest;
-  return "";
+      return &R;
+  return nullptr;
+}
+
+template <class ELFT>
+StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
+  SectionRule *R = find(S);
+  return R ? R->Dest : "";
 }
 
 template <class ELFT>
 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
   return getOutputSection(S) == "/DISCARD/";
 }
 
+template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
+  SectionRule *R = find(S);
+  return R && R->Keep;
+}
+
 // 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)
     return 0;
   return I < J ? -1 : 1;
private:
   void readInclude();
   void readOutput();
   void readOutputArch();
   void readOutputFormat();
   void readSearchDir();
   void readSections();
 
   void readOutputSectionDescription();
+  void readSectionPatterns(StringRef OutSec, bool Keep);
 
   StringSaver Saver;
   std::vector<StringRef> Tokens;
   bool Error = false;
   size_t Pos = 0;
   bool IsUnderSysroot;
 };
 

 void ScriptParser::readSearchDir() {
   expect("(");
   Config->SearchPaths.push_back(next());
   expect(")");
 }
 
 void ScriptParser::readSections() {
   expect("{");
   while (!Error && !skip("}"))
     readOutputSectionDescription();
 }
 
+void ScriptParser::readSectionPatterns(StringRef OutSec, bool Keep) {
+  expect("(");
+  while (!Error && !skip(")"))
+    Script->Sections.emplace_back(OutSec, next(), Keep);
+}
+
 void ScriptParser::readOutputSectionDescription() {
   StringRef OutSec = next();
   Script->SectionOrder.push_back(OutSec);
   expect(":");
   expect("{");
   while (!Error && !skip("}")) {
-    next(); // Skip input file name.
+    StringRef Tok = next();
+    if (Tok == "*") {
+      readSectionPatterns(OutSec, false);
+    } else if (Tok == "KEEP") {
       expect("(");
-    while (!Error && !skip(")"))
-      Script->Sections.push_back({OutSec, next()});
+      next(); // Skip *
+      readSectionPatterns(OutSec, true);
+      expect(")");
+    } else {
+      setError("Unknown command " + Tok);
+    }
   }
 }
 
 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))
       return true;

 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
+
+## A section name matches two entries in the SECTIONS directive. The
+## first one doesn't have KEEP, the second one does. If section that have
+## KEEP is the first in order then section is NOT collected.
+# RUN: echo "SECTIONS { \
+# RUN:  .keep : { KEEP(*(.keep)) } \
+# RUN:  .nokeep : { *(.keep) }}" > %t.script
+# RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | \
+# RUN:   FileCheck -check-prefix=KEEP-AT-FIRST %s
+# KEEP-AT-FIRST:      Sections:
+# KEEP-AT-FIRST-NEXT:  Idx Name          Size      Address         Type
+# KEEP-AT-FIRST-NEXT:   0               00000000 0000000000000000 
+# KEEP-AT-FIRST-NEXT:   1 .keep         00000004 0000000000010120 DATA 
+# KEEP-AT-FIRST-NEXT:   2 .temp         00000004 0000000000010124 DATA 
+# KEEP-AT-FIRST-NEXT:   3 .text         00000007 0000000000011000 TEXT DATA 
+# KEEP-AT-FIRST-NEXT:   4 .symtab       00000060 0000000000000000 
+# KEEP-AT-FIRST-NEXT:   5 .shstrtab     0000002d 0000000000000000 
+# KEEP-AT-FIRST-NEXT:   6 .strtab       00000012 0000000000000000 
+
+## The same, but now section without KEEP is at first place.
+## It will be collected then.
+# RUN: echo "SECTIONS { \
+# RUN:  .nokeep : { *(.keep) } \
+# RUN:  .keep : { KEEP(*(.keep)) }}" > %t.script
+# RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | \
+# RUN:   FileCheck -check-prefix=KEEP-AT-SECOND %s
+# KEEP-AT-SECOND:      Sections:
+# KEEP-AT-SECOND-NEXT:  Idx Name          Size      Address         Type
+# KEEP-AT-SECOND-NEXT:   0               00000000 0000000000000000 
+# KEEP-AT-SECOND-NEXT:   1 .temp         00000004 0000000000010120 DATA 
+# KEEP-AT-SECOND-NEXT:   2 .text         00000007 0000000000011000 TEXT DATA 
+# KEEP-AT-SECOND-NEXT:   3 .symtab       00000048 0000000000000000 
+# KEEP-AT-SECOND-NEXT:   4 .shstrtab     00000027 0000000000000000 
+# KEEP-AT-SECOND-NEXT:   5 .strtab       0000000d 0000000000000000 
+
+.global _start
+_start:
+ mov temp, %eax
+
+.section .keep, "a"
+keep: 
+ .long 1
+
+.section .temp, "a"
+temp:
+ .long 2