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
  43   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
  44   ArrayRef<ObjectFile<ELFT> *> getObjectFiles() const { return ObjectFiles; }
  45   ArrayRef<BinaryFile *> getBinaryFiles() const { return BinaryFiles; }
  46   ArrayRef<SharedFile<ELFT> *> getSharedFiles() const { return SharedFiles; }
  47
  48   DefinedRegular *addAbsolute(StringRef Name,
  49                               uint8_t Visibility = llvm::ELF::STV_HIDDEN,
  50                               uint8_t Binding = llvm::ELF::STB_GLOBAL);
  51   DefinedRegular *addIgnored(StringRef Name,
  52                              uint8_t Visibility = llvm::ELF::STV_HIDDEN);
  53
  54   Symbol *addUndefined(StringRef Name);
  55   Symbol *addUndefined(StringRef Name, bool IsLocal, uint8_t Binding,
  56                        uint8_t StOther, uint8_t Type, bool CanOmitFromDynSym,
  57                        InputFile *File);
  58
  59   Symbol *addRegular(StringRef Name, uint8_t StOther, uint8_t Type,
  60                      uint64_t Value, uint64_t Size, uint8_t Binding,
  61                      SectionBase *Section, InputFile *File);
  62
  63   void addShared(SharedFile<ELFT> *F, StringRef Name, const Elf_Sym &Sym,
  64                  const typename ELFT::Verdef *Verdef);
  65
  66   void addLazyArchive(ArchiveFile *F, const llvm::object::Archive::Symbol S);
  67   void addLazyObject(StringRef Name, LazyObjectFile &Obj);
  68   Symbol *addBitcode(StringRef Name, uint8_t Binding, uint8_t StOther,
  69                      uint8_t Type, bool CanOmitFromDynSym, BitcodeFile *File);
  70
  71   Symbol *addCommon(StringRef N, uint64_t Size, uint32_t Alignment,
  72                     uint8_t Binding, uint8_t StOther, uint8_t Type,
  73                     InputFile *File);
  74
  75   std::pair<Symbol *, bool> insert(StringRef Name);
  76   std::pair<Symbol *, bool> insert(StringRef Name, uint8_t Type,
  77                                    uint8_t Visibility, bool CanOmitFromDynSym,
  78                                    InputFile *File);
  79
  80   void scanUndefinedFlags();
  81   void scanShlibUndefined();
  82   void scanVersionScript();
  83
  84   SymbolBody *find(StringRef Name);
  85   SymbolBody *findInCurrentDSO(StringRef Name);
  86
  87   void trace(StringRef Name);
  88   void wrap(StringRef Name);
  89
  90 private:
  91   std::vector<SymbolBody *> findByVersion(SymbolVersion Ver);
  92   std::vector<SymbolBody *> findAllByVersion(SymbolVersion Ver);
  93
  94   llvm::StringMap<std::vector<SymbolBody *>> &getDemangledSyms();
  95   void handleAnonymousVersion();
  96   void assignExactVersion(SymbolVersion Ver, uint16_t VersionId,
  97                           StringRef VersionName);
  98   void assignWildcardVersion(SymbolVersion Ver, uint16_t VersionId);
  99
 100   struct SymIndex {
 101     SymIndex(int Idx, bool Traced) : Idx(Idx), Traced(Traced) {}
 102     int Idx : 31;
 103     unsigned Traced : 1;
 104   };
 105
 106   // The order the global symbols are in is not defined. We can use an arbitrary
 107   // order, but it has to be reproducible. That is true even when cross linking.
 108   // The default hashing of StringRef produces different results on 32 and 64
 109   // bit systems so we use a map to a vector. That is arbitrary, deterministic
 110   // but a bit inefficient.
 111   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
 112   // once symbol resolution is finished.
 113   llvm::DenseMap<llvm::CachedHashStringRef, SymIndex> Symtab;
 114   std::vector<Symbol *> SymVector;
 115
 116   // Comdat groups define "link once" sections. If two comdat groups have the
 117   // same name, only one of them is linked, and the other is ignored. This set
 118   // is used to uniquify them.
 119   llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 120
 121   std::vector<ObjectFile<ELFT> *> ObjectFiles;
 122   std::vector<SharedFile<ELFT> *> SharedFiles;
 123   std::vector<BitcodeFile *> BitcodeFiles;
 124   std::vector<BinaryFile *> BinaryFiles;
 125
 126   // Set of .so files to not link the same shared object file more than once.
 127   llvm::DenseSet<StringRef> SoNames;
 128
 129   // A map from demangled symbol names to their symbol objects.
 130   // This mapping is 1:N because two symbols with different versions
 131   // can have the same name. We use this map to handle "extern C++ {}"
 132   // directive in version scripts.
 133   llvm::Optional<llvm::StringMap<std::vector<SymbolBody *>>> DemangledSyms;
 134
 135   // For LTO.
 136   std::unique_ptr<BitcodeCompiler> LTO;
 137 };
 138
 139 template <class ELFT> struct Symtab { static SymbolTable<ELFT> *X; };
 140 template <class ELFT> SymbolTable<ELFT> *Symtab<ELFT>::X;
 141
 142 } // namespace elf
 143 } // namespace lld
 144
 145 #endif