63dac2f5dbc294efa737315b1fbd34a0c243583b
[folly.git] / folly / RWSpinLock.h
1 /*
2  * Copyright 2017 Facebook, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 /*
18  * N.B. You most likely do _not_ want to use RWSpinLock or any other
19  * kind of spinlock.  Use SharedMutex instead.
20  *
21  * In short, spinlocks in preemptive multi-tasking operating systems
22  * have serious problems and fast mutexes like SharedMutex are almost
23  * certainly the better choice, because letting the OS scheduler put a
24  * thread to sleep is better for system responsiveness and throughput
25  * than wasting a timeslice repeatedly querying a lock held by a
26  * thread that's blocked, and you can't prevent userspace
27  * programs blocking.
28  *
29  * Spinlocks in an operating system kernel make much more sense than
30  * they do in userspace.
31  *
32  * -------------------------------------------------------------------
33  *
34  * Two Read-Write spin lock implementations.
35  *
36  *  Ref: http://locklessinc.com/articles/locks
37  *
38  *  Both locks here are faster than pthread_rwlock and have very low
39  *  overhead (usually 20-30ns).  They don't use any system mutexes and
40  *  are very compact (4/8 bytes), so are suitable for per-instance
41  *  based locking, particularly when contention is not expected.
42  *
43  *  For a spinlock, RWSpinLock is a reasonable choice.  (See the note
44  *  about for why a spin lock is frequently a bad idea generally.)
45  *  RWSpinLock has minimal overhead, and comparable contention
46  *  performance when the number of competing threads is less than or
47  *  equal to the number of logical CPUs.  Even as the number of
48  *  threads gets larger, RWSpinLock can still be very competitive in
49  *  READ, although it is slower on WRITE, and also inherently unfair
50  *  to writers.
51  *
52  *  RWTicketSpinLock shows more balanced READ/WRITE performance.  If
53  *  your application really needs a lot more threads, and a
54  *  higher-priority writer, prefer one of the RWTicketSpinLock locks.
55  *
56  *  Caveats:
57  *
58  *    RWTicketSpinLock locks can only be used with GCC on x86/x86-64
59  *    based systems.
60  *
61  *    RWTicketSpinLock<32> only allows up to 2^8 - 1 concurrent
62  *    readers and writers.
63  *
64  *    RWTicketSpinLock<64> only allows up to 2^16 - 1 concurrent
65  *    readers and writers.
66  *
67  *    RWTicketSpinLock<..., true> (kFavorWriter = true, that is, strict
68  *    writer priority) is NOT reentrant, even for lock_shared().
69  *
70  *    The lock will not grant any new shared (read) accesses while a thread
71  *    attempting to acquire the lock in write mode is blocked. (That is,
72  *    if the lock is held in shared mode by N threads, and a thread attempts
73  *    to acquire it in write mode, no one else can acquire it in shared mode
74  *    until these N threads release the lock and then the blocked thread
75  *    acquires and releases the exclusive lock.) This also applies for
76  *    attempts to reacquire the lock in shared mode by threads that already
77  *    hold it in shared mode, making the lock non-reentrant.
78  *
79  *    RWSpinLock handles 2^30 - 1 concurrent readers.
80  *
81  * @author Xin Liu <xliux@fb.com>
82  */
83
84 #pragma once
85
86 /*
87 ========================================================================
88 Benchmark on (Intel(R) Xeon(R) CPU  L5630  @ 2.13GHz)  8 cores(16 HTs)
89 ========================================================================
90
91 ------------------------------------------------------------------------------
92 1. Single thread benchmark (read/write lock + unlock overhead)
93 Benchmark                                    Iters   Total t    t/iter iter/sec
94 -------------------------------------------------------------------------------
95 *      BM_RWSpinLockRead                     100000  1.786 ms  17.86 ns   53.4M
96 +30.5% BM_RWSpinLockWrite                    100000  2.331 ms  23.31 ns  40.91M
97 +85.7% BM_RWTicketSpinLock32Read             100000  3.317 ms  33.17 ns  28.75M
98 +96.0% BM_RWTicketSpinLock32Write            100000    3.5 ms     35 ns  27.25M
99 +85.6% BM_RWTicketSpinLock64Read             100000  3.315 ms  33.15 ns  28.77M
100 +96.0% BM_RWTicketSpinLock64Write            100000    3.5 ms     35 ns  27.25M
101 +85.7% BM_RWTicketSpinLock32FavorWriterRead  100000  3.317 ms  33.17 ns  28.75M
102 +29.7% BM_RWTicketSpinLock32FavorWriterWrite 100000  2.316 ms  23.16 ns  41.18M
103 +85.3% BM_RWTicketSpinLock64FavorWriterRead  100000  3.309 ms  33.09 ns  28.82M
104 +30.2% BM_RWTicketSpinLock64FavorWriterWrite 100000  2.325 ms  23.25 ns  41.02M
105 + 175% BM_PThreadRWMutexRead                 100000  4.917 ms  49.17 ns   19.4M
106 + 166% BM_PThreadRWMutexWrite                100000  4.757 ms  47.57 ns  20.05M
107
108 ------------------------------------------------------------------------------
109 2. Contention Benchmark      90% read  10% write
110 Benchmark                    hits       average    min       max        sigma
111 ------------------------------------------------------------------------------
112 ---------- 8  threads ------------
113 RWSpinLock       Write       142666     220ns      78ns      40.8us     269ns
114 RWSpinLock       Read        1282297    222ns      80ns      37.7us     248ns
115 RWTicketSpinLock Write       85692      209ns      71ns      17.9us     252ns
116 RWTicketSpinLock Read        769571     215ns      78ns      33.4us     251ns
117 pthread_rwlock_t Write       84248      2.48us     99ns      269us      8.19us
118 pthread_rwlock_t Read        761646     933ns      101ns     374us      3.25us
119
120 ---------- 16 threads ------------
121 RWSpinLock       Write       124236     237ns      78ns      261us      801ns
122 RWSpinLock       Read        1115807    236ns      78ns      2.27ms     2.17us
123 RWTicketSpinLock Write       81781      231ns      71ns      31.4us     351ns
124 RWTicketSpinLock Read        734518     238ns      78ns      73.6us     379ns
125 pthread_rwlock_t Write       83363      7.12us     99ns      785us      28.1us
126 pthread_rwlock_t Read        754978     2.18us     101ns     1.02ms     14.3us
127
128 ---------- 50 threads ------------
129 RWSpinLock       Write       131142     1.37us     82ns      7.53ms     68.2us
130 RWSpinLock       Read        1181240    262ns      78ns      6.62ms     12.7us
131 RWTicketSpinLock Write       83045      397ns      73ns      7.01ms     31.5us
132 RWTicketSpinLock Read        744133     386ns      78ns        11ms     31.4us
133 pthread_rwlock_t Write       80849      112us      103ns     4.52ms     263us
134 pthread_rwlock_t Read        728698     24us       101ns     7.28ms     194us
135
136 */
137
138 #include <folly/Portability.h>
139 #include <folly/portability/Asm.h>
140
141 #if defined(__GNUC__) && \
142   (defined(__i386) || FOLLY_X64 || \
143    defined(ARCH_K8))
144 # define RW_SPINLOCK_USE_X86_INTRINSIC_
145 # include <x86intrin.h>
146 #elif defined(_MSC_VER) && defined(FOLLY_X64)
147 # define RW_SPINLOCK_USE_X86_INTRINSIC_
148 #else
149 # undef RW_SPINLOCK_USE_X86_INTRINSIC_
150 #endif
151
152 // iOS doesn't define _mm_cvtsi64_si128 and friends
153 #if (FOLLY_SSE >= 2) && !FOLLY_MOBILE
154 #define RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
155 #else
156 #undef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
157 #endif
158
159 #include <algorithm>
160 #include <atomic>
161 #include <string>
162 #include <thread>
163
164 #include <glog/logging.h>
165
166 #include <folly/Likely.h>
167
168 namespace folly {
169
170 /*
171  * A simple, small (4-bytes), but unfair rwlock.  Use it when you want
172  * a nice writer and don't expect a lot of write/read contention, or
173  * when you need small rwlocks since you are creating a large number
174  * of them.
175  *
176  * Note that the unfairness here is extreme: if the lock is
177  * continually accessed for read, writers will never get a chance.  If
178  * the lock can be that highly contended this class is probably not an
179  * ideal choice anyway.
180  *
181  * It currently implements most of the Lockable, SharedLockable and
182  * UpgradeLockable concepts except the TimedLockable related locking/unlocking
183  * interfaces.
184  */
185 class RWSpinLock {
186   enum : int32_t { READER = 4, UPGRADED = 2, WRITER = 1 };
187  public:
188   constexpr RWSpinLock() : bits_(0) {}
189
190   RWSpinLock(RWSpinLock const&) = delete;
191   RWSpinLock& operator=(RWSpinLock const&) = delete;
192
193   // Lockable Concept
194   void lock() {
195     int count = 0;
196     while (!LIKELY(try_lock())) {
197       if (++count > 1000) std::this_thread::yield();
198     }
199   }
200
201   // Writer is responsible for clearing up both the UPGRADED and WRITER bits.
202   void unlock() {
203     static_assert(READER > WRITER + UPGRADED, "wrong bits!");
204     bits_.fetch_and(~(WRITER | UPGRADED), std::memory_order_release);
205   }
206
207   // SharedLockable Concept
208   void lock_shared() {
209     int count = 0;
210     while (!LIKELY(try_lock_shared())) {
211       if (++count > 1000) std::this_thread::yield();
212     }
213   }
214
215   void unlock_shared() {
216     bits_.fetch_add(-READER, std::memory_order_release);
217   }
218
219   // Downgrade the lock from writer status to reader status.
220   void unlock_and_lock_shared() {
221     bits_.fetch_add(READER, std::memory_order_acquire);
222     unlock();
223   }
224
225   // UpgradeLockable Concept
226   void lock_upgrade() {
227     int count = 0;
228     while (!try_lock_upgrade()) {
229       if (++count > 1000) std::this_thread::yield();
230     }
231   }
232
233   void unlock_upgrade() {
234     bits_.fetch_add(-UPGRADED, std::memory_order_acq_rel);
235   }
236
237   // unlock upgrade and try to acquire write lock
238   void unlock_upgrade_and_lock() {
239     int64_t count = 0;
240     while (!try_unlock_upgrade_and_lock()) {
241       if (++count > 1000) std::this_thread::yield();
242     }
243   }
244
245   // unlock upgrade and read lock atomically
246   void unlock_upgrade_and_lock_shared() {
247     bits_.fetch_add(READER - UPGRADED, std::memory_order_acq_rel);
248   }
249
250   // write unlock and upgrade lock atomically
251   void unlock_and_lock_upgrade() {
252     // need to do it in two steps here -- as the UPGRADED bit might be OR-ed at
253     // the same time when other threads are trying do try_lock_upgrade().
254     bits_.fetch_or(UPGRADED, std::memory_order_acquire);
255     bits_.fetch_add(-WRITER, std::memory_order_release);
256   }
257
258
259   // Attempt to acquire writer permission. Return false if we didn't get it.
260   bool try_lock() {
261     int32_t expect = 0;
262     return bits_.compare_exchange_strong(expect, WRITER,
263       std::memory_order_acq_rel);
264   }
265
266   // Try to get reader permission on the lock. This can fail if we
267   // find out someone is a writer or upgrader.
268   // Setting the UPGRADED bit would allow a writer-to-be to indicate
269   // its intention to write and block any new readers while waiting
270   // for existing readers to finish and release their read locks. This
271   // helps avoid starving writers (promoted from upgraders).
272   bool try_lock_shared() {
273     // fetch_add is considerably (100%) faster than compare_exchange,
274     // so here we are optimizing for the common (lock success) case.
275     int32_t value = bits_.fetch_add(READER, std::memory_order_acquire);
276     if (UNLIKELY(value & (WRITER|UPGRADED))) {
277       bits_.fetch_add(-READER, std::memory_order_release);
278       return false;
279     }
280     return true;
281   }
282
283   // try to unlock upgrade and write lock atomically
284   bool try_unlock_upgrade_and_lock() {
285     int32_t expect = UPGRADED;
286     return bits_.compare_exchange_strong(expect, WRITER,
287         std::memory_order_acq_rel);
288   }
289
290   // try to acquire an upgradable lock.
291   bool try_lock_upgrade() {
292     int32_t value = bits_.fetch_or(UPGRADED, std::memory_order_acquire);
293
294     // Note: when failed, we cannot flip the UPGRADED bit back,
295     // as in this case there is either another upgrade lock or a write lock.
296     // If it's a write lock, the bit will get cleared up when that lock's done
297     // with unlock().
298     return ((value & (UPGRADED | WRITER)) == 0);
299   }
300
301   // mainly for debugging purposes.
302   int32_t bits() const { return bits_.load(std::memory_order_acquire); }
303
304   class ReadHolder;
305   class UpgradedHolder;
306   class WriteHolder;
307
308   class ReadHolder {
309    public:
310     explicit ReadHolder(RWSpinLock* lock = nullptr) : lock_(lock) {
311       if (lock_) lock_->lock_shared();
312     }
313
314     explicit ReadHolder(RWSpinLock& lock) : lock_(&lock) {
315       lock_->lock_shared();
316     }
317
318     ReadHolder(ReadHolder&& other) noexcept : lock_(other.lock_) {
319       other.lock_ = nullptr;
320     }
321
322     // down-grade
323     explicit ReadHolder(UpgradedHolder&& upgraded) : lock_(upgraded.lock_) {
324       upgraded.lock_ = nullptr;
325       if (lock_) lock_->unlock_upgrade_and_lock_shared();
326     }
327
328     explicit ReadHolder(WriteHolder&& writer) : lock_(writer.lock_) {
329       writer.lock_ = nullptr;
330       if (lock_) lock_->unlock_and_lock_shared();
331     }
332
333     ReadHolder& operator=(ReadHolder&& other) {
334       using std::swap;
335       swap(lock_, other.lock_);
336       return *this;
337     }
338
339     ReadHolder(const ReadHolder& other) = delete;
340     ReadHolder& operator=(const ReadHolder& other) = delete;
341
342     ~ReadHolder() { if (lock_) lock_->unlock_shared(); }
343
344     void reset(RWSpinLock* lock = nullptr) {
345       if (lock == lock_) return;
346       if (lock_) lock_->unlock_shared();
347       lock_ = lock;
348       if (lock_) lock_->lock_shared();
349     }
350
351     void swap(ReadHolder* other) {
352       std::swap(lock_, other->lock_);
353     }
354
355    private:
356     friend class UpgradedHolder;
357     friend class WriteHolder;
358     RWSpinLock* lock_;
359   };
360
361   class UpgradedHolder {
362    public:
363     explicit UpgradedHolder(RWSpinLock* lock = nullptr) : lock_(lock) {
364       if (lock_) lock_->lock_upgrade();
365     }
366
367     explicit UpgradedHolder(RWSpinLock& lock) : lock_(&lock) {
368       lock_->lock_upgrade();
369     }
370
371     explicit UpgradedHolder(WriteHolder&& writer) {
372       lock_ = writer.lock_;
373       writer.lock_ = nullptr;
374       if (lock_) lock_->unlock_and_lock_upgrade();
375     }
376
377     UpgradedHolder(UpgradedHolder&& other) noexcept : lock_(other.lock_) {
378       other.lock_ = nullptr;
379     }
380
381     UpgradedHolder& operator =(UpgradedHolder&& other) {
382       using std::swap;
383       swap(lock_, other.lock_);
384       return *this;
385     }
386
387     UpgradedHolder(const UpgradedHolder& other) = delete;
388     UpgradedHolder& operator =(const UpgradedHolder& other) = delete;
389
390     ~UpgradedHolder() { if (lock_) lock_->unlock_upgrade(); }
391
392     void reset(RWSpinLock* lock = nullptr) {
393       if (lock == lock_) return;
394       if (lock_) lock_->unlock_upgrade();
395       lock_ = lock;
396       if (lock_) lock_->lock_upgrade();
397     }
398
399     void swap(UpgradedHolder* other) {
400       using std::swap;
401       swap(lock_, other->lock_);
402     }
403
404    private:
405     friend class WriteHolder;
406     friend class ReadHolder;
407     RWSpinLock* lock_;
408   };
409
410   class WriteHolder {
411    public:
412     explicit WriteHolder(RWSpinLock* lock = nullptr) : lock_(lock) {
413       if (lock_) lock_->lock();
414     }
415
416     explicit WriteHolder(RWSpinLock& lock) : lock_(&lock) {
417       lock_->lock();
418     }
419
420     // promoted from an upgrade lock holder
421     explicit WriteHolder(UpgradedHolder&& upgraded) {
422       lock_ = upgraded.lock_;
423       upgraded.lock_ = nullptr;
424       if (lock_) lock_->unlock_upgrade_and_lock();
425     }
426
427     WriteHolder(WriteHolder&& other) noexcept : lock_(other.lock_) {
428       other.lock_ = nullptr;
429     }
430
431     WriteHolder& operator =(WriteHolder&& other) {
432       using std::swap;
433       swap(lock_, other.lock_);
434       return *this;
435     }
436
437     WriteHolder(const WriteHolder& other) = delete;
438     WriteHolder& operator =(const WriteHolder& other) = delete;
439
440     ~WriteHolder () { if (lock_) lock_->unlock(); }
441
442     void reset(RWSpinLock* lock = nullptr) {
443       if (lock == lock_) return;
444       if (lock_) lock_->unlock();
445       lock_ = lock;
446       if (lock_) lock_->lock();
447     }
448
449     void swap(WriteHolder* other) {
450       using std::swap;
451       swap(lock_, other->lock_);
452     }
453
454    private:
455     friend class ReadHolder;
456     friend class UpgradedHolder;
457     RWSpinLock* lock_;
458   };
459
460  private:
461   std::atomic<int32_t> bits_;
462 };
463
464
465 #ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
466 // A more balanced Read-Write spin lock implemented based on GCC intrinsics.
467
468 namespace detail {
469 template <size_t kBitWidth> struct RWTicketIntTrait {
470   static_assert(kBitWidth == 32 || kBitWidth == 64,
471       "bit width has to be either 32 or 64 ");
472 };
473
474 template <>
475 struct RWTicketIntTrait<64> {
476   typedef uint64_t FullInt;
477   typedef uint32_t HalfInt;
478   typedef uint16_t QuarterInt;
479
480 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
481   static __m128i make128(const uint16_t v[4]) {
482     return _mm_set_epi16(0, 0, 0, 0,
483         short(v[3]), short(v[2]), short(v[1]), short(v[0]));
484   }
485   static inline __m128i fromInteger(uint64_t from) {
486     return _mm_cvtsi64_si128(int64_t(from));
487   }
488   static inline uint64_t toInteger(__m128i in) {
489     return uint64_t(_mm_cvtsi128_si64(in));
490   }
491   static inline uint64_t addParallel(__m128i in, __m128i kDelta) {
492     return toInteger(_mm_add_epi16(in, kDelta));
493   }
494 #endif
495 };
496
497 template <>
498 struct RWTicketIntTrait<32> {
499   typedef uint32_t FullInt;
500   typedef uint16_t HalfInt;
501   typedef uint8_t QuarterInt;
502
503 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
504   static __m128i make128(const uint8_t v[4]) {
505     return _mm_set_epi8(
506         0, 0, 0, 0,
507         0, 0, 0, 0,
508         0, 0, 0, 0,
509         char(v[3]), char(v[2]), char(v[1]), char(v[0]));
510   }
511   static inline __m128i fromInteger(uint32_t from) {
512     return _mm_cvtsi32_si128(int32_t(from));
513   }
514   static inline uint32_t toInteger(__m128i in) {
515     return uint32_t(_mm_cvtsi128_si32(in));
516   }
517   static inline uint32_t addParallel(__m128i in, __m128i kDelta) {
518     return toInteger(_mm_add_epi8(in, kDelta));
519   }
520 #endif
521 };
522 }  // detail
523
524
525 template<size_t kBitWidth, bool kFavorWriter=false>
526 class RWTicketSpinLockT {
527   typedef detail::RWTicketIntTrait<kBitWidth> IntTraitType;
528   typedef typename detail::RWTicketIntTrait<kBitWidth>::FullInt FullInt;
529   typedef typename detail::RWTicketIntTrait<kBitWidth>::HalfInt HalfInt;
530   typedef typename detail::RWTicketIntTrait<kBitWidth>::QuarterInt
531     QuarterInt;
532
533   union RWTicket {
534     constexpr RWTicket() : whole(0) {}
535     FullInt whole;
536     HalfInt readWrite;
537     __extension__ struct {
538       QuarterInt write;
539       QuarterInt read;
540       QuarterInt users;
541     };
542   } ticket;
543
544  private: // Some x64-specific utilities for atomic access to ticket.
545   template<class T> static T load_acquire(T* addr) {
546     T t = *addr; // acquire barrier
547     asm_volatile_memory();
548     return t;
549   }
550
551   template<class T>
552   static void store_release(T* addr, T v) {
553     asm_volatile_memory();
554     *addr = v; // release barrier
555   }
556
557  public:
558
559   constexpr RWTicketSpinLockT() {}
560
561   RWTicketSpinLockT(RWTicketSpinLockT const&) = delete;
562   RWTicketSpinLockT& operator=(RWTicketSpinLockT const&) = delete;
563
564   void lock() {
565     if (kFavorWriter) {
566       writeLockAggressive();
567     } else {
568       writeLockNice();
569     }
570   }
571
572   /*
573    * Both try_lock and try_lock_shared diverge in our implementation from the
574    * lock algorithm described in the link above.
575    *
576    * In the read case, it is undesirable that the readers could wait
577    * for another reader (before increasing ticket.read in the other
578    * implementation).  Our approach gives up on
579    * first-come-first-serve, but our benchmarks showed improve
580    * performance for both readers and writers under heavily contended
581    * cases, particularly when the number of threads exceeds the number
582    * of logical CPUs.
583    *
584    * We have writeLockAggressive() using the original implementation
585    * for a writer, which gives some advantage to the writer over the
586    * readers---for that path it is guaranteed that the writer will
587    * acquire the lock after all the existing readers exit.
588    */
589   bool try_lock() {
590     RWTicket t;
591     FullInt old = t.whole = load_acquire(&ticket.whole);
592     if (t.users != t.write) return false;
593     ++t.users;
594     return __sync_bool_compare_and_swap(&ticket.whole, old, t.whole);
595   }
596
597   /*
598    * Call this if you want to prioritize writer to avoid starvation.
599    * Unlike writeLockNice, immediately acquires the write lock when
600    * the existing readers (arriving before the writer) finish their
601    * turns.
602    */
603   void writeLockAggressive() {
604     // std::this_thread::yield() is needed here to avoid a pathology if the number
605     // of threads attempting concurrent writes is >= the number of real
606     // cores allocated to this process. This is less likely than the
607     // corresponding situation in lock_shared(), but we still want to
608     // avoid it
609     int count = 0;
610     QuarterInt val = __sync_fetch_and_add(&ticket.users, 1);
611     while (val != load_acquire(&ticket.write)) {
612       asm_volatile_pause();
613       if (UNLIKELY(++count > 1000)) std::this_thread::yield();
614     }
615   }
616
617   // Call this when the writer should be nicer to the readers.
618   void writeLockNice() {
619     // Here it doesn't cpu-relax the writer.
620     //
621     // This is because usually we have many more readers than the
622     // writers, so the writer has less chance to get the lock when
623     // there are a lot of competing readers.  The aggressive spinning
624     // can help to avoid starving writers.
625     //
626     // We don't worry about std::this_thread::yield() here because the caller
627     // has already explicitly abandoned fairness.
628     while (!try_lock()) {}
629   }
630
631   // Atomically unlock the write-lock from writer and acquire the read-lock.
632   void unlock_and_lock_shared() {
633     QuarterInt val = __sync_fetch_and_add(&ticket.read, 1);
634   }
635
636   // Release writer permission on the lock.
637   void unlock() {
638     RWTicket t;
639     t.whole = load_acquire(&ticket.whole);
640     FullInt old = t.whole;
641
642 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
643     // SSE2 can reduce the lock and unlock overhead by 10%
644     static const QuarterInt kDeltaBuf[4] = { 1, 1, 0, 0 };   // write/read/user
645     static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
646     __m128i m = IntTraitType::fromInteger(old);
647     t.whole = IntTraitType::addParallel(m, kDelta);
648 #else
649     ++t.read;
650     ++t.write;
651 #endif
652     store_release(&ticket.readWrite, t.readWrite);
653   }
654
655   void lock_shared() {
656     // std::this_thread::yield() is important here because we can't grab the
657     // shared lock if there is a pending writeLockAggressive, so we
658     // need to let threads that already have a shared lock complete
659     int count = 0;
660     while (!LIKELY(try_lock_shared())) {
661       asm_volatile_pause();
662       if (UNLIKELY((++count & 1023) == 0)) std::this_thread::yield();
663     }
664   }
665
666   bool try_lock_shared() {
667     RWTicket t, old;
668     old.whole = t.whole = load_acquire(&ticket.whole);
669     old.users = old.read;
670 #ifdef RW_SPINLOCK_USE_SSE_INSTRUCTIONS_
671     // SSE2 may reduce the total lock and unlock overhead by 10%
672     static const QuarterInt kDeltaBuf[4] = { 0, 1, 1, 0 };   // write/read/user
673     static const __m128i kDelta = IntTraitType::make128(kDeltaBuf);
674     __m128i m = IntTraitType::fromInteger(old.whole);
675     t.whole = IntTraitType::addParallel(m, kDelta);
676 #else
677     ++t.read;
678     ++t.users;
679 #endif
680     return __sync_bool_compare_and_swap(&ticket.whole, old.whole, t.whole);
681   }
682
683   void unlock_shared() {
684     QuarterInt val = __sync_fetch_and_add(&ticket.write, 1);
685   }
686
687   class WriteHolder;
688
689   typedef RWTicketSpinLockT<kBitWidth, kFavorWriter> RWSpinLock;
690   class ReadHolder {
691    public:
692     ReadHolder(ReadHolder const&) = delete;
693     ReadHolder& operator=(ReadHolder const&) = delete;
694
695     explicit ReadHolder(RWSpinLock *lock = nullptr) :
696       lock_(lock) {
697       if (lock_) lock_->lock_shared();
698     }
699
700     explicit ReadHolder(RWSpinLock &lock) : lock_ (&lock) {
701       if (lock_) lock_->lock_shared();
702     }
703
704     // atomically unlock the write-lock from writer and acquire the read-lock
705     explicit ReadHolder(WriteHolder *writer) : lock_(nullptr) {
706       std::swap(this->lock_, writer->lock_);
707       if (lock_) {
708         lock_->unlock_and_lock_shared();
709       }
710     }
711
712     ~ReadHolder() {
713       if (lock_) lock_->unlock_shared();
714     }
715
716     void reset(RWSpinLock *lock = nullptr) {
717       if (lock_) lock_->unlock_shared();
718       lock_ = lock;
719       if (lock_) lock_->lock_shared();
720     }
721
722     void swap(ReadHolder *other) {
723       std::swap(this->lock_, other->lock_);
724     }
725
726    private:
727     RWSpinLock *lock_;
728   };
729
730   class WriteHolder {
731    public:
732     WriteHolder(WriteHolder const&) = delete;
733     WriteHolder& operator=(WriteHolder const&) = delete;
734
735     explicit WriteHolder(RWSpinLock *lock = nullptr) : lock_(lock) {
736       if (lock_) lock_->lock();
737     }
738     explicit WriteHolder(RWSpinLock &lock) : lock_ (&lock) {
739       if (lock_) lock_->lock();
740     }
741
742     ~WriteHolder() {
743       if (lock_) lock_->unlock();
744     }
745
746     void reset(RWSpinLock *lock = nullptr) {
747       if (lock == lock_) return;
748       if (lock_) lock_->unlock();
749       lock_ = lock;
750       if (lock_) lock_->lock();
751     }
752
753     void swap(WriteHolder *other) {
754       std::swap(this->lock_, other->lock_);
755     }
756
757    private:
758     friend class ReadHolder;
759     RWSpinLock *lock_;
760   };
761 };
762
763 typedef RWTicketSpinLockT<32> RWTicketSpinLock32;
764 typedef RWTicketSpinLockT<64> RWTicketSpinLock64;
765
766 #endif  // RW_SPINLOCK_USE_X86_INTRINSIC_
767
768 }  // namespace folly
769
770 #ifdef RW_SPINLOCK_USE_X86_INTRINSIC_
771 #undef RW_SPINLOCK_USE_X86_INTRINSIC_
772 #endif