// Copyright 2016 The Fuchsia Authors
// Copyright (c) 2008-2014 Travis Geiselbrecht
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT

/**
 * @file
 * @brief  Kernel timer subsystem
 * @defgroup timer Timers
 *
 * The timer subsystem allows functions to be scheduled for later
 * execution.  Each timer object is used to cause one function to
 * be executed at a later time.
 *
 * Timer callback functions are called in interrupt context.
 *
 * @{
 */
#include "kernel/timer.h"

#include <assert.h>
#include <debug.h>
#include <inttypes.h>
#include <lib/affine/ratio.h>
#include <lib/arch/intrin.h>
#include <lib/counters.h>
#include <lib/zircon-internal/macros.h>
#include <platform.h>
#include <stdlib.h>
#include <trace.h>
#include <zircon/compiler.h>
#include <zircon/errors.h>
#include <zircon/listnode.h>
#include <zircon/time.h>
#include <zircon/types.h>

#include <kernel/align.h>
#include <kernel/lockdep.h>
#include <kernel/mp.h>
#include <kernel/percpu.h>
#include <kernel/scheduler.h>
#include <kernel/spinlock.h>
#include <kernel/stats.h>
#include <kernel/thread.h>
#include <platform/timer.h>

#define LOCAL_TRACE 0

// Total number of timers set. Always increasing.
KCOUNTER(timer_created_counter, "timer.created")

// Number of timers merged into an existing timer because of slack.
KCOUNTER(timer_coalesced_counter, "timer.coalesced")

// Number of timers that have fired (i.e. callback was invoked).
KCOUNTER(timer_fired_counter, "timer.fired")

// Number of timers that were successfully canceled. Attempts to cancel a timer that is currently
// firing are not counted.
KCOUNTER(timer_canceled_counter, "timer.canceled")

namespace {

using fxt::operator""_intern;

// Note that we need to manually name the timer_lock because it is one of and
// extremely small number of "wrapped" locks in the system, and cannot easily
// use lockdep in order to generate its name.
//
// The vast majority of locks in the system are directly instrumented using
// lockdep. This causes the instance of the actual lock to become a member of a
// generated lock dep class, which is used to access the underlying lock.  In
// these cases, lockdep itself controls the construction sequencing of the lock,
// allowing it to configure the internal lock's metadata immediately after
// construction has completed.
//
// Wrapped locks, OTOH, are a bit different.  The lock instance is declared
// outside of the lockdep generated class, which holds a reference to the lock
// instead of encapsulating the lock itself.  This leads to a global ctor race:
// Who is constructed first, the lock itself, or the lock wrapper who holds a
// pointer/reference to the lock?
//
// In situations like this, it is not safe for lock wrapper to be interacting
// with the lock whose reference it holds, since that lock may not have been
// constructed yet.
//
// So instead, we simply manually name the lock, and the lockdep wrapper never
// makes any attempt to name the lock because of the ordering issues.
//
MonitoredSpinLock timer_lock __CPU_ALIGN_EXCLUSIVE{"timer_lock"_intern};
DECLARE_SINGLETON_LOCK_WRAPPER(TimerLock, timer_lock);

affine::Ratio gTicksToTime;
uint64_t gTicksPerSecond;

}  // anonymous namespace

void platform_set_ticks_to_time_ratio(const affine::Ratio& ticks_to_time) {
  // ASSERT that we are not calling this function twice.  Once set, this ratio
  // may not change.
  DEBUG_ASSERT(gTicksPerSecond == 0);
  DEBUG_ASSERT(ticks_to_time.numerator() != 0);
  DEBUG_ASSERT(ticks_to_time.denominator() != 0);
  gTicksToTime = ticks_to_time;
  gTicksPerSecond = gTicksToTime.Inverse().Scale(ZX_SEC(1));
}

const affine::Ratio& platform_get_ticks_to_time_ratio(void) { return gTicksToTime; }

zx_time_t current_time(void) { return gTicksToTime.Scale(current_ticks()); }

zx_ticks_t ticks_per_second(void) { return gTicksPerSecond; }

void TimerQueue::UpdatePlatformTimer(zx_time_t new_deadline) {
  DEBUG_ASSERT(arch_ints_disabled());
  if (new_deadline < next_timer_deadline_) {
    LTRACEF("rescheduling timer for %" PRIi64 " nsecs\n", new_deadline);
    platform_set_oneshot_timer(new_deadline);
    next_timer_deadline_ = new_deadline;
  }
}

