// Copyright 2016 The Fuchsia Authors
// Copyright (c) 2008-2014 Travis Geiselbrecht
// Copyright (c) 2012-2012 Shantanu Gupta
//
// 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  Mutex functions
 *
 * @defgroup mutex Mutex
 * @{
 */

#include <kernel/mutex.h>

#include <assert.h>
#include <debug.h>
#include <err.h>
#include <inttypes.h>
#include <kernel/sched.h>
#include <kernel/thread.h>
#include <kernel/thread_lock.h>
#include <ktl/type_traits.h>
#include <lib/ktrace.h>
#include <trace.h>
#include <zircon/types.h>

#define LOCAL_TRACE 0

namespace {

enum class KernelMutexTracingLevel {
    None,       // No tracing is ever done.  All code drops out at compile time.
    Contested,  // Trace events are only generated when mutexes are contested.
    All         // Trace events are generated for all mutex interactions.
};

// By default, kernel mutex tracing is disabled.
template <KernelMutexTracingLevel = KernelMutexTracingLevel::None, typename = void>
class KTracer;

template <>
class KTracer<KernelMutexTracingLevel::None> {
public:
    KTracer() = default;
    void KernelMutexUncontestedAcquire(const Mutex* mutex) {}
    void KernelMutexUncontestedRelease(const Mutex* mutex) {}
    void KernelMutexBlock(const Mutex* mutex, thread_t* blocker, uint32_t waiter_count) {}
    void KernelMutexWake(const Mutex* mutex, thread_t* new_owner, uint32_t waiter_count) {}
};

template <KernelMutexTracingLevel Level>
class KTracer<Level,
              ktl::enable_if_t<(Level == KernelMutexTracingLevel::Contested) ||
                               (Level == KernelMutexTracingLevel::All)>> {
public:
    KTracer() : ts_(ktrace_timestamp()) {}

    void KernelMutexUncontestedAcquire(const Mutex* mutex) {
        if constexpr (Level == KernelMutexTracingLevel::All) {
            KernelMutexTrace(TAG_KERNEL_MUTEX_ACQUIRE, mutex, nullptr, 0);
        }
    }

    void KernelMutexUncontestedRelease(const Mutex* mutex) {
        if constexpr (Level == KernelMutexTracingLevel::All) {
            KernelMutexTrace(TAG_KERNEL_MUTEX_RELEASE, mutex, nullptr, 0);
        }
    }

    void KernelMutexBlock(const Mutex* mutex, const thread_t* blocker, uint32_t waiter_count) {
        KernelMutexTrace(TAG_KERNEL_MUTEX_BLOCK, mutex, blocker, waiter_count);
    }

    void KernelMutexWake(const Mutex* mutex, const thread_t* new_owner, uint32_t waiter_count) {
        KernelMutexTrace(TAG_KERNEL_MUTEX_RELEASE, mutex, new_owner, waiter_count);
    }

private:
    void KernelMutexTrace(uint32_t tag,
                          const Mutex* mutex,
                          const thread_t* t,
                          uint32_t waiter_count) {
        uint32_t mutex_id = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(mutex));
        uint32_t tid = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(t));
        uint32_t flags = static_cast<uint32_t>(
                arch_curr_cpu_num() & KTRACE_FLAGS_KERNEL_MUTEX_CPUID_MASK);

        if ((t != nullptr) && (t->user_thread != nullptr)) {
            tid = static_cast<uint32_t>(t->user_tid);
            flags |= KTRACE_FLAGS_KERNEL_MUTEX_USER_MODE_TID;
        }

        ktrace(tag, mutex_id, tid, waiter_count, flags, ts_);
    }

    const uint64_t ts_;
};

}  // anon namespace

Mutex::~Mutex() {
    magic_.Assert();
    DEBUG_ASSERT(!arch_blocking_disallowed());

    if (LK_DEBUGLEVEL > 0) {
        if (val() != STATE_FREE) {
            thread_t* h = holder();
            panic("~Mutex(): thread %p (%s) tried to destroy locked mutex %p, locked by %p (%s)\n",
                  get_current_thread(), get_current_thread()->name, this, h, h->name);
        }
    }

    val_.store(STATE_FREE, ktl::memory_order_relaxed);
}

/**
 * @brief  Acquire the mutex
 */
