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. Eventually 11 // this shouldn't be registered with ExprEngineInternalChecks. 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/BugReporter.h" 20 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h" 22 #include "llvm/ADT/ImmutableList.h" 23 24 using namespace clang; 25 using namespace ento; 26 27 namespace { 28 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 29 mutable llvm::OwningPtr<BugType> BT_doublelock; 30 mutable llvm::OwningPtr<BugType> BT_lor; 31 enum LockingSemantics { 32 NotApplicable = 0, 33 PthreadSemantics, 34 XNUSemantics 35 }; 36 public: 37 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 38 39 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 40 bool isTryLock, enum LockingSemantics semantics) const; 41 42 void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 43 }; 44 } // end anonymous namespace 45 46 // GDM Entry for tracking lock state. 47 namespace { class LockSet {}; } 48 namespace clang { 49 namespace ento { 50 template <> struct GRStateTrait<LockSet> : 51 public GRStatePartialTrait<llvm::ImmutableList<const MemRegion*> > { 52 static void* GDMIndex() { static int x = 0; return &x; } 53 }; 54 } // end GR namespace 55 } // end clang namespace 56 57 58 void PthreadLockChecker::checkPostStmt(const CallExpr *CE, 59 CheckerContext &C) const { 60 const GRState *state = C.getState(); 61 const Expr *Callee = CE->getCallee(); 62 const FunctionTextRegion *R = 63 dyn_cast_or_null<FunctionTextRegion>(state->getSVal(Callee).getAsRegion()); 64 65 if (!R) 66 return; 67 68 IdentifierInfo *II = R->getDecl()->getIdentifier(); 69 if (!II) // if no identifier, not a simple C function 70 return; 71 llvm::StringRef FName = II->getName(); 72 73 if (CE->getNumArgs() != 1) 74 return; 75 if (FName == "pthread_mutex_lock" || 76 FName == "pthread_rwlock_rdlock" || 77 FName == "pthread_rwlock_wrlock") 78 AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics); 79 else if (FName == "lck_mtx_lock" || 80 FName == "lck_rw_lock_exclusive" || 81 FName == "lck_rw_lock_shared") 82 AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics); 83 else if (FName == "pthread_mutex_trylock" || 84 FName == "pthread_rwlock_tryrdlock" || 85 FName == "pthread_rwlock_tryrwlock") 86 AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, PthreadSemantics); 87 else if (FName == "lck_mtx_try_lock" || 88 FName == "lck_rw_try_lock_exclusive" || 89 FName == "lck_rw_try_lock_shared") 90 AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, XNUSemantics); 91 else if (FName == "pthread_mutex_unlock" || 92 FName == "pthread_rwlock_unlock" || 93 FName == "lck_mtx_unlock" || 94 FName == "lck_rw_done") 95 ReleaseLock(C, CE, state->getSVal(CE->getArg(0))); 96 } 97 98 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 99 SVal lock, bool isTryLock, 100 enum LockingSemantics semantics) const { 101 102 const MemRegion *lockR = lock.getAsRegion(); 103 if (!lockR) 104 return; 105 106 const GRState *state = C.getState(); 107 108 SVal X = state->getSVal(CE); 109 if (X.isUnknownOrUndef()) 110 return; 111 112 DefinedSVal retVal = cast<DefinedSVal>(X); 113 114 llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 115 116 if (state->contains<LockSet>(lockR)) { 117 if (!BT_doublelock) 118 BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 119 ExplodedNode *N = C.generateSink(); 120 if (!N) 121 return; 122 EnhancedBugReport *report = new EnhancedBugReport(*BT_doublelock, 123 "This lock has already " 124 "been acquired", N); 125 report->addRange(CE->getArg(0)->getSourceRange()); 126 C.EmitReport(report); 127 return; 128 } 129 130 const GRState *lockSucc = state; 131 if (isTryLock) { 132 // Bifurcate the state, and allow a mode where the lock acquisition fails. 133 const GRState *lockFail; 134 switch (semantics) { 135 case PthreadSemantics: 136 llvm::tie(lockFail, lockSucc) = state->assume(retVal); 137 break; 138 case XNUSemantics: 139 llvm::tie(lockSucc, lockFail) = state->assume(retVal); 140 break; 141 default: 142 llvm_unreachable("Unknown tryLock locking semantics"); 143 break; 144 } 145 assert(lockFail && lockSucc); 146 C.addTransition(lockFail); 147 148 } else if (semantics == PthreadSemantics) { 149 // Assume that the return value was 0. 150 lockSucc = state->assume(retVal, false); 151 assert(lockSucc); 152 153 } else { 154 // XNU locking semantics return void on non-try locks 155 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 156 lockSucc = state; 157 } 158 159 // Record that the lock was acquired. 160 lockSucc = lockSucc->add<LockSet>(lockR); 161 C.addTransition(lockSucc); 162 } 163 164 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 165 SVal lock) const { 166 167 const MemRegion *lockR = lock.getAsRegion(); 168 if (!lockR) 169 return; 170 171 const GRState *state = C.getState(); 172 llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 173 174 // FIXME: Better analysis requires IPA for wrappers. 175 // FIXME: check for double unlocks 176 if (LS.isEmpty()) 177 return; 178 179 const MemRegion *firstLockR = LS.getHead(); 180 if (firstLockR != lockR) { 181 if (!BT_lor) 182 BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 183 ExplodedNode *N = C.generateSink(); 184 if (!N) 185 return; 186 EnhancedBugReport *report = new EnhancedBugReport(*BT_lor, 187 "This was not the most " 188 "recently acquired lock. " 189 "Possible lock order " 190 "reversal", N); 191 report->addRange(CE->getArg(0)->getSourceRange()); 192 C.EmitReport(report); 193 return; 194 } 195 196 // Record that the lock was released. 197 state = state->set<LockSet>(LS.getTail()); 198 C.addTransition(state); 199 } 200 201 202 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 203 mgr.registerChecker<PthreadLockChecker>(); 204 } 205