void TimerQueue::Insert(Timer* timer, zx_time_t earliest_deadline, zx_time_t latest_deadline) {
  DEBUG_ASSERT(arch_ints_disabled());
  cpu_num_t cpu = arch_curr_cpu_num();
  LTRACEF("timer %p, cpu %u, scheduled %" PRIi64 "\n", timer, cpu, timer->scheduled_time_);

  // For inserting the timer we consider several cases. In general we
  // want to coalesce with the current timer unless we can prove that
  // either that:
  //  1- there is no slack overlap with current timer OR
  //  2- the next timer is a better fit.
  //
  // In diagrams that follow
  // - Let |e| be the current (existing) timer deadline
  // - Let |t| be the deadline of the timer we are inserting
  // - Let |n| be the next timer deadline if any
  // - Let |x| be the end of the list (not a timer)
  // - Let |(| and |)| the earliest_deadline and latest_deadline.

  for (Timer& entry : timer_list_) {
    if (entry.scheduled_time_ > latest_deadline) {
      // New timer latest is earlier than the current timer.
      // Just add upfront as is, without slack.
      //
      //   ---------t---)--e-------------------------------> time
      timer->slack_ = 0ll;
      timer_list_.insert(entry, timer);
      return;
    }

    if (entry.scheduled_time_ >= timer->scheduled_time_) {
      //  New timer slack overlaps and is to the left (or equal). We
      //  coalesce with current by scheduling late.
      //
      //  --------(----t---e-)----------------------------> time
      timer->slack_ = zx_time_sub_time(entry.scheduled_time_, timer->scheduled_time_);
      timer->scheduled_time_ = entry.scheduled_time_;
      kcounter_add(timer_coalesced_counter, 1);
      timer_list_.insert_after(timer_list_.make_iterator(entry), timer);
      return;
    }

    if (entry.scheduled_time_ < earliest_deadline) {
      // new timer earliest is later than the current timer. This case
      // is handled in a future iteration.
      //
      //   ----------------e--(---t-----------------------> time
      continue;
    }

    // New timer is to the right of current timer and there is overlap
    // with the current timer, but could the next timer (if any) be
    // a better fit?
    //
    //  -------------(--e---t-----?-------------------> time

    auto iter = timer_list_.make_iterator(entry);
    ++iter;
    if (iter != timer_list_.end()) {
      const Timer& next = *iter;
      if (next.scheduled_time_ <= timer->scheduled_time_) {
        // The new timer is to the right of the next timer. There is no
        // chance the current timer is a better fit.
        //
        //  -------------(--e---n---t----------------------> time
        continue;
      }

      if (next.scheduled_time_ < latest_deadline) {
        // There is slack overlap with the next timer, and also with the
        // current timer. Which coalescing is a better match?
        //
        //  --------------(-e---t---n-)-----------------------> time
        zx_duration_t delta_entry = zx_time_sub_time(timer->scheduled_time_, entry.scheduled_time_);
        zx_duration_t delta_next = zx_time_sub_time(next.scheduled_time_, timer->scheduled_time_);
        if (delta_next < delta_entry) {
          // New timer is closer to the next timer, handle it in the
          // next iteration.
          continue;
        }
      }
    }

    // Handles the remaining cases, note that there is overlap with
    // the current timer.
    //
    //  1- this is the last timer (next == NULL) or
    //  2- there is no overlap with the next timer, or
    //  3- there is overlap with both current and next but
    //     current is closer.
    //
    //  So we coalesce by scheduling early.
    timer->slack_ = zx_time_sub_time(entry.scheduled_time_, timer->scheduled_time_);
    timer->scheduled_time_ = entry.scheduled_time_;
    kcounter_add(timer_coalesced_counter, 1);
    timer_list_.insert_after(timer_list_.make_iterator(entry), timer);
    return;
  }

  // Walked off the end of the list and there was no overlap.
  timer->slack_ = 0;
  timer_list_.push_back(timer);
}

Timer::~Timer() {
  // Ensure that we are not on any TimerQueue's list.
  ZX_DEBUG_ASSERT(!InContainer());
  // Ensure that we are not active on some cpu.
  ZX_DEBUG_ASSERT(active_cpu_.load(ktl::memory_order_relaxed) == INVALID_CPU);
}

