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