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
291