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