// 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 <assert.h>
#include <debug.h>
#include <err.h>
#include <inttypes.h>
#include <kernel/align.h>
#include <kernel/lockdep.h>
#include <kernel/mp.h>
#include <kernel/percpu.h>
#include <kernel/sched.h>
#include <kernel/spinlock.h>
#include <kernel/stats.h>
#include <kernel/thread.h>
#include <kernel/timer.h>
#include <lib/counters.h>
#include <list.h>
#include <malloc.h>
#include <platform.h>
#include <platform/timer.h>
#include <trace.h>
#include <zircon/time.h>
#include <zircon/types.h>

#define LOCAL_TRACE 0

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

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

// Number of timers that have fired (i.e. callback was invoked).
KCOUNTER(timer_fired_counter, "kernel.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, "kernel.timer.canceled");

namespace {

spin_lock_t timer_lock __CPU_ALIGN_EXCLUSIVE = SPIN_LOCK_INITIAL_VALUE;
DECLARE_SINGLETON_LOCK_WRAPPER(TimerLock, timer_lock);

} // anonymous namespace

void timer_init(timer_t* timer) {
    *timer = (timer_t)TIMER_INITIAL_VALUE(*timer);
}

// Set the platform's oneshot timer to the minimum of its current deadline and |new_deadline|.
//
// Call this when the timer queue's head changes.
//
// Can only be called when interrupts are disabled and current CPU is |cpu|.
static void update_platform_timer(uint cpu, zx_time_t new_deadline) {
    DEBUG_ASSERT(arch_ints_disabled());
    DEBUG_ASSERT(cpu == arch_curr_cpu_num());
    if (new_deadline < percpu[cpu].next_timer_deadline) {
        LTRACEF("rescheduling timer for %" PRIi64 " nsecs\n", new_deadline);
        platform_set_oneshot_timer(new_deadline);
        percpu[cpu].next_timer_deadline = new_deadline;
    }
}

static void insert_timer_in_queue(uint cpu, timer_t* timer,
                                  zx_time_t earliest_deadline, zx_time_t latest_deadline) {

    DEBUG_ASSERT(arch_ints_disabled());
    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.
    //
    timer_t* entry;

    list_for_every_entry (&percpu[cpu].timer_queue, entry, timer_t, node) {
        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;
            list_add_before(&entry->node, &timer->node);
            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);
            list_add_after(&entry->node, &timer->node);
            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
        //

        const timer_t* next =
            list_next_type(&percpu[cpu].timer_queue, &entry->node, timer_t, node);

        if (next != NULL) {
            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);
        list_add_after(&entry->node, &timer->node);
        return;
    }

    // Walked off the end of the list and there was no overlap.
    timer->slack = 0;
    list_add_tail(&percpu[cpu].timer_queue, &timer->node);
}

void timer_set(timer_t* timer, const Deadline& deadline,
               timer_callback callback, void* arg) {
    LTRACEF("timer %p deadline.when %" PRIi64 " deadline.slack.amount %" PRIi64
            " deadline.slack.mode %u callback %p arg %p\n",
            timer, deadline.when(), deadline.slack().amount(), deadline.slack().mode(), callback,
            arg);

    DEBUG_ASSERT(timer->magic == TIMER_MAGIC);
    DEBUG_ASSERT(deadline.slack().mode() <= TIMER_SLACK_EARLY);
    DEBUG_ASSERT(deadline.slack().amount() >= 0);

    if (list_in_list(&timer->node)) {
        panic("timer %p already in list\n", timer);
    }

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

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

    uint cpu = arch_curr_cpu_num();

    bool currently_active = (timer->active_cpu == (int)cpu);
    if (unlikely(currently_active)) {
        // the timer is active on our own cpu, we must be inside the callback
        if (timer->cancel) {
            return;
        }
    } else if (unlikely(timer->active_cpu >= 0)) {
        panic("timer %p currently active on a different cpu %d\n", timer, timer->active_cpu);
    }

    // Set up the structure.
    timer->scheduled_time = deadline.when();
    timer->callback = callback;
    timer->arg = arg;
    timer->cancel = false;
    // We don't need to modify timer->active_cpu because it is managed by timer_tick().

    LTRACEF("scheduled time %" PRIi64 "\n", timer->scheduled_time);

    insert_timer_in_queue(cpu, timer, earliest_deadline, latest_deadline);
    kcounter_add(timer_created_counter, 1);

    if (list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node) == timer) {
        // we just modified the head of the timer queue
        update_platform_timer(cpu, deadline.when());
    }
}