void Timer::Set(const Deadline& deadline, Callback callback, void* arg) {
  LTRACEF("timer %p deadline.when %" PRIi64 " deadline.slack.amount %" PRIi64
          " deadline.slack.mode %u callback %p arg %p\n",
          this, deadline.when(), deadline.slack().amount(), deadline.slack().mode(), callback, arg);

  DEBUG_ASSERT(magic_ == kMagic);
  DEBUG_ASSERT(deadline.slack().mode() <= TIMER_SLACK_LATE);
  DEBUG_ASSERT(deadline.slack().amount() >= 0);

  if (InContainer()) {
    panic("timer %p already in list\n", this);
  }

  const zx_time_t latest_deadline = deadline.latest();
  const zx_time_t earliest_deadline = deadline.earliest();

  Guard<MonitoredSpinLock, IrqSave> guard{TimerLock::Get(), SOURCE_TAG};

  cpu_num_t cpu = arch_curr_cpu_num();
  cpu_num_t active_cpu = active_cpu_.load(ktl::memory_order_relaxed);

  bool currently_active = (active_cpu == cpu);
  if (unlikely(currently_active)) {
    // The timer is active on our own cpu, we must be inside the callback.
    if (cancel_.load(ktl::memory_order_relaxed)) {
      return;
    }
  } else if (unlikely(active_cpu != INVALID_CPU)) {
    panic("timer %p currently active on a different cpu %u\n", this, active_cpu);
  }

  // Set up the structure.
  scheduled_time_ = deadline.when();
  callback_ = callback;
  arg_ = arg;
  cancel_.store(false, ktl::memory_order_relaxed);
  // We don't need to modify active_cpu_ because it is managed by timer_tick().

  LTRACEF("scheduled time %" PRIi64 "\n", scheduled_time_);

  TimerQueue& timer_queue = percpu::Get(cpu).timer_queue;

  timer_queue.Insert(this, earliest_deadline, latest_deadline);
  kcounter_add(timer_created_counter, 1);

  if (!timer_queue.timer_list_.is_empty() && &timer_queue.timer_list_.front() == this) {
    // We just modified the head of the timer queue.
    timer_queue.UpdatePlatformTimer(deadline.when());
  }
}

void TimerQueue::PreemptReset(zx_time_t deadline) {
  DEBUG_ASSERT(arch_ints_disabled());
  LTRACEF("preempt timer cpu %u deadline %" PRIi64 "\n", arch_curr_cpu_num(), deadline);
  preempt_timer_deadline_ = deadline;
  UpdatePlatformTimer(deadline);
}

bool Timer::Cancel() {
  DEBUG_ASSERT(magic_ == kMagic);

  Guard<MonitoredSpinLock, IrqSave> guard{TimerLock::Get(), SOURCE_TAG};

  cpu_num_t cpu = arch_curr_cpu_num();

  // mark the timer as canceled
  cancel_.store(true, ktl::memory_order_relaxed);
  // TODO(https://fxbug.dev/42142666): Consider whether this DeviceMemoryBarrier is required
  arch::DeviceMemoryBarrier();

  // see if we're trying to cancel the timer we're currently in the middle of handling
  if (unlikely(active_cpu_.load(ktl::memory_order_relaxed) == cpu)) {
    // zero it out
    callback_ = nullptr;
    arg_ = nullptr;

    // we're done, so return back to the callback
    return false;
  }

  bool callback_not_running;

  // If this Timer is in a queue, remove it and adjust hardware timers if needed.
  if (InContainer()) {
    callback_not_running = true;

    TimerQueue& timer_queue = percpu::Get(cpu).timer_queue;

    // Save a copy of the old head of the queue so later we can see if we modified the head.
    const Timer* oldhead = nullptr;
    if (!timer_queue.timer_list_.is_empty()) {
      oldhead = &timer_queue.timer_list_.front();
    }

    // Remove this Timer from this whatever TimerQueue it's on.
    RemoveFromContainer();
    kcounter_add(timer_canceled_counter, 1);

    // TODO(cpu): If, after removing |timer| there is one other single Timer with
    // the same scheduled_time_ and slack_ non-zero, then it is possible to return
    // that timer to the ideal scheduled_time_.

    // See if we've just modified the head of this TimerQueue.
    //
    // If Timer was on another cpu's queue, we'll just let it fire and sort itself out.
    if (unlikely(oldhead == this)) {
      // The Timer we're canceling was at head of this queue, so see if we should update platform
      // timer.
      if (!timer_queue.timer_list_.is_empty()) {
        timer_queue.UpdatePlatformTimer(timer_queue.timer_list_.front().scheduled_time_);
      } else if (timer_queue.next_timer_deadline_ == ZX_TIME_INFINITE) {
        LTRACEF("clearing old hw timer, preempt timer not set, nothing in the queue\n");
        platform_stop_timer();
      }
    }
  } else {
    callback_not_running = false;
  }

  guard.Release();

  // wait for the timer to become un-busy in case a callback is currently active on another cpu
  while (active_cpu_.load(ktl::memory_order_relaxed) != INVALID_CPU) {
    arch::Yield();
  }

  // zero it out
  callback_ = nullptr;
  arg_ = nullptr;

  return callback_not_running;
}

