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