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