// called at interrupt time to process any pending timers
void timer_tick(zx_time_t now) {
  DEBUG_ASSERT(arch_ints_disabled());

  CPU_STATS_INC(timer_ints);

  cpu_num_t cpu = arch_curr_cpu_num();

  LTRACEF("cpu %u now %" PRIi64 ", sp %p\n", cpu, now, __GET_FRAME());

  percpu::Get(cpu).timer_queue.Tick(now, cpu);
}

void TimerQueue::Tick(zx_time_t now, cpu_num_t cpu) {
  // The platform timer has fired, so no deadline is set.
  next_timer_deadline_ = ZX_TIME_INFINITE;

  // Service the preemption timer before acquiring the timer lock.
  if (now >= preempt_timer_deadline_) {
    preempt_timer_deadline_ = ZX_TIME_INFINITE;
    Scheduler::TimerTick(SchedTime{now});
  }

  Guard<MonitoredSpinLock, NoIrqSave> guard{TimerLock::Get(), SOURCE_TAG};

  for (;;) {
    // See if there's an event to process.
    if (timer_list_.is_empty()) {
      break;
    }

    Timer& timer = timer_list_.front();

    LTRACEF("next item on timer queue %p at %" PRIi64 " now %" PRIi64 " (%p, arg %p)\n", &timer,
            timer.scheduled_time_, now, timer.callback_, timer.arg_);
    if (likely(now < timer.scheduled_time_)) {
      break;
    }

    // Process it.
    LTRACEF("timer %p\n", &timer);
    DEBUG_ASSERT_MSG(timer.magic_ == Timer::kMagic,
                     "ASSERT: timer failed magic check: timer %p, magic 0x%x\n", &timer,
                     (uint)timer.magic_);
    timer_list_.erase(timer);

    // Mark the timer busy.
    timer.active_cpu_.store(cpu, ktl::memory_order_relaxed);
    // Unlocking the spinlock in CallUnlocked acts as a release fence.

    // Now that the timer is off of the list, release the spinlock to handle
    // the callback, then re-acquire in case it is requeued.
    guard.CallUnlocked([&timer, now]() {
      LTRACEF("dequeued timer %p, scheduled %" PRIi64 "\n", &timer, timer.scheduled_time_);

      CPU_STATS_INC(timers);
      kcounter_add(timer_fired_counter, 1);

      LTRACEF("timer %p firing callback %p, arg %p\n", &timer, timer.callback_, timer.arg_);
      timer.callback_(&timer, now, timer.arg_);

      DEBUG_ASSERT(arch_ints_disabled());
    });

    // Mark it not busy.
    timer.active_cpu_.store(INVALID_CPU, ktl::memory_order_relaxed);
    // TODO(https://fxbug.dev/42142666): Consider whether this DeviceMemoryBarrier is required
    arch::DeviceMemoryBarrier();
  }

  // Get the deadline of the event at the head of the queue (if any).
  zx_time_t deadline = ZX_TIME_INFINITE;
  if (!timer_list_.is_empty()) {
    deadline = timer_list_.front().scheduled_time_;
    // This has to be the case or it would have fired already.
    DEBUG_ASSERT(deadline > now);
  }

  // We're done manipulating the timer queue.
  guard.Release();

  // Set the platform timer to the *soonest* of queue event and preemption timer.
  if (preempt_timer_deadline_ < deadline) {
    deadline = preempt_timer_deadline_;
  }
  UpdatePlatformTimer(deadline);
}

zx_status_t Timer::TrylockOrCancel(MonitoredSpinLock* lock) {
  // spin trylocking on the passed in spinlock either waiting for it
  // to grab or the passed in timer to be canceled.
  while (unlikely(lock->TryAcquire(SOURCE_TAG))) {
    // we failed to grab it, check for cancel
    if (cancel_.load(ktl::memory_order_relaxed)) {
      // we were canceled, so bail immediately
      return ZX_ERR_TIMED_OUT;
    }
    // tell the arch to wait
    arch::Yield();
  }

  return ZX_OK;
}

