PthreadLockChecker.cpp 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202
  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. #include "ClangSACheckers.h"
  15. #include "clang/StaticAnalyzer/Core/Checker.h"
  16. #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  17. #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  18. #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  19. #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  20. #include "llvm/ADT/ImmutableList.h"
  21. using namespace clang;
  22. using namespace ento;
  23. namespace {
  24. class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
  25. mutable llvm::OwningPtr<BugType> BT_doublelock;
  26. mutable llvm::OwningPtr<BugType> BT_lor;
  27. enum LockingSemantics {
  28. NotApplicable = 0,
  29. PthreadSemantics,
  30. XNUSemantics
  31. };
  32. public:
  33. void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
  34. void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
  35. bool isTryLock, enum LockingSemantics semantics) const;
  36. void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
  37. };
  38. } // end anonymous namespace
  39. // GDM Entry for tracking lock state.
  40. namespace { class LockSet {}; }
  41. namespace clang {
  42. namespace ento {
  43. template <> struct ProgramStateTrait<LockSet> :
  44. public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
  45. static void *GDMIndex() { static int x = 0; return &x; }
  46. };
  47. } // end GR namespace
  48. } // end clang namespace
  49. void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
  50. CheckerContext &C) const {
  51. const ProgramState *state = C.getState();
  52. const Expr *Callee = CE->getCallee();
  53. const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
  54. if (!FD)
  55. return;
  56. // Get the name of the callee.
  57. IdentifierInfo *II = FD->getIdentifier();
  58. if (!II) // if no identifier, not a simple C function
  59. return;
  60. StringRef FName = II->getName();
  61. if (CE->getNumArgs() != 1)
  62. return;
  63. if (FName == "pthread_mutex_lock" ||
  64. FName == "pthread_rwlock_rdlock" ||
  65. FName == "pthread_rwlock_wrlock")
  66. AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics);
  67. else if (FName == "lck_mtx_lock" ||
  68. FName == "lck_rw_lock_exclusive" ||
  69. FName == "lck_rw_lock_shared")
  70. AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics);
  71. else if (FName == "pthread_mutex_trylock" ||
  72. FName == "pthread_rwlock_tryrdlock" ||
  73. FName == "pthread_rwlock_tryrwlock")
  74. AcquireLock(C, CE, state->getSVal(CE->getArg(0)), 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)), true, XNUSemantics);
  79. else if (FName == "pthread_mutex_unlock" ||
  80. FName == "pthread_rwlock_unlock" ||
  81. FName == "lck_mtx_unlock" ||
  82. FName == "lck_rw_done")
  83. ReleaseLock(C, CE, state->getSVal(CE->getArg(0)));
  84. }
  85. void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
  86. SVal lock, bool isTryLock,
  87. enum LockingSemantics semantics) const {
  88. const MemRegion *lockR = lock.getAsRegion();
  89. if (!lockR)
  90. return;
  91. const ProgramState *state = C.getState();
  92. SVal X = state->getSVal(CE);
  93. if (X.isUnknownOrUndef())
  94. return;
  95. DefinedSVal retVal = cast<DefinedSVal>(X);
  96. if (state->contains<LockSet>(lockR)) {
  97. if (!BT_doublelock)
  98. BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
  99. ExplodedNode *N = C.generateSink();
  100. if (!N)
  101. return;
  102. BugReport *report = new BugReport(*BT_doublelock,
  103. "This lock has already "
  104. "been acquired", N);
  105. report->addRange(CE->getArg(0)->getSourceRange());
  106. C.EmitReport(report);
  107. return;
  108. }
  109. const ProgramState *lockSucc = state;
  110. if (isTryLock) {
  111. // Bifurcate the state, and allow a mode where the lock acquisition fails.
  112. const ProgramState *lockFail;
  113. switch (semantics) {
  114. case PthreadSemantics:
  115. llvm::tie(lockFail, lockSucc) = state->assume(retVal);
  116. break;
  117. case XNUSemantics:
  118. llvm::tie(lockSucc, lockFail) = state->assume(retVal);
  119. break;
  120. default:
  121. llvm_unreachable("Unknown tryLock locking semantics");
  122. break;
  123. }
  124. assert(lockFail && lockSucc);
  125. C.addTransition(lockFail);
  126. } else if (semantics == PthreadSemantics) {
  127. // Assume that the return value was 0.
  128. lockSucc = state->assume(retVal, false);
  129. assert(lockSucc);
  130. } else {
  131. // XNU locking semantics return void on non-try locks
  132. assert((semantics == XNUSemantics) && "Unknown locking semantics");
  133. lockSucc = state;
  134. }
  135. // Record that the lock was acquired.
  136. lockSucc = lockSucc->add<LockSet>(lockR);
  137. C.addTransition(lockSucc);
  138. }
  139. void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
  140. SVal lock) const {
  141. const MemRegion *lockR = lock.getAsRegion();
  142. if (!lockR)
  143. return;
  144. const ProgramState *state = C.getState();
  145. llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();
  146. // FIXME: Better analysis requires IPA for wrappers.
  147. // FIXME: check for double unlocks
  148. if (LS.isEmpty())
  149. return;
  150. const MemRegion *firstLockR = LS.getHead();
  151. if (firstLockR != lockR) {
  152. if (!BT_lor)
  153. BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
  154. ExplodedNode *N = C.generateSink();
  155. if (!N)
  156. return;
  157. BugReport *report = new BugReport(*BT_lor,
  158. "This was not the most "
  159. "recently acquired lock. "
  160. "Possible lock order "
  161. "reversal", N);
  162. report->addRange(CE->getArg(0)->getSourceRange());
  163. C.EmitReport(report);
  164. return;
  165. }
  166. // Record that the lock was released.
  167. state = state->set<LockSet>(LS.getTail());
  168. C.addTransition(state);
  169. }
  170. void ento::registerPthreadLockChecker(CheckerManager &mgr) {
  171. mgr.registerChecker<PthreadLockChecker>();
  172. }