[lld][LinkerScript] Add matching of output sections to segments

[denis-protivensky]

Summary

Add method to query segments for specified output section name. Return error if the section is assigned to unknown segment.
Check matching of sections to segments during layout on the subject of correctness.

NOTE: no actual functionality of using custom segments is implemented.

[silvas]

test/elf/linkerscript/phdrs-invalid.test

11–36

You can directly use llvm-mc instead of yaml2obj.

42–63

Can you put the RUN: lines and check lines in the corresponding files?
(you might need to add a lit.local.cfg that identifies the interesting suffixes as tests)

[denis-protivensky]

test/elf/linkerscript/phdrs-invalid.test

11–36

Good point, but I'd prefer to use yaml2obj for consistency with other tests in lld, and because we already have the corresponding yaml file, so there's no need to add another one with assembly code.

42–63

Don't understand the purpose of separating test cases. My intent was to logically group similar tests in one file. Moreover, I won't be able to split up phdrs-default.test file above in the same fasion without test code duplication.

[silvas]

test/elf/linkerscript/phdrs-invalid.test

11–36

There's been discussion about this recently on the mailing lists. Whichever tool is most convenient should be used (in this case, llvm-mc is clearly the most convenient). Generally speaking, yaml2obj has been overused in LLD.

[silvas]

test/elf/linkerscript/phdrs-invalid.test

42–63

It's not so much about having them separate as it is about having good locality of the check lines with the actual input file (in this case the linker script).

I can see the benefit in this case of having them together though.

I'll leave it to another reviewer to decide on what is best in this case.

[silvas]

test/elf/linkerscript/phdrs-invalid.test

11–36

Actually now that I think about it (and discuss with Bigcheese), what this is testing is completely independent of the actual section content, so it doesn't make sense to have an assembly input (or an input generated from assembly). I think that yaml2obj is the right tool here, and that the test case can be significantly reduced from one generated from the one you would get from the assembly.

[Bigcheese]

include/lld/ReaderWriter/LinkerScript.h

1449

Why are you storing the error here? It should be emitted when the error is encountered. Also, I think that SmallVector<..., 2> would be better here.

[denis-protivensky]

include/lld/ReaderWriter/LinkerScript.h

1449

Good, will change to throw an error upon encountered and replace the vector.

test/elf/linkerscript/phdrs-invalid.test

11–36

Yeah, that's right. I'm intrested in sections as the input, not the assembly code.

[denis-protivensky]

Updated:

• return error immediately when encountered
• use SmallVector instead of std::vector for holding matched headers for sections

[Bigcheese]

lgtm

include/lld/Core/Error.h

 }
 
 const std::error_category &LinkerScriptReaderCategory();
 
 enum class LinkerScriptReaderError {
   success = 0,
   parse_error,
   unknown_symbol_in_expr,
-  unrecognized_function_in_expr
+  unrecognized_function_in_expr,
+  unknown_phdr_ids,
 };
 
 inline std::error_code make_error_code(LinkerScriptReaderError e) {
   return std::error_code(static_cast<int>(e), LinkerScriptReaderCategory());
 }
 
 /// Creates an error_code object that has associated with it an arbitrary
 /// error messsage.  The value() of the error_code will always be non-zero

include/lld/ReaderWriter/LinkerScript.h

 #ifndef LLD_READER_WRITER_LINKER_SCRIPT_H
 #define LLD_READER_WRITER_LINKER_SCRIPT_H
 
 #include "lld/Core/Error.h"
 #include "lld/Core/LLVM.h"
 #include "lld/Core/range.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <memory>
static bool classof(const Command *c) {
     return c->getKind() == Kind::OutputSectionDescription;
   }
 
   void dump(raw_ostream &os) const override;
 
   const_iterator begin() const { return _outputSectionCommands.begin(); }
   const_iterator end() const { return _outputSectionCommands.end(); }
   StringRef name() const { return _sectionName; }
+  bool isDiscarded() const { return _discard; }
+  ArrayRef<StringRef> PHDRs() const { return _phdrs; }
 
 private:
   StringRef _sectionName;
   const Expression *_address;
   const Expression *_align;
   const Expression *_subAlign;
   const Expression *_at;
   const Expression *_fillExpr;

 class PHDR {
 public:
   PHDR(StringRef name, uint64_t type, bool includeFileHdr, bool includePHDRs,
        const Expression *at, uint64_t flags)
       : _name(name), _type(type), _includeFileHdr(includeFileHdr),
         _includePHDRs(includePHDRs), _at(at), _flags(flags) {}
 
   ~PHDR() = delete;
+  StringRef name() const { return _name; }
 
   void dump(raw_ostream &os) const;
 
+  /// Special header that discards output sections assigned to it.
+  static const PHDR *NONE;
+
 private:
   StringRef _name;
   uint64_t _type;
   bool _includeFileHdr;
   bool _includePHDRs;
   const Expression *_at;
   uint64_t _flags;
 };
