Split Undefined and UndefinedElf

[• rafael]

Summary

I am working on adding LTO support to the new ELF lld.

In order to do that, it will be necessary to represent defined and undefined symbols that are not from ELF files. One way to do it is to change the symbol hierarchy to look like

Defined : SymbolBody
Undefined : SymbolBody

DefinedElf<ELFT> : Defined
UndefinedElf<ELFT> : Undefined

Another option would be to use bogus Elf_Sym, but I think that is getting a bit too hackish.

The attached patch does the Undefined/UndefinedElf. Split. The next one will do the Defined/DefinedElf split.

[davide]

The conversion seems pretty mechanical and it doesn't seem to complicate the code -- I think I like the idea better than using bogus Elf_Sym. Couple of nits. Thanks!

ELF/OutputSections.cpp

812

Unsorted.

ELF/Symbols.h

67

Ditto.

[• rafael]

Sort entries.

[ruiu]

LGTM with a few nits. Nice change.

ELF/OutputSections.cpp

1335

Why const auto instead of auto? (It's not wrong but looks like excessive.)

ELF/SymbolTable.h

21

Sort.

ELF/Symbols.cpp

82

Pass CanKeepUndefined instead of false.

124

You can write

template class lld::elf2::UndefinedElf<ELF...>;

ELF/Symbols.h

133–136

Thank you for removing this FIXME.

[grimar]

LGTM with a few nits.

ELF/OutputSections.cpp

1333

I am not sure if this place is clang formatted (looks like not).

ELF/Symbols.cpp

82

This false is about IsTls I think.
Thats the problem of these constructors - them are very similiar, but isTls/CanKeepUndefined differs what confuses. May be it is worth to keep both flags here ? One more excess argument is not good either though.

[davide]

Forgot to mark this as accepted yesterday FWIW.

ELF/InputFiles.cpp

SymbolBody *elf2::ObjectFile<ELFT>::createSymbolBody(StringRef StringTable,
   ErrorOr<StringRef> NameOrErr = Sym->getName(StringTable);
   error(NameOrErr.getError());
   StringRef Name = *NameOrErr;
 
   switch (Sym->st_shndx) {
   case SHN_ABS:
     return new (this->Alloc) DefinedAbsolute<ELFT>(Name, *Sym);
   case SHN_UNDEF:
-    return new (this->Alloc) Undefined<ELFT>(Name, *Sym);
+    return new (this->Alloc) UndefinedElf<ELFT>(Name, *Sym);
   case SHN_COMMON:
     return new (this->Alloc) DefinedCommon<ELFT>(Name, *Sym);
   }
 
   switch (Sym->getBinding()) {
   default:
     error("unexpected binding");
   case STB_GLOBAL:
   case STB_WEAK:
   case STB_GNU_UNIQUE: {
     InputSectionBase<ELFT> *Sec = getSection(*Sym);
     if (Sec == &InputSection<ELFT>::Discarded)
-      return new (this->Alloc) Undefined<ELFT>(Name, *Sym);
+      return new (this->Alloc) UndefinedElf<ELFT>(Name, *Sym);
     return new (this->Alloc) DefinedRegular<ELFT>(Name, *Sym, *Sec);
   }
   }
 }
 
 static std::unique_ptr<Archive> openArchive(MemoryBufferRef MB) {
   ErrorOr<std::unique_ptr<Archive>> ArchiveOrErr = Archive::create(MB);
   error(ArchiveOrErr, "Failed to parse archive");

ELF/OutputSections.h

 template <class ELFT> class EHInputSection;
 template <class ELFT> class InputSection;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class MergeInputSection;
 template <class ELFT> class MipsReginfoInputSection;
 template <class ELFT> class OutputSection;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class DefinedRegular;
-template <class ELFT> class ELFSymbolBody;
 
 // Flag to force GOT to be in output if we have relocations
 // that relies on its address.
 extern bool HasGotOffRel;
 
 template <class ELFT>
 static inline typename llvm::object::ELFFile<ELFT>::uintX_t
 getAddend(const typename llvm::object::ELFFile<ELFT>::Elf_Rel &Rel) {

ELF/OutputSections.cpp

typename ELFFile<ELFT>::uintX_t lld::elf2::getSymVA(const SymbolBody &S) {
   case SymbolBody::DefinedCommonKind:
     return Out<ELFT>::Bss->getVA() + cast<DefinedCommon<ELFT>>(S).OffsetInBSS;
   case SymbolBody::SharedKind: {
     auto &SS = cast<SharedSymbol<ELFT>>(S);
     if (SS.NeedsCopy)
       return Out<ELFT>::Bss->getVA() + SS.OffsetInBSS;
     return 0;
   }
+  case SymbolBody::UndefinedElfKind:
   case SymbolBody::UndefinedKind:
     return 0;
   case SymbolBody::LazyKind:
     assert(S.isUsedInRegularObj() && "Lazy symbol reached writer");
     return 0;
   }
   llvm_unreachable("Invalid symbol kind");
 }
 
 // Returns a VA which a relocatin RI refers to. Used only for local symbols.
for (const Elf_Sym &Sym : Syms) {
       ESym->setBindingAndType(Sym.getBinding(), Sym.getType());
       ESym->st_value = VA;
       Buf += sizeof(*ESym);
     }
   }
 }
 
 template <class ELFT>
