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