1//===----- TypeSanitizer.cpp - type-based-aliasing-violation detector -----===//
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 TypeSanitizer, a type-based-aliasing-violation
10// detector.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Instrumentation/TypeSanitizer.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/Analysis/MemoryLocation.h"
20#include "llvm/Analysis/TargetLibraryInfo.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/InstIterator.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/IntrinsicInst.h"
27#include "llvm/IR/Intrinsics.h"
28#include "llvm/IR/LLVMContext.h"
29#include "llvm/IR/MDBuilder.h"
30#include "llvm/IR/Metadata.h"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/Type.h"
33#include "llvm/ProfileData/InstrProf.h"
34#include "llvm/Support/CommandLine.h"
35#include "llvm/Support/MD5.h"
36#include "llvm/Support/Regex.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38#include "llvm/Transforms/Utils/Local.h"
39#include "llvm/Transforms/Utils/ModuleUtils.h"
40
41#include <cctype>
42
43using namespace llvm;
44
45#define DEBUG_TYPE "tysan"
46
47static const char *const kTysanModuleCtorName = "tysan.module_ctor";
48static const char *const kTysanInitName = "__tysan_init";
49static const char *const kTysanCheckName = "__tysan_check";
50static const char *const kTysanGVNamePrefix = "__tysan_v1_";
51
52static const char *const kTysanShadowMemoryAddress =
53 "__tysan_shadow_memory_address";
54static const char *const kTysanAppMemMask = "__tysan_app_memory_mask";
55
56static cl::opt<bool>
57 ClWritesAlwaysSetType("tysan-writes-always-set-type",
58 cl::desc("Writes always set the type"), cl::Hidden,
59 cl::init(Val: false));
60
61static cl::opt<bool> ClOutlineInstrumentation(
62 "tysan-outline-instrumentation",
63 cl::desc("Uses function calls for all TySan instrumentation, reducing "
64 "ELF size"),
65 cl::Hidden, cl::init(Val: true));
66
67static cl::opt<bool> ClVerifyOutlinedInstrumentation(
68 "tysan-verify-outlined-instrumentation",
69 cl::desc("Check types twice with both inlined instrumentation and "
70 "function calls. This verifies that they behave the same."),
71 cl::Hidden, cl::init(Val: false));
72
73STATISTIC(NumInstrumentedAccesses, "Number of instrumented accesses");
74
75namespace {
76
77/// TypeSanitizer: instrument the code in module to find type-based aliasing
78/// violations.
79struct TypeSanitizer {
80 TypeSanitizer(Module &M);
81 bool sanitizeFunction(Function &F, const TargetLibraryInfo &TLI);
82 void instrumentGlobals(Module &M);
83
84private:
85 typedef SmallDenseMap<const MDNode *, GlobalVariable *, 8>
86 TypeDescriptorsMapTy;
87 typedef SmallDenseMap<const MDNode *, std::string, 8> TypeNameMapTy;
88
89 void initializeCallbacks(Module &M);
90
91 Instruction *getShadowBase(Function &F);
92 Instruction *getAppMemMask(Function &F);
93
94 bool instrumentWithShadowUpdate(IRBuilder<> &IRB, const MDNode *TBAAMD,
95 Value *Ptr, uint64_t AccessSize, bool IsRead,
96 bool IsWrite, Value *ShadowBase,
97 Value *AppMemMask, bool ForceSetType,
98 bool SanitizeFunction,
99 TypeDescriptorsMapTy &TypeDescriptors,
100 const DataLayout &DL);
101
102 /// Memory-related intrinsics/instructions reset the type of the destination
103 /// memory (including allocas and byval arguments).
104 bool instrumentMemInst(Value *I, Instruction *ShadowBase,
105 Instruction *AppMemMask, const DataLayout &DL);
106
107 std::string getAnonymousStructIdentifier(const MDNode *MD,
108 TypeNameMapTy &TypeNames);
109 bool generateTypeDescriptor(const MDNode *MD,
110 TypeDescriptorsMapTy &TypeDescriptors,
111 TypeNameMapTy &TypeNames, Module &M);
112 bool generateBaseTypeDescriptor(const MDNode *MD,
113 TypeDescriptorsMapTy &TypeDescriptors,
114 TypeNameMapTy &TypeNames, Module &M);
115
116 const Triple TargetTriple;
117 Regex AnonNameRegex;
118 Type *IntptrTy;
119 uint64_t PtrShift;
120 IntegerType *OrdTy, *U64Ty;
121
122 /// Callbacks to run-time library are computed in initializeCallbacks.
123 FunctionCallee TysanCheck;
124 FunctionCallee TysanCtorFunction;
125
126 FunctionCallee TysanIntrumentMemInst;
127 FunctionCallee TysanInstrumentWithShadowUpdate;
128 FunctionCallee TysanSetShadowType;
129
130 /// Callback to set types for gloabls.
131 Function *TysanGlobalsSetTypeFunction;
132};
133} // namespace
134
135TypeSanitizer::TypeSanitizer(Module &M)
136 : TargetTriple(M.getTargetTriple()),
137 AnonNameRegex("^_ZTS.*N[1-9][0-9]*_GLOBAL__N") {
138 const DataLayout &DL = M.getDataLayout();
139 IntptrTy = DL.getIntPtrType(C&: M.getContext());
140 PtrShift = countr_zero(Val: IntptrTy->getPrimitiveSizeInBits() / 8);
141
142 TysanGlobalsSetTypeFunction = M.getFunction(Name: "__tysan_set_globals_types");
143 initializeCallbacks(M);
144}
145
146void TypeSanitizer::initializeCallbacks(Module &M) {
147 LLVMContext &C = M.getContext();
148 IRBuilder<> IRB(M);
149 OrdTy = IRB.getInt32Ty();
150 U64Ty = IRB.getInt64Ty();
151 Type *BoolType = IRB.getInt1Ty();
152
153 AttributeList Attr;
154 Attr = Attr.addFnAttribute(C, Kind: Attribute::NoUnwind);
155 Attribute::AttrKind SExtAttr =
156 TargetLibraryInfo::getExtAttrForI32Param(T: TargetTriple, /*Signed=*/true);
157 Attribute::AttrKind BoolExtAttr =
158 TargetLibraryInfo::getExtAttrForBoolParam(T: TargetTriple);
159
160 // Initialize the callbacks. TODO: use TLI/emitLibFunc() for these functions.
161 TysanCheck =
162 M.getOrInsertFunction(Name: kTysanCheckName,
163 AttributeList: Attr.maybeAddParamAttribute(C, ArgNo: 1, Kind: SExtAttr)
164 .maybeAddParamAttribute(C, ArgNo: 3, Kind: SExtAttr),
165 RetTy: IRB.getVoidTy(),
166 Args: IRB.getPtrTy(), // Pointer to data to be read.
167 Args: OrdTy, // Size of the data in bytes.
168 Args: IRB.getPtrTy(), // Pointer to type descriptor.
169 Args: OrdTy // Flags.
170 );
171
172 TysanCtorFunction =
173 M.getOrInsertFunction(Name: kTysanModuleCtorName, AttributeList: Attr, RetTy: IRB.getVoidTy());
174
175 TysanIntrumentMemInst = M.getOrInsertFunction(
176 Name: "__tysan_instrument_mem_inst",
177 AttributeList: Attr.maybeAddParamAttribute(C, ArgNo: 3, Kind: BoolExtAttr), RetTy: IRB.getVoidTy(),
178 Args: IRB.getPtrTy(), // Pointer of data to be written to
179 Args: IRB.getPtrTy(), // Pointer of data to write
180 Args: U64Ty, // Size of the data in bytes
181 Args: BoolType // Do we need to call memmove
182 );
183
184 TysanInstrumentWithShadowUpdate =
185 M.getOrInsertFunction(Name: "__tysan_instrument_with_shadow_update",
186 AttributeList: Attr.maybeAddParamAttribute(C, ArgNo: 2, Kind: BoolExtAttr)
187 .maybeAddParamAttribute(C, ArgNo: 4, Kind: SExtAttr),
188 RetTy: IRB.getVoidTy(),
189 Args: IRB.getPtrTy(), // Pointer to data to be read
190 Args: IRB.getPtrTy(), // Pointer to type descriptor
191 Args: BoolType, // Do we need to type check this
192 Args: U64Ty, // Size of data we access in bytes
193 Args: OrdTy // Flags
194 );
195
196 TysanSetShadowType = M.getOrInsertFunction(
197 Name: "__tysan_set_shadow_type", AttributeList: Attr, RetTy: IRB.getVoidTy(),
198 Args: IRB.getPtrTy(), // Pointer of data to be written to
199 Args: IRB.getPtrTy(), // Pointer to the new type descriptor
200 Args: U64Ty // Size of data we access in bytes
201 );
202}
203
204void TypeSanitizer::instrumentGlobals(Module &M) {
205 TysanGlobalsSetTypeFunction = nullptr;
206
207 NamedMDNode *Globals = M.getNamedMetadata(Name: "llvm.tysan.globals");
208 if (!Globals)
209 return;
210
211 TysanGlobalsSetTypeFunction = Function::Create(
212 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), isVarArg: false),
213 Linkage: GlobalValue::InternalLinkage, N: "__tysan_set_globals_types", M: &M);
214 BasicBlock *BB =
215 BasicBlock::Create(Context&: M.getContext(), Name: "", Parent: TysanGlobalsSetTypeFunction);
216 ReturnInst::Create(C&: M.getContext(), InsertAtEnd: BB);
217
218 const DataLayout &DL = M.getDataLayout();
219 Value *ShadowBase = getShadowBase(F&: *TysanGlobalsSetTypeFunction);
220 Value *AppMemMask = getAppMemMask(F&: *TysanGlobalsSetTypeFunction);
221 TypeDescriptorsMapTy TypeDescriptors;
222 TypeNameMapTy TypeNames;
223
224 for (const auto &GMD : Globals->operands()) {
225 auto *GV = mdconst::dyn_extract_or_null<GlobalVariable>(MD: GMD->getOperand(I: 0));
226 if (!GV)
227 continue;
228 const MDNode *TBAAMD = cast<MDNode>(Val: GMD->getOperand(I: 1));
229 if (!generateBaseTypeDescriptor(MD: TBAAMD, TypeDescriptors, TypeNames, M))
230 continue;
231
232 IRBuilder<> IRB(
233 TysanGlobalsSetTypeFunction->getEntryBlock().getTerminator());
234 Type *AccessTy = GV->getValueType();
235 assert(AccessTy->isSized());
236 uint64_t AccessSize = DL.getTypeStoreSize(Ty: AccessTy);
237 instrumentWithShadowUpdate(IRB, TBAAMD, Ptr: GV, AccessSize, IsRead: false, IsWrite: false,
238 ShadowBase, AppMemMask, ForceSetType: true, SanitizeFunction: false,
239 TypeDescriptors, DL);
240 }
241
242 if (TysanGlobalsSetTypeFunction) {
243 IRBuilder<> IRB(cast<Function>(Val: TysanCtorFunction.getCallee())
244 ->getEntryBlock()
245 .getTerminator());
246 IRB.CreateCall(Callee: TysanGlobalsSetTypeFunction, Args: {});
247 }
248}
249
250static const char LUT[] = "0123456789abcdef";
251
252static std::string encodeName(StringRef Name) {
253 size_t Length = Name.size();
254 std::string Output = kTysanGVNamePrefix;
255 Output.reserve(res_arg: Output.size() + 3 * Length);
256 for (size_t i = 0; i < Length; ++i) {
257 const unsigned char c = Name[i];
258 if (isalnum(c)) {
259 Output.push_back(c: c);
260 continue;
261 }
262
263 if (c == '_') {
264 Output.append(s: "__");
265 continue;
266 }
267
268 Output.push_back(c: '_');
269 Output.push_back(c: LUT[c >> 4]);
270 Output.push_back(c: LUT[c & 15]);
271 }
272
273 return Output;
274}
275
276std::string
277TypeSanitizer::getAnonymousStructIdentifier(const MDNode *MD,
278 TypeNameMapTy &TypeNames) {
279 MD5 Hash;
280
281 for (int i = 1, e = MD->getNumOperands(); i < e; i += 2) {
282 const MDNode *MemberNode = dyn_cast<MDNode>(Val: MD->getOperand(I: i));
283 if (!MemberNode)
284 return "";
285
286 auto TNI = TypeNames.find(Val: MemberNode);
287 std::string MemberName;
288 if (TNI != TypeNames.end()) {
289 MemberName = TNI->second;
290 } else {
291 if (MemberNode->getNumOperands() < 1)
292 return "";
293 MDString *MemberNameNode = dyn_cast<MDString>(Val: MemberNode->getOperand(I: 0));
294 if (!MemberNameNode)
295 return "";
296 MemberName = MemberNameNode->getString().str();
297 if (MemberName.empty())
298 MemberName = getAnonymousStructIdentifier(MD: MemberNode, TypeNames);
299 if (MemberName.empty())
300 return "";
301 TypeNames[MemberNode] = MemberName;
302 }
303
304 Hash.update(Str: MemberName);
305 Hash.update(Str: "\0");
306
307 uint64_t Offset =
308 mdconst::extract<ConstantInt>(MD: MD->getOperand(I: i + 1))->getZExtValue();
309 Hash.update(Str: utostr(X: Offset));
310 Hash.update(Str: "\0");
311 }
312
313 MD5::MD5Result HashResult;
314 Hash.final(Result&: HashResult);
315 return "__anonymous_" + std::string(HashResult.digest().str());
316}
317
318bool TypeSanitizer::generateBaseTypeDescriptor(
319 const MDNode *MD, TypeDescriptorsMapTy &TypeDescriptors,
320 TypeNameMapTy &TypeNames, Module &M) {
321 if (MD->getNumOperands() < 1)
322 return false;
323
324 MDString *NameNode = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
325 if (!NameNode)
326 return false;
327
328 std::string Name = NameNode->getString().str();
329 if (Name.empty())
330 Name = getAnonymousStructIdentifier(MD, TypeNames);
331 if (Name.empty())
332 return false;
333 TypeNames[MD] = Name;
334 std::string EncodedName = encodeName(Name);
335
336 GlobalVariable *GV =
337 dyn_cast_or_null<GlobalVariable>(Val: M.getNamedValue(Name: EncodedName));
338 if (GV) {
339 TypeDescriptors[MD] = GV;
340 return true;
341 }
342
343 SmallVector<std::pair<Constant *, uint64_t>> Members;
344 for (int i = 1, e = MD->getNumOperands(); i < e; i += 2) {
345 const MDNode *MemberNode = dyn_cast<MDNode>(Val: MD->getOperand(I: i));
346 if (!MemberNode)
347 return false;
348
349 Constant *Member;
350 auto TDI = TypeDescriptors.find(Val: MemberNode);
351 if (TDI != TypeDescriptors.end()) {
352 Member = TDI->second;
353 } else {
354 if (!generateBaseTypeDescriptor(MD: MemberNode, TypeDescriptors, TypeNames,
355 M))
356 return false;
357
358 Member = TypeDescriptors[MemberNode];
359 }
360
361 uint64_t Offset;
362 if ((unsigned)i + 1 < MD->getNumOperands()) {
363 Offset =
364 mdconst::extract<ConstantInt>(MD: MD->getOperand(I: i + 1))->getZExtValue();
365 } else {
366 assert(i == 1 && MD->getNumOperands() == 2 && "Malformed TBAA MD.");
367 // The third operand for a scalar tag is actually optional, its absence
368 // indicating an offset of zero.
369 Offset = 0;
370 }
371
372 Members.push_back(Elt: std::make_pair(x&: Member, y&: Offset));
373 }
374
375 // The descriptor for a scalar is:
376 // [2, member count, [type pointer, offset]..., name]
377
378 LLVMContext &C = MD->getContext();
379 Constant *NameData = ConstantDataArray::getString(Context&: C, Initializer: NameNode->getString());
380 SmallVector<Type *> TDSubTys;
381 SmallVector<Constant *> TDSubData;
382
383 auto PushTDSub = [&](Constant *C) {
384 TDSubTys.push_back(Elt: C->getType());
385 TDSubData.push_back(Elt: C);
386 };
387
388 PushTDSub(ConstantInt::get(Ty: IntptrTy, V: 2));
389 PushTDSub(ConstantInt::get(Ty: IntptrTy, V: Members.size()));
390
391 // Types that are in an anonymous namespace are local to this module.
392 // FIXME: This should really be marked by the frontend in the metadata
393 // instead of having us guess this from the mangled name. Moreover, the regex
394 // here can pick up (unlikely) names in the non-reserved namespace (because
395 // it needs to search into the type to pick up cases where the type in the
396 // anonymous namespace is a template parameter, etc.).
397 bool ShouldBeComdat = !AnonNameRegex.match(String: NameNode->getString());
398 for (auto &Member : Members) {
399 PushTDSub(Member.first);
400 PushTDSub(ConstantInt::get(Ty: IntptrTy, V: Member.second));
401 }
402
403 PushTDSub(NameData);
404
405 StructType *TDTy = StructType::get(Context&: C, Elements: TDSubTys);
406 Constant *TD = ConstantStruct::get(T: TDTy, V: TDSubData);
407
408 GlobalVariable *TDGV =
409 new GlobalVariable(TDTy, true,
410 !ShouldBeComdat ? GlobalValue::InternalLinkage
411 : GlobalValue::LinkOnceODRLinkage,
412 TD, EncodedName);
413 M.insertGlobalVariable(GV: TDGV);
414
415 if (ShouldBeComdat) {
416 if (TargetTriple.isOSBinFormatELF()) {
417 Comdat *TDComdat = M.getOrInsertComdat(Name: EncodedName);
418 TDGV->setComdat(TDComdat);
419 }
420 appendToUsed(M, Values: TDGV);
421 }
422
423 TypeDescriptors[MD] = TDGV;
424 return true;
425}
426
427bool TypeSanitizer::generateTypeDescriptor(
428 const MDNode *MD, TypeDescriptorsMapTy &TypeDescriptors,
429 TypeNameMapTy &TypeNames, Module &M) {
430 // Here we need to generate a type descriptor corresponding to this TBAA
431 // metadata node. Under the current scheme there are three kinds of TBAA
432 // metadata nodes: scalar nodes, struct nodes, and struct tag nodes.
433
434 if (MD->getNumOperands() < 3)
435 return false;
436
437 const MDNode *BaseNode = dyn_cast<MDNode>(Val: MD->getOperand(I: 0));
438 if (!BaseNode)
439 return false;
440
441 // This is a struct tag (element-access) node.
442
443 const MDNode *AccessNode = dyn_cast<MDNode>(Val: MD->getOperand(I: 1));
444 if (!AccessNode)
445 return false;
446
447 Constant *Base;
448 auto TDI = TypeDescriptors.find(Val: BaseNode);
449 if (TDI != TypeDescriptors.end()) {
450 Base = TDI->second;
451 } else {
452 if (!generateBaseTypeDescriptor(MD: BaseNode, TypeDescriptors, TypeNames, M))
453 return false;
454
455 Base = TypeDescriptors[BaseNode];
456 }
457
458 Constant *Access;
459 TDI = TypeDescriptors.find(Val: AccessNode);
460 if (TDI != TypeDescriptors.end()) {
461 Access = TDI->second;
462 } else {
463 if (!generateBaseTypeDescriptor(MD: AccessNode, TypeDescriptors, TypeNames, M))
464 return false;
465
466 Access = TypeDescriptors[AccessNode];
467 }
468
469 uint64_t Offset =
470 mdconst::extract<ConstantInt>(MD: MD->getOperand(I: 2))->getZExtValue();
471 std::string EncodedName =
472 std::string(Base->getName()) + "_o_" + utostr(X: Offset);
473
474 GlobalVariable *GV =
475 dyn_cast_or_null<GlobalVariable>(Val: M.getNamedValue(Name: EncodedName));
476 if (GV) {
477 TypeDescriptors[MD] = GV;
478 return true;
479 }
480
481 // The descriptor for a scalar is:
482 // [1, base-type pointer, access-type pointer, offset]
483
484 StructType *TDTy =
485 StructType::get(elt1: IntptrTy, elts: Base->getType(), elts: Access->getType(), elts: IntptrTy);
486 Constant *TD =
487 ConstantStruct::get(T: TDTy, Vs: ConstantInt::get(Ty: IntptrTy, V: 1), Vs: Base, Vs: Access,
488 Vs: ConstantInt::get(Ty: IntptrTy, V: Offset));
489
490 bool ShouldBeComdat = cast<GlobalVariable>(Val: Base)->getLinkage() ==
491 GlobalValue::LinkOnceODRLinkage;
492
493 GlobalVariable *TDGV =
494 new GlobalVariable(TDTy, true,
495 !ShouldBeComdat ? GlobalValue::InternalLinkage
496 : GlobalValue::LinkOnceODRLinkage,
497 TD, EncodedName);
498 M.insertGlobalVariable(GV: TDGV);
499
500 if (ShouldBeComdat) {
501 if (TargetTriple.isOSBinFormatELF()) {
502 Comdat *TDComdat = M.getOrInsertComdat(Name: EncodedName);
503 TDGV->setComdat(TDComdat);
504 }
505 appendToUsed(M, Values: TDGV);
506 }
507
508 TypeDescriptors[MD] = TDGV;
509 return true;
510}
511
512Instruction *TypeSanitizer::getShadowBase(Function &F) {
513 IRBuilder<> IRB(&F.front().front());
514 Constant *GlobalShadowAddress =
515 F.getParent()->getOrInsertGlobal(Name: kTysanShadowMemoryAddress, Ty: IntptrTy);
516 return IRB.CreateLoad(Ty: IntptrTy, Ptr: GlobalShadowAddress, Name: "shadow.base");
517}
518
519Instruction *TypeSanitizer::getAppMemMask(Function &F) {
520 IRBuilder<> IRB(&F.front().front());
521 Value *GlobalAppMemMask =
522 F.getParent()->getOrInsertGlobal(Name: kTysanAppMemMask, Ty: IntptrTy);
523 return IRB.CreateLoad(Ty: IntptrTy, Ptr: GlobalAppMemMask, Name: "app.mem.mask");
524}
525
526/// Collect all loads and stores, and for what TBAA nodes we need to generate
527/// type descriptors.
528void collectMemAccessInfo(
529 Function &F, const TargetLibraryInfo &TLI,
530 SmallVectorImpl<std::pair<Instruction *, MemoryLocation>> &MemoryAccesses,
531 SmallSetVector<const MDNode *, 8> &TBAAMetadata,
532 SmallVectorImpl<Value *> &MemTypeResetInsts) {
533 // Traverse all instructions, collect loads/stores/returns, check for calls.
534 for (Instruction &Inst : instructions(F)) {
535 // Skip memory accesses inserted by another instrumentation.
536 if (Inst.getMetadata(KindID: LLVMContext::MD_nosanitize))
537 continue;
538
539 if (isa<LoadInst>(Val: Inst) || isa<StoreInst>(Val: Inst) ||
540 isa<AtomicCmpXchgInst>(Val: Inst) || isa<AtomicRMWInst>(Val: Inst)) {
541 MemoryLocation MLoc = MemoryLocation::get(Inst: &Inst);
542
543 // Swift errors are special (we can't introduce extra uses on them).
544 if (MLoc.Ptr->isSwiftError())
545 continue;
546
547 // Skip non-address-space-0 pointers; we don't know how to handle them.
548 Type *PtrTy = cast<PointerType>(Val: MLoc.Ptr->getType());
549 if (PtrTy->getPointerAddressSpace() != 0)
550 continue;
551
552 if (MLoc.AATags.TBAA)
553 TBAAMetadata.insert(X: MLoc.AATags.TBAA);
554 MemoryAccesses.push_back(Elt: std::make_pair(x: &Inst, y&: MLoc));
555 } else if (isa<CallInst>(Val: Inst) || isa<InvokeInst>(Val: Inst)) {
556 if (CallInst *CI = dyn_cast<CallInst>(Val: &Inst))
557 maybeMarkSanitizerLibraryCallNoBuiltin(CI, TLI: &TLI);
558
559 if (isa<MemIntrinsic, LifetimeIntrinsic>(Val: Inst))
560 MemTypeResetInsts.push_back(Elt: &Inst);
561 } else if (isa<AllocaInst>(Val: Inst)) {
562 MemTypeResetInsts.push_back(Elt: &Inst);
563 }
564 }
565}
566
567bool TypeSanitizer::sanitizeFunction(Function &F,
568 const TargetLibraryInfo &TLI) {
569 if (F.isDeclaration())
570 return false;
571 // This is required to prevent instrumenting call to __tysan_init from within
572 // the module constructor.
573 if (&F == TysanCtorFunction.getCallee() || &F == TysanGlobalsSetTypeFunction)
574 return false;
575 initializeCallbacks(M&: *F.getParent());
576
577 // We need to collect all loads and stores, and know for what TBAA nodes we
578 // need to generate type descriptors.
579 SmallVector<std::pair<Instruction *, MemoryLocation>> MemoryAccesses;
580 SmallSetVector<const MDNode *, 8> TBAAMetadata;
581 SmallVector<Value *> MemTypeResetInsts;
582 collectMemAccessInfo(F, TLI, MemoryAccesses, TBAAMetadata, MemTypeResetInsts);
583
584 // byval arguments also need their types reset (they're new stack memory,
585 // just like allocas).
586 for (auto &A : F.args())
587 if (A.hasByValAttr())
588 MemTypeResetInsts.push_back(Elt: &A);
589
590 Module &M = *F.getParent();
591 TypeDescriptorsMapTy TypeDescriptors;
592 TypeNameMapTy TypeNames;
593 bool Res = false;
594 for (const MDNode *MD : TBAAMetadata) {
595 if (TypeDescriptors.count(Val: MD))
596 continue;
597
598 if (!generateTypeDescriptor(MD, TypeDescriptors, TypeNames, M))
599 return Res; // Giving up.
600
601 Res = true;
602 }
603
604 const DataLayout &DL = F.getDataLayout();
605 bool SanitizeFunction = F.hasFnAttribute(Kind: Attribute::SanitizeType);
606 bool NeedsInstrumentation =
607 MemTypeResetInsts.empty() && MemoryAccesses.empty();
608 Instruction *ShadowBase = NeedsInstrumentation ? nullptr : getShadowBase(F);
609 Instruction *AppMemMask = NeedsInstrumentation ? nullptr : getAppMemMask(F);
610 for (const auto &[I, MLoc] : MemoryAccesses) {
611 IRBuilder<> IRB(I);
612 assert(MLoc.Size.isPrecise());
613 if (instrumentWithShadowUpdate(
614 IRB, TBAAMD: MLoc.AATags.TBAA, Ptr: const_cast<Value *>(MLoc.Ptr),
615 AccessSize: MLoc.Size.getValue(), IsRead: I->mayReadFromMemory(), IsWrite: I->mayWriteToMemory(),
616 ShadowBase, AppMemMask, ForceSetType: false, SanitizeFunction, TypeDescriptors,
617 DL)) {
618 ++NumInstrumentedAccesses;
619 Res = true;
620 }
621 }
622
623 for (auto Inst : MemTypeResetInsts)
624 Res |= instrumentMemInst(I: Inst, ShadowBase, AppMemMask, DL);
625
626 return Res;
627}
628
629static Value *convertToShadowDataInt(IRBuilder<> &IRB, Value *Ptr,
630 Type *IntptrTy, uint64_t PtrShift,
631 Value *ShadowBase, Value *AppMemMask) {
632 return IRB.CreateAdd(
633 LHS: IRB.CreateShl(
634 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Ptr, DestTy: IntptrTy, Name: "app.ptr.int"),
635 RHS: AppMemMask, Name: "app.ptr.masked"),
636 RHS: PtrShift, Name: "app.ptr.shifted"),
637 RHS: ShadowBase, Name: "shadow.ptr.int");
638}
639
640bool TypeSanitizer::instrumentWithShadowUpdate(
641 IRBuilder<> &IRB, const MDNode *TBAAMD, Value *Ptr, uint64_t AccessSize,
642 bool IsRead, bool IsWrite, Value *ShadowBase, Value *AppMemMask,
643 bool ForceSetType, bool SanitizeFunction,
644 TypeDescriptorsMapTy &TypeDescriptors, const DataLayout &DL) {
645 Constant *TDGV;
646 if (TBAAMD)
647 TDGV = TypeDescriptors[TBAAMD];
648 else
649 TDGV = Constant::getNullValue(Ty: IRB.getPtrTy());
650
651 Value *TD = IRB.CreateBitCast(V: TDGV, DestTy: IRB.getPtrTy());
652
653 if (ClOutlineInstrumentation) {
654 if (!ForceSetType && (!ClWritesAlwaysSetType || IsRead)) {
655 // We need to check the type here. If the type is unknown, then the read
656 // sets the type. If the type is known, then it is checked. If the type
657 // doesn't match, then we call the runtime type check (which may yet
658 // determine that the mismatch is okay).
659
660 Constant *Flags =
661 ConstantInt::get(Ty: OrdTy, V: (int)IsRead | (((int)IsWrite) << 1));
662
663 IRB.CreateCall(Callee: TysanInstrumentWithShadowUpdate,
664 Args: {Ptr, TD,
665 SanitizeFunction ? IRB.getTrue() : IRB.getFalse(),
666 IRB.getInt64(C: AccessSize), Flags});
667 } else if (ForceSetType || IsWrite) {
668 // In the mode where writes always set the type, for a write (which does
669 // not also read), we just set the type.
670 IRB.CreateCall(Callee: TysanSetShadowType, Args: {Ptr, TD, IRB.getInt64(C: AccessSize)});
671 }
672
673 return true;
674 }
675
676 Value *ShadowDataInt = convertToShadowDataInt(IRB, Ptr, IntptrTy, PtrShift,
677 ShadowBase, AppMemMask);
678 Type *Int8PtrPtrTy = PointerType::get(C&: IRB.getContext(), AddressSpace: 0);
679 Value *ShadowData =
680 IRB.CreateIntToPtr(V: ShadowDataInt, DestTy: Int8PtrPtrTy, Name: "shadow.ptr");
681
682 auto SetType = [&]() {
683 IRB.CreateStore(Val: TD, Ptr: ShadowData);
684
685 // Now fill the remainder of the shadow memory corresponding to the
686 // remainder of the the bytes of the type with a bad type descriptor.
687 for (uint64_t i = 1; i < AccessSize; ++i) {
688 Value *BadShadowData = IRB.CreateIntToPtr(
689 V: IRB.CreateAdd(LHS: ShadowDataInt,
690 RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift),
691 Name: "shadow.byte." + Twine(i) + ".offset"),
692 DestTy: Int8PtrPtrTy, Name: "shadow.byte." + Twine(i) + ".ptr");
693
694 // This is the TD value, -i, which is used to indicate that the byte is
695 // i bytes after the first byte of the type.
696 Value *BadTD =
697 IRB.CreateIntToPtr(V: ConstantInt::getSigned(Ty: IntptrTy, V: -i),
698 DestTy: IRB.getPtrTy(), Name: "bad.descriptor" + Twine(i));
699 IRB.CreateStore(Val: BadTD, Ptr: BadShadowData);
700 }
701 };
702
703 if (ForceSetType || (ClWritesAlwaysSetType && IsWrite)) {
704 // In the mode where writes always set the type, for a write (which does
705 // not also read), we just set the type.
706 SetType();
707 return true;
708 }
709
710 assert((!ClWritesAlwaysSetType || IsRead) &&
711 "should have handled case above");
712 LLVMContext &C = IRB.getContext();
713 MDNode *UnlikelyBW = MDBuilder(C).createBranchWeights(TrueWeight: 1, FalseWeight: 100000);
714
715 if (!SanitizeFunction) {
716 // If we're not sanitizing this function, then we only care whether we
717 // need to *set* the type.
718 Value *LoadedTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: ShadowData, Name: "shadow.desc");
719 Value *NullTDCmp = IRB.CreateIsNull(Arg: LoadedTD, Name: "desc.set");
720 Instruction *NullTDTerm = SplitBlockAndInsertIfThen(
721 Cond: NullTDCmp, SplitBefore: &*IRB.GetInsertPoint(), Unreachable: false, BranchWeights: UnlikelyBW);
722 IRB.SetInsertPoint(NullTDTerm);
723 NullTDTerm->getParent()->setName("set.type");
724 SetType();
725 return true;
726 }
727 // We need to check the type here. If the type is unknown, then the read
728 // sets the type. If the type is known, then it is checked. If the type
729 // doesn't match, then we call the runtime (which may yet determine that
730 // the mismatch is okay).
731 //
732 // The checks generated below have the following structure.
733 //
734 // ; First we load the descriptor for the load from shadow memory and
735 // ; compare it against the type descriptor for the current access type.
736 // %shadow.desc = load ptr %shadow.data
737 // %bad.desc = icmp ne %shadow.desc, %td
738 // br %bad.desc, %bad.bb, %good.bb
739 //
740 // bad.bb:
741 // %shadow.desc.null = icmp eq %shadow.desc, null
742 // br %shadow.desc.null, %null.td.bb, %good.td.bb
743 //
744 // null.td.bb:
745 // ; The typ is unknown, set it if all bytes in the value are also unknown.
746 // ; To check, we load the shadow data for all bytes of the access. For the
747 // ; pseudo code below, assume an access of size 1.
748 // %shadow.data.int = add %shadow.data.int, 0
749 // %l = load (inttoptr %shadow.data.int)
750 // %is.not.null = icmp ne %l, null
751 // %not.all.unknown = %is.not.null
752 // br %no.all.unknown, before.set.type.bb
753 //
754 // before.set.type.bb:
755 // ; Call runtime to check mismatch.
756 // call void @__tysan_check()
757 // br %set.type.bb
758 //
759 // set.type.bb:
760 // ; Now fill the remainder of the shadow memory corresponding to the
761 // ; remainder of the the bytes of the type with a bad type descriptor.
762 // store %TD, %shadow.data
763 // br %continue.bb
764 //
765 // good.td.bb::
766 // ; We have a non-trivial mismatch. Call the runtime.
767 // call void @__tysan_check()
768 // br %continue.bb
769 //
770 // good.bb:
771 // ; We appear to have the right type. Make sure that all other bytes in
772 // ; the type are still marked as interior bytes. If not, call the runtime.
773 // %shadow.data.int = add %shadow.data.int, 0
774 // %l = load (inttoptr %shadow.data.int)
775 // %not.all.interior = icmp sge %l, 0
776 // br %not.all.interior, label %check.rt.bb, label %continue.bb
777 //
778 // check.rt.bb:
779 // call void @__tysan_check()
780 // br %continue.bb
781
782 Constant *Flags = ConstantInt::get(Ty: OrdTy, V: int(IsRead) | (int(IsWrite) << 1));
783
784 Value *LoadedTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: ShadowData, Name: "shadow.desc");
785 Value *BadTDCmp = IRB.CreateICmpNE(LHS: LoadedTD, RHS: TD, Name: "bad.desc");
786 Instruction *BadTDTerm, *GoodTDTerm;
787 SplitBlockAndInsertIfThenElse(Cond: BadTDCmp, SplitBefore: &*IRB.GetInsertPoint(), ThenTerm: &BadTDTerm,
788 ElseTerm: &GoodTDTerm, BranchWeights: UnlikelyBW);
789 IRB.SetInsertPoint(BadTDTerm);
790
791 // We now know that the types did not match (we're on the slow path). If
792 // the type is unknown, then set it.
793 Value *NullTDCmp = IRB.CreateIsNull(Arg: LoadedTD);
794 Instruction *NullTDTerm, *MismatchTerm;
795 SplitBlockAndInsertIfThenElse(Cond: NullTDCmp, SplitBefore: &*IRB.GetInsertPoint(), ThenTerm: &NullTDTerm,
796 ElseTerm: &MismatchTerm);
797
798 // If the type is unknown, then set the type.
799 IRB.SetInsertPoint(NullTDTerm);
800
801 // We're about to set the type. Make sure that all bytes in the value are
802 // also of unknown type.
803 Value *Size = ConstantInt::get(Ty: OrdTy, V: AccessSize);
804 Value *NotAllUnkTD = IRB.getFalse();
805 for (uint64_t i = 1; i < AccessSize; ++i) {
806 Value *UnkShadowData = IRB.CreateIntToPtr(
807 V: IRB.CreateAdd(LHS: ShadowDataInt, RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift)),
808 DestTy: Int8PtrPtrTy);
809 Value *ILdTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: UnkShadowData);
810 NotAllUnkTD = IRB.CreateOr(LHS: NotAllUnkTD, RHS: IRB.CreateIsNotNull(Arg: ILdTD));
811 }
812
813 Instruction *BeforeSetType = &*IRB.GetInsertPoint();
814 Instruction *BadUTDTerm =
815 SplitBlockAndInsertIfThen(Cond: NotAllUnkTD, SplitBefore: BeforeSetType, Unreachable: false, BranchWeights: UnlikelyBW);
816 IRB.SetInsertPoint(BadUTDTerm);
817 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
818 (Value *)TD, (Value *)Flags});
819
820 IRB.SetInsertPoint(BeforeSetType);
821 SetType();
822
823 // We have a non-trivial mismatch. Call the runtime.
824 IRB.SetInsertPoint(MismatchTerm);
825 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
826 (Value *)TD, (Value *)Flags});
827
828 // We appear to have the right type. Make sure that all other bytes in
829 // the type are still marked as interior bytes. If not, call the runtime.
830 IRB.SetInsertPoint(GoodTDTerm);
831 Value *NotAllBadTD = IRB.getFalse();
832 for (uint64_t i = 1; i < AccessSize; ++i) {
833 Value *BadShadowData = IRB.CreateIntToPtr(
834 V: IRB.CreateAdd(LHS: ShadowDataInt, RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift)),
835 DestTy: Int8PtrPtrTy);
836 Value *ILdTD = IRB.CreatePtrToInt(
837 V: IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: BadShadowData), DestTy: IntptrTy);
838 NotAllBadTD = IRB.CreateOr(
839 LHS: NotAllBadTD, RHS: IRB.CreateICmpSGE(LHS: ILdTD, RHS: ConstantInt::get(Ty: IntptrTy, V: 0)));
840 }
841
842 Instruction *BadITDTerm = SplitBlockAndInsertIfThen(
843 Cond: NotAllBadTD, SplitBefore: &*IRB.GetInsertPoint(), Unreachable: false, BranchWeights: UnlikelyBW);
844 IRB.SetInsertPoint(BadITDTerm);
845 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
846 (Value *)TD, (Value *)Flags});
847 return true;
848}
849
850bool TypeSanitizer::instrumentMemInst(Value *V, Instruction *ShadowBase,
851 Instruction *AppMemMask,
852 const DataLayout &DL) {
853 BasicBlock::iterator IP;
854 BasicBlock *BB;
855 Function *F;
856
857 if (auto *I = dyn_cast<Instruction>(Val: V)) {
858 IP = BasicBlock::iterator(I);
859 BB = I->getParent();
860 F = BB->getParent();
861 } else {
862 auto *A = cast<Argument>(Val: V);
863 F = A->getParent();
864 BB = &F->getEntryBlock();
865 IP = BB->getFirstInsertionPt();
866
867 // Find the next insert point after both ShadowBase and AppMemMask.
868 if (IP->comesBefore(Other: ShadowBase))
869 IP = ShadowBase->getNextNode()->getIterator();
870 if (IP->comesBefore(Other: AppMemMask))
871 IP = AppMemMask->getNextNode()->getIterator();
872 }
873
874 Value *Dest, *Size, *Src = nullptr;
875 bool NeedsMemMove = false;
876 IRBuilder<> IRB(IP);
877
878 if (auto *A = dyn_cast<Argument>(Val: V)) {
879 assert(A->hasByValAttr() && "Type reset for non-byval argument?");
880
881 Dest = A;
882 Size =
883 ConstantInt::get(Ty: IntptrTy, V: DL.getTypeAllocSize(Ty: A->getParamByValType()));
884 } else {
885 auto *I = cast<Instruction>(Val: V);
886 if (auto *MI = dyn_cast<MemIntrinsic>(Val: I)) {
887 if (MI->getDestAddressSpace() != 0)
888 return false;
889
890 Dest = MI->getDest();
891 Size = MI->getLength();
892
893 if (auto *MTI = dyn_cast<MemTransferInst>(Val: MI)) {
894 if (MTI->getSourceAddressSpace() == 0) {
895 Src = MTI->getSource();
896 NeedsMemMove = isa<MemMoveInst>(Val: MTI);
897 }
898 }
899 } else if (auto *II = dyn_cast<LifetimeIntrinsic>(Val: I)) {
900 auto *AI = dyn_cast<AllocaInst>(Val: II->getArgOperand(i: 0));
901 if (!AI)
902 return false;
903
904 Size = IRB.CreateAllocationSize(DestTy: IntptrTy, AI);
905 Dest = II->getArgOperand(i: 0);
906 } else if (auto *AI = dyn_cast<AllocaInst>(Val: I)) {
907 // We need to clear the types for new stack allocations (or else we might
908 // read stale type information from a previous function execution).
909
910 IRB.SetInsertPoint(&*std::next(x: BasicBlock::iterator(I)));
911 IRB.SetInstDebugLocation(I);
912
913 Size = IRB.CreateAllocationSize(DestTy: IntptrTy, AI);
914 Dest = I;
915 } else {
916 return false;
917 }
918 }
919
920 if (ClOutlineInstrumentation) {
921 if (!Src)
922 Src = ConstantPointerNull::get(T: IRB.getPtrTy());
923
924 // The runtime function expects a uint64_t size parameter. On 32-bit
925 // targets, Size may be IntptrTy (i32), so extend it to match.
926 Value *Size64 = IRB.CreateZExtOrTrunc(V: Size, DestTy: U64Ty);
927 IRB.CreateCall(
928 Callee: TysanIntrumentMemInst,
929 Args: {Dest, Src, Size64, NeedsMemMove ? IRB.getTrue() : IRB.getFalse()});
930 return true;
931 } else {
932 if (!ShadowBase)
933 ShadowBase = getShadowBase(F&: *F);
934 if (!AppMemMask)
935 AppMemMask = getAppMemMask(F&: *F);
936
937 Value *ShadowDataInt = IRB.CreateAdd(
938 LHS: IRB.CreateShl(
939 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Dest, DestTy: IntptrTy), RHS: AppMemMask),
940 RHS: PtrShift),
941 RHS: ShadowBase);
942 Value *ShadowData = IRB.CreateIntToPtr(V: ShadowDataInt, DestTy: IRB.getPtrTy());
943
944 if (!Src) {
945 IRB.CreateMemSet(Ptr: ShadowData, Val: IRB.getInt8(C: 0),
946 Size: IRB.CreateShl(LHS: Size, RHS: PtrShift), Align: Align(1ull << PtrShift));
947 return true;
948 }
949
950 Value *SrcShadowDataInt = IRB.CreateAdd(
951 LHS: IRB.CreateShl(
952 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Src, DestTy: IntptrTy), RHS: AppMemMask),
953 RHS: PtrShift),
954 RHS: ShadowBase);
955 Value *SrcShadowData = IRB.CreateIntToPtr(V: SrcShadowDataInt, DestTy: IRB.getPtrTy());
956
957 if (NeedsMemMove) {
958 IRB.CreateMemMove(Dst: ShadowData, DstAlign: Align(1ull << PtrShift), Src: SrcShadowData,
959 SrcAlign: Align(1ull << PtrShift), Size: IRB.CreateShl(LHS: Size, RHS: PtrShift));
960 } else {
961 IRB.CreateMemCpy(Dst: ShadowData, DstAlign: Align(1ull << PtrShift), Src: SrcShadowData,
962 SrcAlign: Align(1ull << PtrShift), Size: IRB.CreateShl(LHS: Size, RHS: PtrShift));
963 }
964 }
965
966 return true;
967}
968
969PreservedAnalyses TypeSanitizerPass::run(Module &M,
970 ModuleAnalysisManager &MAM) {
971 Function *TysanCtorFunction;
972 std::tie(args&: TysanCtorFunction, args: std::ignore) =
973 createSanitizerCtorAndInitFunctions(M, CtorName: kTysanModuleCtorName,
974 InitName: kTysanInitName, /*InitArgTypes=*/{},
975 /*InitArgs=*/{});
976
977 TypeSanitizer TySan(M);
978 TySan.instrumentGlobals(M);
979 appendToGlobalCtors(M, F: TysanCtorFunction, Priority: 0);
980
981 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
982 for (Function &F : M) {
983 const TargetLibraryInfo &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
984 TySan.sanitizeFunction(F, TLI);
985 if (ClVerifyOutlinedInstrumentation && ClOutlineInstrumentation) {
986 // Outlined instrumentation is a new option, and so this exists to
987 // verify there is no difference in behaviour between the options.
988 // If the outlined instrumentation triggers a verification failure
989 // when the original inlined instrumentation does not, or vice versa,
990 // then there is a discrepency which should be investigated.
991 ClOutlineInstrumentation = false;
992 TySan.sanitizeFunction(F, TLI);
993 ClOutlineInstrumentation = true;
994 }
995 }
996
997 return PreservedAnalyses::none();
998}
999