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/BugReporter/BugType.h" 17 #include "clang/StaticAnalyzer/Core/Checker.h" 18 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.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 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 47 48 49 void PthreadLockChecker::checkPostStmt(const CallExpr *CE, 50 CheckerContext &C) const { 51 ProgramStateRef state = C.getState(); 52 const LocationContext *LCtx = C.getLocationContext(); 53 StringRef FName = C.getCalleeName(CE); 54 if (FName.empty()) 55 return; 56 57 if (CE->getNumArgs() != 1) 58 return; 59 60 if (FName == "pthread_mutex_lock" || 61 FName == "pthread_rwlock_rdlock" || 62 FName == "pthread_rwlock_wrlock") 63 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 64 false, PthreadSemantics); 65 else if (FName == "lck_mtx_lock" || 66 FName == "lck_rw_lock_exclusive" || 67 FName == "lck_rw_lock_shared") 68 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 69 false, XNUSemantics); 70 else if (FName == "pthread_mutex_trylock" || 71 FName == "pthread_rwlock_tryrdlock" || 72 FName == "pthread_rwlock_tryrwlock") 73 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 74 true, PthreadSemantics); 75 else if (FName == "lck_mtx_try_lock" || 76 FName == "lck_rw_try_lock_exclusive" || 77 FName == "lck_rw_try_lock_shared") 78 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 79 true, XNUSemantics); 80 else if (FName == "pthread_mutex_unlock" || 81 FName == "pthread_rwlock_unlock" || 82 FName == "lck_mtx_unlock" || 83 FName == "lck_rw_done") 84 ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 85 } 86 87 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 88 SVal lock, bool isTryLock, 89 enum LockingSemantics semantics) const { 90 91 const MemRegion *lockR = lock.getAsRegion(); 92 if (!lockR) 93 return; 94 95 ProgramStateRef state = C.getState(); 96 97 SVal X = state->getSVal(CE, C.getLocationContext()); 98 if (X.isUnknownOrUndef()) 99 return; 100 101 DefinedSVal retVal = X.castAs<DefinedSVal>(); 102 103 if (state->contains<LockSet>(lockR)) { 104 if (!BT_doublelock) 105 BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 106 ExplodedNode *N = C.generateSink(); 107 if (!N) 108 return; 109 BugReport *report = new BugReport(*BT_doublelock, 110 "This lock has already " 111 "been acquired", N); 112 report->addRange(CE->getArg(0)->getSourceRange()); 113 C.emitReport(report); 114 return; 115 } 116 117 ProgramStateRef lockSucc = state; 118 if (isTryLock) { 119 // Bifurcate the state, and allow a mode where the lock acquisition fails. 120 ProgramStateRef lockFail; 121 switch (semantics) { 122 case PthreadSemantics: 123 llvm::tie(lockFail, lockSucc) = state->assume(retVal); 124 break; 125 case XNUSemantics: 126 llvm::tie(lockSucc, lockFail) = state->assume(retVal); 127 break; 128 default: 129 llvm_unreachable("Unknown tryLock locking semantics"); 130 } 131 assert(lockFail && lockSucc); 132 C.addTransition(lockFail); 133 134 } else if (semantics == PthreadSemantics) { 135 // Assume that the return value was 0. 136 lockSucc = state->assume(retVal, false); 137 assert(lockSucc); 138 139 } else { 140 // XNU locking semantics return void on non-try locks 141 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 142 lockSucc = state; 143 } 144 145 // Record that the lock was acquired. 146 lockSucc = lockSucc->add<LockSet>(lockR); 147 C.addTransition(lockSucc); 148 } 149 150 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 151 SVal lock) const { 152 153 const MemRegion *lockR = lock.getAsRegion(); 154 if (!lockR) 155 return; 156 157 ProgramStateRef state = C.getState(); 158 LockSetTy LS = state->get<LockSet>(); 159 160 // FIXME: Better analysis requires IPA for wrappers. 161 // FIXME: check for double unlocks 162 if (LS.isEmpty()) 163 return; 164 165 const MemRegion *firstLockR = LS.getHead(); 166 if (firstLockR != lockR) { 167 if (!BT_lor) 168 BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 169 ExplodedNode *N = C.generateSink(); 170 if (!N) 171 return; 172 BugReport *report = new BugReport(*BT_lor, 173 "This was not the most " 174 "recently acquired lock. " 175 "Possible lock order " 176 "reversal", N); 177 report->addRange(CE->getArg(0)->getSourceRange()); 178 C.emitReport(report); 179 return; 180 } 181 182 // Record that the lock was released. 183 state = state->set<LockSet>(LS.getTail()); 184 C.addTransition(state); 185 } 186 187 188 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 189 mgr.registerChecker<PthreadLockChecker>(); 190 } 191
