Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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 defines PthreadLockChecker, a simple lock -> unlock checker.
10
// Also handles XNU locks, which behave similarly enough to share code.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
15
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
16
#include "clang/StaticAnalyzer/Core/Checker.h"
17
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
20
21
using namespace clang;
22
using namespace ento;
23
24
namespace {
25
26
struct LockState {
27
  enum Kind {
28
    Destroyed,
29
    Locked,
30
    Unlocked,
31
    UntouchedAndPossiblyDestroyed,
32
    UnlockedAndPossiblyDestroyed
33
  } K;
34
35
private:
36
171
  LockState(Kind K) : K(K) {}
37
38
public:
39
53
  static LockState getLocked() { return LockState(Locked); }
40
59
  static LockState getUnlocked() { return LockState(Unlocked); }
41
31
  static LockState getDestroyed() { return LockState(Destroyed); }
42
15
  static LockState getUntouchedAndPossiblyDestroyed() {
43
15
    return LockState(UntouchedAndPossiblyDestroyed);
44
15
  }
45
13
  static LockState getUnlockedAndPossiblyDestroyed() {
46
13
    return LockState(UnlockedAndPossiblyDestroyed);
47
13
  }
48
49
27
  bool operator==(const LockState &X) const {
50
27
    return K == X.K;
51
27
  }
52
53
29
  bool isLocked() const { return K == Locked; }
54
74
  bool isUnlocked() const { return K == Unlocked; }
55
63
  bool isDestroyed() const { return K == Destroyed; }
56
10
  bool isUntouchedAndPossiblyDestroyed() const {
57
10
    return K == UntouchedAndPossiblyDestroyed;
58
10
  }
59
6
  bool isUnlockedAndPossiblyDestroyed() const {
60
6
    return K == UnlockedAndPossiblyDestroyed;
61
6
  }
62
63
194
  void Profile(llvm::FoldingSetNodeID &ID) const {
64
194
    ID.AddInteger(K);
65
194
  }
66
};
67
68
class PthreadLockChecker
69
    : public Checker<check::PostStmt<CallExpr>, check::DeadSymbols> {
70
  mutable std::unique_ptr<BugType> BT_doublelock;
71
  mutable std::unique_ptr<BugType> BT_doubleunlock;
72
  mutable std::unique_ptr<BugType> BT_destroylock;
73
  mutable std::unique_ptr<BugType> BT_initlock;
74
  mutable std::unique_ptr<BugType> BT_lor;
75
  enum LockingSemantics {
76
    NotApplicable = 0,
77
    PthreadSemantics,
78
    XNUSemantics
79
  };
80
public:
81
  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
82
  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
83
  void printState(raw_ostream &Out, ProgramStateRef State,
84
                  const char *NL, const char *Sep) const override;
85
86
  void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
87
                   bool isTryLock, enum LockingSemantics semantics) const;
88
89
  void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
90
  void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock,
91
                   enum LockingSemantics semantics) const;
92
  void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
93
  void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
94
  ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
95
                                                const MemRegion *lockR,
96
                                                const SymbolRef *sym) const;
97
};
98
} // end anonymous namespace
99
100
// A stack of locks for tracking lock-unlock order.
101
REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
102
103
// An entry for tracking lock states.
104
REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
105
106
// Return values for unresolved calls to pthread_mutex_destroy().
107
REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
108
109
void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
110
192
                                       CheckerContext &C) const {
111
192
  StringRef FName = C.getCalleeName(CE);
112
192
  if (FName.empty())
113
0
    return;
114
192
115
192
  if (CE->getNumArgs() != 1 && 
CE->getNumArgs() != 232
)
116
10
    return;
117
182
118
182
  if (FName == "pthread_mutex_lock" ||
119
182
      
FName == "pthread_rwlock_rdlock"140
||
120
182
      
FName == "pthread_rwlock_wrlock"140
)
121
42
    AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, PthreadSemantics);
122
140
  else if (FName == "lck_mtx_lock" ||
123
140
           
FName == "lck_rw_lock_exclusive"127
||
124
140
           
FName == "lck_rw_lock_shared"127
)
125
13
    AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, XNUSemantics);
126
127
  else if (FName == "pthread_mutex_trylock" ||
127
127
           
FName == "pthread_rwlock_tryrdlock"123
||
128
127
           
FName == "pthread_rwlock_trywrlock"123
)
129
4
    AcquireLock(C, CE, C.getSVal(CE->getArg(0)),
130
4
                true, PthreadSemantics);
131
123
  else if (FName == "lck_mtx_try_lock" ||
132
123
           
FName == "lck_rw_try_lock_exclusive"121
||
133
123
           
FName == "lck_rw_try_lock_shared"121
)
134
2
    AcquireLock(C, CE, C.getSVal(CE->getArg(0)), true, XNUSemantics);
