lib/Core/SymbolTable.cpp

   1 //===- Core/SymbolTable.cpp - Main Symbol Table ---------------------------===//
   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 #include "lld/Core/SymbolTable.h"
  11 #include "lld/Core/AbsoluteAtom.h"
  12 #include "lld/Core/Atom.h"
  13 #include "lld/Core/DefinedAtom.h"
  14 #include "lld/Core/File.h"
  15 #include "lld/Core/LLVM.h"
  16 #include "lld/Core/LinkingContext.h"
  17 #include "lld/Core/Resolver.h"
  18 #include "lld/Core/SharedLibraryAtom.h"
  19 #include "lld/Core/UndefinedAtom.h"
  20 #include "llvm/ADT/ArrayRef.h"
  21 #include "llvm/ADT/DenseMapInfo.h"
  22 #include "llvm/ADT/Hashing.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <cstdlib>
  28 #include <vector>
  29
  30 namespace lld {
  31 bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
  32
  33 bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
  34
  35 bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
  36
  37 bool SymbolTable::add(const DefinedAtom &atom) {
  38   if (!atom.name().empty() &&
  39       atom.scope() != DefinedAtom::scopeTranslationUnit) {
  40     // Named atoms cannot be merged by content.
  41     assert(atom.merge() != DefinedAtom::mergeByContent);
  42     // Track named atoms that are not scoped to file (static).
  43     return addByName(atom);
  44   }
  45   if (atom.merge() == DefinedAtom::mergeByContent) {
  46     // Named atoms cannot be merged by content.
  47     assert(atom.name().empty());
  48     // Currently only read-only constants can be merged.
  49     if (atom.permissions() == DefinedAtom::permR__)
  50       return addByContent(atom);
  51     // TODO: support mergeByContent of data atoms by comparing content & fixups.
  52   }
  53   return false;
  54 }
  55
  56 enum NameCollisionResolution {
  57   NCR_First,
  58   NCR_Second,
  59   NCR_DupDef,
  60   NCR_DupUndef,
  61   NCR_DupShLib,
  62   NCR_Error
  63 };
  64
  65 static NameCollisionResolution cases[4][4] = {
  66   //regular     absolute    undef      sharedLib
  67   {
  68     // first is regular
  69     NCR_DupDef, NCR_Error,   NCR_First, NCR_First
  70   },
  71   {
  72     // first is absolute
  73     NCR_Error,  NCR_Error,  NCR_First, NCR_First
  74   },
  75   {
  76     // first is undef
  77     NCR_Second, NCR_Second, NCR_DupUndef, NCR_Second
  78   },
  79   {
  80     // first is sharedLib
  81     NCR_Second, NCR_Second, NCR_First, NCR_DupShLib
  82   }
  83 };
  84
  85 static NameCollisionResolution collide(Atom::Definition first,
  86                                        Atom::Definition second) {
  87   return cases[first][second];
  88 }
  89
  90 enum MergeResolution {
  91   MCR_First,
  92   MCR_Second,
  93   MCR_Largest,
  94   MCR_SameSize,
  95   MCR_Error
  96 };
  97
  98 static MergeResolution mergeCases[][6] = {
  99   // no          tentative      weak          weakAddress   sameNameAndSize largest
 100   {MCR_Error,    MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // no
 101   {MCR_Second,   MCR_Largest,   MCR_Second,   MCR_Second,   MCR_SameSize,   MCR_Largest},  // tentative
 102   {MCR_Second,   MCR_First,     MCR_First,    MCR_Second,   MCR_SameSize,   MCR_Largest},  // weak
 103   {MCR_Second,   MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // weakAddress
 104   {MCR_SameSize, MCR_SameSize,  MCR_SameSize, MCR_SameSize, MCR_SameSize,   MCR_SameSize}, // sameSize
 105   {MCR_Largest,  MCR_Largest,   MCR_Largest,  MCR_Largest,  MCR_SameSize,   MCR_Largest},  // largest
 106 };
 107
 108 static MergeResolution mergeSelect(DefinedAtom::Merge first,
 109                                    DefinedAtom::Merge second) {
 110   assert(first != DefinedAtom::mergeByContent);
 111   assert(second != DefinedAtom::mergeByContent);
 112   return mergeCases[first][second];
 113 }
 114
 115 bool SymbolTable::addByName(const Atom &newAtom) {
 116   StringRef name = newAtom.name();
 117   assert(!name.empty());
 118   const Atom *existing = findByName(name);
 119   if (existing == nullptr) {
 120     // Name is not in symbol table yet, add it associate with this atom.
 121     _nameTable[name] = &newAtom;
 122     return true;
 123   }
 124
 125   // Do nothing if the same object is added more than once.
 126   if (existing == &newAtom)
 127     return false;
 128
 129   // Name is already in symbol table and associated with another atom.
 130   bool useNew = true;
 131   switch (collide(existing->definition(), newAtom.definition())) {
 132   case NCR_First:
 133     useNew = false;
 134     break;
 135   case NCR_Second:
 136     useNew = true;
 137     break;
 138   case NCR_DupDef: {
 139     const auto *existingDef = cast<DefinedAtom>(existing);
 140     const auto *newDef = cast<DefinedAtom>(&newAtom);
 141     switch (mergeSelect(existingDef->merge(), newDef->merge())) {
 142     case MCR_First:
 143       useNew = false;
 144       break;
 145     case MCR_Second:
 146       useNew = true;
 147       break;
 148     case MCR_Largest: {
 149       uint64_t existingSize = existingDef->sectionSize();
 150       uint64_t newSize = newDef->sectionSize();
 151       useNew = (newSize >= existingSize);
 152       break;
 153     }
 154     case MCR_SameSize: {
 155       uint64_t existingSize = existingDef->sectionSize();
 156       uint64_t newSize = newDef->sectionSize();
 157       if (existingSize == newSize) {
 158         useNew = true;
 159         break;
 160       }
 161       llvm::errs() << "Size mismatch: "
 162                    << existing->name() << " (" << existingSize << ") "
 163                    << newAtom.name() << " (" << newSize << ")\n";
 164       // fallthrough
 165     }
 166     case MCR_Error:
 167       llvm::errs() << "Duplicate symbols: "
 168                    << existing->name()
 169                    << ":"
 170                    << existing->file().path()
 171                    << " and "
 172                    << newAtom.name()
 173                    << ":"
 174                    << newAtom.file().path()
 175                    << "\n";
 176       llvm::report_fatal_error("duplicate symbol error");
 177       break;
 178     }
 179     break;
 180   }
 181   case NCR_DupUndef: {
 182     const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing);
 183     const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom);
 184
 185     bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull());
 186     if (sameCanBeNull)
 187       useNew = false;
 188     else
 189       useNew = (newUndef->canBeNull() < existingUndef->canBeNull());
 190     break;
 191   }
 192   case NCR_DupShLib: {
 193     useNew = false;
 194     break;
 195   }
 196   case NCR_Error:
 197     llvm::errs() << "SymbolTable: error while merging " << name << "\n";
 198     llvm::report_fatal_error("duplicate symbol error");
 199     break;
 200   }
 201
 202   if (useNew) {
 203     // Update name table to use new atom.
 204     _nameTable[name] = &newAtom;
 205     // Add existing atom to replacement table.
 206     _replacedAtoms[existing] = &newAtom;
 207   } else {
 208     // New atom is not being used.  Add it to replacement table.
 209     _replacedAtoms[&newAtom] = existing;
 210   }
 211   return false;
 212 }
 213
 214 unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
 215   auto content = atom->rawContent();
 216   return llvm::hash_combine(atom->size(),
 217                             atom->contentType(),
 218                             llvm::hash_combine_range(content.begin(),
 219                                                      content.end()));
 220 }
 221
 222 bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l,
 223                                            const DefinedAtom * const r) {
 224   if (l == r)
 225     return true;
 226   if (l == getEmptyKey() || r == getEmptyKey())
 227     return false;
 228   if (l == getTombstoneKey() || r == getTombstoneKey())
 229     return false;
 230   if (l->contentType() != r->contentType())
 231     return false;
 232   if (l->size() != r->size())
 233     return false;
 234   if (l->sectionChoice() != r->sectionChoice())
 235     return false;
 236   if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) {
 237     if (!l->customSectionName().equals(r->customSectionName()))
 238       return false;
 239   }
 240   ArrayRef<uint8_t> lc = l->rawContent();
 241   ArrayRef<uint8_t> rc = r->rawContent();
 242   return memcmp(lc.data(), rc.data(), lc.size()) == 0;
 243 }
 244
 245 bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
 246   AtomContentSet::iterator pos = _contentTable.find(&newAtom);
 247   if (pos == _contentTable.end()) {
 248     _contentTable.insert(&newAtom);
 249     return true;
 250   }
 251   const Atom* existing = *pos;
 252   // New atom is not being used.  Add it to replacement table.
 253   _replacedAtoms[&newAtom] = existing;
 254   return false;
 255 }
 256
 257 const Atom *SymbolTable::findByName(StringRef sym) {
 258   NameToAtom::iterator pos = _nameTable.find(sym);
 259   if (pos == _nameTable.end())
 260     return nullptr;
 261   return pos->second;
 262 }
 263
 264 const Atom *SymbolTable::replacement(const Atom *atom) {
 265   // Find the replacement for a given atom. Atoms in _replacedAtoms
 266   // may be chained, so find the last one.
 267   for (;;) {
 268     AtomToAtom::iterator pos = _replacedAtoms.find(atom);
 269     if (pos == _replacedAtoms.end())
 270       return atom;
 271     atom = pos->second;
 272   }
 273 }
 274
 275 bool SymbolTable::isCoalescedAway(const Atom *atom) {
 276   return _replacedAtoms.count(atom) > 0;
 277 }
 278
 279 std::vector<const UndefinedAtom *> SymbolTable::undefines() {
 280   std::vector<const UndefinedAtom *> ret;
 281   for (auto it : _nameTable) {
 282     const Atom *atom = it.second;
 283     assert(atom != nullptr);
 284     if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
 285       if (_replacedAtoms.count(undef) == 0)
 286         ret.push_back(undef);
 287   }
 288   return ret;
 289 }
 290
 291 } // namespace lld