// Copyright 2011 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Author: jmaessen@google.com (Jan Maessen)

#include "pagespeed/kernel/thread/scheduler_based_abstract_lock.h"

#include "base/logging.h"
#include "pagespeed/kernel/base/abstract_mutex.h"
#include "pagespeed/kernel/base/atomic_bool.h"
#include "pagespeed/kernel/base/basictypes.h"
#include "pagespeed/kernel/base/condvar.h"
#include "pagespeed/kernel/base/gtest.h"
#include "pagespeed/kernel/base/mock_timer.h"
#include "pagespeed/kernel/base/scoped_ptr.h"
#include "pagespeed/kernel/base/string.h"
#include "pagespeed/kernel/base/string_util.h"
#include "pagespeed/kernel/base/thread.h"
#include "pagespeed/kernel/base/thread_annotations.h"
#include "pagespeed/kernel/base/thread_system.h"
#include "pagespeed/kernel/base/timer.h"
#include "pagespeed/kernel/thread/mock_scheduler.h"
#include "pagespeed/kernel/thread/scheduler.h"
#include "pagespeed/kernel/util/platform.h"

namespace net_instaweb {

namespace {

static const int kShortMs = 10;
static const int kLongMs = 100;

class SchedulerBasedAbstractLockTest : public testing::Test {
 protected:
  SchedulerBasedAbstractLockTest()
      : thread_system_(Platform::CreateThreadSystem()),
        timer_(thread_system_->NewMutex(), 0),
        scheduler_(thread_system_.get(), &timer_) {
  }

  scoped_ptr<ThreadSystem> thread_system_;
  MockTimer timer_;
  MockScheduler scheduler_;

 private:
  DISALLOW_COPY_AND_ASSIGN(SchedulerBasedAbstractLockTest);
};

// A mock lock base class
class MockLockBase : public SchedulerBasedAbstractLock {
 public:
  explicit MockLockBase(Scheduler* scheduler) : scheduler_(scheduler) { }
  virtual ~MockLockBase() { }
  virtual Scheduler* scheduler() const { return scheduler_; }
  // None of the mock locks actually implement locking, so
  // unlocking is a no-op.
  virtual void Unlock() { held_ = false; }
  virtual bool Held() { return held_; }

 protected:
  Scheduler* scheduler_;
  bool held_;

 private:
  DISALLOW_COPY_AND_ASSIGN(MockLockBase);
};

// A mock lock that always claims locking happened
class AlwaysLock : public MockLockBase {
 public:
  explicit AlwaysLock(Scheduler* scheduler) : MockLockBase(scheduler) { }
  virtual ~AlwaysLock() { }
  virtual bool TryLock() {
    held_ = true;
    return true;
  }
  virtual bool TryLockStealOld(int64 timeout_ms) {
    held_ = true;
    return true;
  }
  virtual GoogleString name() const { return GoogleString("AlwaysLock"); }
 private:
  DISALLOW_COPY_AND_ASSIGN(AlwaysLock);
};

// A mock lock that always claims lock attempts failed
class NeverLock : public MockLockBase {
 public:
  explicit NeverLock(Scheduler* scheduler) : MockLockBase(scheduler) { }
  virtual ~NeverLock() { }
  virtual bool TryLock() {
    return false;
  }
  virtual bool TryLockStealOld(int64 timeout_ms) {
    return false;
  }
  virtual GoogleString name() const { return GoogleString("NeverLock"); }
 private:
  DISALLOW_COPY_AND_ASSIGN(NeverLock);
};

// A mock lock that can only be locked by stealing after a timeout.
class StealOnlyLock : public NeverLock {
 public:
  explicit StealOnlyLock(Scheduler* scheduler)
      : NeverLock(scheduler),
        last_hold_time_ms_(scheduler_->timer()->NowMs()) {
  }
  virtual bool TryLockStealOld(int64 timeout_ms) {
    int64 timeout_time_ms = last_hold_time_ms_ + timeout_ms;
    int64 now_ms = scheduler()->timer()->NowMs();
    if (timeout_time_ms <= now_ms) {
      last_hold_time_ms_ = now_ms;
      held_ = true;
      return true;
    } else {
      return false;
    }
  }
  virtual GoogleString name() const { return GoogleString("StealOnlyLock"); }
 private:
  int64 last_hold_time_ms_;