135
121
  else if (FName == "pthread_mutex_unlock" ||
136
121
           
FName == "pthread_rwlock_unlock"76
||
137
121
           
FName == "lck_mtx_unlock"76
||
138
121
           
FName == "lck_rw_done"65
)
139
56
    ReleaseLock(C, CE, C.getSVal(CE->getArg(0)));
140
65
  else if (FName == "pthread_mutex_destroy")
141
31
    DestroyLock(C, CE, C.getSVal(CE->getArg(0)), PthreadSemantics);
142
34
  else if (FName == "lck_mtx_destroy")
143
5
    DestroyLock(C, CE, C.getSVal(CE->getArg(0)), XNUSemantics);
144
29
  else if (FName == "pthread_mutex_init")
145
16
    InitLock(C, CE, C.getSVal(CE->getArg(0)));
146
182
}
147
148
// When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
149
// sure if the destroy call has succeeded or failed, and the lock enters one of
150
// the 'possibly destroyed' state. There is a short time frame for the
151
// programmer to check the return value to see if the lock was successfully
152
// destroyed. Before we model the next operation over that lock, we call this
153
// function to see if the return value was checked by now and set the lock state
154
// - either to destroyed state or back to its previous state.
155
156
// In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
157
// successfully destroyed and it returns a non-zero value otherwise.
158
ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
159
38
    ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
160
38
  const LockState *lstate = state->get<LockMap>(lockR);
161
38
  // Existence in DestroyRetVal ensures existence in LockMap.
162
38
  // Existence in Destroyed also ensures that the lock state for lockR is either
163
38
  // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
164
38
  assert(lstate->isUntouchedAndPossiblyDestroyed() ||
165
38
         lstate->isUnlockedAndPossiblyDestroyed());
166
38
167
38
  ConstraintManager &CMgr = state->getConstraintManager();
168
38
  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
169
38
  if (retZero.isConstrainedFalse()) {
170
10
    if (lstate->isUntouchedAndPossiblyDestroyed())
171
4
      state = state->remove<LockMap>(lockR);
172
6
    else if (lstate->isUnlockedAndPossiblyDestroyed())
173
6
      state = state->set<LockMap>(lockR, LockState::getUnlocked());
174
10
  } else
175
28
    state = state->set<LockMap>(lockR, LockState::getDestroyed());
176
38
177
38
  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
178
38
  // now resolved.
179
38
  state = state->remove<DestroyRetVal>(lockR);
180
38
  return state;
181
38
}
182
183
void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
184
0
                                    const char *NL, const char *Sep) const {
185
0
  LockMapTy LM = State->get<LockMap>();
186
0
  if (!LM.isEmpty()) {
187
0
    Out << Sep << "Mutex states:" << NL;
188
0
    for (auto I : LM) {
189
0
      I.first->dumpToStream(Out);
190
0
      if (I.second.isLocked())
191
0
        Out << ": locked";
192
0
      else if (I.second.isUnlocked())
193
0
        Out << ": unlocked";
194
0
      else if (I.second.isDestroyed())
195
0
        Out << ": destroyed";
196
0
      else if (I.second.isUntouchedAndPossiblyDestroyed())
197
0
        Out << ": not tracked, possibly destroyed";
198
0
      else if (I.second.isUnlockedAndPossiblyDestroyed())
199
0
        Out << ": unlocked, possibly destroyed";
200
0
      Out << NL;
201
0
    }
202
0
  }
203
0
204
0
  LockSetTy LS = State->get<LockSet>();
205
0
  if (!LS.isEmpty()) {
206
0
    Out << Sep << "Mutex lock order:" << NL;
207
0
    for (auto I: LS) {
208
0
      I->dumpToStream(Out);
209
0
      Out << NL;
210
0
    }
211
0
  }
212
0
213
0
  // TODO: Dump destroyed mutex symbols?
214
0
}
215
216
void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
217
                                     SVal lock, bool isTryLock,
