1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This defines PthreadLockChecker, a simple lock -> unlock checker. 11 // Also handles XNU locks, which behave similarly enough to share code. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "ClangSACheckers.h" 16 #include "clang/StaticAnalyzer/Core/Checker.h" 17 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 21 #include "llvm/ADT/ImmutableList.h" 22 23 using namespace clang; 24 using namespace ento; 25 26 namespace { 27 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 28 mutable OwningPtr<BugType> BT_doublelock; 29 mutable OwningPtr<BugType> BT_lor; 30 enum LockingSemantics { 31 NotApplicable = 0, 32 PthreadSemantics, 33 XNUSemantics 34 }; 35 public: 36 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 37 38 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 39 bool isTryLock, enum LockingSemantics semantics) const; 40 41 void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 42 }; 43 } // end anonymous namespace 44 45 // GDM Entry for tracking lock state. 46 namespace { class LockSet {}; } 47 namespace clang { 48 namespace ento { 49 template <> struct ProgramStateTrait<LockSet> : 50 public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > { 51 static void *GDMIndex() { static int x = 0; return &x; } 52 }; 53 } // end of ento (ProgramState) namespace 54 } // end clang namespace 55 56 57 void PthreadLockChecker::checkPostStmt(const CallExpr *CE, 58 CheckerContext &C) const { 59 ProgramStateRef state = C.getState(); 60 const LocationContext *LCtx = C.getLocationContext(); 61 StringRef FName = C.getCalleeName(CE); 62 if (FName.empty()) 63 return; 64 65 if (CE->getNumArgs() != 1) 66 return; 67 68 if (FName == "pthread_mutex_lock" || 69 FName == "pthread_rwlock_rdlock" || 70 FName == "pthread_rwlock_wrlock") 71 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 72 false, PthreadSemantics); 73 else if (FName == "lck_mtx_lock" || 74 FName == "lck_rw_lock_exclusive" || 75 FName == "lck_rw_lock_shared") 76 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 77 false, XNUSemantics); 78 else if (FName == "pthread_mutex_trylock" || 79 FName == "pthread_rwlock_tryrdlock" || 80 FName == "pthread_rwlock_tryrwlock") 81 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 82 true, PthreadSemantics); 83 else if (FName == "lck_mtx_try_lock" || 84 FName == "lck_rw_try_lock_exclusive" || 85 FName == "lck_rw_try_lock_shared") 86 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 87 true, XNUSemantics); 88 else if (FName == "pthread_mutex_unlock" || 89 FName == "pthread_rwlock_unlock" || 90 FName == "lck_mtx_unlock" || 91 FName == "lck_rw_done") 92 ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 93 } 94 95 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 96 SVal lock, bool isTryLock, 97 enum LockingSemantics semantics) const { 98 99 const MemRegion *lockR = lock.getAsRegion(); 100 if (!lockR) 101 return; 102 103 ProgramStateRef state = C.getState(); 104 105 SVal X = state->getSVal(CE, C.getLocationContext()); 106 if (X.isUnknownOrUndef()) 107 return; 108 109 DefinedSVal retVal = cast<DefinedSVal>(X); 110 111 if (state->contains<LockSet>(lockR)) { 112 if (!BT_doublelock) 113 BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 114 ExplodedNode *N = C.generateSink(); 115 if (!N) 116 return; 117 BugReport *report = new BugReport(*BT_doublelock, 118 "This lock has already " 119 "been acquired", N); 120 report->addRange(CE->getArg(0)->getSourceRange()); 121 C.EmitReport(report); 122 return; 123 } 124 125 ProgramStateRef lockSucc = state; 126 if (isTryLock) { 127 // Bifurcate the state, and allow a mode where the lock acquisition fails. 128 ProgramStateRef lockFail; 129 switch (semantics) { 130 case PthreadSemantics: 131 llvm::tie(lockFail, lockSucc) = state->assume(retVal); 132 break; 133 case XNUSemantics: 134 llvm::tie(lockSucc, lockFail) = state->assume(retVal); 135 break; 136 default: 137 llvm_unreachable("Unknown tryLock locking semantics"); 138 } 139 assert(lockFail && lockSucc); 140 C.addTransition(lockFail); 141 142 } else if (semantics == PthreadSemantics) { 143 // Assume that the return value was 0. 144 lockSucc = state->assume(retVal, false); 145 assert(lockSucc); 146 147 } else { 148 // XNU locking semantics return void on non-try locks 149 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 150 lockSucc = state; 151 } 152 153 // Record that the lock was acquired. 154 lockSucc = lockSucc->add<LockSet>(lockR); 155 C.addTransition(lockSucc); 156 } 157 158 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 159 SVal lock) const { 160 161 const MemRegion *lockR = lock.getAsRegion(); 162 if (!lockR) 163 return; 164 165 ProgramStateRef state = C.getState(); 166 llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 167 168 // FIXME: Better analysis requires IPA for wrappers. 169 // FIXME: check for double unlocks 170 if (LS.isEmpty()) 171 return; 172 173 const MemRegion *firstLockR = LS.getHead(); 174 if (firstLockR != lockR) { 175 if (!BT_lor) 176 BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 177 ExplodedNode *N = C.generateSink(); 178 if (!N) 179 return; 180 BugReport *report = new BugReport(*BT_lor, 181 "This was not the most " 182 "recently acquired lock. " 183 "Possible lock order " 184 "reversal", N); 185 report->addRange(CE->getArg(0)->getSourceRange()); 186 C.EmitReport(report); 187 return; 188 } 189 190 // Record that the lock was released. 191 state = state->set<LockSet>(LS.getTail()); 192 C.addTransition(state); 193 } 194 195 196 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 197 mgr.registerChecker<PthreadLockChecker>(); 198 } 199
