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