darling-WTF/wtf/CountingLock.h

/*
 * Copyright (C) 2017 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. 
 */

#pragma once

#include <wtf/DataLog.h>
#include <wtf/LockAlgorithm.h>

namespace WTF {

// This is mostly just a word-sized WTF::Lock. It supports basically everything that lock supports. But as
// a bonus, it atomically counts lock() calls and allows you to perform an optimistic read transaction by
// comparing the count before and after the transaction. If at the start of the transaction the lock is
// not held and the count remains the same throughout the transaction, then you know that nobody could
// have modified your data structure while you ran. You can even use this to optimistically read pointers
// that could become dangling under concurrent writes, if you just revalidate the count every time you're
// about to do something dangerous.
//
// This is largely inspired by StampedLock from Java:
// https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/CountingLock.html
//
// This is simplified a lot compared to StampedLock. Unlike StampedLock, it uses an exclusive lock as a
// fallback. There is no way to acquire a CountingLock for read. The only read access is via optimistic
// read transactions.
//
// CountingLock provides two ways of doing optimistic reads:
//
// - The easy way, where CountingLock does all of the fencing for you. That fencing is free on x86 but
//   somewhat expensive on ARM.
// - The hard way, where you do fencing yourself using Dependency. This allows you to be fenceless on both
//   x86 and ARM.
//
// The latter is important for us because some GC paths are known to be sensitive to fences on ARM.

class CountingLock final {
    WTF_MAKE_NONCOPYABLE(CountingLock);
    WTF_MAKE_FAST_ALLOCATED;

    typedef unsigned LockType;
    
    static constexpr LockType isHeldBit = 1;
    static constexpr LockType hasParkedBit = 2;
    static constexpr LockType mask = isHeldBit | hasParkedBit;
    static constexpr LockType shift = 2;
    static constexpr LockType countUnit = 4;
    
    struct LockHooks {
        static LockType lockHook(LockType value)
        {
            return value + countUnit;
        }
        
        static LockType unlockHook(LockType value) { return value; }
        static LockType parkHook(LockType value) { return value; }
        static LockType handoffHook(LockType value) { return value; }
    };
    
    typedef LockAlgorithm<LockType, isHeldBit, hasParkedBit, LockHooks> ExclusiveAlgorithm;
    
public:
    CountingLock() = default;
    
    bool tryLock()
    {
        return ExclusiveAlgorithm::tryLock(m_word);
    }

    void lock()
    {
        if (UNLIKELY(!ExclusiveAlgorithm::lockFast(m_word)))
            lockSlow();
    }
    
    void unlock()
    {
        if (UNLIKELY(!ExclusiveAlgorithm::unlockFast(m_word)))
            unlockSlow();
    }
    
    bool isHeld() const
    {
        return ExclusiveAlgorithm::isLocked(m_word);
    }
    
    bool isLocked() const
    {
        return isHeld();
    }
    
    // The only thing you're allowed to infer from this value is that if it's zero, then you didn't get
    // a real count.
    class Count {
    public:
        explicit operator bool() const { return !!m_value; }
        
        bool operator==(const Count& other) const { return m_value == other.m_value; }
        bool operator!=(const Count& other) const { return m_value != other.m_value; }
        
    private:
        friend class CountingLock;
        
        LockType m_value { 0 };
    };
    
    // Example of how to use this:
    //
    //     int read()
    //     {
    //         if (CountingLock::Count count = m_lock.tryOptimisticRead()) {
    //             int value = m_things;
    //             if (m_lock.validate(count))
    //                 return value; // success!
    //         }
    //         auto locker = holdLock(m_lock);
    //         int value = m_things;
    //         return value;
    //     }
    //
    // If tryOptimisitcRead() runs when the lock is not held, this thread will run a critical section
    // without ever writing to memory. However, on ARM, this requires fencing. We use a load-acquire for
    // tryOptimisticRead(). We have no choice but to use the more expensive `dmb ish` in validate(). If
    // you want to avoid that, you could try to use tryOptimisticFencelessRead().
    Count tryOptimisticRead()
    {
        LockType currentValue = m_word.load();
        // FIXME: We could eliminate this check, if we think it's OK to proceed with the optimistic read
        // path even after knowing that it must fail. That's probably good for perf since we expect
        // failure to be super rare. We would get rid of this check and instead of calling getCount below,
        // we would return currentValue ^ mask. If the lock state was empty to begin with, the result
        // would be a properly blessed count (both low bits set). If the lock state was anything else, we
        // would get an improperly blessed count that would not possibly succeed in validate. We could
        // actually do something like "return (currentValue | hasParkedBit) ^ isHeldBit", which would mean
        // that we allow parked-but-not-held-locks through.
        // https://bugs.webkit.org/show_bug.cgi?id=180394
        if (currentValue & isHeldBit)
            return Count();
        return getCount(currentValue);
    }
    
