PthreadLockChecker.cpp revision 5eca482fe895ea57bc82410222e6426c09e63284 
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/Checker.h"
17#include "clang/StaticAnalyzer/Core/CheckerManager.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19#include "clang/StaticAnalyzer/Core/BugReporter/BugType.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 llvm::OwningPtr<BugType> BT_doublelock;
29  mutable llvm::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.
46namespace { class LockSet {}; }
47namespace clang {
48namespace ento {
49template <> struct ProgramStateTrait<LockSet> :
50  public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
51    static void *GDMIndex() { static int x = 0; return &x; }
52};
53} // end of ento (ProgramState) namespace
54} // end clang namespace
55
56
57void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
58                                       CheckerContext &C) const {
59  const ProgramState *state = C.getState();
60  const LocationContext *LCtx = C.getLocationContext();
61  StringRef FName = C.getCalleeName(CE);
62  if (FName.empty())
63    return;
64
65  if (CE->getNumArgs() != 1)
66    return;
67
68  if (FName == "pthread_mutex_lock" ||
69      FName == "pthread_rwlock_rdlock" ||
70      FName == "pthread_rwlock_wrlock")
71    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
72                false, PthreadSemantics);
73  else if (FName == "lck_mtx_lock" ||
74           FName == "lck_rw_lock_exclusive" ||
75           FName == "lck_rw_lock_shared")
76    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
77                false, XNUSemantics);
78  else if (FName == "pthread_mutex_trylock" ||
79           FName == "pthread_rwlock_tryrdlock" ||
80           FName == "pthread_rwlock_tryrwlock")
81    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
82                true, PthreadSemantics);
83  else if (FName == "lck_mtx_try_lock" ||
84           FName == "lck_rw_try_lock_exclusive" ||
85           FName == "lck_rw_try_lock_shared")
86    AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
87                true, XNUSemantics);
88  else if (FName == "pthread_mutex_unlock" ||
89           FName == "pthread_rwlock_unlock" ||
90           FName == "lck_mtx_unlock" ||
91           FName == "lck_rw_done")
92    ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
93}
94
95void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
96                                     SVal lock, bool isTryLock,
97                                     enum LockingSemantics semantics) const {
98
99  const MemRegion *lockR = lock.getAsRegion();
100  if (!lockR)
101    return;
102
103  const ProgramState *state = C.getState();
104
105  SVal X = state->getSVal(CE, C.getLocationContext());
106  if (X.isUnknownOrUndef())
107    return;
108
109  DefinedSVal retVal = cast<DefinedSVal>(X);
110
111  if (state->contains<LockSet>(lockR)) {
112    if (!BT_doublelock)
113      BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
114    ExplodedNode *N = C.generateSink();
115    if (!N)
116      return;
117    BugReport *report = new BugReport(*BT_doublelock,
118                                                      "This lock has already "
119                                                      "been acquired", N);
120    report->addRange(CE->getArg(0)->getSourceRange());
121    C.EmitReport(report);
122    return;
123  }
124
125  const ProgramState *lockSucc = state;
126  if (isTryLock) {
127    // Bifurcate the state, and allow a mode where the lock acquisition fails.
128    const ProgramState *lockFail;
129    switch (semantics) {
130    case PthreadSemantics:
131      llvm::tie(lockFail, lockSucc) = state->assume(retVal);
132      break;
133    case XNUSemantics:
134      llvm::tie(lockSucc, lockFail) = state->assume(retVal);
135      break;
136    default:
137      llvm_unreachable("Unknown tryLock locking semantics");
138      break;
139    }
140    assert(lockFail && lockSucc);
141    C.addTransition(lockFail);
142
143  } else if (semantics == PthreadSemantics) {
144    // Assume that the return value was 0.
145    lockSucc = state->assume(retVal, false);
146    assert(lockSucc);
147
148  } else {
149    // XNU locking semantics return void on non-try locks
150    assert((semantics == XNUSemantics) && "Unknown locking semantics");
151    lockSucc = state;
152  }
153
154  // Record that the lock was acquired.
155  lockSucc = lockSucc->add<LockSet>(lockR);
156  C.addTransition(lockSucc);
157}
158
159void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
160                                     SVal lock) const {
161
162  const MemRegion *lockR = lock.getAsRegion();
163  if (!lockR)
164    return;
165
166  const ProgramState *state = C.getState();
167  llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();
168
169  // FIXME: Better analysis requires IPA for wrappers.
170  // FIXME: check for double unlocks
171  if (LS.isEmpty())
172    return;
173
174  const MemRegion *firstLockR = LS.getHead();
175  if (firstLockR != lockR) {
176    if (!BT_lor)
177      BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
178    ExplodedNode *N = C.generateSink();
179    if (!N)
180      return;
181    BugReport *report = new BugReport(*BT_lor,
182                                                      "This was not the most "
183                                                      "recently acquired lock. "
184                                                      "Possible lock order "
185                                                      "reversal", N);
186    report->addRange(CE->getArg(0)->getSourceRange());
187    C.EmitReport(report);
188    return;
189  }
190
191  // Record that the lock was released.
192  state = state->set<LockSet>(LS.getTail());
193  C.addTransition(state);
194}
195
196
197void ento::registerPthreadLockChecker(CheckerManager &mgr) {
198  mgr.registerChecker<PthreadLockChecker>();
199}
200