// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#pragma once

#include <stdint.h>
#include <zircon/assert.h>
#include <zircon/compiler.h>

#include <fbl/intrusive_double_list.h>

#include <lockdep/common.h>
#include <lockdep/lock_class_state.h>

#include <utility>

namespace lockdep {

// Linked list entry that tracks a lock acquired by a thread. Each thread
// maintains a local list of AcquiredLockEntry instances. AcquiredLockEntry is
// intended to be allocated on the stack as a member of a RAII type to manage
// the lifetime of the acquisition. Consequently, this type is move-only to
// permit moving the context to a different stack frame. However, an instance
// must only be manipulated by the thread that created it.
class AcquiredLockEntry : public fbl::DoublyLinkedListable<AcquiredLockEntry*> {
public:
    AcquiredLockEntry() = default;
    AcquiredLockEntry(LockClassId id, uintptr_t order)
        : id_{id}, order_{order} {}

    ~AcquiredLockEntry() {
        ZX_DEBUG_ASSERT(!InContainer());
    }

    AcquiredLockEntry(const AcquiredLockEntry&) = delete;
    AcquiredLockEntry& operator=(const AcquiredLockEntry&) = delete;

    AcquiredLockEntry(AcquiredLockEntry&& other) { *this = std::move(other); }
    AcquiredLockEntry& operator=(AcquiredLockEntry&& other) {
        if (this != &other) {
            ZX_ASSERT(!InContainer());

            if (other.InContainer())
                Replace(&other);

            id_ = other.id_;
            order_ = other.order_;

            other.id_ = kInvalidLockClassId;
            other.order_ = 0;
        }
        return *this;
    }

    LockClassId id() const { return id_; }
    uintptr_t order() const { return order_; }

private:
    friend class ThreadLockState;

    // Replaces the given entry in the list with this entry.
    void Replace(AcquiredLockEntry* target);

    LockClassId id_{kInvalidLockClassId};
    uintptr_t order_{0};
};

// Tracks the locks held by a thread and updates accounting during acquire and
// release operations.
class ThreadLockState {
public:
    // Returns the ThreadLockState instance for the current thread.
    static ThreadLockState* Get() {
        return SystemGetThreadLockState();
    }

    // Attempts to add the given lock class to the acquired lock list. Lock
    // ordering and other checks are performed here.
    void Acquire(AcquiredLockEntry* lock_entry) {
        if (LockClassState::IsTrackingDisabled(lock_entry->id()))
            return;

        if (LockClassState::IsReportingDisabled(lock_entry->id()))
            reporting_disabled_count_++;

        // Scans the acquired lock list and performs the following operations:
        //  1. Checks that the given lock class is not already in the list unless
        //     the lock class is nestable or address ordering is correctly applied.
        //  2. Checks that the given lock class is not in the dependency set for
        //     any lock class already in the list.
        //  3. Checks that irq-safe locks are not held when acquiring an irq-unsafe
        //     lock.
        //  4. Adds each lock class already in the list to the dependency set of the
        //     given lock class.
        last_result_ = LockResult::Success;
        for (AcquiredLockEntry& entry : acquired_locks_) {
            if (entry.id() == lock_entry->id()) {
                if (lock_entry->order() <= entry.order()) {
                    if (!LockClassState::IsNestable(lock_entry->id()) && lock_entry->order() == 0)
                        Report(lock_entry, &entry, LockResult::AlreadyAcquired);
                    else
                        Report(lock_entry, &entry, LockResult::InvalidNesting);
                }
            } else {
                const LockResult result =
                    LockClassState::AddLockClass(lock_entry->id(), entry.id());
                if (result == LockResult::Success) {
                    // A new edge has been added to the graph, trigger a loop
                    // detection pass.
                    TriggerLoopDetection();
                } else if (result == LockResult::MaxLockDependencies) {
                    // If the dependency set is full report error.
                    Report(lock_entry, &entry, result);
                } else /* if (result == LockResult::DependencyExists) */ {
                    // Nothing to do when there are no changes to the graph.
                }

                // The following tests only need to be run when a new edge is
                // added for this ordered pair of locks; when the edge already
                // exists these tests have been performed before.
                if (result == LockResult::Success) {
                    const bool entry_irqsafe = LockClassState::IsIrqSafe(entry.id());
                    const bool lock_entry_irqsafe = LockClassState::IsIrqSafe(lock_entry->id());
                    if (entry_irqsafe && !lock_entry_irqsafe)
                        Report(lock_entry, &entry, LockResult::InvalidIrqSafety);

                    if (LockClassState::HasLockClass(entry.id(), lock_entry->id()))
                        Report(lock_entry, &entry, LockResult::OutOfOrder);
                }
            }
        }

        if (!LockClassState::IsActiveListDisabled(lock_entry->id()))
            acquired_locks_.push_back(lock_entry);
    }

