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
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 GRStateTrait<LockSet> :
50 public GRStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
GDMIndexclang::ento::GRStateTrait51 static void* GDMIndex() { static int x = 0; return &x; }
52 };
53 } // end GR namespace
54 } // end clang namespace
55
56
checkPostStmt(const CallExpr * CE,CheckerContext & C) const57 void 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
AcquireLock(CheckerContext & C,const CallExpr * CE,SVal lock,bool isTryLock,enum LockingSemantics semantics) const98 void 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
ReleaseLock(CheckerContext & C,const CallExpr * CE,SVal lock) const164 void 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
registerPthreadLockChecker(CheckerManager & mgr)202 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
203 mgr.registerChecker<PthreadLockChecker>();
204 }
205