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
23 using namespace clang;
24 using namespace ento;
25
26 namespace {
27
28 struct LockState {
29 enum Kind { Destroyed, Locked, Unlocked } K;
30
31 private:
LockState__anon924e21fa0111::LockState32 LockState(Kind K) : K(K) {}
33
34 public:
getLocked__anon924e21fa0111::LockState35 static LockState getLocked(void) { return LockState(Locked); }
getUnlocked__anon924e21fa0111::LockState36 static LockState getUnlocked(void) { return LockState(Unlocked); }
getDestroyed__anon924e21fa0111::LockState37 static LockState getDestroyed(void) { return LockState(Destroyed); }
38
operator ==__anon924e21fa0111::LockState39 bool operator==(const LockState &X) const {
40 return K == X.K;
41 }
42
isLocked__anon924e21fa0111::LockState43 bool isLocked() const { return K == Locked; }
isUnlocked__anon924e21fa0111::LockState44 bool isUnlocked() const { return K == Unlocked; }
isDestroyed__anon924e21fa0111::LockState45 bool isDestroyed() const { return K == Destroyed; }
46
Profile__anon924e21fa0111::LockState47 void Profile(llvm::FoldingSetNodeID &ID) const {
48 ID.AddInteger(K);
49 }
50 };
51
52 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
53 mutable std::unique_ptr<BugType> BT_doublelock;
54 mutable std::unique_ptr<BugType> BT_doubleunlock;
55 mutable std::unique_ptr<BugType> BT_destroylock;
56 mutable std::unique_ptr<BugType> BT_initlock;
57 mutable std::unique_ptr<BugType> BT_lor;
58 enum LockingSemantics {
59 NotApplicable = 0,
60 PthreadSemantics,
61 XNUSemantics
62 };
63 public:
64 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
65
66 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
67 bool isTryLock, enum LockingSemantics semantics) const;
68
69 void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
70 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
71 void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
72 void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
73 };
74 } // end anonymous namespace
75
76 // GDM Entry for tracking lock state.
REGISTER_LIST_WITH_PROGRAMSTATE(LockSet,const MemRegion *)77 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
78
79 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
80
81 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
82 CheckerContext &C) const {
83 ProgramStateRef state = C.getState();
84 const LocationContext *LCtx = C.getLocationContext();
85 StringRef FName = C.getCalleeName(CE);
86 if (FName.empty())
87 return;
88
89 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
90 return;
91
92 if (FName == "pthread_mutex_lock" ||
93 FName == "pthread_rwlock_rdlock" ||
94 FName == "pthread_rwlock_wrlock")
95 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
96 false, PthreadSemantics);
97 else if (FName == "lck_mtx_lock" ||
98 FName == "lck_rw_lock_exclusive" ||
99 FName == "lck_rw_lock_shared")
100 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
101 false, XNUSemantics);
102 else if (FName == "pthread_mutex_trylock" ||
103 FName == "pthread_rwlock_tryrdlock" ||
104 FName == "pthread_rwlock_trywrlock")
105 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
106 true, PthreadSemantics);
107 else if (FName == "lck_mtx_try_lock" ||
108 FName == "lck_rw_try_lock_exclusive" ||
109 FName == "lck_rw_try_lock_shared")
110 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
111 true, XNUSemantics);
112 else if (FName == "pthread_mutex_unlock" ||
113 FName == "pthread_rwlock_unlock" ||
114 FName == "lck_mtx_unlock" ||
115 FName == "lck_rw_done")
116 ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
117 else if (FName == "pthread_mutex_destroy" ||
118 FName == "lck_mtx_destroy")
119 DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
120 else if (FName == "pthread_mutex_init")
121 InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
122 }
123
AcquireLock(CheckerContext & C,const CallExpr * CE,SVal lock,bool isTryLock,enum LockingSemantics semantics) const124 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
125 SVal lock, bool isTryLock,
126 enum LockingSemantics semantics) const {
127
128 const MemRegion *lockR = lock.getAsRegion();
129 if (!lockR)
130 return;
131
132 ProgramStateRef state = C.getState();
133
134 SVal X = state->getSVal(CE, C.getLocationContext());
135 if (X.isUnknownOrUndef())
136 return;
137
138 DefinedSVal retVal = X.castAs<DefinedSVal>();
139
140 if (const LockState *LState = state->get<LockMap>(lockR)) {
141 if (LState->isLocked()) {
142 if (!BT_doublelock)
143 BT_doublelock.reset(new BugType(this, "Double locking",
144 "Lock checker"));
145 ExplodedNode *N = C.generateSink();
146 if (!N)
147 return;
148 BugReport *report = new BugReport(*BT_doublelock,
149 "This lock has already been acquired",
150 N);
151 report->addRange(CE->getArg(0)->getSourceRange());
152 C.emitReport(report);
153 return;
154 } else if (LState->isDestroyed()) {
155 reportUseDestroyedBug(C, CE);
156 return;
157 }
158 }
159
160 ProgramStateRef lockSucc = state;
161 if (isTryLock) {
162 // Bifurcate the state, and allow a mode where the lock acquisition fails.
163 ProgramStateRef lockFail;
164 switch (semantics) {
165 case PthreadSemantics:
166 std::tie(lockFail, lockSucc) = state->assume(retVal);
167 break;
168 case XNUSemantics:
169 std::tie(lockSucc, lockFail) = state->assume(retVal);
170 break;
171 default:
172 llvm_unreachable("Unknown tryLock locking semantics");
173 }
174 assert(lockFail && lockSucc);
175 C.addTransition(lockFail);
176
177 } else if (semantics == PthreadSemantics) {
178 // Assume that the return value was 0.
179 lockSucc = state->assume(retVal, false);
180 assert(lockSucc);
181
182 } else {
183 // XNU locking semantics return void on non-try locks
184 assert((semantics == XNUSemantics) && "Unknown locking semantics");
185 lockSucc = state;
186 }
187
188 // Record that the lock was acquired.
189 lockSucc = lockSucc->add<LockSet>(lockR);
190 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
191 C.addTransition(lockSucc);
192 }
193
ReleaseLock(CheckerContext & C,const CallExpr * CE,SVal lock) const194 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
195 SVal lock) const {
196
197 const MemRegion *lockR = lock.getAsRegion();
198 if (!lockR)
199 return;
200
201 ProgramStateRef state = C.getState();
202
203 if (const LockState *LState = state->get<LockMap>(lockR)) {
204 if (LState->isUnlocked()) {
205 if (!BT_doubleunlock)
206 BT_doubleunlock.reset(new BugType(this, "Double unlocking",
207 "Lock checker"));
208 ExplodedNode *N = C.generateSink();
209 if (!N)
210 return;
211 BugReport *Report = new BugReport(*BT_doubleunlock,
212 "This lock has already been unlocked",
213 N);
214 Report->addRange(CE->getArg(0)->getSourceRange());
215 C.emitReport(Report);
216 return;
217 } else if (LState->isDestroyed()) {
218 reportUseDestroyedBug(C, CE);
219 return;
220 }
221 }
222
223 LockSetTy LS = state->get<LockSet>();
224
225 // FIXME: Better analysis requires IPA for wrappers.
226
227 if (!LS.isEmpty()) {
228 const MemRegion *firstLockR = LS.getHead();
229 if (firstLockR != lockR) {
230 if (!BT_lor)
231 BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
232 ExplodedNode *N = C.generateSink();
233 if (!N)
234 return;
235 BugReport *report = new BugReport(*BT_lor,
236 "This was not the most recently "
237 "acquired lock. Possible lock order "
238 "reversal",
239 N);
240 report->addRange(CE->getArg(0)->getSourceRange());
241 C.emitReport(report);
242 return;
243 }
244 // Record that the lock was released.
245 state = state->set<LockSet>(LS.getTail());
246 }
247
248 state = state->set<LockMap>(lockR, LockState::getUnlocked());
249 C.addTransition(state);
250 }
251
DestroyLock(CheckerContext & C,const CallExpr * CE,SVal Lock) const252 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
253 SVal Lock) const {
254
255 const MemRegion *LockR = Lock.getAsRegion();
256 if (!LockR)
257 return;
258
259 ProgramStateRef State = C.getState();
260
261 const LockState *LState = State->get<LockMap>(LockR);
262 if (!LState || LState->isUnlocked()) {
263 State = State->set<LockMap>(LockR, LockState::getDestroyed());
264 C.addTransition(State);
265 return;
266 }
267
268 StringRef Message;
269
270 if (LState->isLocked()) {
271 Message = "This lock is still locked";
272 } else {
273 Message = "This lock has already been destroyed";
274 }
275
276 if (!BT_destroylock)
277 BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
278 "Lock checker"));
279 ExplodedNode *N = C.generateSink();
280 if (!N)
281 return;
282 BugReport *Report = new BugReport(*BT_destroylock, Message, N);
283 Report->addRange(CE->getArg(0)->getSourceRange());
284 C.emitReport(Report);
285 }
286
InitLock(CheckerContext & C,const CallExpr * CE,SVal Lock) const287 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
288 SVal Lock) const {
289
290 const MemRegion *LockR = Lock.getAsRegion();
291 if (!LockR)
292 return;
293
294 ProgramStateRef State = C.getState();
295
296 const struct LockState *LState = State->get<LockMap>(LockR);
297 if (!LState || LState->isDestroyed()) {
298 State = State->set<LockMap>(LockR, LockState::getUnlocked());
299 C.addTransition(State);
300 return;
301 }
302
303 StringRef Message;
304
305 if (LState->isLocked()) {
306 Message = "This lock is still being held";
307 } else {
308 Message = "This lock has already been initialized";
309 }
310
311 if (!BT_initlock)
312 BT_initlock.reset(new BugType(this, "Init invalid lock",
313 "Lock checker"));
314 ExplodedNode *N = C.generateSink();
315 if (!N)
316 return;
317 BugReport *Report = new BugReport(*BT_initlock, Message, N);
318 Report->addRange(CE->getArg(0)->getSourceRange());
319 C.emitReport(Report);
320 }
321
reportUseDestroyedBug(CheckerContext & C,const CallExpr * CE) const322 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
323 const CallExpr *CE) const {
324 if (!BT_destroylock)
325 BT_destroylock.reset(new BugType(this, "Use destroyed lock",
326 "Lock checker"));
327 ExplodedNode *N = C.generateSink();
328 if (!N)
329 return;
330 BugReport *Report = new BugReport(*BT_destroylock,
331 "This lock has already been destroyed",
332 N);
333 Report->addRange(CE->getArg(0)->getSourceRange());
334 C.emitReport(Report);
335 }
336
registerPthreadLockChecker(CheckerManager & mgr)337 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
338 mgr.registerChecker<PthreadLockChecker>();
339 }
340