Clang Project

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