Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp
Line
Count
Source (jump to first uncovered line)
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
249
  LockState(Kind K) : K(K) {}
43
44
public:
45
86
  static LockState getLocked() { return LockState(Locked); }
46
90
  static LockState getUnlocked() { return LockState(Unlocked); }
47
38
  static LockState getDestroyed() { return LockState(Destroyed); }
48
15
  static LockState getUntouchedAndPossiblyDestroyed() {
49
15
    return LockState(UntouchedAndPossiblyDestroyed);
50
15
  }
51
20
  static LockState getUnlockedAndPossiblyDestroyed() {
52
20
    return LockState(UnlockedAndPossiblyDestroyed);
53
20
  }
54
55
48
  bool operator==(const LockState &X) const { return K == X.K; }
56
57
47
  bool isLocked() const { return K == Locked; }
58
112
  bool isUnlocked() const { return K == Unlocked; }
59
95
  bool isDestroyed() const { return K == Destroyed; }
60
55
  bool isUntouchedAndPossiblyDestroyed() const {
61
55
    return K == UntouchedAndPossiblyDestroyed;
62
55
  }
63
32
  bool isUnlockedAndPossiblyDestroyed() const {
64
32
    return K == UnlockedAndPossiblyDestroyed;
65
32
  }
66
67
277
  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
45
  void initBugType(CheckerKind checkKind) const {
230
45
    if (BT_doublelock[checkKind])
231
42
      return;
232
3
    BT_doublelock[checkKind].reset(
233
3
        new BugType{CheckNames[checkKind], "Double locking", "Lock checker"});
234
3
    BT_doubleunlock[checkKind].reset(
235
3
        new BugType{CheckNames[checkKind], "Double unlocking", "Lock checker"});
236
3
    BT_destroylock[checkKind].reset(new BugType{
237
3
        CheckNames[checkKind], "Use destroyed lock", "Lock checker"});
238
3
    BT_initlock[checkKind].reset(new BugType{
239
3
        CheckNames[checkKind], "Init invalid lock", "Lock checker"});
240
3
    BT_lor[checkKind].reset(new BugType{CheckNames[checkKind],
241
3
                                        "Lock order reversal", "Lock checker"});
242
3
  }
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
2.51k
                                       CheckerContext &C) const {
257
2.51k
  // An additional umbrella check that all functions modeled by this checker
258
2.51k
  // are global C functions.
259
2.51k
  // TODO: Maybe make this the default behavior of CallDescription
260
2.51k
  // with exactly one identifier?
261
2.51k
  // FIXME: Try to handle cases when the implementation was inlined rather
262
2.51k
  // than just giving up.
263
2.51k
  if (!Call.isGlobalCFunction() || 
C.wasInlined1.62k
)
264
1.22k
    return;
265
1.28k
266
1.28k
  if (const FnCheck *Callback = PThreadCallbacks.lookup(Call))
267
189
    (this->**Callback)(Call, C, CK_PthreadLockChecker);
268
1.09k
  else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
269
33
    (this->**Callback)(Call, C, CK_FuchsiaLockChecker);
270
1.06k
  else if (const FnCheck *Callback = C11Callbacks.lookup(Call))
271
31
    (this->**Callback)(Call, C, CK_C11LockChecker);
272
1.28k
}
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
45
    ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
286
45
  const LockState *lstate = state->get<LockMap>(lockR);
287
45
  // Existence in DestroyRetVal ensures existence in LockMap.
288
45
  // Existence in Destroyed also ensures that the lock state for lockR is either
289
45
  // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
290
45
  assert(lstate->isUntouchedAndPossiblyDestroyed() ||
291
45
         lstate->isUnlockedAndPossiblyDestroyed());
292
45
293
45
  ConstraintManager &CMgr = state->getConstraintManager();
294
45
  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
295
45
  if (retZero.isConstrainedFalse()) {
296
10
    if (lstate->isUntouchedAndPossiblyDestroyed())
297
4
      state = state->remove<LockMap>(lockR);
298
6
    else if (lstate->isUnlockedAndPossiblyDestroyed())
299
6
      state = state->set<LockMap>(lockR, LockState::getUnlocked());
300
10
  } else
301
35
    state = state->set<LockMap>(lockR, LockState::getDestroyed());
302
45
303
45
  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
304
45
  // now resolved.
305
45
  state = state->remove<DestroyRetVal>(lockR);
306
45
  return state;
