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:
LockState__anon958ac69a0111::LockState42 LockState(Kind K) : K(K) {}
43
44 public:
getLocked__anon958ac69a0111::LockState45 static LockState getLocked() { return LockState(Locked); }
getUnlocked__anon958ac69a0111::LockState46 static LockState getUnlocked() { return LockState(Unlocked); }
getDestroyed__anon958ac69a0111::LockState47 static LockState getDestroyed() { return LockState(Destroyed); }
getUntouchedAndPossiblyDestroyed__anon958ac69a0111::LockState48 static LockState getUntouchedAndPossiblyDestroyed() {
49 return LockState(UntouchedAndPossiblyDestroyed);
50 }
getUnlockedAndPossiblyDestroyed__anon958ac69a0111::LockState51 static LockState getUnlockedAndPossiblyDestroyed() {
52 return LockState(UnlockedAndPossiblyDestroyed);
53 }
54
operator ==__anon958ac69a0111::LockState55 bool operator==(const LockState &X) const { return K == X.K; }
56
isLocked__anon958ac69a0111::LockState57 bool isLocked() const { return K == Locked; }
isUnlocked__anon958ac69a0111::LockState58 bool isUnlocked() const { return K == Unlocked; }
isDestroyed__anon958ac69a0111::LockState59 bool isDestroyed() const { return K == Destroyed; }
isUntouchedAndPossiblyDestroyed__anon958ac69a0111::LockState60 bool isUntouchedAndPossiblyDestroyed() const {
61 return K == UntouchedAndPossiblyDestroyed;
62 }
isUnlockedAndPossiblyDestroyed__anon958ac69a0111::LockState63 bool isUnlockedAndPossiblyDestroyed() const {
64 return K == UnlockedAndPossiblyDestroyed;
65 }
66
Profile__anon958ac69a0111::LockState67 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 reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[],
171 const Expr *MtxExpr, CheckerKind CheckKind,
172 StringRef Desc) const;
173
174 // Init.
175 void InitAnyLock(const CallEvent &Call, CheckerContext &C,
176 CheckerKind CheckKind) const;
177 void InitLockAux(const CallEvent &Call, CheckerContext &C,
178 const Expr *MtxExpr, SVal MtxVal,
179 CheckerKind CheckKind) const;
180
181 // Lock, Try-lock.
182 void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,
183 CheckerKind CheckKind) const;
184 void AcquireXNULock(const CallEvent &Call, CheckerContext &C,
185 CheckerKind CheckKind) const;
186 void TryPthreadLock(const CallEvent &Call, CheckerContext &C,
187 CheckerKind CheckKind) const;
188 void TryXNULock(const CallEvent &Call, CheckerContext &C,
189 CheckerKind CheckKind) const;
190 void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,
191 CheckerKind CheckKind) const;
192 void TryC11Lock(const CallEvent &Call, CheckerContext &C,
193 CheckerKind CheckKind) const;
194 void AcquireLockAux(const CallEvent &Call, CheckerContext &C,
195 const Expr *MtxExpr, SVal MtxVal, bool IsTryLock,
196 LockingSemantics Semantics, CheckerKind CheckKind) const;
197
198 // Release.
199 void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,
200 CheckerKind CheckKind) const;
201 void ReleaseLockAux(const CallEvent &Call, CheckerContext &C,
202 const Expr *MtxExpr, SVal MtxVal,
203 CheckerKind CheckKind) const;
204
205 // Destroy.
206 void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,
207 CheckerKind CheckKind) const;
208 void DestroyXNULock(const CallEvent &Call, CheckerContext &C,
209 CheckerKind CheckKind) const;
210 void DestroyLockAux(const CallEvent &Call, CheckerContext &C,
211 const Expr *MtxExpr, SVal MtxVal,
212 LockingSemantics Semantics, CheckerKind CheckKind) const;
213
214 public:
215 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
216 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
217 ProgramStateRef
218 checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
219 ArrayRef<const MemRegion *> ExplicitRegions,
220 ArrayRef<const MemRegion *> Regions,
221 const LocationContext *LCtx, const CallEvent *Call) const;
222 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
223 const char *Sep) const override;
224
225 private:
226 mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
227 mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
228 mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
229 mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
230 mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
231
initBugType(CheckerKind CheckKind) const232 void initBugType(CheckerKind CheckKind) const {
233 if (BT_doublelock[CheckKind])
234 return;
235 BT_doublelock[CheckKind].reset(
236 new BugType{CheckNames[CheckKind], "Double locking", "Lock checker"});
237 BT_doubleunlock[CheckKind].reset(
238 new BugType{CheckNames[CheckKind], "Double unlocking", "Lock checker"});
239 BT_destroylock[CheckKind].reset(new BugType{
240 CheckNames[CheckKind], "Use destroyed lock", "Lock checker"});
241 BT_initlock[CheckKind].reset(new BugType{
242 CheckNames[CheckKind], "Init invalid lock", "Lock checker"});
243 BT_lor[CheckKind].reset(new BugType{CheckNames[CheckKind],
244 "Lock order reversal", "Lock checker"});
245 }
246 };
247 } // end anonymous namespace
248
249 // A stack of locks for tracking lock-unlock order.
REGISTER_LIST_WITH_PROGRAMSTATE(LockSet,const MemRegion *)250 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
251
252 // An entry for tracking lock states.
253 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
254
255 // Return values for unresolved calls to pthread_mutex_destroy().
256 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
257
258 void PthreadLockChecker::checkPostCall(const CallEvent &Call,
259 CheckerContext &C) const {
260 // An additional umbrella check that all functions modeled by this checker
261 // are global C functions.
262 // TODO: Maybe make this the default behavior of CallDescription
263 // with exactly one identifier?
264 // FIXME: Try to handle cases when the implementation was inlined rather
265 // than just giving up.
266 if (!Call.isGlobalCFunction() || C.wasInlined)
267 return;
268
269 if (const FnCheck *Callback = PThreadCallbacks.lookup(Call))
270 (this->**Callback)(Call, C, CK_PthreadLockChecker);
271 else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
272 (this->**Callback)(Call, C, CK_FuchsiaLockChecker);
273 else if (const FnCheck *Callback = C11Callbacks.lookup(Call))
274 (this->**Callback)(Call, C, CK_C11LockChecker);
275 }
276
277 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
278 // sure if the destroy call has succeeded or failed, and the lock enters one of
279 // the 'possibly destroyed' state. There is a short time frame for the
280 // programmer to check the return value to see if the lock was successfully
281 // destroyed. Before we model the next operation over that lock, we call this
282 // function to see if the return value was checked by now and set the lock state
283 // - either to destroyed state or back to its previous state.
284
285 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
286 // successfully destroyed and it returns a non-zero value otherwise.
resolvePossiblyDestroyedMutex(ProgramStateRef state,const MemRegion * lockR,const SymbolRef * sym) const287 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
288 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
289 const LockState *lstate = state->get<LockMap>(lockR);
290 // Existence in DestroyRetVal ensures existence in LockMap.
291 // Existence in Destroyed also ensures that the lock state for lockR is either
292 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
293 assert(lstate->isUntouchedAndPossiblyDestroyed() ||
294 lstate->isUnlockedAndPossiblyDestroyed());
295
296 ConstraintManager &CMgr = state->getConstraintManager();
297 ConditionTruthVal retZero = CMgr.isNull(state, *sym);
298 if (retZero.isConstrainedFalse()) {
299 if (lstate->isUntouchedAndPossiblyDestroyed())
300 state = state->remove<LockMap>(lockR);
301 else if (lstate->isUnlockedAndPossiblyDestroyed())
302 state = state->set<LockMap>(lockR, LockState::getUnlocked());
303 } else
304 state = state->set<LockMap>(lockR, LockState::getDestroyed());
305
306 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
307 // now resolved.
308 state = state->remove<DestroyRetVal>(lockR);
309 return state;
310 }
311
printState(raw_ostream & Out,ProgramStateRef State,const char * NL,const char * Sep) const312 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
313 const char *NL, const char *Sep) const {
314 LockMapTy LM = State->get<LockMap>();
315 if (!LM.isEmpty()) {
316 Out << Sep << "Mutex states:" << NL;
317 for (auto I : LM) {
318 I.first->dumpToStream(Out);
319 if (I.second.isLocked())
320 Out << ": locked";
321 else if (I.second.isUnlocked())
322 Out << ": unlocked";
323 else if (I.second.isDestroyed())
324 Out << ": destroyed";
325 else if (I.second.isUntouchedAndPossiblyDestroyed())
326 Out << ": not tracked, possibly destroyed";
327 else if (I.second.isUnlockedAndPossiblyDestroyed())
328 Out << ": unlocked, possibly destroyed";
329 Out << NL;
330 }
331 }
332
333 LockSetTy LS = State->get<LockSet>();
334 if (!LS.isEmpty()) {
335 Out << Sep << "Mutex lock order:" << NL;
336 for (auto I : LS) {
337 I->dumpToStream(Out);
338 Out << NL;
339 }
340 }
341
342 DestroyRetValTy DRV = State->get<DestroyRetVal>();
343 if (!DRV.isEmpty()) {
344 Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL;
345 for (auto I : DRV) {
346 I.first->dumpToStream(Out);
347 Out << ": ";
348 I.second->dumpToStream(Out);
349 Out << NL;
350 }
351 }
352 }
353
AcquirePthreadLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const354 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
355 CheckerContext &C,
356 CheckerKind CheckKind) const {
357 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
358 PthreadSemantics, CheckKind);
359 }
360
AcquireXNULock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const361 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
362 CheckerContext &C,
363 CheckerKind CheckKind) const {
364 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
365 XNUSemantics, CheckKind);
366 }
367
TryPthreadLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const368 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
369 CheckerContext &C,
370 CheckerKind CheckKind) const {
371 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
372 PthreadSemantics, CheckKind);
373 }
374
TryXNULock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const375 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
376 CheckerKind CheckKind) const {
377 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
378 PthreadSemantics, CheckKind);
379 }
380
TryFuchsiaLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const381 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
382 CheckerContext &C,
383 CheckerKind CheckKind) const {
384 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
385 PthreadSemantics, CheckKind);
386 }
387
TryC11Lock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const388 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
389 CheckerKind CheckKind) const {
390 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
391 PthreadSemantics, CheckKind);
392 }
393
AcquireLockAux(const CallEvent & Call,CheckerContext & C,const Expr * MtxExpr,SVal MtxVal,bool IsTryLock,enum LockingSemantics Semantics,CheckerKind CheckKind) const394 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
395 CheckerContext &C, const Expr *MtxExpr,
396 SVal MtxVal, bool IsTryLock,
397 enum LockingSemantics Semantics,
398 CheckerKind CheckKind) const {
399 if (!ChecksEnabled[CheckKind])
400 return;
401
402 const MemRegion *lockR = MtxVal.getAsRegion();
403 if (!lockR)
404 return;
405
406 ProgramStateRef state = C.getState();
407 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
408 if (sym)
409 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
410
411 if (const LockState *LState = state->get<LockMap>(lockR)) {
412 if (LState->isLocked()) {
413 reportBug(C, BT_doublelock, MtxExpr, CheckKind,
414 "This lock has already been acquired");
415 return;
416 } else if (LState->isDestroyed()) {
417 reportBug(C, BT_destroylock, MtxExpr, CheckKind,
418 "This lock has already been destroyed");
419 return;
420 }
421 }
422
423 ProgramStateRef lockSucc = state;
424 if (IsTryLock) {
425 // Bifurcate the state, and allow a mode where the lock acquisition fails.
426 SVal RetVal = Call.getReturnValue();
427 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
428 ProgramStateRef lockFail;
429 switch (Semantics) {
430 case PthreadSemantics:
431 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
432 break;
433 case XNUSemantics:
434 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
435 break;
436 default:
437 llvm_unreachable("Unknown tryLock locking semantics");
438 }
439 assert(lockFail && lockSucc);
440 C.addTransition(lockFail);
441 }
442 // We might want to handle the case when the mutex lock function was inlined
443 // and returned an Unknown or Undefined value.
444 } else if (Semantics == PthreadSemantics) {
445 // Assume that the return value was 0.
446 SVal RetVal = Call.getReturnValue();
447 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
448 // FIXME: If the lock function was inlined and returned true,
449 // we need to behave sanely - at least generate sink.
450 lockSucc = state->assume(*DefinedRetVal, false);
451 assert(lockSucc);
452 }
453 // We might want to handle the case when the mutex lock function was inlined
454 // and returned an Unknown or Undefined value.
455 } else {
456 // XNU locking semantics return void on non-try locks
457 assert((Semantics == XNUSemantics) && "Unknown locking semantics");
458 lockSucc = state;
459 }
460
461 // Record that the lock was acquired.
462 lockSucc = lockSucc->add<LockSet>(lockR);
463 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
464 C.addTransition(lockSucc);
465 }
466
ReleaseAnyLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const467 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
468 CheckerContext &C,
469 CheckerKind CheckKind) const {
470 ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
471 }
472
ReleaseLockAux(const CallEvent & Call,CheckerContext & C,const Expr * MtxExpr,SVal MtxVal,CheckerKind CheckKind) const473 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
474 CheckerContext &C, const Expr *MtxExpr,
475 SVal MtxVal,
476 CheckerKind CheckKind) const {
477 if (!ChecksEnabled[CheckKind])
478 return;
479
480 const MemRegion *lockR = MtxVal.getAsRegion();
481 if (!lockR)
482 return;
483
484 ProgramStateRef state = C.getState();
485 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
486 if (sym)
487 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
488
489 if (const LockState *LState = state->get<LockMap>(lockR)) {
490 if (LState->isUnlocked()) {
491 reportBug(C, BT_doubleunlock, MtxExpr, CheckKind,
492 "This lock has already been unlocked");
493 return;
494 } else if (LState->isDestroyed()) {
495 reportBug(C, BT_destroylock, MtxExpr, CheckKind,
496 "This lock has already been destroyed");
497 return;
498 }
499 }
500
501 LockSetTy LS = state->get<LockSet>();
502
503 if (!LS.isEmpty()) {
504 const MemRegion *firstLockR = LS.getHead();
505 if (firstLockR != lockR) {
506 reportBug(C, BT_lor, MtxExpr, CheckKind,
507 "This was not the most recently acquired lock. Possible lock "
508 "order reversal");
509 return;
510 }
511 // Record that the lock was released.
512 state = state->set<LockSet>(LS.getTail());
513 }
514
515 state = state->set<LockMap>(lockR, LockState::getUnlocked());
516 C.addTransition(state);
517 }
518
DestroyPthreadLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const519 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
520 CheckerContext &C,
521 CheckerKind CheckKind) const {
522 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0),
523 PthreadSemantics, CheckKind);
524 }
525
DestroyXNULock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const526 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
527 CheckerContext &C,
528 CheckerKind CheckKind) const {
529 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics,
530 CheckKind);
531 }
532
DestroyLockAux(const CallEvent & Call,CheckerContext & C,const Expr * MtxExpr,SVal MtxVal,enum LockingSemantics Semantics,CheckerKind CheckKind) const533 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
534 CheckerContext &C, const Expr *MtxExpr,
535 SVal MtxVal,
536 enum LockingSemantics Semantics,
537 CheckerKind CheckKind) const {
538 if (!ChecksEnabled[CheckKind])
539 return;
540
541 const MemRegion *LockR = MtxVal.getAsRegion();
542 if (!LockR)
543 return;
544
545 ProgramStateRef State = C.getState();
546
547 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
548 if (sym)
549 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
550
551 const LockState *LState = State->get<LockMap>(LockR);
552 // Checking the return value of the destroy method only in the case of
553 // PthreadSemantics
554 if (Semantics == PthreadSemantics) {
555 if (!LState || LState->isUnlocked()) {
556 SymbolRef sym = Call.getReturnValue().getAsSymbol();
557 if (!sym) {
558 State = State->remove<LockMap>(LockR);
559 C.addTransition(State);
560 return;
561 }
562 State = State->set<DestroyRetVal>(LockR, sym);
563 if (LState && LState->isUnlocked())
564 State = State->set<LockMap>(
565 LockR, LockState::getUnlockedAndPossiblyDestroyed());
566 else
567 State = State->set<LockMap>(
568 LockR, LockState::getUntouchedAndPossiblyDestroyed());
569 C.addTransition(State);
570 return;
571 }
572 } else {
573 if (!LState || LState->isUnlocked()) {
574 State = State->set<LockMap>(LockR, LockState::getDestroyed());
575 C.addTransition(State);
576 return;
577 }
578 }
579
580 StringRef Message = LState->isLocked()
581 ? "This lock is still locked"
582 : "This lock has already been destroyed";
583
584 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message);
585 }
586
InitAnyLock(const CallEvent & Call,CheckerContext & C,CheckerKind CheckKind) const587 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
588 CheckerKind CheckKind) const {
589 InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
590 }
591
InitLockAux(const CallEvent & Call,CheckerContext & C,const Expr * MtxExpr,SVal MtxVal,CheckerKind CheckKind) const592 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
593 const Expr *MtxExpr, SVal MtxVal,
594 CheckerKind CheckKind) const {
595 if (!ChecksEnabled[CheckKind])
596 return;
597
598 const MemRegion *LockR = MtxVal.getAsRegion();
599 if (!LockR)
600 return;
601
602 ProgramStateRef State = C.getState();
603
604 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
605 if (sym)
606 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
607
608 const struct LockState *LState = State->get<LockMap>(LockR);
609 if (!LState || LState->isDestroyed()) {
610 State = State->set<LockMap>(LockR, LockState::getUnlocked());
611 C.addTransition(State);
612 return;
613 }
614
615 StringRef Message = LState->isLocked()
616 ? "This lock is still being held"
617 : "This lock has already been initialized";
618
619 reportBug(C, BT_initlock, MtxExpr, CheckKind, Message);
620 }
621
reportBug(CheckerContext & C,std::unique_ptr<BugType> BT[],const Expr * MtxExpr,CheckerKind CheckKind,StringRef Desc) const622 void PthreadLockChecker::reportBug(CheckerContext &C,
623 std::unique_ptr<BugType> BT[],
624 const Expr *MtxExpr, CheckerKind CheckKind,
625 StringRef Desc) const {
626 ExplodedNode *N = C.generateErrorNode();
627 if (!N)
628 return;
629 initBugType(CheckKind);
630 auto Report =
631 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
632 Report->addRange(MtxExpr->getSourceRange());
633 C.emitReport(std::move(Report));
634 }
635
checkDeadSymbols(SymbolReaper & SymReaper,CheckerContext & C) const636 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
637 CheckerContext &C) const {
638 ProgramStateRef State = C.getState();
639
640 for (auto I : State->get<DestroyRetVal>()) {
641 // Once the return value symbol dies, no more checks can be performed
642 // against it. See if the return value was checked before this point.
643 // This would remove the symbol from the map as well.
644 if (SymReaper.isDead(I.second))
645 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
646 }
647
648 for (auto I : State->get<LockMap>()) {
649 // Stop tracking dead mutex regions as well.
650 if (!SymReaper.isLiveRegion(I.first)) {
651 State = State->remove<LockMap>(I.first);
652 State = State->remove<DestroyRetVal>(I.first);
653 }
654 }
655
656 // TODO: We probably need to clean up the lock stack as well.
657 // It is tricky though: even if the mutex cannot be unlocked anymore,
658 // it can still participate in lock order reversal resolution.
659
660 C.addTransition(State);
661 }
662
checkRegionChanges(ProgramStateRef State,const InvalidatedSymbols * Symbols,ArrayRef<const MemRegion * > ExplicitRegions,ArrayRef<const MemRegion * > Regions,const LocationContext * LCtx,const CallEvent * Call) const663 ProgramStateRef PthreadLockChecker::checkRegionChanges(
664 ProgramStateRef State, const InvalidatedSymbols *Symbols,
665 ArrayRef<const MemRegion *> ExplicitRegions,
666 ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,
667 const CallEvent *Call) const {
668
669 bool IsLibraryFunction = false;
670 if (Call && Call->isGlobalCFunction()) {
671 // Avoid invalidating mutex state when a known supported function is called.
672 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
673 C11Callbacks.lookup(*Call))
674 return State;
675
676 if (Call->isInSystemHeader())
677 IsLibraryFunction = true;
678 }
679
680 for (auto R : Regions) {
681 // We assume that system library function wouldn't touch the mutex unless
682 // it takes the mutex explicitly as an argument.
683 // FIXME: This is a bit quadratic.
684 if (IsLibraryFunction &&
685 std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) ==
686 ExplicitRegions.end())
687 continue;
688
689 State = State->remove<LockMap>(R);
690 State = State->remove<DestroyRetVal>(R);
691
692 // TODO: We need to invalidate the lock stack as well. This is tricky
693 // to implement correctly and efficiently though, because the effects
694 // of mutex escapes on lock order may be fairly varied.
695 }
696
697 return State;
698 }
699
registerPthreadLockBase(CheckerManager & mgr)700 void ento::registerPthreadLockBase(CheckerManager &mgr) {
701 mgr.registerChecker<PthreadLockChecker>();
702 }
703
shouldRegisterPthreadLockBase(const CheckerManager & mgr)704 bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }
705
706 #define REGISTER_CHECKER(name) \
707 void ento::register##name(CheckerManager &mgr) { \
708 PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>(); \
709 checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true; \
710 checker->CheckNames[PthreadLockChecker::CK_##name] = \
711 mgr.getCurrentCheckerName(); \
712 } \
713 \
714 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
715
716 REGISTER_CHECKER(PthreadLockChecker)
717 REGISTER_CHECKER(FuchsiaLockChecker)
718 REGISTER_CHECKER(C11LockChecker)
719