1//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This defines PthreadLockChecker, a simple lock -> unlock checker.
11// Also handles XNU locks, which behave similarly enough to share code.
12//
13//===----------------------------------------------------------------------===//
14
15#include "ClangSACheckers.h"
16#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17#include "clang/StaticAnalyzer/Core/Checker.h"
18#include "clang/StaticAnalyzer/Core/CheckerManager.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
21#include "llvm/ADT/ImmutableList.h"
22
23using namespace clang;
24using namespace ento;
25
26namespace {
27class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
28  mutable OwningPtr<BugType> BT_doublelock;
29  mutable OwningPtr<BugType> BT_lor;
30  enum LockingSemantics {
31    NotApplicable = 0,
32    PthreadSemantics,
33    XNUSemantics
34  };
35public:
36  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
37
38  void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
39                   bool isTryLock, enum LockingSemantics semantics) const;
40
41  void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
42};
43} // end anonymous namespace
44
45// GDM Entry for tracking lock state.
46REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
47
48
49void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
50                                       CheckerContext &C) const {
51  ProgramStateRef state = C.getState();
52  const LocationContext *LCtx = C.getLocationContext();
53  StringRef FName = C.getCalleeName(CE);
54  if (FName.empty())
55    return;
56
57  if (CE->getNumArgs() != 1)
58    return;
59
60  if (FName == "pthread_mutex_lock" ||
61      FName == "pthread_rwlock_rdlock" ||
62      FName == "pthread_rwlock_wrlock")
63    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
64                false, PthreadSemantics);
65  else if (FName == "lck_mtx_lock" ||
66           FName == "lck_rw_lock_exclusive" ||
67           FName == "lck_rw_lock_shared")
68    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
69                false, XNUSemantics);
70  else if (FName == "pthread_mutex_trylock" ||
71           FName == "pthread_rwlock_tryrdlock" ||
72           FName == "pthread_rwlock_tryrwlock")
73    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
74                true, PthreadSemantics);
75  else if (FName == "lck_mtx_try_lock" ||
76           FName == "lck_rw_try_lock_exclusive" ||
77           FName == "lck_rw_try_lock_shared")
78    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
79                true, XNUSemantics);
80  else if (FName == "pthread_mutex_unlock" ||
81           FName == "pthread_rwlock_unlock" ||
82           FName == "lck_mtx_unlock" ||
83           FName == "lck_rw_done")
84    ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
85}
86
87void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
88                                     SVal lock, bool isTryLock,
89                                     enum LockingSemantics semantics) const {
90
91  const MemRegion *lockR = lock.getAsRegion();
92  if (!lockR)
93    return;
94
95  ProgramStateRef state = C.getState();
96
97  SVal X = state->getSVal(CE, C.getLocationContext());
98  if (X.isUnknownOrUndef())
99    return;
100
101  DefinedSVal retVal = X.castAs<DefinedSVal>();
102
103  if (state->contains<LockSet>(lockR)) {
104    if (!BT_doublelock)
105      BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
106    ExplodedNode *N = C.generateSink();
107    if (!N)
108      return;
109    BugReport *report = new BugReport(*BT_doublelock,
110                                                      "This lock has already "
111                                                      "been acquired", N);
112    report->addRange(CE->getArg(0)->getSourceRange());
113    C.emitReport(report);
114    return;
115  }
116
117  ProgramStateRef lockSucc = state;
118  if (isTryLock) {
119    // Bifurcate the state, and allow a mode where the lock acquisition fails.
120    ProgramStateRef lockFail;
121    switch (semantics) {
122    case PthreadSemantics:
123      llvm::tie(lockFail, lockSucc) = state->assume(retVal);
124      break;
125    case XNUSemantics:
126      llvm::tie(lockSucc, lockFail) = state->assume(retVal);
127      break;
128    default:
129      llvm_unreachable("Unknown tryLock locking semantics");
130    }
131    assert(lockFail && lockSucc);
132    C.addTransition(lockFail);
133
134  } else if (semantics == PthreadSemantics) {
135    // Assume that the return value was 0.
136    lockSucc = state->assume(retVal, false);
137    assert(lockSucc);
138
139  } else {
140    // XNU locking semantics return void on non-try locks
141    assert((semantics == XNUSemantics) && "Unknown locking semantics");
142    lockSucc = state;
143  }
144
145  // Record that the lock was acquired.
146  lockSucc = lockSucc->add<LockSet>(lockR);
147  C.addTransition(lockSucc);
148}
149
150void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
151                                     SVal lock) const {
152
153  const MemRegion *lockR = lock.getAsRegion();
154  if (!lockR)
155    return;
156
157  ProgramStateRef state = C.getState();
158  LockSetTy LS = state->get<LockSet>();
159
160  // FIXME: Better analysis requires IPA for wrappers.
161  // FIXME: check for double unlocks
162  if (LS.isEmpty())
163    return;
164
165  const MemRegion *firstLockR = LS.getHead();
166  if (firstLockR != lockR) {
167    if (!BT_lor)
168      BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
169    ExplodedNode *N = C.generateSink();
170    if (!N)
171      return;
172    BugReport *report = new BugReport(*BT_lor,
173                                                      "This was not the most "
174                                                      "recently acquired lock. "
175                                                      "Possible lock order "
176                                                      "reversal", N);
177    report->addRange(CE->getArg(0)->getSourceRange());
178    C.emitReport(report);
179    return;
180  }
181
182  // Record that the lock was released.
183  state = state->set<LockSet>(LS.getTail());
184  C.addTransition(state);
185}
186
187
188void ento::registerPthreadLockChecker(CheckerManager &mgr) {
189  mgr.registerChecker<PthreadLockChecker>();
190}
191