folly/futures/Barrier.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 <atomic>
  20 #include <cstdint>
  21
  22 #include <folly/futures/Future.h>
  23 #include <folly/futures/Promise.h>
  24
  25 namespace folly { namespace futures {
  26
  27 // A folly::Future-istic Barrier synchronization primitive
  28 //
  29 // The barrier is initialized with a count N.
  30 //
  31 // The first N-1 calls to wait() return uncompleted futures.
  32 //
  33 // The Nth call to wait() completes the previous N-1 futures successfully,
  34 // returns a future that is already completed successfully, and resets the
  35 // barrier; the barrier may be reused immediately, as soon as at least one
  36 // of the future completions has been observed.
  37 //
  38 // Of these N futures, exactly one is completed with true, while the others are
  39 // completed with false; it is unspecified which future completes with true.
  40 // (This may be used to elect a "leader" among a group of threads.)
  41 //
  42 // If the barrier is destroyed, any futures already returned by wait() will
  43 // complete with an error.
  44 class Barrier {
  45  public:
  46   explicit Barrier(uint32_t n);
  47   ~Barrier();
  48
  49   folly::Future<bool> wait();
  50
  51  private:
  52   typedef folly::Promise<bool> BoolPromise;
  53
  54   static constexpr uint64_t kReaderShift = 32;
  55   static constexpr uint64_t kReader = uint64_t(1) << kReaderShift;
  56   static constexpr uint64_t kValueMask = kReader - 1;
  57
  58   // For each "epoch" that the barrier is active, we have a different
  59   // ControlBlock. The ControlBlock contains the current barrier value
  60   // and the number of readers (currently inside wait()) packed into a
  61   // 64-bit value.
  62   //
  63   // The ControlBlock is allocated as long as either:
  64   // - there are threads currently inside wait() (reader count > 0), or
  65   // - the value has not yet reached size_ (value < size_)
  66   //
  67   // The array of size_ Promise objects is allocated immediately following
  68   // valueAndReaderCount.
  69
  70   struct ControlBlock {
  71     // Reader count in most significant 32 bits
  72     // Value in least significant 32 bits
  73     std::atomic<uint64_t> valueAndReaderCount;
  74   };
  75
  76   struct ControlBlockAndPromise {
  77     ControlBlock cb;
  78     BoolPromise promises[1];
  79   };
  80
  81   static BoolPromise* promises(ControlBlock* cb) {
  82     return reinterpret_cast<ControlBlockAndPromise*>(cb)->promises;
  83   }
  84
  85   static size_t controlBlockSize(size_t n) {
  86     return offsetof(ControlBlockAndPromise, promises) + n * sizeof(BoolPromise);
  87   }
  88
  89   ControlBlock* allocateControlBlock();
  90   void freeControlBlock(ControlBlock* b);
  91
  92   uint32_t size_;
  93   std::atomic<ControlBlock*> controlBlock_;
  94 };
  95
  96 }}  // namespaces