1//===- SanitizerBinaryMetadata.cpp - binary analysis sanitizers metadata --===//
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// This file is a part of SanitizerBinaryMetadata.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Instrumentation/SanitizerBinaryMetadata.h"
14#include "InstrumentationOptions.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/StringExtras.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/ADT/Twine.h"
21#include "llvm/Analysis/CaptureTracking.h"
22#include "llvm/Analysis/TargetLibraryInfo.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/IR/Constant.h"
25#include "llvm/IR/DerivedTypes.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/GlobalValue.h"
28#include "llvm/IR/GlobalVariable.h"
29#include "llvm/IR/IRBuilder.h"
30#include "llvm/IR/Instruction.h"
31#include "llvm/IR/Instructions.h"
32#include "llvm/IR/LLVMContext.h"
33#include "llvm/IR/MDBuilder.h"
34#include "llvm/IR/Metadata.h"
35#include "llvm/IR/Module.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/Value.h"
38#include "llvm/ProfileData/InstrProf.h"
39#include "llvm/Support/Allocator.h"
40#include "llvm/Support/SpecialCaseList.h"
41#include "llvm/Support/StringSaver.h"
42#include "llvm/Support/VirtualFileSystem.h"
43#include "llvm/TargetParser/Triple.h"
44#include "llvm/Transforms/Utils/ModuleUtils.h"
45
46#include <array>
47#include <cstdint>
48#include <memory>
49
50using namespace llvm;
51
52#define DEBUG_TYPE "sanmd"
53
54namespace {
55
56//===--- Constants --------------------------------------------------------===//
57
58constexpr uint32_t kVersionBase = 2; // occupies lower 16 bits
59constexpr uint32_t kVersionPtrSizeRel = (1u << 16); // offsets are pointer-sized
60constexpr int kCtorDtorPriority = 2;
61
62// Pairs of names of initialization callback functions and which section
63// contains the relevant metadata.
64class MetadataInfo {
65public:
66 const StringRef FunctionPrefix;
67 const StringRef SectionSuffix;
68
69 static const MetadataInfo Covered;
70 static const MetadataInfo Atomics;
71
72private:
73 // Forbid construction elsewhere.
74 explicit constexpr MetadataInfo(StringRef FunctionPrefix,
75 StringRef SectionSuffix)
76 : FunctionPrefix(FunctionPrefix), SectionSuffix(SectionSuffix) {}
77};
78const MetadataInfo MetadataInfo::Covered{
79 "__sanitizer_metadata_covered", kSanitizerBinaryMetadataCoveredSection};
80const MetadataInfo MetadataInfo::Atomics{
81 "__sanitizer_metadata_atomics", kSanitizerBinaryMetadataAtomicsSection};
82
83// The only instances of MetadataInfo are the constants above, so a set of
84// them may simply store pointers to them. To deterministically generate code,
85// we need to use a set with stable iteration order, such as SetVector.
86using MetadataInfoSet = SetVector<const MetadataInfo *>;
87
88//===--- Statistics -------------------------------------------------------===//
89
90STATISTIC(NumMetadataCovered, "Metadata attached to covered functions");
91STATISTIC(NumMetadataAtomics, "Metadata attached to atomics");
92STATISTIC(NumMetadataUAR, "Metadata attached to UAR functions");
93
94//===----------------------------------------------------------------------===//
95
96// Apply opt overrides.
97SanitizerBinaryMetadataOptions &&
98transformOptionsFromCl(const InstrumentationOptions &CLOpts,
99 SanitizerBinaryMetadataOptions &&Opts) {
100 Opts.Covered |= CLOpts.sanitizer_metadata_covered;
101 Opts.Atomics |= CLOpts.sanitizer_metadata_atomics;
102 Opts.UAR |= CLOpts.sanitizer_metadata_uar;
103 return std::move(Opts);
104}
105
106class SanitizerBinaryMetadata {
107public:
108 SanitizerBinaryMetadata(const InstrumentationOptions &CLOpts, Module &M,
109 SanitizerBinaryMetadataOptions Opts,
110 std::unique_ptr<SpecialCaseList> Ignorelist)
111 : CLOpts(CLOpts), Mod(M),
112 Options(transformOptionsFromCl(CLOpts, Opts: std::move(Opts))),
113 Ignorelist(std::move(Ignorelist)), TargetTriple(M.getTargetTriple()),
114 VersionStr(utostr(X: getVersion())), IRB(M) {
115 // FIXME: Make it work with other formats.
116 assert(TargetTriple.isOSBinFormatELF() && "ELF only");
117 assert(!TargetTriple.isGPU() && "Device targets are not supported");
118 }
119
120 bool run();
121
122private:
123 uint32_t getVersion() const {
124 uint32_t Version = kVersionBase;
125 const auto CM = Mod.getCodeModel();
126 if (CM.has_value() && (*CM == CodeModel::Medium || *CM == CodeModel::Large))
127 Version |= kVersionPtrSizeRel;
128 return Version;
129 }
130
131 void runOn(Function &F, MetadataInfoSet &MIS);
132
133 // Determines which set of metadata to collect for this instruction.
134 //
135 // Returns true if covered metadata is required to unambiguously interpret
136 // other metadata. For example, if we are interested in atomics metadata, any
137 // function with memory operations (atomic or not) requires covered metadata
138 // to determine if a memory operation is atomic or not in modules compiled
139 // with SanitizerBinaryMetadata.
140 bool runOn(Instruction &I, MetadataInfoSet &MIS, MDBuilder &MDB,
141 uint64_t &FeatureMask);
142
143 // Get start/end section marker pointer.
144 GlobalVariable *getSectionMarker(const Twine &MarkerName, Type *Ty);
145
146 // Returns the target-dependent section name.
147 StringRef getSectionName(StringRef SectionSuffix);
148
149 // Returns the section start marker name.
150 StringRef getSectionStart(StringRef SectionSuffix);
151
152 // Returns the section end marker name.
153 StringRef getSectionEnd(StringRef SectionSuffix);
154
155 // Returns true if the access to the address should be considered "atomic".
156 bool pretendAtomicAccess(const Value *Addr);
157
158 const InstrumentationOptions &CLOpts;
159 Module &Mod;
160 const SanitizerBinaryMetadataOptions Options;
161 std::unique_ptr<SpecialCaseList> Ignorelist;
162 const Triple TargetTriple;
163 const std::string VersionStr;
164 IRBuilder<> IRB;
165 BumpPtrAllocator Alloc;
166 UniqueStringSaver StringPool{Alloc};
167};
168
169bool SanitizerBinaryMetadata::run() {
170 MetadataInfoSet MIS;
171
172 for (Function &F : Mod)
173 runOn(F, MIS);
174
175 if (MIS.empty())
176 return false;
177
178 //
179 // Setup constructors and call all initialization functions for requested
180 // metadata features.
181 //
182
183 auto *PtrTy = IRB.getPtrTy();
184 auto *Int32Ty = IRB.getInt32Ty();
185 const std::array<Type *, 3> InitTypes = {Int32Ty, PtrTy, PtrTy};
186 auto *Version = ConstantInt::get(Ty: Int32Ty, V: getVersion());
187
188 for (const MetadataInfo *MI : MIS) {
189 const std::array<Value *, InitTypes.size()> InitArgs = {
190 Version,
191 getSectionMarker(MarkerName: getSectionStart(SectionSuffix: MI->SectionSuffix), Ty: PtrTy),
192 getSectionMarker(MarkerName: getSectionEnd(SectionSuffix: MI->SectionSuffix), Ty: PtrTy),
193 };
194
195 // Calls to the initialization functions with different versions cannot be
196 // merged. Give the structors unique names based on the version, which will
197 // also be used as the COMDAT key.
198 const std::string StructorPrefix = (MI->FunctionPrefix + VersionStr).str();
199
200 // We declare the _add and _del functions as weak, and only call them if
201 // there is a valid symbol linked. This allows building binaries with
202 // semantic metadata, but without having callbacks. When a tool that wants
203 // the metadata is linked which provides the callbacks, they will be called.
204 auto [Ctor, CtorInitFn] = createSanitizerCtorAndInitFunctions(
205 M&: Mod, CtorName: StructorPrefix + ".module_ctor",
206 InitName: (MI->FunctionPrefix + "_add").str(), InitArgTypes: InitTypes, InitArgs,
207 /*VersionCheckName=*/StringRef(),
208 /*Weak=*/CLOpts.sanitizer_metadata_weak_callbacks);
209 auto [Dtor, DtorInitFn] = createSanitizerCtorAndInitFunctions(
210 M&: Mod, CtorName: StructorPrefix + ".module_dtor",
211 InitName: (MI->FunctionPrefix + "_del").str(), InitArgTypes: InitTypes, InitArgs,
212 /*VersionCheckName=*/StringRef(),
213 /*Weak=*/CLOpts.sanitizer_metadata_weak_callbacks);
214 const Attribute::AttrKind ExtAttr =
215 TargetLibraryInfo::getExtAttrForI32Param(T: TargetTriple,
216 /*Signed=*/false);
217 if (ExtAttr != Attribute::None)
218 for (FunctionCallee InitFn : {CtorInitFn, DtorInitFn})
219 cast<Function>(Val: InitFn.getCallee())->addParamAttr(ArgNo: 0, Kind: ExtAttr);
220 Constant *CtorComdatKey = nullptr;
221 Constant *DtorComdatKey = nullptr;
222 if (TargetTriple.supportsCOMDAT()) {
223 // Use COMDAT to deduplicate constructor/destructor function. The COMDAT
224 // key needs to be a non-local linkage.
225 Ctor->setComdat(Mod.getOrInsertComdat(Name: Ctor->getName()));
226 Dtor->setComdat(Mod.getOrInsertComdat(Name: Dtor->getName()));
227 Ctor->setLinkage(GlobalValue::ExternalLinkage);
228 Dtor->setLinkage(GlobalValue::ExternalLinkage);
229 // DSOs should _not_ call another constructor/destructor!
230 Ctor->setVisibility(GlobalValue::HiddenVisibility);
231 Dtor->setVisibility(GlobalValue::HiddenVisibility);
232 CtorComdatKey = Ctor;
233 DtorComdatKey = Dtor;
234 }
235 appendToGlobalCtors(M&: Mod, F: Ctor, Priority: kCtorDtorPriority, Data: CtorComdatKey);
236 appendToGlobalDtors(M&: Mod, F: Dtor, Priority: kCtorDtorPriority, Data: DtorComdatKey);
237 }
238
239 return true;
240}
241
242void SanitizerBinaryMetadata::runOn(Function &F, MetadataInfoSet &MIS) {
243 if (F.empty())
244 return;
245 // Do not apply any instrumentation for naked functions.
246 if (F.hasFnAttribute(Kind: Attribute::Naked))
247 return;
248 if (F.hasFnAttribute(Kind: Attribute::DisableSanitizerInstrumentation))
249 return;
250 if (Ignorelist && Ignorelist->inSection(Section: "metadata", Prefix: "fun", Query: F.getName()))
251 return;
252 // Don't touch available_externally functions, their actual body is elsewhere.
253 if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage)
254 return;
255
256 MDBuilder MDB(F.getContext());
257
258 // The metadata features enabled for this function, stored along covered
259 // metadata (if enabled).
260 uint64_t FeatureMask = 0;
261 // Don't emit unnecessary covered metadata for all functions to save space.
262 bool RequiresCovered = false;
263
264 if (Options.Atomics || Options.UAR) {
265 for (BasicBlock &BB : F)
266 for (Instruction &I : BB)
267 RequiresCovered |= runOn(I, MIS, MDB, FeatureMask);
268 }
269
270 if (CLOpts.sanitizer_metadata_nosanitize_attr &&
271 F.hasFnAttribute(Kind: "no_sanitize_thread"))
272 FeatureMask &= ~kSanitizerBinaryMetadataAtomics;
273 if (F.isVarArg())
274 FeatureMask &= ~kSanitizerBinaryMetadataUAR;
275 if (FeatureMask & kSanitizerBinaryMetadataUAR) {
276 RequiresCovered = true;
277 NumMetadataUAR++;
278 }
279
280 // Covered metadata is always emitted if explicitly requested, otherwise only
281 // if some other metadata requires it to unambiguously interpret it for
282 // modules compiled with SanitizerBinaryMetadata.
283 if (Options.Covered || (FeatureMask && RequiresCovered)) {
284 NumMetadataCovered++;
285 const auto *MI = &MetadataInfo::Covered;
286 MIS.insert(X: MI);
287 const StringRef Section = getSectionName(SectionSuffix: MI->SectionSuffix);
288 // The feature mask will be placed after the function size.
289 Constant *CFM = IRB.getInt64(C: FeatureMask);
290 F.setMetadata(KindID: LLVMContext::MD_pcsections,
291 Node: MDB.createPCSections(Sections: {{Section, {CFM}}}));
292 }
293}
294
295bool isUARSafeCall(CallInst *CI) {
296 auto *F = CI->getCalledFunction();
297 // There are no intrinsic functions that leak arguments.
298 // If the called function does not return, the current function
299 // does not return as well, so no possibility of use-after-return.
300 // Sanitizer function also don't leak or don't return.
301 // It's safe to both pass pointers to local variables to them
302 // and to tail-call them.
303 return F && (F->isIntrinsic() || F->doesNotReturn() ||
304 F->getName().starts_with(Prefix: "__asan_") ||
305 F->getName().starts_with(Prefix: "__hwsan_") ||
306 F->getName().starts_with(Prefix: "__ubsan_") ||
307 F->getName().starts_with(Prefix: "__msan_") ||
308 F->getName().starts_with(Prefix: "__tsan_"));
309}
310
311bool hasUseAfterReturnUnsafeUses(Value &V) {
312 for (User *U : V.users()) {
313 if (auto *I = dyn_cast<Instruction>(Val: U)) {
314 if (I->isLifetimeStartOrEnd() || I->isDroppable())
315 continue;
316 if (auto *CI = dyn_cast<CallInst>(Val: U)) {
317 if (isUARSafeCall(CI))
318 continue;
319 }
320 if (isa<LoadInst>(Val: U))
321 continue;
322 if (auto *SI = dyn_cast<StoreInst>(Val: U)) {
323 // If storing TO the alloca, then the address isn't taken.
324 if (SI->getOperand(i_nocapture: 1) == &V)
325 continue;
326 }
327 if (auto *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) {
328 if (!hasUseAfterReturnUnsafeUses(V&: *GEPI))
329 continue;
330 } else if (auto *BCI = dyn_cast<BitCastInst>(Val: U)) {
331 if (!hasUseAfterReturnUnsafeUses(V&: *BCI))
332 continue;
333 }
334 }
335 return true;
336 }
337 return false;
338}
339
340bool useAfterReturnUnsafe(Instruction &I) {
341 if (isa<AllocaInst>(Val: I))
342 return hasUseAfterReturnUnsafeUses(V&: I);
343 // Tail-called functions are not necessary intercepted
344 // at runtime because there is no call instruction.
345 // So conservatively mark the caller as requiring checking.
346 else if (auto *CI = dyn_cast<CallInst>(Val: &I))
347 return CI->isTailCall() && !isUARSafeCall(CI);
348 return false;
349}
350
351bool SanitizerBinaryMetadata::pretendAtomicAccess(const Value *Addr) {
352 if (!Addr)
353 return false;
354
355 Addr = Addr->stripInBoundsOffsets();
356 auto *GV = dyn_cast<GlobalVariable>(Val: Addr);
357 if (!GV)
358 return false;
359
360 // Some compiler-generated accesses are known racy, to avoid false positives
361 // in data-race analysis pretend they're atomic.
362 if (GV->hasSection()) {
363 const auto OF = Mod.getTargetTriple().getObjectFormat();
364 const auto ProfSec =
365 getInstrProfSectionName(IPSK: IPSK_cnts, OF, /*AddSegmentInfo=*/false);
366 if (GV->getSection().ends_with(Suffix: ProfSec))
367 return true;
368 }
369 if (GV->getName().starts_with(Prefix: "__llvm_gcov") ||
370 GV->getName().starts_with(Prefix: "__llvm_gcda"))
371 return true;
372
373 return false;
374}
375
376// Returns true if the memory at `Addr` may be shared with other threads.
377bool maybeSharedMutable(const Value *Addr) {
378 // By default assume memory may be shared.
379 if (!Addr)
380 return true;
381
382 const AllocaInst *AI = findAllocaForValue(V: Addr);
383 if (AI && !PointerMayBeCaptured(V: AI, /*ReturnCaptures=*/true))
384 return false; // Object is on stack but does not escape.
385
386 Addr = Addr->stripInBoundsOffsets();
387 if (auto *GV = dyn_cast<GlobalVariable>(Val: Addr)) {
388 if (GV->isConstant())
389 return false; // Shared, but not mutable.
390 }
391
392 return true;
393}
394
395bool SanitizerBinaryMetadata::runOn(Instruction &I, MetadataInfoSet &MIS,
396 MDBuilder &MDB, uint64_t &FeatureMask) {
397 SmallVector<const MetadataInfo *, 1> InstMetadata;
398 bool RequiresCovered = false;
399
400 // Only call if at least 1 type of metadata is requested.
401 assert(Options.UAR || Options.Atomics);
402
403 if (Options.UAR && !(FeatureMask & kSanitizerBinaryMetadataUAR)) {
404 if (useAfterReturnUnsafe(I))
405 FeatureMask |= kSanitizerBinaryMetadataUAR;
406 }
407
408 if (Options.Atomics) {
409 const Value *Addr = nullptr;
410 if (auto *SI = dyn_cast<StoreInst>(Val: &I))
411 Addr = SI->getPointerOperand();
412 else if (auto *LI = dyn_cast<LoadInst>(Val: &I))
413 Addr = LI->getPointerOperand();
414
415 if (I.mayReadOrWriteMemory() && maybeSharedMutable(Addr)) {
416 auto SSID = getAtomicSyncScopeID(I: &I);
417 if ((SSID.has_value() && *SSID != SyncScope::SingleThread) ||
418 pretendAtomicAccess(Addr)) {
419 NumMetadataAtomics++;
420 InstMetadata.push_back(Elt: &MetadataInfo::Atomics);
421 }
422 FeatureMask |= kSanitizerBinaryMetadataAtomics;
423 RequiresCovered = true;
424 }
425 }
426
427 // Attach MD_pcsections to instruction.
428 if (!InstMetadata.empty()) {
429 MIS.insert_range(R&: InstMetadata);
430 SmallVector<MDBuilder::PCSection, 1> Sections;
431 for (const auto &MI : InstMetadata)
432 Sections.push_back(Elt: {getSectionName(SectionSuffix: MI->SectionSuffix), {}});
433 I.setMetadata(KindID: LLVMContext::MD_pcsections, Node: MDB.createPCSections(Sections));
434 }
435
436 return RequiresCovered;
437}
438
439GlobalVariable *
440SanitizerBinaryMetadata::getSectionMarker(const Twine &MarkerName, Type *Ty) {
441 // Use ExternalWeak so that if all sections are discarded due to section
442 // garbage collection, the linker will not report undefined symbol errors.
443 auto *Marker = new GlobalVariable(Mod, Ty, /*isConstant=*/false,
444 GlobalVariable::ExternalWeakLinkage,
445 /*Initializer=*/nullptr, MarkerName);
446 Marker->setVisibility(GlobalValue::HiddenVisibility);
447 return Marker;
448}
449
450StringRef SanitizerBinaryMetadata::getSectionName(StringRef SectionSuffix) {
451 // FIXME: Other TargetTriples.
452 // Request ULEB128 encoding for all integer constants.
453 return StringPool.save(S: SectionSuffix + VersionStr + "!C");
454}
455
456StringRef SanitizerBinaryMetadata::getSectionStart(StringRef SectionSuffix) {
457 // Twine only concatenates 2 strings; with >2 strings, concatenating them
458 // creates Twine temporaries, and returning the final Twine no longer works
459 // because we'd end up with a stack-use-after-return. So here we also use the
460 // StringPool to store the new string.
461 return StringPool.save(S: "__start_" + SectionSuffix + VersionStr);
462}
463
464StringRef SanitizerBinaryMetadata::getSectionEnd(StringRef SectionSuffix) {
465 return StringPool.save(S: "__stop_" + SectionSuffix + VersionStr);
466}
467
468} // namespace
469
470SanitizerBinaryMetadataPass::SanitizerBinaryMetadataPass(
471 SanitizerBinaryMetadataOptions Opts,
472 IntrusiveRefCntPtr<vfs::FileSystem> VFS,
473 ArrayRef<std::string> IgnorelistFiles)
474 : Options(std::move(Opts)),
475 VFS(VFS ? std::move(VFS) : vfs::getRealFileSystem()),
476 IgnorelistFiles(std::move(IgnorelistFiles)) {}
477
478PreservedAnalyses
479SanitizerBinaryMetadataPass::run(Module &M, AnalysisManager<Module> &AM) {
480 std::unique_ptr<SpecialCaseList> Ignorelist;
481 if (!IgnorelistFiles.empty()) {
482 Ignorelist = SpecialCaseList::createOrDie(Paths: IgnorelistFiles, FS&: *VFS);
483 if (Ignorelist->inSection(Section: "metadata", Prefix: "src", Query: M.getSourceFileName()))
484 return PreservedAnalyses::all();
485 }
486
487 const InstrumentationOptions &CLOpts =
488 M.getContext().getLibraryOptions().get<InstrumentationOptions>();
489 SanitizerBinaryMetadata Pass(CLOpts, M, Options, std::move(Ignorelist));
490 if (Pass.run())
491 return PreservedAnalyses::none();
492 return PreservedAnalyses::all();
493}
494