/*
 * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#ifndef WTF_LockAlgorithm_h
#define WTF_LockAlgorithm_h

#include <thread>
#include <wtf/Atomics.h>
#include <wtf/Compiler.h>
#include <wtf/ParkingLot.h>

namespace WTF {

// This is the algorithm used by WTF::Lock. You can use it to project one lock onto any atomic
// field. The limit of one lock is due to the use of the field's address as a key to find the lock's
// queue.

template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
class LockAlgorithm {
    static const bool verbose = false;
    static const LockType mask = isHeldBit | hasParkedBit;

public:
    static bool lockFastAssumingZero(Atomic<LockType>& lock)
    {
        return lock.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire);
    }
    
    static bool lockFast(Atomic<LockType>& lock)
    {
        LockType oldValue = lock.load(std::memory_order_relaxed);
        if (oldValue & isHeldBit)
            return false;
        return lock.compareExchangeWeak(oldValue, oldValue | isHeldBit, std::memory_order_acquire);
    }
    
    static void lock(Atomic<LockType>& lock)
    {
        if (UNLIKELY(!lockFast(lock)))
            lockSlow(lock);
    }
    
    static bool tryLock(Atomic<LockType>& lock)
    {
        for (;;) {
            uint8_t currentByteValue = lock.load(std::memory_order_relaxed);
            if (currentByteValue & isHeldBit)
                return false;
            if (lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit, std::memory_order_acquire))
                return true;
        }
    }

    static bool unlockFastAssumingZero(Atomic<LockType>& lock)
    {
        return lock.compareExchangeWeak(isHeldBit, 0, std::memory_order_release);
    }
    
    static bool unlockFast(Atomic<LockType>& lock)
    {
        LockType oldValue = lock.load(std::memory_order_relaxed);
        if ((oldValue & mask) != isHeldBit)
            return false;
        return lock.compareExchangeWeak(oldValue, oldValue & ~isHeldBit, std::memory_order_release);
    }
    
    static void unlock(Atomic<LockType>& lock)
    {
        if (UNLIKELY(!unlockFast(lock)))
            unlockSlow(lock, Unfair);
    }
    
    static void unlockFairly(Atomic<LockType>& lock)
    {
        if (UNLIKELY(!unlockFast(lock)))
            unlockSlow(lock, Fair);
    }
    
    static bool safepointFast(const Atomic<LockType>& lock)
    {
        WTF::compilerFence();
        return !(lock.load(std::memory_order_relaxed) & hasParkedBit);
    }
    
    static void safepoint(Atomic<LockType>& lock)
    {
        if (UNLIKELY(!safepointFast(lock)))
            safepointSlow(lock);
    }
    
    static bool isLocked(const Atomic<LockType>& lock)
    {
        return lock.load(std::memory_order_acquire) & isHeldBit;
    }
    
    NEVER_INLINE static void lockSlow(Atomic<LockType>& lock)
    {
        unsigned spinCount = 0;

        // This magic number turns out to be optimal based on past JikesRVM experiments.
        const unsigned spinLimit = 40;
    
        for (;;) {
            uint8_t currentByteValue = lock.load();

            // We allow ourselves to barge in.
            if (!(currentByteValue & isHeldBit)
                && lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
                return;

            // If there is nobody parked and we haven't spun too much, we can just try to spin around.
            if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
                spinCount++;
                std::this_thread::yield();
                continue;
            }

            // Need to park. We do this by setting the parked bit first, and then parking. We spin around
            // if the parked bit wasn't set and we failed at setting it.
            if (!(currentByteValue & hasParkedBit)
                && !lock.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
                continue;

            // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
            ParkingLot::ParkResult parkResult =
                ParkingLot::compareAndPark(&lock, currentByteValue | isHeldBit | hasParkedBit);
            if (parkResult.wasUnparked) {
                switch (static_cast<Token>(parkResult.token)) {
                case DirectHandoff:
                    // The lock was never released. It was handed to us directly by the thread that did
                    // unlock(). This means we're done!
                    RELEASE_ASSERT(isLocked(lock));
                    return;
                case BargingOpportunity:
                    // This is the common case. The thread that called unlock() has released the lock,
                    // and we have been woken up so that we may get an opportunity to grab the lock. But
                    // other threads may barge, so the best that we can do is loop around and try again.
                    break;
                }
            }

            // We have awoken, or we never parked because the byte value changed. Either way, we loop
            // around and try again.
        }
    }
    
    enum Fairness {
        Fair,
        Unfair
    };
    NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness)
    {
        // We could get here because the weak CAS in unlock() failed spuriously, or because there is
        // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
        // be held and parked if someone attempts to lock just as we are unlocking.
        for (;;) {
            uint8_t oldByteValue = lock.load();
            RELEASE_ASSERT(
                (oldByteValue & mask) == isHeldBit
                || (oldByteValue & mask) == (isHeldBit | hasParkedBit));
        
            if ((oldByteValue & mask) == isHeldBit) {
                if (lock.compareExchangeWeak(oldByteValue, oldByteValue & ~isHeldBit))
                    return;
                continue;
            }

            // Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
            // directly, or we will unlock the lock at the same time as we unpark to allow for barging.
            // When we unlock, we may leave the parked bit set if there is a chance that there are still
            // other threads parked.
            ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
            ParkingLot::unparkOne(
                &lock,
                [&] (ParkingLot::UnparkResult result) -> intptr_t {
                    // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
                    // so we should still see both bits set right now.
                    ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
                
                    if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
                        // We don't unlock anything. Instead, we hand the lock to the thread that was
                        // waiting.
                        return DirectHandoff;
                    }
                    
                    lock.transaction(
                        [&] (LockType& value) {
                            value &= ~mask;
                            if (result.mayHaveMoreThreads)
                                value |= hasParkedBit;
                        });
                    return BargingOpportunity;
                });
            return;
        }
    }
    
    NEVER_INLINE static void safepointSlow(Atomic<LockType>& lockWord)
    {
        unlockFairly(lockWord);
        lock(lockWord);
    }
    
private:
    enum Token {
        BargingOpportunity,
        DirectHandoff
    };
};

} // namespace WTF

using WTF::LockAlgorithm;

#endif // WTF_LockAlgorithm_h