218
61
                                     enum LockingSemantics semantics) const {
219
61
220
61
  const MemRegion *lockR = lock.getAsRegion();
221
61
  if (!lockR)
222
0
    return;
223
61
224
61
  ProgramStateRef state = C.getState();
225
61
  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
226
61
  if (sym)
227
1
    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
228
61
229
61
  SVal X = C.getSVal(CE);
230
61
  if (X.isUnknownOrUndef())
231
0
    return;
232
61
233
61
  DefinedSVal retVal = X.castAs<DefinedSVal>();
234
61
235
61
  if (const LockState *LState = state->get<LockMap>(lockR)) {
236
19
    if (LState->isLocked()) {
237
4
      if (!BT_doublelock)
238
1
        BT_doublelock.reset(new BugType(this, "Double locking",
239
1
                                        "Lock checker"));
240
4
      ExplodedNode *N = C.generateErrorNode();
241
4
      if (!N)
242
0
        return;
243
4
      auto report = llvm::make_unique<BugReport>(
244
4
          *BT_doublelock, "This lock has already been acquired", N);
245
4
      report->addRange(CE->getArg(0)->getSourceRange());
246
4
      C.emitReport(std::move(report));
247
4
      return;
248
15
    } else if (LState->isDestroyed()) {
249
4
      reportUseDestroyedBug(C, CE);
250
4
      return;
251
4
    }
252
53
  }
253
53
254
53
  ProgramStateRef lockSucc = state;
255
53
  if (isTryLock) {
256
6
    // Bifurcate the state, and allow a mode where the lock acquisition fails.
257
6
    ProgramStateRef lockFail;
258
6
    switch (semantics) {
259
6
    case PthreadSemantics:
260
4
      std::tie(lockFail, lockSucc) = state->assume(retVal);
261
4
      break;
262
6
    case XNUSemantics:
263
2
      std::tie(lockSucc, lockFail) = state->assume(retVal);
264
2
      break;
265
6
    default:
266
0
      llvm_unreachable("Unknown tryLock locking semantics");
267
6
    }
268
6
    assert(lockFail && lockSucc);
269
6
    C.addTransition(lockFail);
270
6
271
47
  } else if (semantics == PthreadSemantics) {
272
37
    // Assume that the return value was 0.
273
37
    lockSucc = state->assume(retVal, false);
274
37
    assert(lockSucc);
275
37
276
37
  } else {
277
10
    // XNU locking semantics return void on non-try locks
278
10
    assert((semantics == XNUSemantics) && "Unknown locking semantics");
279
10
    lockSucc = state;
280
10
  }
281
53
282
53
  // Record that the lock was acquired.
283
53
  lockSucc = lockSucc->add<LockSet>(lockR);
284
53
  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
285
53
  C.addTransition(lockSucc);
286
53
}
287
288
void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
289
56
                                     SVal lock) const {
290
56
291
56
  const MemRegion *lockR = lock.getAsRegion();
292
56
  if (!lockR)
293
0
    return;
294
56
295
56
  ProgramStateRef state = C.getState();
296
56
  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
297
56
  if (sym)
298
0
    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
299
56
300
56
  if (const LockState *LState = state->get<LockMap>(lockR)) {
301
43
    if (LState->isUnlocked()) {
302
7
      if (!BT_doubleunlock)
303
1
        BT_doubleunlock.reset(new BugType(this, "Double unlocking",
304
1
                                          "Lock checker"));
305
7
      ExplodedNode *N = C.generateErrorNode();
306
7
      if (!N)
307
0
        return;
308
7
      auto Report = llvm::make_unique<BugReport>(
309
7
          *BT_doubleunlock, "This lock has already been unlocked", N);
310
7
      Report->addRange(CE->getArg(0)->getSourceRange());
311
7
      C.emitReport(std::move(Report));
312
7
      return;
313
36
    } else if (LState->isDestroyed()) {
314
3
      reportUseDestroyedBug(C, CE);
315
3
      return;
316
3
    }
317
46
  }
318
46
319
46
  LockSetTy LS = state->get<LockSet>();
320
46
321
46
  // FIXME: Better analysis requires IPA for wrappers.
322
46
323
46
  if (!LS.isEmpty()) {
324
33
    const MemRegion *firstLockR = LS.getHead();
325
33
    if (firstLockR != lockR) {
326
4
      if (!BT_lor)
327
1
        BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
328
4
      ExplodedNode *N = C.generateErrorNode();
329
4
      if (!N)
330
0
        return;
331
4
      auto report = llvm::make_unique<BugReport>(
332
4
          *BT_lor, "This was not the most recently acquired lock. Possible "
333
4
                   "lock order reversal", N);
334
4
      report->addRange(CE->getArg(0)->getSourceRange());
335
4
      C.emitReport(std::move(report));
336
4
      return;
337
4
    }
338
29
    // Record that the lock was released.
339
29
    state = state->set<LockSet>(LS.getTail());
340
29
  }
341
46
342
46
  state = state->set<LockMap>(lockR, LockState::getUnlocked());
343
42
  C.addTransition(state);
344
42
}
345
346
void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
347
                                     SVal Lock,
