[ELF2] Implement --start-group,--end-group

[shankare]

Summary

This implements start-group and end-group functionality. Majority of applications on linux need this functionality.

[ruiu]

This is not how we handle archive files in the new LLD. --start-group and --end-group are already supported. You may need to read COFF/README.md, which is referenced by ELF/README.md, first to get the idea of the new linker's architecture.

[Bigcheese]

Specifically we do not implement the exact same semantics that ld does for performance reasons. If we ever find a compelling reason to implement those semantics we would add it as a separate mode. So far we have not seen a reason to do so.

[shankare]

Thanks Ruiu, Bigcheese. It would become confusing for the user when migrating from the GNU linker.

[shankare]

I am trying to say without --start-group and --end-group, the linker would have produced an unresolved symbol.

[ruiu]

What's the point of that?

[grimar]

test/elf2/Inputs/startendgroup/a.s

5

Filenames of inputs are very uninformative. Usually the same name as test name are used, eg:
shared.s
Inputs\shared.s
Inputs\shared2.s

test/elf2/startendgroup.s

19

As Rui already said, --start-group and --end-group are already supported.

Your test will PASS and without your code. Thats because lld currently already works in the way when it does not need --start-group and --end-group in command line to resolve it. These options are silently ignored, see Options.td.

[grimar]

In D14034#274322, @shankare wrote:

I am trying to say without --start-group and --end-group, the linker would have produced an unresolved symbol.

And if you wanted to simulate ld behavior to produce unresolved symbols when inputs not in start/end group then your test does seem to check that case.

[shankare]

How are symbols resolved when there are multiple --start-group and --end-group options currently ? Which symbol is picked when there is a unresolved symbol from the second group ?

If we want to follow --start-group/--end-group with the lld ELF linker, I think its best to follow GNU completely.

[ruiu]

You have to take a look at the actual code of the new linker and understand
its semantics/performance/simplicity before you claim that the best way is
something else.

[• rafael]

If we want to follow --start-group/--end-group with the lld ELF linker, I

think its best to follow GNU completely.

I am late to this thread, but I wanted to point out that "follow GNU
completely" is not how we want to implement *anything* in lld.

We want to start with the simpler/faster solution and make it more gnu like
only the first one is found to be insufficient for an existing real world
project and it would be cumbersome for them to change.

Cheers,
Rafael

[emaste]

I am late to this thread, but I wanted to point out that "follow GNU
completely" is not how we want to implement *anything* in lld.

Thank you. I believe there's a vanishingly small set of projects that rely on behaviour unique to GNU ld, can't be trivially updated to accommodate LLD, and can't just link with GNU ld instead, via -fuse-ld=bfd.

Our experience with Clang in FreeBSD is broadly illustrative - Clang is our /usr/bin/cc and the vast majority of the ~25K third-party ports build and work just fine despite minor differences compared with GCC. A few hundred do not, and have an explicit dependency on GCC. The same thing can easily be done when we bring in LLD as /usr/bin/ld.

[• espindola]

