OLD | NEW |
1 //===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===// | 1 //===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===// |
2 // | 2 // |
3 // The LLVM Compiler Infrastructure | 3 // The LLVM Compiler Infrastructure |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file is a part of AddressSanitizer, an address sanity checker. | 10 // This file is a part of AddressSanitizer, an address sanity checker. |
11 // Details of the algorithm: | 11 // Details of the algorithm: |
12 // http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm | 12 // http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm |
13 // | 13 // |
14 //===----------------------------------------------------------------------===// | 14 //===----------------------------------------------------------------------===// |
15 | 15 |
16 #define DEBUG_TYPE "asan" | 16 #define DEBUG_TYPE "asan" |
17 | 17 |
18 #include "llvm/Transforms/Instrumentation.h" | 18 #include "llvm/Transforms/Instrumentation.h" |
19 #include "llvm/ADT/ArrayRef.h" | 19 #include "llvm/ADT/ArrayRef.h" |
| 20 #include "llvm/ADT/BitVector.h" |
20 #include "llvm/ADT/DenseMap.h" | 21 #include "llvm/ADT/DenseMap.h" |
21 #include "llvm/ADT/DepthFirstIterator.h" | 22 #include "llvm/ADT/DepthFirstIterator.h" |
| 23 #include "llvm/ADT/MapVector.h" |
22 #include "llvm/ADT/OwningPtr.h" | 24 #include "llvm/ADT/OwningPtr.h" |
| 25 #include "llvm/ADT/SCCIterator.h" |
23 #include "llvm/ADT/SmallSet.h" | 26 #include "llvm/ADT/SmallSet.h" |
24 #include "llvm/ADT/SmallString.h" | 27 #include "llvm/ADT/SmallString.h" |
25 #include "llvm/ADT/SmallVector.h" | 28 #include "llvm/ADT/SmallVector.h" |
| 29 #include "llvm/ADT/Statistic.h" |
26 #include "llvm/ADT/StringExtras.h" | 30 #include "llvm/ADT/StringExtras.h" |
27 #include "llvm/ADT/Triple.h" | 31 #include "llvm/ADT/Triple.h" |
28 #include "llvm/DIBuilder.h" | 32 #include "llvm/DIBuilder.h" |
29 #include "llvm/IR/DataLayout.h" | 33 #include "llvm/IR/DataLayout.h" |
30 #include "llvm/IR/Function.h" | 34 #include "llvm/IR/Function.h" |
31 #include "llvm/IR/IRBuilder.h" | 35 #include "llvm/IR/IRBuilder.h" |
32 #include "llvm/IR/InlineAsm.h" | 36 #include "llvm/IR/InlineAsm.h" |
33 #include "llvm/IR/IntrinsicInst.h" | 37 #include "llvm/IR/IntrinsicInst.h" |
34 #include "llvm/IR/LLVMContext.h" | 38 #include "llvm/IR/LLVMContext.h" |
35 #include "llvm/IR/Module.h" | 39 #include "llvm/IR/Module.h" |
36 #include "llvm/IR/Type.h" | 40 #include "llvm/IR/Type.h" |
37 #include "llvm/InstVisitor.h" | 41 #include "llvm/InstVisitor.h" |
| 42 #include "llvm/Support/CFG.h" |
38 #include "llvm/Support/CallSite.h" | 43 #include "llvm/Support/CallSite.h" |
39 #include "llvm/Support/CommandLine.h" | 44 #include "llvm/Support/CommandLine.h" |
40 #include "llvm/Support/DataTypes.h" | 45 #include "llvm/Support/DataTypes.h" |
41 #include "llvm/Support/Debug.h" | 46 #include "llvm/Support/Debug.h" |
42 #include "llvm/Support/raw_ostream.h" | 47 #include "llvm/Support/raw_ostream.h" |
43 #include "llvm/Support/system_error.h" | 48 #include "llvm/Support/system_error.h" |
44 #include "llvm/Target/TargetMachine.h" | 49 #include "llvm/Target/TargetMachine.h" |
45 #include "llvm/Transforms/Utils/BasicBlockUtils.h" | 50 #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
46 #include "llvm/Transforms/Utils/BlackList.h" | 51 #include "llvm/Transforms/Utils/BlackList.h" |
47 #include "llvm/Transforms/Utils/Local.h" | 52 #include "llvm/Transforms/Utils/Local.h" |
48 #include "llvm/Transforms/Utils/ModuleUtils.h" | 53 #include "llvm/Transforms/Utils/ModuleUtils.h" |
49 #include <algorithm> | 54 #include <algorithm> |
| 55 #include <map> |
50 #include <string> | 56 #include <string> |
| 57 #include <vector> |
51 | 58 |
52 using namespace llvm; | 59 using namespace llvm; |
53 | 60 |
54 static const uint64_t kDefaultShadowScale = 3; | 61 static const uint64_t kDefaultShadowScale = 3; |
55 static const uint64_t kDefaultShadowOffset32 = 1ULL << 29; | 62 static const uint64_t kDefaultShadowOffset32 = 1ULL << 29; |
56 static const uint64_t kDefaultShadowOffset64 = 1ULL << 44; | 63 static const uint64_t kDefaultShadowOffset64 = 1ULL << 44; |
57 static const uint64_t kDefaultShort64bitShadowOffset = 0x7FFF8000; // < 2G. | 64 static const uint64_t kDefaultShort64bitShadowOffset = 0x7FFF8000; // < 2G. |
58 static const uint64_t kPPC64_ShadowOffset64 = 1ULL << 41; | 65 static const uint64_t kPPC64_ShadowOffset64 = 1ULL << 41; |
59 | 66 |
60 static const size_t kMaxStackMallocSize = 1 << 16; // 64K | 67 static const size_t kMaxStackMallocSize = 1 << 16; // 64K |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
143 | 150 |
144 // Optimization flags. Not user visible, used mostly for testing | 151 // Optimization flags. Not user visible, used mostly for testing |
145 // and benchmarking the tool. | 152 // and benchmarking the tool. |
146 static cl::opt<bool> ClOpt("asan-opt", | 153 static cl::opt<bool> ClOpt("asan-opt", |
147 cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true)); | 154 cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true)); |
148 static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp", | 155 static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp", |
149 cl::desc("Instrument the same temp just once"), cl::Hidden, | 156 cl::desc("Instrument the same temp just once"), cl::Hidden, |
150 cl::init(true)); | 157 cl::init(true)); |
151 static cl::opt<bool> ClOptGlobals("asan-opt-globals", | 158 static cl::opt<bool> ClOptGlobals("asan-opt-globals", |
152 cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true)); | 159 cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true)); |
| 160 static cl::opt<bool> ClOptSCC("asan-opt-scc", |
| 161 cl::desc("Don't instrument temps already instrumented in " |
| 162 "predessors in the SCC"), cl::Hidden, cl::init(true)); |
153 | 163 |
154 static cl::opt<bool> ClCheckLifetime("asan-check-lifetime", | 164 static cl::opt<bool> ClCheckLifetime("asan-check-lifetime", |
155 cl::desc("Use llvm.lifetime intrinsics to insert extra checks"), | 165 cl::desc("Use llvm.lifetime intrinsics to insert extra checks"), |
156 cl::Hidden, cl::init(false)); | 166 cl::Hidden, cl::init(false)); |
157 | 167 |
158 // Debug flags. | 168 // Debug flags. |
159 static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden, | 169 static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden, |
160 cl::init(0)); | 170 cl::init(0)); |
161 static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"), | 171 static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"), |
162 cl::Hidden, cl::init(0)); | 172 cl::Hidden, cl::init(0)); |
163 static cl::opt<std::string> ClDebugFunc("asan-debug-func", | 173 static cl::opt<std::string> ClDebugFunc("asan-debug-func", |
164 cl::Hidden, cl::desc("Debug func")); | 174 cl::Hidden, cl::desc("Debug func")); |
165 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"), | 175 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"), |
166 cl::Hidden, cl::init(-1)); | 176 cl::Hidden, cl::init(-1)); |
167 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"), | 177 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"), |
168 cl::Hidden, cl::init(-1)); | 178 cl::Hidden, cl::init(-1)); |
169 | 179 |
| 180 STATISTIC(NumInstrumentedInstructions, |
| 181 "Total number of instrumented instructions"); |
| 182 STATISTIC(NumInstrumentedSCC, |
| 183 "Number of instrumented instructions by SCC approach"); |
| 184 STATISTIC(NumInstrumentedBase, |
| 185 "Number of instrumented instructions by basic approach"); |
| 186 |
170 namespace { | 187 namespace { |
171 /// A set of dynamically initialized globals extracted from metadata. | 188 /// A set of dynamically initialized globals extracted from metadata. |
172 class SetOfDynamicallyInitializedGlobals { | 189 class SetOfDynamicallyInitializedGlobals { |
173 public: | 190 public: |
174 void Init(Module& M) { | 191 void Init(Module& M) { |
175 // Clang generates metadata identifying all dynamically initialized globals. | 192 // Clang generates metadata identifying all dynamically initialized globals. |
176 NamedMDNode *DynamicGlobals = | 193 NamedMDNode *DynamicGlobals = |
177 M.getNamedMetadata("llvm.asan.dynamically_initialized_globals"); | 194 M.getNamedMetadata("llvm.asan.dynamically_initialized_globals"); |
178 if (!DynamicGlobals) | 195 if (!DynamicGlobals) |
179 return; | 196 return; |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
273 Value *Size, | 290 Value *Size, |
274 Instruction *InsertBefore, bool IsWrite); | 291 Instruction *InsertBefore, bool IsWrite); |
275 Value *memToShadow(Value *Shadow, IRBuilder<> &IRB); | 292 Value *memToShadow(Value *Shadow, IRBuilder<> &IRB); |
276 bool runOnFunction(Function &F); | 293 bool runOnFunction(Function &F); |
277 bool maybeInsertAsanInitAtFunctionEntry(Function &F); | 294 bool maybeInsertAsanInitAtFunctionEntry(Function &F); |
278 void emitShadowMapping(Module &M, IRBuilder<> &IRB) const; | 295 void emitShadowMapping(Module &M, IRBuilder<> &IRB) const; |
279 virtual bool doInitialization(Module &M); | 296 virtual bool doInitialization(Module &M); |
280 static char ID; // Pass identification, replacement for typeid | 297 static char ID; // Pass identification, replacement for typeid |
281 | 298 |
282 private: | 299 private: |
| 300 struct SCCBlock { |
| 301 // Indices of predessors in the graph of SCCs. |
| 302 std::vector<unsigned> Preds; |
| 303 |
| 304 // Vector of entry blocks in the current component. |
| 305 std::vector<BasicBlock*> EntryBlocks; |
| 306 |
| 307 // Vector of inner blocks in the current component. |
| 308 std::vector<BasicBlock*> InnerBlocks; |
| 309 |
| 310 // i-th element if |IsInstrumented| is true iff it's guaranteed |
| 311 // that i-th interesting memory access in the whole function is |
| 312 // instrumented at exit from this component. |
| 313 BitVector IsInstrumented; |
| 314 |
| 315 // True if any of basic blocks from this component has call |
| 316 // instruction. |
| 317 bool HasCallInstruction; |
| 318 }; |
| 319 |
283 void initializeCallbacks(Module &M); | 320 void initializeCallbacks(Module &M); |
284 | 321 |
285 bool ShouldInstrumentGlobal(GlobalVariable *G); | 322 bool ShouldInstrumentGlobal(GlobalVariable *G); |
286 bool LooksLikeCodeInBug11395(Instruction *I); | 323 bool LooksLikeCodeInBug11395(Instruction *I); |
| 324 bool CanInstrumentFunction(Function &F); |
287 void FindDynamicInitializers(Module &M); | 325 void FindDynamicInitializers(Module &M); |
288 | 326 |
| 327 // Basic analysis. |
| 328 // |
| 329 // Store all instructions that need to be instrumented into |
| 330 // |ToInstrument|, store calls which do not return in |
| 331 // |NoReturnCalls|. |
| 332 bool baseAnalyzeFunction(Function &F, |
| 333 SmallVector<Instruction*, 16> &ToInstrument, |
| 334 SmallVector<Instruction*, 8> &NoReturnCalls); |
| 335 |
| 336 // SCC analysis. |
| 337 // |
| 338 // Analyzes single SCC constructed from basic blocks. Stores all |
| 339 // instructions that need to be instrumented in |ToInstrument|, |
| 340 // calls which do not return in |NoReturnCalls| and adjusts the |
| 341 // component's post-invariant bit vector. |
| 342 void sccAnalyzeComponent( |
| 343 unsigned ComponentIndex, |
| 344 std::vector<SCCBlock> &SCC, |
| 345 const MapVector<Value*, unsigned> &InterestingAccess, |
| 346 SmallVector<Instruction*, 16> &ToInstrument, |
| 347 SmallVector<Instruction*, 8> &NoReturnCalls); |
| 348 void sccAddComponent(std::vector<BasicBlock*> &BasicBlocks, |
| 349 std::map<BasicBlock*, unsigned> &SCCMapping, |
| 350 std::vector<SCCBlock> &SCC); |
| 351 // Analyzes graph constructed from SCCs of |F|'s basic blocks. If |
| 352 // fuction can be instrumented, stores all instructions that need to |
| 353 // be instrumented in |ToInstrument|, stores all calls which do not |
| 354 // return in |NoReturnCalls| and returns true. Otherwise, returns |
| 355 // false. |
| 356 bool sccAnalyzeFunction(Function &F, |
| 357 SmallVector<Instruction*, 16> &ToInstrument, |
| 358 SmallVector<Instruction*, 8> &NoReturnCalls); |
| 359 |
289 bool CheckInitOrder; | 360 bool CheckInitOrder; |
290 bool CheckUseAfterReturn; | 361 bool CheckUseAfterReturn; |
291 bool CheckLifetime; | 362 bool CheckLifetime; |
292 SmallString<64> BlacklistFile; | 363 SmallString<64> BlacklistFile; |
293 bool ZeroBaseShadow; | 364 bool ZeroBaseShadow; |
294 | 365 |
295 LLVMContext *C; | 366 LLVMContext *C; |
296 DataLayout *TD; | 367 DataLayout *TD; |
297 int LongSize; | 368 int LongSize; |
298 Type *IntptrTy; | 369 Type *IntptrTy; |
(...skipping 314 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
613 return RMW->getPointerOperand(); | 684 return RMW->getPointerOperand(); |
614 } | 685 } |
615 if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) { | 686 if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) { |
616 if (!ClInstrumentAtomics) return NULL; | 687 if (!ClInstrumentAtomics) return NULL; |
617 *IsWrite = true; | 688 *IsWrite = true; |
618 return XCHG->getPointerOperand(); | 689 return XCHG->getPointerOperand(); |
619 } | 690 } |
620 return NULL; | 691 return NULL; |
621 } | 692 } |
622 | 693 |
| 694 static bool hasCallInstruction(BasicBlock &BB) { |
| 695 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); |
| 696 BI != BE; ++BI) { |
| 697 CallSite CS(BI); |
| 698 if (CS) |
| 699 return true; |
| 700 } |
| 701 return false; |
| 702 } |
| 703 |
| 704 // Returns map of all interesting to memory accesses (loads and |
| 705 // stores). Memory accesses are stored with their order numbers, |
| 706 // starting with zero. |
| 707 static void getInterestingAccesses(BasicBlock &BB, |
| 708 MapVector<Value*, unsigned> &M) { |
| 709 bool IsWrite; |
| 710 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE; ++BI) { |
| 711 if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { |
| 712 if (M.find(Addr) != M.end()) |
| 713 continue; |
| 714 unsigned Index = M.size(); |
| 715 M.insert(std::make_pair(Addr, Index)); |
| 716 } |
| 717 } |
| 718 } |
| 719 |
| 720 // Returns all instructions that must be instrumented (currently, |
| 721 // memory intrinsics, loads and stores). In addition, returns all call |
| 722 // instructions which do not return. Modifies |IsInstrumented| |
| 723 // according to memory accesses and calls inside |BB|. |
| 724 static void getInsnsToInstrument( |
| 725 BasicBlock &BB, |
| 726 const MapVector<Value*, unsigned> &InterestingAccess, |
| 727 BitVector &IsInstrumented, |
| 728 SmallVector<Instruction*, 16> &ToInstrument, |
| 729 SmallVector<Instruction*, 8> &NoReturnCalls) { |
| 730 int NumInsnsPerBB = 0; |
| 731 bool IsWrite; |
| 732 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE; ++BI) { |
| 733 if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { |
| 734 if (ClOpt && (ClOptSameTemp || ClOptSCC)) { |
| 735 MapVector<Value*, unsigned>::const_iterator MI = |
| 736 InterestingAccess.find(Addr); |
| 737 assert(MI != InterestingAccess.end()); |
| 738 unsigned Index = MI->second; |
| 739 if (IsInstrumented.test(Index)) |
| 740 continue; // We've seen this temp in the current BB. |
| 741 IsInstrumented.set(Index); |
| 742 } |
| 743 // OK, take it. |
| 744 } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { |
| 745 // OK, take it. |
| 746 } else { |
| 747 CallSite CS(BI); |
| 748 if (CS) { |
| 749 // A call inside BB. |
| 750 IsInstrumented.reset(); |
| 751 if (CS.doesNotReturn()) |
| 752 NoReturnCalls.push_back(CS.getInstruction()); |
| 753 } |
| 754 continue; |
| 755 } |
| 756 ToInstrument.push_back(BI); |
| 757 NumInsnsPerBB++; |
| 758 if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) |
| 759 break; |
| 760 } |
| 761 } |
| 762 |
623 void AddressSanitizer::instrumentMop(Instruction *I) { | 763 void AddressSanitizer::instrumentMop(Instruction *I) { |
624 bool IsWrite = false; | 764 bool IsWrite = false; |
625 Value *Addr = isInterestingMemoryAccess(I, &IsWrite); | 765 Value *Addr = isInterestingMemoryAccess(I, &IsWrite); |
626 assert(Addr); | 766 assert(Addr); |
627 if (ClOpt && ClOptGlobals) { | 767 if (ClOpt && ClOptGlobals) { |
628 if (GlobalVariable *G = dyn_cast<GlobalVariable>(Addr)) { | 768 if (GlobalVariable *G = dyn_cast<GlobalVariable>(Addr)) { |
629 // If initialization order checking is disabled, a simple access to a | 769 // If initialization order checking is disabled, a simple access to a |
630 // dynamically initialized global is always valid. | 770 // dynamically initialized global is always valid. |
631 if (!CheckInitOrder) | 771 if (!CheckInitOrder) |
632 return; | 772 return; |
(...skipping 469 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1102 // If needed, insert __asan_init before checking for SanitizeAddress attr. | 1242 // If needed, insert __asan_init before checking for SanitizeAddress attr. |
1103 maybeInsertAsanInitAtFunctionEntry(F); | 1243 maybeInsertAsanInitAtFunctionEntry(F); |
1104 | 1244 |
1105 if (!F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, | 1245 if (!F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, |
1106 Attribute::SanitizeAddress)) | 1246 Attribute::SanitizeAddress)) |
1107 return false; | 1247 return false; |
1108 | 1248 |
1109 if (!ClDebugFunc.empty() && ClDebugFunc != F.getName()) | 1249 if (!ClDebugFunc.empty() && ClDebugFunc != F.getName()) |
1110 return false; | 1250 return false; |
1111 | 1251 |
1112 // We want to instrument every address only once per basic block (unless there | |
1113 // are calls between uses). | |
1114 SmallSet<Value*, 16> TempsToInstrument; | |
1115 SmallVector<Instruction*, 16> ToInstrument; | 1252 SmallVector<Instruction*, 16> ToInstrument; |
1116 SmallVector<Instruction*, 8> NoReturnCalls; | 1253 SmallVector<Instruction*, 8> NoReturnCalls; |
1117 bool IsWrite; | |
1118 | 1254 |
1119 // Fill the set of memory operations to instrument. | 1255 bool SCCAnalysis = false; |
1120 for (Function::iterator FI = F.begin(), FE = F.end(); | 1256 if (ClOptSCC && sccAnalyzeFunction(F, ToInstrument, NoReturnCalls)) |
1121 FI != FE; ++FI) { | 1257 SCCAnalysis = true; |
1122 TempsToInstrument.clear(); | 1258 else if (baseAnalyzeFunction(F, ToInstrument, NoReturnCalls)) |
1123 int NumInsnsPerBB = 0; | 1259 SCCAnalysis = false; |
1124 for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); | 1260 else |
1125 BI != BE; ++BI) { | 1261 return false; |
1126 if (LooksLikeCodeInBug11395(BI)) return false; | |
1127 if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { | |
1128 if (ClOpt && ClOptSameTemp) { | |
1129 if (!TempsToInstrument.insert(Addr)) | |
1130 continue; // We've seen this temp in the current BB. | |
1131 } | |
1132 } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { | |
1133 // ok, take it. | |
1134 } else { | |
1135 CallSite CS(BI); | |
1136 if (CS) { | |
1137 // A call inside BB. | |
1138 TempsToInstrument.clear(); | |
1139 if (CS.doesNotReturn()) | |
1140 NoReturnCalls.push_back(CS.getInstruction()); | |
1141 } | |
1142 continue; | |
1143 } | |
1144 ToInstrument.push_back(BI); | |
1145 NumInsnsPerBB++; | |
1146 if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) | |
1147 break; | |
1148 } | |
1149 } | |
1150 | 1262 |
1151 // Instrument. | 1263 // Instrument. |
1152 int NumInstrumented = 0; | 1264 int NumInstrumented = 0; |
| 1265 bool IsWrite; |
1153 for (size_t i = 0, n = ToInstrument.size(); i != n; i++) { | 1266 for (size_t i = 0, n = ToInstrument.size(); i != n; i++) { |
1154 Instruction *Inst = ToInstrument[i]; | 1267 Instruction *Inst = ToInstrument[i]; |
1155 if (ClDebugMin < 0 || ClDebugMax < 0 || | 1268 if (ClDebugMin < 0 || ClDebugMax < 0 || |
1156 (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) { | 1269 (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) { |
1157 if (isInterestingMemoryAccess(Inst, &IsWrite)) | 1270 if (isInterestingMemoryAccess(Inst, &IsWrite)) |
1158 instrumentMop(Inst); | 1271 instrumentMop(Inst); |
1159 else | 1272 else |
1160 instrumentMemIntrinsic(cast<MemIntrinsic>(Inst)); | 1273 instrumentMemIntrinsic(cast<MemIntrinsic>(Inst)); |
1161 } | 1274 } |
1162 NumInstrumented++; | 1275 NumInstrumented++; |
1163 } | 1276 } |
1164 | 1277 |
| 1278 NumInstrumentedInstructions += NumInstrumented; |
| 1279 if (SCCAnalysis) |
| 1280 NumInstrumentedSCC += NumInstrumented; |
| 1281 else |
| 1282 NumInstrumentedBase += NumInstrumented; |
| 1283 |
1165 FunctionStackPoisoner FSP(F, *this); | 1284 FunctionStackPoisoner FSP(F, *this); |
1166 bool ChangedStack = FSP.runOnFunction(); | 1285 bool ChangedStack = FSP.runOnFunction(); |
1167 | 1286 |
1168 // We must unpoison the stack before every NoReturn call (throw, _exit, etc). | 1287 // We must unpoison the stack before every NoReturn call (throw, _exit, etc). |
1169 // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37 | 1288 // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37 |
1170 for (size_t i = 0, n = NoReturnCalls.size(); i != n; i++) { | 1289 for (size_t i = 0, n = NoReturnCalls.size(); i != n; i++) { |
1171 Instruction *CI = NoReturnCalls[i]; | 1290 Instruction *CI = NoReturnCalls[i]; |
1172 IRBuilder<> IRB(CI); | 1291 IRBuilder<> IRB(CI); |
1173 IRB.CreateCall(AsanHandleNoReturnFunc); | 1292 IRB.CreateCall(AsanHandleNoReturnFunc); |
1174 } | 1293 } |
1175 DEBUG(dbgs() << "ASAN done instrumenting:\n" << F << "\n"); | 1294 DEBUG(dbgs() << "ASAN done instrumenting:\n" << F << "\n"); |
1176 | 1295 |
1177 return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); | 1296 return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); |
1178 } | 1297 } |
1179 | 1298 |
| 1299 bool AddressSanitizer::baseAnalyzeFunction( |
| 1300 Function& F, |
| 1301 SmallVector<Instruction*, 16> &ToInstrument, |
| 1302 SmallVector<Instruction*, 8> &NoReturnCalls) { |
| 1303 if (!CanInstrumentFunction(F)) |
| 1304 return false; |
| 1305 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
| 1306 BasicBlock &BB = *FI; |
| 1307 MapVector<Value*, unsigned> InterestingAccess; |
| 1308 getInterestingAccesses(BB, InterestingAccess); |
| 1309 BitVector IsInstrumented(InterestingAccess.size()); |
| 1310 getInsnsToInstrument(BB, InterestingAccess, IsInstrumented, ToInstrument, |
| 1311 NoReturnCalls); |
| 1312 } |
| 1313 return true; |
| 1314 } |
| 1315 |
| 1316 void AddressSanitizer::sccAnalyzeComponent( |
| 1317 unsigned ComponentIndex, |
| 1318 std::vector<SCCBlock> &SCC, |
| 1319 const MapVector<Value*, unsigned> &InterestingAccess, |
| 1320 SmallVector<Instruction*, 16> &ToInstrument, |
| 1321 SmallVector<Instruction*, 8> &NoReturnCalls) { |
| 1322 SCCBlock &Component = SCC[ComponentIndex]; |
| 1323 BitVector IsInstrumented(InterestingAccess.size()); |
| 1324 Component.IsInstrumented.resize(InterestingAccess.size()); |
| 1325 if (!Component.HasCallInstruction) { |
| 1326 // Constructs pre-invariant BitVector. i-th element of |
| 1327 // IsInstrumented is true iff it's guaranteed that i-th memory |
| 1328 // access from InterestingAccess do not require instrumentation. |
| 1329 if (!Component.Preds.empty()) { |
| 1330 IsInstrumented.set(0, InterestingAccess.size()); |
| 1331 for (std::vector<unsigned>::iterator SI = Component.Preds.begin(), |
| 1332 SE = Component.Preds.end(); SI != SE; ++SI) { |
| 1333 IsInstrumented &= SCC[*SI].IsInstrumented; |
| 1334 } |
| 1335 } |
| 1336 Component.IsInstrumented.set(); |
| 1337 } |
| 1338 |
| 1339 // Iterate over all entry blocks and update pre-invariant vector for |
| 1340 // inner blocks. |
| 1341 for (std::vector<BasicBlock*>::iterator I = Component.EntryBlocks.begin(), |
| 1342 E = Component.EntryBlocks.end(); I != E; ++I) { |
| 1343 BitVector PostEntryInstrumented(IsInstrumented); |
| 1344 BasicBlock *BB = *I; |
| 1345 assert(BB); |
| 1346 getInsnsToInstrument(*BB, InterestingAccess, PostEntryInstrumented, |
| 1347 ToInstrument, NoReturnCalls); |
| 1348 Component.IsInstrumented &= PostEntryInstrumented; |
| 1349 } |
| 1350 |
| 1351 // Iterate over all inner blocks. |
| 1352 for (std::vector<BasicBlock*>::iterator I = Component.InnerBlocks.begin(), |
| 1353 E = Component.InnerBlocks.end(); I != E; ++I) { |
| 1354 BitVector PreInnerInstrumented(Component.IsInstrumented); |
| 1355 BasicBlock *BB = *I; |
| 1356 assert(BB); |
| 1357 getInsnsToInstrument(*BB, InterestingAccess, PreInnerInstrumented, |
| 1358 ToInstrument, NoReturnCalls); |
| 1359 } |
| 1360 } |
| 1361 |
| 1362 void AddressSanitizer::sccAddComponent( |
| 1363 std::vector<BasicBlock*> &BasicBlocks, |
| 1364 std::map<BasicBlock*, unsigned> &SCCMapping, |
| 1365 std::vector<SCCBlock> &SCC) { |
| 1366 unsigned NewComponentIndex = SCC.size(); |
| 1367 SCC.push_back(SCCBlock()); |
| 1368 SCCBlock &Component = SCC.back(); |
| 1369 Component.HasCallInstruction = false; |
| 1370 for (std::vector<BasicBlock*>::iterator I = BasicBlocks.begin(), |
| 1371 E = BasicBlocks.end(); I != E; ++I) { |
| 1372 BasicBlock *BB = *I; |
| 1373 SCCMapping[BB] = NewComponentIndex; |
| 1374 if (hasCallInstruction(*BB)) |
| 1375 Component.HasCallInstruction = true; |
| 1376 } |
| 1377 for (std::vector<BasicBlock*>::iterator I = BasicBlocks.begin(), |
| 1378 E = BasicBlocks.end(); I != E; ++I) { |
| 1379 BasicBlock *BB = *I; |
| 1380 assert(BB); |
| 1381 bool IsEntryBlock = (pred_begin(BB) == pred_end(BB)); |
| 1382 for (pred_iterator BI = pred_begin(BB), BE = pred_end(BB); BI != BE; ++BI) { |
| 1383 BasicBlock *PredBB = *BI; |
| 1384 assert(SCCMapping.find(PredBB) != SCCMapping.end()); |
| 1385 if (SCCMapping[PredBB] != NewComponentIndex) { |
| 1386 Component.Preds.push_back(SCCMapping[PredBB]); |
| 1387 IsEntryBlock = true; |
| 1388 } |
| 1389 } |
| 1390 if (IsEntryBlock) |
| 1391 Component.EntryBlocks.push_back(BB); |
| 1392 else |
| 1393 Component.InnerBlocks.push_back(BB); |
| 1394 } |
| 1395 |
| 1396 // Remove duplicates from the list of predessors. |
| 1397 std::sort(Component.Preds.begin(), Component.Preds.end()); |
| 1398 Component.Preds.resize(std::unique(Component.Preds.begin(), |
| 1399 Component.Preds.end()) - |
| 1400 Component.Preds.begin()); |
| 1401 } |
| 1402 |
| 1403 bool AddressSanitizer::sccAnalyzeFunction( |
| 1404 Function &F, |
| 1405 SmallVector<Instruction*, 16> &ToInstrument, |
| 1406 SmallVector<Instruction*, 8> &NoReturnCalls) { |
| 1407 if (!CanInstrumentFunction(F)) |
| 1408 return false; |
| 1409 |
| 1410 // Can't use SCC analysis when function has more than one entry |
| 1411 // basic blocks. |
| 1412 int NumEntryNodes = 0; |
| 1413 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
| 1414 if (pred_begin(FI) == pred_end(FI)) |
| 1415 ++NumEntryNodes; |
| 1416 } |
| 1417 if (NumEntryNodes != 1) |
| 1418 return false; |
| 1419 |
| 1420 // List of all interesting memory accesses. |
| 1421 MapVector<Value*, unsigned> InterestingAccess; |
| 1422 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) |
| 1423 getInterestingAccesses(*FI, InterestingAccess); |
| 1424 |
| 1425 std::vector<std::vector<BasicBlock*> > SCCBlocks; |
| 1426 |
| 1427 // Add SCCs in the topological order (the entry node goes last). |
| 1428 for (scc_iterator<Function*> SCCI = scc_begin(&F), SCCE = scc_end(&F); |
| 1429 SCCI != SCCE; ++SCCI) { |
| 1430 SCCBlocks.push_back(*SCCI); |
| 1431 } |
| 1432 |
| 1433 // Reverse order, so the entry node goes first. |
| 1434 std::reverse(SCCBlocks.begin(), SCCBlocks.end()); |
| 1435 |
| 1436 // Vector of SCCs. |
| 1437 std::vector<SCCBlock> SCC; |
| 1438 |
| 1439 // Maps each BasicBlock to the index of the corresponding SCC. |
| 1440 std::map<BasicBlock*, unsigned> SCCMapping; |
| 1441 |
| 1442 for (size_t i = 0; i < SCCBlocks.size(); ++i) |
| 1443 sccAddComponent(SCCBlocks[i], SCCMapping, SCC); |
| 1444 |
| 1445 // Analyze SCCs in the topological order. |
| 1446 for (unsigned I = 0; I < SCC.size(); ++I) |
| 1447 sccAnalyzeComponent(I, SCC, InterestingAccess, ToInstrument, NoReturnCalls); |
| 1448 |
| 1449 return true; |
| 1450 } |
| 1451 |
1180 static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) { | 1452 static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) { |
1181 if (ShadowRedzoneSize == 1) return PoisonByte; | 1453 if (ShadowRedzoneSize == 1) return PoisonByte; |
1182 if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte; | 1454 if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte; |
1183 if (ShadowRedzoneSize == 4) | 1455 if (ShadowRedzoneSize == 4) |
1184 return (PoisonByte << 24) + (PoisonByte << 16) + | 1456 return (PoisonByte << 24) + (PoisonByte << 16) + |
1185 (PoisonByte << 8) + (PoisonByte); | 1457 (PoisonByte << 8) + (PoisonByte); |
1186 llvm_unreachable("ShadowRedzoneSize is either 1, 2 or 4"); | 1458 llvm_unreachable("ShadowRedzoneSize is either 1, 2 or 4"); |
1187 } | 1459 } |
1188 | 1460 |
1189 static void PoisonShadowPartialRightRedzone(uint8_t *Shadow, | 1461 static void PoisonShadowPartialRightRedzone(uint8_t *Shadow, |
(...skipping 18 matching lines...) Expand all Loading... |
1208 // FIXME: remove once the bug 11395 is fixed. | 1480 // FIXME: remove once the bug 11395 is fixed. |
1209 bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) { | 1481 bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) { |
1210 if (LongSize != 32) return false; | 1482 if (LongSize != 32) return false; |
1211 CallInst *CI = dyn_cast<CallInst>(I); | 1483 CallInst *CI = dyn_cast<CallInst>(I); |
1212 if (!CI || !CI->isInlineAsm()) return false; | 1484 if (!CI || !CI->isInlineAsm()) return false; |
1213 if (CI->getNumArgOperands() <= 5) return false; | 1485 if (CI->getNumArgOperands() <= 5) return false; |
1214 // We have inline assembly with quite a few arguments. | 1486 // We have inline assembly with quite a few arguments. |
1215 return true; | 1487 return true; |
1216 } | 1488 } |
1217 | 1489 |
| 1490 bool AddressSanitizer::CanInstrumentFunction(Function &F) { |
| 1491 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
| 1492 for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); |
| 1493 BI != BE; ++BI) { |
| 1494 if (LooksLikeCodeInBug11395(BI)) |
| 1495 return false; |
| 1496 } |
| 1497 } |
| 1498 return true; |
| 1499 } |
| 1500 |
1218 void FunctionStackPoisoner::initializeCallbacks(Module &M) { | 1501 void FunctionStackPoisoner::initializeCallbacks(Module &M) { |
1219 IRBuilder<> IRB(*C); | 1502 IRBuilder<> IRB(*C); |
1220 AsanStackMallocFunc = checkInterfaceFunction(M.getOrInsertFunction( | 1503 AsanStackMallocFunc = checkInterfaceFunction(M.getOrInsertFunction( |
1221 kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL)); | 1504 kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL)); |
1222 AsanStackFreeFunc = checkInterfaceFunction(M.getOrInsertFunction( | 1505 AsanStackFreeFunc = checkInterfaceFunction(M.getOrInsertFunction( |
1223 kAsanStackFreeName, IRB.getVoidTy(), | 1506 kAsanStackFreeName, IRB.getVoidTy(), |
1224 IntptrTy, IntptrTy, IntptrTy, NULL)); | 1507 IntptrTy, IntptrTy, IntptrTy, NULL)); |
1225 AsanPoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( | 1508 AsanPoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( |
1226 kAsanPoisonStackMemoryName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL)); | 1509 kAsanPoisonStackMemoryName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL)); |
1227 AsanUnpoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( | 1510 AsanUnpoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( |
(...skipping 216 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1444 // AI for incoming values should exist and should all be equal. | 1727 // AI for incoming values should exist and should all be equal. |
1445 if (IncValueAI == 0 || (Res != 0 && IncValueAI != Res)) | 1728 if (IncValueAI == 0 || (Res != 0 && IncValueAI != Res)) |
1446 return 0; | 1729 return 0; |
1447 Res = IncValueAI; | 1730 Res = IncValueAI; |
1448 } | 1731 } |
1449 } | 1732 } |
1450 if (Res != 0) | 1733 if (Res != 0) |
1451 AllocaForValue[V] = Res; | 1734 AllocaForValue[V] = Res; |
1452 return Res; | 1735 return Res; |
1453 } | 1736 } |
OLD | NEW |