public:
   /// Retrieve the set of symbols defined in linker script expressions.
   const llvm::StringSet<> &getScriptDefinedSymbols() const;
 
   /// Queries the linker script symbol table for the value of a given symbol.
   /// This function must be called after linker script expressions evaluation
   /// has been performed (by calling evalExpr() for all expressions).
   uint64_t getLinkerScriptExprValue(StringRef name) const;
 
+  /// Retrieve all the headers the given output section is assigned to.
+  /// Error is returned if the output section is assigned to headers with
+  /// missing declarations.
+  std::error_code
+  getPHDRsForOutputSection(StringRef name,
+                           std::vector<const PHDR *> &phdrs) const;
+
   void dump() const;
 
 private:
   /// A custom hash operator to teach the STL how to handle our custom keys.
   /// This will be used in our hash table mapping Sections to a Layout Order
   /// number (caching results).
   struct SectionKeyHash {
     int64_t operator()(const SectionKey &k) const {
private:
   int getLayoutOrder(const SectionKey &key, bool coarse) const;
 
   /// Compare two sections that have the same mapping rule (i.e., are matched
   /// by the same InputSectionsCmd).
   /// Determine if lhs < rhs by analyzing the InputSectionsCmd structure.
   bool localCompare(int order, const SectionKey &lhs,
                     const SectionKey &rhs) const;
 
+  /// Build map that matches output section names to segments they should be
+  /// put into.
+  std::error_code buildSectionToPHDR();
 
   /// Our goal with all linearizeAST overloaded functions is to
   /// traverse the linker script AST while putting nodes in a vector and
   /// thus enforcing order among nodes (which comes first).
   ///
   /// The order among nodes is determined by their indexes in this vector
   /// (_layoutCommands). This index allows us to solve the problem of
   /// establishing the order among two different input sections: we match each
private:
   std::vector<const Command *> _layoutCommands;
   std::unordered_multimap<std::string, int> _memberToLayoutOrder;
   std::vector<std::pair<StringRef, int>> _memberNameWildcards;
   mutable std::unordered_map<SectionKey, int, SectionKeyHash, SectionKeyEq>
       _cacheSectionOrder, _cacheExpressionOrder;
   llvm::DenseSet<int> _deliveredExprs;
   mutable llvm::StringSet<> _definedSymbols;
 
+  bool _parsedPHDRS;
+  llvm::StringMap<llvm::SmallVector<const PHDR *, 2>> _sectionToPHDR;
+
   Expression::SymbolTableTy _symbolTable;
 };
 
 llvm::BumpPtrAllocator &Command::getAllocator() const {
   return _ctx.getAllocator();
 }
 llvm::BumpPtrAllocator &Expression::getAllocator() const {
   return _ctx.getAllocator();
 }
 } // end namespace script
 } // end namespace lld
 
 #endif

lib/Core/Error.cpp

case LinkerScriptReaderError::success:
       return "Success";
     case LinkerScriptReaderError::parse_error:
       return "Error parsing linker script";
     case LinkerScriptReaderError::unknown_symbol_in_expr:
       return "Unknown symbol found when evaluating linker script expression";
     case LinkerScriptReaderError::unrecognized_function_in_expr:
       return "Unrecognized function call when evaluating linker script "
              "expression";
