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