1//===- LibraryResolver.cpp - Library Resolution of Unresolved Symbols ---===//
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// Library resolution impl for unresolved symbols
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ExecutionEngine/Orc/TargetProcess/LibraryResolver.h"
14#include "llvm/ExecutionEngine/Orc/TargetProcess/LibraryScanner.h"
15
16#include "llvm/Object/COFF.h"
17#include "llvm/Object/ELFObjectFile.h"
18#include "llvm/Object/ObjectFile.h"
19#include "llvm/Support/DJB.h"
20#include "llvm/Support/Error.h"
21
22#define DEBUG_TYPE "orc-resolver"
23
24namespace llvm::orc {
25
26LibraryResolver::LibraryResolver(const LibraryResolver::Setup &S)
27 : LibMgr(LibraryManager()),
28 LibPathCache(std::make_shared<LibraryPathCache>()),
29 LibPathResolver(std::make_shared<PathResolver>(args&: LibPathCache)),
30 ScanHelper(S.BasePaths, LibPathCache, LibPathResolver),
31 FB(S.FilterBuilder),
32 ShouldScanCall(S.ShouldScanCall ? S.ShouldScanCall
33 : [](StringRef) -> bool { return true; }),
34 scanBatchSize(S.ScanBatchSize) {
35
36 if (!ScanHelper.hasSearchPath()) {
37 LLVM_DEBUG(dbgs() << "Warning: No base paths provided for scanning.\n");
38 }
39}
40
41std::unique_ptr<LibraryResolutionDriver>
42LibraryResolutionDriver::create(const LibraryResolver::Setup &S) {
43 auto LR = std::make_unique<LibraryResolver>(args: S);
44 return std::unique_ptr<LibraryResolutionDriver>(
45 new LibraryResolutionDriver(std::move(LR)));
46}
47
48void LibraryResolutionDriver::addScanPath(const std::string &Path, PathType K) {
49 LR->ScanHelper.addBasePath(P: Path, Kind: K);
50}
51
52void LibraryResolutionDriver::markLibraryLoaded(StringRef Path) {
53 LR->LibMgr.markLoaded(Path);
54}
55
56void LibraryResolutionDriver::markLibraryUnLoaded(StringRef Path) {
57 LR->LibMgr.markUnloaded(Path);
58}
59
60void LibraryResolutionDriver::resolveSymbols(
61 ArrayRef<StringRef> Symbols, LibraryResolver::OnSearchComplete OnCompletion,
62 const SearchConfig &Config) {
63 LR->searchSymbolsInLibraries(SymList: Symbols, OnComplete: std::move(OnCompletion), Config);
64}
65
66static bool shouldIgnoreSymbol(const object::SymbolRef &Sym,
67 uint32_t IgnoreFlags) {
68 Expected<uint32_t> FlagsOrErr = Sym.getFlags();
69 if (!FlagsOrErr) {
70 consumeError(Err: FlagsOrErr.takeError());
71 return true;
72 }
73
74 uint32_t Flags = *FlagsOrErr;
75
76 using Filter = SymbolEnumeratorOptions;
77 if ((IgnoreFlags & Filter::IgnoreUndefined) &&
78 (Flags & object::SymbolRef::SF_Undefined))
79 return true;
80 if ((IgnoreFlags & Filter::IgnoreNonExported) &&
81 !(Flags & object::SymbolRef::SF_Exported))
82 return true;
83 if ((IgnoreFlags & Filter::IgnoreNonGlobal) &&
84 !(Flags & object::SymbolRef::SF_Global))
85 return true;
86 if ((IgnoreFlags & Filter::IgnoreHidden) &&
87 (Flags & object::SymbolRef::SF_Hidden))
88 return true;
89 if ((IgnoreFlags & Filter::IgnoreIndirect) &&
90 (Flags & object::SymbolRef::SF_Indirect))
91 return true;
92 if ((IgnoreFlags & Filter::IgnoreWeak) &&
93 (Flags & object::SymbolRef::SF_Weak))
94 return true;
95
96 return false;
97}
98
99bool SymbolEnumerator::enumerateSymbols(object::ObjectFile *Obj,
100 OnEachSymbolFn OnEach,
101 const SymbolEnumeratorOptions &Opts) {
102 if (!Obj)
103 return false;
104
105 auto processSymbolRange =
106 [&](object::ObjectFile::symbol_iterator_range Range) -> EnumerateResult {
107 for (const auto &Sym : Range) {
108 if (shouldIgnoreSymbol(Sym, IgnoreFlags: Opts.FilterFlags))
109 continue;
110
111 auto NameOrErr = Sym.getName();
112 if (!NameOrErr) {
113 consumeError(Err: NameOrErr.takeError());
114 continue;
115 }
116
117 StringRef Name = *NameOrErr;
118 if (Name.empty())
119 continue;
120
121 EnumerateResult Res = OnEach(Name);
122 if (Res != EnumerateResult::Continue)
123 return Res;
124 }
125 return EnumerateResult::Continue;
126 };
127
128 EnumerateResult Res = processSymbolRange(Obj->symbols());
129 if (Res != EnumerateResult::Continue)
130 return Res == EnumerateResult::Stop;
131
132 if (Obj->isELF()) {
133 const auto *ElfObj = cast<object::ELFObjectFileBase>(Val: Obj);
134 Res = processSymbolRange(ElfObj->getDynamicSymbolIterators());
135 if (Res != EnumerateResult::Continue)
136 return Res == EnumerateResult::Stop;
137 } else if (Obj->isCOFF()) {
138 const auto *CoffObj = cast<object::COFFObjectFile>(Val: Obj);
139 for (auto I = CoffObj->export_directory_begin(),
140 E = CoffObj->export_directory_end();
141 I != E; ++I) {
142 StringRef Name;
143 if (I->getSymbolName(Result&: Name))
144 continue;
145 if (Name.empty())
146 continue;
147
148 EnumerateResult Res = OnEach(Name);
149 if (Res != EnumerateResult::Continue)
150 return Res == EnumerateResult::Stop;
151 }
152 } else if (Obj->isMachO()) {
153 }
154
155 return true;
156}
157
158bool SymbolEnumerator::enumerateSymbols(StringRef Path, OnEachSymbolFn OnEach,
159 const SymbolEnumeratorOptions &Opts) {
160 ObjectFileLoader ObjLoader(Path);
161
162 auto ObjOrErr = ObjLoader.getObjectFile();
163 if (!ObjOrErr) {
164 std::string ErrMsg;
165 handleAllErrors(E: ObjOrErr.takeError(),
166 Handlers: [&](const ErrorInfoBase &EIB) { ErrMsg = EIB.message(); });
167 LLVM_DEBUG(dbgs() << "Failed loading object file: " << Path
168 << "\nError: " << ErrMsg << "\n");
169 return false;
170 }
171
172 return SymbolEnumerator::enumerateSymbols(Obj: &ObjOrErr.get(), OnEach, Opts);
173}
174
175static StringRef GetGnuHashSection(llvm::object::ObjectFile *file) {
176 for (auto S : file->sections()) {
177 StringRef name = llvm::cantFail(ValOrErr: S.getName());
178 if (name == ".gnu.hash") {
179 return llvm::cantFail(ValOrErr: S.getContents());
180 }
181 }
182 return "";
183}
184
185/// Bloom filter is a stochastic data structure which can tell us if a symbol
186/// name does not exist in a library with 100% certainty. If it tells us it
187/// exists this may not be true:
188/// https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2
189///
190/// ELF has this optimization in the new linkers by default, It is stored in the
191/// gnu.hash section of the object file.
192///
193///\returns true if the symbol may be in the library.
194static bool MayExistInElfObjectFile(llvm::object::ObjectFile *soFile,
195 StringRef Sym) {
196 assert(soFile->isELF() && "Not ELF");
197
198 uint32_t hash = djbHash(Buffer: Sym);
199 // Compute the platform bitness -- either 64 or 32.
200 const unsigned bits = 8 * soFile->getBytesInAddress();
201
202 StringRef contents = GetGnuHashSection(file: soFile);
203 if (contents.size() < 16)
204 // We need to search if the library doesn't have .gnu.hash section!
205 return true;
206 const char *hashContent = contents.data();
207
208 // See https://flapenguin.me/2017/05/10/elf-lookup-dt-gnu-hash/ for .gnu.hash
209 // table layout.
210 uint32_t maskWords = *reinterpret_cast<const uint32_t *>(hashContent + 8);
211 uint32_t shift2 = *reinterpret_cast<const uint32_t *>(hashContent + 12);
212 uint32_t hash2 = hash >> shift2;
213 uint32_t n = (hash / bits) % maskWords;
214
215 const char *bloomfilter = hashContent + 16;
216 const char *hash_pos = bloomfilter + n * (bits / 8); // * (Bits / 8)
217 uint64_t word = *reinterpret_cast<const uint64_t *>(hash_pos);
218 uint64_t bitmask = ((1ULL << (hash % bits)) | (1ULL << (hash2 % bits)));
219 return (bitmask & word) == bitmask;
220}
221
222void LibraryResolver::resolveSymbolsInLibrary(
223 LibraryInfo *Lib, SymbolQuery &Query, const SymbolEnumeratorOptions &Opts) {
224 LLVM_DEBUG(dbgs() << "Checking unresolved symbols "
225 << " in library : " << Lib->getFileName() << "\n";);
226
227 if (!Query.hasUnresolved()) {
228 LLVM_DEBUG(dbgs() << "Skipping library: " << Lib->getFullPath()
229 << " — unresolved symbols exist.\n";);
230 return;
231 }
232
233 bool HadAnySym = false;
234
235 // Build candidate vector
236 SmallVector<StringRef, 24> CandidateVec;
237
238 Query.getUnresolvedSymbols(Unresolved&: CandidateVec, Allow: [&](StringRef S) {
239 return !Lib->hasFilter() || Lib->mayContain(Symbol: S);
240 });
241
242 LLVM_DEBUG(dbgs() << "Total candidate symbols : " << CandidateVec.size()
243 << "\n";);
244 if (CandidateVec.empty()) {
245 LLVM_DEBUG(dbgs() << "No symbol Exist "
246 " in library: "
247 << Lib->getFullPath() << "\n";);
248 return;
249 }
250
251 bool BuildingFilter = !Lib->hasFilter();
252
253 ObjectFileLoader ObjLoader(Lib->getFullPath());
254 auto ObjOrErr = ObjLoader.getObjectFile();
255 if (!ObjOrErr) {
256 std::string ErrMsg;
257 handleAllErrors(E: ObjOrErr.takeError(),
258 Handlers: [&](const ErrorInfoBase &EIB) { ErrMsg = EIB.message(); });
259 LLVM_DEBUG(dbgs() << "Failed loading object file: " << Lib->getFullPath()
260 << "\nError: " << ErrMsg << "\n");
261 return;
262 }
263
264 object::ObjectFile *Obj = &ObjOrErr.get();
265 if (BuildingFilter && Obj->isELF()) {
266
267 erase_if(C&: CandidateVec,
268 P: [&](StringRef C) { return !MayExistInElfObjectFile(soFile: Obj, Sym: C); });
269 if (CandidateVec.empty())
270 return;
271 }
272
273 SmallVector<StringRef, 256> SymbolVec;
274
275 LLVM_DEBUG(dbgs() << "Enumerating symbols in library: " << Lib->getFullPath()
276 << "\n";);
277
278 SymbolEnumerator::enumerateSymbols(
279 Obj,
280 OnEach: [&](StringRef S) {
281 // Collect symbols if we're building a filter
282 if (BuildingFilter)
283 SymbolVec.push_back(Elt: S);
284
285 // auto It = std::lower_bound(CandidateVec.begin(),
286 // CandidateVec.end(), S);
287 auto It = std::find(first: CandidateVec.begin(), last: CandidateVec.end(), val: S);
288 if (It != CandidateVec.end() && *It == S) {
289 // Resolve and remove from CandidateVec
290 LLVM_DEBUG(dbgs() << "Symbol '" << S << "' resolved in library: "
291 << Lib->getFullPath() << "\n";);
292 Query.resolve(Sym: S, LibPath: Lib->getFullPath());
293 HadAnySym = true;
294 *It = CandidateVec.back();
295 CandidateVec.pop_back();
296
297 // Stop — if nothing remains, stop enumeration
298 if (!BuildingFilter && CandidateVec.empty()) {
299 return EnumerateResult::Stop;
300 }
301 // Also stop if SymbolQuery has no more unresolved symbols
302 if (!BuildingFilter && !Query.hasUnresolved())
303 return EnumerateResult::Stop;
304 }
305
306 return EnumerateResult::Continue;
307 },
308 Opts);
309
310 if (BuildingFilter) {
311 LLVM_DEBUG(dbgs() << "Building filter for library: " << Lib->getFullPath()
312 << "\n";);
313 if (SymbolVec.empty()) {
314 LLVM_DEBUG(dbgs() << " Skip : No symbols found in : "
315 << Lib->getFullPath() << "\n";);
316 return;
317 }
318
319 Lib->ensureFilterBuilt(FB, Symbols: SymbolVec);
320 LLVM_DEBUG({
321 dbgs() << "DiscoveredSymbols : " << SymbolVec.size() << "\n";
322 for (const auto &S : SymbolVec)
323 dbgs() << "DiscoveredSymbols : " << S << "\n";
324 });
325 }
326
327 if (HadAnySym && Lib->getState() != LibState::Loaded)
328 Lib->setState(LibState::Queried);
329}
330
331void LibraryResolver::searchSymbolsInLibraries(ArrayRef<StringRef> SymbolList,
332 OnSearchComplete OnComplete,
333 const SearchConfig &Config) {
334 SymbolQuery Q(SymbolList);
335
336 using LibraryType = PathType;
337 auto tryResolveFrom = [&](LibState S, LibraryType K) {
338 LLVM_DEBUG(dbgs() << "Trying resolve from state=" << static_cast<int>(S)
339 << " type=" << static_cast<int>(K) << "\n";);
340
341 LibraryCursor Cur = LibMgr.getCursor(K, S);
342 while (!Q.allResolved()) {
343 const LibraryInfo *Lib = Cur.nextValidLib();
344 // Cursor not valid?
345 if (!Lib) {
346 if (!scanForNewLibraries(K, Cur))
347 break; // nothing new was added
348 continue; // Try to resolve next library
349 }
350
351 // can use Async here?
352 resolveSymbolsInLibrary(Lib: const_cast<LibraryInfo *>(Lib), Query&: Q,
353 Opts: Config.Options);
354 if (Q.allResolved())
355 break;
356 }
357 };
358
359 for (const auto &[St, Ty] : Config.Policy.Plan) {
360 tryResolveFrom(St, Ty);
361 if (Q.allResolved())
362 break;
363 }
364
365 // done:
366 LLVM_DEBUG({
367 dbgs() << "Search complete.\n";
368 for (const auto &r : Q.getAllResults())
369 dbgs() << "Resolved Symbol:" << r->Name << " -> " << r->ResolvedLibPath
370 << "\n";
371 });
372
373 OnComplete(Q);
374}
375
376bool LibraryResolver::scanForNewLibraries(PathType K, LibraryCursor &Cur) {
377 while (ScanHelper.leftToScan(K)) {
378 scanLibrariesIfNeeded(K, BatchSize: scanBatchSize);
379
380 // Check if scanning added new libraries
381 if (Cur.hasMoreValidLib())
382 return true;
383 }
384
385 // No new libraries were added
386 return false;
387}
388
389bool LibraryResolver::scanLibrariesIfNeeded(PathType PK, size_t BatchSize) {
390 LLVM_DEBUG(dbgs() << "LibraryResolver::scanLibrariesIfNeeded: Scanning for "
391 << (PK == PathType::User ? "User" : "System")
392 << " libraries\n";);
393 if (!ScanHelper.leftToScan(K: PK))
394 return false;
395
396 LibraryScanner Scanner(ScanHelper, LibMgr, ShouldScanCall);
397 Scanner.scanNext(Kind: PK, batchSize: BatchSize);
398 return true;
399}
400} // end namespace llvm::orc
401