/* * 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 <atomic> #include <cstdint> #include <cstring> #include <memory> #include <system_error> #include <folly/CPortability.h> #include <folly/IndexedMemPool.h> #include <folly/Likely.h> #include <folly/Portability.h> #include <folly/Traits.h> #include <folly/detail/StaticSingletonManager.h> #include <folly/lang/Aligned.h> #include <folly/lang/SafeAssert.h> #include <folly/synchronization/AtomicStruct.h> #include <folly/synchronization/SaturatingSemaphore.h> namespace folly { template < template <typename> class Atom = std::atomic, class BatonType = SaturatingSemaphore<true, Atom>> struct LifoSemImpl; /// LifoSem is a semaphore that wakes its waiters in a manner intended to /// maximize performance rather than fairness. It should be preferred /// to a mutex+condvar or POSIX sem_t solution when all of the waiters /// are equivalent. It is faster than a condvar or sem_t, and it has a /// shutdown state that might save you a lot of complexity when it comes /// time to shut down your work pipelines. LifoSem is larger than sem_t, /// but that is only because it uses padding and alignment to avoid /// false sharing. /// /// LifoSem allows multi-post and multi-tryWait, and provides a shutdown /// state that awakens all waiters. LifoSem is faster than sem_t because /// it performs exact wakeups, so it often requires fewer system calls. /// It provides all of the functionality of sem_t except for timed waiting. /// It is called LifoSem because its wakeup policy is approximately LIFO, /// rather than the usual FIFO. /// /// The core semaphore operations provided are: /// /// -- post() -- if there is a pending waiter, wake it up, otherwise /// increment the value of the semaphore. If the value of the semaphore /// is already 2^32-1, does nothing. Compare to sem_post(). /// /// -- post(n) -- equivalent to n calls to post(), but much more efficient. /// sem_t has no equivalent to this method. /// /// -- bool tryWait() -- if the semaphore's value is positive, decrements it /// and returns true, otherwise returns false. Compare to sem_trywait(). /// /// -- uint32_t tryWait(uint32_t n) -- attempts to decrement the semaphore's /// value by n, returning the amount by which it actually was decremented /// (a value from 0 to n inclusive). Not atomic. Equivalent to n calls /// to tryWait(). sem_t has no equivalent to this method. /// /// -- wait() -- waits until tryWait() can succeed. Compare to sem_wait(). /// /// -- timed wait variants - will wait until timeout. Note when these /// timeout, the current implementation takes a lock, blocking /// concurrent pushes and pops. (If timed wait calls are /// substantial, consider re-working this code to be lock-free). /// /// LifoSem also has the notion of a shutdown state, in which any calls /// that would block (or are already blocked) throw ShutdownSemError. /// Note the difference between a call to wait() and a call to wait() /// that might block. In the former case tryWait() would succeed, and no /// isShutdown() check is performed. In the latter case an exception is /// thrown. This behavior allows a LifoSem controlling work distribution /// to drain. If you want to immediately stop all waiting on shutdown, /// you can just check isShutdown() yourself (preferrably wrapped in /// an UNLIKELY). This fast-stop behavior is easy to add, but difficult /// to remove if you want the draining behavior, which is why we have /// chosen the former. /// /// All LifoSem operations except valueGuess() are guaranteed to be /// linearizable. LifoSem; /// The exception thrown when wait()ing on an isShutdown() LifoSem class FOLLY_EXPORT ShutdownSemError : public std::runtime_error { … }; namespace detail { // Internally, a LifoSem is either a value or a linked list of wait nodes. // This union is captured in the LifoSemHead type, which holds either a // value or an indexed pointer to the list. LifoSemHead itself is a value // type, the head is a mutable atomic box containing a LifoSemHead value. // Each wait node corresponds to exactly one waiter. Values can flow // through the semaphore either by going into and out of the head's value, // or by direct communication from a poster to a waiter. The former path // is taken when there are no pending waiters, the latter otherwise. The // general flow of a post is to try to increment the value or pop-and-post // a wait node. Either of those have the effect of conveying one semaphore // unit. Waiting is the opposite, either a decrement of the value or // push-and-wait of a wait node. The generic LifoSemBase abstracts the // actual mechanism by which a wait node's post->wait communication is // performed, which is why we have LifoSemRawNode and LifoSemNode. /// LifoSemRawNode is the actual pooled storage that backs LifoSemNode /// for user-specified Handoff types. This is done so that we can have /// a large static IndexedMemPool of nodes, instead of per-type pools template <template <typename> class Atom> struct LifoSemRawNode { … }; /// Handoff is a type not bigger than a void* that knows how to perform a /// single post() -> wait() communication. It must have a post() method. /// If it has a wait() method then LifoSemBase's wait() implementation /// will work out of the box, otherwise you will need to specialize /// LifoSemBase::wait accordingly. template <typename Handoff, template <typename> class Atom> struct LifoSemNode : public LifoSemRawNode<Atom> { … }; template <typename Handoff, template <typename> class Atom> struct LifoSemNodeRecycler { … }; /// LifoSemHead is a 64-bit struct that holds a 32-bit value, some state /// bits, and a sequence number used to avoid ABA problems in the lock-free /// management of the LifoSem's wait lists. The value can either hold /// an integral semaphore value (if there are no waiters) or a node index /// (see IndexedMemPool) for the head of a list of wait nodes class LifoSemHead { … }; /// LifoSemBase is the engine for several different types of LIFO /// semaphore. LifoSemBase handles storage of positive semaphore values /// and wait nodes, but the actual waiting and notification mechanism is /// up to the client. /// /// The Handoff type is responsible for arranging one wakeup notification. /// See LifoSemNode for more information on how to make your own. template <typename Handoff, template <typename> class Atom = std::atomic> struct LifoSemBase { … }; } // namespace detail template <template <typename> class Atom, class BatonType> struct LifoSemImpl : public detail::LifoSemBase<BatonType, Atom> { … }; } // namespace folly
Codebase Browser
folly