1 //===- SymbolTable.cpp ----------------------------------------------------===//
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 "SymbolTable.h"
10 #include "ConcatOutputSection.h"
11 #include "Config.h"
12 #include "InputFiles.h"
13 #include "Symbols.h"
14 #include "SyntheticSections.h"
15 #include "lld/Common/ErrorHandler.h"
16 #include "lld/Common/Memory.h"
17 
18 using namespace llvm;
19 using namespace lld;
20 using namespace lld::macho;
21 
22 Symbol *SymbolTable::find(CachedHashStringRef cachedName) {
23   auto it = symMap.find(cachedName);
24   if (it == symMap.end())
25     return nullptr;
26   return symVector[it->second];
27 }
28 
29 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
30                                               const InputFile *file) {
31   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
32 
33   Symbol *sym;
34   if (!p.second) {
35     // Name already present in the symbol table.
36     sym = symVector[p.first->second];
37   } else {
38     // Name is a new symbol.
39     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
40     symVector.push_back(sym);
41   }
42 
43   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
44   return {sym, p.second};
45 }
46 
47 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
48                                  InputSection *isec, uint64_t value,
49                                  uint64_t size, bool isWeakDef,
50                                  bool isPrivateExtern, bool isThumb,
51                                  bool isReferencedDynamically,
52                                  bool noDeadStrip) {
53   Symbol *s;
54   bool wasInserted;
55   bool overridesWeakDef = false;
56   std::tie(s, wasInserted) = insert(name, file);
57 
58   assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
59          (isa<ObjFile>(file) && file == isec->getFile()));
60 
61   if (!wasInserted) {
62     if (auto *defined = dyn_cast<Defined>(s)) {
63       if (isWeakDef) {
64         if (defined->isWeakDef()) {
65           // Both old and new symbol weak (e.g. inline function in two TUs):
66           // If one of them isn't private extern, the merged symbol isn't.
67           defined->privateExtern &= isPrivateExtern;
68           defined->referencedDynamically |= isReferencedDynamically;
69           defined->noDeadStrip |= noDeadStrip;
70 
71           // FIXME: Handle this for bitcode files.
72           // FIXME: We currently only do this if both symbols are weak.
73           //        We could do this if either is weak (but getting the
74           //        case where !isWeakDef && defined->isWeakDef() right
75           //        requires some care and testing).
76           if (auto concatIsec = dyn_cast_or_null<ConcatInputSection>(isec))
77             concatIsec->wasCoalesced = true;
78         }
79 
80         return defined;
81       }
82       if (!defined->isWeakDef())
83         error("duplicate symbol: " + name + "\n>>> defined in " +
84               toString(defined->getFile()) + "\n>>> defined in " +
85               toString(file));
86     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
87       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
88       dysym->unreference();
89     }
90     // Defined symbols take priority over other types of symbols, so in case
91     // of a name conflict, we fall through to the replaceSymbol() call below.
92   }
93 
94   Defined *defined = replaceSymbol<Defined>(
95       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
96       isPrivateExtern, isThumb, isReferencedDynamically, noDeadStrip);
97   defined->overridesWeakDef = overridesWeakDef;
98   return defined;
99 }
100 
101 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
102                                   bool isWeakRef) {
103   Symbol *s;
104   bool wasInserted;
105   std::tie(s, wasInserted) = insert(name, file);
106 
107   RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;
108 
109   if (wasInserted)
110     replaceSymbol<Undefined>(s, name, file, refState);
111   else if (auto *lazy = dyn_cast<LazySymbol>(s))
112     lazy->fetchArchiveMember();
113   else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
114     dynsym->reference(refState);
115   else if (auto *undefined = dyn_cast<Undefined>(s))
116     undefined->refState = std::max(undefined->refState, refState);
117   return s;
118 }
119 
120 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
121                                uint32_t align, bool isPrivateExtern) {
122   Symbol *s;
123   bool wasInserted;
124   std::tie(s, wasInserted) = insert(name, file);
125 
126   if (!wasInserted) {
127     if (auto *common = dyn_cast<CommonSymbol>(s)) {
128       if (size < common->size)
129         return s;
130     } else if (isa<Defined>(s)) {
131       return s;
132     }
133     // Common symbols take priority over all non-Defined symbols, so in case of
134     // a name conflict, we fall through to the replaceSymbol() call below.
135   }
136 
137   replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
138   return s;
139 }
140 
141 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
142                               bool isTlv) {
143   Symbol *s;
144   bool wasInserted;
145   std::tie(s, wasInserted) = insert(name, file);
146 
147   RefState refState = RefState::Unreferenced;
148   if (!wasInserted) {
149     if (auto *defined = dyn_cast<Defined>(s)) {
150       if (isWeakDef && !defined->isWeakDef())
151         defined->overridesWeakDef = true;
152     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
153       refState = undefined->refState;
154     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
155       refState = dysym->getRefState();
156     }
157   }
158 
159   bool isDynamicLookup = file == nullptr;
160   if (wasInserted || isa<Undefined>(s) ||
161       (isa<DylibSymbol>(s) &&
162        ((!isWeakDef && s->isWeakDef()) ||
163         (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup())))) {
164     if (auto *dynsym = dyn_cast<DylibSymbol>(s))
165       dynsym->unreference();
166     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
167   }
168 
169   return s;
170 }
171 
172 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
173   return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
174 }
175 
176 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
177                              const object::Archive::Symbol &sym) {
178   Symbol *s;
179   bool wasInserted;
180   std::tie(s, wasInserted) = insert(name, file);
181 
182   if (wasInserted)
183     replaceSymbol<LazySymbol>(s, file, sym);
184   else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
185     file->fetch(sym);
186   return s;
187 }
188 
189 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
190                                    uint64_t value, bool isPrivateExtern,
191                                    bool includeInSymtab,
192                                    bool referencedDynamically) {
193   Defined *s = addDefined(name, nullptr, isec, value, /*size=*/0,
194                           /*isWeakDef=*/false, isPrivateExtern,
195                           /*isThumb=*/false, referencedDynamically,
196                           /*noDeadStrip=*/false);
197   s->includeInSymtab = includeInSymtab;
198   return s;
199 }
200 
201 enum class Boundary {
202   Start,
203   End,
204 };
205 
206 static Defined *createBoundarySymbol(const Undefined &sym) {
207   return symtab->addSynthetic(
208       sym.getName(), /*isec=*/nullptr, /*value=*/-1, /*isPrivateExtern=*/true,
209       /*includeInSymtab=*/false, /*referencedDynamically=*/false);
210 }
211 
212 static void handleSectionBoundarySymbol(const Undefined &sym, StringRef segSect,
213                                         Boundary which) {
214   StringRef segName, sectName;
215   std::tie(segName, sectName) = segSect.split('$');
216 
217   // Attach the symbol to any InputSection that will end up in the right
218   // OutputSection -- it doesn't matter which one we pick.
219   // Don't bother looking through inputSections for a matching
220   // ConcatInputSection -- we need to create ConcatInputSection for
221   // non-existing sections anyways, and that codepath works even if we should
222   // already have a ConcatInputSection with the right name.
223 
224   OutputSection *osec = nullptr;
225   // This looks for __TEXT,__cstring etc.
226   for (SyntheticSection *ssec : syntheticSections)
227     if (ssec->segname == segName && ssec->name == sectName) {
228       osec = ssec->isec->parent;
229       break;
230     }
231 
232   if (!osec) {
233     ConcatInputSection *isec = make<ConcatInputSection>(segName, sectName);
234 
235     // This runs after markLive() and is only called for Undefineds that are
236     // live. Marking the isec live ensures an OutputSection is created that the
237     // start/end symbol can refer to.
238     assert(sym.isLive());
239     isec->live = true;
240 
241     // This runs after gatherInputSections(), so need to explicitly set parent
242     // and add to inputSections.
243     osec = isec->parent = ConcatOutputSection::getOrCreateForInput(isec);
244     inputSections.push_back(isec);
245   }
246 
247   if (which == Boundary::Start)
248     osec->sectionStartSymbols.push_back(createBoundarySymbol(sym));
249   else
250     osec->sectionEndSymbols.push_back(createBoundarySymbol(sym));
251 }
252 
253 static void handleSegmentBoundarySymbol(const Undefined &sym, StringRef segName,
254                                         Boundary which) {
255   OutputSegment *seg = getOrCreateOutputSegment(segName);
256   if (which == Boundary::Start)
257     seg->segmentStartSymbols.push_back(createBoundarySymbol(sym));
258   else
259     seg->segmentEndSymbols.push_back(createBoundarySymbol(sym));
260 }
261 
262 void lld::macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
263   // Handle start/end symbols.
264   StringRef name = sym.getName();
265   if (name.consume_front("section$start$"))
266     return handleSectionBoundarySymbol(sym, name, Boundary::Start);
267   if (name.consume_front("section$end$"))
268     return handleSectionBoundarySymbol(sym, name, Boundary::End);
269   if (name.consume_front("segment$start$"))
270     return handleSegmentBoundarySymbol(sym, name, Boundary::Start);
271   if (name.consume_front("segment$end$"))
272     return handleSegmentBoundarySymbol(sym, name, Boundary::End);
273 
274   // Handle -U.
275   if (config->explicitDynamicLookups.count(sym.getName())) {
276     symtab->addDynamicLookup(sym.getName());
277     return;
278   }
279 
280   // Handle -undefined.
281   auto message = [source, &sym]() {
282     std::string message = "undefined symbol";
283     if (config->archMultiple)
284       message += (" for arch " + getArchitectureName(config->arch())).str();
285     message += ": " + toString(sym);
286     if (!source.empty())
287       message += "\n>>> referenced by " + source.str();
288     else
289       message += "\n>>> referenced by " + toString(sym.getFile());
290     return message;
291   };
292   switch (config->undefinedSymbolTreatment) {
293   case UndefinedSymbolTreatment::error:
294     error(message());
295     break;
296   case UndefinedSymbolTreatment::warning:
297     warn(message());
298     LLVM_FALLTHROUGH;
299   case UndefinedSymbolTreatment::dynamic_lookup:
300   case UndefinedSymbolTreatment::suppress:
301     symtab->addDynamicLookup(sym.getName());
302     break;
303   case UndefinedSymbolTreatment::unknown:
304     llvm_unreachable("unknown -undefined TREATMENT");
305   }
306 }
307 
308 SymbolTable *macho::symtab;
309