head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.9 netbsd-11-0-RC3:1.1.1.9 netbsd-11-0-RC2:1.1.1.9 netbsd-11-0-RC1:1.1.1.9 perseant-exfatfs-base-20250801:1.1.1.9 netbsd-11:1.1.1.9.0.10 netbsd-11-base:1.1.1.9 netbsd-10-1-RELEASE:1.1.1.9 perseant-exfatfs-base-20240630:1.1.1.9 perseant-exfatfs:1.1.1.9.0.8 perseant-exfatfs-base:1.1.1.9 netbsd-8-3-RELEASE:1.1.1.6 netbsd-9-4-RELEASE:1.1.1.8 netbsd-10-0-RELEASE:1.1.1.9 netbsd-10-0-RC6:1.1.1.9 netbsd-10-0-RC5:1.1.1.9 netbsd-10-0-RC4:1.1.1.9 netbsd-10-0-RC3:1.1.1.9 netbsd-10-0-RC2:1.1.1.9 netbsd-10-0-RC1:1.1.1.9 netbsd-10:1.1.1.9.0.6 netbsd-10-base:1.1.1.9 netbsd-9-3-RELEASE:1.1.1.8 cjep_sun2x:1.1.1.9.0.4 cjep_sun2x-base:1.1.1.9 cjep_staticlib_x-base1:1.1.1.9 netbsd-9-2-RELEASE:1.1.1.8 cjep_staticlib_x:1.1.1.9.0.2 cjep_staticlib_x-base:1.1.1.9 netbsd-9-1-RELEASE:1.1.1.8 phil-wifi-20200421:1.1.1.9 phil-wifi-20200411:1.1.1.9 phil-wifi-20200406:1.1.1.9 netbsd-8-2-RELEASE:1.1.1.6 netbsd-9-0-RELEASE:1.1.1.8 netbsd-9-0-RC2:1.1.1.8 netbsd-9-0-RC1:1.1.1.8 netbsd-9:1.1.1.8.0.2 netbsd-9-base:1.1.1.8 phil-wifi-20190609:1.1.1.8 netbsd-8-1-RELEASE:1.1.1.6 netbsd-8-1-RC1:1.1.1.6 pgoyette-compat-merge-20190127:1.1.1.7.2.1 pgoyette-compat-20190127:1.1.1.8 pgoyette-compat-20190118:1.1.1.8 pgoyette-compat-1226:1.1.1.8 pgoyette-compat-1126:1.1.1.8 pgoyette-compat-1020:1.1.1.8 pgoyette-compat-0930:1.1.1.8 pgoyette-compat-0906:1.1.1.8 netbsd-7-2-RELEASE:1.1.1.4 pgoyette-compat-0728:1.1.1.8 clang-337282:1.1.1.8 netbsd-8-0-RELEASE:1.1.1.6 phil-wifi:1.1.1.7.0.4 phil-wifi-base:1.1.1.7 pgoyette-compat-0625:1.1.1.7 netbsd-8-0-RC2:1.1.1.6 pgoyette-compat-0521:1.1.1.7 pgoyette-compat-0502:1.1.1.7 pgoyette-compat-0422:1.1.1.7 netbsd-8-0-RC1:1.1.1.6 pgoyette-compat-0415:1.1.1.7 pgoyette-compat-0407:1.1.1.7 pgoyette-compat-0330:1.1.1.7 pgoyette-compat-0322:1.1.1.7 pgoyette-compat-0315:1.1.1.7 netbsd-7-1-2-RELEASE:1.1.1.4 pgoyette-compat:1.1.1.7.0.2 pgoyette-compat-base:1.1.1.7 netbsd-7-1-1-RELEASE:1.1.1.4 clang-319952:1.1.1.7 matt-nb8-mediatek:1.1.1.6.0.10 matt-nb8-mediatek-base:1.1.1.6 clang-309604:1.1.1.7 perseant-stdc-iso10646:1.1.1.6.0.8 perseant-stdc-iso10646-base:1.1.1.6 netbsd-8:1.1.1.6.0.6 netbsd-8-base:1.1.1.6 prg-localcount2-base3:1.1.1.6 prg-localcount2-base2:1.1.1.6 prg-localcount2-base1:1.1.1.6 prg-localcount2:1.1.1.6.0.4 prg-localcount2-base:1.1.1.6 pgoyette-localcount-20170426:1.1.1.6 bouyer-socketcan-base1:1.1.1.6 pgoyette-localcount-20170320:1.1.1.6 netbsd-7-1:1.1.1.4.0.10 netbsd-7-1-RELEASE:1.1.1.4 netbsd-7-1-RC2:1.1.1.4 clang-294123:1.1.1.6 netbsd-7-nhusb-base-20170116:1.1.1.4 bouyer-socketcan:1.1.1.6.0.2 bouyer-socketcan-base:1.1.1.6 clang-291444:1.1.1.6 pgoyette-localcount-20170107:1.1.1.5 netbsd-7-1-RC1:1.1.1.4 pgoyette-localcount-20161104:1.1.1.5 netbsd-7-0-2-RELEASE:1.1.1.4 localcount-20160914:1.1.1.5 netbsd-7-nhusb:1.1.1.4.0.8 netbsd-7-nhusb-base:1.1.1.4 clang-280599:1.1.1.5 pgoyette-localcount-20160806:1.1.1.5 pgoyette-localcount-20160726:1.1.1.5 pgoyette-localcount:1.1.1.5.0.2 pgoyette-localcount-base:1.1.1.5 netbsd-7-0-1-RELEASE:1.1.1.4 clang-261930:1.1.1.5 netbsd-7-0:1.1.1.4.0.6 netbsd-7-0-RELEASE:1.1.1.4 netbsd-7-0-RC3:1.1.1.4 netbsd-7-0-RC2:1.1.1.4 netbsd-7-0-RC1:1.1.1.4 clang-237755:1.1.1.4 clang-232565:1.1.1.4 clang-227398:1.1.1.4 tls-maxphys-base:1.1.1.4 tls-maxphys:1.1.1.4.0.4 netbsd-7:1.1.1.4.0.2 netbsd-7-base:1.1.1.4 clang-215315:1.1.1.4 clang-209886:1.1.1.4 yamt-pagecache:1.1.1.3.0.4 yamt-pagecache-base9:1.1.1.3 tls-earlyentropy:1.1.1.3.0.2 tls-earlyentropy-base:1.1.1.4 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.3 riastradh-drm2-base3:1.1.1.3 clang-202566:1.1.1.3 clang-201163:1.1.1.2 clang-199312:1.1.1.1 clang-198450:1.1.1.1 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.52; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.52; author joerg; state Exp; branches; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.02.14.20.07.25; author joerg; state Exp; branches; next 1.1.1.3; commitid annVkZ1sc17rF6px; 1.1.1.3 date 2014.03.04.19.54.57; author joerg; state Exp; branches 1.1.1.3.2.1 1.1.1.3.4.1; next 1.1.1.4; commitid 29z1hJonZISIXprx; 1.1.1.4 date 2014.05.30.18.14.44; author joerg; state Exp; branches 1.1.1.4.4.1; next 1.1.1.5; commitid 8q0kdlBlCn09GACx; 1.1.1.5 date 2016.02.27.22.12.06; author joerg; state Exp; branches 1.1.1.5.2.1; next 1.1.1.6; commitid tIimz3oDlh1NpBWy; 1.1.1.6 date 2017.01.11.10.35.40; author joerg; state Exp; branches; next 1.1.1.7; commitid CNnUNfII1jgNmxBz; 1.1.1.7 date 2017.08.01.19.35.18; author joerg; state Exp; branches 1.1.1.7.2.1 1.1.1.7.4.1; next 1.1.1.8; commitid pMuDy65V0VicSx1A; 1.1.1.8 date 2018.07.17.18.31.08; author joerg; state Exp; branches; next 1.1.1.9; commitid wDzL46ALjrCZgwKA; 1.1.1.9 date 2019.11.13.22.19.28; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.3.2.1 date 2014.08.10.07.08.10; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.3.4.1 date 2014.03.04.19.54.57; author yamt; state dead; branches; next 1.1.1.3.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.3.4.2 date 2014.05.22.16.18.31; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.4.4.1 date 2014.05.30.18.14.44; author tls; state dead; branches; next 1.1.1.4.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.4.4.2 date 2014.08.19.23.47.31; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.5.2.1 date 2017.03.20.06.52.42; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.7.2.1 date 2018.07.28.04.33.23; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.7.4.1 date 2019.06.10.21.45.28; author christos; state Exp; branches; next 1.1.1.7.4.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.7.4.2 date 2020.04.13.07.46.39; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This defines PthreadLockChecker, a simple lock -> unlock checker. // Also handles XNU locks, which behave similarly enough to share code. // //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/ImmutableList.h" using namespace clang; using namespace ento; namespace { class PthreadLockChecker : public Checker< check::PostStmt > { mutable OwningPtr BT_doublelock; mutable OwningPtr BT_lor; enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; public: void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const; void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; }; } // end anonymous namespace // GDM Entry for tracking lock state. REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) void PthreadLockChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { ProgramStateRef state = C.getState(); const LocationContext *LCtx = C.getLocationContext(); StringRef FName = C.getCalleeName(CE); if (FName.empty()) return; if (CE->getNumArgs() != 1) return; if (FName == "pthread_mutex_lock" || FName == "pthread_rwlock_rdlock" || FName == "pthread_rwlock_wrlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, PthreadSemantics); else if (FName == "lck_mtx_lock" || FName == "lck_rw_lock_exclusive" || FName == "lck_rw_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, XNUSemantics); else if (FName == "pthread_mutex_trylock" || FName == "pthread_rwlock_tryrdlock" || FName == "pthread_rwlock_tryrwlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, PthreadSemantics); else if (FName == "lck_mtx_try_lock" || FName == "lck_rw_try_lock_exclusive" || FName == "lck_rw_try_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, XNUSemantics); else if (FName == "pthread_mutex_unlock" || FName == "pthread_rwlock_unlock" || FName == "lck_mtx_unlock" || FName == "lck_rw_done") ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); } void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); SVal X = state->getSVal(CE, C.getLocationContext()); if (X.isUnknownOrUndef()) return; DefinedSVal retVal = X.castAs(); if (state->contains(lockR)) { if (!BT_doublelock) BT_doublelock.reset(new BugType("Double locking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_doublelock, "This lock has already " "been acquired", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } ProgramStateRef lockSucc = state; if (isTryLock) { // Bifurcate the state, and allow a mode where the lock acquisition fails. ProgramStateRef lockFail; switch (semantics) { case PthreadSemantics: llvm::tie(lockFail, lockSucc) = state->assume(retVal); break; case XNUSemantics: llvm::tie(lockSucc, lockFail) = state->assume(retVal); break; default: llvm_unreachable("Unknown tryLock locking semantics"); } assert(lockFail && lockSucc); C.addTransition(lockFail); } else if (semantics == PthreadSemantics) { // Assume that the return value was 0. lockSucc = state->assume(retVal, false); assert(lockSucc); } else { // XNU locking semantics return void on non-try locks assert((semantics == XNUSemantics) && "Unknown locking semantics"); lockSucc = state; } // Record that the lock was acquired. lockSucc = lockSucc->add(lockR); C.addTransition(lockSucc); } void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); LockSetTy LS = state->get(); // FIXME: Better analysis requires IPA for wrappers. // FIXME: check for double unlocks if (LS.isEmpty()) return; const MemRegion *firstLockR = LS.getHead(); if (firstLockR != lockR) { if (!BT_lor) BT_lor.reset(new BugType("Lock order reversal", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_lor, "This was not the most " "recently acquired lock. " "Possible lock order " "reversal", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } // Record that the lock was released. state = state->set(LS.getTail()); C.addTransition(state); } void ento::registerPthreadLockChecker(CheckerManager &mgr) { mgr.registerChecker(); } @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.2 log @Import Clang 3.5svn r201163. @ text @d72 1 a72 1 FName == "pthread_rwlock_trywrlock") d173 4 a176 4 "This was not the most " "recently acquired lock. " "Possible lock order " "reversal", N); @ 1.1.1.3 log @Import Clang 3.5svn r202566. @ text @d105 1 a105 1 BT_doublelock.reset(new BugType(this, "Double locking", "Lock checker")); d168 1 a168 1 BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); d187 1 @ 1.1.1.3.2.1 log @Rebase. @ text @a26 25 struct LockState { enum Kind { Destroyed, Locked, Unlocked } K; private: LockState(Kind K) : K(K) {} public: static LockState getLocked(void) { return LockState(Locked); } static LockState getUnlocked(void) { return LockState(Unlocked); } static LockState getDestroyed(void) { return LockState(Destroyed); } bool operator==(const LockState &X) const { return K == X.K; } bool isLocked() const { return K == Locked; } bool isUnlocked() const { return K == Unlocked; } bool isDestroyed() const { return K == Destroyed; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } }; d28 2 a29 5 mutable std::unique_ptr BT_doublelock; mutable std::unique_ptr BT_doubleunlock; mutable std::unique_ptr BT_destroylock; mutable std::unique_ptr BT_initlock; mutable std::unique_ptr BT_lor; a41 3 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; a47 1 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) d57 1 a57 1 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) a84 5 else if (FName == "pthread_mutex_destroy" || FName == "lck_mtx_destroy") DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); else if (FName == "pthread_mutex_init") InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); d103 5 a107 13 if (const LockState *LState = state->get(lockR)) { if (LState->isLocked()) { if (!BT_doublelock) BT_doublelock.reset(new BugType(this, "Double locking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_doublelock, "This lock has already been acquired", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); d109 6 a114 4 } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } d123 1 a123 1 std::tie(lockFail, lockSucc) = state->assume(retVal); d126 1 a126 1 std::tie(lockSucc, lockFail) = state->assume(retVal); a146 1 lockSucc = lockSucc->set(lockR, LockState::getLocked()); a157 21 if (const LockState *LState = state->get(lockR)) { if (LState->isUnlocked()) { if (!BT_doubleunlock) BT_doubleunlock.reset(new BugType(this, "Double unlocking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_doubleunlock, "This lock has already been unlocked", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); return; } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } } d161 10 a170 16 if (!LS.isEmpty()) { const MemRegion *firstLockR = LS.getHead(); if (firstLockR != lockR) { if (!BT_lor) BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_lor, "This was not the most recently " "acquired lock. Possible lock order " "reversal", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); d172 8 a179 3 } // Record that the lock was released. state = state->set(LS.getTail()); d182 2 a183 1 state = state->set(lockR, LockState::getUnlocked()); a186 85 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const LockState *LState = State->get(LockR); if (!LState || LState->isUnlocked()) { State = State->set(LockR, LockState::getDestroyed()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still locked"; } else { Message = "This lock has already been destroyed"; } if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Destroy invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const struct LockState *LState = State->get(LockR); if (!LState || LState->isDestroyed()) { State = State->set(LockR, LockState::getUnlocked()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still being held"; } else { Message = "This lock has already been initialized"; } if (!BT_initlock) BT_initlock.reset(new BugType(this, "Init invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_initlock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const { if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Use destroyed lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, "This lock has already been destroyed", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } @ 1.1.1.4 log @Import Clang 3.5svn r209886. @ text @a26 25 struct LockState { enum Kind { Destroyed, Locked, Unlocked } K; private: LockState(Kind K) : K(K) {} public: static LockState getLocked(void) { return LockState(Locked); } static LockState getUnlocked(void) { return LockState(Unlocked); } static LockState getDestroyed(void) { return LockState(Destroyed); } bool operator==(const LockState &X) const { return K == X.K; } bool isLocked() const { return K == Locked; } bool isUnlocked() const { return K == Unlocked; } bool isDestroyed() const { return K == Destroyed; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } }; d28 2 a29 5 mutable std::unique_ptr BT_doublelock; mutable std::unique_ptr BT_doubleunlock; mutable std::unique_ptr BT_destroylock; mutable std::unique_ptr BT_initlock; mutable std::unique_ptr BT_lor; a41 3 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; a47 1 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) d57 1 a57 1 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) a84 5 else if (FName == "pthread_mutex_destroy" || FName == "lck_mtx_destroy") DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); else if (FName == "pthread_mutex_init") InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); d103 5 a107 13 if (const LockState *LState = state->get(lockR)) { if (LState->isLocked()) { if (!BT_doublelock) BT_doublelock.reset(new BugType(this, "Double locking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_doublelock, "This lock has already been acquired", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); d109 6 a114 4 } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } d123 1 a123 1 std::tie(lockFail, lockSucc) = state->assume(retVal); d126 1 a126 1 std::tie(lockSucc, lockFail) = state->assume(retVal); a146 1 lockSucc = lockSucc->set(lockR, LockState::getLocked()); a157 21 if (const LockState *LState = state->get(lockR)) { if (LState->isUnlocked()) { if (!BT_doubleunlock) BT_doubleunlock.reset(new BugType(this, "Double unlocking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_doubleunlock, "This lock has already been unlocked", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); return; } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } } d161 10 a170 16 if (!LS.isEmpty()) { const MemRegion *firstLockR = LS.getHead(); if (firstLockR != lockR) { if (!BT_lor) BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_lor, "This was not the most recently " "acquired lock. Possible lock order " "reversal", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); d172 8 a179 3 } // Record that the lock was released. state = state->set(LS.getTail()); d182 2 a183 1 state = state->set(lockR, LockState::getUnlocked()); a186 85 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const LockState *LState = State->get(LockR); if (!LState || LState->isUnlocked()) { State = State->set(LockR, LockState::getDestroyed()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still locked"; } else { Message = "This lock has already been destroyed"; } if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Destroy invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const struct LockState *LState = State->get(LockR); if (!LState || LState->isDestroyed()) { State = State->set(LockR, LockState::getUnlocked()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still being held"; } else { Message = "This lock has already been initialized"; } if (!BT_initlock) BT_initlock.reset(new BugType(this, "Init invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_initlock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const { if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Use destroyed lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, "This lock has already been destroyed", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } @ 1.1.1.5 log @Import Clang 3.8.0rc3 r261930. @ text @d35 3 a37 3 static LockState getLocked() { return LockState(Locked); } static LockState getUnlocked() { return LockState(Unlocked); } static LockState getDestroyed() { return LockState(Destroyed); } d65 1 a65 1 d68 1 a68 1 d99 1 a99 1 FName == "lck_rw_lock_shared") d127 1 a127 1 d131 1 a131 1 d133 1 a133 1 d137 1 a137 1 d145 1 a145 1 ExplodedNode *N = C.generateErrorNode(); d148 3 a150 2 auto report = llvm::make_unique( *BT_doublelock, "This lock has already been acquired", N); d152 1 a152 1 C.emitReport(std::move(report)); d187 2 a188 2 // Record that the lock was acquired. d200 1 a200 1 d208 1 a208 1 ExplodedNode *N = C.generateErrorNode(); d211 3 a213 2 auto Report = llvm::make_unique( *BT_doubleunlock, "This lock has already been unlocked", N); d215 1 a215 1 C.emitReport(std::move(Report)); d232 1 a232 1 ExplodedNode *N = C.generateErrorNode(); d235 5 a239 3 auto report = llvm::make_unique( *BT_lor, "This was not the most recently acquired lock. Possible " "lock order reversal", N); d241 1 a241 1 C.emitReport(std::move(report)); d279 1 a279 1 ExplodedNode *N = C.generateErrorNode(); d282 1 a282 1 auto Report = llvm::make_unique(*BT_destroylock, Message, N); d284 1 a284 1 C.emitReport(std::move(Report)); d314 1 a314 1 ExplodedNode *N = C.generateErrorNode(); d317 1 a317 1 auto Report = llvm::make_unique(*BT_initlock, Message, N); d319 1 a319 1 C.emitReport(std::move(Report)); d327 1 a327 1 ExplodedNode *N = C.generateErrorNode(); d330 3 a332 2 auto Report = llvm::make_unique( *BT_destroylock, "This lock has already been destroyed", N); d334 1 a334 1 C.emitReport(std::move(Report)); @ 1.1.1.5.2.1 log @Sync with HEAD @ text @d21 1 @ 1.1.1.6 log @Import Clang pre-4.0.0 r291444. @ text @d21 1 @ 1.1.1.7 log @Import clang r309604 from branches/release_50 @ text @d28 1 a28 7 enum Kind { Destroyed, Locked, Unlocked, UntouchedAndPossiblyDestroyed, UnlockedAndPossiblyDestroyed } K; a36 6 static LockState getUntouchedAndPossiblyDestroyed() { return LockState(UntouchedAndPossiblyDestroyed); } static LockState getUnlockedAndPossiblyDestroyed() { return LockState(UnlockedAndPossiblyDestroyed); } a44 6 bool isUntouchedAndPossiblyDestroyed() const { return K == UntouchedAndPossiblyDestroyed; } bool isUnlockedAndPossiblyDestroyed() const { return K == UnlockedAndPossiblyDestroyed; } d51 1 a51 2 class PthreadLockChecker : public Checker, check::DeadSymbols> { a63 1 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; d69 1 a69 2 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock, enum LockingSemantics semantics) const; a71 3 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const; d75 1 a75 1 // A stack of locks for tracking lock-unlock order. a77 1 // An entry for tracking lock states. a79 3 // Return values for unresolved calls to pthread_mutex_destroy(). REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) d116 3 a118 4 else if (FName == "pthread_mutex_destroy") DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics); else if (FName == "lck_mtx_destroy") DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics); a122 35 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not // sure if the destroy call has succeeded or failed, and the lock enters one of // the 'possibly destroyed' state. There is a short time frame for the // programmer to check the return value to see if the lock was successfully // destroyed. Before we model the next operation over that lock, we call this // function to see if the return value was checked by now and set the lock state // - either to destroyed state or back to its previous state. // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is // successfully destroyed and it returns a non-zero value otherwise. ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex( ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const { const LockState *lstate = state->get(lockR); // Existence in DestroyRetVal ensures existence in LockMap. // Existence in Destroyed also ensures that the lock state for lockR is either // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed. assert(lstate->isUntouchedAndPossiblyDestroyed() || lstate->isUnlockedAndPossiblyDestroyed()); ConstraintManager &CMgr = state->getConstraintManager(); ConditionTruthVal retZero = CMgr.isNull(state, *sym); if (retZero.isConstrainedFalse()) { if (lstate->isUntouchedAndPossiblyDestroyed()) state = state->remove(lockR); else if (lstate->isUnlockedAndPossiblyDestroyed()) state = state->set(lockR, LockState::getUnlocked()); } else state = state->set(lockR, LockState::getDestroyed()); // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is // now resolved. state = state->remove(lockR); return state; } a131 3 const SymbolRef *sym = state->get(lockR); if (sym) state = resolvePossiblyDestroyedMutex(state, lockR, sym); a199 3 const SymbolRef *sym = state->get(lockR); if (sym) state = resolvePossiblyDestroyedMutex(state, lockR, sym); d248 1 a248 2 SVal Lock, enum LockingSemantics semantics) const { a255 4 const SymbolRef *sym = State->get(LockR); if (sym) State = resolvePossiblyDestroyedMutex(State, LockR, sym); d257 4 a260 26 // Checking the return value of the destroy method only in the case of // PthreadSemantics if (semantics == PthreadSemantics) { if (!LState || LState->isUnlocked()) { SymbolRef sym = C.getSVal(CE).getAsSymbol(); if (!sym) { State = State->remove(LockR); C.addTransition(State); return; } State = State->set(LockR, sym); if (LState && LState->isUnlocked()) State = State->set( LockR, LockState::getUnlockedAndPossiblyDestroyed()); else State = State->set( LockR, LockState::getUntouchedAndPossiblyDestroyed()); C.addTransition(State); return; } } else { if (!LState || LState->isUnlocked()) { State = State->set(LockR, LockState::getDestroyed()); C.addTransition(State); return; } d262 1 a290 4 const SymbolRef *sym = State->get(LockR); if (sym) State = resolvePossiblyDestroyedMutex(State, LockR, sym); a330 20 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const { ProgramStateRef State = C.getState(); // TODO: Clean LockMap when a mutex region dies. DestroyRetValTy TrackedSymbols = State->get(); for (DestroyRetValTy::iterator I = TrackedSymbols.begin(), E = TrackedSymbols.end(); I != E; ++I) { const SymbolRef Sym = I->second; const MemRegion *lockR = I->first; bool IsSymDead = SymReaper.isDead(Sym); // Remove the dead symbol from the return value symbols map. if (IsSymDead) State = resolvePossiblyDestroyedMutex(State, lockR, &Sym); } C.addTransition(State); } @ 1.1.1.7.4.1 log @Sync with HEAD @ text @a83 2 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; d110 2 d122 2 a123 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, PthreadSemantics); d127 2 a128 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, XNUSemantics); d132 1 a132 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), d137 2 a138 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), true, XNUSemantics); d143 1 a143 1 ReleaseLock(C, CE, C.getSVal(CE->getArg(0))); d145 1 a145 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), PthreadSemantics); d147 1 a147 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), XNUSemantics); d149 1 a149 1 InitLock(C, CE, C.getSVal(CE->getArg(0))); a186 33 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { LockMapTy LM = State->get(); if (!LM.isEmpty()) { Out << Sep << "Mutex states:" << NL; for (auto I : LM) { I.first->dumpToStream(Out); if (I.second.isLocked()) Out << ": locked"; else if (I.second.isUnlocked()) Out << ": unlocked"; else if (I.second.isDestroyed()) Out << ": destroyed"; else if (I.second.isUntouchedAndPossiblyDestroyed()) Out << ": not tracked, possibly destroyed"; else if (I.second.isUnlockedAndPossiblyDestroyed()) Out << ": unlocked, possibly destroyed"; Out << NL; } } LockSetTy LS = State->get(); if (!LS.isEmpty()) { Out << Sep << "Mutex lock order:" << NL; for (auto I: LS) { I->dumpToStream(Out); Out << NL; } } // TODO: Dump destroyed mutex symbols? } d200 1 a200 1 SVal X = C.getSVal(CE); @ 1.1.1.7.4.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.7.2.1 log @Sync with HEAD @ text @a83 2 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; d110 2 d122 2 a123 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, PthreadSemantics); d127 2 a128 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, XNUSemantics); d132 1 a132 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), d137 2 a138 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), true, XNUSemantics); d143 1 a143 1 ReleaseLock(C, CE, C.getSVal(CE->getArg(0))); d145 1 a145 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), PthreadSemantics); d147 1 a147 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), XNUSemantics); d149 1 a149 1 InitLock(C, CE, C.getSVal(CE->getArg(0))); a186 33 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { LockMapTy LM = State->get(); if (!LM.isEmpty()) { Out << Sep << "Mutex states:" << NL; for (auto I : LM) { I.first->dumpToStream(Out); if (I.second.isLocked()) Out << ": locked"; else if (I.second.isUnlocked()) Out << ": unlocked"; else if (I.second.isDestroyed()) Out << ": destroyed"; else if (I.second.isUntouchedAndPossiblyDestroyed()) Out << ": not tracked, possibly destroyed"; else if (I.second.isUnlockedAndPossiblyDestroyed()) Out << ": unlocked, possibly destroyed"; Out << NL; } } LockSetTy LS = State->get(); if (!LS.isEmpty()) { Out << Sep << "Mutex lock order:" << NL; for (auto I: LS) { I->dumpToStream(Out); Out << NL; } } // TODO: Dump destroyed mutex symbols? } d200 1 a200 1 SVal X = C.getSVal(CE); @ 1.1.1.8 log @Import clang r337282 from trunk @ text @a83 2 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; d110 2 d122 2 a123 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, PthreadSemantics); d127 2 a128 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, XNUSemantics); d132 1 a132 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), d137 2 a138 1 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), true, XNUSemantics); d143 1 a143 1 ReleaseLock(C, CE, C.getSVal(CE->getArg(0))); d145 1 a145 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), PthreadSemantics); d147 1 a147 1 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), XNUSemantics); d149 1 a149 1 InitLock(C, CE, C.getSVal(CE->getArg(0))); a186 33 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { LockMapTy LM = State->get(); if (!LM.isEmpty()) { Out << Sep << "Mutex states:" << NL; for (auto I : LM) { I.first->dumpToStream(Out); if (I.second.isLocked()) Out << ": locked"; else if (I.second.isUnlocked()) Out << ": unlocked"; else if (I.second.isDestroyed()) Out << ": destroyed"; else if (I.second.isUntouchedAndPossiblyDestroyed()) Out << ": not tracked, possibly destroyed"; else if (I.second.isUnlockedAndPossiblyDestroyed()) Out << ": unlocked, possibly destroyed"; Out << NL; } } LockSetTy LS = State->get(); if (!LS.isEmpty()) { Out << Sep << "Mutex lock order:" << NL; for (auto I: LS) { I->dumpToStream(Out); Out << NL; } } // TODO: Dump destroyed mutex symbols? } d200 1 a200 1 SVal X = C.getSVal(CE); @ 1.1.1.9 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.4.4.1 log @file PthreadLockChecker.cpp was added on branch tls-maxphys on 2014-08-19 23:47:31 +0000 @ text @d1 339 @ 1.1.1.4.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 339 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This defines PthreadLockChecker, a simple lock -> unlock checker. // Also handles XNU locks, which behave similarly enough to share code. // //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/ImmutableList.h" using namespace clang; using namespace ento; namespace { struct LockState { enum Kind { Destroyed, Locked, Unlocked } K; private: LockState(Kind K) : K(K) {} public: static LockState getLocked(void) { return LockState(Locked); } static LockState getUnlocked(void) { return LockState(Unlocked); } static LockState getDestroyed(void) { return LockState(Destroyed); } bool operator==(const LockState &X) const { return K == X.K; } bool isLocked() const { return K == Locked; } bool isUnlocked() const { return K == Unlocked; } bool isDestroyed() const { return K == Destroyed; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } }; class PthreadLockChecker : public Checker< check::PostStmt > { mutable std::unique_ptr BT_doublelock; mutable std::unique_ptr BT_doubleunlock; mutable std::unique_ptr BT_destroylock; mutable std::unique_ptr BT_initlock; mutable std::unique_ptr BT_lor; enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; public: void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const; void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; }; } // end anonymous namespace // GDM Entry for tracking lock state. REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) void PthreadLockChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { ProgramStateRef state = C.getState(); const LocationContext *LCtx = C.getLocationContext(); StringRef FName = C.getCalleeName(CE); if (FName.empty()) return; if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) return; if (FName == "pthread_mutex_lock" || FName == "pthread_rwlock_rdlock" || FName == "pthread_rwlock_wrlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, PthreadSemantics); else if (FName == "lck_mtx_lock" || FName == "lck_rw_lock_exclusive" || FName == "lck_rw_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, XNUSemantics); else if (FName == "pthread_mutex_trylock" || FName == "pthread_rwlock_tryrdlock" || FName == "pthread_rwlock_trywrlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, PthreadSemantics); else if (FName == "lck_mtx_try_lock" || FName == "lck_rw_try_lock_exclusive" || FName == "lck_rw_try_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, XNUSemantics); else if (FName == "pthread_mutex_unlock" || FName == "pthread_rwlock_unlock" || FName == "lck_mtx_unlock" || FName == "lck_rw_done") ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); else if (FName == "pthread_mutex_destroy" || FName == "lck_mtx_destroy") DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); else if (FName == "pthread_mutex_init") InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); } void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); SVal X = state->getSVal(CE, C.getLocationContext()); if (X.isUnknownOrUndef()) return; DefinedSVal retVal = X.castAs(); if (const LockState *LState = state->get(lockR)) { if (LState->isLocked()) { if (!BT_doublelock) BT_doublelock.reset(new BugType(this, "Double locking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_doublelock, "This lock has already been acquired", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } } ProgramStateRef lockSucc = state; if (isTryLock) { // Bifurcate the state, and allow a mode where the lock acquisition fails. ProgramStateRef lockFail; switch (semantics) { case PthreadSemantics: std::tie(lockFail, lockSucc) = state->assume(retVal); break; case XNUSemantics: std::tie(lockSucc, lockFail) = state->assume(retVal); break; default: llvm_unreachable("Unknown tryLock locking semantics"); } assert(lockFail && lockSucc); C.addTransition(lockFail); } else if (semantics == PthreadSemantics) { // Assume that the return value was 0. lockSucc = state->assume(retVal, false); assert(lockSucc); } else { // XNU locking semantics return void on non-try locks assert((semantics == XNUSemantics) && "Unknown locking semantics"); lockSucc = state; } // Record that the lock was acquired. lockSucc = lockSucc->add(lockR); lockSucc = lockSucc->set(lockR, LockState::getLocked()); C.addTransition(lockSucc); } void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); if (const LockState *LState = state->get(lockR)) { if (LState->isUnlocked()) { if (!BT_doubleunlock) BT_doubleunlock.reset(new BugType(this, "Double unlocking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_doubleunlock, "This lock has already been unlocked", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); return; } else if (LState->isDestroyed()) { reportUseDestroyedBug(C, CE); return; } } LockSetTy LS = state->get(); // FIXME: Better analysis requires IPA for wrappers. if (!LS.isEmpty()) { const MemRegion *firstLockR = LS.getHead(); if (firstLockR != lockR) { if (!BT_lor) BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_lor, "This was not the most recently " "acquired lock. Possible lock order " "reversal", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } // Record that the lock was released. state = state->set(LS.getTail()); } state = state->set(lockR, LockState::getUnlocked()); C.addTransition(state); } void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const LockState *LState = State->get(LockR); if (!LState || LState->isUnlocked()) { State = State->set(LockR, LockState::getDestroyed()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still locked"; } else { Message = "This lock has already been destroyed"; } if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Destroy invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); const struct LockState *LState = State->get(LockR); if (!LState || LState->isDestroyed()) { State = State->set(LockR, LockState::getUnlocked()); C.addTransition(State); return; } StringRef Message; if (LState->isLocked()) { Message = "This lock is still being held"; } else { Message = "This lock has already been initialized"; } if (!BT_initlock) BT_initlock.reset(new BugType(this, "Init invalid lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_initlock, Message, N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const { if (!BT_destroylock) BT_destroylock.reset(new BugType(this, "Use destroyed lock", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *Report = new BugReport(*BT_destroylock, "This lock has already been destroyed", N); Report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(Report); } void ento::registerPthreadLockChecker(CheckerManager &mgr) { mgr.registerChecker(); } @ 1.1.1.3.4.1 log @file PthreadLockChecker.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:31 +0000 @ text @d1 189 @ 1.1.1.3.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 189 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This defines PthreadLockChecker, a simple lock -> unlock checker. // Also handles XNU locks, which behave similarly enough to share code. // //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/ImmutableList.h" using namespace clang; using namespace ento; namespace { class PthreadLockChecker : public Checker< check::PostStmt > { mutable OwningPtr BT_doublelock; mutable OwningPtr BT_lor; enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; public: void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const; void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; }; } // end anonymous namespace // GDM Entry for tracking lock state. REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) void PthreadLockChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { ProgramStateRef state = C.getState(); const LocationContext *LCtx = C.getLocationContext(); StringRef FName = C.getCalleeName(CE); if (FName.empty()) return; if (CE->getNumArgs() != 1) return; if (FName == "pthread_mutex_lock" || FName == "pthread_rwlock_rdlock" || FName == "pthread_rwlock_wrlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, PthreadSemantics); else if (FName == "lck_mtx_lock" || FName == "lck_rw_lock_exclusive" || FName == "lck_rw_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), false, XNUSemantics); else if (FName == "pthread_mutex_trylock" || FName == "pthread_rwlock_tryrdlock" || FName == "pthread_rwlock_trywrlock") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, PthreadSemantics); else if (FName == "lck_mtx_try_lock" || FName == "lck_rw_try_lock_exclusive" || FName == "lck_rw_try_lock_shared") AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), true, XNUSemantics); else if (FName == "pthread_mutex_unlock" || FName == "pthread_rwlock_unlock" || FName == "lck_mtx_unlock" || FName == "lck_rw_done") ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); } void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, bool isTryLock, enum LockingSemantics semantics) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); SVal X = state->getSVal(CE, C.getLocationContext()); if (X.isUnknownOrUndef()) return; DefinedSVal retVal = X.castAs(); if (state->contains(lockR)) { if (!BT_doublelock) BT_doublelock.reset(new BugType(this, "Double locking", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_doublelock, "This lock has already " "been acquired", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } ProgramStateRef lockSucc = state; if (isTryLock) { // Bifurcate the state, and allow a mode where the lock acquisition fails. ProgramStateRef lockFail; switch (semantics) { case PthreadSemantics: llvm::tie(lockFail, lockSucc) = state->assume(retVal); break; case XNUSemantics: llvm::tie(lockSucc, lockFail) = state->assume(retVal); break; default: llvm_unreachable("Unknown tryLock locking semantics"); } assert(lockFail && lockSucc); C.addTransition(lockFail); } else if (semantics == PthreadSemantics) { // Assume that the return value was 0. lockSucc = state->assume(retVal, false); assert(lockSucc); } else { // XNU locking semantics return void on non-try locks assert((semantics == XNUSemantics) && "Unknown locking semantics"); lockSucc = state; } // Record that the lock was acquired. lockSucc = lockSucc->add(lockR); C.addTransition(lockSucc); } void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const { const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); LockSetTy LS = state->get(); // FIXME: Better analysis requires IPA for wrappers. // FIXME: check for double unlocks if (LS.isEmpty()) return; const MemRegion *firstLockR = LS.getHead(); if (firstLockR != lockR) { if (!BT_lor) BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); ExplodedNode *N = C.generateSink(); if (!N) return; BugReport *report = new BugReport(*BT_lor, "This was not the most " "recently acquired lock. " "Possible lock order " "reversal", N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(report); return; } // Record that the lock was released. state = state->set(LS.getTail()); C.addTransition(state); } void ento::registerPthreadLockChecker(CheckerManager &mgr) { mgr.registerChecker(); } @