307
45
}
308
309
void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
310
0
                                    const char *NL, const char *Sep) const {
311
0
  LockMapTy LM = State->get<LockMap>();
312
0
  if (!LM.isEmpty()) {
313
0
    Out << Sep << "Mutex states:" << NL;
314
0
    for (auto I : LM) {
315
0
      I.first->dumpToStream(Out);
316
0
      if (I.second.isLocked())
317
0
        Out << ": locked";
318
0
      else if (I.second.isUnlocked())
319
0
        Out << ": unlocked";
320
0
      else if (I.second.isDestroyed())
321
0
        Out << ": destroyed";
322
0
      else if (I.second.isUntouchedAndPossiblyDestroyed())
323
0
        Out << ": not tracked, possibly destroyed";
324
0
      else if (I.second.isUnlockedAndPossiblyDestroyed())
325
0
        Out << ": unlocked, possibly destroyed";
326
0
      Out << NL;
327
0
    }
328
0
  }
329
0
330
0
  LockSetTy LS = State->get<LockSet>();
331
0
  if (!LS.isEmpty()) {
332
0
    Out << Sep << "Mutex lock order:" << NL;
333
0
    for (auto I : LS) {
334
0
      I->dumpToStream(Out);
335
0
      Out << NL;
336
0
    }
337
0
  }
338
0
339
0
  // TODO: Dump destroyed mutex symbols?
340
0
}
341
342
void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
343
                                            CheckerContext &C,
344
67
                                            CheckerKind checkKind) const {
345
67
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, PthreadSemantics,
346
67
                 checkKind);
347
67
}
348
349
void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
350
                                        CheckerContext &C,
351
17
                                        CheckerKind checkKind) const {
352
17
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, XNUSemantics,
353
17
                 checkKind);
354
17
}
355
356
void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
357
                                        CheckerContext &C,
358
4
                                        CheckerKind checkKind) const {
359
4
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
360
4
                 checkKind);
361
4
}
362
363
void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
364
2
                                    CheckerKind checkKind) const {
365
2
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
366
2
                 checkKind);
367
2
}
368
369
void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
370
                                        CheckerContext &C,
371
5
                                        CheckerKind checkKind) const {
372
5
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
373
5
                 checkKind);
374
5
}
375
376
void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
377
3
                                    CheckerKind checkKind) const {
378
3
  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
379
3
                 checkKind);
380
3
}
381
382
void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
383
                                        CheckerContext &C, unsigned ArgNo,
384
                                        SVal lock, bool isTryLock,
385
                                        enum LockingSemantics semantics,
386
98
                                        CheckerKind checkKind) const {
387
98
  if (!ChecksEnabled[checkKind])
388
0
    return;
389
98
390
98
  const MemRegion *lockR = lock.getAsRegion();
391
98
  if (!lockR)
392
0
    return;
393
98
394
98
  ProgramStateRef state = C.getState();
395
98
  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
396
98
  if (sym)
397
1
    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
398
98
399
98
  if (const LockState *LState = state->get<LockMap>(lockR)) {
400
37
    if (LState->isLocked()) {
401
8
      ExplodedNode *N = C.generateErrorNode();
402
8
      if (!N)
403
0
        return;
404
8
      initBugType(checkKind);
405
8
      auto report = std::make_unique<PathSensitiveBugReport>(
406
8
          *BT_doublelock[checkKind], "This lock has already been acquired", N);
407
8
      report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
408
8
      C.emitReport(std::move(report));
409
8
      return;
410
29
    } else if (LState->isDestroyed()) {
411
4
      reportUseDestroyedBug(Call, C, ArgNo, checkKind);
412
4
      return;
413
4
    }
414
86
  }
415
86
416
86
  ProgramStateRef lockSucc = state;
417
86
  if (isTryLock) {
418
14
    // Bifurcate the state, and allow a mode where the lock acquisition fails.
419
14
    SVal RetVal = Call.getReturnValue();
420
14
    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
421
14
      ProgramStateRef lockFail;
422
14
      switch (semantics) {
423
14
      case PthreadSemantics:
424
14
        std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
425
14
        break;
426
0
      case XNUSemantics:
427
0
        std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
428
0
        break;
429
0
      default:
430
0
        llvm_unreachable("Unknown tryLock locking semantics");
431
14
      }
432
14
      assert(lockFail && lockSucc);
433
14
      C.addTransition(lockFail);
434
14
    }
435
14
    // We might want to handle the case when the mutex lock function was inlined
436
14
    // and returned an Unknown or Undefined value.
437
72
  } else if (semantics == PthreadSemantics) {
438
58
    // Assume that the return value was 0.
439
58
    SVal RetVal = Call.getReturnValue();
440
58
    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
441
49
      // FIXME: If the lock function was inlined and returned true,
442
49
      // we need to behave sanely - at least generate sink.
443
49
      lockSucc = state->assume(*DefinedRetVal, false);
444
49
      assert(lockSucc);
445
49
    }
