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 "Config.h"
11 #include "InputFiles.h"
12 #include "Symbols.h"
13 #include "lld/Common/ErrorHandler.h"
14 #include "lld/Common/Memory.h"
15 
16 using namespace llvm;
17 using namespace lld;
18 using namespace lld::macho;
19 
20 Symbol *SymbolTable::find(CachedHashStringRef cachedName) {
21   auto it = symMap.find(cachedName);
22   if (it == symMap.end())
23     return nullptr;
24   return symVector[it->second];
25 }
26 
27 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
28                                               const InputFile *file) {
29   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
30 
31   Symbol *sym;
32   if (!p.second) {
33     // Name already present in the symbol table.
34     sym = symVector[p.first->second];
35   } else {
36     // Name is a new symbol.
37     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
38     symVector.push_back(sym);
39   }
40 
41   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
42   return {sym, p.second};
43 }
44 
45 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
46                                  InputSection *isec, uint64_t value,
47                                  uint64_t size, bool isWeakDef,
48                                  bool isPrivateExtern, bool isThumb,
49                                  bool isReferencedDynamically) {
50   Symbol *s;
51   bool wasInserted;
52   bool overridesWeakDef = false;
53   std::tie(s, wasInserted) = insert(name, file);
54 
55   assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
56          (isa<ObjFile>(file) && file == isec->file));
57 
58   if (!wasInserted) {
59     if (auto *defined = dyn_cast<Defined>(s)) {
60       if (isWeakDef) {
61         if (defined->isWeakDef()) {
62           // Both old and new symbol weak (e.g. inline function in two TUs):
63           // If one of them isn't private extern, the merged symbol isn't.
64           defined->privateExtern &= isPrivateExtern;
65           defined->referencedDynamically |= isReferencedDynamically;
66 
67           // FIXME: Handle this for bitcode files.
68           // FIXME: We currently only do this if both symbols are weak.
69           //        We could do this if either is weak (but getting the
70           //        case where !isWeakDef && defined->isWeakDef() right
71           //        requires some care and testing).
72           if (isec)
73             isec->canOmitFromOutput = true;
74         }
75 
76         return defined;
77       }
78       if (!defined->isWeakDef())
79         error("duplicate symbol: " + name + "\n>>> defined in " +
80               toString(defined->getFile()) + "\n>>> defined in " +
81               toString(file));
82     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
83       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
84     }
85     // Defined symbols take priority over other types of symbols, so in case
86     // of a name conflict, we fall through to the replaceSymbol() call below.
87   }
88 
89   Defined *defined = replaceSymbol<Defined>(
90       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
91       isPrivateExtern, isThumb, isReferencedDynamically);
92   defined->overridesWeakDef = overridesWeakDef;
93   return defined;
94 }
95 
96 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
97                                   bool isWeakRef) {
98   Symbol *s;
99   bool wasInserted;
100   std::tie(s, wasInserted) = insert(name, file);
101 
102   RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;
103 
104   if (wasInserted)
105     replaceSymbol<Undefined>(s, name, file, refState);
106   else if (auto *lazy = dyn_cast<LazySymbol>(s))
107     lazy->fetchArchiveMember();
108   else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
109     dynsym->refState = std::max(dynsym->refState, refState);
110   else if (auto *undefined = dyn_cast<Undefined>(s))
111     undefined->refState = std::max(undefined->refState, refState);
112   return s;
113 }
114 
115 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
116                                uint32_t align, bool isPrivateExtern) {
117   Symbol *s;
118   bool wasInserted;
119   std::tie(s, wasInserted) = insert(name, file);
120 
121   if (!wasInserted) {
122     if (auto *common = dyn_cast<CommonSymbol>(s)) {
123       if (size < common->size)
124         return s;
125     } else if (isa<Defined>(s)) {
126       return s;
127     }
128     // Common symbols take priority over all non-Defined symbols, so in case of
129     // a name conflict, we fall through to the replaceSymbol() call below.
130   }
131 
132   replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
133   return s;
134 }
135 
136 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
137                               bool isTlv) {
138   Symbol *s;
139   bool wasInserted;
140   std::tie(s, wasInserted) = insert(name, file);
141 
142   RefState refState = RefState::Unreferenced;
143   if (!wasInserted) {
144     if (auto *defined = dyn_cast<Defined>(s)) {
145       if (isWeakDef && !defined->isWeakDef())
146         defined->overridesWeakDef = true;
147     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
148       refState = undefined->refState;
149     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
150       refState = dysym->refState;
151     }
152   }
153 
154   bool isDynamicLookup = file == nullptr;
155   if (wasInserted || isa<Undefined>(s) ||
156       (isa<DylibSymbol>(s) &&
157        ((!isWeakDef && s->isWeakDef()) ||
158         (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup()))))
159     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
160 
161   return s;
162 }
163 
164 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
165   return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
166 }
167 
168 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
169                              const object::Archive::Symbol &sym) {
170   Symbol *s;
171   bool wasInserted;
172   std::tie(s, wasInserted) = insert(name, file);
173 
174   if (wasInserted)
175     replaceSymbol<LazySymbol>(s, file, sym);
176   else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
177     file->fetch(sym);
178   return s;
179 }
180 
181 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
182                                    uint64_t value, bool isPrivateExtern,
183                                    bool includeInSymtab,
184                                    bool referencedDynamically) {
185   Defined *s = addDefined(name, nullptr, isec, value, /*size=*/0,
186                           /*isWeakDef=*/false, isPrivateExtern,
187                           /*isThumb=*/false, referencedDynamically);
188   s->includeInSymtab = includeInSymtab;
189   return s;
190 }
191 
192 void lld::macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
193   auto message = [source, &sym]() {
194     std::string message = "undefined symbol: " + toString(sym);
195     if (!source.empty())
196       message += "\n>>> referenced by " + source.str();
197     else
198       message += "\n>>> referenced by " + toString(sym.getFile());
199     return message;
200   };
201   switch (config->undefinedSymbolTreatment) {
202   case UndefinedSymbolTreatment::error:
203     error(message());
204     break;
205   case UndefinedSymbolTreatment::warning:
206     warn(message());
207     LLVM_FALLTHROUGH;
208   case UndefinedSymbolTreatment::dynamic_lookup:
209   case UndefinedSymbolTreatment::suppress:
210     symtab->addDynamicLookup(sym.getName());
211     break;
212   case UndefinedSymbolTreatment::unknown:
213     llvm_unreachable("unknown -undefined TREATMENT");
214   }
215 }
216 
217 SymbolTable *macho::symtab;
218