void timer_preempt_reset(zx_time_t deadline) {
    DEBUG_ASSERT(arch_ints_disabled());

    uint cpu = arch_curr_cpu_num();

    LTRACEF("preempt timer cpu %u deadline %" PRIi64 "\n", cpu, deadline);

    percpu[cpu].preempt_timer_deadline = deadline;

    update_platform_timer(cpu, deadline);
}

void timer_preempt_cancel() {
    DEBUG_ASSERT(arch_ints_disabled());

    uint cpu = arch_curr_cpu_num();

    percpu[cpu].preempt_timer_deadline = ZX_TIME_INFINITE;

    // Note, we're not updating the platform timer. It's entirely possible the timer queue is empty
    // and the preemption timer is the only reason the platform timer is set. To know that, we'd
    // need to acquire a lock and look at the queue. Rather than pay that cost, leave the platform
    // timer as is and expect the recipient to handle spurious wakeups.
}

bool timer_cancel(timer_t* timer) {
    DEBUG_ASSERT(timer->magic == TIMER_MAGIC);

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

    uint cpu = arch_curr_cpu_num();

    // mark the timer as canceled
    timer->cancel = true;
    mb();

    // see if we're trying to cancel the timer we're currently in the middle of handling
    if (unlikely(timer->active_cpu == (int)cpu)) {
        // zero it out
        timer->callback = NULL;
        timer->arg = NULL;

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

    bool callback_not_running;

    // if the timer is in a queue, remove it and adjust hardware timers if needed
    if (list_in_list(&timer->node)) {
        callback_not_running = true;

        // save a copy of the old head of the queue so later we can see if we modified the head
        timer_t* oldhead = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);

        // remove our timer from the queue
        list_delete(&timer->node);
        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 cpu's timer queue.
        // if we modified another cpu's queue, we'll just let it fire and sort itself out
        if (unlikely(oldhead == timer)) {
            // timer we're canceling was at head of queue, see if we should update platform timer
            timer_t* newhead = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);
            if (newhead) {
                update_platform_timer(cpu, newhead->scheduled_time);
            } else if (percpu[cpu].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 (timer->active_cpu >= 0) {
        arch_spinloop_pause();
    }

    // zero it out
    timer->callback = NULL;
    timer->arg = NULL;

    return callback_not_running;
}

// called at interrupt time to process any pending timers
void timer_tick(zx_time_t now) {
    timer_t* timer;

    DEBUG_ASSERT(arch_ints_disabled());

    CPU_STATS_INC(timer_ints);

    uint cpu = arch_curr_cpu_num();

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

    // platform timer has fired, no deadline is set
    percpu[cpu].next_timer_deadline = ZX_TIME_INFINITE;

    // service preempt timer before acquiring the timer lock
    if (now >= percpu[cpu].preempt_timer_deadline) {
        percpu[cpu].preempt_timer_deadline = ZX_TIME_INFINITE;
        sched_preempt_timer_tick(now);
    }

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

    for (;;) {
        // see if there's an event to process
        timer = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);
        if (likely(timer == 0)) {
            break;
        }
        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 && timer->magic == TIMER_MAGIC,
                         "ASSERT: timer failed magic check: timer %p, magic 0x%x\n",
                         timer, (uint)timer->magic);
        list_delete(&timer->node);

        // mark the timer busy
        timer->active_cpu = cpu;
        // Unlocking the spinlock in CallUnlocked acts as a memory barrier.

        // 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 = -1;
        mb();
    }

    // get the deadline of the event at the head of the queue (if any)
    zx_time_t deadline = ZX_TIME_INFINITE;
    timer = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);
    if (timer) {
        deadline = timer->scheduled_time;

        // 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 preempt timer
    if (percpu[cpu].preempt_timer_deadline < deadline) {
        deadline = percpu[cpu].preempt_timer_deadline;
    }
    update_platform_timer(cpu, deadline);
}

