folly/RWSpinLock.h

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