[lld] Implement --dynamic-list

[zatrazz]

Summary

This patch implements the --dynamic-list option, which adds a list of
global symbol that either should not be bounded by default definition
when creating shared libraries, or add in dynamic symbol table in the
case of creating executables.

The patch modifies the ScriptParserBase class to use a list of Token
instead of StringRef, which contains information if the token is a
quoted or unquoted strings. It is used to use a faster search for
exact match symbol name.

The input file follow a similar format of linker script with some
simplifications (it does not have scope or node names). It leads
to a simplified parser define in DynamicList.{cpp,h}.

Different from ld/gold neither glob pattern nor mangled names
(extern 'C++') are currently supported.

[grimar]

ELF/DynamicList.cpp

50

Its a bit strange function name, there is standart (http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly) saying that "Function names should be verb phrases (as they represent actions)"
So I would add "get":

getSupportedLanguage(StringRef Lang);

Probably "get" is not best word here, but it shows the idea. And also function name is uppercase, but should be lowercase.

116

Looks this can be simplified:

StringRef Entry = next();
if (Entry != "extern" || peek() == ";") {
  DynList->ExactMatch.insert(Entry);
  return;
}

StringRef Tok = next();
DynamicList::GlobLanguage Lang = SupportedLanguage(Tok);
if (Lang != DynamicList::LANGUAGE_NOT_SUPPORTED)
  readLanguageGroup(Lang);
else
  setError("invalid language in extern definition (" + Tok + ")");

121

You can remove brackets.

while (!atEOF())
  readGroup();

131

I would write:

return ExactMatch.find(Symbol) != ExactMatch.end();

ELF/Options.td

169

Not sorted.

[zatrazz]

ELF/DynamicList.cpp

50

In since language demangling is not really supported I will just remove this method.

116

Rui has asked to remove external demangling support, so I will simplify to just:

void DynamicListParser::readEntry() {
  DynList->ExactMatch.insert(next());
}

121

Ack.

[zatrazz]

Updated patch based on previous comments.

[ruiu]

ELF/Driver.cpp

42

I think it is better to not use DynList as a container of the list of dynamic list symbols. You can just add a new set to Config instead and use that as

if (Config->DynamicList.count(Sym.getName()))

or something like that.

143–149

You might want to make this piece of code a separate function because it is repeated at least twice.

ELF/DynamicList.cpp

35

You have an extra }.

65–67

I wouldn't make this a function because it's too short.

ELF/Writer.cpp

836–837 ↗

