lib/Core/Resolver.cpp

   1 //===- Core/Resolver.cpp - Resolves Atom References -----------------------===//
   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/Atom.h"
  11 #include "lld/Core/ArchiveLibraryFile.h"
  12 #include "lld/Core/File.h"
  13 #include "lld/Core/Instrumentation.h"
  14 #include "lld/Core/LLVM.h"
  15 #include "lld/Core/LinkingContext.h"
  16 #include "lld/Core/Resolver.h"
  17 #include "lld/Core/SharedLibraryFile.h"
  18 #include "lld/Core/SymbolTable.h"
  19 #include "lld/Core/UndefinedAtom.h"
  20 #include "llvm/ADT/iterator_range.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/ErrorHandling.h"
  23 #include "llvm/Support/Format.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <utility>
  28 #include <vector>
  29
  30 namespace lld {
  31
  32 bool Resolver::handleFile(File &file) {
  33   bool undefAdded = false;
  34   for (const DefinedAtom *atom : file.defined())
  35     doDefinedAtom(*atom);
  36   for (const UndefinedAtom *atom : file.undefined()) {
  37     if (doUndefinedAtom(*atom)) {
  38       undefAdded = true;
  39       maybePreloadArchiveMember(atom->name());
  40     }
  41   }
  42   for (const SharedLibraryAtom *atom : file.sharedLibrary())
  43     doSharedLibraryAtom(*atom);
  44   for (const AbsoluteAtom *atom : file.absolute())
  45     doAbsoluteAtom(*atom);
  46   return undefAdded;
  47 }
  48
  49 void Resolver::forEachUndefines(File &file, bool searchForOverrides,
  50                                 UndefCallback callback) {
  51   size_t i = _undefineIndex[&file];
  52   do {
  53     for (; i < _undefines.size(); ++i) {
  54       StringRef undefName = _undefines[i];
  55       if (undefName.empty())
  56         continue;
  57       const Atom *atom = _symbolTable.findByName(undefName);
  58       if (!isa<UndefinedAtom>(atom) || _symbolTable.isCoalescedAway(atom)) {
  59         // The symbol was resolved by some other file. Cache the result.
  60         _undefines[i] = "";
  61         continue;
  62       }
  63       callback(undefName, false);
  64     }
  65     if (!searchForOverrides)
  66       continue;
  67     for (StringRef tentDefName : _symbolTable.tentativeDefinitions()) {
  68       // Load for previous tentative may also have loaded
  69       // something that overrode this tentative, so always check.
  70       const Atom *curAtom = _symbolTable.findByName(tentDefName);
  71       assert(curAtom != nullptr);
  72       if (const DefinedAtom *curDefAtom = dyn_cast<DefinedAtom>(curAtom))
  73         if (curDefAtom->merge() == DefinedAtom::mergeAsTentative)
  74           callback(tentDefName, true);
  75     }
  76   } while (i < _undefines.size());
  77   _undefineIndex[&file] = i;
  78 }
  79
  80 bool Resolver::handleArchiveFile(File &file) {
  81   ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
  82   bool searchForOverrides =
  83       _ctx.searchArchivesToOverrideTentativeDefinitions();
  84   bool undefAdded = false;
  85   forEachUndefines(file, searchForOverrides,
  86                    [&](StringRef undefName, bool dataSymbolOnly) {
  87     if (File *member = archiveFile->find(undefName, dataSymbolOnly)) {
  88       member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
  89       member->beforeLink();
  90       updatePreloadArchiveMap();
  91       undefAdded = handleFile(*member) || undefAdded;
  92     }
  93   });
  94   return undefAdded;
  95 }
  96
  97 void Resolver::handleSharedLibrary(File &file) {
  98   // Add all the atoms from the shared library
  99   SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
 100   handleFile(*sharedLibrary);
 101   bool searchForOverrides =
 102       _ctx.searchSharedLibrariesToOverrideTentativeDefinitions();
 103   forEachUndefines(file, searchForOverrides,
 104                    [&](StringRef undefName, bool dataSymbolOnly) {
 105     if (const SharedLibraryAtom *atom =
 106             sharedLibrary->exports(undefName, dataSymbolOnly))
 107       doSharedLibraryAtom(*atom);
 108   });
 109 }
 110
 111 bool Resolver::doUndefinedAtom(const UndefinedAtom &atom) {
 112   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
 113                     << "       UndefinedAtom: "
 114                     << llvm::format("0x%09lX", &atom)
 115                     << ", name=" << atom.name() << "\n");
 116
 117   // add to list of known atoms
 118   _atoms.push_back(&atom);
 119
 120   // tell symbol table
 121   bool newUndefAdded = _symbolTable.add(atom);
 122   if (newUndefAdded)
 123     _undefines.push_back(atom.name());
 124
 125   // If the undefined symbol has an alternative name, try to resolve the
 126   // symbol with the name to give it a second chance. This feature is used
 127   // for COFF "weak external" symbol.
 128   if (newUndefAdded || !_symbolTable.isDefined(atom.name())) {
 129     if (const UndefinedAtom *fallbackAtom = atom.fallback()) {
 130       doUndefinedAtom(*fallbackAtom);
 131       _symbolTable.addReplacement(&atom, fallbackAtom);
 132     }
 133   }
 134   return newUndefAdded;
 135 }
 136
 137 /// \brief Add the section group and the group-child reference members.
 138 void Resolver::maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom) {
 139   // First time adding a group?
 140   bool isFirstTime = _symbolTable.addGroup(atom);
 141
 142   if (!isFirstTime) {
 143     // If duplicate symbols are allowed, select the first group.
 144     if (_ctx.getAllowDuplicates())
 145       return;
 146     auto *prevGroup = dyn_cast<DefinedAtom>(_symbolTable.findGroup(atom.name()));
 147     assert(prevGroup &&
 148            "Internal Error: The group atom could only be a defined atom");
 149     // The atoms should be of the same content type, reject invalid group
 150     // resolution behaviors.
 151     if (atom.contentType() == prevGroup->contentType())
 152       return;
 153     llvm::errs() << "SymbolTable: error while merging " << atom.name()
 154                  << "\n";
 155     llvm::report_fatal_error("duplicate symbol error");
 156     return;
 157   }
 158
 159   for (const Reference *r : atom) {
 160     if (r->kindNamespace() == lld::Reference::KindNamespace::all &&
 161         r->kindValue() == lld::Reference::kindGroupChild) {
 162       const DefinedAtom *target = dyn_cast<DefinedAtom>(r->target());
 163       assert(target && "Internal Error: kindGroupChild references need to "
 164                        "be associated with Defined Atoms only");
 165       _atoms.push_back(target);
 166       _symbolTable.add(*target);
 167     }
 168   }
 169 }
 170
 171 // Called on each atom when a file is added. Returns true if a given
 172 // atom is added to the symbol table.
 173 void Resolver::doDefinedAtom(const DefinedAtom &atom) {
 174   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
 175                     << "         DefinedAtom: "
 176                     << llvm::format("0x%09lX", &atom)
 177                     << ", file=#"
 178                     << atom.file().ordinal()
 179                     << ", atom=#"
 180                     << atom.ordinal()
 181                     << ", name="
 182                     << atom.name()
 183                     << "\n");
 184
 185   // add to list of known atoms
 186   _atoms.push_back(&atom);
 187
 188   if (atom.isGroupParent()) {
 189     maybeAddSectionGroupOrGnuLinkOnce(atom);
 190   } else {
 191     _symbolTable.add(atom);
 192   }
 193
 194   // An atom that should never be dead-stripped is a dead-strip root.
 195   if (_ctx.deadStrip() && atom.deadStrip() == DefinedAtom::deadStripNever) {
 196     _deadStripRoots.insert(&atom);
 197   }
 198 }
 199
 200 void Resolver::doSharedLibraryAtom(const SharedLibraryAtom &atom) {
 201   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
 202                     << "   SharedLibraryAtom: "
 203                     << llvm::format("0x%09lX", &atom)
 204                     << ", name="
 205                     << atom.name()
 206                     << "\n");
 207
 208   // add to list of known atoms
 209   _atoms.push_back(&atom);
 210
 211   // tell symbol table
 212   _symbolTable.add(atom);
 213 }
 214
 215 void Resolver::doAbsoluteAtom(const AbsoluteAtom &atom) {
 216   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
 217                     << "       AbsoluteAtom: "
 218                     << llvm::format("0x%09lX", &atom)
 219                     << ", name="
 220                     << atom.name()
 221                     << "\n");
 222
 223   // add to list of known atoms
 224   _atoms.push_back(&atom);
 225
 226   // tell symbol table
 227   if (atom.scope() != Atom::scopeTranslationUnit)
 228     _symbolTable.add(atom);
 229 }
 230
 231 // utility to add a vector of atoms
 232 void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) {
 233   for (const DefinedAtom *newAtom : newAtoms)
 234     doDefinedAtom(*newAtom);
 235 }
 236
 237 // Instantiate an archive file member if there's a file containing a
 238 // defined symbol for a given symbol name. Instantiation is done in a
 239 // different worker thread and has no visible side effect.
 240 void Resolver::maybePreloadArchiveMember(StringRef sym) {
 241   auto it = _archiveMap.find(sym);
 242   if (it == _archiveMap.end())
 243     return;
 244   ArchiveLibraryFile *archive = it->second;
 245   archive->preload(_ctx.getTaskGroup(), sym);
 246 }
 247
 248 // Returns true if at least one of N previous files has created an
 249 // undefined symbol.
 250 bool Resolver::undefinesAdded(int begin, int end) {
 251   std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
 252   for (int i = begin; i < end; ++i)
 253     if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
 254       if (_newUndefinesAdded[node->getFile()])
 255         return true;
 256   return false;
 257 }
 258
 259 File *Resolver::getFile(int &index) {
 260   std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
 261   if ((size_t)index >= inputs.size())
 262     return nullptr;
 263   if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) {
 264     // We are at the end of the current group. If one or more new
 265     // undefined atom has been added in the last groupSize files, we
 266     // reiterate over the files.
 267     int size = group->getSize();
 268     if (undefinesAdded(index - size, index)) {
 269       index -= size;
 270       return getFile(index);
 271     }
 272     ++index;
 273     return getFile(index);
 274   }
 275   return cast<FileNode>(inputs[index++].get())->getFile();
 276 }
 277
 278 // Update a map of Symbol -> ArchiveFile. The map is used for speculative
 279 // file loading.
 280 void Resolver::updatePreloadArchiveMap() {
 281   std::vector<std::unique_ptr<Node>> &nodes = _ctx.getNodes();
 282   for (int i = nodes.size() - 1; i >= 0; --i) {
 283     auto *fnode = dyn_cast<FileNode>(nodes[i].get());
 284     if (!fnode)
 285       continue;
 286     auto *archive = dyn_cast<ArchiveLibraryFile>(fnode->getFile());
 287     if (!archive || _archiveSeen.count(archive))
 288       continue;
 289     _archiveSeen.insert(archive);
 290     for (StringRef sym : archive->getDefinedSymbols())
 291       _archiveMap[sym] = archive;
 292   }
 293 }
 294
 295 // Keep adding atoms until _ctx.getNextFile() returns an error. This
 296 // function is where undefined atoms are resolved.
 297 bool Resolver::resolveUndefines() {
 298   ScopedTask task(getDefaultDomain(), "resolveUndefines");
 299   int index = 0;
 300   std::set<File *> seen;
 301   for (;;) {
 302     bool undefAdded = false;
 303     File *file = getFile(index);
 304     if (!file)
 305       return true;
 306     if (std::error_code ec = file->parse()) {
 307       llvm::errs() << "Cannot open " + file->path()
 308                    << ": " << ec.message() << "\n";
 309       return false;
 310     }
 311     file->beforeLink();
 312     updatePreloadArchiveMap();
 313     switch (file->kind()) {
 314     case File::kindObject:
 315       // The same file may be visited more than once if the file is
 316       // in --start-group and --end-group. Only library files should
 317       // be processed more than once.
 318       if (seen.count(file))
 319         break;
 320       seen.insert(file);
 321       assert(!file->hasOrdinal());
 322       file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
 323       undefAdded = handleFile(*file);
 324       break;
 325     case File::kindArchiveLibrary:
 326       if (!file->hasOrdinal())
 327         file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
 328       undefAdded = handleArchiveFile(*file);
 329       break;
 330     case File::kindSharedLibrary:
 331       if (!file->hasOrdinal())
 332         file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
 333       handleSharedLibrary(*file);
 334       break;
 335     }
 336     _newUndefinesAdded[file] = undefAdded;
 337   }
 338 }
 339
 340 // switch all references to undefined or coalesced away atoms
 341 // to the new defined atom
 342 void Resolver::updateReferences() {
 343   ScopedTask task(getDefaultDomain(), "updateReferences");
 344   for (const Atom *atom : _atoms) {
 345     if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
 346       for (const Reference *ref : *defAtom) {
 347         // A reference of type kindAssociate should't be updated.
 348         // Instead, an atom having such reference will be removed
 349         // if the target atom is coalesced away, so that they will
 350         // go away as a group.
 351         if (ref->kindNamespace() == lld::Reference::KindNamespace::all &&
 352             ref->kindValue() == lld::Reference::kindAssociate) {
 353           if (_symbolTable.isCoalescedAway(atom))
 354             _deadAtoms.insert(ref->target());
 355           continue;
 356         }
 357         const Atom *newTarget = _symbolTable.replacement(ref->target());
 358         const_cast<Reference *>(ref)->setTarget(newTarget);
 359       }
 360     }
 361   }
 362 }
 363
 364 // For dead code stripping, recursively mark atoms "live"
 365 void Resolver::markLive(const Atom *atom) {
 366   // Mark the atom is live. If it's already marked live, then stop recursion.
 367   auto exists = _liveAtoms.insert(atom);
 368   if (!exists.second)
 369     return;
 370
 371   // Mark all atoms it references as live
 372   if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
 373     for (const Reference *ref : *defAtom)
 374       markLive(ref->target());
 375     for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) {
 376       const Atom *target = p.second;
 377       markLive(target);
 378     }
 379   }
 380 }
 381
 382 static bool isBackref(const Reference *ref) {
 383   if (ref->kindNamespace() != lld::Reference::KindNamespace::all)
 384     return false;
 385   return (ref->kindValue() == lld::Reference::kindLayoutAfter ||
 386           ref->kindValue() == lld::Reference::kindGroupChild);
 387 }
 388
 389 // remove all atoms not actually used
 390 void Resolver::deadStripOptimize() {
 391   ScopedTask task(getDefaultDomain(), "deadStripOptimize");
 392   // only do this optimization with -dead_strip
 393   if (!_ctx.deadStrip())
 394     return;
 395
 396   // Some type of references prevent referring atoms to be dead-striped.
 397   // Make a reverse map of such references before traversing the graph.
 398   // While traversing the list of atoms, mark AbsoluteAtoms as live
 399   // in order to avoid reclaim.
 400   for (const Atom *atom : _atoms) {
 401     if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom))
 402       for (const Reference *ref : *defAtom)
 403         if (isBackref(ref))
 404           _reverseRef.insert(std::make_pair(ref->target(), atom));
 405     if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom))
 406       markLive(absAtom);
 407   }
 408
 409   // By default, shared libraries are built with all globals as dead strip roots
 410   if (_ctx.globalsAreDeadStripRoots())
 411     for (const Atom *atom : _atoms)
 412       if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom))
 413         if (defAtom->scope() == DefinedAtom::scopeGlobal)
 414           _deadStripRoots.insert(defAtom);
 415
 416   // Or, use list of names that are dead strip roots.
 417   for (const StringRef &name : _ctx.deadStripRoots()) {
 418     const Atom *symAtom = _symbolTable.findByName(name);
 419     assert(symAtom);
 420     _deadStripRoots.insert(symAtom);
 421   }
 422
 423   // mark all roots as live, and recursively all atoms they reference
 424   for (const Atom *dsrAtom : _deadStripRoots)
 425     markLive(dsrAtom);
 426
 427   // now remove all non-live atoms from _atoms
 428   _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), [&](const Atom *a) {
 429                  return _liveAtoms.count(a) == 0;
 430                }),
 431                _atoms.end());
 432 }
 433
 434 // error out if some undefines remain
 435 bool Resolver::checkUndefines() {
 436   // build vector of remaining undefined symbols
 437   std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines();
 438   if (_ctx.deadStrip()) {
 439     // When dead code stripping, we don't care if dead atoms are undefined.
 440     undefinedAtoms.erase(
 441         std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
 442                        [&](const Atom *a) { return _liveAtoms.count(a) == 0; }),
 443         undefinedAtoms.end());
 444   }
 445
 446   if (undefinedAtoms.empty())
 447     return false;
 448
 449   // Warn about unresolved symbols.
 450   bool foundUndefines = false;
 451   for (const UndefinedAtom *undef : undefinedAtoms) {
 452     // Skip over a weak symbol.
 453     if (undef->canBeNull() != UndefinedAtom::canBeNullNever)
 454       continue;
 455
 456     // If this is a library and undefined symbols are allowed on the
 457     // target platform, skip over it.
 458     if (isa<SharedLibraryFile>(undef->file()) && _ctx.allowShlibUndefines())
 459       continue;
 460
 461     // If the undefine is coalesced away, skip over it.
 462     if (_symbolTable.isCoalescedAway(undef))
 463       continue;
 464
 465     // Seems like this symbol is undefined. Warn that.
 466     foundUndefines = true;
 467     if (_ctx.printRemainingUndefines()) {
 468       llvm::errs() << "Undefined symbol: " << undef->file().path()
 469                    << ": " << _ctx.demangle(undef->name())
 470                    << "\n";
 471     }
 472   }
 473   if (!foundUndefines)
 474     return false;
 475   if (_ctx.printRemainingUndefines())
 476     llvm::errs() << "symbol(s) not found\n";
 477   return true;
 478 }
 479
 480 // remove from _atoms all coaleseced away atoms
 481 void Resolver::removeCoalescedAwayAtoms() {
 482   ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
 483   _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), [&](const Atom *a) {
 484                  return _symbolTable.isCoalescedAway(a) || _deadAtoms.count(a);
 485                }),
 486                _atoms.end());
 487 }
 488
 489 bool Resolver::resolve() {
 490   updatePreloadArchiveMap();
 491   if (!resolveUndefines())
 492     return false;
 493   updateReferences();
 494   deadStripOptimize();
 495   if (checkUndefines())
 496     if (!_ctx.allowRemainingUndefines())
 497       return false;
 498   removeCoalescedAwayAtoms();
 499   _result->addAtoms(_atoms);
 500   return true;
 501 }
 502
 503 void Resolver::MergedFile::addAtoms(std::vector<const Atom *> &all) {
 504   ScopedTask task(getDefaultDomain(), "addAtoms");
 505   DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");
 506   for (const Atom *atom : all) {
 507     DEBUG_WITH_TYPE("resolver", llvm::dbgs()
 508                     << llvm::format("    0x%09lX", atom)
 509                     << ", name="
 510                     << atom->name()
 511                     << "\n");
 512     addAtom(*atom);
 513   }
 514 }
 515
 516 } // namespace lld