This is not relevant anymore.

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 "SymbolTable.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Option/ArgList.h"
+#include <set>
 
 namespace lld {
 namespace elf2 {
 
 extern class LinkerDriver *Driver;
 
 // Entry point of the ELF linker.
 void link(ArrayRef<const char *> Args);
 
 class LinkerDriver {
 public:
+  typedef std::vector<std::unique_ptr<Input>>::iterator InputVectorIterT;
+
   void main(ArrayRef<const char *> Args);
   void createFiles(llvm::opt::InputArgList &Args);
   template <class ELFT> void link(llvm::opt::InputArgList &Args);
 
   void addFile(StringRef Path);
 
-private:
-  template <template <class> class T>
-  std::unique_ptr<InputFile> createELFInputFile(MemoryBufferRef MB);
+  template <class ELFT>
+  InputVectorIterT handleGroup(SymbolTable<ELFT> &SymTab,
+                               InputVectorIterT Current);
 
+private:
   llvm::BumpPtrAllocator Alloc;
   bool WholeArchive = false;
-  std::vector<std::unique_ptr<InputFile>> Files;
-  std::vector<std::unique_ptr<ArchiveFile>> OwningArchives;
+  std::vector<std::unique_ptr<Input>> Files;
+  std::vector<std::unique_ptr<Input>> OwningArchives;
   std::vector<std::unique_ptr<MemoryBuffer>> OwningMBs;
 };
 
 // Parses command line options.
 llvm::opt::InputArgList parseArgs(llvm::BumpPtrAllocator *A,
                                   ArrayRef<const char *> Args);
 
 // Create enum with OPT_xxx values for each option in Options.td

ELF/Driver.cpp

for (auto *Arg : Args.filtered(OPT_z)) {
     if (S == "nodelete")
       Config->ZNodelete = true;
     else if (S == "now")
       Config->ZNow = true;
     else if (S == "origin")
       Config->ZOrigin = true;
   }
 
+  int groupUnMatchedCount = 0;
   for (auto *Arg : Args) {
     switch (Arg->getOption().getID()) {
     case OPT_l:
       addFile(searchLibrary(Arg->getValue()));
       break;
+    case OPT_start_group:
+      ++groupUnMatchedCount;
+      Files.push_back(std::unique_ptr<Input>(new Input(Input::StartGroup)));
+      break;
+    case OPT_end_group:
+      --groupUnMatchedCount;
+      Files.push_back(std::unique_ptr<Input>(new Input(Input::EndGroup)));
+      break;
     case OPT_INPUT:
     case OPT_script:
       addFile(Arg->getValue());
       break;
     case OPT_as_needed:
       Config->AsNeeded = true;
       break;
     case OPT_no_as_needed:
case OPT_whole_archive:
       WholeArchive = true;
       break;
     case OPT_no_whole_archive:
       WholeArchive = false;
       break;
     }
   }
 
+  if (groupUnMatchedCount)
+    error("unmatched --start/--end group");
+
   if (Files.empty())
     error("no input files.");
 }
 
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   SymbolTable<ELFT> Symtab;
   Target.reset(createTarget());
 
if (!Config->Shared) {
     // The situation is even stranger on x86_64 where the assembly doesn't
     // need the magical symbol, but gas still puts _GLOBAL_OFFSET_TABLE_ as
     // an undefined symbol in the .o files.
     // Given that the symbol is effectively unused, we just create a dummy
     // hidden one to avoid the undefined symbol error.
     Symtab.addIgnoredSym("_GLOBAL_OFFSET_TABLE_");
   }
 
-  for (std::unique_ptr<InputFile> &F : Files)
-    Symtab.addFile(std::move(F));
+  InputVectorIterT Start = Files.begin(), End = Files.end();
+  while (Start != End) {
+    InputVectorIterT Current = Start;
+    // Handle Groups if the linker finds a --start-group input.
+    if ((*Current)->type() == Input::StartGroup)
+      Start = handleGroup(Symtab, Current);
+    else if ((dyn_cast<InputFile>(Current->get()))->kind() ==
+             InputFile::ArchiveKind)
+      Symtab.addArchiveFile(Current->get());
+    else
+      Symtab.addFile(std::move(*Current));
+    ++Start;
+  }
 
   for (StringRef S : Config->Undefined)
     Symtab.addUndefinedOpt(S);
 
   if (Config->OutputFile.empty())
     Config->OutputFile = "a.out";
 
   // Write the result to the file.
   Symtab.scanShlibUndefined();
   if (Config->GcSections)
     markLive<ELFT>(&Symtab);
   writeResult<ELFT>(&Symtab);
 }
+
+template <class ELFT>
+LinkerDriver::InputVectorIterT
+LinkerDriver::handleGroup(SymbolTable<ELFT> &Symtab, InputVectorIterT Current) {
+  InputVectorIterT GroupStart = Current;
+  bool AddNewFiles = false;
+  do {
+    // Initialize AddNewFiles for every iteration.
+    AddNewFiles = false;
+    Current = GroupStart;
+    while (true) {
+      ++Current;
+      if (!(*Current))
+        continue;
+      if ((*Current)->type() == Input::EndGroup)
+        break;
+      Input::Type InputType = (*Current)->type();
+      Input *currentInput = Current->get();
+      switch (InputType) {
+      // Handle group inside another group. This is not usually seen but its not
+      // a lot of code to handle it.
+      case Input::StartGroup:
+        Current = handleGroup(Symtab, Current);
+        break;
+      case Input::EndGroup:
+        break;
+      case Input::File: {
+        InputFile *inputFile = dyn_cast<InputFile>(currentInput);
+        if (inputFile->kind() == InputFile::ArchiveKind)
+          // Archive files are needed to be looked up multiple times inside a
+          // Group. Dont transfer ownership.
+          AddNewFiles |= Symtab.addArchiveFile(currentInput);
+        else
+          AddNewFiles |= Symtab.addFile(std::move(*Current));
+        break;
+      }
+      } // End Case(Type)
+    }
+  } while (AddNewFiles);
+  return Current;
+}

