• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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__anone5bbdb130111::LockState32   LockState(Kind K) : K(K) {}
33 
34 public:
getLocked__anone5bbdb130111::LockState35   static LockState getLocked() { return LockState(Locked); }
getUnlocked__anone5bbdb130111::LockState36   static LockState getUnlocked() { return LockState(Unlocked); }
getDestroyed__anone5bbdb130111::LockState37   static LockState getDestroyed() { return LockState(Destroyed); }
38 
operator ==__anone5bbdb130111::LockState39   bool operator==(const LockState &X) const {
40     return K == X.K;
41   }
42 
isLocked__anone5bbdb130111::LockState43   bool isLocked() const { return K == Locked; }
isUnlocked__anone5bbdb130111::LockState44   bool isUnlocked() const { return K == Unlocked; }
isDestroyed__anone5bbdb130111::LockState45   bool isDestroyed() const { return K == Destroyed; }
46 
Profile__anone5bbdb130111::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.generateErrorNode();
146       if (!N)
147         return;
148       auto report = llvm::make_unique<BugReport>(
149           *BT_doublelock, "This lock has already been acquired", N);
150       report->addRange(CE->getArg(0)->getSourceRange());
151       C.emitReport(std::move(report));
152       return;
153     } else if (LState->isDestroyed()) {
154       reportUseDestroyedBug(C, CE);
155       return;
156     }
157   }
158 
159   ProgramStateRef lockSucc = state;
160   if (isTryLock) {
161     // Bifurcate the state, and allow a mode where the lock acquisition fails.
162     ProgramStateRef lockFail;
163     switch (semantics) {
164     case PthreadSemantics:
165       std::tie(lockFail, lockSucc) = state->assume(retVal);
166       break;
167     case XNUSemantics:
168       std::tie(lockSucc, lockFail) = state->assume(retVal);
169       break;
170     default:
171       llvm_unreachable("Unknown tryLock locking semantics");
172     }
173     assert(lockFail && lockSucc);
174     C.addTransition(lockFail);
175 
176   } else if (semantics == PthreadSemantics) {
177     // Assume that the return value was 0.
178     lockSucc = state->assume(retVal, false);
179     assert(lockSucc);
180 
181   } else {
182     // XNU locking semantics return void on non-try locks
183     assert((semantics == XNUSemantics) && "Unknown locking semantics");
184     lockSucc = state;
185   }
186 
187   // Record that the lock was acquired.
188   lockSucc = lockSucc->add<LockSet>(lockR);
189   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
190   C.addTransition(lockSucc);
191 }
192 
ReleaseLock(CheckerContext & C,const CallExpr * CE,SVal lock) const193 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
194                                      SVal lock) const {
195 
196   const MemRegion *lockR = lock.getAsRegion();
197   if (!lockR)
198     return;
199 
200   ProgramStateRef state = C.getState();
201 
202   if (const LockState *LState = state->get<LockMap>(lockR)) {
203     if (LState->isUnlocked()) {
204       if (!BT_doubleunlock)
205         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
206                                           "Lock checker"));
207       ExplodedNode *N = C.generateErrorNode();
208       if (!N)
209         return;
210       auto Report = llvm::make_unique<BugReport>(
211           *BT_doubleunlock, "This lock has already been unlocked", N);
212       Report->addRange(CE->getArg(0)->getSourceRange());
213       C.emitReport(std::move(Report));
214       return;
215     } else if (LState->isDestroyed()) {
216       reportUseDestroyedBug(C, CE);
217       return;
218     }
219   }
220 
221   LockSetTy LS = state->get<LockSet>();
222 
223   // FIXME: Better analysis requires IPA for wrappers.
224 
225   if (!LS.isEmpty()) {
226     const MemRegion *firstLockR = LS.getHead();
227     if (firstLockR != lockR) {
228       if (!BT_lor)
229         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
230       ExplodedNode *N = C.generateErrorNode();
231       if (!N)
232         return;
233       auto report = llvm::make_unique<BugReport>(
234           *BT_lor, "This was not the most recently acquired lock. Possible "
235                    "lock order reversal", N);
236       report->addRange(CE->getArg(0)->getSourceRange());
237       C.emitReport(std::move(report));
238       return;
239     }
240     // Record that the lock was released.
241     state = state->set<LockSet>(LS.getTail());
242   }
243 
244   state = state->set<LockMap>(lockR, LockState::getUnlocked());
245   C.addTransition(state);
246 }
247 
DestroyLock(CheckerContext & C,const CallExpr * CE,SVal Lock) const248 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
249                                      SVal Lock) const {
250 
251   const MemRegion *LockR = Lock.getAsRegion();
252   if (!LockR)
253     return;
254 
255   ProgramStateRef State = C.getState();
256 
257   const LockState *LState = State->get<LockMap>(LockR);
258   if (!LState || LState->isUnlocked()) {
259     State = State->set<LockMap>(LockR, LockState::getDestroyed());
260     C.addTransition(State);
261     return;
262   }
263 
264   StringRef Message;
265 
266   if (LState->isLocked()) {
267     Message = "This lock is still locked";
268   } else {
269     Message = "This lock has already been destroyed";
270   }
271 
272   if (!BT_destroylock)
273     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
274                                      "Lock checker"));
275   ExplodedNode *N = C.generateErrorNode();
276   if (!N)
277     return;
278   auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
279   Report->addRange(CE->getArg(0)->getSourceRange());
280   C.emitReport(std::move(Report));
281 }
282 
InitLock(CheckerContext & C,const CallExpr * CE,SVal Lock) const283 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
284                                   SVal Lock) const {
285 
286   const MemRegion *LockR = Lock.getAsRegion();
287   if (!LockR)
288     return;
289 
290   ProgramStateRef State = C.getState();
291 
292   const struct LockState *LState = State->get<LockMap>(LockR);
293   if (!LState || LState->isDestroyed()) {
294     State = State->set<LockMap>(LockR, LockState::getUnlocked());
295     C.addTransition(State);
296     return;
297   }
298 
299   StringRef Message;
300 
301   if (LState->isLocked()) {
302     Message = "This lock is still being held";
303   } else {
304     Message = "This lock has already been initialized";
305   }
306 
307   if (!BT_initlock)
308     BT_initlock.reset(new BugType(this, "Init invalid lock",
309                                   "Lock checker"));
310   ExplodedNode *N = C.generateErrorNode();
311   if (!N)
312     return;
313   auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
314   Report->addRange(CE->getArg(0)->getSourceRange());
315   C.emitReport(std::move(Report));
316 }
317 
reportUseDestroyedBug(CheckerContext & C,const CallExpr * CE) const318 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
319                                                const CallExpr *CE) const {
320   if (!BT_destroylock)
321     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
322                                      "Lock checker"));
323   ExplodedNode *N = C.generateErrorNode();
324   if (!N)
325     return;
326   auto Report = llvm::make_unique<BugReport>(
327       *BT_destroylock, "This lock has already been destroyed", N);
328   Report->addRange(CE->getArg(0)->getSourceRange());
329   C.emitReport(std::move(Report));
330 }
331 
registerPthreadLockChecker(CheckerManager & mgr)332 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
333   mgr.registerChecker<PthreadLockChecker>();
334 }
335