ELF2: Add basic linker script support.

[ruiu]

Summary

This linker script parser and evaluator is powerful enough to read
Linux's libc.so, which is (despite its name) a linker script that
contains OUTPUT_FORMAT, GROUP and AS_NEEDED directives.

The parser implemented in this patch is a recursive-descendent one.
It does *not* construct an AST but consumes directives in place and
sets the results to the Config object, like Driver is doing. This
should be very fast since less objects are allocated, and this is
also more readable.

[silvas]

test/elf2/basic.s

181

typo: response

test/elf2/invalid-elf.test

1–8 ↗

(On Diff #35934)

Why is this test affected?

[ruiu]

test/elf2/invalid-elf.test

1–8 ↗

(On Diff #35935)

Because these invalid ELF files are not actually recognized as ELF files by their magic bytes. Previously, they were tried to be parsed as ELF files anyways. Now all files that have unrecognized magic are parsed as linker scripts. So these errors are not printed.

[ruiu]

Fix typo, remove debug output, and fix indentation.

[silvas]

test/elf2/invalid-elf.test

1–8 ↗

(On Diff #35936)

But you did not remove the place where we print the error message. Should we convert the error messages into assertions?

[ruiu]

Rebased to head

[• rafael]

ELF/DriverUtils.cpp

203

This opens a file, mmaps it, calls identify_magic and then drops everything and returns a bool :-(

Could this be reorganized into something like

addInptsForArg(StringRef Arg) {

open file
check type
 if (archiver or elf) {
    add it.
    return;
}
parse linker script.

}

That way we only open, mmap and identify each file once.

[ikudrin]

ELF/DriverUtils.cpp

203

What if we remove intermediate containers like Inputs or InputFiles and just put all files into SymbolTable directly? Anyway, I'm going to suggest this change in my next patch for support --[no-]whole-archive.

[ruiu]

Open file only once.

[• rafael]

Please git-clang-format the patch.

It is still undesirable that we call identify_magic twice, but we can work on that on another patch.

LGTM with the patch git-clang-formated.

Thanks a lot!

[ruiu]

Committed as r248918. Thanks!

[Eugene.Zelenko]

Committed in r248918.

ELF/Driver.h

 //===- Driver.h -------------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_DRIVER_H
 #define LLD_ELF_DRIVER_H
 
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Option/ArgList.h"
 
 namespace lld {
 namespace elf2 {
 
+class SymbolTable;
+
+// The owner of all opened files.
+extern std::vector<std::unique_ptr<MemoryBuffer>> *MemoryBufferPool;
+MemoryBufferRef openFile(StringRef Path);
+
 // Entry point of the ELF linker.
 void link(ArrayRef<const char *> Args);
 
 class ArgParser {
 public:
   // Parses command line options.
   llvm::opt::InputArgList parse(ArrayRef<const char *> Args);
 
 private:
   llvm::BumpPtrAllocator Alloc;
 };
 
 class LinkerDriver {
 public:
   void link(ArrayRef<const char *> Args);
 
 private:
   ArgParser Parser;
-
-  // Opens a file. Path has to be resolved already.
-  MemoryBufferRef openFile(StringRef Path);
-
-  // Driver is the owner of all opened files.
-  // InputFiles have MemoryBufferRefs to them.
-  std::vector<std::unique_ptr<MemoryBuffer>> OwningMBs;
 };
 
 // Create enum with OPT_xxx values for each option in Options.td
 enum {
   OPT_INVALID = 0,
 #define OPTION(_1, _2, ID, _4, _5, _6, _7, _8, _9, _10, _11) OPT_##ID,
 #include "Options.inc"
 #undef OPTION
 };
 
+// Parses a linker script. Calling this function updates the Symtab and Config.
+void readLinkerScript(SymbolTable *Symtab, MemoryBufferRef MB);
+
 } // namespace elf2
 } // namespace lld
 
 #endif

ELF/Driver.cpp

 
 using namespace llvm;
 
 using namespace lld;
 using namespace lld::elf2;
 
 namespace lld {
 namespace elf2 {
+
 Configuration *Config;
+std::vector<std::unique_ptr<MemoryBuffer>> *MemoryBufferPool;
 
 void link(ArrayRef<const char *> Args) {
   Configuration C;
   Config = &C;
+  std::vector<std::unique_ptr<MemoryBuffer>> V;
+  MemoryBufferPool = &V;
   LinkerDriver().link(Args.slice(1));
 }
 
-}
-}
-
 // Opens a file. Path has to be resolved already.
 // Newly created memory buffers are owned by this driver.
-MemoryBufferRef LinkerDriver::openFile(StringRef Path) {
+MemoryBufferRef openFile(StringRef Path) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> MBOrErr = MemoryBuffer::getFile(Path);
   error(MBOrErr, Twine("cannot open ") + Path);
   std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
   MemoryBufferRef MBRef = MB->getMemBufferRef();
-  OwningMBs.push_back(std::move(MB)); // take ownership
+  MemoryBufferPool->push_back(std::move(MB)); // transfer ownership
   return MBRef;
 }
 
-static std::unique_ptr<InputFile> createFile(MemoryBufferRef MB) {
-  using namespace llvm::sys::fs;
-  file_magic Magic = identify_magic(MB.getBuffer());
-
-  if (Magic == file_magic::archive)
-    return make_unique<ArchiveFile>(MB);
-
-  if (Magic == file_magic::elf_shared_object)
-    return createELFFile<SharedFile>(MB);
-
-  return createELFFile<ObjectFile>(MB);
+}
 }
 
 // Makes a path by concatenating Dir and File.
 // If Dir starts with "=" the result will be preceded by SysRoot,
 // which can be set with --sysroot command line switch.
 static std::string buildSysrootedPath(StringRef Dir, StringRef File) {
   SmallString<128> Path;
   if (Dir.startswith("=")) {
for (const std::string &Name : Names) {
       std::string FullPath = buildSysrootedPath(Dir, Name);
       if (sys::fs::exists(FullPath))
         return FullPath;
     }
   }
   error(Twine("Unable to find library -l") + Path);
 }
 
+// Returns true if MB looks like a linker script.
+static bool isLinkerScript(MemoryBufferRef MB) {
+  using namespace llvm::sys::fs;
+  file_magic Magic = identify_magic(MB.getBuffer());
+  return Magic == file_magic::unknown;
+}
+
 void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   // Parse command line options.
   opt::InputArgList Args = Parser.parse(ArgsArr);
 
   if (auto *Arg = Args.getLastArg(OPT_output))
     Config->OutputFile = Arg->getValue();
 
   if (auto *Arg = Args.getLastArg(OPT_dynamic_linker))
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   Config->AllowMultipleDefinition = Args.hasArg(OPT_allow_multiple_definition);
   Config->DiscardAll = Args.hasArg(OPT_discard_all);
   Config->DiscardLocals = Args.hasArg(OPT_discard_locals);
   Config->DiscardNone = Args.hasArg(OPT_discard_none);
   Config->ExportDynamic = Args.hasArg(OPT_export_dynamic);
   Config->NoInhibitExec = Args.hasArg(OPT_noinhibit_exec);
   Config->Shared = Args.hasArg(OPT_shared);
 
-  // Create a list of input files.
-  std::vector<MemoryBufferRef> Inputs;
+  // Create a symbol table.
+  SymbolTable Symtab;
 
   for (auto *Arg : Args.filtered(OPT_l, OPT_INPUT)) {
-    StringRef Path = Arg->getValue();
-    if (Arg->getOption().getID() == OPT_l) {
-      Inputs.push_back(openFile(searchLibrary(Path)));
+    std::string Path = Arg->getValue();
+    if (Arg->getOption().getID() == OPT_l)
+      Path = searchLibrary(Path);
+    MemoryBufferRef MB = openFile(Path);
+    if (isLinkerScript(MB)) {
+      // readLinkerScript may add files to the symbol table.
+      readLinkerScript(&Symtab, MB);
       continue;
     }
-    Inputs.push_back(openFile(Path));
+    Symtab.addFile(createFile(MB));
   }
 
-  if (Inputs.empty())
+  if (Symtab.getObjectFiles().empty())
     error("no input files.");
 
-  // Create a symbol table.
-  SymbolTable Symtab;
-
-  // Parse all input files and put all symbols to the symbol table.
-  // The symbol table will take care of name resolution.
-  for (MemoryBufferRef MB : Inputs) {
-    std::unique_ptr<InputFile> File = createFile(MB);
-    Symtab.addFile(std::move(File));
-  }
-
   // Write the result.
   const ELFFileBase *FirstObj = Symtab.getFirstELF();
   switch (FirstObj->getELFKind()) {
   case ELF32LEKind:
     writeResult<object::ELF32LE>(&Symtab);
     return;
   case ELF32BEKind:
     writeResult<object::ELF32BE>(&Symtab);

ELF/DriverUtils.cpp

 //===- DriverUtils.cpp ----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains utility functions for the driver. Because there
 // are so many small functions, we created this separate file to make
 // Driver.cpp less cluttered.
 //
 //===----------------------------------------------------------------------===//
 
+#include "Config.h"
 #include "Driver.h"
 #include "Error.h"
+#include "SymbolTable.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;
 
 using namespace lld;
 using namespace lld::elf2;
 
 // Create OptTable
opt::InputArgList ArgParser::parse(ArrayRef<const char *> Argv) {
   iterator_range<opt::arg_iterator> Unknowns = Args.filtered(OPT_UNKNOWN);
   for (auto *Arg : Unknowns)
     warning("warning: unknown argument: " + Arg->getSpelling());
   if (Unknowns.begin() != Unknowns.end())
     error("unknown argument(s) found");
 
   return Args;
 }
+
+// Parser and evaluator of the linker script.
+// Results are directly written to the Config object.
+namespace {
+class LinkerScript {
+public:
+  LinkerScript(SymbolTable *T, StringRef S) : Symtab(T), Tokens(tokenize(S)) {}
+  void run();
+
+private:
+  static std::vector<StringRef> tokenize(StringRef S);
+  static StringRef skipSpace(StringRef S);
+  StringRef next();
+  bool atEOF() { return Tokens.size() == Pos; }
+  void expect(StringRef Expect);
+
+  void readAsNeeded();
+  void readGroup();
+  void readOutputFormat();
+
+  SymbolTable *Symtab;
+  std::vector<StringRef> Tokens;
+  size_t Pos = 0;
+};
+}
+
+void LinkerScript::run() {
+  while (!atEOF()) {
+    StringRef Tok = next();
+    if (Tok == "GROUP") {
+      readGroup();
+    } else if (Tok == "OUTPUT_FORMAT") {
+      readOutputFormat();
+    } else {
+      error("unknown directive: " + Tok);
+    }
+  }
+}
+
+// Split S into linker script tokens.
+std::vector<StringRef> LinkerScript::tokenize(StringRef S) {
+  std::vector<StringRef> Ret;
+  for (;;) {
+    S = skipSpace(S);
+    if (S.empty())
+      return Ret;
+    size_t Pos = S.find_first_not_of(
+          "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
+          "0123456789_.$/\\~=+[]*?-:");
+    // A character that cannot start a word (which is usually a
+    // punctuation) forms a single character token.
+    if (Pos == 0)
+      Pos = 1;
+    Ret.push_back(S.substr(0, Pos));
+    S = S.substr(Pos);
+  }
+}
+
+// Skip leading whitespace characters or /**/-style comments.
+StringRef LinkerScript::skipSpace(StringRef S) {
+  for (;;) {
+    if (S.startswith("/*")) {
+      size_t E = S.find("*/", 2);
+      if (E == StringRef::npos)
+        error("unclosed comment in a linker script");
+      S = S.substr(E + 2);
+      continue;
+    }
+    size_t Size = S.size();
+    S = S.ltrim();
+    if (S.size() == Size)
+      return S;
+  }
+}
+
+StringRef LinkerScript::next() {
+  if (Pos == Tokens.size())
+    error("unexpected EOF");
+  return Tokens[Pos++];
+}
+
+void LinkerScript::expect(StringRef Expect) {
+  StringRef Tok = next();
+  if (Tok != Expect)
+    error(Expect + " expected, but got " + Tok);
+}
+
+void LinkerScript::readAsNeeded() {
+  expect("(");
+  for (;;) {
+    StringRef Tok = next();
+    if (Tok == ")")
+      return;
+    Symtab->addFile(createFile(openFile(Tok)));
+  }
+}
+
+void LinkerScript::readGroup() {
+  expect("(");
+  for (;;) {
+    StringRef Tok = next();
+    if (Tok == ")")
+      return;
+    if (Tok == "AS_NEEDED") {
+      readAsNeeded();
+      continue;
+    }
+    Symtab->addFile(createFile(openFile(Tok)));
+  }
+}
+
+void LinkerScript::readOutputFormat() {
+  // Error checking only for now.
+  expect("(");
+  next();
+  expect(")");
+}
+
+void lld::elf2::readLinkerScript(SymbolTable *Symtab, MemoryBufferRef MB) {
+  LinkerScript(Symtab, MB.getBuffer()).run();
+}

ELF/InputFiles.h

 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf2 {
 
 using llvm::object::Archive;
 
+class InputFile;
 class Lazy;
 class SymbolBody;
 
+std::unique_ptr<InputFile> createFile(MemoryBufferRef MB);
+
 // The root class of input files.
 class InputFile {
 public:
   enum Kind { ObjectKind, SharedKind, ArchiveKind };
   Kind kind() const { return FileKind; }
   virtual ~InputFile() {}
 
   // Reads a file (constructors don't do that).

ELF/InputFiles.cpp

 #include "InputSection.h"
 #include "Error.h"
 #include "Symbols.h"
 #include "llvm/ADT/STLExtras.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
+using namespace llvm::sys::fs;
 
 using namespace lld;
 using namespace lld::elf2;
 
+std::unique_ptr<InputFile> lld::elf2::createFile(MemoryBufferRef MB) {
+  file_magic Magic = identify_magic(MB.getBuffer());
+  if (Magic == file_magic::archive)
+    return make_unique<ArchiveFile>(MB);
+  if (Magic == file_magic::elf_shared_object)
+    return createELFFile<SharedFile>(MB);
+  return createELFFile<ObjectFile>(MB);
+}
+
 template <class ELFT> static uint16_t getEMachine(const ELFFileBase &B) {
   bool IsShared = isa<SharedFileBase>(B);
   if (IsShared)
     return cast<SharedFile<ELFT>>(B).getEMachine();
   return cast<ObjectFile<ELFT>>(B).getEMachine();
 }
 
 uint16_t ELFFileBase::getEMachine() const {

test/elf2/basic.s

 # CHECK-NEXT:     Flags [ (0x5)
 # CHECK-NEXT:       PF_R (0x4)
 # CHECK-NEXT:       PF_X (0x1)
 # CHECK-NEXT:     ]
 # CHECK-NEXT:     Alignment: 4096
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
+
+# Test for the response file
 # RUN: echo " -o %t2" > %t.responsefile
 # RUN: lld -flavor gnu2 %t @%t.responsefile
 # RUN: llvm-readobj -file-headers -sections -program-headers -symbols %t2 \
 # RUN:   | FileCheck %s
 
+# Test for the linker script
+# RUN: echo "GROUP(" %t ")" > %t.script
+# RUN: lld -flavor gnu2 -o %t2 %t.script
+# RUN: llvm-readobj -file-headers -sections -program-headers -symbols %t2 \
+# RUN:   | FileCheck %s
+
+# RUN: echo "OUTPUT_FORMAT(elf64-x86-64) /*/*/ GROUP(" %t ")" > %t.script
+# RUN: lld -flavor gnu2 -o %t2 %t.script
+# RUN: llvm-readobj -file-headers -sections -program-headers -symbols %t2 \
+# RUN:   | FileCheck %s
+
 # RUN: not lld -flavor gnu2 %t.foo -o %t2 2>&1 | \
 # RUN:  FileCheck --check-prefix=MISSING %s
 # MISSING: cannot open {{.*}}.foo: {{[Nn]}}o such file or directory
 
 # RUN: not lld -flavor gnu2 -o %t2 2>&1 | \
 # RUN:  FileCheck --check-prefix=NO_INPUT %s
 # NO_INPUT: no input files.
 

test/elf2/linkerscript.test

+# RUN: echo "FOO(BAR)" > %t.script
+# RUN: not lld -flavor gnu2 -o foo %t.script > %t.log 2>&1
+# RUN: FileCheck -check-prefix=ERR1 %s < %t.log
+
+ERR1: unknown directive: FOO