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