1dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// 2ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// 3ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// The LLVM Compiler Infrastructure 4ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// 5ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// This file is distributed under the University of Illinois Open Source 6ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// License. See LICENSE.TXT for details. 7ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// 8ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek//===----------------------------------------------------------------------===// 9ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// 104cc1187e8a04f1f36e8c3656f65097e770bdc437Jordy Rose// This defines PthreadLockChecker, a simple lock -> unlock checker. 114cc1187e8a04f1f36e8c3656f65097e770bdc437Jordy Rose// Also handles XNU locks, which behave similarly enough to share code. 12ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// 13ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek//===----------------------------------------------------------------------===// 14ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 15a0decc9a2481f938e1675b4f7bbd58761a882a36Argyrios Kyrtzidis#include "ClangSACheckers.h" 1655fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 18695fb502825a53ccd178ec1c85c77929d88acb71Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 2018c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 21dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose#include "llvm/ADT/ImmutableList.h" 22ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 23ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenekusing namespace clang; 249ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 25ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 26ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremeneknamespace { 27dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Roseclass PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 286f42b62b6194f53bcbc349f5d17388e1936535d7Dylan Noblesmith mutable OwningPtr<BugType> BT_doublelock; 296f42b62b6194f53bcbc349f5d17388e1936535d7Dylan Noblesmith mutable OwningPtr<BugType> BT_lor; 30dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose enum LockingSemantics { 31dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose NotApplicable = 0, 32dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose PthreadSemantics, 33dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose XNUSemantics 34dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose }; 35ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenekpublic: 36983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 37ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 38dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 39dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose bool isTryLock, enum LockingSemantics semantics) const; 40ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 41dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 42ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek}; 43ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek} // end anonymous namespace 44ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 45ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek// GDM Entry for tracking lock state. 46166d502d5367ceacd1313a33cac43b1048b8524dJordan RoseREGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 47ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 48695fb502825a53ccd178ec1c85c77929d88acb71Argyrios Kyrtzidis 49983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidisvoid PthreadLockChecker::checkPostStmt(const CallExpr *CE, 50983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis CheckerContext &C) const { 518bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 525eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx = C.getLocationContext(); 53b805c8ff133ef0c62df032fa711d6b13c5afd7f4Anna Zaks StringRef FName = C.getCalleeName(CE); 54b805c8ff133ef0c62df032fa711d6b13c5afd7f4Anna Zaks if (FName.empty()) 5590d26a4afdbf6d917a5241ef3b316e1c8337c9b8Douglas Gregor return; 56dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 57dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (CE->getNumArgs() != 1) 58dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose return; 594cc1187e8a04f1f36e8c3656f65097e770bdc437Jordy Rose 60dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (FName == "pthread_mutex_lock" || 61dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "pthread_rwlock_rdlock" || 62dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "pthread_rwlock_wrlock") 635eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 645eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek false, PthreadSemantics); 65dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose else if (FName == "lck_mtx_lock" || 66dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_rw_lock_exclusive" || 67dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_rw_lock_shared") 685eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 695eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek false, XNUSemantics); 70dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose else if (FName == "pthread_mutex_trylock" || 71dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "pthread_rwlock_tryrdlock" || 72dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "pthread_rwlock_tryrwlock") 735eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 745eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek true, PthreadSemantics); 75dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose else if (FName == "lck_mtx_try_lock" || 76dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_rw_try_lock_exclusive" || 77dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_rw_try_lock_shared") 785eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 795eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek true, XNUSemantics); 80dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose else if (FName == "pthread_mutex_unlock" || 81dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "pthread_rwlock_unlock" || 82dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_mtx_unlock" || 83dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose FName == "lck_rw_done") 845eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 85ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek} 86ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 87ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenekvoid PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 88dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose SVal lock, bool isTryLock, 89dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose enum LockingSemantics semantics) const { 90ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 91ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek const MemRegion *lockR = lock.getAsRegion(); 92ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek if (!lockR) 93ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek return; 94ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 958bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 96ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 975eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal X = state->getSVal(CE, C.getLocationContext()); 98ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek if (X.isUnknownOrUndef()) 99ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek return; 100ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 1015251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie DefinedSVal retVal = X.castAs<DefinedSVal>(); 102dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 103dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (state->contains<LockSet>(lockR)) { 104dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (!BT_doublelock) 105dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose BT_doublelock.reset(new BugType("Double locking", "Lock checker")); 106dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose ExplodedNode *N = C.generateSink(); 107dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (!N) 108dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose return; 109e172e8b9e7fc67d7d03589af7e92fe777afcf33aAnna Zaks BugReport *report = new BugReport(*BT_doublelock, 110dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "This lock has already " 111dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "been acquired", N); 112dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose report->addRange(CE->getArg(0)->getSourceRange()); 113785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose C.emitReport(report); 114dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose return; 115dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose } 116dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 1178bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef lockSucc = state; 118ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek if (isTryLock) { 119dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // Bifurcate the state, and allow a mode where the lock acquisition fails. 1208bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef lockFail; 121dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose switch (semantics) { 122dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose case PthreadSemantics: 123dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose llvm::tie(lockFail, lockSucc) = state->assume(retVal); 124dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose break; 125dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose case XNUSemantics: 126dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose llvm::tie(lockSucc, lockFail) = state->assume(retVal); 127dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose break; 128dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose default: 129dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose llvm_unreachable("Unknown tryLock locking semantics"); 130dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose } 131ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek assert(lockFail && lockSucc); 1320bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(lockFail); 133dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 134dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose } else if (semantics == PthreadSemantics) { 135dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // Assume that the return value was 0. 13628f47b92e760ccf641ac91cb0fe1c12d9ca89795Ted Kremenek lockSucc = state->assume(retVal, false); 137ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek assert(lockSucc); 138dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 139dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose } else { 140dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // XNU locking semantics return void on non-try locks 141dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose assert((semantics == XNUSemantics) && "Unknown locking semantics"); 142dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose lockSucc = state; 143ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek } 144ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 145dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // Record that the lock was acquired. 146ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek lockSucc = lockSucc->add<LockSet>(lockR); 1470bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(lockSucc); 148ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek} 149ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 150ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenekvoid PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 151983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis SVal lock) const { 152ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 153ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek const MemRegion *lockR = lock.getAsRegion(); 154ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek if (!lockR) 155ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek return; 156ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 1578bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = C.getState(); 158166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose LockSetTy LS = state->get<LockSet>(); 159ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 160dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // FIXME: Better analysis requires IPA for wrappers. 161dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // FIXME: check for double unlocks 162dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (LS.isEmpty()) 163ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek return; 164ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek 165dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose const MemRegion *firstLockR = LS.getHead(); 166dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (firstLockR != lockR) { 167dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (!BT_lor) 168dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); 169dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose ExplodedNode *N = C.generateSink(); 170dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose if (!N) 171dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose return; 172e172e8b9e7fc67d7d03589af7e92fe777afcf33aAnna Zaks BugReport *report = new BugReport(*BT_lor, 173dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "This was not the most " 174dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "recently acquired lock. " 175dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "Possible lock order " 176dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose "reversal", N); 177dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose report->addRange(CE->getArg(0)->getSourceRange()); 178785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose C.emitReport(report); 179dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose return; 180dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose } 181dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 182dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose // Record that the lock was released. 183dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose state = state->set<LockSet>(LS.getTail()); 1840bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks C.addTransition(state); 185ac9bea8bb7a4f1821d63aaa926b60062311b2aa3Ted Kremenek} 186983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis 187dcb1d5d681d857eb7f534dec1f2b3d5a9f81d1f1Jordy Rose 188983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidisvoid ento::registerPthreadLockChecker(CheckerManager &mgr) { 189983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis mgr.registerChecker<PthreadLockChecker>(); 190983326f32c746f5e47161a73758e4d363263dd2cArgyrios Kyrtzidis} 191