+    case LinkerScriptReaderError::unknown_phdr_ids:
+      return "Unknown header identifiers (missing in PHDRS command) are used";
     }
     llvm_unreachable("An enumerator of LinkerScriptReaderError does not have a "
                      "message defined.");
   }
 };
 
 const std::error_category &lld::LinkerScriptReaderCategory() {
   static _LinkerScriptReaderErrorCategory o;

lib/ReaderWriter/ELF/TargetLayout.h

AtomLayout *findAbsoluteAtom(StringRef name) {
     if (iter == _absoluteAtoms.end())
       return nullptr;
     return *iter;
   }
 
   // Output sections with the same name into a OutputSection
   void createOutputSections();
 
+  // Check that output section has proper segment set
+  void checkOutputSectionSegment(const OutputSection<ELFT> *sec);
+
   /// \brief Sort the sections by their order as defined by the layout,
   /// preparing all sections to be assigned to a segment.
   virtual void sortInputSections();
 
   /// \brief Add extra chunks to a segment just before including the input
   /// section given by <archivePath, memberPath, sectionName>. This
   /// is used to add linker script expressions before each section.
   virtual void addExtraChunksToSegment(Segment<ELFT> *segment,

lib/ReaderWriter/ELF/TargetLayout.cpp

const std::pair<StringRef, OutputSection<ELFT> *> currentOutputSection(
         section->outputSectionName(), nullptr);
     std::pair<typename OutputSectionMapT::iterator, bool> outputSectionInsert(
         _outputSectionMap.insert(currentOutputSection));
     if (!outputSectionInsert.second) {
       outputSection = outputSectionInsert.first->second;
     } else {
       outputSection = new (_allocator.Allocate<OutputSection<ELFT>>())
           OutputSection<ELFT>(section->outputSectionName());
+      checkOutputSectionSegment(outputSection);
       _outputSections.push_back(outputSection);
       outputSectionInsert.first->second = outputSection;
     }
     outputSection->appendSection(section);
   }
 }
 
+// Check that output section has proper segment set
+template <class ELFT>
+void TargetLayout<ELFT>::checkOutputSectionSegment(
+    const OutputSection<ELFT> *sec) {
+  std::vector<const script::PHDR *> phdrs;
+  if (_linkerScriptSema.getPHDRsForOutputSection(sec->name(), phdrs)) {
+    llvm::report_fatal_error(
+        "Linker script has wrong segments set for output sections");
+  }
+}
+
 template <class ELFT>
 uint64_t
 TargetLayout<ELFT>::getLookupSectionFlags(const OutputSection<ELFT> *os) const {
   uint64_t flags = os->flags();
   if (!(flags & llvm::ELF::SHF_WRITE) && _ctx.mergeRODataToTextSegment())
     flags &= ~llvm::ELF::SHF_EXECINSTR;
 
   // Merge string sections into Data segment itself

lib/ReaderWriter/LinkerScript.cpp

if (_at) {
     _at->dump(os);
     os << ")";
   }
   if (_flags)
     os << " FLAGS (" << _flags << ")";
   os << ";\n";
 }
 
+static PHDR none("NONE", 0, false, false, NULL, 0);
+const PHDR *PHDR::NONE = &none;
+
 void PHDRS::dump(raw_ostream &os) const {
   os << "PHDRS\n{\n";
   for (auto &&phdr : _phdrs) {
     phdr->dump(os);
   }
   os << "}\n";
 }
 
Extern *Parser::parseExtern() {
 
   if (!expectAndConsume(Token::r_paren, "expected symbol in EXTERN."))
     return nullptr;
 
   return new (_alloc) Extern(*this, symbols);
 }
 
 // Sema member functions
-Sema::Sema()
-    : _scripts(), _layoutCommands(), _memberToLayoutOrder(),
-      _memberNameWildcards(), _cacheSectionOrder(), _cacheExpressionOrder(),
-      _deliveredExprs(), _symbolTable() {}
+Sema::Sema() : _parsedPHDRS(false) {}
 
 void Sema::perform() {
   for (auto &parser : _scripts)
     perform(parser->get());
 }
 
 bool Sema::less(const SectionKey &lhs, const SectionKey &rhs) const {
   int a = getLayoutOrder(lhs, true);

 }
 
 uint64_t Sema::getLinkerScriptExprValue(StringRef name) const {
   auto it = _symbolTable.find(name);
   assert (it != _symbolTable.end() && "Invalid symbol name!");
   return it->second;
 }
 
