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 SymbolTable::SymbolTable(LinkingContext &context) : _context(context) {}
  32
  33 bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
  34
  35 bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
  36
  37 bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
  38
  39 bool SymbolTable::add(const DefinedAtom &atom) {
  40   if (!atom.name().empty() &&
  41       atom.scope() != DefinedAtom::scopeTranslationUnit) {
  42     // Named atoms cannot be merged by content.
  43     assert(atom.merge() != DefinedAtom::mergeByContent);
  44     // Track named atoms that are not scoped to file (static).
  45     return addByName(atom);
  46   }
  47   if (atom.merge() == DefinedAtom::mergeByContent) {
  48     // Named atoms cannot be merged by content.
  49     assert(atom.name().empty());
  50     // Currently only read-only constants can be merged.
  51     if (atom.permissions() == DefinedAtom::permR__)
  52       return addByContent(atom);
  53     // TODO: support mergeByContent of data atoms by comparing content & fixups.
  54   }
  55   return false;
  56 }
  57
  58 const Atom *SymbolTable::findGroup(StringRef sym) {
  59   NameToAtom::iterator pos = _groupTable.find(sym);
  60   if (pos == _groupTable.end())
  61     return nullptr;
  62   return pos->second;
  63 }
  64
  65 bool SymbolTable::addGroup(const DefinedAtom &da) {
  66   StringRef name = da.name();
  67   assert(!name.empty());
  68   const Atom *existing = findGroup(name);
  69   if (existing == nullptr) {
  70     _groupTable[name] = &da;
  71     return true;
  72   }
  73   _replacedAtoms[&da] = existing;
  74   return false;
  75 }
  76
  77 enum NameCollisionResolution {
  78   NCR_First,
  79   NCR_Second,
  80   NCR_DupDef,
  81   NCR_DupUndef,
  82   NCR_DupShLib,
  83   NCR_Error
  84 };
  85
  86 static NameCollisionResolution cases[4][4] = {
  87   //regular     absolute    undef      sharedLib
  88   {
  89     // first is regular
  90     NCR_DupDef, NCR_Error,   NCR_First, NCR_First
  91   },
  92   {
  93     // first is absolute
  94     NCR_Error,  NCR_Error,  NCR_First, NCR_First
  95   },
  96   {
  97     // first is undef
  98     NCR_Second, NCR_Second, NCR_DupUndef, NCR_Second
  99   },
 100   {
 101     // first is sharedLib
 102     NCR_Second, NCR_Second, NCR_First, NCR_DupShLib
 103   }
 104 };
 105
 106 static NameCollisionResolution collide(Atom::Definition first,
 107                                        Atom::Definition second) {
 108   return cases[first][second];
 109 }
 110
 111 enum MergeResolution {
 112   MCR_First,
 113   MCR_Second,
 114   MCR_Largest,
 115   MCR_SameSize,
 116   MCR_Error
 117 };
 118
 119 static MergeResolution mergeCases[][6] = {
 120   // no          tentative      weak          weakAddress   sameNameAndSize largest
 121   {MCR_Error,    MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // no
 122   {MCR_Second,   MCR_Largest,   MCR_Second,   MCR_Second,   MCR_SameSize,   MCR_Largest},  // tentative
 123   {MCR_Second,   MCR_First,     MCR_First,    MCR_Second,   MCR_SameSize,   MCR_Largest},  // weak
 124   {MCR_Second,   MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // weakAddress
 125   {MCR_SameSize, MCR_SameSize,  MCR_SameSize, MCR_SameSize, MCR_SameSize,   MCR_SameSize}, // sameSize
 126   {MCR_Largest,  MCR_Largest,   MCR_Largest,  MCR_Largest,  MCR_SameSize,   MCR_Largest},  // largest
 127 };
 128
 129 static MergeResolution mergeSelect(DefinedAtom::Merge first,
 130                                    DefinedAtom::Merge second) {
 131   assert(first != DefinedAtom::mergeByContent);
 132   assert(second != DefinedAtom::mergeByContent);
 133   return mergeCases[first][second];
 134 }
 135
 136 bool SymbolTable::addByName(const Atom &newAtom) {
 137   StringRef name = newAtom.name();
 138   assert(!name.empty());
 139   const Atom *existing = findByName(name);
 140   if (existing == nullptr) {
 141     // Name is not in symbol table yet, add it associate with this atom.
 142     _nameTable[name] = &newAtom;
 143     return true;
 144   }
 145
 146   // Do nothing if the same object is added more than once.
 147   if (existing == &newAtom)
 148     return false;
 149
 150   // Name is already in symbol table and associated with another atom.
 151   bool useNew = true;
 152   switch (collide(existing->definition(), newAtom.definition())) {
 153   case NCR_First:
 154     useNew = false;
 155     break;
 156   case NCR_Second:
 157     useNew = true;
 158     break;
 159   case NCR_DupDef: {
 160     const auto *existingDef = cast<DefinedAtom>(existing);
 161     const auto *newDef = cast<DefinedAtom>(&newAtom);
 162     switch (mergeSelect(existingDef->merge(), newDef->merge())) {
 163     case MCR_First:
 164       useNew = false;
 165       break;
 166     case MCR_Second:
 167       useNew = true;
 168       break;
 169     case MCR_Largest: {
 170       uint64_t existingSize = existingDef->sectionSize();
 171       uint64_t newSize = newDef->sectionSize();
 172       useNew = (newSize >= existingSize);
 173       break;
 174     }
 175     case MCR_SameSize: {
 176       uint64_t existingSize = existingDef->sectionSize();
 177       uint64_t newSize = newDef->sectionSize();
 178       if (existingSize == newSize) {
 179         useNew = true;
 180         break;
 181       }
 182       llvm::errs() << "Size mismatch: "
 183                    << existing->name() << " (" << existingSize << ") "
 184                    << newAtom.name() << " (" << newSize << ")\n";
 185       // fallthrough
 186     }
 187     case MCR_Error:
 188       if (!_context.getAllowDuplicates()) {
 189         llvm::errs() << "Duplicate symbols: "
 190                      << existing->name()
 191                      << ":"
 192                      << existing->file().path()
 193                      << " and "
 194                      << newAtom.name()
 195                      << ":"
 196                      << newAtom.file().path()
 197                      << "\n";
 198         llvm::report_fatal_error("duplicate symbol error");
 199       }
 200       useNew = false;
 201       break;
 202     }
 203     break;
 204   }
 205   case NCR_DupUndef: {
 206     const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing);
 207     const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom);
 208
 209     bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull());
 210     if (!sameCanBeNull &&
 211         _context.warnIfCoalesableAtomsHaveDifferentCanBeNull()) {
 212       llvm::errs() << "lld warning: undefined symbol "
 213                    << existingUndef->name()
 214                    << " has different weakness in "
 215                    << existingUndef->file().path()
 216                    << " and in " << newUndef->file().path() << "\n";
 217     }
 218
 219     const UndefinedAtom *existingFallback = existingUndef->fallback();
 220     const UndefinedAtom *newFallback = newUndef->fallback();
 221     bool hasDifferentFallback =
 222         (existingFallback && newFallback &&
 223          existingFallback->name() != newFallback->name());
 224     if (hasDifferentFallback) {
 225       llvm::errs() << "lld warning: undefined symbol "
 226                    << existingUndef->name() << " has different fallback: "
 227                    << existingFallback->name() << " in "
 228                    << existingUndef->file().path() << " and "
 229                    << newFallback->name() << " in "
 230                    << newUndef->file().path() << "\n";
 231     }
 232
 233     bool hasNewFallback = newUndef->fallback();
 234     if (sameCanBeNull)
 235       useNew = hasNewFallback;
 236     else
 237       useNew = (newUndef->canBeNull() < existingUndef->canBeNull());
 238     break;
 239   }
 240   case NCR_DupShLib: {
 241     const SharedLibraryAtom *curShLib = cast<SharedLibraryAtom>(existing);
 242     const SharedLibraryAtom *newShLib = cast<SharedLibraryAtom>(&newAtom);
 243     bool sameNullness =
 244         (curShLib->canBeNullAtRuntime() == newShLib->canBeNullAtRuntime());
 245     bool sameName = curShLib->loadName().equals(newShLib->loadName());
 246     if (sameName && !sameNullness &&
 247         _context.warnIfCoalesableAtomsHaveDifferentCanBeNull()) {
 248       // FIXME: need diagonstics interface for writing warning messages
 249       llvm::errs() << "lld warning: shared library symbol "
 250                    << curShLib->name() << " has different weakness in "
 251                    << curShLib->file().path() << " and in "
 252                    << newShLib->file().path();
 253     }
 254     if (!sameName && _context.warnIfCoalesableAtomsHaveDifferentLoadName()) {
 255       // FIXME: need diagonstics interface for writing warning messages
 256       llvm::errs() << "lld warning: shared library symbol "
 257                    << curShLib->name() << " has different load path in "
 258                    << curShLib->file().path() << " and in "
 259                    << newShLib->file().path();
 260     }
 261     useNew = false;
 262     break;
 263   }
 264   case NCR_Error:
 265     llvm::errs() << "SymbolTable: error while merging " << name << "\n";
 266     llvm::report_fatal_error("duplicate symbol error");
 267     break;
 268   }
 269
 270   // Give context a chance to change which is kept.
 271   _context.notifySymbolTableCoalesce(existing, &newAtom, useNew);
 272
 273   if (useNew) {
 274     // Update name table to use new atom.
 275     _nameTable[name] = &newAtom;
 276     // Add existing atom to replacement table.
 277     _replacedAtoms[existing] = &newAtom;
 278   } else {
 279     // New atom is not being used.  Add it to replacement table.
 280     _replacedAtoms[&newAtom] = existing;
 281   }
 282   return false;
 283 }
 284
 285 unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
 286   auto content = atom->rawContent();
 287   return llvm::hash_combine(atom->size(),
 288                             atom->contentType(),
 289                             llvm::hash_combine_range(content.begin(),
 290                                                      content.end()));
 291 }
 292
 293 bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l,
 294                                            const DefinedAtom * const r) {
 295   if (l == r)
 296     return true;
 297   if (l == getEmptyKey())
 298     return false;
 299   if (r == getEmptyKey())
 300     return false;
 301   if (l == getTombstoneKey())
 302     return false;
 303   if (r == getTombstoneKey())
 304     return false;
 305   if (l->contentType() != r->contentType())
 306     return false;
 307   if (l->size() != r->size())
 308     return false;
 309   if (l->sectionChoice() != r->sectionChoice())
 310     return false;
 311   if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) {
 312     if (!l->customSectionName().equals(r->customSectionName()))
 313       return false;
 314   }
 315   ArrayRef<uint8_t> lc = l->rawContent();
 316   ArrayRef<uint8_t> rc = r->rawContent();
 317   return memcmp(lc.data(), rc.data(), lc.size()) == 0;
 318 }
 319
 320 bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
 321   AtomContentSet::iterator pos = _contentTable.find(&newAtom);
 322   if (pos == _contentTable.end()) {
 323     _contentTable.insert(&newAtom);
 324     return true;
 325   }
 326   const Atom* existing = *pos;
 327   // New atom is not being used.  Add it to replacement table.
 328   _replacedAtoms[&newAtom] = existing;
 329   return false;
 330 }
 331
 332 const Atom *SymbolTable::findByName(StringRef sym) {
 333   NameToAtom::iterator pos = _nameTable.find(sym);
 334   if (pos == _nameTable.end())
 335     return nullptr;
 336   return pos->second;
 337 }
 338
 339 bool SymbolTable::isDefined(StringRef sym) {
 340   if (const Atom *atom = findByName(sym))
 341     return !isa<UndefinedAtom>(atom);
 342   return false;
 343 }
 344
 345 void SymbolTable::addReplacement(const Atom *replaced,
 346                                  const Atom *replacement) {
 347   _replacedAtoms[replaced] = replacement;
 348 }
 349
 350 const Atom *SymbolTable::replacement(const Atom *atom) {
 351   // Find the replacement for a given atom. Atoms in _replacedAtoms
 352   // may be chained, so find the last one.
 353   for (;;) {
 354     AtomToAtom::iterator pos = _replacedAtoms.find(atom);
 355     if (pos == _replacedAtoms.end())
 356       return atom;
 357     atom = pos->second;
 358   }
 359 }
 360
 361 bool SymbolTable::isCoalescedAway(const Atom *atom) {
 362   return _replacedAtoms.count(atom) > 0;
 363 }
 364
 365 std::vector<const UndefinedAtom *> SymbolTable::undefines() {
 366   std::vector<const UndefinedAtom *> ret;
 367   for (auto it : _nameTable) {
 368     const Atom *atom = it.second;
 369     assert(atom != nullptr);
 370     if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
 371       if (_replacedAtoms.count(undef) == 0)
 372         ret.push_back(undef);
 373   }
 374   return ret;
 375 }
 376
 377 std::vector<StringRef> SymbolTable::tentativeDefinitions() {
 378   std::vector<StringRef> ret;
 379   for (auto entry : _nameTable) {
 380     const Atom *atom = entry.second;
 381     StringRef name   = entry.first;
 382     assert(atom != nullptr);
 383     if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom))
 384       if (defAtom->merge() == DefinedAtom::mergeAsTentative)
 385         ret.push_back(name);
 386   }
 387   return ret;
 388 }
 389
 390 } // namespace lld