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