blob: dcdc5290aead14b89725da4d347e001259e2764d [file] [log] [blame]
/*
* 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.
*/
#pragma once
#include <wtf/Atomics.h>
#include <wtf/ScopedLambda.h>
#include <wtf/TimeWithDynamicClockType.h>
namespace WTF {
class Thread;
class ParkingLot {
ParkingLot() = delete;
ParkingLot(const ParkingLot&) = delete;
public:
// ParkingLot will accept any kind of time and convert it internally, but this typedef tells
// you what kind of time ParkingLot would be able to use without conversions. It's sad that
// this is WallTime not MonotonicTime, but that's just how OS wait functions work. However,
// because ParkingLot evaluates whether it should wait by checking if your time has passed
// using whatever clock you used, specifying timeouts in MonotonicTime is semantically better.
// For example, if the user sets his computer's clock back during the time that you wanted to
// wait for one second, and you specified the timeout using the MonotonicTime, then ParkingLot
// will be smart enough to know that your one second has elapsed.
typedef WallTime Time;
// Parks the thread in a queue associated with the given address, which cannot be null. The
// parking only succeeds if the validation function returns true while the queue lock is held.
//
// If validation returns false, it will unlock the internal parking queue and then it will
// return a null ParkResult (wasUnparked = false, token = 0) without doing anything else.
//
// If validation returns true, it will enqueue the thread, unlock the parking queue lock, call
// the beforeSleep function, and then it will sleep so long as the thread continues to be on the
// queue and the timeout hasn't fired. Finally, this returns wasUnparked = true if we actually
// got unparked or wasUnparked = false if the timeout was hit. When wasUnparked = true, the
// token will contain whatever token was returned from the callback to unparkOne(), or 0 if the
// thread was unparked using unparkAll() or the form of unparkOne() that doesn't take a
// callback.
//
// Note that beforeSleep is called with no locks held, so it's OK to do pretty much anything so
// long as you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll()
// though. It's useful to use beforeSleep() to unlock some mutex in the implementation of
// Condition::wait().
struct ParkResult {
bool wasUnparked { false };
intptr_t token { 0 };
};
template<typename ValidationFunctor, typename BeforeSleepFunctor>
static ParkResult parkConditionally(
const void* address,
const ValidationFunctor& validation,
const BeforeSleepFunctor& beforeSleep,
const TimeWithDynamicClockType& timeout)
{
return parkConditionallyImpl(
address,
scopedLambdaRef<bool()>(validation),
scopedLambdaRef<void()>(beforeSleep),
timeout);
}
// Simple version of parkConditionally() that covers the most common case: you want to park
// indefinitely so long as the value at the given address hasn't changed.
template<typename T, typename U>
static ParkResult compareAndPark(const Atomic<T>* address, U expected)
{
return parkConditionally(
address,
[address, expected] () -> bool {
U value = address->load();
return value == expected;
},
[] () { },
Time::infinity());
}
// Unparking status given to you anytime you unparkOne().
struct UnparkResult {
// True if some thread was unparked.
bool didUnparkThread { false };
// True if there may be more threads on this address. This may be conservatively true.
bool mayHaveMoreThreads { false };
// This bit is randomly set to true indicating that it may be profitable to unlock the lock
// using a fair unlocking protocol. This is most useful when used in conjunction with
// unparkOne(address, callback).
bool timeToBeFair { false };
};
// Unparks one thread from the queue associated with the given address, which cannot be null.
// Returns true if there may still be other threads on that queue, or false if there definitely
// are no more threads on the queue.
WTF_EXPORT_PRIVATE static UnparkResult unparkOne(const void* address);
// This is an expert-mode version of unparkOne() that allows for really good thundering herd
// avoidance and eventual stochastic fairness in adaptive mutexes.
//
// Unparks one thread from the queue associated with the given address, and calls the given
// callback while the address is locked. Reports to the callback whether any thread got
// unparked, whether there may be any other threads still on the queue, and whether this may be
// a good time to do fair unlocking. The callback returns an intptr_t token, which is returned
// to the unparked thread via ParkResult::token.
//
// WTF::Lock and WTF::Condition both use this form of unparkOne() because it allows them to use
// the ParkingLot's internal queue lock to serialize some decision-making. For example, if
// UnparkResult::mayHaveMoreThreads is false inside the callback, then we know that at that
// moment nobody can add any threads to the queue because the queue lock is still held. Also,
// WTF::Lock uses the timeToBeFair and token mechanism to implement eventual fairness.
template<typename Callback>
static void unparkOne(const void* address, const Callback& callback)
{
unparkOneImpl(address, scopedLambdaRef<intptr_t(UnparkResult)>(callback));
}
WTF_EXPORT_PRIVATE static unsigned unparkCount(const void* address, unsigned count);
// Unparks every thread from the queue associated with the given address, which cannot be null.
WTF_EXPORT_PRIVATE static void unparkAll(const void* address);
// Locks the parking lot and walks all of the parked threads and the addresses they are waiting
// on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
// queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
// the queue for address A2 has T3 and T4, then you might see iteration orders like:
//
// A1,T1 A1,T2 A2,T3 A2,T4
// A2,T3 A2,T4 A1,T1 A1,T2
// A1,T1 A2,T3 A1,T2 A2,T4
// A1,T1 A2,T3 A2,T4 A1,T2
//
// As well as many other possible interleavings that all have T1 before T2 and T3 before T4 but are
// otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
// tests.
template<typename Func>
static void forEach(const Func& func)
{
forEachImpl(scopedLambdaRef<void(Thread&, const void*)>(func));
}
private:
WTF_EXPORT_PRIVATE static ParkResult parkConditionallyImpl(
const void* address,
const ScopedLambda<bool()>& validation,
const ScopedLambda<void()>& beforeSleep,
const TimeWithDynamicClockType& timeout);
WTF_EXPORT_PRIVATE static void unparkOneImpl(
const void* address, const ScopedLambda<intptr_t(UnparkResult)>& callback);
WTF_EXPORT_PRIVATE static void forEachImpl(const ScopedLambda<void(Thread&, const void*)>&);
};
} // namespace WTF
using WTF::ParkingLot;