2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
22 #include <folly/futures/Future.h>
23 #include <folly/futures/Promise.h>
25 namespace folly { namespace futures {
27 // A folly::Future-istic Barrier synchronization primitive
29 // The barrier is initialized with a count N.
31 // The first N-1 calls to wait() return uncompleted futures.
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.
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.)
42 // If the barrier is destroyed, any futures already returned by wait() will
43 // complete with an error.
46 explicit Barrier(uint32_t n);
49 folly::Future<bool> wait();
52 typedef folly::Promise<bool> BoolPromise;
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;
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
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_)
67 // The array of size_ Promise objects is allocated immediately following
68 // valueAndReaderCount.
71 // Reader count in most significant 32 bits
72 // Value in least significant 32 bits
73 std::atomic<uint64_t> valueAndReaderCount;
76 struct ControlBlockAndPromise {
78 BoolPromise promises[1];
81 static BoolPromise* promises(ControlBlock* cb) {
82 return reinterpret_cast<ControlBlockAndPromise*>(cb)->promises;
85 static size_t controlBlockSize(size_t n) {
86 return offsetof(ControlBlockAndPromise, promises) + n * sizeof(BoolPromise);
89 ControlBlock* allocateControlBlock();
90 void freeControlBlock(ControlBlock* b);
93 std::atomic<ControlBlock*> controlBlock_;