zx_status_t Timer::TrylockOrCancel(ChainLock& lock) {
  // Just like the previous implementation of TrylockOrCancel, but this version
  // attempts operates on a ChainLock instead of a MonitoredSpinLock, and is
  // used by the wait queue timeout mechanism.  Keep attempting to acquire the
  // lock, arch:Yield'ing in between attempts, and bailing out in the case that
  // we notice that the cancel_ flag has been set.
  while (!lock.TryAcquire()) {
    if (cancel_.load(ktl::memory_order_relaxed)) {
      return ZX_ERR_TIMED_OUT;
    }
    arch::Yield();
  }

  return ZX_OK;
}

void TimerQueue::TransitionOffCpu(TimerQueue& source) {
  Guard<MonitoredSpinLock, IrqSave> guard{TimerLock::Get(), SOURCE_TAG};

  Timer* old_head = nullptr;
  if (!timer_list_.is_empty()) {
    old_head = &timer_list_.front();
  }

  // Move all timers from |source| to this TimerQueue.
  Timer* timer;
  while ((timer = source.timer_list_.pop_front()) != nullptr) {
    // We lost the original asymmetric slack information so when we combine them
    // with the other timer queue they are not coalesced again.
    // TODO(cpu): figure how important this case is.
    Insert(timer, timer->scheduled_time_, timer->scheduled_time_);
    // Note, we do not increment the "created" counter here because we are simply moving these
    // timers from one queue to another and we already counted them when they were first
    // created.
  }

  Timer* new_head = nullptr;
  if (!timer_list_.is_empty()) {
    new_head = &timer_list_.front();
  }

  if (new_head != nullptr && new_head != old_head) {
    // We just modified the head of the timer queue.
    UpdatePlatformTimer(new_head->scheduled_time_);
  }

  // The old TimerQueue has no tasks left, so reset the deadlines.
  source.preempt_timer_deadline_ = ZX_TIME_INFINITE;
  source.next_timer_deadline_ = ZX_TIME_INFINITE;
}

void TimerQueue::ThawPercpu(void) {
  DEBUG_ASSERT(arch_ints_disabled());
  Guard<MonitoredSpinLock, NoIrqSave> guard{TimerLock::Get(), SOURCE_TAG};

  // Reset next_timer_deadline_ so that UpdatePlatformTimer will reconfigure the timer.
  next_timer_deadline_ = ZX_TIME_INFINITE;
  zx_time_t deadline = preempt_timer_deadline_;

  if (!timer_list_.is_empty()) {
    Timer& t = timer_list_.front();
    if (t.scheduled_time_ < deadline) {
      deadline = t.scheduled_time_;
    }
  }

  guard.Release();

  UpdatePlatformTimer(deadline);
}

void TimerQueue::PrintTimerQueues(char* buf, size_t len) {
  size_t ptr = 0;
  zx_time_t now = current_time();

  Guard<MonitoredSpinLock, IrqSave> guard{TimerLock::Get(), SOURCE_TAG};
  for (cpu_num_t i = 0; i < percpu::processor_count(); i++) {
    if (mp_is_cpu_online(i)) {
      ptr += snprintf(buf + ptr, len - ptr, "cpu %u:\n", i);
      if (ptr >= len) {
        return;
      }
      zx_time_t last = now;
      for (Timer& t : percpu::Get(i).timer_queue.timer_list_) {
        zx_duration_t delta_now = zx_time_sub_time(t.scheduled_time_, now);
        zx_duration_t delta_last = zx_time_sub_time(t.scheduled_time_, last);
        ptr += snprintf(buf + ptr, len - ptr,
                        "\ttime %" PRIi64 " delta_now %" PRIi64 " delta_last %" PRIi64
                        " func %p arg %p\n",
                        t.scheduled_time_, delta_now, delta_last, t.callback_, t.arg_);
        if (ptr >= len) {
          return;
        }
        last = t.scheduled_time_;
      }
    }
  }
}

#include <lib/console.h>

static int cmd_timers(int argc, const cmd_args* argv, uint32_t flags) {
  const size_t timer_buffer_size = PAGE_SIZE;

  // allocate a buffer to dump the timer queue into to avoid reentrancy issues with the
  // timer spinlock
  char* buf = static_cast<char*>(malloc(timer_buffer_size));
  if (!buf) {
    return ZX_ERR_NO_MEMORY;
  }

  TimerQueue::PrintTimerQueues(buf, timer_buffer_size);

  printf("%s", buf);

  free(buf);

  return 0;
}

STATIC_COMMAND_START
STATIC_COMMAND_MASKED("timers", "dump the current kernel timer queues", &cmd_timers,
                      CMD_AVAIL_NORMAL)
STATIC_COMMAND_END(kernel)