446
58
    // We might want to handle the case when the mutex lock function was inlined
447
58
    // and returned an Unknown or Undefined value.
448
58
  } else {
449
14
    // XNU locking semantics return void on non-try locks
450
14
    assert((semantics == XNUSemantics) && "Unknown locking semantics");
451
14
    lockSucc = state;
452
14
  }
453
86
454
86
  // Record that the lock was acquired.
455
86
  lockSucc = lockSucc->add<LockSet>(lockR);
456
86
  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
457
86
  C.addTransition(lockSucc);
458
86
}
459
460
void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
461
                                        CheckerContext &C,
462
84
                                        CheckerKind checkKind) const {
463
84
  ReleaseLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
464
84
}
465
466
void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
467
                                        CheckerContext &C, unsigned ArgNo,
468
                                        SVal lock,
469
84
                                        CheckerKind checkKind) const {
470
84
  if (!ChecksEnabled[checkKind])
471
0
    return;
472
84
473
84
  const MemRegion *lockR = lock.getAsRegion();
474
84
  if (!lockR)
475
0
    return;
476
84
477
84
  ProgramStateRef state = C.getState();
478
84
  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
479
84
  if (sym)
480
0
    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
481
84
482
84
  if (const LockState *LState = state->get<LockMap>(lockR)) {
483
67
    if (LState->isUnlocked()) {
484
13
      ExplodedNode *N = C.generateErrorNode();
485
13
      if (!N)
486
0
        return;
487
13
      initBugType(checkKind);
488
13
      auto Report = std::make_unique<PathSensitiveBugReport>(
489
13
          *BT_doubleunlock[checkKind], "This lock has already been unlocked",
490
13
          N);
491
13
      Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
492
13
      C.emitReport(std::move(Report));
493
13
      return;
494
54
    } else if (LState->isDestroyed()) {
495
3
      reportUseDestroyedBug(Call, C, ArgNo, checkKind);
496
3
      return;
497
3
    }
498
68
  }
499
68
500
68
  LockSetTy LS = state->get<LockSet>();
501
68
502
68
  if (!LS.isEmpty()) {
503
52
    const MemRegion *firstLockR = LS.getHead();
504
52
    if (firstLockR != lockR) {
505
7
      ExplodedNode *N = C.generateErrorNode();
506
7
      if (!N)
507
0
        return;
508
7
      initBugType(checkKind);
509
7
      auto report = std::make_unique<PathSensitiveBugReport>(
510
7
          *BT_lor[checkKind],
511
7
          "This was not the most recently acquired lock. Possible "
512
7
          "lock order reversal",
513
7
          N);
514
7
      report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
515
7
      C.emitReport(std::move(report));
516
7
      return;
517
7
    }
518
45
    // Record that the lock was released.
519
45
    state = state->set<LockSet>(LS.getTail());
520
45
  }
521
68
522
68
  state = state->set<LockMap>(lockR, LockState::getUnlocked());
523
61
  C.addTransition(state);
524
61
}
525
526
void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
527
                                            CheckerContext &C,
528
38
                                            CheckerKind checkKind) const {
529
38
  DestroyLockAux(Call, C, 0, Call.getArgSVal(0), PthreadSemantics, checkKind);
530
38
}
531
532
void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
533
                                        CheckerContext &C,
534
5
                                        CheckerKind checkKind) const {
535
5
  DestroyLockAux(Call, C, 0, Call.getArgSVal(0), XNUSemantics, checkKind);
536
5
}
537
538
void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
539
                                        CheckerContext &C, unsigned ArgNo,
540
                                        SVal Lock,
541
                                        enum LockingSemantics semantics,
