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 {
add(const UndefinedAtom & atom)30 bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
31
add(const SharedLibraryAtom & atom)32 bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
33
add(const AbsoluteAtom & atom)34 bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
35
add(const DefinedAtom & atom)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
collide(Atom::Definition first,Atom::Definition second)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
mergeSelect(DefinedAtom::Merge first,DefinedAtom::Merge second)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
addByName(const Atom & newAtom)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: " << existing->name() << " ("
161 << existingSize << ") " << newAtom.name() << " (" << newSize
162 << ")\n";
163 LLVM_FALLTHROUGH;
164 }
165 case MCR_Error:
166 llvm::errs() << "Duplicate symbols: " << existing->name() << ":"
167 << existing->file().path() << " and " << newAtom.name()
168 << ":" << newAtom.file().path() << "\n";
169 llvm::report_fatal_error("duplicate symbol error");
170 break;
171 }
172 break;
173 }
174 case NCR_DupUndef: {
175 const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing);
176 const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom);
177
178 bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull());
179 if (sameCanBeNull)
180 useNew = false;
181 else
182 useNew = (newUndef->canBeNull() < existingUndef->canBeNull());
183 break;
184 }
185 case NCR_DupShLib: {
186 useNew = false;
187 break;
188 }
189 case NCR_Error:
190 llvm::errs() << "SymbolTable: error while merging " << name << "\n";
191 llvm::report_fatal_error("duplicate symbol error");
192 break;
193 }
194
195 if (useNew) {
196 // Update name table to use new atom.
197 _nameTable[name] = &newAtom;
198 // Add existing atom to replacement table.
199 _replacedAtoms[existing] = &newAtom;
200 } else {
201 // New atom is not being used. Add it to replacement table.
202 _replacedAtoms[&newAtom] = existing;
203 }
204 return false;
205 }
206
getHashValue(const DefinedAtom * atom)207 unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
208 auto content = atom->rawContent();
209 return llvm::hash_combine(atom->size(),
210 atom->contentType(),
211 llvm::hash_combine_range(content.begin(),
212 content.end()));
213 }
214
isEqual(const DefinedAtom * const l,const DefinedAtom * const r)215 bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l,
216 const DefinedAtom * const r) {
217 if (l == r)
218 return true;
219 if (l == getEmptyKey() || r == getEmptyKey())
220 return false;
221 if (l == getTombstoneKey() || r == getTombstoneKey())
222 return false;
223 if (l->contentType() != r->contentType())
224 return false;
225 if (l->size() != r->size())
226 return false;
227 if (l->sectionChoice() != r->sectionChoice())
228 return false;
229 if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) {
230 if (!l->customSectionName().equals(r->customSectionName()))
231 return false;
232 }
233 ArrayRef<uint8_t> lc = l->rawContent();
234 ArrayRef<uint8_t> rc = r->rawContent();
235 return memcmp(lc.data(), rc.data(), lc.size()) == 0;
236 }
237
addByContent(const DefinedAtom & newAtom)238 bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
239 AtomContentSet::iterator pos = _contentTable.find(&newAtom);
240 if (pos == _contentTable.end()) {
241 _contentTable.insert(&newAtom);
242 return true;
243 }
244 const Atom* existing = *pos;
245 // New atom is not being used. Add it to replacement table.
246 _replacedAtoms[&newAtom] = existing;
247 return false;
248 }
249
findByName(StringRef sym)250 const Atom *SymbolTable::findByName(StringRef sym) {
251 NameToAtom::iterator pos = _nameTable.find(sym);
252 if (pos == _nameTable.end())
253 return nullptr;
254 return pos->second;
255 }
256
replacement(const Atom * atom)257 const Atom *SymbolTable::replacement(const Atom *atom) {
258 // Find the replacement for a given atom. Atoms in _replacedAtoms
259 // may be chained, so find the last one.
260 for (;;) {
261 AtomToAtom::iterator pos = _replacedAtoms.find(atom);
262 if (pos == _replacedAtoms.end())
263 return atom;
264 atom = pos->second;
265 }
266 }
267
isCoalescedAway(const Atom * atom)268 bool SymbolTable::isCoalescedAway(const Atom *atom) {
269 return _replacedAtoms.count(atom) > 0;
270 }
271
undefines()272 std::vector<const UndefinedAtom *> SymbolTable::undefines() {
273 std::vector<const UndefinedAtom *> ret;
274 for (auto it : _nameTable) {
275 const Atom *atom = it.second;
276 assert(atom != nullptr);
277 if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
278 if (_replacedAtoms.count(undef) == 0)
279 ret.push_back(undef);
280 }
281 return ret;
282 }
283
284 } // namespace lld
285