folly/MPMCQueue.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 #pragma once
  18
  19 #include <algorithm>
  20 #include <atomic>
  21 #include <cassert>
  22 #include <cstring>
  23 #include <limits>
  24 #include <type_traits>
  25
  26 #include <boost/noncopyable.hpp>
  27
  28 #include <folly/Traits.h>
  29 #include <folly/concurrency/CacheLocality.h>
  30 #include <folly/detail/TurnSequencer.h>
  31 #include <folly/portability/Unistd.h>
  32
  33 namespace folly {
  34
  35 namespace detail {
  36
  37 template <typename T, template <typename> class Atom>
  38 struct SingleElementQueue;
  39
  40 template <typename T> class MPMCPipelineStageImpl;
  41
  42 /// MPMCQueue base CRTP template
  43 template <typename> class MPMCQueueBase;
  44
  45 } // namespace detail
  46
  47 /// MPMCQueue<T> is a high-performance bounded concurrent queue that
  48 /// supports multiple producers, multiple consumers, and optional blocking.
  49 /// The queue has a fixed capacity, for which all memory will be allocated
  50 /// up front.  The bulk of the work of enqueuing and dequeuing can be
  51 /// performed in parallel.
  52 ///
  53 /// MPMCQueue is linearizable.  That means that if a call to write(A)
  54 /// returns before a call to write(B) begins, then A will definitely end up
  55 /// in the queue before B, and if a call to read(X) returns before a call
  56 /// to read(Y) is started, that X will be something from earlier in the
  57 /// queue than Y.  This also means that if a read call returns a value, you
  58 /// can be sure that all previous elements of the queue have been assigned
  59 /// a reader (that reader might not yet have returned, but it exists).
  60 ///
  61 /// The underlying implementation uses a ticket dispenser for the head and
  62 /// the tail, spreading accesses across N single-element queues to produce
  63 /// a queue with capacity N.  The ticket dispensers use atomic increment,
  64 /// which is more robust to contention than a CAS loop.  Each of the
  65 /// single-element queues uses its own CAS to serialize access, with an
  66 /// adaptive spin cutoff.  When spinning fails on a single-element queue
  67 /// it uses futex()'s _BITSET operations to reduce unnecessary wakeups
  68 /// even if multiple waiters are present on an individual queue (such as
  69 /// when the MPMCQueue's capacity is smaller than the number of enqueuers
  70 /// or dequeuers).
  71 ///
  72 /// In benchmarks (contained in tao/queues/ConcurrentQueueTests)
  73 /// it handles 1 to 1, 1 to N, N to 1, and N to M thread counts better
  74 /// than any of the alternatives present in fbcode, for both small (~10)
  75 /// and large capacities.  In these benchmarks it is also faster than
  76 /// tbb::concurrent_bounded_queue for all configurations.  When there are
  77 /// many more threads than cores, MPMCQueue is _much_ faster than the tbb
  78 /// queue because it uses futex() to block and unblock waiting threads,
  79 /// rather than spinning with sched_yield.
  80 ///
  81 /// NOEXCEPT INTERACTION: tl;dr; If it compiles you're fine.  Ticket-based
  82 /// queues separate the assignment of queue positions from the actual
  83 /// construction of the in-queue elements, which means that the T
  84 /// constructor used during enqueue must not throw an exception.  This is
  85 /// enforced at compile time using type traits, which requires that T be
  86 /// adorned with accurate noexcept information.  If your type does not
  87 /// use noexcept, you will have to wrap it in something that provides
  88 /// the guarantee.  We provide an alternate safe implementation for types
  89 /// that don't use noexcept but that are marked folly::IsRelocatable
  90 /// and std::is_nothrow_constructible, which is common for folly types.
  91 /// In particular, if you can declare FOLLY_ASSUME_FBVECTOR_COMPATIBLE
  92 /// then your type can be put in MPMCQueue.
  93 ///
  94 /// If you have a pool of N queue consumers that you want to shut down
  95 /// after the queue has drained, one way is to enqueue N sentinel values
  96 /// to the queue.  If the producer doesn't know how many consumers there
  97 /// are you can enqueue one sentinel and then have each consumer requeue
  98 /// two sentinels after it receives it (by requeuing 2 the shutdown can
  99 /// complete in O(log P) time instead of O(P)).
 100 template <
 101     typename T,
 102     template <typename> class Atom = std::atomic,
 103     bool Dynamic = false>
 104 class MPMCQueue : public detail::MPMCQueueBase<MPMCQueue<T,Atom,Dynamic>> {
 105   friend class detail::MPMCPipelineStageImpl<T>;
 106   using Slot = detail::SingleElementQueue<T,Atom>;
 107  public:
 108
 109   explicit MPMCQueue(size_t queueCapacity)
 110     : detail::MPMCQueueBase<MPMCQueue<T,Atom,Dynamic>>(queueCapacity)
 111   {
 112     this->stride_ = this->computeStride(queueCapacity);
 113     this->slots_ = new Slot[queueCapacity + 2 * this->kSlotPadding];
 114   }
 115
 116   MPMCQueue() noexcept { }
 117 };
 118
 119 /// The dynamic version of MPMCQueue allows dynamic expansion of queue
 120 /// capacity, such that a queue may start with a smaller capacity than
 121 /// specified and expand only if needed. Users may optionally specify
 122 /// the initial capacity and the expansion multiplier.
 123 ///
 124 /// The design uses a seqlock to enforce mutual exclusion among
 125 /// expansion attempts. Regular operations read up-to-date queue
 126 /// information (slots array, capacity, stride) inside read-only
 127 /// seqlock sections, which are unimpeded when no expansion is in
 128 /// progress.
 129 ///
 130 /// An expansion computes a new capacity, allocates a new slots array,
 131 /// and updates stride. No information needs to be copied from the
 132 /// current slots array to the new one. When this happens, new slots
 133 /// will not have sequence numbers that match ticket numbers. The
 134 /// expansion needs to compute a ticket offset such that operations
 135 /// that use new arrays can adjust the calculations of slot indexes
 136 /// and sequence numbers that take into account that the new slots
 137 /// start with sequence numbers of zero. The current ticket offset is
 138 /// packed with the seqlock in an atomic 64-bit integer. The initial
 139 /// offset is zero.
 140 ///
 141 /// Lagging write and read operations with tickets lower than the
 142 /// ticket offset of the current slots array (i.e., the minimum ticket
 143 /// number that can be served by the current array) must use earlier
 144 /// closed arrays instead of the current one. Information about closed
 145 /// slots arrays (array address, capacity, stride, and offset) is
 146 /// maintained in a logarithmic-sized structure. Each entry in that
 147 /// structure never need to be changed once set. The number of closed
 148 /// arrays is half the value of the seqlock (when unlocked).
 149 ///
 150 /// The acquisition of the seqlock to perform an expansion does not
 151 /// prevent the issuing of new push and pop tickets concurrently. The
 152 /// expansion must set the new ticket offset to a value that couldn't
 153 /// have been issued to an operation that has already gone through a
 154 /// seqlock read-only section (and hence obtained information for
 155 /// older closed arrays).
 156 ///
 157 /// Note that the total queue capacity can temporarily exceed the
 158 /// specified capacity when there are lagging consumers that haven't
 159 /// yet consumed all the elements in closed arrays. Users should not
 160 /// rely on the capacity of dynamic queues for synchronization, e.g.,
 161 /// they should not expect that a thread will definitely block on a
 162 /// call to blockingWrite() when the queue size is known to be equal
 163 /// to its capacity.
 164 ///
 165 /// Note that some writeIfNotFull() and tryWriteUntil() operations may
 166 /// fail even if the size of the queue is less than its maximum
 167 /// capacity and despite the success of expansion, if the operation
 168 /// happens to acquire a ticket that belongs to a closed array. This
 169 /// is a transient condition. Typically, one or two ticket values may
 170 /// be subject to such condition per expansion.
 171 ///
 172 /// The dynamic version is a partial specialization of MPMCQueue with
 173 /// Dynamic == true
 174 template <typename T, template <typename> class Atom>
 175 class MPMCQueue<T,Atom,true> :
 176       public detail::MPMCQueueBase<MPMCQueue<T,Atom,true>> {
 177   friend class detail::MPMCQueueBase<MPMCQueue<T,Atom,true>>;
 178   using Slot = detail::SingleElementQueue<T,Atom>;
 179
 180   struct ClosedArray {
 181     uint64_t offset_ {0};
 182     Slot* slots_ {nullptr};
 183     size_t capacity_ {0};
 184     int stride_ {0};
 185   };
 186
 187  public:
 188
 189   explicit MPMCQueue(size_t queueCapacity)
 190     : detail::MPMCQueueBase<MPMCQueue<T,Atom,true>>(queueCapacity)
 191   {
 192     size_t cap = std::min<size_t>(kDefaultMinDynamicCapacity, queueCapacity);
 193     initQueue(cap, kDefaultExpansionMultiplier);
 194   }
 195
 196   explicit MPMCQueue(size_t queueCapacity,
 197                      size_t minCapacity,
 198                      size_t expansionMultiplier)
 199     : detail::MPMCQueueBase<MPMCQueue<T,Atom,true>>(queueCapacity)
 200   {
 201     minCapacity = std::max<size_t>(1, minCapacity);
 202     size_t cap = std::min<size_t>(minCapacity, queueCapacity);
 203     expansionMultiplier = std::max<size_t>(2, expansionMultiplier);
 204     initQueue(cap, expansionMultiplier);
 205   }
 206
 207   MPMCQueue() noexcept {
 208     dmult_ = 0;
 209     closed_ = nullptr;
 210   }
 211
 212   MPMCQueue(MPMCQueue<T,Atom,true>&& rhs) noexcept {
 213     this->capacity_ = rhs.capacity_;
 214     this->slots_ = rhs.slots_;
 215     this->stride_ = rhs.stride_;
 216     this->dstate_.store(rhs.dstate_.load(std::memory_order_relaxed),
 217                         std::memory_order_relaxed);
 218     this->dcapacity_.store(rhs.dcapacity_.load(std::memory_order_relaxed),
 219                            std::memory_order_relaxed);
 220     this->pushTicket_.store(rhs.pushTicket_.load(std::memory_order_relaxed),
 221                             std::memory_order_relaxed);
 222     this->popTicket_.store(rhs.popTicket_.load(std::memory_order_relaxed),
 223                            std::memory_order_relaxed);
 224     this->pushSpinCutoff_.store(
 225       rhs.pushSpinCutoff_.load(std::memory_order_relaxed),
 226       std::memory_order_relaxed);
 227     this->popSpinCutoff_.store(
 228       rhs.popSpinCutoff_.load(std::memory_order_relaxed),
 229       std::memory_order_relaxed);
 230     dmult_ = rhs.dmult_;
 231     closed_ = rhs.closed_;
 232
 233     rhs.capacity_ = 0;
 234     rhs.slots_ = nullptr;
 235     rhs.stride_ = 0;
 236     rhs.dstate_.store(0, std::memory_order_relaxed);
 237     rhs.dcapacity_.store(0, std::memory_order_relaxed);
 238     rhs.pushTicket_.store(0, std::memory_order_relaxed);
 239     rhs.popTicket_.store(0, std::memory_order_relaxed);
 240     rhs.pushSpinCutoff_.store(0, std::memory_order_relaxed);
 241     rhs.popSpinCutoff_.store(0, std::memory_order_relaxed);
 242     rhs.dmult_ = 0;
 243     rhs.closed_ = nullptr;
 244   }
 245
 246   MPMCQueue<T,Atom, true> const& operator= (MPMCQueue<T,Atom, true>&& rhs) {
 247     if (this != &rhs) {
 248       this->~MPMCQueue();
 249       new (this) MPMCQueue(std::move(rhs));
 250     }
 251     return *this;
 252   }
 253
 254   ~MPMCQueue() {
 255     if (closed_ != nullptr) {
 256       for (int i = getNumClosed(this->dstate_.load()) - 1; i >= 0; --i) {
 257         delete[] closed_[i].slots_;
 258       }
 259       delete[] closed_;
 260     }
 261   }
 262
 263   size_t allocatedCapacity() const noexcept {
 264     return this->dcapacity_.load(std::memory_order_relaxed);
 265   }
 266
 267   template <typename ...Args>
 268   void blockingWrite(Args&&... args) noexcept {
 269     uint64_t ticket = this->pushTicket_++;
 270     Slot* slots;
 271     size_t cap;
 272     int stride;
 273     uint64_t state;
 274     uint64_t offset;
 275     do {
 276       if (!trySeqlockReadSection(state, slots, cap, stride)) {
 277         asm_volatile_pause();
 278         continue;
 279       }
 280       if (maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride)) {
 281         // There was an expansion after this ticket was issued.
 282         break;
 283       }
 284       if (slots[this->idx((ticket-offset), cap, stride)]
 285           .mayEnqueue(this->turn(ticket-offset, cap))) {
 286         // A slot is ready. No need to expand.
 287         break;
 288       } else if (this->popTicket_.load(std::memory_order_relaxed) + cap
 289                  > ticket) {
 290         // May block, but a pop is in progress. No need to expand.
 291         // Get seqlock read section info again in case an expansion
 292         // occurred with an equal or higher ticket.
 293         continue;
 294       } else {
 295         // May block. See if we can expand.
 296         if (tryExpand(state, cap)) {
 297           // This or another thread started an expansion. Get updated info.
 298           continue;
 299         } else {
 300           // Can't expand.
 301           break;
 302         }
 303       }
 304     } while (true);
 305     this->enqueueWithTicketBase(ticket-offset, slots, cap, stride,
 306                                 std::forward<Args>(args)...);
 307   }
 308
 309   void blockingReadWithTicket(uint64_t& ticket, T& elem) noexcept {
 310     ticket = this->popTicket_++;
 311     Slot* slots;
 312     size_t cap;
 313     int stride;
 314     uint64_t state;
 315     uint64_t offset;
 316     while (!trySeqlockReadSection(state, slots, cap, stride)) {
 317       asm_volatile_pause();
 318     }
 319     // If there was an expansion after the corresponding push ticket
 320     // was issued, adjust accordingly
 321     maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 322     this->dequeueWithTicketBase(ticket-offset, slots, cap, stride, elem);
 323   }
 324
 325  private:
 326
 327   enum {
 328     kSeqlockBits = 6,
 329     kDefaultMinDynamicCapacity = 10,
 330     kDefaultExpansionMultiplier = 10,
 331   };
 332
 333   size_t dmult_;
 334
 335   //  Info about closed slots arrays for use by lagging operations
 336   ClosedArray* closed_;
 337
 338   void initQueue(const size_t cap, const size_t mult) {
 339     this->stride_ = this->computeStride(cap);
 340     this->slots_ = new Slot[cap + 2 * this->kSlotPadding];
 341     this->dstate_.store(0);
 342     this->dcapacity_.store(cap);
 343     dmult_ = mult;
 344     size_t maxClosed = 0;
 345     for (size_t expanded = cap;
 346          expanded < this->capacity_;
 347          expanded *= mult) {
 348       ++maxClosed;
 349     }
 350     closed_ = (maxClosed > 0) ? new ClosedArray[maxClosed] : nullptr;
 351   }
 352
 353   bool tryObtainReadyPushTicket(
 354       uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
 355   ) noexcept {
 356     uint64_t state;
 357     do {
 358       ticket = this->pushTicket_.load(std::memory_order_acquire); // A
 359       if (!trySeqlockReadSection(state, slots, cap, stride)) {
 360         asm_volatile_pause();
 361         continue;
 362       }
 363
 364       // If there was an expansion with offset greater than this ticket,
 365       // adjust accordingly
 366       uint64_t offset;
 367       maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 368
 369       if (slots[this->idx((ticket-offset), cap, stride)]
 370           .mayEnqueue(this->turn(ticket-offset, cap))) {
 371         // A slot is ready.
 372         if (this->pushTicket_.compare_exchange_strong(ticket, ticket + 1)) {
 373           // Adjust ticket
 374           ticket -= offset;
 375           return true;
 376         } else {
 377           continue;
 378         }
 379       } else {
 380         if (ticket != this->pushTicket_.load(std::memory_order_relaxed)) { // B
 381           // Try again. Ticket changed.
 382           continue;
 383         }
 384         // Likely to block.
 385         // Try to expand unless the ticket is for a closed array
 386         if (offset == getOffset(state)) {
 387           if (tryExpand(state, cap)) {
 388             // This or another thread started an expansion. Get up-to-date info.
 389             continue;
 390           }
 391         }
 392         return false;
 393       }
 394     } while (true);
 395   }
 396
 397   bool tryObtainPromisedPushTicket(
 398     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
 399   ) noexcept {
 400     uint64_t state;
 401     do {
 402       ticket = this->pushTicket_.load(std::memory_order_acquire);
 403       auto numPops = this->popTicket_.load(std::memory_order_acquire);
 404       if (!trySeqlockReadSection(state, slots, cap, stride)) {
 405         asm_volatile_pause();
 406         continue;
 407       }
 408
 409       const auto curCap = cap;
 410       // If there was an expansion with offset greater than this ticket,
 411       // adjust accordingly
 412       uint64_t offset;
 413       maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 414
 415       int64_t n = ticket - numPops;
 416
 417       if (n >= static_cast<ssize_t>(cap)) {
 418         if ((cap == curCap) && tryExpand(state, cap)) {
 419           // This or another thread started an expansion. Start over.
 420           continue;
 421         }
 422         // Can't expand.
 423         ticket -= offset;
 424         return false;
 425       }
 426
 427       if (this->pushTicket_.compare_exchange_strong(ticket, ticket + 1)) {
 428         // Adjust ticket
 429         ticket -= offset;
 430         return true;
 431       }
 432     } while (true);
 433   }
 434
 435   bool tryObtainReadyPopTicket(
 436     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
 437   ) noexcept {
 438     uint64_t state;
 439     do {
 440       ticket = this->popTicket_.load(std::memory_order_relaxed);
 441       if (!trySeqlockReadSection(state, slots, cap, stride)) {
 442         asm_volatile_pause();
 443         continue;
 444       }
 445
 446       // If there was an expansion after the corresponding push ticket
 447       // was issued, adjust accordingly
 448       uint64_t offset;
 449       maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 450
 451       if (slots[this->idx((ticket-offset), cap, stride)]
 452           .mayDequeue(this->turn(ticket-offset, cap))) {
 453         if (this->popTicket_.compare_exchange_strong(ticket, ticket + 1)) {
 454           // Adjust ticket
 455           ticket -= offset;
 456           return true;
 457         }
 458       } else {
 459         return false;
 460       }
 461     } while (true);
 462   }
 463
 464   bool tryObtainPromisedPopTicket(
 465     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
 466   ) noexcept {
 467     uint64_t state;
 468     do {
 469       ticket = this->popTicket_.load(std::memory_order_acquire);
 470       auto numPushes = this->pushTicket_.load(std::memory_order_acquire);
 471       if (!trySeqlockReadSection(state, slots, cap, stride)) {
 472         asm_volatile_pause();
 473         continue;
 474       }
 475
 476       uint64_t offset;
 477       // If there was an expansion after the corresponding push
 478       // ticket was issued, adjust accordingly
 479       maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 480
 481       if (ticket >= numPushes) {
 482         ticket -= offset;
 483         return false;
 484       }
 485       if (this->popTicket_.compare_exchange_strong(ticket, ticket + 1)) {
 486         ticket -= offset;
 487         return true;
 488       }
 489     } while (true);
 490   }
 491
 492   /// Enqueues an element with a specific ticket number
 493   template <typename ...Args>
 494   void enqueueWithTicket(const uint64_t ticket, Args&&... args) noexcept {
 495     Slot* slots;
 496     size_t cap;
 497     int stride;
 498     uint64_t state;
 499     uint64_t offset;
 500
 501     while (!trySeqlockReadSection(state, slots, cap, stride)) {}
 502
 503     // If there was an expansion after this ticket was issued, adjust
 504     // accordingly
 505     maybeUpdateFromClosed(state, ticket, offset, slots, cap, stride);
 506
 507     this->enqueueWithTicketBase(ticket-offset, slots, cap, stride,
 508                                 std::forward<Args>(args)...);
 509   }
 510
 511   uint64_t getOffset(const uint64_t state) const noexcept {
 512     return state >> kSeqlockBits;
 513   }
 514
 515   int getNumClosed(const uint64_t state) const noexcept {
 516     return (state & ((1 << kSeqlockBits) - 1)) >> 1;
 517   }
 518
 519   /// Try to expand the queue. Returns true if this expansion was
 520   /// successful or a concurent expansion is in progress. Returns
 521   /// false if the queue has reached its maximum capacity or
 522   /// allocation has failed.
 523   bool tryExpand(const uint64_t state, const size_t cap) noexcept {
 524     if (cap == this->capacity_) {
 525       return false;
 526     }
 527     // Acquire seqlock
 528     uint64_t oldval = state;
 529     assert((state & 1) == 0);
 530     if (this->dstate_.compare_exchange_strong(oldval, state + 1)) {
 531       assert(cap == this->dcapacity_.load());
 532       uint64_t ticket = 1 + std::max(this->pushTicket_.load(),
 533                                      this->popTicket_.load());
 534       size_t newCapacity =
 535         std::min(dmult_ * cap, this->capacity_);
 536       Slot* newSlots =
 537         new (std::nothrow) Slot[newCapacity + 2 * this->kSlotPadding];
 538       if (newSlots == nullptr) {
 539         // Expansion failed. Restore the seqlock
 540         this->dstate_.store(state);
 541         return false;
 542       }
 543       // Successful expansion
 544       // calculate the current ticket offset
 545       uint64_t offset = getOffset(state);
 546       // calculate index in closed array
 547       int index = getNumClosed(state);
 548       assert((index << 1) < (1 << kSeqlockBits));
 549       // fill the info for the closed slots array
 550       closed_[index].offset_ = offset;
 551       closed_[index].slots_ = this->dslots_.load();
 552       closed_[index].capacity_ = cap;
 553       closed_[index].stride_ = this->dstride_.load();
 554       // update the new slots array info
 555       this->dslots_.store(newSlots);
 556       this->dcapacity_.store(newCapacity);
 557       this->dstride_.store(this->computeStride(newCapacity));
 558       // Release the seqlock and record the new ticket offset
 559       this->dstate_.store((ticket << kSeqlockBits) + (2 * (index + 1)));
 560       return true;
 561     } else { // failed to acquire seqlock
 562       // Someone acaquired the seqlock. Go back to the caller and get
 563       // up-to-date info.
 564       return true;
 565     }
 566   }
 567
 568   /// Seqlock read-only section
 569   bool trySeqlockReadSection(
 570     uint64_t& state, Slot*& slots, size_t& cap, int& stride
 571   ) noexcept {
 572     state = this->dstate_.load(std::memory_order_acquire);
 573     if (state & 1) {
 574       // Locked.
 575       return false;
 576     }
 577     // Start read-only section.
 578     slots = this->dslots_.load(std::memory_order_relaxed);
 579     cap = this->dcapacity_.load(std::memory_order_relaxed);
 580     stride = this->dstride_.load(std::memory_order_relaxed);
 581     // End of read-only section. Validate seqlock.
 582     std::atomic_thread_fence(std::memory_order_acquire);
 583     return (state == this->dstate_.load(std::memory_order_relaxed));
 584   }
 585
 586   /// If there was an expansion after ticket was issued, update local variables
 587   /// of the lagging operation using the most recent closed array with
 588   /// offset <= ticket and return true. Otherwise, return false;
 589   bool maybeUpdateFromClosed(
 590       const uint64_t state,
 591       const uint64_t ticket,
 592       uint64_t& offset,
 593       Slot*& slots,
 594       size_t& cap,
 595       int& stride) noexcept {
 596     offset = getOffset(state);
 597     if (ticket >= offset) {
 598       return false;
 599     }
 600     for (int i = getNumClosed(state) - 1; i >= 0; --i) {
 601       offset = closed_[i].offset_;
 602       if (offset <= ticket) {
 603         slots = closed_[i].slots_;
 604         cap = closed_[i].capacity_;
 605         stride = closed_[i].stride_;
 606         return true;
 607       }
 608     }
 609     // A closed array with offset <= ticket should have been found
 610     assert(false);
 611     return false;
 612   }
 613 };
 614
 615 namespace detail {
 616
 617 /// CRTP specialization of MPMCQueueBase
 618 template <
 619     template <typename T, template <typename> class Atom, bool Dynamic>
 620     class Derived,
 621     typename T,
 622     template <typename> class Atom,
 623     bool Dynamic>
 624 class MPMCQueueBase<Derived<T, Atom, Dynamic>> : boost::noncopyable {
 625
 626 // Note: Using CRTP static casts in several functions of this base
 627 // template instead of making called functions virtual or duplicating
 628 // the code of calling functions in the derived partially specialized
 629 // template
 630
 631   static_assert(std::is_nothrow_constructible<T,T&&>::value ||
 632                 folly::IsRelocatable<T>::value,
 633       "T must be relocatable or have a noexcept move constructor");
 634
 635  public:
 636   typedef T value_type;
 637
 638   using Slot = detail::SingleElementQueue<T,Atom>;
 639
 640   explicit MPMCQueueBase(size_t queueCapacity)
 641     : capacity_(queueCapacity)
 642     , pushTicket_(0)
 643     , popTicket_(0)
 644     , pushSpinCutoff_(0)
 645     , popSpinCutoff_(0)
 646   {
 647     if (queueCapacity == 0) {
 648       throw std::invalid_argument(
 649         "MPMCQueue with explicit capacity 0 is impossible"
 650         // Stride computation in derived classes would sigfpe if capacity is 0
 651       );
 652     }
 653
 654     // ideally this would be a static assert, but g++ doesn't allow it
 655     assert(alignof(MPMCQueue<T, Atom>) >= CacheLocality::kFalseSharingRange);
 656     assert(
 657         static_cast<uint8_t*>(static_cast<void*>(&popTicket_)) -
 658             static_cast<uint8_t*>(static_cast<void*>(&pushTicket_)) >=
 659         CacheLocality::kFalseSharingRange);
 660   }
 661
 662   /// A default-constructed queue is useful because a usable (non-zero
 663   /// capacity) queue can be moved onto it or swapped with it
 664   MPMCQueueBase() noexcept
 665     : capacity_(0)
 666     , slots_(nullptr)
 667     , stride_(0)
 668     , dstate_(0)
 669     , dcapacity_(0)
 670     , pushTicket_(0)
 671     , popTicket_(0)
 672     , pushSpinCutoff_(0)
 673     , popSpinCutoff_(0)
 674   {}
 675
 676   /// IMPORTANT: The move constructor is here to make it easier to perform
 677   /// the initialization phase, it is not safe to use when there are any
 678   /// concurrent accesses (this is not checked).
 679   MPMCQueueBase(MPMCQueueBase<Derived<T,Atom,Dynamic>>&& rhs) noexcept
 680     : capacity_(rhs.capacity_)
 681     , slots_(rhs.slots_)
 682     , stride_(rhs.stride_)
 683     , dstate_(rhs.dstate_.load(std::memory_order_relaxed))
 684     , dcapacity_(rhs.dcapacity_.load(std::memory_order_relaxed))
 685     , pushTicket_(rhs.pushTicket_.load(std::memory_order_relaxed))
 686     , popTicket_(rhs.popTicket_.load(std::memory_order_relaxed))
 687     , pushSpinCutoff_(rhs.pushSpinCutoff_.load(std::memory_order_relaxed))
 688     , popSpinCutoff_(rhs.popSpinCutoff_.load(std::memory_order_relaxed))
 689   {
 690     // relaxed ops are okay for the previous reads, since rhs queue can't
 691     // be in concurrent use
 692
 693     // zero out rhs
 694     rhs.capacity_ = 0;
 695     rhs.slots_ = nullptr;
 696     rhs.stride_ = 0;
 697     rhs.dstate_.store(0, std::memory_order_relaxed);
 698     rhs.dcapacity_.store(0, std::memory_order_relaxed);
 699     rhs.pushTicket_.store(0, std::memory_order_relaxed);
 700     rhs.popTicket_.store(0, std::memory_order_relaxed);
 701     rhs.pushSpinCutoff_.store(0, std::memory_order_relaxed);
 702     rhs.popSpinCutoff_.store(0, std::memory_order_relaxed);
 703   }
 704
 705   /// IMPORTANT: The move operator is here to make it easier to perform
 706   /// the initialization phase, it is not safe to use when there are any
 707   /// concurrent accesses (this is not checked).
 708   MPMCQueueBase<Derived<T,Atom,Dynamic>> const& operator=
 709     (MPMCQueueBase<Derived<T,Atom,Dynamic>>&& rhs) {
 710     if (this != &rhs) {
 711       this->~MPMCQueueBase();
 712       new (this) MPMCQueueBase(std::move(rhs));
 713     }
 714     return *this;
 715   }
 716
 717   /// MPMCQueue can only be safely destroyed when there are no
 718   /// pending enqueuers or dequeuers (this is not checked).
 719   ~MPMCQueueBase() {
 720     delete[] slots_;
 721   }
 722
 723   /// Returns the number of writes (including threads that are blocked waiting
 724   /// to write) minus the number of reads (including threads that are blocked
 725   /// waiting to read). So effectively, it becomes:
 726   /// elements in queue + pending(calls to write) - pending(calls to read).
 727   /// If nothing is pending, then the method returns the actual number of
 728   /// elements in the queue.
 729   /// The returned value can be negative if there are no writers and the queue
 730   /// is empty, but there is one reader that is blocked waiting to read (in
 731   /// which case, the returned size will be -1).
 732   ssize_t size() const noexcept {
 733     // since both pushes and pops increase monotonically, we can get a
 734     // consistent snapshot either by bracketing a read of popTicket_ with
 735     // two reads of pushTicket_ that return the same value, or the other
 736     // way around.  We maximize our chances by alternately attempting
 737     // both bracketings.
 738     uint64_t pushes = pushTicket_.load(std::memory_order_acquire); // A
 739     uint64_t pops = popTicket_.load(std::memory_order_acquire); // B
 740     while (true) {
 741       uint64_t nextPushes = pushTicket_.load(std::memory_order_acquire); // C
 742       if (pushes == nextPushes) {
 743         // pushTicket_ didn't change from A (or the previous C) to C,
 744         // so we can linearize at B (or D)
 745         return ssize_t(pushes - pops);
 746       }
 747       pushes = nextPushes;
 748       uint64_t nextPops = popTicket_.load(std::memory_order_acquire); // D
 749       if (pops == nextPops) {
 750         // popTicket_ didn't chance from B (or the previous D), so we
 751         // can linearize at C
 752         return ssize_t(pushes - pops);
 753       }
 754       pops = nextPops;
 755     }
 756   }
 757
 758   /// Returns true if there are no items available for dequeue
 759   bool isEmpty() const noexcept {
 760     return size() <= 0;
 761   }
 762
 763   /// Returns true if there is currently no empty space to enqueue
 764   bool isFull() const noexcept {
 765     // careful with signed -> unsigned promotion, since size can be negative
 766     return size() >= static_cast<ssize_t>(capacity_);
 767   }
 768
 769   /// Returns is a guess at size() for contexts that don't need a precise
 770   /// value, such as stats. More specifically, it returns the number of writes
 771   /// minus the number of reads, but after reading the number of writes, more
 772   /// writers could have came before the number of reads was sampled,
 773   /// and this method doesn't protect against such case.
 774   /// The returned value can be negative.
 775   ssize_t sizeGuess() const noexcept {
 776     return writeCount() - readCount();
 777   }
 778
 779   /// Doesn't change
 780   size_t capacity() const noexcept {
 781     return capacity_;
 782   }
 783
 784   /// Doesn't change for non-dynamic
 785   size_t allocatedCapacity() const noexcept {
 786     return capacity_;
 787   }
 788
 789   /// Returns the total number of calls to blockingWrite or successful
 790   /// calls to write, including those blockingWrite calls that are
 791   /// currently blocking
 792   uint64_t writeCount() const noexcept {
 793     return pushTicket_.load(std::memory_order_acquire);
 794   }
 795
 796   /// Returns the total number of calls to blockingRead or successful
 797   /// calls to read, including those blockingRead calls that are currently
 798   /// blocking
 799   uint64_t readCount() const noexcept {
 800     return popTicket_.load(std::memory_order_acquire);
 801   }
 802
 803   /// Enqueues a T constructed from args, blocking until space is
 804   /// available.  Note that this method signature allows enqueue via
 805   /// move, if args is a T rvalue, via copy, if args is a T lvalue, or
 806   /// via emplacement if args is an initializer list that can be passed
 807   /// to a T constructor.
 808   template <typename ...Args>
 809   void blockingWrite(Args&&... args) noexcept {
 810     enqueueWithTicketBase(pushTicket_++, slots_, capacity_, stride_,
 811                           std::forward<Args>(args)...);
 812   }
 813
 814   /// If an item can be enqueued with no blocking, does so and returns
 815   /// true, otherwise returns false.  This method is similar to
 816   /// writeIfNotFull, but if you don't have a specific need for that
 817   /// method you should use this one.
 818   ///
 819   /// One of the common usages of this method is to enqueue via the
 820   /// move constructor, something like q.write(std::move(x)).  If write
 821   /// returns false because the queue is full then x has not actually been
 822   /// consumed, which looks strange.  To understand why it is actually okay
 823   /// to use x afterward, remember that std::move is just a typecast that
 824   /// provides an rvalue reference that enables use of a move constructor
 825   /// or operator.  std::move doesn't actually move anything.  It could
 826   /// more accurately be called std::rvalue_cast or std::move_permission.
 827   template <typename ...Args>
 828   bool write(Args&&... args) noexcept {
 829     uint64_t ticket;
 830     Slot* slots;
 831     size_t cap;
 832     int stride;
 833     if (static_cast<Derived<T,Atom,Dynamic>*>(this)->
 834         tryObtainReadyPushTicket(ticket, slots, cap, stride)) {
 835       // we have pre-validated that the ticket won't block
 836       enqueueWithTicketBase(ticket, slots, cap, stride,
 837                             std::forward<Args>(args)...);
 838       return true;
 839     } else {
 840       return false;
 841     }
 842   }
 843
 844   template <class Clock, typename... Args>
 845   bool tryWriteUntil(const std::chrono::time_point<Clock>& when,
 846                      Args&&... args) noexcept {
 847     uint64_t ticket;
 848     Slot* slots;
 849     size_t cap;
 850     int stride;
 851     if (tryObtainPromisedPushTicketUntil(ticket, slots, cap, stride, when)) {
 852         // we have pre-validated that the ticket won't block, or rather that
 853         // it won't block longer than it takes another thread to dequeue an
 854         // element from the slot it identifies.
 855       enqueueWithTicketBase(ticket, slots, cap, stride,
 856                             std::forward<Args>(args)...);
 857       return true;
 858     } else {
 859       return false;
 860     }
 861   }
 862
 863   /// If the queue is not full, enqueues and returns true, otherwise
 864   /// returns false.  Unlike write this method can be blocked by another
 865   /// thread, specifically a read that has linearized (been assigned
 866   /// a ticket) but not yet completed.  If you don't really need this
 867   /// function you should probably use write.
 868   ///
 869   /// MPMCQueue isn't lock-free, so just because a read operation has
 870   /// linearized (and isFull is false) doesn't mean that space has been
 871   /// made available for another write.  In this situation write will
 872   /// return false, but writeIfNotFull will wait for the dequeue to finish.
 873   /// This method is required if you are composing queues and managing
 874   /// your own wakeup, because it guarantees that after every successful
 875   /// write a readIfNotEmpty will succeed.
 876   template <typename ...Args>
 877   bool writeIfNotFull(Args&&... args) noexcept {
 878     uint64_t ticket;
 879     Slot* slots;
 880     size_t cap;
 881     int stride;
 882     if (static_cast<Derived<T,Atom,Dynamic>*>(this)->
 883         tryObtainPromisedPushTicket(ticket, slots, cap, stride)) {
 884       // some other thread is already dequeuing the slot into which we
 885       // are going to enqueue, but we might have to wait for them to finish
 886       enqueueWithTicketBase(ticket, slots, cap, stride,
 887                             std::forward<Args>(args)...);
 888       return true;
 889     } else {
 890       return false;
 891     }
 892   }
 893
 894   /// Moves a dequeued element onto elem, blocking until an element
 895   /// is available
 896   void blockingRead(T& elem) noexcept {
 897     uint64_t ticket;
 898     static_cast<Derived<T,Atom,Dynamic>*>(this)->
 899       blockingReadWithTicket(ticket, elem);
 900   }
 901
 902   /// Same as blockingRead() but also records the ticket nunmer
 903   void blockingReadWithTicket(uint64_t& ticket, T& elem) noexcept {
 904     assert(capacity_ != 0);
 905     ticket = popTicket_++;
 906     dequeueWithTicketBase(ticket, slots_, capacity_, stride_, elem);
 907   }
 908
 909   /// If an item can be dequeued with no blocking, does so and returns
 910   /// true, otherwise returns false.
 911   bool read(T& elem) noexcept {
 912     uint64_t ticket;
 913     return readAndGetTicket(ticket, elem);
 914   }
 915
 916   /// Same as read() but also records the ticket nunmer
 917   bool readAndGetTicket(uint64_t& ticket, T& elem) noexcept {
 918     Slot* slots;
 919     size_t cap;
 920     int stride;
 921     if (static_cast<Derived<T,Atom,Dynamic>*>(this)->
 922         tryObtainReadyPopTicket(ticket, slots, cap, stride)) {
 923       // the ticket has been pre-validated to not block
 924       dequeueWithTicketBase(ticket, slots, cap, stride, elem);
 925       return true;
 926     } else {
 927       return false;
 928     }
 929   }
 930
 931   template <class Clock, typename... Args>
 932   bool tryReadUntil(
 933       const std::chrono::time_point<Clock>& when,
 934       T& elem) noexcept {
 935     uint64_t ticket;
 936     Slot* slots;
 937     size_t cap;
 938     int stride;
 939     if (tryObtainPromisedPopTicketUntil(ticket, slots, cap, stride, when)) {
 940       // we have pre-validated that the ticket won't block, or rather that
 941       // it won't block longer than it takes another thread to enqueue an
 942       // element on the slot it identifies.
 943       dequeueWithTicketBase(ticket, slots, cap, stride, elem);
 944       return true;
 945     } else {
 946       return false;
 947     }
 948   }
 949
 950   /// If the queue is not empty, dequeues and returns true, otherwise
 951   /// returns false.  If the matching write is still in progress then this
 952   /// method may block waiting for it.  If you don't rely on being able
 953   /// to dequeue (such as by counting completed write) then you should
 954   /// prefer read.
 955   bool readIfNotEmpty(T& elem) noexcept {
 956     uint64_t ticket;
 957     Slot* slots;
 958     size_t cap;
 959     int stride;
 960     if (static_cast<Derived<T,Atom,Dynamic>*>(this)->
 961         tryObtainPromisedPopTicket(ticket, slots, cap, stride)) {
 962       // the matching enqueue already has a ticket, but might not be done
 963       dequeueWithTicketBase(ticket, slots, cap, stride, elem);
 964       return true;
 965     } else {
 966       return false;
 967     }
 968   }
 969
 970  protected:
 971   enum {
 972     /// Once every kAdaptationFreq we will spin longer, to try to estimate
 973     /// the proper spin backoff
 974     kAdaptationFreq = 128,
 975
 976     /// To avoid false sharing in slots_ with neighboring memory
 977     /// allocations, we pad it with this many SingleElementQueue-s at
 978     /// each end
 979     kSlotPadding = (CacheLocality::kFalseSharingRange - 1) / sizeof(Slot) + 1
 980   };
 981
 982   /// The maximum number of items in the queue at once
 983   size_t FOLLY_ALIGN_TO_AVOID_FALSE_SHARING capacity_;
 984
 985   /// Anonymous union for use when Dynamic = false and true, respectively
 986   union {
 987     /// An array of capacity_ SingleElementQueue-s, each of which holds
 988     /// either 0 or 1 item.  We over-allocate by 2 * kSlotPadding and don't
 989     /// touch the slots at either end, to avoid false sharing
 990     Slot* slots_;
 991     /// Current dynamic slots array of dcapacity_ SingleElementQueue-s
 992     Atom<Slot*> dslots_;
 993   };
 994
 995   /// Anonymous union for use when Dynamic = false and true, respectively
 996   union {
 997     /// The number of slots_ indices that we advance for each ticket, to
 998     /// avoid false sharing.  Ideally slots_[i] and slots_[i + stride_]
 999     /// aren't on the same cache line
1000     int stride_;
1001     /// Current stride
1002     Atom<int> dstride_;
1003   };
1004
1005   /// The following two memebers are used by dynamic MPMCQueue.
1006   /// Ideally they should be in MPMCQueue<T,Atom,true>, but we get
1007   /// better cache locality if they are in the same cache line as
1008   /// dslots_ and dstride_.
1009   ///
1010   /// Dynamic state. A packed seqlock and ticket offset
1011   Atom<uint64_t> dstate_;
1012   /// Dynamic capacity
1013   Atom<size_t> dcapacity_;
1014
1015   /// Enqueuers get tickets from here
1016   Atom<uint64_t> FOLLY_ALIGN_TO_AVOID_FALSE_SHARING pushTicket_;
1017
1018   /// Dequeuers get tickets from here
1019   Atom<uint64_t> FOLLY_ALIGN_TO_AVOID_FALSE_SHARING popTicket_;
1020
1021   /// This is how many times we will spin before using FUTEX_WAIT when
1022   /// the queue is full on enqueue, adaptively computed by occasionally
1023   /// spinning for longer and smoothing with an exponential moving average
1024   Atom<uint32_t> FOLLY_ALIGN_TO_AVOID_FALSE_SHARING pushSpinCutoff_;
1025
1026   /// The adaptive spin cutoff when the queue is empty on dequeue
1027   Atom<uint32_t> FOLLY_ALIGN_TO_AVOID_FALSE_SHARING popSpinCutoff_;
1028
1029   /// Alignment doesn't prevent false sharing at the end of the struct,
1030   /// so fill out the last cache line
1031   char padding_[CacheLocality::kFalseSharingRange - sizeof(Atom<uint32_t>)];
1032
1033   /// We assign tickets in increasing order, but we don't want to
1034   /// access neighboring elements of slots_ because that will lead to
1035   /// false sharing (multiple cores accessing the same cache line even
1036   /// though they aren't accessing the same bytes in that cache line).
1037   /// To avoid this we advance by stride slots per ticket.
1038   ///
1039   /// We need gcd(capacity, stride) to be 1 so that we will use all
1040   /// of the slots.  We ensure this by only considering prime strides,
1041   /// which either have no common divisors with capacity or else have
1042   /// a zero remainder after dividing by capacity.  That is sufficient
1043   /// to guarantee correctness, but we also want to actually spread the
1044   /// accesses away from each other to avoid false sharing (consider a
1045   /// stride of 7 with a capacity of 8).  To that end we try a few taking
1046   /// care to observe that advancing by -1 is as bad as advancing by 1
1047   /// when in comes to false sharing.
1048   ///
1049   /// The simple way to avoid false sharing would be to pad each
1050   /// SingleElementQueue, but since we have capacity_ of them that could
1051   /// waste a lot of space.
1052   static int computeStride(size_t capacity) noexcept {
1053     static const int smallPrimes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
1054
1055     int bestStride = 1;
1056     size_t bestSep = 1;
1057     for (int stride : smallPrimes) {
1058       if ((stride % capacity) == 0 || (capacity % stride) == 0) {
1059         continue;
1060       }
1061       size_t sep = stride % capacity;
1062       sep = std::min(sep, capacity - sep);
1063       if (sep > bestSep) {
1064         bestStride = stride;
1065         bestSep = sep;
1066       }
1067     }
1068     return bestStride;
1069   }
1070
1071   /// Returns the index into slots_ that should be used when enqueuing or
1072   /// dequeuing with the specified ticket
1073   size_t idx(uint64_t ticket, size_t cap, int stride) noexcept {
1074     return ((ticket * stride) % cap) + kSlotPadding;
1075   }
1076
1077   /// Maps an enqueue or dequeue ticket to the turn should be used at the
1078   /// corresponding SingleElementQueue
1079   uint32_t turn(uint64_t ticket, size_t cap) noexcept {
1080     assert(cap != 0);
1081     return uint32_t(ticket / cap);
1082   }
1083
1084   /// Tries to obtain a push ticket for which SingleElementQueue::enqueue
1085   /// won't block.  Returns true on immediate success, false on immediate
1086   /// failure.
1087   bool tryObtainReadyPushTicket(
1088     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
1089   ) noexcept {
1090     ticket = pushTicket_.load(std::memory_order_acquire); // A
1091     slots = slots_;
1092     cap = capacity_;
1093     stride = stride_;
1094     while (true) {
1095       if (!slots[idx(ticket, cap, stride)]
1096           .mayEnqueue(turn(ticket, cap))) {
1097         // if we call enqueue(ticket, ...) on the SingleElementQueue
1098         // right now it would block, but this might no longer be the next
1099         // ticket.  We can increase the chance of tryEnqueue success under
1100         // contention (without blocking) by rechecking the ticket dispenser
1101         auto prev = ticket;
1102         ticket = pushTicket_.load(std::memory_order_acquire); // B
1103         if (prev == ticket) {
1104           // mayEnqueue was bracketed by two reads (A or prev B or prev
1105           // failing CAS to B), so we are definitely unable to enqueue
1106           return false;
1107         }
1108       } else {
1109         // we will bracket the mayEnqueue check with a read (A or prev B
1110         // or prev failing CAS) and the following CAS.  If the CAS fails
1111         // it will effect a load of pushTicket_
1112         if (pushTicket_.compare_exchange_strong(ticket, ticket + 1)) {
1113           return true;
1114         }
1115       }
1116     }
1117   }
1118
1119   /// Tries until when to obtain a push ticket for which
1120   /// SingleElementQueue::enqueue  won't block.  Returns true on success, false
1121   /// on failure.
1122   /// ticket is filled on success AND failure.
1123   template <class Clock>
1124   bool tryObtainPromisedPushTicketUntil(
1125     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride,
1126     const std::chrono::time_point<Clock>& when
1127   ) noexcept {
1128     bool deadlineReached = false;
1129     while (!deadlineReached) {
1130       if (static_cast<Derived<T,Atom,Dynamic>*>(this)->
1131           tryObtainPromisedPushTicket(ticket, slots, cap, stride)) {
1132         return true;
1133       }
1134       // ticket is a blocking ticket until the preceding ticket has been
1135       // processed: wait until this ticket's turn arrives. We have not reserved
1136       // this ticket so we will have to re-attempt to get a non-blocking ticket
1137       // if we wake up before we time-out.
1138       deadlineReached = !slots[idx(ticket, cap, stride)]
1139         .tryWaitForEnqueueTurnUntil(turn(ticket, cap), pushSpinCutoff_,
1140                                     (ticket % kAdaptationFreq) == 0, when);
1141     }
1142     return false;
1143   }
1144
1145   /// Tries to obtain a push ticket which can be satisfied if all
1146   /// in-progress pops complete.  This function does not block, but
1147   /// blocking may be required when using the returned ticket if some
1148   /// other thread's pop is still in progress (ticket has been granted but
1149   /// pop has not yet completed).
1150   bool tryObtainPromisedPushTicket(
1151     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
1152   ) noexcept {
1153     auto numPushes = pushTicket_.load(std::memory_order_acquire); // A
1154     slots = slots_;
1155     cap = capacity_;
1156     stride = stride_;
1157     while (true) {
1158       ticket = numPushes;
1159       const auto numPops = popTicket_.load(std::memory_order_acquire); // B
1160       // n will be negative if pops are pending
1161       const int64_t n = int64_t(numPushes - numPops);
1162       if (n >= static_cast<ssize_t>(capacity_)) {
1163         // Full, linearize at B.  We don't need to recheck the read we
1164         // performed at A, because if numPushes was stale at B then the
1165         // real numPushes value is even worse
1166         return false;
1167       }
1168       if (pushTicket_.compare_exchange_strong(numPushes, numPushes + 1)) {
1169         return true;
1170       }
1171     }
1172   }
1173
1174   /// Tries to obtain a pop ticket for which SingleElementQueue::dequeue
1175   /// won't block.  Returns true on immediate success, false on immediate
1176   /// failure.
1177   bool tryObtainReadyPopTicket(
1178     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
1179   ) noexcept {
1180     ticket = popTicket_.load(std::memory_order_acquire);
1181     slots = slots_;
1182     cap = capacity_;
1183     stride = stride_;
1184     while (true) {
1185       if (!slots[idx(ticket, cap, stride)]
1186           .mayDequeue(turn(ticket, cap))) {
1187         auto prev = ticket;
1188         ticket = popTicket_.load(std::memory_order_acquire);
1189         if (prev == ticket) {
1190           return false;
1191         }
1192       } else {
1193         if (popTicket_.compare_exchange_strong(ticket, ticket + 1)) {
1194           return true;
1195         }
1196       }
1197     }
1198   }
1199
1200   /// Tries until when to obtain a pop ticket for which
1201   /// SingleElementQueue::dequeue won't block.  Returns true on success, false
1202   /// on failure.
1203   /// ticket is filled on success AND failure.
1204   template <class Clock>
1205   bool tryObtainPromisedPopTicketUntil(
1206       uint64_t& ticket,
1207       Slot*& slots,
1208       size_t& cap,
1209       int& stride,
1210       const std::chrono::time_point<Clock>& when) noexcept {
1211     bool deadlineReached = false;
1212     while (!deadlineReached) {
1213       if (static_cast<Derived<T, Atom, Dynamic>*>(this)
1214               ->tryObtainPromisedPopTicket(ticket, slots, cap, stride)) {
1215         return true;
1216       }
1217       // ticket is a blocking ticket until the preceding ticket has been
1218       // processed: wait until this ticket's turn arrives. We have not reserved
1219       // this ticket so we will have to re-attempt to get a non-blocking ticket
1220       // if we wake up before we time-out.
1221       deadlineReached =
1222           !slots[idx(ticket, cap, stride)].tryWaitForDequeueTurnUntil(
1223               turn(ticket, cap),
1224               pushSpinCutoff_,
1225               (ticket % kAdaptationFreq) == 0,
1226               when);
1227     }
1228     return false;
1229   }
1230
1231   /// Similar to tryObtainReadyPopTicket, but returns a pop ticket whose
1232   /// corresponding push ticket has already been handed out, rather than
1233   /// returning one whose corresponding push ticket has already been
1234   /// completed.  This means that there is a possibility that the caller
1235   /// will block when using the ticket, but it allows the user to rely on
1236   /// the fact that if enqueue has succeeded, tryObtainPromisedPopTicket
1237   /// will return true.  The "try" part of this is that we won't have
1238   /// to block waiting for someone to call enqueue, although we might
1239   /// have to block waiting for them to finish executing code inside the
1240   /// MPMCQueue itself.
1241   bool tryObtainPromisedPopTicket(
1242     uint64_t& ticket, Slot*& slots, size_t& cap, int& stride
1243   ) noexcept {
1244     auto numPops = popTicket_.load(std::memory_order_acquire); // A
1245     slots = slots_;
1246     cap = capacity_;
1247     stride = stride_;
1248     while (true) {
1249       ticket = numPops;
1250       const auto numPushes = pushTicket_.load(std::memory_order_acquire); // B
1251       if (numPops >= numPushes) {
1252         // Empty, or empty with pending pops.  Linearize at B.  We don't
1253         // need to recheck the read we performed at A, because if numPops
1254         // is stale then the fresh value is larger and the >= is still true
1255         return false;
1256       }
1257       if (popTicket_.compare_exchange_strong(numPops, numPops + 1)) {
1258         return true;
1259       }
1260     }
1261   }
1262
1263   // Given a ticket, constructs an enqueued item using args
1264   template <typename ...Args>
1265   void enqueueWithTicketBase(
1266     uint64_t ticket, Slot* slots, size_t cap, int stride, Args&&... args
1267   ) noexcept {
1268     slots[idx(ticket, cap, stride)]
1269       .enqueue(turn(ticket, cap),
1270                pushSpinCutoff_,
1271                (ticket % kAdaptationFreq) == 0,
1272                std::forward<Args>(args)...);
1273   }
1274
1275   // To support tracking ticket numbers in MPMCPipelineStageImpl
1276   template <typename ...Args>
1277   void enqueueWithTicket(uint64_t ticket, Args&&... args) noexcept {
1278     enqueueWithTicketBase(ticket, slots_, capacity_, stride_,
1279                           std::forward<Args>(args)...);
1280   }
1281
1282   // Given a ticket, dequeues the corresponding element
1283   void dequeueWithTicketBase(
1284     uint64_t ticket, Slot* slots, size_t cap, int stride, T& elem
1285   ) noexcept {
1286     assert(cap != 0);
1287     slots[idx(ticket, cap, stride)]
1288       .dequeue(turn(ticket, cap),
1289                popSpinCutoff_,
1290                (ticket % kAdaptationFreq) == 0,
1291                elem);
1292   }
1293 };
1294
1295 /// SingleElementQueue implements a blocking queue that holds at most one
1296 /// item, and that requires its users to assign incrementing identifiers
1297 /// (turns) to each enqueue and dequeue operation.  Note that the turns
1298 /// used by SingleElementQueue are doubled inside the TurnSequencer
1299 template <typename T, template <typename> class Atom>
1300 struct SingleElementQueue {
1301
1302   ~SingleElementQueue() noexcept {
1303     if ((sequencer_.uncompletedTurnLSB() & 1) == 1) {
1304       // we are pending a dequeue, so we have a constructed item
1305       destroyContents();
1306     }
1307   }
1308
1309   /// enqueue using in-place noexcept construction
1310   template <typename ...Args,
1311             typename = typename std::enable_if<
1312               std::is_nothrow_constructible<T,Args...>::value>::type>
1313   void enqueue(const uint32_t turn,
1314                Atom<uint32_t>& spinCutoff,
1315                const bool updateSpinCutoff,
1316                Args&&... args) noexcept {
1317     sequencer_.waitForTurn(turn * 2, spinCutoff, updateSpinCutoff);
1318     new (&contents_) T(std::forward<Args>(args)...);
1319     sequencer_.completeTurn(turn * 2);
1320   }
1321
1322   /// enqueue using move construction, either real (if
1323   /// is_nothrow_move_constructible) or simulated using relocation and
1324   /// default construction (if IsRelocatable and is_nothrow_constructible)
1325   template <
1326       typename = typename std::enable_if<
1327           (folly::IsRelocatable<T>::value &&
1328            std::is_nothrow_constructible<T>::value) ||
1329           std::is_nothrow_constructible<T, T&&>::value>::type>
1330   void enqueue(
1331       const uint32_t turn,
1332       Atom<uint32_t>& spinCutoff,
1333       const bool updateSpinCutoff,
1334       T&& goner) noexcept {
1335     enqueueImpl(
1336         turn,
1337         spinCutoff,
1338         updateSpinCutoff,
1339         std::move(goner),
1340         typename std::conditional<std::is_nothrow_constructible<T,T&&>::value,
1341                                   ImplByMove, ImplByRelocation>::type());
1342   }
1343
1344   /// Waits until either:
1345   /// 1: the dequeue turn preceding the given enqueue turn has arrived
1346   /// 2: the given deadline has arrived
1347   /// Case 1 returns true, case 2 returns false.
1348   template <class Clock>
1349   bool tryWaitForEnqueueTurnUntil(
1350       const uint32_t turn,
1351       Atom<uint32_t>& spinCutoff,
1352       const bool updateSpinCutoff,
1353       const std::chrono::time_point<Clock>& when) noexcept {
1354     return sequencer_.tryWaitForTurn(
1355                turn * 2, spinCutoff, updateSpinCutoff, &when) !=
1356         TurnSequencer<Atom>::TryWaitResult::TIMEDOUT;
1357   }
1358
1359   bool mayEnqueue(const uint32_t turn) const noexcept {
1360     return sequencer_.isTurn(turn * 2);
1361   }
1362
1363   void dequeue(uint32_t turn,
1364                Atom<uint32_t>& spinCutoff,
1365                const bool updateSpinCutoff,
1366                T& elem) noexcept {
1367     dequeueImpl(turn,
1368                 spinCutoff,
1369                 updateSpinCutoff,
1370                 elem,
1371                 typename std::conditional<folly::IsRelocatable<T>::value,
1372                                           ImplByRelocation,
1373                                           ImplByMove>::type());
1374   }
1375
1376   /// Waits until either:
1377   /// 1: the enqueue turn preceding the given dequeue turn has arrived
1378   /// 2: the given deadline has arrived
1379   /// Case 1 returns true, case 2 returns false.
1380   template <class Clock>
1381   bool tryWaitForDequeueTurnUntil(
1382       const uint32_t turn,
1383       Atom<uint32_t>& spinCutoff,
1384       const bool updateSpinCutoff,
1385       const std::chrono::time_point<Clock>& when) noexcept {
1386     return sequencer_.tryWaitForTurn(
1387                turn * 2 + 1, spinCutoff, updateSpinCutoff, &when) !=
1388         TurnSequencer<Atom>::TryWaitResult::TIMEDOUT;
1389   }
1390
1391   bool mayDequeue(const uint32_t turn) const noexcept {
1392     return sequencer_.isTurn(turn * 2 + 1);
1393   }
1394
1395  private:
1396   /// Storage for a T constructed with placement new
1397   typename std::aligned_storage<sizeof(T),alignof(T)>::type contents_;
1398
1399   /// Even turns are pushes, odd turns are pops
1400   TurnSequencer<Atom> sequencer_;
1401
1402   T* ptr() noexcept {
1403     return static_cast<T*>(static_cast<void*>(&contents_));
1404   }
1405
1406   void destroyContents() noexcept {
1407     try {
1408       ptr()->~T();
1409     } catch (...) {
1410       // g++ doesn't seem to have std::is_nothrow_destructible yet
1411     }
1412 #ifndef NDEBUG
1413     memset(&contents_, 'Q', sizeof(T));
1414 #endif
1415   }
1416
1417   /// Tag classes for dispatching to enqueue/dequeue implementation.
1418   struct ImplByRelocation {};
1419   struct ImplByMove {};
1420
1421   /// enqueue using nothrow move construction.
1422   void enqueueImpl(const uint32_t turn,
1423                    Atom<uint32_t>& spinCutoff,
1424                    const bool updateSpinCutoff,
1425                    T&& goner,
1426                    ImplByMove) noexcept {
1427     sequencer_.waitForTurn(turn * 2, spinCutoff, updateSpinCutoff);
1428     new (&contents_) T(std::move(goner));
1429     sequencer_.completeTurn(turn * 2);
1430   }
1431
1432   /// enqueue by simulating nothrow move with relocation, followed by
1433   /// default construction to a noexcept relocation.
1434   void enqueueImpl(const uint32_t turn,
1435                    Atom<uint32_t>& spinCutoff,
1436                    const bool updateSpinCutoff,
1437                    T&& goner,
1438                    ImplByRelocation) noexcept {
1439     sequencer_.waitForTurn(turn * 2, spinCutoff, updateSpinCutoff);
1440     memcpy(&contents_, &goner, sizeof(T));
1441     sequencer_.completeTurn(turn * 2);
1442     new (&goner) T();
1443   }
1444
1445   /// dequeue by destructing followed by relocation.  This version is preferred,
1446   /// because as much work as possible can be done before waiting.
1447   void dequeueImpl(uint32_t turn,
1448                    Atom<uint32_t>& spinCutoff,
1449                    const bool updateSpinCutoff,
1450                    T& elem,
1451                    ImplByRelocation) noexcept {
1452     try {
1453       elem.~T();
1454     } catch (...) {
1455       // unlikely, but if we don't complete our turn the queue will die
1456     }
1457     sequencer_.waitForTurn(turn * 2 + 1, spinCutoff, updateSpinCutoff);
1458     memcpy(&elem, &contents_, sizeof(T));
1459     sequencer_.completeTurn(turn * 2 + 1);
1460   }
1461
1462   /// dequeue by nothrow move assignment.
1463   void dequeueImpl(uint32_t turn,
1464                    Atom<uint32_t>& spinCutoff,
1465                    const bool updateSpinCutoff,
1466                    T& elem,
1467                    ImplByMove) noexcept {
1468     sequencer_.waitForTurn(turn * 2 + 1, spinCutoff, updateSpinCutoff);
1469     elem = std::move(*ptr());
1470     destroyContents();
1471     sequencer_.completeTurn(turn * 2 + 1);
1472   }
1473 };
1474
1475 } // namespace detail
1476
1477 } // namespace folly