+std::error_code
+Sema::getPHDRsForOutputSection(StringRef name,
+                               std::vector<const PHDR *> &phdrs) const {
+  // Cache results if not done yet.
+  if (auto ec = const_cast<Sema *>(this)->buildSectionToPHDR())
+    return ec;
+
+  auto vec = _sectionToPHDR.lookup(name);
+  std::copy(std::begin(vec), std::end(vec), std::back_inserter(phdrs));
+  return std::error_code();
+}
+
 void Sema::dump() const {
   raw_ostream &os = llvm::outs();
   os << "Linker script semantics dump\n";
   int num = 0;
   for (auto &parser : _scripts) {
     os << "Dumping script #" << ++num << ":\n";
     parser->get()->dump(os);
     os << "\n";
for (const InputSection *inputSection : *cmd) {
     return compareSortedNames(sortedGroup->sortMode(), lhs.sectionName,
                               rhs.sectionName);
   }
 
   llvm_unreachable("");
   return false;
 }
 
+std::error_code Sema::buildSectionToPHDR() {
+  if (_parsedPHDRS)
+    return std::error_code();
+  _parsedPHDRS = true;
+
+  // No scripts - nothing to do.
+  if (_scripts.empty() || _layoutCommands.empty())
+    return std::error_code();
+
+  // Collect all header declarations.
+  llvm::StringMap<const PHDR *> phdrs;
+  for (auto &parser : _scripts) {
+    for (auto *cmd : parser->get()->_commands) {
+      if (auto *ph = dyn_cast<PHDRS>(cmd)) {
+        for (auto *p : *ph)
+          phdrs[p->name()] = p;
+      }
+    }
+  }
+  const bool noPhdrs = phdrs.empty();
+
+  // Add NONE header to the map provided there's no user-defined
+  // header with the same name.
+  if (!_sectionToPHDR.count(PHDR::NONE->name()))
+    phdrs[PHDR::NONE->name()] = PHDR::NONE;
+
+  // Match output sections to available headers.
+  llvm::SmallVector<const PHDR *, 2> phdrsCur, phdrsLast { PHDR::NONE };
+  for (const Command *cmd : _layoutCommands) {
+    auto osd = dyn_cast<OutputSectionDescription>(cmd);
+    if (!osd || osd->isDiscarded())
+      continue;
+
+    phdrsCur.clear();
+    for (StringRef name : osd->PHDRs()) {
+      auto it = phdrs.find(name);
+      if (it == phdrs.end()) {
+        return LinkerScriptReaderError::unknown_phdr_ids;
+      }
+      phdrsCur.push_back(it->second);
+    }
+
+    // If no headers and no errors - insert empty headers set.
+    // If the current set of headers is empty, then use the last non-empty
+    // set. Otherwise mark the current set to be the last non-empty set for
+    // successors.
+    if (noPhdrs)
+      phdrsCur.clear();
+    else if (phdrsCur.empty())
+      phdrsCur = phdrsLast;
+    else
+      phdrsLast = phdrsCur;
+
+    _sectionToPHDR[osd->name()] = phdrsCur;
+  }
+  return std::error_code();
+}
+
 static bool hasWildcard(StringRef name) {
   for (auto ch : name)
     if (ch == '*' || ch == '?' || ch == '[' || ch == '\\')
       return true;
   return false;
 }
 
 void Sema::linearizeAST(const InputSection *inputSection) {

test/elf/linkerscript/phdrs-default.test

+/*
+This group of tests checks usage of default headers during linking,
+when PHDRS command is not defined or defined empty in linker scripts.
+
+This test uses a single X86-64 input object, simple.o, created with the
+following X86-64 assembly code:
+
+*** simple.S:
+
+(command line clang -c simple.S -o simple.o)
+
+      .text
+      main:
+        mov $1, %eax
+        movq $1, %rdi
+        movq $msg, %rsi
+        movq $14, %rdx
+        syscall
+        ret
+
+        .globl _start
+      _start:
+        call  main
+        mov $60, %eax
+        syscall
+        ret
+
+      .data
+      msg: .asciz "Hello, World!\n"
+*/
+
+/*
+Prepare the object file to test on.
+
+RUN: yaml2obj -format=elf %p/Inputs/simple.o.yaml -o=%t.o
+*/
+
+/*
+Test when no linker script passed.
+
+RUN: lld -flavor gnu -target x86_64 %t.o -static -o %t1
+RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix SECTIONS %s
+RUN: llvm-readobj -program-headers %t1 | FileCheck -check-prefix HEADERS %s
+
+SECTIONS: .text {{[0-9a-f]+}} 00000000004000b0
+SECTIONS: .data {{[0-9a-f]+}} 0000000000401000
+
+HEADERS: ProgramHeader {
+HEADERS: Type: PT_LOAD (0x1)
+HEADERS: VirtualAddress: 0x400000
+HEADERS: }
+HEADERS: ProgramHeader {
+HEADERS: Type: PT_LOAD (0x1)
+HEADERS: VirtualAddress: 0x401000
+HEADERS: }
+*/
+
+/*
+Test when linker script doesn't contain PHDRS and sections are not assigned to any segments.
+
+RUN: lld -flavor gnu -target x86_64 -T %p/phdrs/sections-no-phdrs.script %t.o -static -o %t2
+RUN: llvm-objdump -section-headers %t2 | FileCheck -check-prefix SECTIONS %s
+RUN: llvm-readobj -program-headers %t2 | FileCheck -check-prefix HEADERS %s
+*/
+
+/*
+Test when linker script contains empty PHDRS and sections are not assigned to any segments.
+
+RUN: lld -flavor gnu -target x86_64 -T %p/phdrs/sections-empty-phdrs.script %t.o -static -o %t3
+RUN: llvm-objdump -section-headers %t3 | FileCheck -check-prefix SECTIONS %s
+RUN: llvm-readobj -program-headers %t3 | FileCheck -check-prefix HEADERS %s
+*/
+
+/*
+Test when linker script contains empty PHDRS and sections are only assigned to NONE segments
+or not assigned at all.
+NOTE: Segments with the name NONE are ignored in such a case.
+
+RUN: lld -flavor gnu -target x86_64 -T %p/phdrs/sections-none-phdrs.script %t.o -static -o %t4
+RUN: llvm-objdump -section-headers %t4 | FileCheck -check-prefix SECTIONS %s
+RUN: llvm-readobj -program-headers %t4 | FileCheck -check-prefix HEADERS %s
+*/

test/elf/linkerscript/phdrs-invalid.test

+/*
+This group of tests checks invalid cases of defining and using PHDRS
+command in linker scripts.
+
+This test uses a single X86-64 input object, simple.o, created with the
+following X86-64 assembly code:
+
+*** simple.S:
+
+(command line clang -c simple.S -o simple.o)
+
+      .text
+      main:
+        mov $1, %eax
+        movq $1, %rdi
+        movq $msg, %rsi
+        movq $14, %rdx
+        syscall
+        ret
+
+        .globl _start
+      _start:
+        call  main
+        mov $60, %eax
+        syscall
+        ret
+
+      .data
+      msg: .asciz "Hello, World!\n"
+*/
+
+/*
+Prepare the object file to test on.
+
+RUN: yaml2obj -format=elf %p/Inputs/simple.o.yaml -o=%t.o
+*/
+
+/*
+Test undefined header used when no PHDRS defined.
+
+RUN: not lld -flavor gnu -target x86_64 -T %p/phdrs/undef-no-phdrs.script %t.o -static -o %t1 &> %t1-error
+RUN: FileCheck -check-prefix UNDEF-NO-PHDRS %s < %t1-error
+
+UNDEF-NO-PHDRS: Linker script has wrong segments set for output sections
+*/
+
+/*
+Test undefined header used when PHDRS is empty.
+
+RUN: not lld -flavor gnu -target x86_64 -T %p/phdrs/undef-empty-phdrs.script %t.o -static -o %t2 &> %t2-error
+RUN: FileCheck -check-prefix UNDEF-EMPTY-PHDRS %s < %t2-error
+
+UNDEF-EMPTY-PHDRS: Linker script has wrong segments set for output sections
+*/
+
+/*
+Test undefined header used when PHDRS contains definitions.
+
+RUN: not lld -flavor gnu -target x86_64 -T %p/phdrs/undef-id-phdrs.script %t.o -static -o %t3 &> %t3-error
+RUN: FileCheck -check-prefix UNDEF-ID-PHDRS %s < %t3-error
+
+UNDEF-ID-PHDRS: Linker script has wrong segments set for output sections
+*/

test/elf/linkerscript/phdrs/sections-empty-phdrs.script

+ENTRY(_start)
+
+PHDRS
+{
+}
+
+SECTIONS
+{
+  .text : { *(.text) }
+  .data : { *(.data) }
+}

test/elf/linkerscript/phdrs/sections-no-phdrs.script

+ENTRY(_start)
+
+SECTIONS
+{
+  .text : { *(.text) }
+  .data : { *(.data) }
+}

test/elf/linkerscript/phdrs/sections-none-phdrs.script

+ENTRY(_start)
+
+PHDRS
+{
+}
+
+SECTIONS
+{
+  .text : { *(.text) } :NONE
+  .data : { *(.data) }
+}

test/elf/linkerscript/phdrs/undef-empty-phdrs.script

+ENTRY(_start)
+
+PHDRS
+{
+}
+
+SECTIONS
+{
+  .text : { *(.text) }
+  .data : { *(.data) } :phdr
+}

test/elf/linkerscript/phdrs/undef-id-phdrs.script

+ENTRY(_start)
+
+PHDRS
+{
+  phdr PT_LOAD;
+}
+
+SECTIONS
+{
+  .text : { *(.text) } :phdr_wrong
+  .data : { *(.data) }
+}

test/elf/linkerscript/phdrs/undef-no-phdrs.script

+ENTRY(_start)
+
+SECTIONS
+{
+  .text : { *(.text) } :phdr
+  .data : { *(.data) }
+}