Index: .gitignore =================================================================== --- .gitignore +++ .gitignore @@ -5,6 +5,7 @@ # This file is intentionally different from the output of `git svn show-ignore`, # as most of those are useless. #==============================================================================# +.DS_Store #==============================================================================# # File extensions to be ignored anywhere in the tree. Index: lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp +++ lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp @@ -25,7 +25,13 @@ namespace { struct LockState { - enum Kind { Destroyed, Locked, Unlocked } K; + enum Kind { + Destroyed, + Locked, + Unlocked, + UntouchedAndPossiblyDestroyed, + UnlockedAndPossiblyDestroyed + } K; private: LockState(Kind K) : K(K) {} @@ -34,49 +40,64 @@ static LockState getLocked() { return LockState(Locked); } static LockState getUnlocked() { return LockState(Unlocked); } static LockState getDestroyed() { return LockState(Destroyed); } - - bool operator==(const LockState &X) const { - return K == X.K; + static LockState getUntouchedAndPossiblyDestroyed() { + return LockState(UntouchedAndPossiblyDestroyed); + } + static LockState getUnlockedAndPossiblyDestroyed() { + return LockState(UnlockedAndPossiblyDestroyed); } + 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); + bool isUntouchedAndPossiblyDestroyed() const { + return K == UntouchedAndPossiblyDestroyed; } + bool isUnlockedAndPossiblyDestroyed() const { + return K == UnlockedAndPossiblyDestroyed; + } + + void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } }; -class PthreadLockChecker : public Checker< check::PostStmt > { +class PthreadLockChecker + : public Checker, check::DeadSymbols> { 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 - }; + enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; + public: void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; + void checkDeadSymbols(SymbolReaper &SymReaper, 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 DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock, + enum LockingSemantics semantics) const; void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; + ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, + const MemRegion *lockR, + const SymbolRef *sym) const; }; } // end anonymous namespace -// GDM Entry for tracking lock state. +// A stack of locks for tracking lock-unlock order. REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) +// An entry for tracking lock states. REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) +// Return values for unresolved calls to pthread_mutex_destroy(). +REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) + void PthreadLockChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { ProgramStateRef state = C.getState(); @@ -88,47 +109,82 @@ if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) return; - if (FName == "pthread_mutex_lock" || - FName == "pthread_rwlock_rdlock" || + 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" || + 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); + 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); + 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); + 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 == "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_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); else if (FName == "pthread_mutex_init") InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); } +// 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; +} + 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(); + const SymbolRef *sym = state->get(lockR); + if (sym) + state = resolvePossiblyDestroyedMutex(state, lockR, sym); SVal X = state->getSVal(CE, C.getLocationContext()); if (X.isUnknownOrUndef()) @@ -139,8 +195,8 @@ if (const LockState *LState = state->get(lockR)) { if (LState->isLocked()) { if (!BT_doublelock) - BT_doublelock.reset(new BugType(this, "Double locking", - "Lock checker")); + BT_doublelock.reset( + new BugType(this, "Double locking", "Lock checker")); ExplodedNode *N = C.generateErrorNode(); if (!N) return; @@ -191,18 +247,20 @@ void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const { - const MemRegion *lockR = lock.getAsRegion(); if (!lockR) return; ProgramStateRef state = C.getState(); + const SymbolRef *sym = state->get(lockR); + if (sym) + state = resolvePossiblyDestroyedMutex(state, lockR, sym); if (const LockState *LState = state->get(lockR)) { if (LState->isUnlocked()) { if (!BT_doubleunlock) - BT_doubleunlock.reset(new BugType(this, "Double unlocking", - "Lock checker")); + BT_doubleunlock.reset( + new BugType(this, "Double unlocking", "Lock checker")); ExplodedNode *N = C.generateErrorNode(); if (!N) return; @@ -230,8 +288,10 @@ if (!N) return; auto report = llvm::make_unique( - *BT_lor, "This was not the most recently acquired lock. Possible " - "lock order reversal", N); + *BT_lor, + "This was not the most recently acquired lock. Possible " + "lock order reversal", + N); report->addRange(CE->getArg(0)->getSourceRange()); C.emitReport(std::move(report)); return; @@ -245,21 +305,46 @@ } void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, - SVal Lock) const { - + SVal Lock, + enum LockingSemantics semantics) const { const MemRegion *LockR = Lock.getAsRegion(); if (!LockR) return; ProgramStateRef State = C.getState(); + const SymbolRef *sym = State->get(LockR); + if (sym) + State = resolvePossiblyDestroyedMutex(State, LockR, sym); + const LockState *LState = State->get(LockR); - if (!LState || LState->isUnlocked()) { - State = State->set(LockR, LockState::getDestroyed()); - C.addTransition(State); - return; + // 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; + } } - StringRef Message; if (LState->isLocked()) { @@ -269,8 +354,8 @@ } if (!BT_destroylock) - BT_destroylock.reset(new BugType(this, "Destroy invalid lock", - "Lock checker")); + BT_destroylock.reset( + new BugType(this, "Destroy invalid lock", "Lock checker")); ExplodedNode *N = C.generateErrorNode(); if (!N) return; @@ -288,6 +373,10 @@ ProgramStateRef State = C.getState(); + const SymbolRef *sym = State->get(LockR); + if (sym) + State = resolvePossiblyDestroyedMutex(State, LockR, sym); + const struct LockState *LState = State->get(LockR); if (!LState || LState->isDestroyed()) { State = State->set(LockR, LockState::getUnlocked()); @@ -304,8 +393,7 @@ } if (!BT_initlock) - BT_initlock.reset(new BugType(this, "Init invalid lock", - "Lock checker")); + BT_initlock.reset(new BugType(this, "Init invalid lock", "Lock checker")); ExplodedNode *N = C.generateErrorNode(); if (!N) return; @@ -317,8 +405,8 @@ void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const { if (!BT_destroylock) - BT_destroylock.reset(new BugType(this, "Use destroyed lock", - "Lock checker")); + BT_destroylock.reset( + new BugType(this, "Use destroyed lock", "Lock checker")); ExplodedNode *N = C.generateErrorNode(); if (!N) return; @@ -328,6 +416,26 @@ C.emitReport(std::move(Report)); } +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); + + if (IsSymDead) + State = resolvePossiblyDestroyedMutex(State, lockR, &Sym); + } + C.addTransition(State); +} + void ento::registerPthreadLockChecker(CheckerManager &mgr) { mgr.registerChecker(); } Index: test/Analysis/pthreadlock.c =================================================================== --- test/Analysis/pthreadlock.c +++ test/Analysis/pthreadlock.c @@ -176,6 +176,49 @@ pthread_mutex_unlock(pmtx); // no-warning } +void +ok23(void) { + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_destroy(&mtx1); // no-warning +} + +void +ok24(void) { + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_lock(&mtx1); // no-warning +} + +void +ok25(void) { + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_unlock(&mtx1); // no-warning +} + +void +ok26(void) { + pthread_mutex_unlock(&mtx1); // no-warning + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_lock(&mtx1); // no-warning +} + +void +ok27(void) { + pthread_mutex_unlock(&mtx1); // no-warning + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_lock(&mtx1); // no-warning + else + pthread_mutex_init(&mtx1, NULL); // no-warning +} + +void +ok28() { + if(pthread_mutex_destroy(&mtx1)!=0) { // no-warning + pthread_mutex_lock(&mtx1); // no-warning + pthread_mutex_unlock(&mtx1); // no-warning + pthread_mutex_destroy(&mtx1); // no-warning + } +} + void bad1(void) @@ -392,3 +435,56 @@ pthread_mutex_unlock(&mtx1); // no-warning pthread_mutex_init(&mtx1, NULL); // expected-warning{{This lock has already been initialized}} } + +void +bad27(void) +{ + pthread_mutex_unlock(&mtx1); // no-warning + int ret = pthread_mutex_destroy(&mtx1); // no-warning + if(ret != 0) // no-warning + pthread_mutex_lock(&mtx1); // no-warning + else + pthread_mutex_unlock(&mtx1); // expected-warning{{This lock has already been destroyed}} +} + +void +bad28(void) +{ + pthread_mutex_unlock(&mtx1); // no-warning + int ret = pthread_mutex_destroy(&mtx1); // no-warning + if(ret != 0) // no-warning + pthread_mutex_lock(&mtx1); // no-warning + else + pthread_mutex_lock(&mtx1); // expected-warning{{This lock has already been destroyed}} +} + +void +bad29() +{ + pthread_mutex_lock(&mtx1); // no-warning + pthread_mutex_unlock(&mtx1); // no-warning + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_init(&mtx1, NULL); // expected-warning{{This lock has already been initialized}} + else + pthread_mutex_init(&mtx1, NULL); // no-warning +} + +void +bad30() +{ + pthread_mutex_lock(&mtx1); // no-warning + pthread_mutex_unlock(&mtx1); // no-warning + if(pthread_mutex_destroy(&mtx1) != 0) // no-warning + pthread_mutex_init(&mtx1, NULL); // expected-warning{{This lock has already been initialized}} + else + pthread_mutex_destroy(&mtx1); // expected-warning{{This lock has already been destroyed}} +} + +void +bad31() +{ + int ret = pthread_mutex_destroy(&mtx1); // no-warning + pthread_mutex_lock(&mtx1); // expected-warning{{This lock has already been destroyed}} + if(ret != 0) + pthread_mutex_lock(&mtx1); +}