140 #if defined(__GNUC__) && (defined(__i386) || FOLLY_X64 || defined(ARCH_K8)) 141 #define RW_SPINLOCK_USE_X86_INTRINSIC_ 142 #include <x86intrin.h> 143 #elif defined(_MSC_VER) && defined(FOLLY_X64) 144 #define RW_SPINLOCK_USE_X86_INTRINSIC_ 146 #define RW_SPINLOCK_USE_X86_INTRINSIC_ 148 #undef RW_SPINLOCK_USE_X86_INTRINSIC_ 152 #if (FOLLY_SSE >= 2) && !FOLLY_MOBILE && FOLLY_X64 153 #define RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 155 #undef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 192 uint_fast32_t
count = 0;
194 if (++count > 1000) {
208 uint_fast32_t
count = 0;
210 if (++count > 1000) {
217 bits_.fetch_add(-
READER, std::memory_order_release);
222 bits_.fetch_add(
READER, std::memory_order_acquire);
228 uint_fast32_t
count = 0;
230 if (++count > 1000) {
244 if (++count > 1000) {
260 bits_.fetch_add(-
WRITER, std::memory_order_release);
266 return bits_.compare_exchange_strong(
267 expect,
WRITER, std::memory_order_acq_rel);
281 bits_.fetch_add(-
READER, std::memory_order_release);
290 return bits_.compare_exchange_strong(
291 expect,
WRITER, std::memory_order_acq_rel);
307 return bits_.load(std::memory_order_acquire);
327 other.lock_ =
nullptr;
332 upgraded.lock_ =
nullptr;
339 writer.lock_ =
nullptr;
396 lock_ = writer.lock_;
397 writer.lock_ =
nullptr;
404 other.lock_ =
nullptr;
460 lock_ = upgraded.lock_;
461 upgraded.lock_ =
nullptr;
468 other.lock_ =
nullptr;
514 #ifdef RW_SPINLOCK_USE_X86_INTRINSIC_ 518 template <
size_t kBitW
idth>
519 struct RWTicketIntTrait {
521 kBitWidth == 32 || kBitWidth == 64,
522 "bit width has to be either 32 or 64 ");
526 struct RWTicketIntTrait<64> {
531 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 532 static __m128i make128(
const uint16_t v[4]) {
533 return _mm_set_epi16(
534 0, 0, 0, 0,
short(v[3]),
short(v[2]),
short(v[1]),
short(v[0]));
537 return _mm_cvtsi64_si128(
int64_t(from));
539 static inline uint64_t toInteger(__m128i in) {
540 return uint64_t(_mm_cvtsi128_si64(in));
542 static inline uint64_t addParallel(__m128i in, __m128i kDelta) {
543 return toInteger(_mm_add_epi16(in, kDelta));
549 struct RWTicketIntTrait<32> {
554 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 555 static __m128i make128(
const uint8_t v[4]) {
561 char(v[3]),
char(v[2]),
char(v[1]),
char(v[0]));
565 return _mm_cvtsi32_si128(
int32_t(from));
567 static inline uint32_t toInteger(__m128i in) {
568 return uint32_t(_mm_cvtsi128_si32(in));
570 static inline uint32_t addParallel(__m128i in, __m128i kDelta) {
571 return toInteger(_mm_add_epi8(in, kDelta));
577 template <
size_t kBitW
idth,
bool kFavorWriter = false>
578 class RWTicketSpinLockT {
579 typedef detail::RWTicketIntTrait<kBitWidth> IntTraitType;
580 typedef typename detail::RWTicketIntTrait<kBitWidth>::FullInt FullInt;
581 typedef typename detail::RWTicketIntTrait<kBitWidth>::HalfInt HalfInt;
582 typedef typename detail::RWTicketIntTrait<kBitWidth>::QuarterInt QuarterInt;
585 constexpr RWTicket() : whole(0) {}
588 __extension__
struct {
597 static T load_acquire(
T*
addr) {
604 static void store_release(
T* addr,
T v) {
610 constexpr RWTicketSpinLockT() {}
612 RWTicketSpinLockT(RWTicketSpinLockT
const&) =
delete;
613 RWTicketSpinLockT&
operator=(RWTicketSpinLockT
const&) =
delete;
617 writeLockAggressive();
642 FullInt old = t.whole = load_acquire(&
ticket.whole);
643 if (t.users != t.write) {
647 return __sync_bool_compare_and_swap(&
ticket.whole, old, t.whole);
656 void writeLockAggressive() {
662 uint_fast32_t
count = 0;
663 QuarterInt
val = __sync_fetch_and_add(&
ticket.users, 1);
664 while (val != load_acquire(&
ticket.write)) {
673 void writeLockNice() {
689 QuarterInt
val = __sync_fetch_and_add(&
ticket.read, 1);
695 t.whole = load_acquire(&
ticket.whole);
697 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 698 FullInt old = t.whole;
700 static const QuarterInt kDeltaBuf[4] = {1, 1, 0, 0};
701 static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
702 __m128i
m = IntTraitType::fromInteger(old);
703 t.whole = IntTraitType::addParallel(m, kDelta);
708 store_release(&
ticket.readWrite, t.readWrite);
715 uint_fast32_t
count = 0;
718 if (
UNLIKELY((++count & 1023) == 0)) {
726 old.whole = t.whole = load_acquire(&
ticket.whole);
727 old.users = old.read;
728 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_ 730 static const QuarterInt kDeltaBuf[4] = {0, 1, 1, 0};
731 static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
732 __m128i
m = IntTraitType::fromInteger(old.whole);
733 t.whole = IntTraitType::addParallel(m, kDelta);
738 return __sync_bool_compare_and_swap(&
ticket.whole, old.whole, t.whole);
742 __sync_fetch_and_add(&
ticket.write, 1);
747 typedef RWTicketSpinLockT<kBitWidth, kFavorWriter>
RWSpinLock;
779 void reset(RWSpinLock* lock =
nullptr) {
819 void reset(RWSpinLock* lock =
nullptr) {
842 typedef RWTicketSpinLockT<32> RWTicketSpinLock32;
843 typedef RWTicketSpinLockT<64> RWTicketSpinLock64;
845 #endif // RW_SPINLOCK_USE_X86_INTRINSIC_ 849 #ifdef RW_SPINLOCK_USE_X86_INTRINSIC_ 850 #undef RW_SPINLOCK_USE_X86_INTRINSIC_
std::atomic< int32_t > bits_
ReadHolder(WriteHolder &&writer)
ReadHolder(ReadHolder &&other) noexcept
void unlock_upgrade_and_lock_shared()
void write(const T &in, folly::io::Appender &appender)
void unlock_and_lock_upgrade()
UpgradedHolder & operator=(UpgradedHolder &&other)
void reset(RWSpinLock *lock=nullptr)
UpgradedHolder(UpgradedHolder &&other) noexcept
WriteHolder(UpgradedHolder &&upgraded)
RWSpinLock & operator=(RWSpinLock const &)=delete
—— Concurrent Priority Queue Implementation ——
WriteHolder(RWSpinLock &lock)
requires E e noexcept(noexcept(s.error(std::move(e))))
ReadHolder(RWSpinLock &lock)
WriteHolder & operator=(WriteHolder &&other)
static constexpr StringPiece ticket
ReadHolder(UpgradedHolder &&upgraded)
void swap(WriteHolder *other)
void unlock_and_lock_shared()
friend class UpgradedHolder
size_t read(T &out, folly::io::Cursor &cursor)
void swap(UpgradedHolder *other)
static map< string, int > m
UpgradedHolder(RWSpinLock &lock)
WriteHolder(RWSpinLock *lock)
void expect(LineReader &lr, const char *expected)
UpgradedHolder(RWSpinLock *lock)
void reset(RWSpinLock *lock=nullptr)
PUSHMI_INLINE_VAR constexpr struct folly::pushmi::operators::from_fn from
void reset(RWSpinLock *lock=nullptr)
UpgradedHolder(WriteHolder &&writer)
void unlock_upgrade_and_lock()
WriteHolder(WriteHolder &&other) noexcept
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
void swap(SwapTrackingAlloc< T > &, SwapTrackingAlloc< T > &)
void swap(ReadHolder *other)
ThreadPoolListHook * addr
ReadHolder(RWSpinLock *lock)
bool try_unlock_upgrade_and_lock()
void asm_volatile_memory()
ReadHolder & operator=(ReadHolder &&other)
void asm_volatile_pause()