542
43
                                        CheckerKind checkKind) const {
543
43
  if (!ChecksEnabled[checkKind])
544
0
    return;
545
43
546
43
  const MemRegion *LockR = Lock.getAsRegion();
547
43
  if (!LockR)
548
0
    return;
549
43
550
43
  ProgramStateRef State = C.getState();
551
43
552
43
  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
553
43
  if (sym)
554
0
    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
555
43
556
43
  const LockState *LState = State->get<LockMap>(LockR);
557
43
  // Checking the return value of the destroy method only in the case of
558
43
  // PthreadSemantics
559
43
  if (semantics == PthreadSemantics) {
560
38
    if (!LState || 
LState->isUnlocked()23
) {
561
35
      SymbolRef sym = Call.getReturnValue().getAsSymbol();
562
35
      if (!sym) {
563
0
        State = State->remove<LockMap>(LockR);
564
0
        C.addTransition(State);
565
0
        return;
566
0
      }
567
35
      State = State->set<DestroyRetVal>(LockR, sym);
568
35
      if (LState && 
LState->isUnlocked()20
)
569
20
        State = State->set<LockMap>(
570
20
            LockR, LockState::getUnlockedAndPossiblyDestroyed());
571
15
      else
572
15
        State = State->set<LockMap>(
573
15
            LockR, LockState::getUntouchedAndPossiblyDestroyed());
574
35
      C.addTransition(State);
575
35
      return;
576
35
    }
577
5
  } else {
578
5
    if (!LState || 
LState->isUnlocked()2
) {
579
3
      State = State->set<LockMap>(LockR, LockState::getDestroyed());
580
3
      C.addTransition(State);
581
3
      return;
582
3
    }
583
5
  }
584
5
  StringRef Message;
585
5
586
5
  if (LState->isLocked()) {
587
2
    Message = "This lock is still locked";
588
3
  } else {
589
3
    Message = "This lock has already been destroyed";
590
3
  }
591
5
592
5
  ExplodedNode *N = C.generateErrorNode();
593
5
  if (!N)
594
0
    return;
595
5
  initBugType(checkKind);
596
5
  auto Report = std::make_unique<PathSensitiveBugReport>(
597
5
      *BT_destroylock[checkKind], Message, N);
598
5
  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
599
5
  C.emitReport(std::move(Report));
600
5
}
601
602
void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
603
28
                                     CheckerKind checkKind) const {
604
28
  InitLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
605
28
}
606
607
void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
608
                                     unsigned ArgNo, SVal Lock,
609
28
                                     CheckerKind checkKind) const {
610
28
  if (!ChecksEnabled[checkKind])
611
0
    return;
612
28
613
28
  const MemRegion *LockR = Lock.getAsRegion();
614
28
  if (!LockR)
615
0
    return;
616
28
617
28
  ProgramStateRef State = C.getState();
618
28
619
28
  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
620
28
  if (sym)
621
0
    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
622
28
623
28
  const struct LockState *LState = State->get<LockMap>(LockR);
624
28
  if (!LState || 
LState->isDestroyed()12
) {
625
23
    State = State->set<LockMap>(LockR, LockState::getUnlocked());
626
23
    C.addTransition(State);
627
23
    return;
628
23
  }
629
5
630
5
  StringRef Message;
631
5
632
5
  if (LState->isLocked()) {
633
1
    Message = "This lock is still being held";
634
4
  } else {
635
4
    Message = "This lock has already been initialized";
636
4
  }
637
5
638
5
  ExplodedNode *N = C.generateErrorNode();
639
5
  if (!N)
640
0
    return;
641
5
  initBugType(checkKind);
642
5
  auto Report = std::make_unique<PathSensitiveBugReport>(
643
5
      *BT_initlock[checkKind], Message, N);
644
5
  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
645
5
  C.emitReport(std::move(Report));
646
5
}
647
648
void PthreadLockChecker::reportUseDestroyedBug(const CallEvent &Call,
649
                                               CheckerContext &C,
650
                                               unsigned ArgNo,
651
7
                                               CheckerKind checkKind) const {
652
7
  ExplodedNode *N = C.generateErrorNode();
653
7
  if (!N)
654
0
    return;
655
7
  initBugType(checkKind);
656
7
  auto Report = std::make_unique<PathSensitiveBugReport>(
657
7
      *BT_destroylock[checkKind], "This lock has already been destroyed", N);
658
7
  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
659
7
  C.emitReport(std::move(Report));
660
7
}
661
662
void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
663
10.3k
                                          CheckerContext &C) const {
664
10.3k
  ProgramStateRef State = C.getState();
665
10.3k
666
10.3k
  for (auto I : State->get<DestroyRetVal>()) {
667
48
    // Once the return value symbol dies, no more checks can be performed
668
48
    // against it. See if the return value was checked before this point.
669
48
    // This would remove the symbol from the map as well.
670
48
    if (SymReaper.isDead(I.second))
671
44
      State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
672
48
  }
673
10.3k
674
10.3k
  for (auto I : State->get<LockMap>()) {
675
284
    // Stop tracking dead mutex regions as well.
676
284
    if (!SymReaper.isLiveRegion(I.first))
677
15
      State = State->remove<LockMap>(I.first);
678
284
  }
679
10.3k
680
10.3k
  // TODO: We probably need to clean up the lock stack as well.
681
10.3k
  // It is tricky though: even if the mutex cannot be unlocked anymore,
682
10.3k
  // it can still participate in lock order reversal resolution.
683
10.3k
684
10.3k
  C.addTransition(State);
685
10.3k
}
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
4.15k
    const CallEvent *Call) const {
692
4.15k
693
4.15k
  bool IsLibraryFunction = false;
694
4.15k
  if (Call && 
Call->isGlobalCFunction()1.44k
) {
695
847
    // Avoid invalidating mutex state when a known supported function is called.
696
847
    if (PThreadCallbacks.lookup(*Call) || 
FuchsiaCallbacks.lookup(*Call)657
||
697
847
        
C11Callbacks.lookup(*Call)624
)
698
254
      return State;
699
593
700
593
    if (Call->isInSystemHeader())
701
2
      IsLibraryFunction = true;
702
593
  }
703
4.15k
704
7.24k
  
for (auto R : Regions)3.90k
{
705
7.24k
    // We assume that system library function wouldn't touch the mutex unless
706
7.24k
    // it takes the mutex explicitly as an argument.
707
7.24k
    // FIXME: This is a bit quadratic.
708
7.24k
    if (IsLibraryFunction &&
709
7.24k
        std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) ==
710
5
            ExplicitRegions.end())
711
4
      continue;
712
7.24k
713
7.24k
    State = State->remove<LockMap>(R);
714
7.24k
    State = State->remove<DestroyRetVal>(R);
715
7.24k
716
7.24k
    // TODO: We need to invalidate the lock stack as well. This is tricky
717
7.24k
    // to implement correctly and efficiently though, because the effects
718
7.24k
    // of mutex escapes on lock order may be fairly varied.
719
7.24k
  }
