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 | |
25 | namespace folly { |
26 | namespace 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. |
45 | class 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 | |