contrib/llvm/tools/lld/ELF/SymbolTable.h

   1 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLD_ELF_SYMBOL_TABLE_H
  11 #define LLD_ELF_SYMBOL_TABLE_H
  12
  13 #include "InputFiles.h"
  14 #include "LTO.h"
  15 #include "Strings.h"
  16 #include "llvm/ADT/CachedHashString.h"
  17 #include "llvm/ADT/DenseMap.h"
  18
  19 namespace lld {
  20 namespace elf {
  21 class Lazy;
  22 struct Symbol;
  23
  24 // SymbolTable is a bucket of all known symbols, including defined,
  25 // undefined, or lazy symbols (the last one is symbols in archive
  26 // files whose archive members are not yet loaded).
  27 //
  28 // We put all symbols of all files to a SymbolTable, and the
  29 // SymbolTable selects the "best" symbols if there are name
  30 // conflicts. For example, obviously, a defined symbol is better than
  31 // an undefined symbol. Or, if there's a conflict between a lazy and a
  32 // undefined, it'll read an archive member to read a real definition
  33 // to replace the lazy symbol. The logic is implemented in the
  34 // add*() functions, which are called by input files as they are parsed. There
  35 // is one add* function per symbol type.
  36 template <class ELFT> class SymbolTable {
  37   typedef typename ELFT::Sym Elf_Sym;
  38
  39 public:
  40   void addFile(InputFile *File);
  41   void addCombinedLTOObject();
  42   void addSymbolAlias(StringRef Alias, StringRef Name);
  43   void addSymbolWrap(StringRef Name);
  44   void applySymbolRenames();
  45
  46   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
  47   ArrayRef<ObjectFile<ELFT> *> getObjectFiles() const { return ObjectFiles; }
  48   ArrayRef<BinaryFile *> getBinaryFiles() const { return BinaryFiles; }
  49   ArrayRef<SharedFile<ELFT> *> getSharedFiles() const { return SharedFiles; }
  50
  51   DefinedRegular *addAbsolute(StringRef Name,
  52                               uint8_t Visibility = llvm::ELF::STV_HIDDEN,
  53                               uint8_t Binding = llvm::ELF::STB_GLOBAL);
  54   DefinedRegular *addIgnored(StringRef Name,
  55                              uint8_t Visibility = llvm::ELF::STV_HIDDEN);
  56
  57   Symbol *addUndefined(StringRef Name);
  58   Symbol *addUndefined(StringRef Name, bool IsLocal, uint8_t Binding,
  59                        uint8_t StOther, uint8_t Type, bool CanOmitFromDynSym,
  60                        InputFile *File);
  61
  62   Symbol *addRegular(StringRef Name, uint8_t StOther, uint8_t Type,
  63                      uint64_t Value, uint64_t Size, uint8_t Binding,
  64                      SectionBase *Section, InputFile *File);
  65
  66   void addShared(SharedFile<ELFT> *F, StringRef Name, const Elf_Sym &Sym,
  67                  const typename ELFT::Verdef *Verdef);
  68
  69   Symbol *addLazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S);
  70   void addLazyObject(StringRef Name, LazyObjectFile &Obj);
  71   Symbol *addBitcode(StringRef Name, uint8_t Binding, uint8_t StOther,
  72                      uint8_t Type, bool CanOmitFromDynSym, BitcodeFile *File);
  73
  74   Symbol *addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
  75                     uint8_t Binding, uint8_t StOther, uint8_t Type,
  76                     InputFile *File);
  77
  78   std::pair<Symbol *, bool> insert(StringRef Name);
  79   std::pair<Symbol *, bool> insert(StringRef Name, uint8_t Type,
  80                                    uint8_t Visibility, bool CanOmitFromDynSym,
  81                                    InputFile *File);
  82
  83   void scanUndefinedFlags();
  84   void scanShlibUndefined();
  85   void scanVersionScript();
  86
  87   SymbolBody *find(StringRef Name);
  88   SymbolBody *findInCurrentDSO(StringRef Name);
  89
  90   void trace(StringRef Name);
  91
  92 private:
  93   std::vector<SymbolBody *> findByVersion(SymbolVersion Ver);
  94   std::vector<SymbolBody *> findAllByVersion(SymbolVersion Ver);
  95
  96   llvm::StringMap<std::vector<SymbolBody *>> &getDemangledSyms();
  97   void handleAnonymousVersion();
  98   void assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
  99                           StringRef VersionName);
 100   void assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId);
 101
 102   struct SymIndex {
 103     SymIndex(int Idx, bool Traced) : Idx(Idx), Traced(Traced) {}
 104     int Idx : 31;
 105     unsigned Traced : 1;
 106   };
 107
 108   // The order the global symbols are in is not defined. We can use an arbitrary
 109   // order, but it has to be reproducible. That is true even when cross linking.
 110   // The default hashing of StringRef produces different results on 32 and 64
 111   // bit systems so we use a map to a vector. That is arbitrary, deterministic
 112   // but a bit inefficient.
 113   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
 114   // once symbol resolution is finished.
 115   llvm::DenseMap<llvm::CachedHashStringRef, SymIndex> Symtab;
 116   std::vector<Symbol *> SymVector;
 117
 118   // Comdat groups define "link once" sections. If two comdat groups have the
 119   // same name, only one of them is linked, and the other is ignored. This set
 120   // is used to uniquify them.
 121   llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 122
 123   std::vector<ObjectFile<ELFT> *> ObjectFiles;
 124   std::vector<SharedFile<ELFT> *> SharedFiles;
 125   std::vector<BitcodeFile *> BitcodeFiles;
 126   std::vector<BinaryFile *> BinaryFiles;
 127
 128   // Set of .so files to not link the same shared object file more than once.
 129   llvm::DenseSet<StringRef> SoNames;
 130
 131   // A map from demangled symbol names to their symbol objects.
 132   // This mapping is 1:N because two symbols with different versions
 133   // can have the same name. We use this map to handle "extern C++ {}"
 134   // directive in version scripts.
 135   llvm::Optional<llvm::StringMap<std::vector<SymbolBody *>>> DemangledSyms;
 136
 137   // For LTO.
 138   std::unique_ptr<BitcodeCompiler> LTO;
 139 };
 140
 141 template <class ELFT> struct Symtab { static SymbolTable<ELFT> *X; };
 142 template <class ELFT> SymbolTable<ELFT> *Symtab<ELFT>::X;
 143
 144 } // namespace elf
 145 } // namespace lld
 146
 147 #endif