(On Diff #53279)

Adding code here is not a good idea because this piece of code would be executed for all symbols. That's too expensive.

Instead of doing that, run a loop for each symbols in the dynamic list and set MustBeInDynSym flag. It's much cheaper.

[zatrazz]

Updated patch based on previous comment.

[ruiu]

ELF/Config.h

54

Instead of adding DynamicList, please add DenseSet<StringRef>, because the simple set just works.

ELF/Driver.cpp

135

Since we handle errors inside this function, it is rather confusing to propagate a detailed error back to callers. I'd use llvm::Optional instead of ErrorOr.

136

Do you need this?

ELF/Writer.cpp

1115 ↗

(On Diff #53396)

This comment needs to be more explanatory.

// The dyanmic list is a feature to give a list of symbols that need
// to be exported via the dynamic symbol table. Here is where the
// dynamic list is processed.

1124 ↗

(On Diff #53396)

Why did you change this?

[zatrazz]

ELF/Config.h

54

Right, but since the idea is to visit each dynamic list entry to check against the Symtab symbols, why not just a std::vector<llvm::StringRef> as well?

ELF/Driver.cpp

42

Ack.

135

Ack.

136

I will remove it.

143–149

Ack.

ELF/DynamicList.cpp

35

Ack.

65–67

Ack.

ELF/Writer.cpp

1115 ↗

(On Diff #53396)

Ack.

1124 ↗

(On Diff #53396)

Because the list is already being copies above to be used in the dynamic list processing. Do we really need to get the mapvector again?

836–837 ↗

(On Diff #53279)

Ack.

[ruiu]

ELF/Config.h

54

Yeah. Set felt to be a right choice because it is logically a set, but since we are using vector<StringRef> for other things that are logically sets (e.g. Undefined), it probably makes sense more to make this a vector.

ELF/Writer.cpp

1124 ↗

(On Diff #53396)

I'm sorry but I don't get what you mean. SymtabSymbols is used only once here, so this seems to be just defining a redundant temporary variable and that makes a copy of the mapvector. Am I missing something?

[zatrazz]

ELF/Writer.cpp

1124 ↗

(On Diff #53396)

My mistake, I notice I am using the Symtab::find method instead. I will change it back.

[zatrazz]

Updated patch based on previous comments.

[ruiu]

ELF/Config.h

51–53

Sort.

ELF/Driver.h

25

Please don't use using in the header.

35

So you need to write llvm::Optional<...>

ELF/DynamicList.h

24–29

Now you can remove this class and replace it with readDynamicList function.

ELF/Writer.cpp

12 ↗

(On Diff #53448)

Remove.

1116 ↗

(On Diff #53448)

Remove {}

[zatrazz]

Updated patch based on previous comments.

[ruiu]

ELF/Driver.cpp

104

Remove llvm:: (since in this .cpp file we have using namespace llvm.)

136

Ditto

149

Ditto

320–321

This place does not seems the right position to add this code because this looks different from other lines just above this one. I'd probably add this at end of this function.

ELF/DynamicList.cpp

17–24

Remove unused includes. I don't think we need Driver.h, for example.

26–29

Please remove unused ones.

ELF/DynamicList.h

14–16

Remove.

22

Remove.

ELF/Options.td

169

Yes, please sort.

ELF/Writer.cpp

1112–1117 ↗

(On Diff #53552)

I don't think this piece of code needs to be added to this place. This function is large and complex, so no new code should be added unless it is absolutely needed. One way to avoid doing this is to move this code to SymbolTable.cpp just like scanShlibUndefines and call the new function from the driver.

[grimar]

test/ELF/invalid-dynamic-list.test

31

foobar, not foobaar

[zatrazz]

Updated patch based on previous comments.

[ruiu]

LGTM with a few nits. Thanks!

ELF/DynamicList.cpp

16–23

Do you need Driver.h, FileSystem.h, Path.h and StringSaver.h?

ELF/DynamicList.h

14

You can remove StringSet.h no?

ELF/Options.td

48

Let's use the same help message as gold. Read a list of dynamic symbols

[zatrazz]

ELF/DynamicList.cpp

16–23

Nops, I will remove it.

ELF/DynamicList.h

14

Yes, I will remove it.

ELF/Options.td

48

Ack.

ELF/CMakeLists.txt

 add_lld_library(lldELF
   Driver.cpp
   DriverUtils.cpp
+  DynamicList.cpp
   Error.cpp
   ICF.cpp
   InputFiles.cpp

ELF/Config.h

   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   std::string RPath;
+  std::vector<llvm::StringRef> DynamicList;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> Undefined;
   bool AllowMultipleDefinition;

ELF/Driver.h

 
 #include "SymbolTable.h"
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/Optional.h" 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Support/raw_ostream.h"

 
 private:
   std::vector<MemoryBufferRef> getArchiveMembers(MemoryBufferRef MB);
+  llvm::Optional<MemoryBufferRef> readFile(StringRef Path);
   void readConfigs(llvm::opt::InputArgList &Args);
+  void readDynamicList(StringRef Path);
   void createFiles(llvm::opt::InputArgList &Args);
   template <class ELFT> void link(llvm::opt::InputArgList &Args);
 

ELF/Driver.cpp

 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
+#include "DynamicList.h"
 #include "Config.h"
 #include "Error.h"
 #include "ICF.h"

   using namespace llvm::sys::fs;
   if (Config->Verbose || Config->Trace)
     llvm::outs() << Path << "\n";
-  auto MBOrErr = MemoryBuffer::getFile(Path);
-  if (!MBOrErr) {
-    error(MBOrErr, "cannot open " + Path);
+  Optional<MemoryBufferRef> Buffer = readFile(Path);
+  if (!Buffer.hasValue())
     return;
-  }
-  std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
-  MemoryBufferRef MBRef = MB->getMemBufferRef();
-  OwningMBs.push_back(std::move(MB)); // take MB ownership
+  MemoryBufferRef MBRef = *Buffer;
 
   switch (identify_magic(MBRef.getBuffer())) {
   case file_magic::unknown:

   }
 }
 
+Optional<MemoryBufferRef> LinkerDriver::readFile(StringRef Path) {
+  auto MBOrErr = MemoryBuffer::getFile(Path);
+  if (std::error_code EC = MBOrErr.getError()) {
+    error(MBOrErr, "cannot open " + Path);
+    return None;
+  }
+  std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
+  MemoryBufferRef MBRef = MB->getMemBufferRef();
+  OwningMBs.push_back(std::move(MB)); // take MB ownership
+  return MBRef;
+}
+
+void LinkerDriver::readDynamicList(StringRef Path) {
+  if (Optional<MemoryBufferRef> Buffer = readFile(Path))
+    parseDynamicList(*Buffer);
+}
+
 // Add a given library by searching it from input search paths.
 void LinkerDriver::addLibrary(StringRef Name) {
   std::string Path = searchLibrary(Name);

 
   for (auto *Arg : Args.filtered(OPT_undefined))
     Config->Undefined.push_back(Arg->getValue());
+
+  if (Args.hasArg(OPT_dynamic_list))
+    readDynamicList(getString(Args, OPT_dynamic_list));
 }
 
 void LinkerDriver::createFiles(opt::InputArgList &Args) {

 
   // Write the result to the file.
   Symtab.scanShlibUndefined();
+  Symtab.scanDynamicList();
   if (Config->GcSections)
     markLive<ELFT>(&Symtab);
   if (Config->ICF)

ELF/DynamicList.h

+//===- DynamicList.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_DYNAMIC_LIST_H
+#define LLD_ELF_DYNAMIC_LIST_H
+
+#include "lld/Core/LLVM.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/MemoryBuffer.h"
+
+namespace lld {
+namespace elf {
+
+void parseDynamicList(MemoryBufferRef MB);
+
+} // namespace elf
+} // namespace lld
+
+#endif

ELF/DynamicList.cpp

+//===- LinkerScript.cpp ---------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the parser/evaluator of the linker script.
+// It does not construct an AST but consume linker script directives directly.
+// Results are written to Driver or Config object.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DynamicList.h"
+#include "Config.h"
+#include "Driver.h"
+#include "ScriptParser.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/StringSaver.h"
+
+using namespace llvm;
+using namespace llvm::object;
+using namespace lld;
+using namespace lld::elf;
+
+// Parse the --dynamic-list argument.  A dynamic list is in the form
+//
+//  { symbol1; symbol2; [...]; symbolN };
+//
+// Multiple groups can be defined in the same file and they are merged
+// in only one definition.
+
+class DynamicListParser final : public ScriptParserBase {
+public:
+  DynamicListParser(StringRef S) : ScriptParserBase(S) {}
+
+  void run() override;
+
+private:
+  void readGroup();
+};
+
+// Parse the default group definition using C language symbol name.
+void DynamicListParser::readGroup() {
+  expect("{");
+  while (!Error) {
+    Config->DynamicList.push_back(next());
+    expect(";");
+    if (peek() == "}") {
+      next();
+      break;
+    }
+  }
+  expect(";");
+}
+
+void DynamicListParser::run() {
+  while (!atEOF())
+    readGroup();
+}
+
+void elf::parseDynamicList(MemoryBufferRef MB) {
+  DynamicListParser(MB.getBuffer()).run();
+}

ELF/Options.td

 def dynamic_linker : Separate<["--", "-"], "dynamic-linker">,
   HelpText<"Which dynamic linker to use">;
 
+def dynamic_list : Separate<["--", "-"], "dynamic-list">,
+  HelpText<"Dynamic list to use">;
+
 def eh_frame_hdr : Flag<["--"], "eh-frame-hdr">,
   HelpText<"Request creation of .eh_frame_hdr section and PT_GNU_EH_FRAME segment header">;
 

 def alias_L__library_path : Joined<["--"], "library-path=">, Alias<L>;
 def alias_discard_all_x: Flag<["-"], "x">, Alias<discard_all>;
 def alias_discard_locals_X: Flag<["-"], "X">, Alias<discard_locals>;
+def alias_dynamic_list: Joined<["--", "-"], "dynamic-list=">, Alias<dynamic_list>;
 def alias_entry_e : JoinedOrSeparate<["-"], "e">, Alias<entry>;
 def alias_export_dynamic_E: Flag<["-"], "E">, Alias<export_dynamic>;
 def alias_fini_fini : Joined<["-"], "fini=">, Alias<fini>;

ELF/SymbolTable.h

                                    uint8_t Visibility = llvm::ELF::STV_HIDDEN);
 
   void scanShlibUndefined();
+  void scanDynamicList();
   SymbolBody *find(StringRef Name);
   void wrap(StringRef Name);
   InputFile *findFile(SymbolBody *B);

ELF/SymbolTable.cpp

           Sym->MustBeInDynSym = true;
 }
 
+// This function process the dynamic list option by marking all the symbols
+// to be exported in the dynamic table.
+template <class ELFT> void SymbolTable<ELFT>::scanDynamicList() {
+  for (StringRef S : Config->DynamicList)
+    if (SymbolBody *B = find(S))
+      B->MustBeInDynSym = true;
+}
+
 template class elf::SymbolTable<ELF32LE>;
 template class elf::SymbolTable<ELF32BE>;
 template class elf::SymbolTable<ELF64LE>;

test/ELF/dynamic-list.s

+## There is some bad quoting interaction between lit's internal shell, which is
+## implemented in Python, and the Cygwin implementations of the Unix utilities.
+## Avoid running these tests on Windows for now by requiring a real shell.
+
+# REQUIRES: shell
+
+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/shared.s -o %t2.o
+# RUN: ld.lld -shared %t2.o -soname shared -o %t2.so
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+## Check exporting only one symbol.
+# RUN: echo "{ foo1; };" > %t.list
+# RUN: ld.lld --dynamic-list %t.list %t %t2.so -o %t.exe
+# RUN: llvm-readobj -dyn-symbols %t.exe | FileCheck %s
+
+## And now using quoted strings (the output is the same since it does
+## use any wildcard character).
+# RUN: echo "{ \"foo1\"; };" > %t.list
+# RUN: ld.lld --dynamic-list %t.list %t %t2.so -o %t.exe
+# RUN: llvm-readobj -dyn-symbols %t.exe | FileCheck %s
+
+# CHECK:      DynamicSymbols [
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: @ (0)
+# CHECK-NEXT:     Value: 0x0
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Local
+# CHECK-NEXT:     Type: None
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: Undefined
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo1@ (1)
+# CHECK-NEXT:     Value: 0x11000
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Global (0x1)
+# CHECK-NEXT:     Type: None (0x0)
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: .text (0x4)
+# CHECK-NEXT:   }
+# CHECK-NEXT: ] 
+
+
+## Now export all the foo1, foo2, and foo31 symbols
+# RUN: echo "{ foo1; foo2; foo31; };" > %t.list
+# RUN: ld.lld --dynamic-list %t.list %t %t2.so -o %t.exe
+# RUN: llvm-readobj -dyn-symbols %t.exe | FileCheck -check-prefix=CHECK2 %s
+
+# CHECK2:      DynamicSymbols [
+# CHECK2-NEXT:   Symbol {
+# CHECK2-NEXT:     Name: @ (0)
+# CHECK2-NEXT:     Value: 0x0
+# CHECK2-NEXT:     Size: 0
+# CHECK2-NEXT:     Binding: Local
+# CHECK2-NEXT:     Type: None
+# CHECK2-NEXT:     Other: 0
+# CHECK2-NEXT:     Section: Undefined
+# CHECK2-NEXT:   }
+# CHECK2-NEXT:   Symbol {
+# CHECK2-NEXT:     Name: foo1@ (1)
+# CHECK2-NEXT:     Value: 0x11000
+# CHECK2-NEXT:     Size: 0
+# CHECK2-NEXT:     Binding: Global (0x1)
+# CHECK2-NEXT:     Type: None (0x0)
+# CHECK2-NEXT:     Other: 0
+# CHECK2-NEXT:     Section: .text (0x4)
+# CHECK2-NEXT:   }
+# CHECK2-NEXT:   Symbol {
+# CHECK2-NEXT:     Name: foo2@ (6)
+# CHECK2-NEXT:     Value: 0x11001
+# CHECK2-NEXT:     Size: 0
+# CHECK2-NEXT:     Binding: Global (0x1)
+# CHECK2-NEXT:     Type: None (0x0)
+# CHECK2-NEXT:     Other: 0
+# CHECK2-NEXT:     Section: .text (0x4)
+# CHECK2-NEXT:   }
+# CHECK2-NEXT:   Symbol {
+# CHECK2-NEXT:     Name: foo31@ (11)
+# CHECK2-NEXT:     Value: 0x11002
+# CHECK2-NEXT:     Size: 0
+# CHECK2-NEXT:     Binding: Global (0x1)
+# CHECK2-NEXT:     Type: None (0x0)
+# CHECK2-NEXT:     Other: 0
+# CHECK2-NEXT:     Section: .text (0x4)
+# CHECK2-NEXT:   }
+# CHECK2-NEXT: ] 
+
+.globl foo1
+foo1:
+  ret
+
+.globl foo2
+foo2:
+  ret
+
+.globl foo31
+foo31:
+  ret
+
+.globl _start
+_start:
+  retq

test/ELF/invalid-dynamic-list.test

+## Different "echo" commands on Windows interpret quoted strings and
+## wildcards in similar but different way (On Windows, ARGV tokenization
+## and wildcard expansion are not done by the shell but by each command.)
+## Because of that reason, this test fails on some Windows environment.
+## We can't write quoted strings that are interpreted the same way
+## by all echo commands. So, we don't want to run this on Windows.
+
+# REQUIRES: shell
+
+# RUN: mkdir -p %t.dir
+
+# RUN: echo foobar > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR1 %s
+# ERR1: line 1: { expected, but got foobar
+
+# RUN: echo "{ foobar;" > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR2 %s
+# ERR2: line 1: unexpected EOF
+
+## Missing ';' before '}'
+# RUN: echo "{ foobar }" > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR3 %s
+# ERR3: line 1: ; expected, but got }
+
+## Missing final ';'
+# RUN: echo "{ foobar; }" > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR4 %s
+# ERR4: line 1: unexpected EOF
+
+## Missing \" in foobar definition
+# RUN echo "{ \"foobar; };" > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR5 %s
+# ERR5: line 1: unexpected EOF
+
+# RUN: echo "{ extern \"BOGUS\" { test }; };" > %t1
+# RUN: not ld.lld --dynamic-list %t1 2>&1 | FileCheck -check-prefix=ERR6 %s
+# ERR6: line 1: ; expected, but got BOGUS