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