xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229)
1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines:
10 //  * PthreadLockChecker, a simple lock -> unlock checker.
11 //    Which also checks for XNU locks, which behave similarly enough to share
12 //    code.
13 //  * FuchsiaLocksChecker, which is also rather similar.
14 //  * C11LockChecker which also closely follows Pthread semantics.
15 //
16 //  TODO: Path notes.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
21 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
22 #include "clang/StaticAnalyzer/Core/Checker.h"
23 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
26 
27 using namespace clang;
28 using namespace ento;
29 
30 namespace {
31 
32 struct LockState {
33   enum Kind {
34     Destroyed,
35     Locked,
36     Unlocked,
37     UntouchedAndPossiblyDestroyed,
38     UnlockedAndPossiblyDestroyed
39   } K;
40 
41 private:
42   LockState(Kind K) : K(K) {}
43 
44 public:
45   static LockState getLocked() { return LockState(Locked); }
46   static LockState getUnlocked() { return LockState(Unlocked); }
47   static LockState getDestroyed() { return LockState(Destroyed); }
48   static LockState getUntouchedAndPossiblyDestroyed() {
49     return LockState(UntouchedAndPossiblyDestroyed);
50   }
51   static LockState getUnlockedAndPossiblyDestroyed() {
52     return LockState(UnlockedAndPossiblyDestroyed);
53   }
54 
55   bool operator==(const LockState &X) const { return K == X.K; }
56 
57   bool isLocked() const { return K == Locked; }
58   bool isUnlocked() const { return K == Unlocked; }
59   bool isDestroyed() const { return K == Destroyed; }
60   bool isUntouchedAndPossiblyDestroyed() const {
61     return K == UntouchedAndPossiblyDestroyed;
62   }
63   bool isUnlockedAndPossiblyDestroyed() const {
64     return K == UnlockedAndPossiblyDestroyed;
65   }
66 
67   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
68 };
69 
70 class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols,
71                                           check::RegionChanges> {
72 public:
73   enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics };
74   enum CheckerKind {
75     CK_PthreadLockChecker,
76     CK_FuchsiaLockChecker,
77     CK_C11LockChecker,
78     CK_NumCheckKinds
79   };
80   DefaultBool ChecksEnabled[CK_NumCheckKinds];
81   CheckerNameRef CheckNames[CK_NumCheckKinds];
82 
83 private:
84   typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call,
85                                               CheckerContext &C,
86                                               CheckerKind checkkind) const;
87   CallDescriptionMap<FnCheck> PThreadCallbacks = {
88       // Init.
89       {{"pthread_mutex_init", 2}, &PthreadLockChecker::InitAnyLock},
90       // TODO: pthread_rwlock_init(2 arguments).
91       // TODO: lck_mtx_init(3 arguments).
92       // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex.
93       // TODO: lck_rw_init(3 arguments).
94       // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex.
95 
96       // Acquire.
97       {{"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
98       {{"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
99       {{"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
100       {{"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock},
101       {{"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock},
102       {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock},
103 
104       // Try.
105       {{"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock},
106       {{"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock},
107       {{"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock},
108       {{"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock},
109       {{"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock},
110       {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock},
111 
112       // Release.
113       {{"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
114       {{"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
115       {{"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
116       {{"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock},
117       {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock},
118       {{"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock},
119 
120       // Destroy.
121       {{"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
122       {{"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock},
123       // TODO: pthread_rwlock_destroy(1 argument).
124       // TODO: lck_rw_destroy(2 arguments).
125   };
126 
127   CallDescriptionMap<FnCheck> FuchsiaCallbacks = {
128       // Init.
129       {{"spin_lock_init", 1}, &PthreadLockChecker::InitAnyLock},
130 
131       // Acquire.
132       {{"spin_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
133       {{"spin_lock_save", 3}, &PthreadLockChecker::AcquirePthreadLock},
134       {{"sync_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
135       {{"sync_mutex_lock_with_waiter", 1},
136        &PthreadLockChecker::AcquirePthreadLock},
137 
138       // Try.
139       {{"spin_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
140       {{"sync_mutex_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
141       {{"sync_mutex_timedlock", 2}, &PthreadLockChecker::TryFuchsiaLock},
142 
143       // Release.
144       {{"spin_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
145       {{"spin_unlock_restore", 3}, &PthreadLockChecker::ReleaseAnyLock},
146       {{"sync_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
147   };
148 
149   CallDescriptionMap<FnCheck> C11Callbacks = {
150       // Init.
151       {{"mtx_init", 2}, &PthreadLockChecker::InitAnyLock},
152 
153       // Acquire.
154       {{"mtx_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
155 
156       // Try.
157       {{"mtx_trylock", 1}, &PthreadLockChecker::TryC11Lock},
158       {{"mtx_timedlock", 2}, &PthreadLockChecker::TryC11Lock},
159 
160       // Release.
161       {{"mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
162 
163       // Destroy
164       {{"mtx_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
165   };
166 
167   ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
168                                                 const MemRegion *lockR,
169                                                 const SymbolRef *sym) const;
170   void reportUseDestroyedBug(const CallEvent &Call, CheckerContext &C,
171                              unsigned ArgNo, CheckerKind checkKind) const;
172 
173   // Init.
174   void InitAnyLock(const CallEvent &Call, CheckerContext &C,
175                    CheckerKind checkkind) const;
176   void InitLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
177                    SVal Lock, CheckerKind checkkind) const;
178 
179   // Lock, Try-lock.
180   void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,
181                           CheckerKind checkkind) const;
182   void AcquireXNULock(const CallEvent &Call, CheckerContext &C,
183                       CheckerKind checkkind) const;
184   void TryPthreadLock(const CallEvent &Call, CheckerContext &C,
185                       CheckerKind checkkind) const;
186   void TryXNULock(const CallEvent &Call, CheckerContext &C,
187                   CheckerKind checkkind) const;
188   void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,
189                       CheckerKind checkkind) const;
190   void TryC11Lock(const CallEvent &Call, CheckerContext &C,
191                   CheckerKind checkkind) const;
192   void AcquireLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
193                       SVal lock, bool isTryLock, LockingSemantics semantics,
194                       CheckerKind checkkind) const;
195 
196   // Release.
197   void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,
198                       CheckerKind checkkind) const;
199   void ReleaseLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
200                       SVal lock, CheckerKind checkkind) const;
201 
202   // Destroy.
203   void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,
204                           CheckerKind checkkind) const;
205   void DestroyXNULock(const CallEvent &Call, CheckerContext &C,
206                       CheckerKind checkkind) const;
207   void DestroyLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
208                       SVal Lock, LockingSemantics semantics,
209                       CheckerKind checkkind) const;
210 
211 public:
212   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
213   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
214   ProgramStateRef
215   checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
216                      ArrayRef<const MemRegion *> ExplicitRegions,
217                      ArrayRef<const MemRegion *> Regions,
218                      const LocationContext *LCtx, const CallEvent *Call) const;
219   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
220                   const char *Sep) const override;
221 
222 private:
223   mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
224   mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
225   mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
226   mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
227   mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
228 
229   void initBugType(CheckerKind checkKind) const {
230     if (BT_doublelock[checkKind])
231       return;
232     BT_doublelock[checkKind].reset(
233         new BugType{CheckNames[checkKind], "Double locking", "Lock checker"});
234     BT_doubleunlock[checkKind].reset(
235         new BugType{CheckNames[checkKind], "Double unlocking", "Lock checker"});
236     BT_destroylock[checkKind].reset(new BugType{
237         CheckNames[checkKind], "Use destroyed lock", "Lock checker"});
238     BT_initlock[checkKind].reset(new BugType{
239         CheckNames[checkKind], "Init invalid lock", "Lock checker"});
240     BT_lor[checkKind].reset(new BugType{CheckNames[checkKind],
241                                         "Lock order reversal", "Lock checker"});
242   }
243 };
244 } // end anonymous namespace
245 
246 // A stack of locks for tracking lock-unlock order.
247 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
248 
249 // An entry for tracking lock states.
250 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
251 
252 // Return values for unresolved calls to pthread_mutex_destroy().
253 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
254 
255 void PthreadLockChecker::checkPostCall(const CallEvent &Call,
256                                        CheckerContext &C) const {
257   // An additional umbrella check that all functions modeled by this checker
258   // are global C functions.
259   // TODO: Maybe make this the default behavior of CallDescription
260   // with exactly one identifier?
261   // FIXME: Try to handle cases when the implementation was inlined rather
262   // than just giving up.
263   if (!Call.isGlobalCFunction() || C.wasInlined)
264     return;
265 
266   if (const FnCheck *Callback = PThreadCallbacks.lookup(Call))
267     (this->**Callback)(Call, C, CK_PthreadLockChecker);
268   else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
269     (this->**Callback)(Call, C, CK_FuchsiaLockChecker);
270   else if (const FnCheck *Callback = C11Callbacks.lookup(Call))
271     (this->**Callback)(Call, C, CK_C11LockChecker);
272 }
273 
274 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
275 // sure if the destroy call has succeeded or failed, and the lock enters one of
276 // the 'possibly destroyed' state. There is a short time frame for the
277 // programmer to check the return value to see if the lock was successfully
278 // destroyed. Before we model the next operation over that lock, we call this
279 // function to see if the return value was checked by now and set the lock state
280 // - either to destroyed state or back to its previous state.
281 
282 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
283 // successfully destroyed and it returns a non-zero value otherwise.
284 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
285     ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
286   const LockState *lstate = state->get<LockMap>(lockR);
287   // Existence in DestroyRetVal ensures existence in LockMap.
288   // Existence in Destroyed also ensures that the lock state for lockR is either
289   // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
290   assert(lstate->isUntouchedAndPossiblyDestroyed() ||
291          lstate->isUnlockedAndPossiblyDestroyed());
292 
293   ConstraintManager &CMgr = state->getConstraintManager();
294   ConditionTruthVal retZero = CMgr.isNull(state, *sym);
295   if (retZero.isConstrainedFalse()) {
296     if (lstate->isUntouchedAndPossiblyDestroyed())
297       state = state->remove<LockMap>(lockR);
298     else if (lstate->isUnlockedAndPossiblyDestroyed())
299       state = state->set<LockMap>(lockR, LockState::getUnlocked());
300   } else
301     state = state->set<LockMap>(lockR, LockState::getDestroyed());
302 
303   // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
304   // now resolved.
305   state = state->remove<DestroyRetVal>(lockR);
306   return state;
307 }
308 
309 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
310                                     const char *NL, const char *Sep) const {
311   LockMapTy LM = State->get<LockMap>();
312   if (!LM.isEmpty()) {
313     Out << Sep << "Mutex states:" << NL;
314     for (auto I : LM) {
315       I.first->dumpToStream(Out);
316       if (I.second.isLocked())
317         Out << ": locked";
318       else if (I.second.isUnlocked())
319         Out << ": unlocked";
320       else if (I.second.isDestroyed())
321         Out << ": destroyed";
322       else if (I.second.isUntouchedAndPossiblyDestroyed())
323         Out << ": not tracked, possibly destroyed";
324       else if (I.second.isUnlockedAndPossiblyDestroyed())
325         Out << ": unlocked, possibly destroyed";
326       Out << NL;
327     }
328   }
329 
330   LockSetTy LS = State->get<LockSet>();
331   if (!LS.isEmpty()) {
332     Out << Sep << "Mutex lock order:" << NL;
333     for (auto I : LS) {
334       I->dumpToStream(Out);
335       Out << NL;
336     }
337   }
338 
339   // TODO: Dump destroyed mutex symbols?
340 }
341 
342 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
343                                             CheckerContext &C,
344                                             CheckerKind checkKind) const {
345   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, PthreadSemantics,
346                  checkKind);
347 }
348 
349 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
350                                         CheckerContext &C,
351                                         CheckerKind checkKind) const {
352   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, XNUSemantics,
353                  checkKind);
354 }
355 
356 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
357                                         CheckerContext &C,
358                                         CheckerKind checkKind) const {
359   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
360                  checkKind);
361 }
362 
363 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
364                                     CheckerKind checkKind) const {
365   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
366                  checkKind);
367 }
368 
369 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
370                                         CheckerContext &C,
371                                         CheckerKind checkKind) const {
372   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
373                  checkKind);
374 }
375 
376 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
377                                     CheckerKind checkKind) const {
378   AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
379                  checkKind);
380 }
381 
382 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
383                                         CheckerContext &C, unsigned ArgNo,
384                                         SVal lock, bool isTryLock,
385                                         enum LockingSemantics semantics,
386                                         CheckerKind checkKind) const {
387   if (!ChecksEnabled[checkKind])
388     return;
389 
390   const MemRegion *lockR = lock.getAsRegion();
391   if (!lockR)
392     return;
393 
394   ProgramStateRef state = C.getState();
395   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
396   if (sym)
397     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
398 
399   if (const LockState *LState = state->get<LockMap>(lockR)) {
400     if (LState->isLocked()) {
401       ExplodedNode *N = C.generateErrorNode();
402       if (!N)
403         return;
404       initBugType(checkKind);
405       auto report = std::make_unique<PathSensitiveBugReport>(
406           *BT_doublelock[checkKind], "This lock has already been acquired", N);
407       report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
408       C.emitReport(std::move(report));
409       return;
410     } else if (LState->isDestroyed()) {
411       reportUseDestroyedBug(Call, C, ArgNo, checkKind);
412       return;
413     }
414   }
415 
416   ProgramStateRef lockSucc = state;
417   if (isTryLock) {
418     // Bifurcate the state, and allow a mode where the lock acquisition fails.
419     SVal RetVal = Call.getReturnValue();
420     if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
421       ProgramStateRef lockFail;
422       switch (semantics) {
423       case PthreadSemantics:
424         std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
425         break;
426       case XNUSemantics:
427         std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
428         break;
429       default:
430         llvm_unreachable("Unknown tryLock locking semantics");
431       }
432       assert(lockFail && lockSucc);
433       C.addTransition(lockFail);
434     }
435     // We might want to handle the case when the mutex lock function was inlined
436     // and returned an Unknown or Undefined value.
437   } else if (semantics == PthreadSemantics) {
438     // Assume that the return value was 0.
439     SVal RetVal = Call.getReturnValue();
440     if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
441       // FIXME: If the lock function was inlined and returned true,
442       // we need to behave sanely - at least generate sink.
443       lockSucc = state->assume(*DefinedRetVal, false);
444       assert(lockSucc);
445     }
446     // We might want to handle the case when the mutex lock function was inlined
447     // and returned an Unknown or Undefined value.
448   } else {
449     // XNU locking semantics return void on non-try locks
450     assert((semantics == XNUSemantics) && "Unknown locking semantics");
451     lockSucc = state;
452   }
453 
454   // Record that the lock was acquired.
455   lockSucc = lockSucc->add<LockSet>(lockR);
456   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
457   C.addTransition(lockSucc);
458 }
459 
460 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
461                                         CheckerContext &C,
462                                         CheckerKind checkKind) const {
463   ReleaseLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
464 }
465 
466 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
467                                         CheckerContext &C, unsigned ArgNo,
468                                         SVal lock,
469                                         CheckerKind checkKind) const {
470   if (!ChecksEnabled[checkKind])
471     return;
472 
473   const MemRegion *lockR = lock.getAsRegion();
474   if (!lockR)
475     return;
476 
477   ProgramStateRef state = C.getState();
478   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
479   if (sym)
480     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
481 
482   if (const LockState *LState = state->get<LockMap>(lockR)) {
483     if (LState->isUnlocked()) {
484       ExplodedNode *N = C.generateErrorNode();
485       if (!N)
486         return;
487       initBugType(checkKind);
488       auto Report = std::make_unique<PathSensitiveBugReport>(
489           *BT_doubleunlock[checkKind], "This lock has already been unlocked",
490           N);
491       Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
492       C.emitReport(std::move(Report));
493       return;
494     } else if (LState->isDestroyed()) {
495       reportUseDestroyedBug(Call, C, ArgNo, checkKind);
496       return;
497     }
498   }
499 
500   LockSetTy LS = state->get<LockSet>();
501 
502   if (!LS.isEmpty()) {
503     const MemRegion *firstLockR = LS.getHead();
504     if (firstLockR != lockR) {
505       ExplodedNode *N = C.generateErrorNode();
506       if (!N)
507         return;
508       initBugType(checkKind);
509       auto report = std::make_unique<PathSensitiveBugReport>(
510           *BT_lor[checkKind],
511           "This was not the most recently acquired lock. Possible "
512           "lock order reversal",
513           N);
514       report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
515       C.emitReport(std::move(report));
516       return;
517     }
518     // Record that the lock was released.
519     state = state->set<LockSet>(LS.getTail());
520   }
521 
522   state = state->set<LockMap>(lockR, LockState::getUnlocked());
523   C.addTransition(state);
524 }
525 
526 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
527                                             CheckerContext &C,
528                                             CheckerKind checkKind) const {
529   DestroyLockAux(Call, C, 0, Call.getArgSVal(0), PthreadSemantics, checkKind);
530 }
531 
532 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
533                                         CheckerContext &C,
534                                         CheckerKind checkKind) const {
535   DestroyLockAux(Call, C, 0, Call.getArgSVal(0), XNUSemantics, checkKind);
536 }
537 
538 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
539                                         CheckerContext &C, unsigned ArgNo,
540                                         SVal Lock,
541                                         enum LockingSemantics semantics,
542                                         CheckerKind checkKind) const {
543   if (!ChecksEnabled[checkKind])
544     return;
545 
546   const MemRegion *LockR = Lock.getAsRegion();
547   if (!LockR)
548     return;
549 
550   ProgramStateRef State = C.getState();
551 
552   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
553   if (sym)
554     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
555 
556   const LockState *LState = State->get<LockMap>(LockR);
557   // Checking the return value of the destroy method only in the case of
558   // PthreadSemantics
559   if (semantics == PthreadSemantics) {
560     if (!LState || LState->isUnlocked()) {
561       SymbolRef sym = Call.getReturnValue().getAsSymbol();
562       if (!sym) {
563         State = State->remove<LockMap>(LockR);
564         C.addTransition(State);
565         return;
566       }
567       State = State->set<DestroyRetVal>(LockR, sym);
568       if (LState && LState->isUnlocked())
569         State = State->set<LockMap>(
570             LockR, LockState::getUnlockedAndPossiblyDestroyed());
571       else
572         State = State->set<LockMap>(
573             LockR, LockState::getUntouchedAndPossiblyDestroyed());
574       C.addTransition(State);
575       return;
576     }
577   } else {
578     if (!LState || LState->isUnlocked()) {
579       State = State->set<LockMap>(LockR, LockState::getDestroyed());
580       C.addTransition(State);
581       return;
582     }
583   }
584   StringRef Message;
585 
586   if (LState->isLocked()) {
587     Message = "This lock is still locked";
588   } else {
589     Message = "This lock has already been destroyed";
590   }
591 
592   ExplodedNode *N = C.generateErrorNode();
593   if (!N)
594     return;
595   initBugType(checkKind);
596   auto Report = std::make_unique<PathSensitiveBugReport>(
597       *BT_destroylock[checkKind], Message, N);
598   Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
599   C.emitReport(std::move(Report));
600 }
601 
602 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
603                                      CheckerKind checkKind) const {
604   InitLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
605 }
606 
607 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
608                                      unsigned ArgNo, SVal Lock,
609                                      CheckerKind checkKind) const {
610   if (!ChecksEnabled[checkKind])
611     return;
612 
613   const MemRegion *LockR = Lock.getAsRegion();
614   if (!LockR)
615     return;
616 
617   ProgramStateRef State = C.getState();
618 
619   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
620   if (sym)
621     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
622 
623   const struct LockState *LState = State->get<LockMap>(LockR);
624   if (!LState || LState->isDestroyed()) {
625     State = State->set<LockMap>(LockR, LockState::getUnlocked());
626     C.addTransition(State);
627     return;
628   }
629 
630   StringRef Message;
631 
632   if (LState->isLocked()) {
633     Message = "This lock is still being held";
634   } else {
635     Message = "This lock has already been initialized";
636   }
637 
638   ExplodedNode *N = C.generateErrorNode();
639   if (!N)
640     return;
641   initBugType(checkKind);
642   auto Report = std::make_unique<PathSensitiveBugReport>(
643       *BT_initlock[checkKind], Message, N);
644   Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
645   C.emitReport(std::move(Report));
646 }
647 
648 void PthreadLockChecker::reportUseDestroyedBug(const CallEvent &Call,
649                                                CheckerContext &C,
650                                                unsigned ArgNo,
651                                                CheckerKind checkKind) const {
652   ExplodedNode *N = C.generateErrorNode();
653   if (!N)
654     return;
655   initBugType(checkKind);
656   auto Report = std::make_unique<PathSensitiveBugReport>(
657       *BT_destroylock[checkKind], "This lock has already been destroyed", N);
658   Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
659   C.emitReport(std::move(Report));
660 }
661 
662 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
663                                           CheckerContext &C) const {
664   ProgramStateRef State = C.getState();
665 
666   for (auto I : State->get<DestroyRetVal>()) {
667     // Once the return value symbol dies, no more checks can be performed
668     // against it. See if the return value was checked before this point.
669     // This would remove the symbol from the map as well.
670     if (SymReaper.isDead(I.second))
671       State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
672   }
673 
674   for (auto I : State->get<LockMap>()) {
675     // Stop tracking dead mutex regions as well.
676     if (!SymReaper.isLiveRegion(I.first))
677       State = State->remove<LockMap>(I.first);
678   }
679 
680   // TODO: We probably need to clean up the lock stack as well.
681   // It is tricky though: even if the mutex cannot be unlocked anymore,
682   // it can still participate in lock order reversal resolution.
683 
684   C.addTransition(State);
685 }
686 
687 ProgramStateRef PthreadLockChecker::checkRegionChanges(
688     ProgramStateRef State, const InvalidatedSymbols *Symbols,
689     ArrayRef<const MemRegion *> ExplicitRegions,
690     ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,
691     const CallEvent *Call) const {
692 
693   bool IsLibraryFunction = false;
694   if (Call && Call->isGlobalCFunction()) {
695     // Avoid invalidating mutex state when a known supported function is called.
696     if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
697         C11Callbacks.lookup(*Call))
698       return State;
699 
700     if (Call->isInSystemHeader())
701       IsLibraryFunction = true;
702   }
703 
704   for (auto R : Regions) {
705     // We assume that system library function wouldn't touch the mutex unless
706     // it takes the mutex explicitly as an argument.
707     // FIXME: This is a bit quadratic.
708     if (IsLibraryFunction &&
709         std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) ==
710             ExplicitRegions.end())
711       continue;
712 
713     State = State->remove<LockMap>(R);
714     State = State->remove<DestroyRetVal>(R);
715 
716     // TODO: We need to invalidate the lock stack as well. This is tricky
717     // to implement correctly and efficiently though, because the effects
718     // of mutex escapes on lock order may be fairly varied.
719   }
720 
721   return State;
722 }
723 
724 void ento::registerPthreadLockBase(CheckerManager &mgr) {
725   mgr.registerChecker<PthreadLockChecker>();
726 }
727 
728 bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }
729 
730 #define REGISTER_CHECKER(name)                                                 \
731   void ento::register##name(CheckerManager &mgr) {                             \
732     PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733     checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734     checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735         mgr.getCurrentCheckerName();                                           \
736   }                                                                            \
737                                                                                \
738   bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
739 
740 REGISTER_CHECKER(PthreadLockChecker)
741 REGISTER_CHECKER(FuchsiaLockChecker)
742 REGISTER_CHECKER(C11LockChecker)
743