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())
227     return false;
228   if (r == getEmptyKey())
229     return false;
230   if (l == getTombstoneKey())
231     return false;
232   if (r == getTombstoneKey())
233     return false;
234   if (l->contentType() != r->contentType())
235     return false;
236   if (l->size() != r->size())
237     return false;
238   if (l->sectionChoice() != r->sectionChoice())
239     return false;
240   if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) {
241     if (!l->customSectionName().equals(r->customSectionName()))
242       return false;
243   }
244   ArrayRef<uint8_t> lc = l->rawContent();
245   ArrayRef<uint8_t> rc = r->rawContent();
246   return memcmp(lc.data(), rc.data(), lc.size()) == 0;
247 }
248 
249 bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
250   AtomContentSet::iterator pos = _contentTable.find(&newAtom);
251   if (pos == _contentTable.end()) {
252     _contentTable.insert(&newAtom);
253     return true;
254   }
255   const Atom* existing = *pos;
256   // New atom is not being used.  Add it to replacement table.
257   _replacedAtoms[&newAtom] = existing;
258   return false;
259 }
260 
261 const Atom *SymbolTable::findByName(StringRef sym) {
262   NameToAtom::iterator pos = _nameTable.find(sym);
263   if (pos == _nameTable.end())
264     return nullptr;
265   return pos->second;
266 }
267 
268 bool SymbolTable::isDefined(StringRef sym) {
269   if (const Atom *atom = findByName(sym))
270     return !isa<UndefinedAtom>(atom);
271   return false;
272 }
273 
274 void SymbolTable::addReplacement(const Atom *replaced,
275                                  const Atom *replacement) {
276   _replacedAtoms[replaced] = replacement;
277 }
278 
279 const Atom *SymbolTable::replacement(const Atom *atom) {
280   // Find the replacement for a given atom. Atoms in _replacedAtoms
281   // may be chained, so find the last one.
282   for (;;) {
283     AtomToAtom::iterator pos = _replacedAtoms.find(atom);
284     if (pos == _replacedAtoms.end())
285       return atom;
286     atom = pos->second;
287   }
288 }
289 
290 bool SymbolTable::isCoalescedAway(const Atom *atom) {
291   return _replacedAtoms.count(atom) > 0;
292 }
293 
294 std::vector<const UndefinedAtom *> SymbolTable::undefines() {
295   std::vector<const UndefinedAtom *> ret;
296   for (auto it : _nameTable) {
297     const Atom *atom = it.second;
298     assert(atom != nullptr);
299     if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
300       if (_replacedAtoms.count(undef) == 0)
301         ret.push_back(undef);
302   }
303   return ret;
304 }
305 
306 std::vector<StringRef> SymbolTable::tentativeDefinitions() {
307   std::vector<StringRef> ret;
308   for (auto entry : _nameTable) {
309     const Atom *atom = entry.second;
310     StringRef name   = entry.first;
311     assert(atom != nullptr);
312     if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom))
313       if (defAtom->merge() == DefinedAtom::mergeAsTentative)
314         ret.push_back(name);
315   }
316   return ret;
317 }
318 
319 } // namespace lld
320