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 // This is required to prevent instrumenting call to __tysan_init from within
559 // the module constructor.
560 if (&F == TysanCtorFunction.getCallee() || &F == TysanGlobalsSetTypeFunction)
561 return false;
562 initializeCallbacks(M&: *F.getParent());
563
564 // We need to collect all loads and stores, and know for what TBAA nodes we
565 // need to generate type descriptors.
566 SmallVector<std::pair<Instruction *, MemoryLocation>> MemoryAccesses;
567 SmallSetVector<const MDNode *, 8> TBAAMetadata;
568 SmallVector<Value *> MemTypeResetInsts;
569 collectMemAccessInfo(F, TLI, MemoryAccesses, TBAAMetadata, MemTypeResetInsts);
570
571 // byval arguments also need their types reset (they're new stack memory,
572 // just like allocas).
573 for (auto &A : F.args())
574 if (A.hasByValAttr())
575 MemTypeResetInsts.push_back(Elt: &A);
576
577 Module &M = *F.getParent();
578 TypeDescriptorsMapTy TypeDescriptors;
579 TypeNameMapTy TypeNames;
580 bool Res = false;
581 for (const MDNode *MD : TBAAMetadata) {
582 if (TypeDescriptors.count(Val: MD))
583 continue;
584
585 if (!generateTypeDescriptor(MD, TypeDescriptors, TypeNames, M))
586 return Res; // Giving up.
587
588 Res = true;
589 }
590
591 const DataLayout &DL = F.getDataLayout();
592 bool SanitizeFunction = F.hasFnAttribute(Kind: Attribute::SanitizeType);
593 bool NeedsInstrumentation =
594 MemTypeResetInsts.empty() && MemoryAccesses.empty();
595 Instruction *ShadowBase = NeedsInstrumentation ? nullptr : getShadowBase(F);
596 Instruction *AppMemMask = NeedsInstrumentation ? nullptr : getAppMemMask(F);
597 for (const auto &[I, MLoc] : MemoryAccesses) {
598 IRBuilder<> IRB(I);
599 assert(MLoc.Size.isPrecise());
600 if (instrumentWithShadowUpdate(
601 IRB, TBAAMD: MLoc.AATags.TBAA, Ptr: const_cast<Value *>(MLoc.Ptr),
602 AccessSize: MLoc.Size.getValue(), IsRead: I->mayReadFromMemory(), IsWrite: I->mayWriteToMemory(),
603 ShadowBase, AppMemMask, ForceSetType: false, SanitizeFunction, TypeDescriptors,
604 DL)) {
605 ++NumInstrumentedAccesses;
606 Res = true;
607 }
608 }
609
610 for (auto Inst : MemTypeResetInsts)
611 Res |= instrumentMemInst(I: Inst, ShadowBase, AppMemMask, DL);
612
613 return Res;
614}
615
616static Value *convertToShadowDataInt(IRBuilder<> &IRB, Value *Ptr,
617 Type *IntptrTy, uint64_t PtrShift,
618 Value *ShadowBase, Value *AppMemMask) {
619 return IRB.CreateAdd(
620 LHS: IRB.CreateShl(
621 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Ptr, DestTy: IntptrTy, Name: "app.ptr.int"),
622 RHS: AppMemMask, Name: "app.ptr.masked"),
623 RHS: PtrShift, Name: "app.ptr.shifted"),
624 RHS: ShadowBase, Name: "shadow.ptr.int");
625}
626
627bool TypeSanitizer::instrumentWithShadowUpdate(
628 IRBuilder<> &IRB, const MDNode *TBAAMD, Value *Ptr, uint64_t AccessSize,
629 bool IsRead, bool IsWrite, Value *ShadowBase, Value *AppMemMask,
630 bool ForceSetType, bool SanitizeFunction,
631 TypeDescriptorsMapTy &TypeDescriptors, const DataLayout &DL) {
632 Constant *TDGV;
633 if (TBAAMD)
634 TDGV = TypeDescriptors[TBAAMD];
635 else
636 TDGV = Constant::getNullValue(Ty: IRB.getPtrTy());
637
638 Value *TD = IRB.CreateBitCast(V: TDGV, DestTy: IRB.getPtrTy());
639
640 if (OutlineInstrumentation) {
641 if (!ForceSetType && (!Opts.tysan_writes_always_set_type || IsRead)) {
642 // We need to check the type here. If the type is unknown, then the read
643 // sets the type. If the type is known, then it is checked. If the type
644 // doesn't match, then we call the runtime type check (which may yet
645 // determine that the mismatch is okay).
646
647 Constant *Flags =
648 ConstantInt::get(Ty: OrdTy, V: (int)IsRead | (((int)IsWrite) << 1));
649
650 IRB.CreateCall(Callee: TysanInstrumentWithShadowUpdate,
651 Args: {Ptr, TD,
652 SanitizeFunction ? IRB.getTrue() : IRB.getFalse(),
653 IRB.getInt64(C: AccessSize), Flags});
654 } else if (ForceSetType || IsWrite) {
655 // In the mode where writes always set the type, for a write (which does
656 // not also read), we just set the type.
657 IRB.CreateCall(Callee: TysanSetShadowType, Args: {Ptr, TD, IRB.getInt64(C: AccessSize)});
658 }
659
660 return true;
661 }
662
663 Value *ShadowDataInt = convertToShadowDataInt(IRB, Ptr, IntptrTy, PtrShift,
664 ShadowBase, AppMemMask);
665 Type *Int8PtrPtrTy = PointerType::get(C&: IRB.getContext(), AddressSpace: 0);
666 Value *ShadowData =
667 IRB.CreateIntToPtr(V: ShadowDataInt, DestTy: Int8PtrPtrTy, Name: "shadow.ptr");
668
669 auto SetType = [&]() {
670 IRB.CreateStore(Val: TD, Ptr: ShadowData);
671
672 // Now fill the remainder of the shadow memory corresponding to the
673 // remainder of the the bytes of the type with a bad type descriptor.
674 for (uint64_t i = 1; i < AccessSize; ++i) {
675 Value *BadShadowData = IRB.CreateIntToPtr(
676 V: IRB.CreateAdd(LHS: ShadowDataInt,
677 RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift),
678 Name: "shadow.byte." + Twine(i) + ".offset"),
679 DestTy: Int8PtrPtrTy, Name: "shadow.byte." + Twine(i) + ".ptr");
680
681 // This is the TD value, -i, which is used to indicate that the byte is
682 // i bytes after the first byte of the type.
683 Value *BadTD =
684 IRB.CreateIntToPtr(V: ConstantInt::getSigned(Ty: IntptrTy, V: -i),
685 DestTy: IRB.getPtrTy(), Name: "bad.descriptor" + Twine(i));
686 IRB.CreateStore(Val: BadTD, Ptr: BadShadowData);
687 }
688 };
689
690 if (ForceSetType || (Opts.tysan_writes_always_set_type && IsWrite)) {
691 // In the mode where writes always set the type, for a write (which does
692 // not also read), we just set the type.
693 SetType();
694 return true;
695 }
696
697 assert((!Opts.tysan_writes_always_set_type || IsRead) &&
698 "should have handled case above");
699 LLVMContext &C = IRB.getContext();
700 MDNode *UnlikelyBW = MDBuilder(C).createBranchWeights(TrueWeight: 1, FalseWeight: 100000);
701
702 if (!SanitizeFunction) {
703 // If we're not sanitizing this function, then we only care whether we
704 // need to *set* the type.
705 Value *LoadedTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: ShadowData, Name: "shadow.desc");
706 Value *NullTDCmp = IRB.CreateIsNull(Arg: LoadedTD, Name: "desc.set");
707 Instruction *NullTDTerm = SplitBlockAndInsertIfThen(
708 Cond: NullTDCmp, SplitBefore: &*IRB.GetInsertPoint(), Unreachable: false, BranchWeights: UnlikelyBW);
709 IRB.SetInsertPoint(NullTDTerm);
710 NullTDTerm->getParent()->setName("set.type");
711 SetType();
712 return true;
713 }
714 // We need to check the type here. If the type is unknown, then the read
715 // sets the type. If the type is known, then it is checked. If the type
716 // doesn't match, then we call the runtime (which may yet determine that
717 // the mismatch is okay).
718 //
719 // The checks generated below have the following structure.
720 //
721 // ; First we load the descriptor for the load from shadow memory and
722 // ; compare it against the type descriptor for the current access type.
723 // %shadow.desc = load ptr %shadow.data
724 // %bad.desc = icmp ne %shadow.desc, %td
725 // br %bad.desc, %bad.bb, %good.bb
726 //
727 // bad.bb:
728 // %shadow.desc.null = icmp eq %shadow.desc, null
729 // br %shadow.desc.null, %null.td.bb, %good.td.bb
730 //
731 // null.td.bb:
732 // ; The typ is unknown, set it if all bytes in the value are also unknown.
733 // ; To check, we load the shadow data for all bytes of the access. For the
734 // ; pseudo code below, assume an access of size 1.
735 // %shadow.data.int = add %shadow.data.int, 0
736 // %l = load (inttoptr %shadow.data.int)
737 // %is.not.null = icmp ne %l, null
738 // %not.all.unknown = %is.not.null
739 // br %no.all.unknown, before.set.type.bb
740 //
741 // before.set.type.bb:
742 // ; Call runtime to check mismatch.
743 // call void @__tysan_check()
744 // br %set.type.bb
745 //
746 // set.type.bb:
747 // ; Now fill the remainder of the shadow memory corresponding to the
748 // ; remainder of the the bytes of the type with a bad type descriptor.
749 // store %TD, %shadow.data
750 // br %continue.bb
751 //
752 // good.td.bb::
753 // ; We have a non-trivial mismatch. Call the runtime.
754 // call void @__tysan_check()
755 // br %continue.bb
756 //
757 // good.bb:
758 // ; We appear to have the right type. Make sure that all other bytes in
759 // ; the type are still marked as interior bytes. If not, call the runtime.
760 // %shadow.data.int = add %shadow.data.int, 0
761 // %l = load (inttoptr %shadow.data.int)
762 // %not.all.interior = icmp sge %l, 0
763 // br %not.all.interior, label %check.rt.bb, label %continue.bb
764 //
765 // check.rt.bb:
766 // call void @__tysan_check()
767 // br %continue.bb
768
769 Constant *Flags = ConstantInt::get(Ty: OrdTy, V: int(IsRead) | (int(IsWrite) << 1));
770
771 Value *LoadedTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: ShadowData, Name: "shadow.desc");
772 Value *BadTDCmp = IRB.CreateICmpNE(LHS: LoadedTD, RHS: TD, Name: "bad.desc");
773 Instruction *BadTDTerm, *GoodTDTerm;
774 SplitBlockAndInsertIfThenElse(Cond: BadTDCmp, SplitBefore: &*IRB.GetInsertPoint(), ThenTerm: &BadTDTerm,
775 ElseTerm: &GoodTDTerm, BranchWeights: UnlikelyBW);
776 IRB.SetInsertPoint(BadTDTerm);
777
778 // We now know that the types did not match (we're on the slow path). If
779 // the type is unknown, then set it.
780 Value *NullTDCmp = IRB.CreateIsNull(Arg: LoadedTD);
781 Instruction *NullTDTerm, *MismatchTerm;
782 SplitBlockAndInsertIfThenElse(Cond: NullTDCmp, SplitBefore: &*IRB.GetInsertPoint(), ThenTerm: &NullTDTerm,
783 ElseTerm: &MismatchTerm);
784
785 // If the type is unknown, then set the type.
786 IRB.SetInsertPoint(NullTDTerm);
787
788 // We're about to set the type. Make sure that all bytes in the value are
789 // also of unknown type.
790 Value *Size = ConstantInt::get(Ty: OrdTy, V: AccessSize);
791 Value *NotAllUnkTD = IRB.getFalse();
792 for (uint64_t i = 1; i < AccessSize; ++i) {
793 Value *UnkShadowData = IRB.CreateIntToPtr(
794 V: IRB.CreateAdd(LHS: ShadowDataInt, RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift)),
795 DestTy: Int8PtrPtrTy);
796 Value *ILdTD = IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: UnkShadowData);
797 NotAllUnkTD = IRB.CreateOr(LHS: NotAllUnkTD, RHS: IRB.CreateIsNotNull(Arg: ILdTD));
798 }
799
800 Instruction *BeforeSetType = &*IRB.GetInsertPoint();
801 Instruction *BadUTDTerm =
802 SplitBlockAndInsertIfThen(Cond: NotAllUnkTD, SplitBefore: BeforeSetType, Unreachable: false, BranchWeights: UnlikelyBW);
803 IRB.SetInsertPoint(BadUTDTerm);
804 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
805 (Value *)TD, (Value *)Flags});
806
807 IRB.SetInsertPoint(BeforeSetType);
808 SetType();
809
810 // We have a non-trivial mismatch. Call the runtime.
811 IRB.SetInsertPoint(MismatchTerm);
812 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
813 (Value *)TD, (Value *)Flags});
814
815 // We appear to have the right type. Make sure that all other bytes in
816 // the type are still marked as interior bytes. If not, call the runtime.
817 IRB.SetInsertPoint(GoodTDTerm);
818 Value *NotAllBadTD = IRB.getFalse();
819 for (uint64_t i = 1; i < AccessSize; ++i) {
820 Value *BadShadowData = IRB.CreateIntToPtr(
821 V: IRB.CreateAdd(LHS: ShadowDataInt, RHS: ConstantInt::get(Ty: IntptrTy, V: i << PtrShift)),
822 DestTy: Int8PtrPtrTy);
823 Value *ILdTD = IRB.CreatePtrToInt(
824 V: IRB.CreateLoad(Ty: IRB.getPtrTy(), Ptr: BadShadowData), DestTy: IntptrTy);
825 NotAllBadTD = IRB.CreateOr(
826 LHS: NotAllBadTD, RHS: IRB.CreateICmpSGE(LHS: ILdTD, RHS: ConstantInt::get(Ty: IntptrTy, V: 0)));
827 }
828
829 Instruction *BadITDTerm = SplitBlockAndInsertIfThen(
830 Cond: NotAllBadTD, SplitBefore: &*IRB.GetInsertPoint(), Unreachable: false, BranchWeights: UnlikelyBW);
831 IRB.SetInsertPoint(BadITDTerm);
832 IRB.CreateCall(Callee: TysanCheck, Args: {IRB.CreateBitCast(V: Ptr, DestTy: IRB.getPtrTy()), Size,
833 (Value *)TD, (Value *)Flags});
834 return true;
835}
836
837bool TypeSanitizer::instrumentMemInst(Value *V, Instruction *ShadowBase,
838 Instruction *AppMemMask,
839 const DataLayout &DL) {
840 BasicBlock::iterator IP;
841 BasicBlock *BB;
842 Function *F;
843
844 if (auto *I = dyn_cast<Instruction>(Val: V)) {
845 IP = BasicBlock::iterator(I);
846 BB = I->getParent();
847 F = BB->getParent();
848 } else {
849 auto *A = cast<Argument>(Val: V);
850 F = A->getParent();
851 BB = &F->getEntryBlock();
852 IP = BB->getFirstInsertionPt();
853
854 // Find the next insert point after both ShadowBase and AppMemMask.
855 if (IP->comesBefore(Other: ShadowBase))
856 IP = ShadowBase->getNextNode()->getIterator();
857 if (IP->comesBefore(Other: AppMemMask))
858 IP = AppMemMask->getNextNode()->getIterator();
859 }
860
861 Value *Dest, *Size, *Src = nullptr;
862 bool NeedsMemMove = false;
863 IRBuilder<> IRB(IP);
864
865 if (auto *A = dyn_cast<Argument>(Val: V)) {
866 assert(A->hasByValAttr() && "Type reset for non-byval argument?");
867
868 Dest = A;
869 Size =
870 ConstantInt::get(Ty: IntptrTy, V: DL.getTypeAllocSize(Ty: A->getParamByValType()));
871 } else {
872 auto *I = cast<Instruction>(Val: V);
873 if (auto *MI = dyn_cast<MemIntrinsic>(Val: I)) {
874 if (MI->getDestAddressSpace() != 0)
875 return false;
876
877 Dest = MI->getDest();
878 Size = MI->getLength();
879
880 if (auto *MTI = dyn_cast<MemTransferInst>(Val: MI)) {
881 if (MTI->getSourceAddressSpace() == 0) {
882 Src = MTI->getSource();
883 NeedsMemMove = isa<MemMoveInst>(Val: MTI);
884 }
885 }
886 } else if (auto *II = dyn_cast<LifetimeIntrinsic>(Val: I)) {
887 auto *AI = dyn_cast<AllocaInst>(Val: II->getArgOperand(i: 0));
888 if (!AI)
889 return false;
890
891 Size = IRB.CreateAllocationSize(DestTy: IntptrTy, AI);
892 Dest = II->getArgOperand(i: 0);
893 } else if (auto *AI = dyn_cast<AllocaInst>(Val: I)) {
894 // We need to clear the types for new stack allocations (or else we might
895 // read stale type information from a previous function execution).
896
897 IRB.SetInsertPoint(&*std::next(x: BasicBlock::iterator(I)));
898 IRB.SetInstDebugLocation(I);
899
900 Size = IRB.CreateAllocationSize(DestTy: IntptrTy, AI);
901 Dest = I;
902 } else {
903 return false;
904 }
905 }
906
907 if (OutlineInstrumentation) {
908 if (!Src)
909 Src = ConstantPointerNull::get(T: IRB.getPtrTy());
910
911 // The runtime function expects a uint64_t size parameter. On 32-bit
912 // targets, Size may be IntptrTy (i32), so extend it to match.
913 Value *Size64 = IRB.CreateZExtOrTrunc(V: Size, DestTy: U64Ty);
914 IRB.CreateCall(
915 Callee: TysanIntrumentMemInst,
916 Args: {Dest, Src, Size64, NeedsMemMove ? IRB.getTrue() : IRB.getFalse()});
917 return true;
918 } else {
919 if (!ShadowBase)
920 ShadowBase = getShadowBase(F&: *F);
921 if (!AppMemMask)
922 AppMemMask = getAppMemMask(F&: *F);
923
924 Value *ShadowDataInt = IRB.CreateAdd(
925 LHS: IRB.CreateShl(
926 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Dest, DestTy: IntptrTy), RHS: AppMemMask),
927 RHS: PtrShift),
928 RHS: ShadowBase);
929 Value *ShadowData = IRB.CreateIntToPtr(V: ShadowDataInt, DestTy: IRB.getPtrTy());
930
931 if (!Src) {
932 IRB.CreateMemSet(Ptr: ShadowData, Val: IRB.getInt8(C: 0),
933 Size: IRB.CreateShl(LHS: Size, RHS: PtrShift),
934 Align: Align::fromLog2(Log2Value: PtrShift));
935 return true;
936 }
937
938 Value *SrcShadowDataInt = IRB.CreateAdd(
939 LHS: IRB.CreateShl(
940 LHS: IRB.CreateAnd(LHS: IRB.CreatePtrToInt(V: Src, DestTy: IntptrTy), RHS: AppMemMask),
941 RHS: PtrShift),
942 RHS: ShadowBase);
943 Value *SrcShadowData = IRB.CreateIntToPtr(V: SrcShadowDataInt, DestTy: IRB.getPtrTy());
944
945 if (NeedsMemMove) {
946 IRB.CreateMemMove(Dst: ShadowData, DstAlign: Align::fromLog2(Log2Value: PtrShift), Src: SrcShadowData,
947 SrcAlign: Align::fromLog2(Log2Value: PtrShift),
948 Size: IRB.CreateShl(LHS: Size, RHS: PtrShift));
949 } else {
950 IRB.CreateMemCpy(Dst: ShadowData, DstAlign: Align::fromLog2(Log2Value: PtrShift), Src: SrcShadowData,
951 SrcAlign: Align::fromLog2(Log2Value: PtrShift),
952 Size: IRB.CreateShl(LHS: Size, RHS: PtrShift));
953 }
954 }
955
956 return true;
957}
958
959PreservedAnalyses TypeSanitizerPass::run(Module &M,
960 ModuleAnalysisManager &MAM) {
961 Function *TysanCtorFunction;
962 std::tie(args&: TysanCtorFunction, args: std::ignore) =
963 createSanitizerCtorAndInitFunctions(M, CtorName: kTysanModuleCtorName,
964 InitName: kTysanInitName, /*InitArgTypes=*/{},
965 /*InitArgs=*/{});
966
967 const InstrumentationOptions &Opts =
968 M.getContext().getLibraryOptions().get<InstrumentationOptions>();
969 TypeSanitizer TySan(Opts, M);
970 TySan.instrumentGlobals(M);
971 appendToGlobalCtors(M, F: TysanCtorFunction, Priority: 0);
972
973 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
974 for (Function &F : M) {
975 const TargetLibraryInfo &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
976 TySan.sanitizeFunction(F, TLI);
977 if (Opts.tysan_verify_outlined_instrumentation &&
978 Opts.tysan_outline_instrumentation) {
979 // Outlined instrumentation is a new option, and so this exists to
980 // verify there is no difference in behaviour between the options.
981 // If the outlined instrumentation triggers a verification failure
982 // when the original inlined instrumentation does not, or vice versa,
983 // then there is a discrepency which should be investigated.
984 TySan.OutlineInstrumentation = false;
985 TySan.sanitizeFunction(F, TLI);
986 TySan.OutlineInstrumentation = true;
987 }
988 }
989
990 return PreservedAnalyses::none();
991}
992