348
36
                                     enum LockingSemantics semantics) const {
349
36
350
36
  const MemRegion *LockR = Lock.getAsRegion();
351
36
  if (!LockR)
352
0
    return;
353
36
354
36
  ProgramStateRef State = C.getState();
355
36
356
36
  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
357
36
  if (sym)
358
0
    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
359
36
360
36
  const LockState *LState = State->get<LockMap>(LockR);
361
36
  // Checking the return value of the destroy method only in the case of
362
36
  // PthreadSemantics
363
36
  if (semantics == PthreadSemantics) {
364
31
    if (!LState || 
LState->isUnlocked()16
) {
365
28
      SymbolRef sym = C.getSVal(CE).getAsSymbol();
366
28
      if (!sym) {
367
0
        State = State->remove<LockMap>(LockR);
368
0
        C.addTransition(State);
369
0
        return;
370
0
      }
371
28
      State = State->set<DestroyRetVal>(LockR, sym);
372
28
      if (LState && 
LState->isUnlocked()13
)
373
13
        State = State->set<LockMap>(
374
13
            LockR, LockState::getUnlockedAndPossiblyDestroyed());
375
15
      else
376
15
        State = State->set<LockMap>(
377
15
            LockR, LockState::getUntouchedAndPossiblyDestroyed());
378
28
      C.addTransition(State);
379
28
      return;
380
28
    }
381
5
  } else {
382
5
    if (!LState || 
LState->isUnlocked()2
) {
383
3
      State = State->set<LockMap>(LockR, LockState::getDestroyed());
384
3
      C.addTransition(State);
385
3
      return;
386
3
    }
387
5
  }
388
5
  StringRef Message;
389
5
390
5
  if (LState->isLocked()) {
391
2
    Message = "This lock is still locked";
392
3
  } else {
393
3
    Message = "This lock has already been destroyed";
394
3
  }
395
5
396
5
  if (!BT_destroylock)
397
0
    BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
398
0
                                     "Lock checker"));
399
5
  ExplodedNode *N = C.generateErrorNode();
400
5
  if (!N)
401
0
    return;
402
5
  auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
403
5
  Report->addRange(CE->getArg(0)->getSourceRange());
404
5
  C.emitReport(std::move(Report));
405
5
}
406
407
void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
408
16
                                  SVal Lock) const {
409
16
410
16
  const MemRegion *LockR = Lock.getAsRegion();
411
16
  if (!LockR)
412
0
    return;
413
16
414
16
  ProgramStateRef State = C.getState();
415
16
416
16
  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
417
16
  if (sym)
418
0
    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
419
16
420
16
  const struct LockState *LState = State->get<LockMap>(LockR);
421
16
  if (!LState || 
LState->isDestroyed()12
) {
422
11
    State = State->set<LockMap>(LockR, LockState::getUnlocked());
423
11
    C.addTransition(State);
424
11
    return;
425
11
  }
426
5
427
5
  StringRef Message;
428
5
429
5
  if (LState->isLocked()) {
430
1
    Message = "This lock is still being held";
431
4
  } else {
432
4
    Message = "This lock has already been initialized";
433
4
  }
434
5
435
5
  if (!BT_initlock)
436
1
    BT_initlock.reset(new BugType(this, "Init invalid lock",
437
1
                                  "Lock checker"));
438
5
  ExplodedNode *N = C.generateErrorNode();
439
5
  if (!N)
440
0
    return;
441
5
  auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
442
5
  Report->addRange(CE->getArg(0)->getSourceRange());
443
5
  C.emitReport(std::move(Report));
444
5
}
445
446
void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
447
7
                                               const CallExpr *CE) const {
448
7
  if (!BT_destroylock)
449
1
    BT_destroylock.reset(new BugType(this, "Use destroyed lock",
450
1
                                     "Lock checker"));
451
7
  ExplodedNode *N = C.generateErrorNode();
452
7
  if (!N)
453
0
    return;
454
7
  auto Report = llvm::make_unique<BugReport>(
455
7
      *BT_destroylock, "This lock has already been destroyed", N);
456
7
  Report->addRange(CE->getArg(0)->getSourceRange());
457
7
  C.emitReport(std::move(Report));
458
7
}
459
460
void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
461
475
                                          CheckerContext &C) const {
462
475
  ProgramStateRef State = C.getState();
463
475
464
475
  // TODO: Clean LockMap when a mutex region dies.
465
475
466
475
  DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
467
475
  for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
468
475
                                 E = TrackedSymbols.end();
469
516
       I != E; 
++I41
) {
470
41
    const SymbolRef Sym = I->second;
471
41
    const MemRegion *lockR = I->first;
472
41
    bool IsSymDead = SymReaper.isDead(Sym);
473
41
    // Remove the dead symbol from the return value symbols map.
474
41
    if (IsSymDead)
475
37
      State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
476
41
  }
477
475
  C.addTransition(State);
478
475
}
479
480
5
void ento::registerPthreadLockChecker(CheckerManager &mgr) {
481
5
  mgr.registerChecker<PthreadLockChecker>();
482
5
}
483
484
5
bool ento::shouldRegisterPthreadLockChecker(const LangOptions &LO) {
485
5
  return true;
486
5
}