zx_status_t timer_trylock_or_cancel(timer_t* t, spin_lock_t* lock) {
    // spin trylocking on the passed in spinlock either waiting for it
    // to grab or the passed in timer to be canceled.
    while (unlikely(spin_trylock(lock))) {
        // we failed to grab it, check for cancel
        if (t->cancel) {
            // we were canceled, so bail immediately
            return ZX_ERR_TIMED_OUT;
        }
        // tell the arch to wait
        arch_spinloop_pause();
    }

    return ZX_OK;
}

void timer_transition_off_cpu(uint old_cpu) {
    Guard<spin_lock_t, IrqSave> guard{TimerLock::Get()};
    uint cpu = arch_curr_cpu_num();

    timer_t* old_head = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);

    timer_t *entry = NULL, *tmp_entry = NULL;
    // Move all timers from old_cpu to this cpu
    list_for_every_entry_safe (&percpu[old_cpu].timer_queue, entry, tmp_entry, timer_t, node) {
        list_delete(&entry->node);
        // 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_in_queue(cpu, entry, entry->scheduled_time, entry->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_t* new_head = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);
    if (new_head != NULL && new_head != old_head) {
        // we just modified the head of the timer queue
        update_platform_timer(cpu, new_head->scheduled_time);
    }

    // the old cpu has no tasks left, so reset the deadlines
    percpu[old_cpu].preempt_timer_deadline = ZX_TIME_INFINITE;
    percpu[old_cpu].next_timer_deadline = ZX_TIME_INFINITE;
}

void timer_thaw_percpu(void) {
    DEBUG_ASSERT(arch_ints_disabled());
    Guard<spin_lock_t, NoIrqSave> guard{TimerLock::Get()};

    uint cpu = arch_curr_cpu_num();

    // reset next_timer_deadline so that update_platform_timer will reconfigure the timer
    percpu[cpu].next_timer_deadline = ZX_TIME_INFINITE;
    zx_time_t deadline = percpu[cpu].preempt_timer_deadline;

    timer_t* t = list_peek_head_type(&percpu[cpu].timer_queue, timer_t, node);
    if (t) {
        if (t->scheduled_time < deadline) {
            deadline = t->scheduled_time;
        }
    }

    guard.Release();

    update_platform_timer(cpu, deadline);
}

void timer_queue_init(void) {
    for (uint i = 0; i < SMP_MAX_CPUS; i++) {
        list_initialize(&percpu[i].timer_queue);
        percpu[i].preempt_timer_deadline = ZX_TIME_INFINITE;
        percpu[i].next_timer_deadline = ZX_TIME_INFINITE;
    }
}

// print a timer queue dump into the passed in buffer
static void dump_timer_queues(char* buf, size_t len) {
    size_t ptr = 0;
    zx_time_t now = current_time();

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

    for (uint i = 0; i < SMP_MAX_CPUS; i++) {
        if (mp_is_cpu_online(i)) {
            ptr += snprintf(buf + ptr, len - ptr, "cpu %u:\n", i);

            timer_t* t;
            zx_time_t last = now;
            list_for_every_entry (&percpu[i].timer_queue, t, timer_t, node) {
                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);
                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;
    }

    dump_timer_queues(buf, timer_buffer_size);

    printf("%s", buf);

    free(buf);

    return 0;
}

STATIC_COMMAND_START
#if LK_DEBUGLEVEL > 1
STATIC_COMMAND_MASKED("timers", "dump the current kernel timer queues", &cmd_timers, CMD_AVAIL_NORMAL)
#endif
STATIC_COMMAND_END(kernel);