  DISALLOW_COPY_AND_ASSIGN(StealOnlyLock);
};

// Simple tests that involve either failed try or successfully obtaining lock.
// Note that we always capture start times before lock construction, to account
// for possible passage of mock time due to time queries during lock
// construction.
TEST_F(SchedulerBasedAbstractLockTest, AlwaysLock) {
  int64 start = timer_.NowMs();
  AlwaysLock always_lock(&scheduler_);
  EXPECT_TRUE(always_lock.LockTimedWait(kLongMs));

  SchedulerBlockingFunction block1(&scheduler_);
  always_lock.LockTimedWait(kLongMs, &block1);
  EXPECT_TRUE(block1.Block());

  EXPECT_TRUE(always_lock.LockTimedWaitStealOld(kLongMs, kLongMs));

  SchedulerBlockingFunction block2(&scheduler_);
  always_lock.LockTimedWaitStealOld(kLongMs, kLongMs, &block2);
  EXPECT_TRUE(block2.Block());

  // Nothing should ever have slept.
  int64 end = timer_.NowMs();
  EXPECT_EQ(0, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, TimeoutHappens) {
  int64 start = timer_.NowMs();
  NeverLock never_lock(&scheduler_);
  EXPECT_FALSE(never_lock.LockTimedWait(kShortMs));
  int64 end = timer_.NowMs();
  // At least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutHappens) {
  int64 start = timer_.NowMs();
  NeverLock never_lock(&scheduler_);
  SchedulerBlockingFunction block(&scheduler_);
  never_lock.LockTimedWait(kShortMs, &block);
  EXPECT_FALSE(block.Block());
  int64 end = timer_.NowMs();
  // At least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, TimeoutHappensStealOld) {
  int64 start = timer_.NowMs();
  NeverLock never_lock(&scheduler_);
  EXPECT_FALSE(never_lock.LockTimedWaitStealOld(kShortMs, kLongMs));
  int64 end = timer_.NowMs();
  // Again at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutHappensStealOld) {
  int64 start = timer_.NowMs();
  NeverLock never_lock(&scheduler_);
  SchedulerBlockingFunction block(&scheduler_);
  never_lock.LockTimedWaitStealOld(kShortMs, kLongMs, &block);
  EXPECT_FALSE(block.Block());
  int64 end = timer_.NowMs();
  // Again at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, TimeoutBeforeSteal) {
  int64 start = timer_.NowMs();
  StealOnlyLock steal_only_lock(&scheduler_);
  EXPECT_FALSE(steal_only_lock.LockTimedWaitStealOld(kShortMs, kLongMs));
  int64 end = timer_.NowMs();
  // Again at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutBeforeSteal) {
  int64 start = timer_.NowMs();
  StealOnlyLock steal_only_lock(&scheduler_);
  SchedulerBlockingFunction block(&scheduler_);
  steal_only_lock.LockTimedWaitStealOld(kShortMs, kLongMs, &block);
  EXPECT_FALSE(block.Block());
  int64 end = timer_.NowMs();
  // Again at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // But not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, StealBeforeTimeout) {
  int64 start = timer_.NowMs();
  StealOnlyLock steal_only_lock(&scheduler_);
  EXPECT_TRUE(steal_only_lock.LockTimedWaitStealOld(kLongMs, kShortMs));
  int64 end = timer_.NowMs();
  // Again, at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // And again, not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

TEST_F(SchedulerBasedAbstractLockTest, CallbackStealBeforeTimeout) {
  int64 start = timer_.NowMs();
  StealOnlyLock steal_only_lock(&scheduler_);
  SchedulerBlockingFunction block(&scheduler_);
  steal_only_lock.LockTimedWaitStealOld(kLongMs, kShortMs, &block);
  EXPECT_TRUE(block.Block());
  int64 end = timer_.NowMs();
  // Again, at least kShortMs must have elapsed.
  EXPECT_LE(kShortMs, end - start);
  // And again, not more than twice as long.
  EXPECT_GT(2 * kShortMs, end - start);
}

// A wrapper that locks before operating on the underlying timer.  This really
// only makes sense for a MockTimer, as most timers inherit any necessary
// synchronization from the underlying library and OS (where it's done far more
// efficiently).
class LockedTimer : public Timer {
 public:
  LockedTimer(Timer* timer, ThreadSystem::CondvarCapableMutex* mutex)
      : timer_(timer),
        mutex_(mutex),
        sleep_wakeup_condvar_(mutex->NewCondvar()) { }
  virtual ~LockedTimer() { }
  virtual void SleepUs(int64 us) {
    {
      ScopedMutex lock(mutex_);
      timer_->SleepUs(us);
      sleep_wakeup_condvar_->Signal();
    }
  }
  virtual int64 NowUs() const {
    ScopedMutex lock(mutex_);
    return timer_->NowUs();
  }
  // Wait for other threads to advance mock time to end_ms.  Does not itself
  // advance time; we're monitoring the activities of those other threads, which
  // aren't going to terminate (and thus can't be monitored in line).
  virtual void WaitUntilMs(int64 end_ms) {
    ScopedMutex lock(mutex_);
    while (timer_->NowMs() < end_ms) {
      sleep_wakeup_condvar_->Wait();
    }
  }

 private:
  Timer* timer_;
  ThreadSystem::CondvarCapableMutex* mutex_;
  scoped_ptr<ThreadSystem::Condvar> sleep_wakeup_condvar_;
};

class ThreadedSchedulerBasedLockTest : public SchedulerBasedAbstractLockTest {
 public:
  // Various helper threads.  We could have done this with subclasses, but it's
  // clunky for present needs (which are very simple).
  // Grumble: C++ appears to require these methods to be public
  // if we take their address in a subclass method.

  // The default is DoNothingHelper, which just sleeps a long time and
  // terminates.  The other helper threads do not terminate (and fail if they
  // try).
  void DoNothingHelper() {
    SleepMs(kLongMs);
  }
  // Attempt to lock and spin forever
  void LockHelper() {
    while (!never_lock_.LockTimedWait(10 * kLongMs) && !done_.value()) { }
    CHECK(done_.value()) << "Should not lock!";
  }
  // Attempt to Lock with a steal and spin forever.  This used to fail.
  void LockStealHelper() {
    while (!never_lock_.LockTimedWaitStealOld(10 * kLongMs, kShortMs) &&
           !done_.value()) { }
    CHECK(done_.value()) << "Shouldn't lock!";
  }

 protected:
  typedef void (ThreadedSchedulerBasedLockTest::*HelperThreadMethod)();
  ThreadedSchedulerBasedLockTest()
      : never_lock_(&scheduler_),
        startup_condvar_(scheduler_.mutex()->NewCondvar()),
        helper_thread_method_(
            &ThreadedSchedulerBasedLockTest::DoNothingHelper) { }
  void SleepUntilMs(int64 end_ms) EXCLUSIVE_LOCKS_REQUIRED(scheduler_.mutex()) {
    int64 now_ms = timer_.NowMs();
    while (now_ms < end_ms) {
      scheduler_.ProcessAlarmsOrWaitUs((end_ms - now_ms) * Timer::kMsUs);
      now_ms = timer_.NowMs();
    }
  }
  void SleepMs(int64 sleep_ms) LOCKS_EXCLUDED(scheduler_.mutex()) {
    ScopedMutex lock(scheduler_.mutex());
    int64 now_ms = timer_.NowMs();
    SleepUntilMs(now_ms + sleep_ms);
  }
  // Start helper, then sleep for sleep_ms and return.
  void SleepForHelper(int64 sleep_ms) LOCKS_EXCLUDED(scheduler_.mutex()) {
    int64 now_ms;
    {
      ScopedMutex lock(scheduler_.mutex());
      now_ms = timer_.NowMs();
    }
    StartHelper();
    {
      ScopedMutex lock(scheduler_.mutex());
      SleepUntilMs(now_ms + sleep_ms);
    }
  }
  void StartHelper() LOCKS_EXCLUDED(scheduler_.mutex()) {
    helper_thread_.reset(
        new ThreadedSchedulerBasedLockTest::HelperThread(this));
    helper_thread_->Start();
    {
      ScopedMutex lock(scheduler_.mutex());
      while (!ready_to_start_.value()) {
        startup_condvar_->Wait();
      }
      ready_to_start_.set_value(false);
      startup_condvar_->Signal();
    }
  }
  void FinishHelper() {
    helper_thread_->Join();
  }
  // If the helper thread runs forever, we need to cancel it so that
  // we can safely destruct the test objects before exit.
  void CancelHelper() {
    done_.set_value(true);
    FinishHelper();
  }
  void set_helper(HelperThreadMethod helper) {
    helper_thread_method_ = helper;
  }

  NeverLock never_lock_;

 private:
  class HelperThread : public ThreadSystem::Thread {
   public:
    explicit HelperThread(ThreadedSchedulerBasedLockTest* test)
        : ThreadSystem::Thread(test->thread_system_.get(),
                               "threaded_scheduler_based_lock_test_helper",
                               ThreadSystem::kJoinable),
          test_(test) { }
    virtual void Run() LOCKS_EXCLUDED(test_->scheduler_.mutex()) {
      {
        ScopedMutex lock(test_->scheduler_.mutex());
        test_->ready_to_start_.set_value(true);
        test_->startup_condvar_->Signal();
        while (test_->ready_to_start_.value()) {
          test_->startup_condvar_->Wait();
        }
      }
      (test_->*(test_->helper_thread_method_))();
    }
   private:
    ThreadedSchedulerBasedLockTest* test_;
    DISALLOW_COPY_AND_ASSIGN(HelperThread);
  };

  AtomicBool ready_to_start_;
  AtomicBool done_;
  scoped_ptr<ThreadSystem::Condvar> startup_condvar_;
  scoped_ptr<HelperThread> helper_thread_;
  HelperThreadMethod helper_thread_method_;

  DISALLOW_COPY_AND_ASSIGN(ThreadedSchedulerBasedLockTest);
};

// Meta-Test that all is well.
TEST_F(ThreadedSchedulerBasedLockTest, TestStartupHandshake) {
  SleepForHelper(kShortMs);
  FinishHelper();
}

TEST_F(ThreadedSchedulerBasedLockTest, TestLockBlock) {
  set_helper(&ThreadedSchedulerBasedLockTest::LockHelper);
  SleepForHelper(kLongMs);
  CancelHelper();
}

TEST_F(ThreadedSchedulerBasedLockTest, TestLockStealBlock) {
  set_helper(&ThreadedSchedulerBasedLockTest::LockStealHelper);
  SleepForHelper(kLongMs);
  CancelHelper();
}

}  // namespace

}  // namespace net_instaweb