    // Removes the given lock entry from the acquired lock list.
    void Release(AcquiredLockEntry* entry) {
        if (LockClassState::IsTrackingDisabled(entry->id()))
            return;

        if (LockClassState::IsReportingDisabled(entry->id()))
            reporting_disabled_count_--;

        if (entry->InContainer())
            acquired_locks_.erase(*entry);
    }

    // Returns result of the last Acquire operation for testing.
    LockResult last_result() const { return last_result_; }

    bool reporting_disabled() const { return reporting_disabled_count_ > 0; }

private:
    friend ThreadLockState* SystemGetThreadLockState();
    friend void SystemInitThreadLockState(ThreadLockState*);
    friend void AcquiredLockEntry::Replace(AcquiredLockEntry*);

    ThreadLockState() = default;
    ~ThreadLockState() = default;
    ThreadLockState(const ThreadLockState&) = delete;
    void operator=(const ThreadLockState&) = delete;

    // Replaces the given original entry with the replacement entry. This permits
    // lock entries to be allocated on the stack and migrate between stack
    // frames if lock guards are moved or returned.
    //
    // The original entry must already be on the acquired locks list and the
    // replacement entry must not be on any list.
    void Replace(AcquiredLockEntry* original, AcquiredLockEntry* replacement) {
        acquired_locks_.replace(*original, replacement);
    }

    // Reports a detected lock violation using the system-defined runtime handler.
    void Report(AcquiredLockEntry* bad_entry, AcquiredLockEntry* conflicting_entry,
                LockResult result) {
        if ((result == LockResult::AlreadyAcquired ||
             result == LockResult::InvalidNesting) &&
            LockClassState::IsReAcquireFatal(bad_entry->id())) {
            SystemLockValidationFatal(bad_entry, this,
                                      __GET_CALLER(0),
                                      __GET_FRAME(0),
                                      LockResult::AlreadyAcquired);
        }

        if (!reporting_disabled()) {
            reporting_disabled_count_++;

            SystemLockValidationError(bad_entry, conflicting_entry, this,
                                      __GET_CALLER(0), __GET_FRAME(0), result);

            reporting_disabled_count_--;

            // Update the last result for testing.
            if (last_result_ == LockResult::Success)
                last_result_ = result;
        }
    }

    // Triggers a loop detection by the system-defined runtime handler.
    void TriggerLoopDetection() {
        if (!reporting_disabled()) {
            reporting_disabled_count_++;

            SystemTriggerLoopDetection();

            reporting_disabled_count_--;
        }
    }

    // Tracks the lock classes acquired by the current thread.
    fbl::DoublyLinkedList<AcquiredLockEntry*> acquired_locks_{};

    // Tracks the number of locks held that have the LockFlagsReportingDisabled
    // flag set. Reporting and loop detection are not triggered when this count
    // is greater than zero. This value is also incremented by one for the
    // duration of a report or loop detection trigger to prevent recursive calls
    // due to locks acquired by the system-defined runtime API.
    uint16_t reporting_disabled_count_{0};

    // Tracks the result of the last Acquire operation for testing.
    LockResult last_result_{LockResult::Success};
};

// Defined after ThreadLockState because of dependency on its methods.
inline void AcquiredLockEntry::Replace(AcquiredLockEntry* target) {
    ThreadLockState::Get()->Replace(target, this);
}

} // namespace lockdep