+static const typename llvm::object::ELFFile<ELFT>::Elf_Sym *
+getElfSym(SymbolBody &Body) {
+  if (const auto *EBody = dyn_cast<Defined<ELFT>>(&Body))
+    return &EBody->Sym;
+  if (const auto *EBody = dyn_cast<UndefinedElf<ELFT>>(&Body))
+    return &EBody->Sym;
+  return nullptr;
+}
+
+template <class ELFT>
 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
   // Write the internal symbol table contents to the output symbol table
   // pointed by Buf.
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
   for (SymbolBody *Body : Symbols) {
     const OutputSectionBase<ELFT> *OutSec = nullptr;
 
     switch (Body->kind()) {
for (SymbolBody *Body : Symbols) {
     case SymbolBody::DefinedCommonKind:
       OutSec = Out<ELFT>::Bss;
       break;
     case SymbolBody::SharedKind: {
       if (cast<SharedSymbol<ELFT>>(Body)->NeedsCopy)
         OutSec = Out<ELFT>::Bss;
       break;
     }
+    case SymbolBody::UndefinedElfKind:
     case SymbolBody::UndefinedKind:
     case SymbolBody::DefinedAbsoluteKind:
     case SymbolBody::LazyKind:
       break;
     }
 
     StringRef Name = Body->getName();
     ESym->st_name = StrTabSec.getOffset(Name);
 
     unsigned char Type = STT_NOTYPE;
     uintX_t Size = 0;
-    if (const auto *EBody = dyn_cast<ELFSymbolBody<ELFT>>(Body)) {
-      const Elf_Sym &InputSym = EBody->Sym;
-      Type = InputSym.getType();
-      Size = InputSym.st_size;
+    if (const Elf_Sym *InputSym = getElfSym<ELFT>(*Body)) {
+      Type = InputSym->getType();
+      Size = InputSym->st_size;
     }
 
     ESym->setBindingAndType(getSymbolBinding(Body), Type);
     ESym->st_size = Size;
     ESym->setVisibility(Body->getVisibility());
     ESym->st_value = getSymVA<ELFT>(*Body);
 
     if (isa<DefinedAbsolute<ELFT>>(Body))
       ESym->st_shndx = SHN_ABS;
     else if (OutSec)
       ESym->st_shndx = OutSec->SectionIndex;
 
     ++ESym;
   }
 }
 
 template <class ELFT>
 uint8_t SymbolTableSection<ELFT>::getSymbolBinding(SymbolBody *Body) {
   uint8_t Visibility = Body->getVisibility();
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return STB_LOCAL;
-  if (const auto *EBody = dyn_cast<ELFSymbolBody<ELFT>>(Body))
-    return EBody->Sym.getBinding();
+  if (const Elf_Sym *ESym = getElfSym<ELFT>(*Body))
+    return ESym->getBinding();
   return Body->isWeak() ? STB_WEAK : STB_GLOBAL;
 }
 
 template <class ELFT>
 MipsReginfoOutputSection<ELFT>::MipsReginfoOutputSection()
     : OutputSectionBase<ELFT>(".reginfo", SHT_MIPS_REGINFO, SHF_ALLOC) {
   this->Header.sh_addralign = 4;
   this->Header.sh_entsize = sizeof(Elf_Mips_RegInfo);

ELF/SymbolTable.h

 #include "InputFiles.h"
 #include "llvm/ADT/MapVector.h"
 
 namespace lld {
 namespace elf2 {
 class Lazy;
 struct Symbol;
 template <class ELFT> class OutputSectionBase;
-template <class ELFT> class Undefined;
+class Undefined;
 
 // SymbolTable is a bucket of all known symbols, including defined,
 // undefined, or lazy symbols (the last one is symbols in archive
 // files whose archive members are not yet loaded).
 //
 // We put all symbols of all files to a SymbolTable, and the
 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
public:
   SymbolBody *addIgnored(StringRef Name);
   bool isUndefined(StringRef Name);
   void scanShlibUndefined();
   SymbolBody *find(StringRef Name);
 
 private:
   Symbol *insert(SymbolBody *New);
   void addLazy(Lazy *New);
-  void addMemberFile(Undefined<ELFT> *Undef, Lazy *L);
+  void addMemberFile(Undefined *Undef, Lazy *L);
   void resolve(SymbolBody *Body);
   std::string conflictMsg(SymbolBody *Old, SymbolBody *New);
 
   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

ELF/SymbolTable.cpp

void SymbolTable<ELFT>::addFile(std::unique_ptr<InputFile> File) {
   ObjectFiles.emplace_back(F);
   F->parse(Comdats);
   for (SymbolBody *B : F->getSymbols())
     resolve(B);
 }
 
 template <class ELFT>
 SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
-  auto *Sym = new (Alloc) Undefined<ELFT>(Name, Undefined<ELFT>::Required);
+  auto *Sym = new (Alloc) Undefined(Name, false, STV_DEFAULT, false);
   resolve(Sym);
   return Sym;
 }
 
 template <class ELFT>
 SymbolBody *SymbolTable<ELFT>::addUndefinedOpt(StringRef Name) {
-  auto *Sym = new (Alloc) Undefined<ELFT>(Name, Undefined<ELFT>::Optional);
+  auto *Sym = new (Alloc) Undefined(Name, false, STV_HIDDEN, true);
   resolve(Sym);
   return Sym;
 }
 
 template <class ELFT>
 void SymbolTable<ELFT>::addAbsolute(StringRef Name,
                                     typename ELFFile<ELFT>::Elf_Sym &ESym) {
   resolve(new (Alloc) DefinedAbsolute<ELFT>(Name, ESym));

 }
 
 // Returns a file from which symbol B was created.
 // If B does not belong to any file in ObjectFiles, returns a nullptr.
 template <class ELFT>
 ELFFileBase<ELFT> *
 elf2::findFile(ArrayRef<std::unique_ptr<ObjectFile<ELFT>>> ObjectFiles,
                const SymbolBody *B) {
-  typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
-  typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
-
-  const Elf_Sym *Sym = &cast<ELFSymbolBody<ELFT>>(*B).Sym;
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : ObjectFiles) {
-    Elf_Sym_Range R = F->getObj().symbols(F->getSymbolTable());
-    if (R.begin() <= Sym && Sym < R.end())
+    ArrayRef<SymbolBody *> Syms = F->getSymbols();
+    if (std::find(Syms.begin(), Syms.end(), B) != Syms.end())
       return F.get();
   }
   return nullptr;
 }
 
 template <class ELFT>
 std::string SymbolTable<ELFT>::conflictMsg(SymbolBody *Old, SymbolBody *New) {
   ELFFileBase<ELFT> *OldFile = findFile<ELFT>(ObjectFiles, Old);

 template <class ELFT> void SymbolTable<ELFT>::resolve(SymbolBody *New) {
   Symbol *Sym = insert(New);
   if (Sym->Body == New)
     return;
 
   SymbolBody *Existing = Sym->Body;
 
   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
-    if (auto *Undef = dyn_cast<Undefined<ELFT>>(New)) {
+    if (auto *Undef = dyn_cast<Undefined>(New)) {
       addMemberFile(Undef, L);
       return;
     }
     // Found a definition for something also in an archive.
     // Ignore the archive definition.
     Sym->Body = New;
     return;
   }
if (It == Symtab.end())
     return nullptr;
   return It->second->Body;
 }
 
 template <class ELFT> void SymbolTable<ELFT>::addLazy(Lazy *L) {
   Symbol *Sym = insert(L);
   if (Sym->Body == L)
     return;
-  if (auto *Undef = dyn_cast<Undefined<ELFT>>(Sym->Body)) {
+  if (auto *Undef = dyn_cast<Undefined>(Sym->Body)) {
     Sym->Body = L;
     addMemberFile(Undef, L);
   }
 }
 
 template <class ELFT>
-void SymbolTable<ELFT>::addMemberFile(Undefined<ELFT> *Undef, Lazy *L) {
+void SymbolTable<ELFT>::addMemberFile(Undefined *Undef, Lazy *L) {
   // 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 (Undef->isWeak()) {

ELF/Symbols.h

public:
   enum Kind {
     DefinedFirst,
     DefinedRegularKind = DefinedFirst,
     DefinedAbsoluteKind,
     DefinedCommonKind,
     DefinedSyntheticKind,
     SharedKind,
     DefinedLast = SharedKind,
+    UndefinedElfKind,
     UndefinedKind,
     LazyKind
   };
 
   Kind kind() const { return static_cast<Kind>(SymbolKind); }
 
   bool isWeak() const { return IsWeak; }
-  bool isUndefined() const { return SymbolKind == UndefinedKind; }
+  bool isUndefined() const {
+    return SymbolKind == UndefinedKind || SymbolKind == UndefinedElfKind;
+  }
   bool isDefined() const { return SymbolKind <= DefinedLast; }
   bool isCommon() const { return SymbolKind == DefinedCommonKind; }
   bool isLazy() const { return SymbolKind == LazyKind; }
   bool isShared() const { return SymbolKind == SharedKind; }
   bool isUsedInRegularObj() const { return IsUsedInRegularObj; }
   bool isUsedInDynamicReloc() const { return IsUsedInDynamicReloc; }
   void setUsedInDynamicReloc() { IsUsedInDynamicReloc = true; }
   bool isTls() const { return IsTls; }
protected:
   unsigned Visibility : 2;
   unsigned IsUsedInRegularObj : 1;
   unsigned IsUsedInDynamicReloc : 1;
   unsigned IsTls : 1;
   StringRef Name;
   Symbol *Backref = nullptr;
 };
 
-// This is for symbols created from elf files and not from the command line.
-// Since they come from object files, they have a Elf_Sym.
-//
-// FIXME: Another alternative is to give every symbol an Elf_Sym. To do that
-// we have to delay creating the symbol table until the output format is
-// known and some of its methods will be templated. We should experiment with
-// that once we have a bit more code.
-template <class ELFT> class ELFSymbolBody : public SymbolBody {
-protected:
-  typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
-  ELFSymbolBody(Kind K, StringRef Name, const Elf_Sym &Sym)
-      : SymbolBody(K, Name, Sym.getBinding() == llvm::ELF::STB_WEAK,
-                   Sym.getVisibility(), Sym.getType() == llvm::ELF::STT_TLS),
-        Sym(Sym) {}
-
-public:
-  const Elf_Sym &Sym;
-
-  static bool classof(const SymbolBody *S) {
-    Kind K = S->kind();
-    return K >= DefinedFirst && K <= UndefinedKind;
-  }
-};
-
 // The base class for any defined symbols, including absolute symbols, etc.
-template <class ELFT> class Defined : public ELFSymbolBody<ELFT> {
+template <class ELFT> class Defined : public SymbolBody {
 protected:
-  typedef typename SymbolBody::Kind Kind;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
 
 public:
   Defined(Kind K, StringRef N, const Elf_Sym &Sym)
-      : ELFSymbolBody<ELFT>(K, N, Sym) {}
+      : SymbolBody(K, N, Sym.getBinding() == llvm::ELF::STB_WEAK,
+                   Sym.getVisibility(), Sym.getType() == llvm::ELF::STT_TLS),
+        Sym(Sym) {}
 
+  const Elf_Sym &Sym;
   static bool classof(const SymbolBody *S) { return S->isDefined(); }
 };
 
 template <class ELFT> class DefinedAbsolute : public Defined<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
 
 public:
   static Elf_Sym IgnoreUndef;
public:
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedSyntheticKind;
   }
 
   const OutputSectionBase<ELFT> &Section;
 };
 
 // Undefined symbol.
-template <class ELFT> class Undefined : public ELFSymbolBody<ELFT> {
-  typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
+class Undefined : public SymbolBody {
+  typedef SymbolBody::Kind Kind;
+  bool CanKeepUndefined;
 
-public:
-  static Elf_Sym Required;
-  static Elf_Sym Optional;
+protected:
+  Undefined(Kind K, StringRef N, bool IsWeak, uint8_t Visibility, bool IsTls);
 
-  Undefined(StringRef N, const Elf_Sym &Sym)
-      : ELFSymbolBody<ELFT>(SymbolBody::UndefinedKind, N, Sym) {}
+public:
+  Undefined(StringRef N, bool IsWeak, uint8_t Visibility,
+            bool CanKeepUndefined);
 
-  static bool classof(const SymbolBody *S) {
-    return S->kind() == SymbolBody::UndefinedKind;
-  }
+  static bool classof(const SymbolBody *S) { return S->isUndefined(); }
 
-  bool canKeepUndefined() const { return &this->Sym == &Optional; }
+  bool canKeepUndefined() const { return CanKeepUndefined; }
 };
 
-template <class ELFT>
-typename Undefined<ELFT>::Elf_Sym Undefined<ELFT>::Required;
-template <class ELFT>
-typename Undefined<ELFT>::Elf_Sym Undefined<ELFT>::Optional;
+template <class ELFT> class UndefinedElf : public Undefined {
+  typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
+
+public:
+  UndefinedElf(StringRef N, const Elf_Sym &Sym);
+  const Elf_Sym &Sym;
+};
 
 template <class ELFT> class SharedSymbol : public Defined<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::SharedKind;

ELF/Symbols.cpp

if (isCommon()) {
     OtherC->MaxAlignment = Align;
     return -1;
   }
   if (Other->isCommon())
     return 1;
   return 0;
 }
 
+Undefined::Undefined(SymbolBody::Kind K, StringRef N, bool IsWeak,
+                     uint8_t Visibility, bool IsTls)
+    : SymbolBody(K, N, IsWeak, Visibility, IsTls), CanKeepUndefined(false) {}
+
+Undefined::Undefined(StringRef N, bool IsWeak, uint8_t Visibility,
+                     bool CanKeepUndefined)
+    : Undefined(SymbolBody::UndefinedKind, N, IsWeak, Visibility, false) {
+  this->CanKeepUndefined = CanKeepUndefined;
+}
+
+template <typename ELFT>
+UndefinedElf<ELFT>::UndefinedElf(StringRef N, const Elf_Sym &Sym)
+    : Undefined(SymbolBody::UndefinedElfKind, N,
+                Sym.getBinding() == llvm::ELF::STB_WEAK, Sym.getVisibility(),
+                Sym.getType() == llvm::ELF::STT_TLS),
+      Sym(Sym) {}
+
 std::unique_ptr<InputFile> Lazy::getMember() {
   MemoryBufferRef MBRef = File->getMember(&Sym);
 
   // getMember returns an empty buffer if the member was already
   // read from the library.
   if (MBRef.getBuffer().empty())
     return std::unique_ptr<InputFile>(nullptr);
 
   return createELFFile<ObjectFile>(MBRef);
 }
 
 template <class ELFT> static void doInitSymbols() {
   DefinedAbsolute<ELFT>::End.setBinding(STB_GLOBAL);
   DefinedAbsolute<ELFT>::IgnoreUndef.setBinding(STB_WEAK);
   DefinedAbsolute<ELFT>::IgnoreUndef.setVisibility(STV_HIDDEN);
-  Undefined<ELFT>::Optional.setVisibility(STV_HIDDEN);
 }
 
 void lld::elf2::initSymbols() {
   doInitSymbols<ELF32LE>();
   doInitSymbols<ELF32BE>();
   doInitSymbols<ELF64LE>();
   doInitSymbols<ELF64BE>();
 }
 
 template int SymbolBody::compare<ELF32LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF32BE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64BE>(SymbolBody *Other);
+
+namespace lld {
+namespace elf2 {
+template class UndefinedElf<ELF32LE>;
+template class UndefinedElf<ELF32BE>;
+template class UndefinedElf<ELF64LE>;
+template class UndefinedElf<ELF64BE>;
+}
+}

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::createSections() {
   }
 
   addIRelocMarkers<ELFT>(Symtab, isOutputDynamic());
 
   std::vector<DefinedCommon<ELFT> *> CommonSymbols;
   std::vector<SharedSymbol<ELFT> *> SharedCopySymbols;
   for (auto &P : Symtab.getSymbols()) {
     SymbolBody *Body = P.second->Body;
-    if (auto *U = dyn_cast<Undefined<ELFT>>(Body))
+    if (auto *U = dyn_cast<Undefined>(Body))
       if (!U->isWeak() && !U->canKeepUndefined())
         reportUndefined<ELFT>(Symtab, *Body);
 
     if (auto *C = dyn_cast<DefinedCommon<ELFT>>(Body))
       CommonSymbols.push_back(C);
     if (auto *SC = dyn_cast<SharedSymbol<ELFT>>(Body))
       if (SC->NeedsCopy)
         SharedCopySymbols.push_back(SC);