720
3.90k
721
3.90k
  return State;
722
4.15k
}
723
724
74
void ento::registerPthreadLockBase(CheckerManager &mgr) {
725
74
  mgr.registerChecker<PthreadLockChecker>();
726
74
}
727
728
69
bool ento::shouldRegisterPthreadLockBase(const LangOptions &LO) { return true; }
729
730
#define REGISTER_CHECKER(name)                                                 \
731
78
  void ento::register##name(CheckerManager &mgr) {                             \
732
78
    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733
78
    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734
78
    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735
78
        mgr.getCurrentCheckerName();                                           \
736
78
  }                                                                            \
clang::ento::registerPthreadLockChecker(clang::ento::CheckerManager&)
Line
Count
Source
731
5
  void ento::register##name(CheckerManager &mgr) {                             \
732
5
    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733
5
    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734
5
    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735
5
        mgr.getCurrentCheckerName();                                           \
736
5
  }                                                                            \
clang::ento::registerFuchsiaLockChecker(clang::ento::CheckerManager&)
Line
Count
Source
731
3
  void ento::register##name(CheckerManager &mgr) {                             \
732
3
    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733
3
    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734
3
    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735
3
        mgr.getCurrentCheckerName();                                           \
736
3
  }                                                                            \
clang::ento::registerC11LockChecker(clang::ento::CheckerManager&)
Line
Count
Source
731
70
  void ento::register##name(CheckerManager &mgr) {                             \
732
70
    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733
70
    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734
70
    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735
70
        mgr.getCurrentCheckerName();                                           \
736
70
  }                                                                            \
737
                                                                               \
738
78
  bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
clang::ento::shouldRegisterPthreadLockChecker(clang::LangOptions const&)
Line
Count
Source
738
5
  bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
clang::ento::shouldRegisterFuchsiaLockChecker(clang::LangOptions const&)
Line
Count
Source
738
3
  bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
clang::ento::shouldRegisterC11LockChecker(clang::LangOptions const&)
Line
Count
Source
738
70
  bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
739
740
REGISTER_CHECKER(PthreadLockChecker)
741
REGISTER_CHECKER(FuchsiaLockChecker)
742
REGISTER_CHECKER(C11LockChecker)