void Mutex::Acquire() {
    magic_.Assert();
    DEBUG_ASSERT(!arch_blocking_disallowed());

    thread_t* ct = get_current_thread();
    uintptr_t old_mutex_state;
    uintptr_t new_mutex_state;

    // fast path: assume the mutex is unlocked and try to grab it
    //
    old_mutex_state = STATE_FREE;
    new_mutex_state = reinterpret_cast<uintptr_t>(ct);
    if (likely(val_.compare_exchange_strong(old_mutex_state, new_mutex_state,
                                            ktl::memory_order_seq_cst,
                                            ktl::memory_order_seq_cst))) {
        // acquired it cleanly.  Don't bother to update the ownership of our
        // wait queue.  As of this instant, the mutex appears to be uncontested.
        // If someone else attempts to acquire the mutex and discovers it to be
        // already locked, they will take care of updating the wait queue
        // ownership while they are inside of the thread_lock.
        KTracer{}.KernelMutexUncontestedAcquire(this);
        return;
    }

    if ((LK_DEBUGLEVEL > 0) && unlikely(this->IsHeld())) {
        panic("Mutex::Acquire: thread %p (%s) tried to acquire mutex %p it already owns.\n",
              ct, ct->name, this);
    }

    {
        // we contended with someone else, will probably need to block
        Guard<spin_lock_t, IrqSave> guard{ThreadLock::Get()};

        // Check if the queued flag is currently set. The contested flag can only be changed
        // whilst the thread lock is held so we know we aren't racing with anyone here. This
        // is just an optimization and allows us to avoid redundantly doing the atomic OR.
        old_mutex_state = val();

        if (unlikely(!(old_mutex_state & STATE_FLAG_CONTESTED))) {
            // Set the queued flag to indicate that we're blocking.
            old_mutex_state = val_.fetch_or(STATE_FLAG_CONTESTED, ktl::memory_order_seq_cst);
            // We may have raced with the holder as they dropped the mutex.
            if (unlikely(old_mutex_state == STATE_FREE)) {
                // Since we set the contested flag we know that there are no
                // waiters and no one is able to perform fast path acquisition.
                // Therefore we can just take the mutex, and remove the queued
                // flag.
                val_.store(reinterpret_cast<uintptr_t>(ct), ktl::memory_order_seq_cst);
                return;
            }
        }

        // extract the current holder of the mutex from oldval, no need to
        // re-read from the mutex as it cannot change if the queued flag is set
        // without holding the thread lock (which we currently hold).  We need
        // to be sure that we inform our owned wait queue that this is the
        // proper queue owner as we block.
        thread_t* cur_owner = holder_from_val(old_mutex_state);
        KTracer{}.KernelMutexBlock(this, cur_owner, wait_.Count() + 1);
        zx_status_t ret = wait_.BlockAndAssignOwner(Deadline::infinite(),
                                                    cur_owner,
                                                    ResourceOwnership::Normal);

        if (unlikely(ret < ZX_OK)) {
            // mutexes are not interruptible and cannot time out, so it
            // is illegal to return with any error state.
            panic("Mutex::Acquire: wait queue block returns with error %d m %p, thr %p, sp %p\n",
                   ret, this, ct, __GET_FRAME());
        }

        // someone must have woken us up, we should own the mutex now
        DEBUG_ASSERT(ct == holder());
    }
}

