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 llvm::OwningPtr<BugType> BT_doublelock; 29 mutable llvm::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 const ProgramState *state = C.getState(); 60 const Expr *Callee = CE->getCallee(); 61 const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl(); 62 63 if (!FD) 64 return; 65 66 // Get the name of the callee. 67 IdentifierInfo *II = FD->getIdentifier(); 68 if (!II) // if no identifier, not a simple C function 69 return; 70 StringRef FName = II->getName(); 71 72 if (CE->getNumArgs() != 1) 73 return; 74 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 ProgramState *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 if (state->contains<LockSet>(lockR)) { 115 if (!BT_doublelock) 116 BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 117 ExplodedNode *N = C.generateSink(); 118 if (!N) 119 return; 120 BugReport *report = new BugReport(*BT_doublelock, 121 "This lock has already " 122 "been acquired", N); 123 report->addRange(CE->getArg(0)->getSourceRange()); 124 C.EmitReport(report); 125 return; 126 } 127 128 const ProgramState *lockSucc = state; 129 if (isTryLock) { 130 // Bifurcate the state, and allow a mode where the lock acquisition fails. 131 const ProgramState *lockFail; 132 switch (semantics) { 133 case PthreadSemantics: 134 llvm::tie(lockFail, lockSucc) = state->assume(retVal); 135 break; 136 case XNUSemantics: 137 llvm::tie(lockSucc, lockFail) = state->assume(retVal); 138 break; 139 default: 140 llvm_unreachable("Unknown tryLock locking semantics"); 141 break; 142 } 143 assert(lockFail && lockSucc); 144 C.addTransition(lockFail); 145 146 } else if (semantics == PthreadSemantics) { 147 // Assume that the return value was 0. 148 lockSucc = state->assume(retVal, false); 149 assert(lockSucc); 150 151 } else { 152 // XNU locking semantics return void on non-try locks 153 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 154 lockSucc = state; 155 } 156 157 // Record that the lock was acquired. 158 lockSucc = lockSucc->add<LockSet>(lockR); 159 C.addTransition(lockSucc); 160 } 161 162 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 163 SVal lock) const { 164 165 const MemRegion *lockR = lock.getAsRegion(); 166 if (!lockR) 167 return; 168 169 const ProgramState *state = C.getState(); 170 llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 171 172 // FIXME: Better analysis requires IPA for wrappers. 173 // FIXME: check for double unlocks 174 if (LS.isEmpty()) 175 return; 176 177 const MemRegion *firstLockR = LS.getHead(); 178 if (firstLockR != lockR) { 179 if (!BT_lor) 180 BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 181 ExplodedNode *N = C.generateSink(); 182 if (!N) 183 return; 184 BugReport *report = new BugReport(*BT_lor, 185 "This was not the most " 186 "recently acquired lock. " 187 "Possible lock order " 188 "reversal", N); 189 report->addRange(CE->getArg(0)->getSourceRange()); 190 C.EmitReport(report); 191 return; 192 } 193 194 // Record that the lock was released. 195 state = state->set<LockSet>(LS.getTail()); 196 C.addTransition(state); 197 } 198 199 200 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 201 mgr.registerChecker<PthreadLockChecker>(); 202 } 203