//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This defines PthreadLockChecker, a simple lock -> unlock checker.
// Also handles XNU locks, which behave similarly enough to share code.
//
//===----------------------------------------------------------------------===//

#include "ClangSACheckers.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
#include "llvm/ADT/ImmutableList.h"

using namespace clang;
using namespace ento;

namespace {
class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
  mutable llvm::OwningPtr<BugType> BT_doublelock;
  mutable llvm::OwningPtr<BugType> BT_lor;
  enum LockingSemantics {
    NotApplicable = 0,
    PthreadSemantics,
    XNUSemantics
  };
public:
  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
    
  void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
                   bool isTryLock, enum LockingSemantics semantics) const;
    
  void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
};
} // end anonymous namespace

// GDM Entry for tracking lock state.
namespace { class LockSet {}; }
namespace clang {
namespace ento {
template <> struct ProgramStateTrait<LockSet> :
  public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
    static void *GDMIndex() { static int x = 0; return &x; }
};
} // end of ento (ProgramState) namespace
} // end clang namespace


void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
                                       CheckerContext &C) const {
  const ProgramState *state = C.getState();
  const Expr *Callee = CE->getCallee();
  const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();

  if (!FD)
    return;

  // Get the name of the callee.
  IdentifierInfo *II = FD->getIdentifier();
  if (!II)   // if no identifier, not a simple C function
    return;
  StringRef FName = II->getName();

  if (CE->getNumArgs() != 1)
    return;

  if (FName == "pthread_mutex_lock" ||
      FName == "pthread_rwlock_rdlock" ||
      FName == "pthread_rwlock_wrlock")
    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics);
  else if (FName == "lck_mtx_lock" ||
           FName == "lck_rw_lock_exclusive" ||
           FName == "lck_rw_lock_shared") 
    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics);
  else if (FName == "pthread_mutex_trylock" ||
           FName == "pthread_rwlock_tryrdlock" ||
           FName == "pthread_rwlock_tryrwlock")
    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, PthreadSemantics);
  else if (FName == "lck_mtx_try_lock" ||
           FName == "lck_rw_try_lock_exclusive" ||
           FName == "lck_rw_try_lock_shared")
    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, XNUSemantics);
  else if (FName == "pthread_mutex_unlock" ||
           FName == "pthread_rwlock_unlock" ||
           FName == "lck_mtx_unlock" ||
           FName == "lck_rw_done")
    ReleaseLock(C, CE, state->getSVal(CE->getArg(0)));
}

void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
                                     SVal lock, bool isTryLock,
                                     enum LockingSemantics semantics) const {
  
  const MemRegion *lockR = lock.getAsRegion();
  if (!lockR)
    return;
  
  const ProgramState *state = C.getState();
  
  SVal X = state->getSVal(CE);
  if (X.isUnknownOrUndef())
    return;
  
  DefinedSVal retVal = cast<DefinedSVal>(X);

  if (state->contains<LockSet>(lockR)) {
    if (!BT_doublelock)
      BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
    ExplodedNode *N = C.generateSink();
    if (!N)
      return;
    BugReport *report = new BugReport(*BT_doublelock,
                                                      "This lock has already "
                                                      "been acquired", N);
    report->addRange(CE->getArg(0)->getSourceRange());
    C.EmitReport(report);
    return;
  }

  const ProgramState *lockSucc = state;
  if (isTryLock) {
    // Bifurcate the state, and allow a mode where the lock acquisition fails.
    const ProgramState *lockFail;
    switch (semantics) {
    case PthreadSemantics:
      llvm::tie(lockFail, lockSucc) = state->assume(retVal);    
      break;
    case XNUSemantics:
      llvm::tie(lockSucc, lockFail) = state->assume(retVal);    
      break;
    default:
      llvm_unreachable("Unknown tryLock locking semantics");
      break;
    }
    assert(lockFail && lockSucc);
    C.addTransition(lockFail);

  } else if (semantics == PthreadSemantics) {
    // Assume that the return value was 0.
    lockSucc = state->assume(retVal, false);
    assert(lockSucc);

  } else {
    // XNU locking semantics return void on non-try locks
    assert((semantics == XNUSemantics) && "Unknown locking semantics");
    lockSucc = state;
  }
  
  // Record that the lock was acquired.  
  lockSucc = lockSucc->add<LockSet>(lockR);
  C.addTransition(lockSucc);
}

void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
                                     SVal lock) const {

  const MemRegion *lockR = lock.getAsRegion();
  if (!lockR)
    return;
  
  const ProgramState *state = C.getState();
  llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();

  // FIXME: Better analysis requires IPA for wrappers.
  // FIXME: check for double unlocks
  if (LS.isEmpty())
    return;
  
  const MemRegion *firstLockR = LS.getHead();
  if (firstLockR != lockR) {
    if (!BT_lor)
      BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
    ExplodedNode *N = C.generateSink();
    if (!N)
      return;
    BugReport *report = new BugReport(*BT_lor,
                                                      "This was not the most "
                                                      "recently acquired lock. "
                                                      "Possible lock order "
                                                      "reversal", N);
    report->addRange(CE->getArg(0)->getSourceRange());
    C.EmitReport(report);
    return;
  }

  // Record that the lock was released. 
  state = state->set<LockSet>(LS.getTail());
  C.addTransition(state);
}


void ento::registerPthreadLockChecker(CheckerManager &mgr) {
  mgr.registerChecker<PthreadLockChecker>();
}