contrib/llvm-project/lld/lib/Core/SymbolTable.cpp

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