// Shared implementation of release
template <Mutex::ThreadLockState TLS>
void Mutex::ReleaseInternal(const bool allow_reschedule) {
    thread_t* ct = get_current_thread();

    // Try the fast path.  Assume that we are locked, but uncontested.
    uintptr_t old_mutex_state = reinterpret_cast<uintptr_t>(ct);
    if (likely(val_.compare_exchange_strong(old_mutex_state, STATE_FREE,
                                            ktl::memory_order_seq_cst,
                                            ktl::memory_order_seq_cst))) {
        // We're done.  Since this mutex was uncontested, we know that we were
        // not receiving any priority pressure from the wait queue, and there is
        // nothing further to do.
        KTracer{}.KernelMutexUncontestedRelease(this);
        return;
    }

    // Sanity checks.  The mutex should have been either locked by us and
    // uncontested, or locked by us and contested.  Anything else is an internal
    // consistency error worthy of a panic.
    if (LK_DEBUGLEVEL > 0) {
        uintptr_t expected_state = reinterpret_cast<uintptr_t>(ct) | STATE_FLAG_CONTESTED;

        if (unlikely(old_mutex_state != expected_state)) {
            auto other_holder = reinterpret_cast<thread_t*>(old_mutex_state & ~STATE_FLAG_CONTESTED);
            panic("Mutex::ReleaseInternal: sanity check failure.  Thread %p (%s) tried to release "
                  "mutex %p.  Expected state (%lx) != observed state (%lx).  Other holder (%s)\n",
                  ct, ct->name, this, expected_state, old_mutex_state,
                  other_holder ? other_holder->name : "<none>");
        }
    }

    // compile-time conditionally acquire/release the thread lock
    // NOTE: using the manual spinlock grab/release instead of THREAD_LOCK because
    // the state variable needs to exit in either path.
    __UNUSED spin_lock_saved_state_t irq_state;
    if constexpr (TLS == ThreadLockState::NotHeld) {
        spin_lock_irqsave(&thread_lock, irq_state);
    }

    // Attempt to release a thread. If there are still waiters in the queue
    // after we successfully have woken a thread, be sure to assign ownership of
    // the queue to the thread which was woken so that it can properly receive
    // the priority pressure of the remaining waiters.
    using Action = OwnedWaitQueue::Hook::Action;
    thread_t* woken;
    auto cbk = [](thread_t* woken, void* ctx) -> Action {
        *(reinterpret_cast<thread**>(ctx)) = woken;
        return Action::SelectAndAssignOwner;
    };

    KTracer tracer;
    bool need_reschedule = wait_.WakeThreads(1, { cbk, &woken });
    tracer.KernelMutexWake(this, woken, wait_.Count());

    ktrace_ptr(TAG_KWAIT_WAKE, &wait_, 1, 0);

    // So, the mutex is now in one of three states.  It can be...
    //
    // 1) Owned and contested (we woke a thread up, and there are still waiters)
    // 2) Owned and uncontested (we woke a thread up, but it was the last one)
    // 3) Unowned (no thread woke up when we tried to wake one)
    //
    // Note, the only way to be in situation #3 is for the lock to have become
    // contested at some point in the past, but then to have a thread stop
    // waiting for the lock before acquiring it (either it timed out or was
    // killed).
    //
    uintptr_t new_mutex_state;
    if (woken != nullptr) {
        // We woke _someone_ up.  We be in situation #1 or #2
        new_mutex_state = reinterpret_cast<uintptr_t>(woken);
        if (!wait_.IsEmpty()) {
            // Situation #1.
            DEBUG_ASSERT(wait_.owner() == woken);
            new_mutex_state |= STATE_FLAG_CONTESTED;
        } else {
            // Situation #2.
            DEBUG_ASSERT(wait_.owner() == nullptr);
        }
    } else {
        DEBUG_ASSERT(wait_.IsEmpty());
        DEBUG_ASSERT(wait_.owner() == nullptr);
        new_mutex_state = STATE_FREE;
    }

    if (unlikely(!val_.compare_exchange_strong(old_mutex_state, new_mutex_state,
                                               ktl::memory_order_seq_cst,
                                               ktl::memory_order_seq_cst))) {
        panic("bad state (%lx != %lx) in mutex release %p, current thread %p\n",
                reinterpret_cast<uintptr_t>(ct) | STATE_FLAG_CONTESTED,
                old_mutex_state, this, ct);
    }

    if (allow_reschedule && need_reschedule) {
        sched_reschedule();
    }

    // compile-time conditionally THREAD_UNLOCK
    if constexpr (TLS == ThreadLockState::NotHeld) {
        spin_unlock_irqrestore(&thread_lock, irq_state);
    }
}

void Mutex::Release() {
    magic_.Assert();
    DEBUG_ASSERT(!arch_blocking_disallowed());

    // default release will reschedule if any threads are woken up and acquire the thread lock
    ReleaseInternal<ThreadLockState::NotHeld>(true);
}

void Mutex::ReleaseThreadLocked(const bool allow_reschedule) {
    magic_.Assert();
    DEBUG_ASSERT(!arch_blocking_disallowed());
    DEBUG_ASSERT(arch_ints_disabled());
    DEBUG_ASSERT(spin_lock_held(&thread_lock));

    // This special version of release will pass through the allow_reschedule flag
    // and not acquire the thread_lock
    ReleaseInternal<ThreadLockState::Held>(allow_reschedule);
}