1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 //  * PthreadLockChecker, a simple lock -> unlock checker.
18 //===----------------------------------------------------------------------===//
201   ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
215   // Lock, Try-lock.
252   checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
256   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
270         new BugType{CheckNames[CheckKind], "Double locking", "Lock checker"});  in initBugType()
272         new BugType{CheckNames[CheckKind], "Double unlocking", "Lock checker"});  in initBugType()
274         CheckNames[CheckKind], "Use destroyed lock", "Lock checker"});  in initBugType()
276         CheckNames[CheckKind], "Init invalid lock", "Lock checker"});  in initBugType()
278                                         "Lock order reversal", "Lock checker"});  in initBugType()
283 // A stack of locks for tracking lock-unlock order.
286 // An entry for tracking lock states.  in REGISTER_LIST_WITH_PROGRAMSTATE()
300     (this->**Callback)(Call, C, CK_PthreadLockChecker);  in REGISTER_LIST_WITH_PROGRAMSTATE()
302     (this->**Callback)(Call, C, CK_FuchsiaLockChecker);  in REGISTER_LIST_WITH_PROGRAMSTATE()
304     (this->**Callback)(Call, C, CK_C11LockChecker);  in REGISTER_LIST_WITH_PROGRAMSTATE()
307 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
308 // sure if the destroy call has succeeded or failed, and the lock enters one of
309 // the 'possibly destroyed' state. There is a short time frame for the
310 // programmer to check the return value to see if the lock was successfully
311 // destroyed. Before we model the next operation over that lock, we call this
312 // function to see if the return value was checked by now and set the lock state
313 // - either to destroyed state or back to its previous state.
315 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
316 // successfully destroyed and it returns a non-zero value otherwise.
318     ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {  in resolvePossiblyDestroyedMutex()  argument
319   const LockState *lstate = state->get<LockMap>(lockR);  in resolvePossiblyDestroyedMutex()
321   // Existence in Destroyed also ensures that the lock state for lockR is either  in resolvePossiblyDestroyedMutex()
324   assert(lstate->isUntouchedAndPossiblyDestroyed() ||  in resolvePossiblyDestroyedMutex()
325          lstate->isUnlockedAndPossiblyDestroyed());  in resolvePossiblyDestroyedMutex()
327   ConstraintManager &CMgr = state->getConstraintManager();  in resolvePossiblyDestroyedMutex()
328   ConditionTruthVal retZero = CMgr.isNull(state, *sym);  in resolvePossiblyDestroyedMutex()
330     if (lstate->isUntouchedAndPossiblyDestroyed())  in resolvePossiblyDestroyedMutex()
331       state = state->remove<LockMap>(lockR);  in resolvePossiblyDestroyedMutex()
332     else if (lstate->isUnlockedAndPossiblyDestroyed())  in resolvePossiblyDestroyedMutex()
333       state = state->set<LockMap>(lockR, LockState::getUnlocked());  in resolvePossiblyDestroyedMutex()
335     state = state->set<LockMap>(lockR, LockState::getDestroyed());  in resolvePossiblyDestroyedMutex()
337   // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is  in resolvePossiblyDestroyedMutex()
339   state = state->remove<DestroyRetVal>(lockR);  in resolvePossiblyDestroyedMutex()
340   return state;  in resolvePossiblyDestroyedMutex()
343 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,  in printState()  argument
345   LockMapTy LM = State->get<LockMap>();  in printState()
349       I.first->dumpToStream(Out);  in printState()
364   LockSetTy LS = State->get<LockSet>();  in printState()
366     Out << Sep << "Mutex lock order:" << NL;  in printState()
368       I->dumpToStream(Out);  in printState()
373   DestroyRetValTy DRV = State->get<DestroyRetVal>();  in printState()
375     Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL;  in printState()
377       I.first->dumpToStream(Out);  in printState()
379       I.second->dumpToStream(Out);  in printState()
437   ProgramStateRef state = C.getState();  in AcquireLockAux()  local
438   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);  in AcquireLockAux()
440     state = resolvePossiblyDestroyedMutex(state, lockR, sym);  in AcquireLockAux()
442   if (const LockState *LState = state->get<LockMap>(lockR)) {  in AcquireLockAux()
443     if (LState->isLocked()) {  in AcquireLockAux()
445                 "This lock has already been acquired");  in AcquireLockAux()
447     } else if (LState->isDestroyed()) {  in AcquireLockAux()
449                 "This lock has already been destroyed");  in AcquireLockAux()
454   ProgramStateRef lockSucc = state;  in AcquireLockAux()
456     // Bifurcate the state, and allow a mode where the lock acquisition fails.  in AcquireLockAux()
462         std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);  in AcquireLockAux()
465         std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);  in AcquireLockAux()
473     // We might want to handle the case when the mutex lock function was inlined  in AcquireLockAux()
479       // FIXME: If the lock function was inlined and returned true,  in AcquireLockAux()
480       // we need to behave sanely - at least generate sink.  in AcquireLockAux()
481       lockSucc = state->assume(*DefinedRetVal, false);  in AcquireLockAux()
484     // We might want to handle the case when the mutex lock function was inlined  in AcquireLockAux()
487     // XNU locking semantics return void on non-try locks  in AcquireLockAux()
489     lockSucc = state;  in AcquireLockAux()
492   // Record that the lock was acquired.  in AcquireLockAux()
493   lockSucc = lockSucc->add<LockSet>(lockR);  in AcquireLockAux()
494   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());  in AcquireLockAux()
515   ProgramStateRef state = C.getState();  in ReleaseLockAux()  local
516   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);  in ReleaseLockAux()
518     state = resolvePossiblyDestroyedMutex(state, lockR, sym);  in ReleaseLockAux()
520   if (const LockState *LState = state->get<LockMap>(lockR)) {  in ReleaseLockAux()
521     if (LState->isUnlocked()) {  in ReleaseLockAux()
523                 "This lock has already been unlocked");  in ReleaseLockAux()
525     } else if (LState->isDestroyed()) {  in ReleaseLockAux()
527                 "This lock has already been destroyed");  in ReleaseLockAux()
532   LockSetTy LS = state->get<LockSet>();  in ReleaseLockAux()
538                 "This was not the most recently acquired lock. Possible lock "  in ReleaseLockAux()
542     // Record that the lock was released.  in ReleaseLockAux()
543     state = state->set<LockSet>(LS.getTail());  in ReleaseLockAux()
546   state = state->set<LockMap>(lockR, LockState::getUnlocked());  in ReleaseLockAux()
547   C.addTransition(state);  in ReleaseLockAux()
576   ProgramStateRef State = C.getState();  in DestroyLockAux()  local
578   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);  in DestroyLockAux()
580     State = resolvePossiblyDestroyedMutex(State, LockR, sym);  in DestroyLockAux()
582   const LockState *LState = State->get<LockMap>(LockR);  in DestroyLockAux()
586     if (!LState || LState->isUnlocked()) {  in DestroyLockAux()
589         State = State->remove<LockMap>(LockR);  in DestroyLockAux()
590         C.addTransition(State);  in DestroyLockAux()
593       State = State->set<DestroyRetVal>(LockR, sym);  in DestroyLockAux()
594       if (LState && LState->isUnlocked())  in DestroyLockAux()
595         State = State->set<LockMap>(  in DestroyLockAux()
598         State = State->set<LockMap>(  in DestroyLockAux()
600       C.addTransition(State);  in DestroyLockAux()
604     if (!LState || LState->isUnlocked()) {  in DestroyLockAux()
605       State = State->set<LockMap>(LockR, LockState::getDestroyed());  in DestroyLockAux()
606       C.addTransition(State);  in DestroyLockAux()
611   StringRef Message = LState->isLocked()  in DestroyLockAux()
612                           ? "This lock is still locked"  in DestroyLockAux()
613                           : "This lock has already been destroyed";  in DestroyLockAux()
633   ProgramStateRef State = C.getState();  in InitLockAux()  local
635   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);  in InitLockAux()
637     State = resolvePossiblyDestroyedMutex(State, LockR, sym);  in InitLockAux()
639   const struct LockState *LState = State->get<LockMap>(LockR);  in InitLockAux()
640   if (!LState || LState->isDestroyed()) {  in InitLockAux()
641     State = State->set<LockMap>(LockR, LockState::getUnlocked());  in InitLockAux()
642     C.addTransition(State);  in InitLockAux()
646   StringRef Message = LState->isLocked()  in InitLockAux()
647                           ? "This lock is still being held"  in InitLockAux()
648                           : "This lock has already been initialized";  in InitLockAux()
663   Report->addRange(MtxExpr->getSourceRange());  in reportBug()
669   ProgramStateRef State = C.getState();  in checkDeadSymbols()  local
671   for (auto I : State->get<DestroyRetVal>()) {  in checkDeadSymbols()
676       State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);  in checkDeadSymbols()
679   for (auto I : State->get<LockMap>()) {  in checkDeadSymbols()
682       State = State->remove<LockMap>(I.first);  in checkDeadSymbols()
683       State = State->remove<DestroyRetVal>(I.first);  in checkDeadSymbols()
687   // TODO: We probably need to clean up the lock stack as well.  in checkDeadSymbols()
689   // it can still participate in lock order reversal resolution.  in checkDeadSymbols()
691   C.addTransition(State);  in checkDeadSymbols()
695     ProgramStateRef State, const InvalidatedSymbols *Symbols,  in checkRegionChanges()  argument
701   if (Call && Call->isGlobalCFunction()) {  in checkRegionChanges()
702     // Avoid invalidating mutex state when a known supported function is called.  in checkRegionChanges()
705       return State;  in checkRegionChanges()
707     if (Call->isInSystemHeader())  in checkRegionChanges()
718     State = State->remove<LockMap>(R);  in checkRegionChanges()
719     State = State->remove<DestroyRetVal>(R);  in checkRegionChanges()
721     // TODO: We need to invalidate the lock stack as well. This is tricky  in checkRegionChanges()
723     // of mutex escapes on lock order may be fairly varied.  in checkRegionChanges()
726   return State;  in checkRegionChanges()
738     checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
739     checker->CheckNames[PthreadLockChecker::CK_##name] =                       \