/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #pragma once #include <algorithm> #include <limits> #include <glog/logging.h> #include <folly/Portability.h> #include <folly/chrono/Hardware.h> #include <folly/detail/Futex.h> #include <folly/portability/Asm.h> #include <folly/portability/Unistd.h> namespace folly { namespace detail { /// A TurnSequencer allows threads to order their execution according to /// a monotonically increasing (with wraparound) "turn" value. The two /// operations provided are to wait for turn T, and to move to the next /// turn. Every thread that is waiting for T must have arrived before /// that turn is marked completed (for MPMCQueue only one thread waits /// for any particular turn, so this is trivially true). /// /// TurnSequencer's state_ holds 26 bits of the current turn (shifted /// left by 6), along with a 6 bit saturating value that records the /// maximum waiter minus the current turn. Wraparound of the turn space /// is expected and handled. This allows us to atomically adjust the /// number of outstanding waiters when we perform a FUTEX_WAKE operation. /// Compare this strategy to sem_t's separate num_waiters field, which /// isn't decremented until after the waiting thread gets scheduled, /// during which time more enqueues might have occurred and made pointless /// FUTEX_WAKE calls. /// /// TurnSequencer uses futex() directly. It is optimized for the /// case that the highest awaited turn is 32 or less higher than the /// current turn. We use the FUTEX_WAIT_BITSET variant, which lets /// us embed 32 separate wakeup channels in a single futex. See /// http://locklessinc.com/articles/futex_cheat_sheet for a description. /// /// We only need to keep exact track of the delta between the current /// turn and the maximum waiter for the 32 turns that follow the current /// one, because waiters at turn t+32 will be awoken at turn t. At that /// point they can then adjust the delta using the higher base. Since we /// need to encode waiter deltas of 0 to 32 inclusive, we use 6 bits. /// We actually store waiter deltas up to 63, since that might reduce /// the number of CAS operations a tiny bit. /// /// To avoid some futex() calls entirely, TurnSequencer uses an adaptive /// spin cutoff before waiting. The overheads (and convergence rate) /// of separately tracking the spin cutoff for each TurnSequencer would /// be prohibitive, so the actual storage is passed in as a parameter and /// updated atomically. This also lets the caller use different adaptive /// cutoffs for different operations (read versus write, for example). /// To avoid contention, the spin cutoff is only updated when requested /// by the caller. /// /// On x86 the latency of a spin loop varies dramatically across /// architectures due to changes in the PAUSE instruction. Skylake /// increases the latency by about a factor of 15 compared to previous /// architectures. To work around this, on x86 we measure spins using /// RDTSC rather than a loop counter. template <template <typename> class Atom> struct TurnSequencer { … }; } // namespace detail } // namespace folly
Codebase Browser
folly