ELF/InputFiles.h

 namespace elf2 {
 
 using llvm::object::Archive;
 
 class InputFile;
 class Lazy;
 class SymbolBody;
 
+class Input {
+public:
+  enum Type { File, StartGroup, EndGroup };
+  Input(Type T) : InputType(T) {}
+  Type type() const { return InputType; }
+
+private:
+  const Type InputType;
+};
+
 // The root class of input files.
-class InputFile {
+class InputFile : public Input {
 public:
   enum Kind { ObjectKind, SharedKind, ArchiveKind };
   Kind kind() const { return FileKind; }
 
   StringRef getName() const { return MB.getBufferIdentifier(); }
 
+  static bool classof(const Input *F) { return true; }
+
 protected:
-  InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {}
+  InputFile(Kind K, MemoryBufferRef M)
+      : Input(Input::File), MB(M), FileKind(K) {}
   MemoryBufferRef MB;
 
 private:
   const Kind FileKind;
 };
 
 template <typename ELFT> class ELFFileBase : public InputFile {
 public:

ELF/SymbolTable.h

 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in resolve().
 template <class ELFT> class SymbolTable {
 public:
   SymbolTable();
 
-  void addFile(std::unique_ptr<InputFile> File);
+  bool addFile(std::unique_ptr<Input> I);
+
+  // Add archive file without transferring ownership.
+  bool addArchiveFile(Input *I);
 
   bool shouldUseRela() const;
 
   const llvm::MapVector<StringRef, Symbol *> &getSymbols() const {
     return Symtab;
   }
 
   const std::vector<std::unique_ptr<ObjectFile<ELFT>>> &getObjectFiles() const {
public:
   void addIgnoredSym(StringRef Name);
   bool isUndefined(StringRef Name);
   void scanShlibUndefined();
   SymbolBody *find(StringRef Name);
 
 private:
   Symbol *insert(SymbolBody *New);
   void addELFFile(ELFFileBase<ELFT> *File);
-  void addLazy(Lazy *New);
+  bool addLazy(Lazy *New);
   void addMemberFile(Lazy *Body);
-  void checkCompatibility(std::unique_ptr<InputFile> &File);
+  void checkCompatibility(InputFile *File);
   void resolve(SymbolBody *Body);
   void reportConflict(const Twine &Message, const SymbolBody &Old,
                       const SymbolBody &New, bool Warning);
 
-  std::vector<std::unique_ptr<InputFile>> ArchiveFiles;
-
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we use a MapVector. That is arbitrary, deterministic but
   // a bit inefficient.
   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
   // once symbol resolution is finished.
   llvm::MapVector<StringRef, Symbol *> Symtab;

ELF/SymbolTable.cpp

 template <class ELFT> SymbolTable<ELFT>::SymbolTable() {}
 
 template <class ELFT> bool SymbolTable<ELFT>::shouldUseRela() const {
   ELFKind K = cast<ELFFileBase<ELFT>>(Config->FirstElf)->getELFKind();
   return K == ELF64LEKind || K == ELF64BEKind;
 }
 
 template <class ELFT>
-void SymbolTable<ELFT>::addFile(std::unique_ptr<InputFile> File) {
-  checkCompatibility(File);
+bool SymbolTable<ELFT>::addFile(std::unique_ptr<Input> I) {
+  bool AddNewMember = false;
+  InputFile *File = dyn_cast<InputFile>(I.get());
 
-  if (auto *AF = dyn_cast<ArchiveFile>(File.get())) {
-    ArchiveFiles.emplace_back(std::move(File));
-    AF->parse();
-    for (Lazy &Sym : AF->getLazySymbols())
-      addLazy(&Sym);
-    return;
-  }
+  checkCompatibility(File);
 
-  if (auto *S = dyn_cast<SharedFile<ELFT>>(File.get())) {
+  if (auto *S = dyn_cast<SharedFile<ELFT>>(File)) {
     S->parseSoName();
     if (!IncludedSoNames.insert(S->getSoName()).second)
-      return;
+      return AddNewMember;
     S->parse();
   } else {
-    cast<ObjectFile<ELFT>>(File.get())->parse(Comdats);
+    cast<ObjectFile<ELFT>>(File)->parse(Comdats);
+  }
+  addELFFile(cast<ELFFileBase<ELFT>>(dyn_cast<InputFile>(I.release())));
+  return true;
+}
+
+template <class ELFT> bool SymbolTable<ELFT>::addArchiveFile(Input *I) {
+  bool AddNewMember = false;
+  InputFile *File = dyn_cast<InputFile>(I);
+
+  checkCompatibility(File);
+
+  if (auto *AF = dyn_cast<ArchiveFile>(File)) {
+    AF->parse();
+    for (Lazy &Sym : AF->getLazySymbols())
+      AddNewMember |= addLazy(&Sym);
   }
-  addELFFile(cast<ELFFileBase<ELFT>>(File.release()));
+  return AddNewMember;
 }
 
 template <class ELFT>
 SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
   auto *Sym = new (Alloc) Undefined<ELFT>(Name, Undefined<ELFT>::Required);
   resolve(Sym);
   return Sym;
 }

 
 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
   auto It = Symtab.find(Name);
   if (It == Symtab.end())
     return nullptr;
   return It->second->Body;
 }
 
-template <class ELFT> void SymbolTable<ELFT>::addLazy(Lazy *New) {
+template <class ELFT> bool SymbolTable<ELFT>::addLazy(Lazy *New) {
   Symbol *Sym = insert(New);
   if (Sym->Body == New)
-    return;
+    return false;
   SymbolBody *Existing = Sym->Body;
   if (Existing->isDefined() || Existing->isLazy())
-    return;
+    return false;
   Sym->Body = New;
   assert(Existing->isUndefined() && "Unexpected symbol kind.");
 
   // Weak undefined symbols should not fetch members from archives.
   // If we were to keep old symbol we would not know that an archive member was
   // available if a strong undefined symbol shows up afterwards in the link.
   // If a strong undefined symbol never shows up, this lazy symbol will
   // get to the end of the link and must be treated as the weak undefined one.
   // We set UsedInRegularObj in a similar way to what is done with shared
   // symbols and mark it as weak to reduce how many special cases are needed.
   if (Existing->isWeak()) {
     New->setUsedInRegularObj();
     New->setWeak();
-    return;
+    return false;
   }
   addMemberFile(New);
+  return true;
 }
 
 template <class ELFT>
-void SymbolTable<ELFT>::checkCompatibility(std::unique_ptr<InputFile> &File) {
-  auto *E = dyn_cast<ELFFileBase<ELFT>>(File.get());
+void SymbolTable<ELFT>::checkCompatibility(InputFile *File) {
+  auto *E = dyn_cast<ELFFileBase<ELFT>>(File);
   if (!E)
     return;
   if (E->getELFKind() == Config->EKind && E->getEMachine() == Config->EMachine)
     return;
   StringRef A = E->getName();
   StringRef B = Config->Emulation;
   if (B.empty())
     B = Config->FirstElf->getName();

ELF/Target.cpp

public:
   void writePltEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
                    uint64_t SA) const override;
 };
 
-template <class ELFT> class HexagonTargetInfo final : public TargetInfo {
-public:
-  HexagonTargetInfo();
-  void writePltEntry(uint8_t *Buf, uint64_t GotEntryAddr,
-                     uint64_t PltEntryAddr) const override;
-  bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
-  bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
-  void relocateOne(uint8_t *Buf, uint8_t *BufEnd, const void *RelP,
-                   uint32_t Type, uint64_t BaseAddr,
-                   uint64_t SA) const override;
-};
 } // anonymous namespace
 
 TargetInfo *createTarget() {
   switch (Config->EMachine) {
   case EM_386:
     return new X86TargetInfo();
   case EM_AARCH64:
     return new AArch64TargetInfo();

test/elf2/Inputs/startendgroup/a.s

+  .text
+  .globl  main
+  .type main,@function
+main:
+  jmp bar

test/elf2/Inputs/startendgroup/b1.s

+  .text
+  .weak bar
+  .type bar,@function
+bar:
+  jmp baz

test/elf2/Inputs/startendgroup/b11.s

+  .text
+  .globl  moo
+  .type moo,@function
+moo:
+  retq

test/elf2/Inputs/startendgroup/b2.s

+  .text
+  .weak boo
+  .type boo,@function
+boo:
+  callq moo

test/elf2/Inputs/startendgroup/c.s

+  .text
+  .weak baz
+  .type baz,@function
+baz:
+  jmp boo

test/elf2/startendgroup.s

+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/startendgroup/a.s -o %t1.a.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/startendgroup/c.s -o %t1.c.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/startendgroup/b1.s -o %t1.b1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/startendgroup/b2.s -o %t1.b2.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/startendgroup/b11.s -o %t1.b11.o
+# RUN: llvm-ar rcs %t1.libb1.a %t1.b1.o %t1.b11.o
+# RUN: llvm-ar rcs %t1.libb2.a %t1.b2.o
+# RUN: llvm-ar rcs %t1.libc.a %t1.c.o
+# RUN: ld.lld2 --noinhibit-exec %t1.a.o --start-group %t1.libb1.a %t1.libb2.a %t1.libc.a --end-group -o %toutsimple
+# RUN: llvm-nm -n %toutsimple | FileCheck %s
+# RUN: ld.lld2 --noinhibit-exec %t1.a.o --start-group %t1.libb1.a --start-group %t1.libb2.a --end-group %t1.libc.a --end-group -o %tout
+# RUN: llvm-nm -n %tout | FileCheck %s
+# REQUIRES: x86
+
+#CHECK: main
+#CHECK: bar
+#CHECK: baz
+#CHECK: boo
+#CHECK: moo