TEST baton_test SOURCES BatonTest.cpp
TEST call_once_test SOURCES CallOnceTest.cpp
TEST lifo_sem_test SOURCES LifoSemTests.cpp
+ TEST rw_spin_lock_test SOURCES RWSpinLockTest.cpp
DIRECTORY system/test/
TEST memory_mapping_test SOURCES MemoryMappingTest.cpp
TEST portability_test SOURCES PortabilityTest.cpp
TEST producer_consumer_queue_test SLOW
SOURCES ProducerConsumerQueueTest.cpp
- TEST r_w_spin_lock_test SOURCES RWSpinLockTest.cpp
TEST random_test SOURCES RandomTest.cpp
TEST range_test SOURCES RangeTest.cpp
TEST safe_assert_test SOURCES SafeAssertTest.cpp
Random-inl.h \
Range.h \
Replaceable.h \
- RWSpinLock.h \
ScopeGuard.h \
SharedMutex.h \
Singleton.h \
synchronization/CallOnce.h \
synchronization/LifoSem.h \
synchronization/ParkingLot.h \
+ synchronization/RWSpinLock.h \
synchronization/SaturatingSemaphore.h \
synchronization/detail/AtomicUtils.h \
synchronization/detail/Sleeper.h \
* limitations under the License.
*/
-/*
- * N.B. You most likely do _not_ want to use RWSpinLock or any other
- * kind of spinlock. Use SharedMutex instead.
- *
- * In short, spinlocks in preemptive multi-tasking operating systems
- * have serious problems and fast mutexes like SharedMutex are almost
- * certainly the better choice, because letting the OS scheduler put a
- * thread to sleep is better for system responsiveness and throughput
- * than wasting a timeslice repeatedly querying a lock held by a
- * thread that's blocked, and you can't prevent userspace
- * programs blocking.
- *
- * Spinlocks in an operating system kernel make much more sense than
- * they do in userspace.
- *
- * -------------------------------------------------------------------
- *
- * Two Read-Write spin lock implementations.
- *
- * Ref: http://locklessinc.com/articles/locks
- *
- * Both locks here are faster than pthread_rwlock and have very low
- * overhead (usually 20-30ns). They don't use any system mutexes and
- * are very compact (4/8 bytes), so are suitable for per-instance
- * based locking, particularly when contention is not expected.
- *
- * For a spinlock, RWSpinLock is a reasonable choice. (See the note
- * about for why a spin lock is frequently a bad idea generally.)
- * RWSpinLock has minimal overhead, and comparable contention
- * performance when the number of competing threads is less than or
- * equal to the number of logical CPUs. Even as the number of
- * threads gets larger, RWSpinLock can still be very competitive in
- * READ, although it is slower on WRITE, and also inherently unfair
- * to writers.
- *
- * RWTicketSpinLock shows more balanced READ/WRITE performance. If
- * your application really needs a lot more threads, and a
- * higher-priority writer, prefer one of the RWTicketSpinLock locks.
- *
- * Caveats:
- *
- * RWTicketSpinLock locks can only be used with GCC on x86/x86-64
- * based systems.
- *
- * RWTicketSpinLock<32> only allows up to 2^8 - 1 concurrent
- * readers and writers.
- *
- * RWTicketSpinLock<64> only allows up to 2^16 - 1 concurrent
- * readers and writers.
- *
- * RWTicketSpinLock<..., true> (kFavorWriter = true, that is, strict
- * writer priority) is NOT reentrant, even for lock_shared().
- *
- * The lock will not grant any new shared (read) accesses while a thread
- * attempting to acquire the lock in write mode is blocked. (That is,
- * if the lock is held in shared mode by N threads, and a thread attempts
- * to acquire it in write mode, no one else can acquire it in shared mode
- * until these N threads release the lock and then the blocked thread
- * acquires and releases the exclusive lock.) This also applies for
- * attempts to reacquire the lock in shared mode by threads that already
- * hold it in shared mode, making the lock non-reentrant.
- *
- * RWSpinLock handles 2^30 - 1 concurrent readers.
- *
- * @author Xin Liu <xliux@fb.com>
- */
-
-#pragma once
-
-/*
-========================================================================
-Benchmark on (Intel(R) Xeon(R) CPU L5630 @ 2.13GHz) 8 cores(16 HTs)
-========================================================================
-
-------------------------------------------------------------------------------
-1. Single thread benchmark (read/write lock + unlock overhead)
-Benchmark Iters Total t t/iter iter/sec
--------------------------------------------------------------------------------
-* BM_RWSpinLockRead 100000 1.786 ms 17.86 ns 53.4M
-+30.5% BM_RWSpinLockWrite 100000 2.331 ms 23.31 ns 40.91M
-+85.7% BM_RWTicketSpinLock32Read 100000 3.317 ms 33.17 ns 28.75M
-+96.0% BM_RWTicketSpinLock32Write 100000 3.5 ms 35 ns 27.25M
-+85.6% BM_RWTicketSpinLock64Read 100000 3.315 ms 33.15 ns 28.77M
-+96.0% BM_RWTicketSpinLock64Write 100000 3.5 ms 35 ns 27.25M
-+85.7% BM_RWTicketSpinLock32FavorWriterRead 100000 3.317 ms 33.17 ns 28.75M
-+29.7% BM_RWTicketSpinLock32FavorWriterWrite 100000 2.316 ms 23.16 ns 41.18M
-+85.3% BM_RWTicketSpinLock64FavorWriterRead 100000 3.309 ms 33.09 ns 28.82M
-+30.2% BM_RWTicketSpinLock64FavorWriterWrite 100000 2.325 ms 23.25 ns 41.02M
-+ 175% BM_PThreadRWMutexRead 100000 4.917 ms 49.17 ns 19.4M
-+ 166% BM_PThreadRWMutexWrite 100000 4.757 ms 47.57 ns 20.05M
-
-------------------------------------------------------------------------------
-2. Contention Benchmark 90% read 10% write
-Benchmark hits average min max sigma
-------------------------------------------------------------------------------
----------- 8 threads ------------
-RWSpinLock Write 142666 220ns 78ns 40.8us 269ns
-RWSpinLock Read 1282297 222ns 80ns 37.7us 248ns
-RWTicketSpinLock Write 85692 209ns 71ns 17.9us 252ns
-RWTicketSpinLock Read 769571 215ns 78ns 33.4us 251ns
-pthread_rwlock_t Write 84248 2.48us 99ns 269us 8.19us
-pthread_rwlock_t Read 761646 933ns 101ns 374us 3.25us
-
----------- 16 threads ------------
-RWSpinLock Write 124236 237ns 78ns 261us 801ns
-RWSpinLock Read 1115807 236ns 78ns 2.27ms 2.17us
-RWTicketSpinLock Write 81781 231ns 71ns 31.4us 351ns
-RWTicketSpinLock Read 734518 238ns 78ns 73.6us 379ns
-pthread_rwlock_t Write 83363 7.12us 99ns 785us 28.1us
-pthread_rwlock_t Read 754978 2.18us 101ns 1.02ms 14.3us
-
----------- 50 threads ------------
-RWSpinLock Write 131142 1.37us 82ns 7.53ms 68.2us
-RWSpinLock Read 1181240 262ns 78ns 6.62ms 12.7us
-RWTicketSpinLock Write 83045 397ns 73ns 7.01ms 31.5us
-RWTicketSpinLock Read 744133 386ns 78ns 11ms 31.4us
-pthread_rwlock_t Write 80849 112us 103ns 4.52ms 263us
-pthread_rwlock_t Read 728698 24us 101ns 7.28ms 194us
-
-*/
-
-#include <folly/Portability.h>
-#include <folly/portability/Asm.h>
-
-#if defined(__GNUC__) && (defined(__i386) || FOLLY_X64 || defined(ARCH_K8))
-#define RW_SPINLOCK_USE_X86_INTRINSIC_
-#include <x86intrin.h>
-#elif defined(_MSC_VER) && defined(FOLLY_X64)
-#define RW_SPINLOCK_USE_X86_INTRINSIC_
-#elif FOLLY_AARCH64
-#define RW_SPINLOCK_USE_X86_INTRINSIC_
-#else
-#undef RW_SPINLOCK_USE_X86_INTRINSIC_
-#endif
-
-// iOS doesn't define _mm_cvtsi64_si128 and friends
-#if (FOLLY_SSE >= 2) && !FOLLY_MOBILE && FOLLY_X64
-#define RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
-#else
-#undef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
-#endif
-
-#include <algorithm>
-#include <atomic>
-#include <string>
-#include <thread>
-
-#include <glog/logging.h>
-
-#include <folly/Likely.h>
-
-namespace folly {
-
-/*
- * A simple, small (4-bytes), but unfair rwlock. Use it when you want
- * a nice writer and don't expect a lot of write/read contention, or
- * when you need small rwlocks since you are creating a large number
- * of them.
- *
- * Note that the unfairness here is extreme: if the lock is
- * continually accessed for read, writers will never get a chance. If
- * the lock can be that highly contended this class is probably not an
- * ideal choice anyway.
- *
- * It currently implements most of the Lockable, SharedLockable and
- * UpgradeLockable concepts except the TimedLockable related locking/unlocking
- * interfaces.
- */
-class RWSpinLock {
- enum : int32_t { READER = 4, UPGRADED = 2, WRITER = 1 };
- public:
- constexpr RWSpinLock() : bits_(0) {}
-
- RWSpinLock(RWSpinLock const&) = delete;
- RWSpinLock& operator=(RWSpinLock const&) = delete;
-
- // Lockable Concept
- void lock() {
- uint_fast32_t count = 0;
- while (!LIKELY(try_lock())) {
- if (++count > 1000) {
- std::this_thread::yield();
- }
- }
- }
-
- // Writer is responsible for clearing up both the UPGRADED and WRITER bits.
- void unlock() {
- static_assert(READER > WRITER + UPGRADED, "wrong bits!");
- bits_.fetch_and(~(WRITER | UPGRADED), std::memory_order_release);
- }
-
- // SharedLockable Concept
- void lock_shared() {
- uint_fast32_t count = 0;
- while (!LIKELY(try_lock_shared())) {
- if (++count > 1000) {
- std::this_thread::yield();
- }
- }
- }
-
- void unlock_shared() {
- bits_.fetch_add(-READER, std::memory_order_release);
- }
-
- // Downgrade the lock from writer status to reader status.
- void unlock_and_lock_shared() {
- bits_.fetch_add(READER, std::memory_order_acquire);
- unlock();
- }
-
- // UpgradeLockable Concept
- void lock_upgrade() {
- uint_fast32_t count = 0;
- while (!try_lock_upgrade()) {
- if (++count > 1000) {
- std::this_thread::yield();
- }
- }
- }
-
- void unlock_upgrade() {
- bits_.fetch_add(-UPGRADED, std::memory_order_acq_rel);
- }
-
- // unlock upgrade and try to acquire write lock
- void unlock_upgrade_and_lock() {
- int64_t count = 0;
- while (!try_unlock_upgrade_and_lock()) {
- if (++count > 1000) {
- std::this_thread::yield();
- }
- }
- }
-
- // unlock upgrade and read lock atomically
- void unlock_upgrade_and_lock_shared() {
- bits_.fetch_add(READER - UPGRADED, std::memory_order_acq_rel);
- }
-
- // write unlock and upgrade lock atomically
- void unlock_and_lock_upgrade() {
- // need to do it in two steps here -- as the UPGRADED bit might be OR-ed at
- // the same time when other threads are trying do try_lock_upgrade().
- bits_.fetch_or(UPGRADED, std::memory_order_acquire);
- bits_.fetch_add(-WRITER, std::memory_order_release);
- }
-
-
- // Attempt to acquire writer permission. Return false if we didn't get it.
- bool try_lock() {
- int32_t expect = 0;
- return bits_.compare_exchange_strong(expect, WRITER,
- std::memory_order_acq_rel);
- }
-
- // Try to get reader permission on the lock. This can fail if we
- // find out someone is a writer or upgrader.
- // Setting the UPGRADED bit would allow a writer-to-be to indicate
- // its intention to write and block any new readers while waiting
- // for existing readers to finish and release their read locks. This
- // helps avoid starving writers (promoted from upgraders).
- bool try_lock_shared() {
- // fetch_add is considerably (100%) faster than compare_exchange,
- // so here we are optimizing for the common (lock success) case.
- int32_t value = bits_.fetch_add(READER, std::memory_order_acquire);
- if (UNLIKELY(value & (WRITER|UPGRADED))) {
- bits_.fetch_add(-READER, std::memory_order_release);
- return false;
- }
- return true;
- }
-
- // try to unlock upgrade and write lock atomically
- bool try_unlock_upgrade_and_lock() {
- int32_t expect = UPGRADED;
- return bits_.compare_exchange_strong(expect, WRITER,
- std::memory_order_acq_rel);
- }
-
- // try to acquire an upgradable lock.
- bool try_lock_upgrade() {
- int32_t value = bits_.fetch_or(UPGRADED, std::memory_order_acquire);
-
- // Note: when failed, we cannot flip the UPGRADED bit back,
- // as in this case there is either another upgrade lock or a write lock.
- // If it's a write lock, the bit will get cleared up when that lock's done
- // with unlock().
- return ((value & (UPGRADED | WRITER)) == 0);
- }
-
- // mainly for debugging purposes.
- int32_t bits() const { return bits_.load(std::memory_order_acquire); }
-
- class ReadHolder;
- class UpgradedHolder;
- class WriteHolder;
-
- class ReadHolder {
- public:
- explicit ReadHolder(RWSpinLock* lock) : lock_(lock) {
- if (lock_) {
- lock_->lock_shared();
- }
- }
-
- explicit ReadHolder(RWSpinLock& lock) : lock_(&lock) {
- lock_->lock_shared();
- }
-
- ReadHolder(ReadHolder&& other) noexcept : lock_(other.lock_) {
- other.lock_ = nullptr;
- }
-
- // down-grade
- explicit ReadHolder(UpgradedHolder&& upgraded) : lock_(upgraded.lock_) {
- upgraded.lock_ = nullptr;
- if (lock_) {
- lock_->unlock_upgrade_and_lock_shared();
- }
- }
-
- explicit ReadHolder(WriteHolder&& writer) : lock_(writer.lock_) {
- writer.lock_ = nullptr;
- if (lock_) {
- lock_->unlock_and_lock_shared();
- }
- }
-
- ReadHolder& operator=(ReadHolder&& other) {
- using std::swap;
- swap(lock_, other.lock_);
- return *this;
- }
-
- ReadHolder(const ReadHolder& other) = delete;
- ReadHolder& operator=(const ReadHolder& other) = delete;
-
- ~ReadHolder() {
- if (lock_) {
- lock_->unlock_shared();
- }
- }
-
- void reset(RWSpinLock* lock = nullptr) {
- if (lock == lock_) {
- return;
- }
- if (lock_) {
- lock_->unlock_shared();
- }
- lock_ = lock;
- if (lock_) {
- lock_->lock_shared();
- }
- }
-
- void swap(ReadHolder* other) {
- std::swap(lock_, other->lock_);
- }
-
- private:
- friend class UpgradedHolder;
- friend class WriteHolder;
- RWSpinLock* lock_;
- };
-
- class UpgradedHolder {
- public:
- explicit UpgradedHolder(RWSpinLock* lock) : lock_(lock) {
- if (lock_) {
- lock_->lock_upgrade();
- }
- }
-
- explicit UpgradedHolder(RWSpinLock& lock) : lock_(&lock) {
- lock_->lock_upgrade();
- }
-
- explicit UpgradedHolder(WriteHolder&& writer) {
- lock_ = writer.lock_;
- writer.lock_ = nullptr;
- if (lock_) {
- lock_->unlock_and_lock_upgrade();
- }
- }
-
- UpgradedHolder(UpgradedHolder&& other) noexcept : lock_(other.lock_) {
- other.lock_ = nullptr;
- }
-
- UpgradedHolder& operator =(UpgradedHolder&& other) {
- using std::swap;
- swap(lock_, other.lock_);
- return *this;
- }
-
- UpgradedHolder(const UpgradedHolder& other) = delete;
- UpgradedHolder& operator =(const UpgradedHolder& other) = delete;
-
- ~UpgradedHolder() {
- if (lock_) {
- lock_->unlock_upgrade();
- }
- }
-
- void reset(RWSpinLock* lock = nullptr) {
- if (lock == lock_) {
- return;
- }
- if (lock_) {
- lock_->unlock_upgrade();
- }
- lock_ = lock;
- if (lock_) {
- lock_->lock_upgrade();
- }
- }
-
- void swap(UpgradedHolder* other) {
- using std::swap;
- swap(lock_, other->lock_);
- }
-
- private:
- friend class WriteHolder;
- friend class ReadHolder;
- RWSpinLock* lock_;
- };
-
- class WriteHolder {
- public:
- explicit WriteHolder(RWSpinLock* lock) : lock_(lock) {
- if (lock_) {
- lock_->lock();
- }
- }
-
- explicit WriteHolder(RWSpinLock& lock) : lock_(&lock) {
- lock_->lock();
- }
-
- // promoted from an upgrade lock holder
- explicit WriteHolder(UpgradedHolder&& upgraded) {
- lock_ = upgraded.lock_;
- upgraded.lock_ = nullptr;
- if (lock_) {
- lock_->unlock_upgrade_and_lock();
- }
- }
-
- WriteHolder(WriteHolder&& other) noexcept : lock_(other.lock_) {
- other.lock_ = nullptr;
- }
-
- WriteHolder& operator =(WriteHolder&& other) {
- using std::swap;
- swap(lock_, other.lock_);
- return *this;
- }
-
- WriteHolder(const WriteHolder& other) = delete;
- WriteHolder& operator =(const WriteHolder& other) = delete;
-
- ~WriteHolder() {
- if (lock_) {
- lock_->unlock();
- }
- }
-
- void reset(RWSpinLock* lock = nullptr) {
- if (lock == lock_) {
- return;
- }
- if (lock_) {
- lock_->unlock();
- }
- lock_ = lock;
- if (lock_) {
- lock_->lock();
- }
- }
-
- void swap(WriteHolder* other) {
- using std::swap;
- swap(lock_, other->lock_);
- }
-
- private:
- friend class ReadHolder;
- friend class UpgradedHolder;
- RWSpinLock* lock_;
- };
-
- private:
- std::atomic<int32_t> bits_;
-};
-
-
-#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
-// A more balanced Read-Write spin lock implemented based on GCC intrinsics.
-
-namespace detail {
-template <size_t kBitWidth> struct RWTicketIntTrait {
- static_assert(kBitWidth == 32 || kBitWidth == 64,
- "bit width has to be either 32 or 64 ");
-};
-
-template <>
-struct RWTicketIntTrait<64> {
- typedef uint64_t FullInt;
- typedef uint32_t HalfInt;
- typedef uint16_t QuarterInt;
-
-#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
- static __m128i make128(const uint16_t v[4]) {
- return _mm_set_epi16(0, 0, 0, 0,
- short(v[3]), short(v[2]), short(v[1]), short(v[0]));
- }
- static inline __m128i fromInteger(uint64_t from) {
- return _mm_cvtsi64_si128(int64_t(from));
- }
- static inline uint64_t toInteger(__m128i in) {
- return uint64_t(_mm_cvtsi128_si64(in));
- }
- static inline uint64_t addParallel(__m128i in, __m128i kDelta) {
- return toInteger(_mm_add_epi16(in, kDelta));
- }
-#endif
-};
-
-template <>
-struct RWTicketIntTrait<32> {
- typedef uint32_t FullInt;
- typedef uint16_t HalfInt;
- typedef uint8_t QuarterInt;
-
-#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
- static __m128i make128(const uint8_t v[4]) {
- return _mm_set_epi8(
- 0, 0, 0, 0,
- 0, 0, 0, 0,
- 0, 0, 0, 0,
- char(v[3]), char(v[2]), char(v[1]), char(v[0]));
- }
- static inline __m128i fromInteger(uint32_t from) {
- return _mm_cvtsi32_si128(int32_t(from));
- }
- static inline uint32_t toInteger(__m128i in) {
- return uint32_t(_mm_cvtsi128_si32(in));
- }
- static inline uint32_t addParallel(__m128i in, __m128i kDelta) {
- return toInteger(_mm_add_epi8(in, kDelta));
- }
-#endif
-};
-} // namespace detail
-
-template <size_t kBitWidth, bool kFavorWriter = false>
-class RWTicketSpinLockT {
- typedef detail::RWTicketIntTrait<kBitWidth> IntTraitType;
- typedef typename detail::RWTicketIntTrait<kBitWidth>::FullInt FullInt;
- typedef typename detail::RWTicketIntTrait<kBitWidth>::HalfInt HalfInt;
- typedef typename detail::RWTicketIntTrait<kBitWidth>::QuarterInt
- QuarterInt;
-
- union RWTicket {
- constexpr RWTicket() : whole(0) {}
- FullInt whole;
- HalfInt readWrite;
- __extension__ struct {
- QuarterInt write;
- QuarterInt read;
- QuarterInt users;
- };
- } ticket;
-
- private: // Some x64-specific utilities for atomic access to ticket.
- template <class T> static T load_acquire(T* addr) {
- T t = *addr; // acquire barrier
- asm_volatile_memory();
- return t;
- }
-
- template <class T>
- static void store_release(T* addr, T v) {
- asm_volatile_memory();
- *addr = v; // release barrier
- }
-
- public:
-
- constexpr RWTicketSpinLockT() {}
-
- RWTicketSpinLockT(RWTicketSpinLockT const&) = delete;
- RWTicketSpinLockT& operator=(RWTicketSpinLockT const&) = delete;
-
- void lock() {
- if (kFavorWriter) {
- writeLockAggressive();
- } else {
- writeLockNice();
- }
- }
-
- /*
- * Both try_lock and try_lock_shared diverge in our implementation from the
- * lock algorithm described in the link above.
- *
- * In the read case, it is undesirable that the readers could wait
- * for another reader (before increasing ticket.read in the other
- * implementation). Our approach gives up on
- * first-come-first-serve, but our benchmarks showed improve
- * performance for both readers and writers under heavily contended
- * cases, particularly when the number of threads exceeds the number
- * of logical CPUs.
- *
- * We have writeLockAggressive() using the original implementation
- * for a writer, which gives some advantage to the writer over the
- * readers---for that path it is guaranteed that the writer will
- * acquire the lock after all the existing readers exit.
- */
- bool try_lock() {
- RWTicket t;
- FullInt old = t.whole = load_acquire(&ticket.whole);
- if (t.users != t.write) {
- return false;
- }
- ++t.users;
- return __sync_bool_compare_and_swap(&ticket.whole, old, t.whole);
- }
-
- /*
- * Call this if you want to prioritize writer to avoid starvation.
- * Unlike writeLockNice, immediately acquires the write lock when
- * the existing readers (arriving before the writer) finish their
- * turns.
- */
- void writeLockAggressive() {
- // std::this_thread::yield() is needed here to avoid a pathology if the number
- // of threads attempting concurrent writes is >= the number of real
- // cores allocated to this process. This is less likely than the
- // corresponding situation in lock_shared(), but we still want to
- // avoid it
- uint_fast32_t count = 0;
- QuarterInt val = __sync_fetch_and_add(&ticket.users, 1);
- while (val != load_acquire(&ticket.write)) {
- asm_volatile_pause();
- if (UNLIKELY(++count > 1000)) {
- std::this_thread::yield();
- }
- }
- }
-
- // Call this when the writer should be nicer to the readers.
- void writeLockNice() {
- // Here it doesn't cpu-relax the writer.
- //
- // This is because usually we have many more readers than the
- // writers, so the writer has less chance to get the lock when
- // there are a lot of competing readers. The aggressive spinning
- // can help to avoid starving writers.
- //
- // We don't worry about std::this_thread::yield() here because the caller
- // has already explicitly abandoned fairness.
- while (!try_lock()) {}
- }
-
- // Atomically unlock the write-lock from writer and acquire the read-lock.
- void unlock_and_lock_shared() {
- QuarterInt val = __sync_fetch_and_add(&ticket.read, 1);
- }
-
- // Release writer permission on the lock.
- void unlock() {
- RWTicket t;
- t.whole = load_acquire(&ticket.whole);
-
-#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
- FullInt old = t.whole;
- // SSE2 can reduce the lock and unlock overhead by 10%
- static const QuarterInt kDeltaBuf[4] = { 1, 1, 0, 0 }; // write/read/user
- static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
- __m128i m = IntTraitType::fromInteger(old);
- t.whole = IntTraitType::addParallel(m, kDelta);
-#else
- ++t.read;
- ++t.write;
-#endif
- store_release(&ticket.readWrite, t.readWrite);
- }
-
- void lock_shared() {
- // std::this_thread::yield() is important here because we can't grab the
- // shared lock if there is a pending writeLockAggressive, so we
- // need to let threads that already have a shared lock complete
- uint_fast32_t count = 0;
- while (!LIKELY(try_lock_shared())) {
- asm_volatile_pause();
- if (UNLIKELY((++count & 1023) == 0)) {
- std::this_thread::yield();
- }
- }
- }
-
- bool try_lock_shared() {
- RWTicket t, old;
- old.whole = t.whole = load_acquire(&ticket.whole);
- old.users = old.read;
-#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
- // SSE2 may reduce the total lock and unlock overhead by 10%
- static const QuarterInt kDeltaBuf[4] = { 0, 1, 1, 0 }; // write/read/user
- static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
- __m128i m = IntTraitType::fromInteger(old.whole);
- t.whole = IntTraitType::addParallel(m, kDelta);
-#else
- ++t.read;
- ++t.users;
-#endif
- return __sync_bool_compare_and_swap(&ticket.whole, old.whole, t.whole);
- }
-
- void unlock_shared() {
- __sync_fetch_and_add(&ticket.write, 1);
- }
-
- class WriteHolder;
-
- typedef RWTicketSpinLockT<kBitWidth, kFavorWriter> RWSpinLock;
- class ReadHolder {
- public:
- ReadHolder(ReadHolder const&) = delete;
- ReadHolder& operator=(ReadHolder const&) = delete;
-
- explicit ReadHolder(RWSpinLock* lock) : lock_(lock) {
- if (lock_) {
- lock_->lock_shared();
- }
- }
-
- explicit ReadHolder(RWSpinLock &lock) : lock_ (&lock) {
- if (lock_) {
- lock_->lock_shared();
- }
- }
-
- // atomically unlock the write-lock from writer and acquire the read-lock
- explicit ReadHolder(WriteHolder *writer) : lock_(nullptr) {
- std::swap(this->lock_, writer->lock_);
- if (lock_) {
- lock_->unlock_and_lock_shared();
- }
- }
-
- ~ReadHolder() {
- if (lock_) {
- lock_->unlock_shared();
- }
- }
-
- void reset(RWSpinLock *lock = nullptr) {
- if (lock_) {
- lock_->unlock_shared();
- }
- lock_ = lock;
- if (lock_) {
- lock_->lock_shared();
- }
- }
-
- void swap(ReadHolder *other) {
- std::swap(this->lock_, other->lock_);
- }
-
- private:
- RWSpinLock *lock_;
- };
-
- class WriteHolder {
- public:
- WriteHolder(WriteHolder const&) = delete;
- WriteHolder& operator=(WriteHolder const&) = delete;
-
- explicit WriteHolder(RWSpinLock* lock) : lock_(lock) {
- if (lock_) {
- lock_->lock();
- }
- }
- explicit WriteHolder(RWSpinLock &lock) : lock_ (&lock) {
- if (lock_) {
- lock_->lock();
- }
- }
-
- ~WriteHolder() {
- if (lock_) {
- lock_->unlock();
- }
- }
-
- void reset(RWSpinLock *lock = nullptr) {
- if (lock == lock_) {
- return;
- }
- if (lock_) {
- lock_->unlock();
- }
- lock_ = lock;
- if (lock_) {
- lock_->lock();
- }
- }
-
- void swap(WriteHolder *other) {
- std::swap(this->lock_, other->lock_);
- }
-
- private:
- friend class ReadHolder;
- RWSpinLock *lock_;
- };
-};
-
-typedef RWTicketSpinLockT<32> RWTicketSpinLock32;
-typedef RWTicketSpinLockT<64> RWTicketSpinLock64;
-
-#endif // RW_SPINLOCK_USE_X86_INTRINSIC_
-
-} // namespace folly
-
-#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
-#undef RW_SPINLOCK_USE_X86_INTRINSIC_
-#endif
+#include <folly/synchronization/RWSpinLock.h> // @shim
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
// SingletonVault - a library to manage the creation and destruction
// of interdependent singletons.
//
#include <folly/Exception.h>
#include <folly/Executor.h>
#include <folly/Memory.h>
-#include <folly/RWSpinLock.h>
#include <folly/Synchronized.h>
#include <folly/detail/StaticSingletonManager.h>
#include <folly/experimental/ReadMostlySharedPtr.h>
#include <folly/hash/Hash.h>
#include <folly/synchronization/Baton.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <algorithm>
#include <atomic>
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
#pragma once
#include <folly/Executor.h>
#include <folly/Memory.h>
-#include <folly/RWSpinLock.h>
#include <folly/executors/GlobalThreadPoolList.h>
#include <folly/executors/task_queue/LifoSemMPMCQueue.h>
#include <folly/executors/thread_factory/NamedThreadFactory.h>
#include <folly/io/async/Request.h>
#include <folly/synchronization/Baton.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <algorithm>
#include <mutex>
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
#include <folly/experimental/exception_tracer/ExceptionCounterLib.h>
#include <iosfwd>
#include <unordered_map>
-#include <folly/RWSpinLock.h>
#include <folly/Range.h>
#include <folly/Synchronized.h>
#include <folly/ThreadLocal.h>
#include <folly/hash/SpookyHashV2.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <folly/experimental/exception_tracer/ExceptionTracerLib.h>
#include <folly/experimental/exception_tracer/StackTrace.h>
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <functional>
#include <string>
-#include <folly/RWSpinLock.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <folly/io/async/AsyncServerSocket.h>
--- /dev/null
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * 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.
+ */
+/*
+ * N.B. You most likely do _not_ want to use RWSpinLock or any other
+ * kind of spinlock. Use SharedMutex instead.
+ *
+ * In short, spinlocks in preemptive multi-tasking operating systems
+ * have serious problems and fast mutexes like SharedMutex are almost
+ * certainly the better choice, because letting the OS scheduler put a
+ * thread to sleep is better for system responsiveness and throughput
+ * than wasting a timeslice repeatedly querying a lock held by a
+ * thread that's blocked, and you can't prevent userspace
+ * programs blocking.
+ *
+ * Spinlocks in an operating system kernel make much more sense than
+ * they do in userspace.
+ *
+ * -------------------------------------------------------------------
+ *
+ * Two Read-Write spin lock implementations.
+ *
+ * Ref: http://locklessinc.com/articles/locks
+ *
+ * Both locks here are faster than pthread_rwlock and have very low
+ * overhead (usually 20-30ns). They don't use any system mutexes and
+ * are very compact (4/8 bytes), so are suitable for per-instance
+ * based locking, particularly when contention is not expected.
+ *
+ * For a spinlock, RWSpinLock is a reasonable choice. (See the note
+ * about for why a spin lock is frequently a bad idea generally.)
+ * RWSpinLock has minimal overhead, and comparable contention
+ * performance when the number of competing threads is less than or
+ * equal to the number of logical CPUs. Even as the number of
+ * threads gets larger, RWSpinLock can still be very competitive in
+ * READ, although it is slower on WRITE, and also inherently unfair
+ * to writers.
+ *
+ * RWTicketSpinLock shows more balanced READ/WRITE performance. If
+ * your application really needs a lot more threads, and a
+ * higher-priority writer, prefer one of the RWTicketSpinLock locks.
+ *
+ * Caveats:
+ *
+ * RWTicketSpinLock locks can only be used with GCC on x86/x86-64
+ * based systems.
+ *
+ * RWTicketSpinLock<32> only allows up to 2^8 - 1 concurrent
+ * readers and writers.
+ *
+ * RWTicketSpinLock<64> only allows up to 2^16 - 1 concurrent
+ * readers and writers.
+ *
+ * RWTicketSpinLock<..., true> (kFavorWriter = true, that is, strict
+ * writer priority) is NOT reentrant, even for lock_shared().
+ *
+ * The lock will not grant any new shared (read) accesses while a thread
+ * attempting to acquire the lock in write mode is blocked. (That is,
+ * if the lock is held in shared mode by N threads, and a thread attempts
+ * to acquire it in write mode, no one else can acquire it in shared mode
+ * until these N threads release the lock and then the blocked thread
+ * acquires and releases the exclusive lock.) This also applies for
+ * attempts to reacquire the lock in shared mode by threads that already
+ * hold it in shared mode, making the lock non-reentrant.
+ *
+ * RWSpinLock handles 2^30 - 1 concurrent readers.
+ *
+ * @author Xin Liu <xliux@fb.com>
+ */
+
+#pragma once
+
+/*
+========================================================================
+Benchmark on (Intel(R) Xeon(R) CPU L5630 @ 2.13GHz) 8 cores(16 HTs)
+========================================================================
+
+------------------------------------------------------------------------------
+1. Single thread benchmark (read/write lock + unlock overhead)
+Benchmark Iters Total t t/iter iter/sec
+-------------------------------------------------------------------------------
+* BM_RWSpinLockRead 100000 1.786 ms 17.86 ns 53.4M
++30.5% BM_RWSpinLockWrite 100000 2.331 ms 23.31 ns 40.91M
++85.7% BM_RWTicketSpinLock32Read 100000 3.317 ms 33.17 ns 28.75M
++96.0% BM_RWTicketSpinLock32Write 100000 3.5 ms 35 ns 27.25M
++85.6% BM_RWTicketSpinLock64Read 100000 3.315 ms 33.15 ns 28.77M
++96.0% BM_RWTicketSpinLock64Write 100000 3.5 ms 35 ns 27.25M
++85.7% BM_RWTicketSpinLock32FavorWriterRead 100000 3.317 ms 33.17 ns 28.75M
++29.7% BM_RWTicketSpinLock32FavorWriterWrite 100000 2.316 ms 23.16 ns 41.18M
++85.3% BM_RWTicketSpinLock64FavorWriterRead 100000 3.309 ms 33.09 ns 28.82M
++30.2% BM_RWTicketSpinLock64FavorWriterWrite 100000 2.325 ms 23.25 ns 41.02M
++ 175% BM_PThreadRWMutexRead 100000 4.917 ms 49.17 ns 19.4M
++ 166% BM_PThreadRWMutexWrite 100000 4.757 ms 47.57 ns 20.05M
+
+------------------------------------------------------------------------------
+2. Contention Benchmark 90% read 10% write
+Benchmark hits average min max sigma
+------------------------------------------------------------------------------
+---------- 8 threads ------------
+RWSpinLock Write 142666 220ns 78ns 40.8us 269ns
+RWSpinLock Read 1282297 222ns 80ns 37.7us 248ns
+RWTicketSpinLock Write 85692 209ns 71ns 17.9us 252ns
+RWTicketSpinLock Read 769571 215ns 78ns 33.4us 251ns
+pthread_rwlock_t Write 84248 2.48us 99ns 269us 8.19us
+pthread_rwlock_t Read 761646 933ns 101ns 374us 3.25us
+
+---------- 16 threads ------------
+RWSpinLock Write 124236 237ns 78ns 261us 801ns
+RWSpinLock Read 1115807 236ns 78ns 2.27ms 2.17us
+RWTicketSpinLock Write 81781 231ns 71ns 31.4us 351ns
+RWTicketSpinLock Read 734518 238ns 78ns 73.6us 379ns
+pthread_rwlock_t Write 83363 7.12us 99ns 785us 28.1us
+pthread_rwlock_t Read 754978 2.18us 101ns 1.02ms 14.3us
+
+---------- 50 threads ------------
+RWSpinLock Write 131142 1.37us 82ns 7.53ms 68.2us
+RWSpinLock Read 1181240 262ns 78ns 6.62ms 12.7us
+RWTicketSpinLock Write 83045 397ns 73ns 7.01ms 31.5us
+RWTicketSpinLock Read 744133 386ns 78ns 11ms 31.4us
+pthread_rwlock_t Write 80849 112us 103ns 4.52ms 263us
+pthread_rwlock_t Read 728698 24us 101ns 7.28ms 194us
+
+*/
+
+#include <folly/Portability.h>
+#include <folly/portability/Asm.h>
+
+#if defined(__GNUC__) && (defined(__i386) || FOLLY_X64 || defined(ARCH_K8))
+#define RW_SPINLOCK_USE_X86_INTRINSIC_
+#include <x86intrin.h>
+#elif defined(_MSC_VER) && defined(FOLLY_X64)
+#define RW_SPINLOCK_USE_X86_INTRINSIC_
+#elif FOLLY_AARCH64
+#define RW_SPINLOCK_USE_X86_INTRINSIC_
+#else
+#undef RW_SPINLOCK_USE_X86_INTRINSIC_
+#endif
+
+// iOS doesn't define _mm_cvtsi64_si128 and friends
+#if (FOLLY_SSE >= 2) && !FOLLY_MOBILE && FOLLY_X64
+#define RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+#else
+#undef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+#endif
+
+#include <algorithm>
+#include <atomic>
+#include <string>
+#include <thread>
+
+#include <glog/logging.h>
+
+#include <folly/Likely.h>
+
+namespace folly {
+
+/*
+ * A simple, small (4-bytes), but unfair rwlock. Use it when you want
+ * a nice writer and don't expect a lot of write/read contention, or
+ * when you need small rwlocks since you are creating a large number
+ * of them.
+ *
+ * Note that the unfairness here is extreme: if the lock is
+ * continually accessed for read, writers will never get a chance. If
+ * the lock can be that highly contended this class is probably not an
+ * ideal choice anyway.
+ *
+ * It currently implements most of the Lockable, SharedLockable and
+ * UpgradeLockable concepts except the TimedLockable related locking/unlocking
+ * interfaces.
+ */
+class RWSpinLock {
+ enum : int32_t { READER = 4, UPGRADED = 2, WRITER = 1 };
+ public:
+ constexpr RWSpinLock() : bits_(0) {}
+
+ RWSpinLock(RWSpinLock const&) = delete;
+ RWSpinLock& operator=(RWSpinLock const&) = delete;
+
+ // Lockable Concept
+ void lock() {
+ uint_fast32_t count = 0;
+ while (!LIKELY(try_lock())) {
+ if (++count > 1000) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ // Writer is responsible for clearing up both the UPGRADED and WRITER bits.
+ void unlock() {
+ static_assert(READER > WRITER + UPGRADED, "wrong bits!");
+ bits_.fetch_and(~(WRITER | UPGRADED), std::memory_order_release);
+ }
+
+ // SharedLockable Concept
+ void lock_shared() {
+ uint_fast32_t count = 0;
+ while (!LIKELY(try_lock_shared())) {
+ if (++count > 1000) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ void unlock_shared() {
+ bits_.fetch_add(-READER, std::memory_order_release);
+ }
+
+ // Downgrade the lock from writer status to reader status.
+ void unlock_and_lock_shared() {
+ bits_.fetch_add(READER, std::memory_order_acquire);
+ unlock();
+ }
+
+ // UpgradeLockable Concept
+ void lock_upgrade() {
+ uint_fast32_t count = 0;
+ while (!try_lock_upgrade()) {
+ if (++count > 1000) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ void unlock_upgrade() {
+ bits_.fetch_add(-UPGRADED, std::memory_order_acq_rel);
+ }
+
+ // unlock upgrade and try to acquire write lock
+ void unlock_upgrade_and_lock() {
+ int64_t count = 0;
+ while (!try_unlock_upgrade_and_lock()) {
+ if (++count > 1000) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ // unlock upgrade and read lock atomically
+ void unlock_upgrade_and_lock_shared() {
+ bits_.fetch_add(READER - UPGRADED, std::memory_order_acq_rel);
+ }
+
+ // write unlock and upgrade lock atomically
+ void unlock_and_lock_upgrade() {
+ // need to do it in two steps here -- as the UPGRADED bit might be OR-ed at
+ // the same time when other threads are trying do try_lock_upgrade().
+ bits_.fetch_or(UPGRADED, std::memory_order_acquire);
+ bits_.fetch_add(-WRITER, std::memory_order_release);
+ }
+
+
+ // Attempt to acquire writer permission. Return false if we didn't get it.
+ bool try_lock() {
+ int32_t expect = 0;
+ return bits_.compare_exchange_strong(expect, WRITER,
+ std::memory_order_acq_rel);
+ }
+
+ // Try to get reader permission on the lock. This can fail if we
+ // find out someone is a writer or upgrader.
+ // Setting the UPGRADED bit would allow a writer-to-be to indicate
+ // its intention to write and block any new readers while waiting
+ // for existing readers to finish and release their read locks. This
+ // helps avoid starving writers (promoted from upgraders).
+ bool try_lock_shared() {
+ // fetch_add is considerably (100%) faster than compare_exchange,
+ // so here we are optimizing for the common (lock success) case.
+ int32_t value = bits_.fetch_add(READER, std::memory_order_acquire);
+ if (UNLIKELY(value & (WRITER|UPGRADED))) {
+ bits_.fetch_add(-READER, std::memory_order_release);
+ return false;
+ }
+ return true;
+ }
+
+ // try to unlock upgrade and write lock atomically
+ bool try_unlock_upgrade_and_lock() {
+ int32_t expect = UPGRADED;
+ return bits_.compare_exchange_strong(expect, WRITER,
+ std::memory_order_acq_rel);
+ }
+
+ // try to acquire an upgradable lock.
+ bool try_lock_upgrade() {
+ int32_t value = bits_.fetch_or(UPGRADED, std::memory_order_acquire);
+
+ // Note: when failed, we cannot flip the UPGRADED bit back,
+ // as in this case there is either another upgrade lock or a write lock.
+ // If it's a write lock, the bit will get cleared up when that lock's done
+ // with unlock().
+ return ((value & (UPGRADED | WRITER)) == 0);
+ }
+
+ // mainly for debugging purposes.
+ int32_t bits() const { return bits_.load(std::memory_order_acquire); }
+
+ class ReadHolder;
+ class UpgradedHolder;
+ class WriteHolder;
+
+ class ReadHolder {
+ public:
+ explicit ReadHolder(RWSpinLock* lock) : lock_(lock) {
+ if (lock_) {
+ lock_->lock_shared();
+ }
+ }
+
+ explicit ReadHolder(RWSpinLock& lock) : lock_(&lock) {
+ lock_->lock_shared();
+ }
+
+ ReadHolder(ReadHolder&& other) noexcept : lock_(other.lock_) {
+ other.lock_ = nullptr;
+ }
+
+ // down-grade
+ explicit ReadHolder(UpgradedHolder&& upgraded) : lock_(upgraded.lock_) {
+ upgraded.lock_ = nullptr;
+ if (lock_) {
+ lock_->unlock_upgrade_and_lock_shared();
+ }
+ }
+
+ explicit ReadHolder(WriteHolder&& writer) : lock_(writer.lock_) {
+ writer.lock_ = nullptr;
+ if (lock_) {
+ lock_->unlock_and_lock_shared();
+ }
+ }
+
+ ReadHolder& operator=(ReadHolder&& other) {
+ using std::swap;
+ swap(lock_, other.lock_);
+ return *this;
+ }
+
+ ReadHolder(const ReadHolder& other) = delete;
+ ReadHolder& operator=(const ReadHolder& other) = delete;
+
+ ~ReadHolder() {
+ if (lock_) {
+ lock_->unlock_shared();
+ }
+ }
+
+ void reset(RWSpinLock* lock = nullptr) {
+ if (lock == lock_) {
+ return;
+ }
+ if (lock_) {
+ lock_->unlock_shared();
+ }
+ lock_ = lock;
+ if (lock_) {
+ lock_->lock_shared();
+ }
+ }
+
+ void swap(ReadHolder* other) {
+ std::swap(lock_, other->lock_);
+ }
+
+ private:
+ friend class UpgradedHolder;
+ friend class WriteHolder;
+ RWSpinLock* lock_;
+ };
+
+ class UpgradedHolder {
+ public:
+ explicit UpgradedHolder(RWSpinLock* lock) : lock_(lock) {
+ if (lock_) {
+ lock_->lock_upgrade();
+ }
+ }
+
+ explicit UpgradedHolder(RWSpinLock& lock) : lock_(&lock) {
+ lock_->lock_upgrade();
+ }
+
+ explicit UpgradedHolder(WriteHolder&& writer) {
+ lock_ = writer.lock_;
+ writer.lock_ = nullptr;
+ if (lock_) {
+ lock_->unlock_and_lock_upgrade();
+ }
+ }
+
+ UpgradedHolder(UpgradedHolder&& other) noexcept : lock_(other.lock_) {
+ other.lock_ = nullptr;
+ }
+
+ UpgradedHolder& operator =(UpgradedHolder&& other) {
+ using std::swap;
+ swap(lock_, other.lock_);
+ return *this;
+ }
+
+ UpgradedHolder(const UpgradedHolder& other) = delete;
+ UpgradedHolder& operator =(const UpgradedHolder& other) = delete;
+
+ ~UpgradedHolder() {
+ if (lock_) {
+ lock_->unlock_upgrade();
+ }
+ }
+
+ void reset(RWSpinLock* lock = nullptr) {
+ if (lock == lock_) {
+ return;
+ }
+ if (lock_) {
+ lock_->unlock_upgrade();
+ }
+ lock_ = lock;
+ if (lock_) {
+ lock_->lock_upgrade();
+ }
+ }
+
+ void swap(UpgradedHolder* other) {
+ using std::swap;
+ swap(lock_, other->lock_);
+ }
+
+ private:
+ friend class WriteHolder;
+ friend class ReadHolder;
+ RWSpinLock* lock_;
+ };
+
+ class WriteHolder {
+ public:
+ explicit WriteHolder(RWSpinLock* lock) : lock_(lock) {
+ if (lock_) {
+ lock_->lock();
+ }
+ }
+
+ explicit WriteHolder(RWSpinLock& lock) : lock_(&lock) {
+ lock_->lock();
+ }
+
+ // promoted from an upgrade lock holder
+ explicit WriteHolder(UpgradedHolder&& upgraded) {
+ lock_ = upgraded.lock_;
+ upgraded.lock_ = nullptr;
+ if (lock_) {
+ lock_->unlock_upgrade_and_lock();
+ }
+ }
+
+ WriteHolder(WriteHolder&& other) noexcept : lock_(other.lock_) {
+ other.lock_ = nullptr;
+ }
+
+ WriteHolder& operator =(WriteHolder&& other) {
+ using std::swap;
+ swap(lock_, other.lock_);
+ return *this;
+ }
+
+ WriteHolder(const WriteHolder& other) = delete;
+ WriteHolder& operator =(const WriteHolder& other) = delete;
+
+ ~WriteHolder() {
+ if (lock_) {
+ lock_->unlock();
+ }
+ }
+
+ void reset(RWSpinLock* lock = nullptr) {
+ if (lock == lock_) {
+ return;
+ }
+ if (lock_) {
+ lock_->unlock();
+ }
+ lock_ = lock;
+ if (lock_) {
+ lock_->lock();
+ }
+ }
+
+ void swap(WriteHolder* other) {
+ using std::swap;
+ swap(lock_, other->lock_);
+ }
+
+ private:
+ friend class ReadHolder;
+ friend class UpgradedHolder;
+ RWSpinLock* lock_;
+ };
+
+ private:
+ std::atomic<int32_t> bits_;
+};
+
+
+#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
+// A more balanced Read-Write spin lock implemented based on GCC intrinsics.
+
+namespace detail {
+template <size_t kBitWidth> struct RWTicketIntTrait {
+ static_assert(kBitWidth == 32 || kBitWidth == 64,
+ "bit width has to be either 32 or 64 ");
+};
+
+template <>
+struct RWTicketIntTrait<64> {
+ typedef uint64_t FullInt;
+ typedef uint32_t HalfInt;
+ typedef uint16_t QuarterInt;
+
+#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+ static __m128i make128(const uint16_t v[4]) {
+ return _mm_set_epi16(0, 0, 0, 0,
+ short(v[3]), short(v[2]), short(v[1]), short(v[0]));
+ }
+ static inline __m128i fromInteger(uint64_t from) {
+ return _mm_cvtsi64_si128(int64_t(from));
+ }
+ static inline uint64_t toInteger(__m128i in) {
+ return uint64_t(_mm_cvtsi128_si64(in));
+ }
+ static inline uint64_t addParallel(__m128i in, __m128i kDelta) {
+ return toInteger(_mm_add_epi16(in, kDelta));
+ }
+#endif
+};
+
+template <>
+struct RWTicketIntTrait<32> {
+ typedef uint32_t FullInt;
+ typedef uint16_t HalfInt;
+ typedef uint8_t QuarterInt;
+
+#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+ static __m128i make128(const uint8_t v[4]) {
+ return _mm_set_epi8(
+ 0, 0, 0, 0,
+ 0, 0, 0, 0,
+ 0, 0, 0, 0,
+ char(v[3]), char(v[2]), char(v[1]), char(v[0]));
+ }
+ static inline __m128i fromInteger(uint32_t from) {
+ return _mm_cvtsi32_si128(int32_t(from));
+ }
+ static inline uint32_t toInteger(__m128i in) {
+ return uint32_t(_mm_cvtsi128_si32(in));
+ }
+ static inline uint32_t addParallel(__m128i in, __m128i kDelta) {
+ return toInteger(_mm_add_epi8(in, kDelta));
+ }
+#endif
+};
+} // namespace detail
+
+template <size_t kBitWidth, bool kFavorWriter = false>
+class RWTicketSpinLockT {
+ typedef detail::RWTicketIntTrait<kBitWidth> IntTraitType;
+ typedef typename detail::RWTicketIntTrait<kBitWidth>::FullInt FullInt;
+ typedef typename detail::RWTicketIntTrait<kBitWidth>::HalfInt HalfInt;
+ typedef typename detail::RWTicketIntTrait<kBitWidth>::QuarterInt
+ QuarterInt;
+
+ union RWTicket {
+ constexpr RWTicket() : whole(0) {}
+ FullInt whole;
+ HalfInt readWrite;
+ __extension__ struct {
+ QuarterInt write;
+ QuarterInt read;
+ QuarterInt users;
+ };
+ } ticket;
+
+ private: // Some x64-specific utilities for atomic access to ticket.
+ template <class T> static T load_acquire(T* addr) {
+ T t = *addr; // acquire barrier
+ asm_volatile_memory();
+ return t;
+ }
+
+ template <class T>
+ static void store_release(T* addr, T v) {
+ asm_volatile_memory();
+ *addr = v; // release barrier
+ }
+
+ public:
+
+ constexpr RWTicketSpinLockT() {}
+
+ RWTicketSpinLockT(RWTicketSpinLockT const&) = delete;
+ RWTicketSpinLockT& operator=(RWTicketSpinLockT const&) = delete;
+
+ void lock() {
+ if (kFavorWriter) {
+ writeLockAggressive();
+ } else {
+ writeLockNice();
+ }
+ }
+
+ /*
+ * Both try_lock and try_lock_shared diverge in our implementation from the
+ * lock algorithm described in the link above.
+ *
+ * In the read case, it is undesirable that the readers could wait
+ * for another reader (before increasing ticket.read in the other
+ * implementation). Our approach gives up on
+ * first-come-first-serve, but our benchmarks showed improve
+ * performance for both readers and writers under heavily contended
+ * cases, particularly when the number of threads exceeds the number
+ * of logical CPUs.
+ *
+ * We have writeLockAggressive() using the original implementation
+ * for a writer, which gives some advantage to the writer over the
+ * readers---for that path it is guaranteed that the writer will
+ * acquire the lock after all the existing readers exit.
+ */
+ bool try_lock() {
+ RWTicket t;
+ FullInt old = t.whole = load_acquire(&ticket.whole);
+ if (t.users != t.write) {
+ return false;
+ }
+ ++t.users;
+ return __sync_bool_compare_and_swap(&ticket.whole, old, t.whole);
+ }
+
+ /*
+ * Call this if you want to prioritize writer to avoid starvation.
+ * Unlike writeLockNice, immediately acquires the write lock when
+ * the existing readers (arriving before the writer) finish their
+ * turns.
+ */
+ void writeLockAggressive() {
+ // std::this_thread::yield() is needed here to avoid a pathology if the number
+ // of threads attempting concurrent writes is >= the number of real
+ // cores allocated to this process. This is less likely than the
+ // corresponding situation in lock_shared(), but we still want to
+ // avoid it
+ uint_fast32_t count = 0;
+ QuarterInt val = __sync_fetch_and_add(&ticket.users, 1);
+ while (val != load_acquire(&ticket.write)) {
+ asm_volatile_pause();
+ if (UNLIKELY(++count > 1000)) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ // Call this when the writer should be nicer to the readers.
+ void writeLockNice() {
+ // Here it doesn't cpu-relax the writer.
+ //
+ // This is because usually we have many more readers than the
+ // writers, so the writer has less chance to get the lock when
+ // there are a lot of competing readers. The aggressive spinning
+ // can help to avoid starving writers.
+ //
+ // We don't worry about std::this_thread::yield() here because the caller
+ // has already explicitly abandoned fairness.
+ while (!try_lock()) {}
+ }
+
+ // Atomically unlock the write-lock from writer and acquire the read-lock.
+ void unlock_and_lock_shared() {
+ QuarterInt val = __sync_fetch_and_add(&ticket.read, 1);
+ }
+
+ // Release writer permission on the lock.
+ void unlock() {
+ RWTicket t;
+ t.whole = load_acquire(&ticket.whole);
+
+#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+ FullInt old = t.whole;
+ // SSE2 can reduce the lock and unlock overhead by 10%
+ static const QuarterInt kDeltaBuf[4] = { 1, 1, 0, 0 }; // write/read/user
+ static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
+ __m128i m = IntTraitType::fromInteger(old);
+ t.whole = IntTraitType::addParallel(m, kDelta);
+#else
+ ++t.read;
+ ++t.write;
+#endif
+ store_release(&ticket.readWrite, t.readWrite);
+ }
+
+ void lock_shared() {
+ // std::this_thread::yield() is important here because we can't grab the
+ // shared lock if there is a pending writeLockAggressive, so we
+ // need to let threads that already have a shared lock complete
+ uint_fast32_t count = 0;
+ while (!LIKELY(try_lock_shared())) {
+ asm_volatile_pause();
+ if (UNLIKELY((++count & 1023) == 0)) {
+ std::this_thread::yield();
+ }
+ }
+ }
+
+ bool try_lock_shared() {
+ RWTicket t, old;
+ old.whole = t.whole = load_acquire(&ticket.whole);
+ old.users = old.read;
+#ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
+ // SSE2 may reduce the total lock and unlock overhead by 10%
+ static const QuarterInt kDeltaBuf[4] = { 0, 1, 1, 0 }; // write/read/user
+ static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
+ __m128i m = IntTraitType::fromInteger(old.whole);
+ t.whole = IntTraitType::addParallel(m, kDelta);
+#else
+ ++t.read;
+ ++t.users;
+#endif
+ return __sync_bool_compare_and_swap(&ticket.whole, old.whole, t.whole);
+ }
+
+ void unlock_shared() {
+ __sync_fetch_and_add(&ticket.write, 1);
+ }
+
+ class WriteHolder;
+
+ typedef RWTicketSpinLockT<kBitWidth, kFavorWriter> RWSpinLock;
+ class ReadHolder {
+ public:
+ ReadHolder(ReadHolder const&) = delete;
+ ReadHolder& operator=(ReadHolder const&) = delete;
+
+ explicit ReadHolder(RWSpinLock* lock) : lock_(lock) {
+ if (lock_) {
+ lock_->lock_shared();
+ }
+ }
+
+ explicit ReadHolder(RWSpinLock &lock) : lock_ (&lock) {
+ if (lock_) {
+ lock_->lock_shared();
+ }
+ }
+
+ // atomically unlock the write-lock from writer and acquire the read-lock
+ explicit ReadHolder(WriteHolder *writer) : lock_(nullptr) {
+ std::swap(this->lock_, writer->lock_);
+ if (lock_) {
+ lock_->unlock_and_lock_shared();
+ }
+ }
+
+ ~ReadHolder() {
+ if (lock_) {
+ lock_->unlock_shared();
+ }
+ }
+
+ void reset(RWSpinLock *lock = nullptr) {
+ if (lock_) {
+ lock_->unlock_shared();
+ }
+ lock_ = lock;
+ if (lock_) {
+ lock_->lock_shared();
+ }
+ }
+
+ void swap(ReadHolder *other) {
+ std::swap(this->lock_, other->lock_);
+ }
+
+ private:
+ RWSpinLock *lock_;
+ };
+
+ class WriteHolder {
+ public:
+ WriteHolder(WriteHolder const&) = delete;
+ WriteHolder& operator=(WriteHolder const&) = delete;
+
+ explicit WriteHolder(RWSpinLock* lock) : lock_(lock) {
+ if (lock_) {
+ lock_->lock();
+ }
+ }
+ explicit WriteHolder(RWSpinLock &lock) : lock_ (&lock) {
+ if (lock_) {
+ lock_->lock();
+ }
+ }
+
+ ~WriteHolder() {
+ if (lock_) {
+ lock_->unlock();
+ }
+ }
+
+ void reset(RWSpinLock *lock = nullptr) {
+ if (lock == lock_) {
+ return;
+ }
+ if (lock_) {
+ lock_->unlock();
+ }
+ lock_ = lock;
+ if (lock_) {
+ lock_->lock();
+ }
+ }
+
+ void swap(WriteHolder *other) {
+ std::swap(this->lock_, other->lock_);
+ }
+
+ private:
+ friend class ReadHolder;
+ RWSpinLock *lock_;
+ };
+};
+
+typedef RWTicketSpinLockT<32> RWTicketSpinLock32;
+typedef RWTicketSpinLockT<64> RWTicketSpinLock64;
+
+#endif // RW_SPINLOCK_USE_X86_INTRINSIC_
+
+} // namespace folly
+
+#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
+#undef RW_SPINLOCK_USE_X86_INTRINSIC_
+#endif
--- /dev/null
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * 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.
+ */
+//
+// @author xliu (xliux@fb.com)
+//
+
+#include <folly/synchronization/RWSpinLock.h>
+
+#include <stdlib.h>
+#include <thread>
+#include <vector>
+
+#include <glog/logging.h>
+
+#include <folly/portability/GFlags.h>
+#include <folly/portability/GTest.h>
+#include <folly/portability/Unistd.h>
+
+DEFINE_int32(num_threads, 8, "num threads");
+
+namespace {
+
+static const int kMaxReaders = 50;
+static std::atomic<bool> stopThread;
+using namespace folly;
+
+template <typename RWSpinLockT> struct RWSpinLockTest: public testing::Test {
+ typedef RWSpinLockT RWSpinLockType;
+};
+
+typedef testing::Types<RWSpinLock
+#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
+ , RWTicketSpinLockT<32, true>,
+ RWTicketSpinLockT<32, false>,
+ RWTicketSpinLockT<64, true>,
+ RWTicketSpinLockT<64, false>
+#endif
+> Implementations;
+
+TYPED_TEST_CASE(RWSpinLockTest, Implementations);
+
+template <typename RWSpinLockType>
+static void run(RWSpinLockType* lock) {
+ int64_t reads = 0;
+ int64_t writes = 0;
+ while (!stopThread.load(std::memory_order_acquire)) {
+ if (rand() % 10 == 0) { // write
+ typename RWSpinLockType::WriteHolder guard(lock);
+ ++writes;
+ } else { // read
+ typename RWSpinLockType::ReadHolder guard(lock);
+ ++reads;
+ }
+ }
+ // VLOG(0) << "total reads: " << reads << "; total writes: " << writes;
+}
+
+
+TYPED_TEST(RWSpinLockTest, Writer_Wait_Readers) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+
+ for (int i = 0; i < kMaxReaders; ++i) {
+ EXPECT_TRUE(l.try_lock_shared());
+ EXPECT_FALSE(l.try_lock());
+ }
+
+ for (int i = 0; i < kMaxReaders; ++i) {
+ EXPECT_FALSE(l.try_lock());
+ l.unlock_shared();
+ }
+
+ EXPECT_TRUE(l.try_lock());
+}
+
+TYPED_TEST(RWSpinLockTest, Readers_Wait_Writer) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+
+ EXPECT_TRUE(l.try_lock());
+
+ for (int i = 0; i < kMaxReaders; ++i) {
+ EXPECT_FALSE(l.try_lock_shared());
+ }
+
+ l.unlock_and_lock_shared();
+ for (int i = 0; i < kMaxReaders - 1; ++i) {
+ EXPECT_TRUE(l.try_lock_shared());
+ }
+}
+
+TYPED_TEST(RWSpinLockTest, Writer_Wait_Writer) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+
+ EXPECT_TRUE(l.try_lock());
+ EXPECT_FALSE(l.try_lock());
+ l.unlock();
+
+ EXPECT_TRUE(l.try_lock());
+ EXPECT_FALSE(l.try_lock());
+}
+
+TYPED_TEST(RWSpinLockTest, Read_Holders) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+
+ {
+ typename RWSpinLockType::ReadHolder guard(&l);
+ EXPECT_FALSE(l.try_lock());
+ EXPECT_TRUE(l.try_lock_shared());
+ l.unlock_shared();
+
+ EXPECT_FALSE(l.try_lock());
+ }
+
+ EXPECT_TRUE(l.try_lock());
+ l.unlock();
+}
+
+TYPED_TEST(RWSpinLockTest, Write_Holders) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+ {
+ typename RWSpinLockType::WriteHolder guard(&l);
+ EXPECT_FALSE(l.try_lock());
+ EXPECT_FALSE(l.try_lock_shared());
+ }
+
+ EXPECT_TRUE(l.try_lock_shared());
+ EXPECT_FALSE(l.try_lock());
+ l.unlock_shared();
+ EXPECT_TRUE(l.try_lock());
+}
+
+TYPED_TEST(RWSpinLockTest, ConcurrentTests) {
+ typedef typename TestFixture::RWSpinLockType RWSpinLockType;
+ RWSpinLockType l;
+ srand(time(nullptr));
+
+ std::vector<std::thread> threads;
+ for (int i = 0; i < FLAGS_num_threads; ++i) {
+ threads.push_back(std::thread(&run<RWSpinLockType>, &l));
+ }
+
+ sleep(1);
+ stopThread.store(true, std::memory_order_release);
+
+ for (auto& t : threads) {
+ t.join();
+ }
+}
+
+// RWSpinLock specific tests
+
+TEST(RWSpinLock, lock_unlock_tests) {
+ folly::RWSpinLock lock;
+ EXPECT_TRUE(lock.try_lock_upgrade());
+ EXPECT_FALSE(lock.try_lock_shared());
+ EXPECT_FALSE(lock.try_lock());
+ EXPECT_FALSE(lock.try_lock_upgrade());
+ lock.unlock_upgrade();
+ lock.lock_shared();
+ EXPECT_FALSE(lock.try_lock());
+ EXPECT_TRUE(lock.try_lock_upgrade());
+ lock.unlock_upgrade();
+ lock.unlock_shared();
+ EXPECT_TRUE(lock.try_lock());
+ EXPECT_FALSE(lock.try_lock_upgrade());
+ lock.unlock_and_lock_upgrade();
+ EXPECT_FALSE(lock.try_lock_shared());
+ lock.unlock_upgrade_and_lock_shared();
+ lock.unlock_shared();
+ EXPECT_EQ(0, lock.bits());
+}
+
+TEST(RWSpinLock, concurrent_holder_test) {
+ srand(time(nullptr));
+
+ folly::RWSpinLock lock;
+ std::atomic<int64_t> reads(0);
+ std::atomic<int64_t> writes(0);
+ std::atomic<int64_t> upgrades(0);
+ std::atomic<bool> stop(false);
+
+ auto go = [&] {
+ while (!stop.load(std::memory_order_acquire)) {
+ auto r = (uint32_t)(rand()) % 10;
+ if (r < 3) { // starts from write lock
+ RWSpinLock::ReadHolder rg{
+ RWSpinLock::UpgradedHolder{
+ RWSpinLock::WriteHolder{&lock}}};
+ writes.fetch_add(1, std::memory_order_acq_rel);;
+ } else if (r < 6) { // starts from upgrade lock
+ RWSpinLock::UpgradedHolder ug(&lock);
+ if (r < 4) {
+ RWSpinLock::WriteHolder wg(std::move(ug));
+ } else {
+ RWSpinLock::ReadHolder rg(std::move(ug));
+ }
+ upgrades.fetch_add(1, std::memory_order_acq_rel);;
+ } else {
+ RWSpinLock::ReadHolder rg{&lock};
+ reads.fetch_add(1, std::memory_order_acq_rel);
+ }
+ }
+ };
+
+ std::vector<std::thread> threads;
+ for (int i = 0; i < FLAGS_num_threads; ++i) {
+ threads.push_back(std::thread(go));
+ }
+
+ sleep(5);
+ stop.store(true, std::memory_order_release);
+
+ for (auto& t : threads) {
+ t.join();
+ }
+
+ LOG(INFO) << "reads: " << reads.load(std::memory_order_acquire)
+ << "; writes: " << writes.load(std::memory_order_acquire)
+ << "; upgrades: " << upgrades.load(std::memory_order_acquire);
+}
+
+} // namespace
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
// @author: Xin Liu <xliux@fb.com>
#include <map>
#include <folly/Benchmark.h>
#include <folly/ConcurrentSkipList.h>
-#include <folly/RWSpinLock.h>
#include <folly/hash/Hash.h>
#include <folly/portability/GFlags.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <glog/logging.h>
DEFINE_int32(num_threads, 12, "num concurrent threads to test");
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <mutex>
-#include <folly/RWSpinLock.h>
#include <folly/SharedMutex.h>
#include <folly/SpinLock.h>
#include <folly/portability/GTest.h>
+#include <folly/synchronization/RWSpinLock.h>
using namespace folly;
endian_test_LDADD = libfollytestmain.la
TESTS += endian_test
-rw_spinlock_test_SOURCES = RWSpinLockTest.cpp
+rw_spinlock_test_SOURCES = ../synchronization/test/RWSpinLockTest.cpp
rw_spinlock_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la
TESTS += rw_spinlock_test
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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.
- */
-
-//
-// @author xliu (xliux@fb.com)
-//
-
-#include <folly/RWSpinLock.h>
-
-#include <stdlib.h>
-#include <thread>
-#include <vector>
-
-#include <glog/logging.h>
-
-#include <folly/portability/GFlags.h>
-#include <folly/portability/GTest.h>
-#include <folly/portability/Unistd.h>
-
-DEFINE_int32(num_threads, 8, "num threads");
-
-namespace {
-
-static const int kMaxReaders = 50;
-static std::atomic<bool> stopThread;
-using namespace folly;
-
-template <typename RWSpinLockT> struct RWSpinLockTest: public testing::Test {
- typedef RWSpinLockT RWSpinLockType;
-};
-
-typedef testing::Types<RWSpinLock
-#ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
- , RWTicketSpinLockT<32, true>,
- RWTicketSpinLockT<32, false>,
- RWTicketSpinLockT<64, true>,
- RWTicketSpinLockT<64, false>
-#endif
-> Implementations;
-
-TYPED_TEST_CASE(RWSpinLockTest, Implementations);
-
-template <typename RWSpinLockType>
-static void run(RWSpinLockType* lock) {
- int64_t reads = 0;
- int64_t writes = 0;
- while (!stopThread.load(std::memory_order_acquire)) {
- if (rand() % 10 == 0) { // write
- typename RWSpinLockType::WriteHolder guard(lock);
- ++writes;
- } else { // read
- typename RWSpinLockType::ReadHolder guard(lock);
- ++reads;
- }
- }
- // VLOG(0) << "total reads: " << reads << "; total writes: " << writes;
-}
-
-
-TYPED_TEST(RWSpinLockTest, Writer_Wait_Readers) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
-
- for (int i = 0; i < kMaxReaders; ++i) {
- EXPECT_TRUE(l.try_lock_shared());
- EXPECT_FALSE(l.try_lock());
- }
-
- for (int i = 0; i < kMaxReaders; ++i) {
- EXPECT_FALSE(l.try_lock());
- l.unlock_shared();
- }
-
- EXPECT_TRUE(l.try_lock());
-}
-
-TYPED_TEST(RWSpinLockTest, Readers_Wait_Writer) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
-
- EXPECT_TRUE(l.try_lock());
-
- for (int i = 0; i < kMaxReaders; ++i) {
- EXPECT_FALSE(l.try_lock_shared());
- }
-
- l.unlock_and_lock_shared();
- for (int i = 0; i < kMaxReaders - 1; ++i) {
- EXPECT_TRUE(l.try_lock_shared());
- }
-}
-
-TYPED_TEST(RWSpinLockTest, Writer_Wait_Writer) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
-
- EXPECT_TRUE(l.try_lock());
- EXPECT_FALSE(l.try_lock());
- l.unlock();
-
- EXPECT_TRUE(l.try_lock());
- EXPECT_FALSE(l.try_lock());
-}
-
-TYPED_TEST(RWSpinLockTest, Read_Holders) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
-
- {
- typename RWSpinLockType::ReadHolder guard(&l);
- EXPECT_FALSE(l.try_lock());
- EXPECT_TRUE(l.try_lock_shared());
- l.unlock_shared();
-
- EXPECT_FALSE(l.try_lock());
- }
-
- EXPECT_TRUE(l.try_lock());
- l.unlock();
-}
-
-TYPED_TEST(RWSpinLockTest, Write_Holders) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
- {
- typename RWSpinLockType::WriteHolder guard(&l);
- EXPECT_FALSE(l.try_lock());
- EXPECT_FALSE(l.try_lock_shared());
- }
-
- EXPECT_TRUE(l.try_lock_shared());
- EXPECT_FALSE(l.try_lock());
- l.unlock_shared();
- EXPECT_TRUE(l.try_lock());
-}
-
-TYPED_TEST(RWSpinLockTest, ConcurrentTests) {
- typedef typename TestFixture::RWSpinLockType RWSpinLockType;
- RWSpinLockType l;
- srand(time(nullptr));
-
- std::vector<std::thread> threads;
- for (int i = 0; i < FLAGS_num_threads; ++i) {
- threads.push_back(std::thread(&run<RWSpinLockType>, &l));
- }
-
- sleep(1);
- stopThread.store(true, std::memory_order_release);
-
- for (auto& t : threads) {
- t.join();
- }
-}
-
-// RWSpinLock specific tests
-
-TEST(RWSpinLock, lock_unlock_tests) {
- folly::RWSpinLock lock;
- EXPECT_TRUE(lock.try_lock_upgrade());
- EXPECT_FALSE(lock.try_lock_shared());
- EXPECT_FALSE(lock.try_lock());
- EXPECT_FALSE(lock.try_lock_upgrade());
- lock.unlock_upgrade();
- lock.lock_shared();
- EXPECT_FALSE(lock.try_lock());
- EXPECT_TRUE(lock.try_lock_upgrade());
- lock.unlock_upgrade();
- lock.unlock_shared();
- EXPECT_TRUE(lock.try_lock());
- EXPECT_FALSE(lock.try_lock_upgrade());
- lock.unlock_and_lock_upgrade();
- EXPECT_FALSE(lock.try_lock_shared());
- lock.unlock_upgrade_and_lock_shared();
- lock.unlock_shared();
- EXPECT_EQ(0, lock.bits());
-}
-
-TEST(RWSpinLock, concurrent_holder_test) {
- srand(time(nullptr));
-
- folly::RWSpinLock lock;
- std::atomic<int64_t> reads(0);
- std::atomic<int64_t> writes(0);
- std::atomic<int64_t> upgrades(0);
- std::atomic<bool> stop(false);
-
- auto go = [&] {
- while (!stop.load(std::memory_order_acquire)) {
- auto r = (uint32_t)(rand()) % 10;
- if (r < 3) { // starts from write lock
- RWSpinLock::ReadHolder rg{
- RWSpinLock::UpgradedHolder{
- RWSpinLock::WriteHolder{&lock}}};
- writes.fetch_add(1, std::memory_order_acq_rel);;
- } else if (r < 6) { // starts from upgrade lock
- RWSpinLock::UpgradedHolder ug(&lock);
- if (r < 4) {
- RWSpinLock::WriteHolder wg(std::move(ug));
- } else {
- RWSpinLock::ReadHolder rg(std::move(ug));
- }
- upgrades.fetch_add(1, std::memory_order_acq_rel);;
- } else {
- RWSpinLock::ReadHolder rg{&lock};
- reads.fetch_add(1, std::memory_order_acq_rel);
- }
- }
- };
-
- std::vector<std::thread> threads;
- for (int i = 0; i < FLAGS_num_threads; ++i) {
- threads.push_back(std::thread(go));
- }
-
- sleep(5);
- stop.store(true, std::memory_order_release);
-
- for (auto& t : threads) {
- t.join();
- }
-
- LOG(INFO) << "reads: " << reads.load(std::memory_order_acquire)
- << "; writes: " << writes.load(std::memory_order_acquire)
- << "; upgrades: " << upgrades.load(std::memory_order_acquire);
-}
-
-} // namespace
/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
#include <folly/SharedMutex.h>
#include <stdlib.h>
#include <folly/Benchmark.h>
#include <folly/MPMCQueue.h>
-#include <folly/RWSpinLock.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <folly/test/DeterministicSchedule.h>
using namespace folly;
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
#include <folly/SynchronizedPtr.h>
#include <folly/Optional.h>
-#include <folly/RWSpinLock.h>
#include <folly/Replaceable.h>
#include <folly/portability/GTest.h>
+#include <folly/synchronization/RWSpinLock.h>
template <typename SPtr>
void basics(SPtr& sptr) {
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
// @author: Andrei Alexandrescu (aalexandre)
// Test bed for folly/Synchronized.h
+#include <folly/Synchronized.h>
#include <folly/LockTraitsBoost.h>
#include <folly/Portability.h>
-#include <folly/RWSpinLock.h>
#include <folly/SharedMutex.h>
#include <folly/SpinLock.h>
-#include <folly/Synchronized.h>
#include <folly/portability/GTest.h>
+#include <folly/synchronization/RWSpinLock.h>
#include <folly/test/SynchronizedTestLib.h>
using namespace folly::sync_tests;
projects / folly.git / commitdiff