PthreadLockChecker.cpp revision 5f9e272e632e951b1efe824cd16acb4d96077930
1a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// 2a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// 3a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// The LLVM Compiler Infrastructure 4a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// 5a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// This file is distributed under the University of Illinois Open Source 6a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// License. See LICENSE.TXT for details. 7a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// 8a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown//===----------------------------------------------------------------------===// 9a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// 10a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// This defines PthreadLockChecker, a simple lock -> unlock checker. 11a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// Also handles XNU locks, which behave similarly enough to share code. 12a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown// 13a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown//===----------------------------------------------------------------------===// 14a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 15a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown#include "ClangSACheckers.h" 16a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown#include "clang/StaticAnalyzer/Core/Checker.h" 17a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown#include "clang/StaticAnalyzer/Core/CheckerManager.h" 18a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19f9390605bacda7bbe8ea33aa0a39c1581ff6aea2Lorenzo Colitti#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h" 21cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti#include "llvm/ADT/ImmutableList.h" 22d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti 23a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drownusing namespace clang; 24a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drownusing namespace ento; 25a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 26a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drownnamespace { 27a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drownclass PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 28a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown mutable llvm::OwningPtr<BugType> BT_doublelock; 29ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti mutable llvm::OwningPtr<BugType> BT_lor; 30ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti enum LockingSemantics { 31ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti NotApplicable = 0, 32ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti PthreadSemantics, 33ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti XNUSemantics 34ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti }; 35ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colittipublic: 36a4454bfda99803c287b78f8d1cd7bdc1b56065dbLorenzo Colitti void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 37ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 38ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 39ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti bool isTryLock, enum LockingSemantics semantics) const; 40ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 41ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 42ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti}; 43ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti} // end anonymous namespace 44ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 45ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti// GDM Entry for tracking lock state. 46ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colittinamespace { class LockSet {}; } 47ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colittinamespace clang { 48d90841824dc00f65a48a789396c7f428807432caLorenzo Colittinamespace ento { 49cd70b354eb985678175904a937085bed6094af77Lorenzo Colittitemplate <> struct GRStateTrait<LockSet> : 50d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti public GRStatePartialTrait<llvm::ImmutableList<const MemRegion*> > { 51d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti static void* GDMIndex() { static int x = 0; return &x; } 52a4454bfda99803c287b78f8d1cd7bdc1b56065dbLorenzo Colitti}; 53d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti} // end GR namespace 54d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti} // end clang namespace 55ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 56d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti 57d90841824dc00f65a48a789396c7f428807432caLorenzo Colittivoid PthreadLockChecker::checkPostStmt(const CallExpr *CE, 58d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti CheckerContext &C) const { 59d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti const GRState *state = C.getState(); 60d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti const Expr *Callee = CE->getCallee(); 61ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl(); 62ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 63ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti if (!FD) 64ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti return; 65ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 66ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti // Get the name of the callee. 67ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti IdentifierInfo *II = FD->getIdentifier(); 68ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti if (!II) // if no identifier, not a simple C function 69ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti return; 70ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti StringRef FName = II->getName(); 71ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 72ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti if (CE->getNumArgs() != 1) 73ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti return; 74ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 75ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti if (FName == "pthread_mutex_lock" || 76ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "pthread_rwlock_rdlock" || 77ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "pthread_rwlock_wrlock") 78ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics); 79cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti else if (FName == "lck_mtx_lock" || 80cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti FName == "lck_rw_lock_exclusive" || 81ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "lck_rw_lock_shared") 82cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics); 83cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti else if (FName == "pthread_mutex_trylock" || 84cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti FName == "pthread_rwlock_tryrdlock" || 85ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "pthread_rwlock_tryrwlock") 86ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, PthreadSemantics); 87ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti else if (FName == "lck_mtx_try_lock" || 88ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "lck_rw_try_lock_exclusive" || 89ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "lck_rw_try_lock_shared") 90ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, XNUSemantics); 91ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti else if (FName == "pthread_mutex_unlock" || 92ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "pthread_rwlock_unlock" || 93ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "lck_mtx_unlock" || 94ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti FName == "lck_rw_done") 95ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti ReleaseLock(C, CE, state->getSVal(CE->getArg(0))); 96ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti} 97ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 98ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colittivoid PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 99ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti SVal lock, bool isTryLock, 100ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti enum LockingSemantics semantics) const { 101ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 102ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti const MemRegion *lockR = lock.getAsRegion(); 103ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti if (!lockR) 104ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti return; 105ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 106a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown const GRState *state = C.getState(); 107a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 108a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown SVal X = state->getSVal(CE); 109a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown if (X.isUnknownOrUndef()) 110a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown return; 111a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 112a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown DefinedSVal retVal = cast<DefinedSVal>(X); 113a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 114a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 115a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 116a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown if (state->contains<LockSet>(lockR)) { 117d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti if (!BT_doublelock) 118d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 119a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown ExplodedNode *N = C.generateSink(); 120a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown if (!N) 121d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti return; 122a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown EnhancedBugReport *report = new EnhancedBugReport(*BT_doublelock, 123d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti "This lock has already " 124d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti "been acquired", N); 125cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti report->addRange(CE->getArg(0)->getSourceRange()); 126d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti C.EmitReport(report); 127d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti return; 128d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti } 129d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti 130d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti const GRState *lockSucc = state; 131d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti if (isTryLock) { 132d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti // Bifurcate the state, and allow a mode where the lock acquisition fails. 133d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti const GRState *lockFail; 134d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti switch (semantics) { 135d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti case PthreadSemantics: 136d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti llvm::tie(lockFail, lockSucc) = state->assume(retVal); 137d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti break; 138ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti case XNUSemantics: 139ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti llvm::tie(lockSucc, lockFail) = state->assume(retVal); 140cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti break; 141cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti default: 142cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti llvm_unreachable("Unknown tryLock locking semantics"); 143cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti break; 1449477a464bd70849bcddcb8d11613cff117235cb0Lorenzo Colitti } 145cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti assert(lockFail && lockSucc); 146cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti C.addTransition(lockFail); 147cd70b354eb985678175904a937085bed6094af77Lorenzo Colitti 148a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown } else if (semantics == PthreadSemantics) { 149a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown // Assume that the return value was 0. 150a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown lockSucc = state->assume(retVal, false); 151d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti assert(lockSucc); 152d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti 153a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown } else { 154a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown // XNU locking semantics return void on non-try locks 155d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti assert((semantics == XNUSemantics) && "Unknown locking semantics"); 156a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown lockSucc = state; 157d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti } 158d90841824dc00f65a48a789396c7f428807432caLorenzo Colitti 159a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown // Record that the lock was acquired. 160a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown lockSucc = lockSucc->add<LockSet>(lockR); 161a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown C.addTransition(lockSucc); 162a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown} 163a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown 164a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drownvoid PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 165a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown SVal lock) const { 166ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti 167ee80ca65907d214e2483e315a1ba7f610184de03Lorenzo Colitti const MemRegion *lockR = lock.getAsRegion(); 168a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown if (!lockR) 169a45056e35c1af2a0f0a6eed258fd5fdf4846a79fDaniel Drown return; 17057d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 17157d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti const GRState *state = C.getState(); 17257d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>(); 17357d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 17457d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti // FIXME: Better analysis requires IPA for wrappers. 17557d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti // FIXME: check for double unlocks 17657d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti if (LS.isEmpty()) 17757d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti return; 17857d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 17957d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti const MemRegion *firstLockR = LS.getHead(); 18057d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti if (firstLockR != lockR) { 18157d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti if (!BT_lor) 18257d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 18357d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti ExplodedNode *N = C.generateSink(); 18457d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti if (!N) 18557d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti return; 18657d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti EnhancedBugReport *report = new EnhancedBugReport(*BT_lor, 18757d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti "This was not the most " 18857d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti "recently acquired lock. " 18957d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti "Possible lock order " 19057d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti "reversal", N); 19157d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti report->addRange(CE->getArg(0)->getSourceRange()); 19257d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti C.EmitReport(report); 19357d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti return; 19457d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti } 19557d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 19657d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti // Record that the lock was released. 19757d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti state = state->set<LockSet>(LS.getTail()); 19857d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti C.addTransition(state); 19957d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti} 20057d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 20157d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti 20257d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colittivoid ento::registerPthreadLockChecker(CheckerManager &mgr) { 20357d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti mgr.registerChecker<PthreadLockChecker>(); 20457d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti} 20557d480d2b425ef20d8b6f84abd4e9e3209fa9422Lorenzo Colitti