    bool validate(Count count)
    {
        WTF::loadLoadFence();
        LockType currentValue = m_word.loadRelaxed();
        return getCount(currentValue) == count;
    }
    
    // Example of how to use this:
    //
    //     int read()
    //     {
    //         return m_lock.doOptimizedRead(
    //             [&] () -> int {
    //                 int value = m_things;
    //                 return value;
    //             });
    //     }
    template<typename Func>
    auto doOptimizedRead(const Func& func)
    {
        Count count = tryOptimisticRead();
        if (count) {
            auto result = func();
            if (validate(count))
                return result;
        }
        lock();
        auto result = func();
        unlock();
        return result;
    }
    
    // Example of how to use this:
    //
    //     int read()
    //     {
    //         auto result = m_lock.tryOptimisticFencelessRead();
    //         if (CountingLock::Count count = result.value) {
    //             Dependency fenceBefore = Dependency::fence(result.input);
    //             auto* fencedThis = fenceBefore.consume(this);
    //             int value = fencedThis->m_things;
    //             if (m_lock.fencelessValidate(count, Dependency::fence(value)))
    //                 return value; // success!
    //         }
    //         auto locker = holdLock(m_lock);
    //         int value = m_things;
    //         return value;
    //     }
    //
    // Use this to create a read transaction using dependency chains only. You have to be careful to
    // thread the dependency input (the `input` field that the returns) through a Dependency, and then
    // thread that Dependency into every load (except for loads that are chasing pointers loaded from
    // loads that already uses that dependency). Then, to validate the read transaction, you have to pass
    // both the count and another Dependency that is based on whatever loads you used to produce the
    // output.
    //
    // On non-ARM platforms, the Dependency objects don't do anything except for Dependency::fence, which
    // is a load-load fence. The idiom above does the right thing on both ARM and TSO.
    //
    // WARNING: This can be hard to get right. Please only use this for very short critical sections that
    // are known to be sufficiently perf-critical to justify the risk.
    InputAndValue<LockType, Count> tryOptimisticFencelessRead()
    {
        LockType currentValue = m_word.loadRelaxed();
        if (currentValue & isHeldBit)
            return inputAndValue(currentValue, Count());
        return inputAndValue(currentValue, getCount(currentValue));
    }
    
    bool fencelessValidate(Count count, Dependency dependency)
    {
        LockType currentValue = dependency.consume(this)->m_word.loadRelaxed();
        return getCount(currentValue) == count;
    }
    
    template<typename OptimisticFunc, typename Func>
    auto doOptimizedFencelessRead(const OptimisticFunc& optimisticFunc, const Func& func)
    {
        auto count = tryOptimisticFencelessRead();
        if (count.value) {
            Dependency dependency = Dependency::fence(count.input);
            auto result = optimisticFunc(dependency, count.value);
            if (fencelessValidate(count.value, dependency))
                return result;
        }
        lock();
        auto result = func();
        unlock();
        return result;
    }
    
private:
    WTF_EXPORT_PRIVATE void lockSlow();
    WTF_EXPORT_PRIVATE void unlockSlow();
    
    Count getCount(LockType value)
    {
        Count result;
        result.m_value = value | mask;
        return result;
    }
    
    Atomic<LockType> m_word { 0 };
};

} // namespace WTF

using WTF::CountingLock;