1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H
10#define _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H
11
12#include <__assert>
13#include <__atomic/atomic.h>
14#include <__atomic/atomic_sync.h>
15#include <__atomic/memory_order.h>
16#include <__config>
17#include <__cstddef/size_t.h>
18#include <__memory/addressof.h>
19#include <__memory/construct_at.h>
20#include <__new/global_new_delete.h>
21#include <__new/nothrow_t.h>
22#include <__optional/nullopt_t.h>
23#include <__optional/optional.h>
24#include <__utility/exchange.h>
25#include <__utility/forward.h>
26#include <__utility/move.h>
27
28#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
29# pragma GCC system_header
30#endif
31
32_LIBCPP_PUSH_MACROS
33#include <__undef_macros>
34
35#if _LIBCPP_STD_VER >= 17
36
37_LIBCPP_BEGIN_NAMESPACE_STD
38namespace __pstl {
39
40namespace __statpart {
41
42// Based on the paper "Single-pass Parallel Prefix Scan with Decoupled Look-back" (Merrill, Garland, 2016).
43
44inline constexpr unsigned char __decoupled_lookback_status_invalid = 0;
45inline constexpr unsigned char __decoupled_lookback_status_aggregate_available = 1 << 0;
46inline constexpr unsigned char __decoupled_lookback_status_prefix_available = 1 << 1;
47
48// __decoupled_lookback_partition contains 2 values of _Tp (local aggregate and inclusive prefix) and a status flag.
49// The values can be initialized by a thread working on this partition by calling __construct_aggregate or
50// __construct_inclusive_prefix. These functions implicitly update the status flag and notify any thread potentially
51// waiting on it.
52// Other threads reaching this partition via a lookback should use __acquire_available_status() to wait until either of
53// the two values is available. Depending on the status flag, the constructed values can be accessed via __aggregate()
54// and __inclusive_prefix().
55template <typename _Tp>
56struct _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition {
57 _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition() {}
58 __decoupled_lookback_partition(const __decoupled_lookback_partition&) = delete;
59 __decoupled_lookback_partition& operator=(const __decoupled_lookback_partition&) = delete;
60
61 // Destructor: destroy the aggregate and inclusive prefix if they have been constructed.
62 _LIBCPP_HIDE_FROM_ABI ~__decoupled_lookback_partition() {
63 unsigned char __flag = __status_flag_.load(m: std::memory_order_relaxed);
64 if (__flag & __decoupled_lookback_status_aggregate_available) {
65 __aggregate_.~_Tp();
66 }
67 if (__flag & __decoupled_lookback_status_prefix_available) {
68 __inclusive_prefix_.~_Tp();
69 }
70 }
71
72 // Acquire the current status of the partition.
73 // If no value is published yet, wait until one becomes available.
74 _LIBCPP_HIDE_FROM_ABI unsigned char __acquire_available_status() {
75 unsigned char __current_status = __status_flag_.load(m: std::memory_order_acquire);
76 if (__current_status != __decoupled_lookback_status_invalid)
77 return __current_status;
78 std::__atomic_wait(a&: __status_flag_, val: __decoupled_lookback_status_invalid, order: std::memory_order_acquire);
79 return __status_flag_.load(m: std::memory_order_acquire);
80 }
81
82 // Construct the aggregate value of the partition and publish this change.
83 template <class... _Args>
84 _LIBCPP_HIDE_FROM_ABI void __construct_aggregate(_Args&&... __args) {
85 _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_aggregate_available) == 0,
86 "__decoupled_lookback_status_aggregate_available flag must not be set");
87 std::__construct_at(std::addressof(__aggregate_), std::forward<_Args>(__args)...);
88 __status_flag_.fetch_or(op: __decoupled_lookback_status_aggregate_available, m: std::memory_order_release);
89 std::__atomic_notify_all(a: __status_flag_);
90 }
91
92 // Access the aggregate value of the partition.
93 // Precondition: __acquire_available_status() & __decoupled_lookback_status_aggregate_available
94 _LIBCPP_HIDE_FROM_ABI const _Tp& __aggregate() const {
95 _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_aggregate_available) != 0,
96 "__decoupled_lookback_status_aggregate_available flag must be set");
97 return __aggregate_;
98 }
99
100 // Construct the inclusive prefix of the partition and publish this change.
101 template <class... _Args>
102 _LIBCPP_HIDE_FROM_ABI void __construct_inclusive_prefix(_Args&&... __args) {
103 _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_prefix_available) == 0,
104 "__decoupled_lookback_status_prefix_available flag must not be set");
105 std::__construct_at(std::addressof(__inclusive_prefix_), std::forward<_Args>(__args)...);
106 __status_flag_.fetch_or(op: __decoupled_lookback_status_prefix_available, m: std::memory_order_release);
107 std::__atomic_notify_all(a: __status_flag_);
108 }
109
110 // Access the inclusive prefix of the partition.
111 // Precondition: __acquire_available_status() & __decoupled_lookback_status_prefix_available
112 _LIBCPP_HIDE_FROM_ABI const _Tp& __inclusive_prefix() const {
113 _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_prefix_available) != 0,
114 "__decoupled_lookback_status_prefix_available flag must be set");
115 return __inclusive_prefix_;
116 }
117
118private:
119 // Storage for the aggregate reduced value of the partition.
120 union {
121 _Tp __aggregate_;
122 };
123
124 // Storage for the inclusive prefix of the partition.
125 union {
126 _Tp __inclusive_prefix_;
127 };
128
129 // Atomic/waitable flag indicating the status of the partition.
130 std::atomic<unsigned char> __status_flag_{__decoupled_lookback_status_invalid};
131
132 // NB! Currently the layout of __decoupled_lookback_partition allows for false sharing to occur.
133};
134
135// __decoupled_lookback holds a dynamically-allocated array of __decoupled_lookback_partition.
136// Created by __make_decoupled_lookback().
137template <typename _Tp>
138class _LIBCPP_HIDE_FROM_ABI __decoupled_lookback {
139public:
140 _LIBCPP_HIDE_FROM_ABI __decoupled_lookback(__decoupled_lookback&& __other) noexcept
141 : __partitions_(std::exchange(__other.__partitions_, nullptr)),
142 __partitions_count_(std::exchange(obj&: __other.__partitions_count_, new_value: 0)) {}
143
144 __decoupled_lookback(const __decoupled_lookback&) = delete;
145 __decoupled_lookback& operator=(const __decoupled_lookback&) = delete;
146 __decoupled_lookback& operator=(__decoupled_lookback&&) = delete;
147
148 _LIBCPP_HIDE_FROM_ABI ~__decoupled_lookback() { delete[] __partitions_; }
149
150 // Returns the number of partitions in the lookback.
151 _LIBCPP_HIDE_FROM_ABI size_t __size() const { return __partitions_count_; }
152
153 // Provides a pointer to the first partition in a contiguous storage.
154 _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition<_Tp>* __partitions() const { return __partitions_; }
155
156 // Provides a reference to the specified partition.
157 _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition<_Tp>& __partition(size_t __index) const {
158 _LIBCPP_ASSERT_INTERNAL(__index < __partitions_count_, "__index must be less than __partitions_count_");
159 return __partitions_[__index];
160 }
161
162private:
163 _LIBCPP_HIDE_FROM_ABI __decoupled_lookback() = default;
164
165 __decoupled_lookback_partition<_Tp>* __partitions_ = nullptr;
166 size_t __partitions_count_ = 0;
167
168 template <class _Up>
169 friend _LIBCPP_HIDE_FROM_ABI optional<__decoupled_lookback<_Up>> __make_decoupled_lookback(size_t) noexcept;
170};
171
172// Creates a lookback partition with the specified capacity.
173// In case memory allocation fails, returns std::nullopt.
174template <typename _Tp>
175_LIBCPP_HIDE_FROM_ABI optional<__decoupled_lookback<_Tp>> __make_decoupled_lookback(size_t __size) noexcept {
176 __decoupled_lookback<_Tp> __lookback;
177 __lookback.__partitions_ = new (std::nothrow) __decoupled_lookback_partition<_Tp>[__size];
178 if (!__lookback.__partitions_)
179 return nullopt;
180 __lookback.__partitions_count_ = __size;
181 return __lookback;
182}
183
184// Calculate an inclusive prefix of a given partition that currently has only an aggregate.
185// Performs reductions of aggregate values until it arrives at a partition with an available prefix.
186// Precondition: __partition->__acquire_available_status() == __decoupled_lookback_status_aggregate_available.
187template <typename _Tp, class _BinaryOperation>
188_LIBCPP_HIDE_FROM_ABI _Tp
189__calculate_inclusive_prefix_of_partition(__decoupled_lookback_partition<_Tp>* __partition, _BinaryOperation __reduce) {
190 // Start at the given partition.
191 _Tp __prefix = __partition->__aggregate();
192 while (true) {
193 // Move to the previous partition and check its status.
194 --__partition;
195 unsigned char __status = __partition->__acquire_available_status();
196 if (__status & __decoupled_lookback_status_prefix_available) {
197 // Found a partition with an available prefix - can perform a final reduction and terminate.
198 return __reduce(__partition->__inclusive_prefix(), std::move(__prefix));
199 }
200 // Reduce with another aggregate and continue moving left.
201 __prefix = __reduce(__partition->__aggregate(), std::move(__prefix));
202 }
203}
204
205} // namespace __statpart
206
207} // namespace __pstl
208_LIBCPP_END_NAMESPACE_STD
209
210#endif // _LIBCPP_STD_VER >= 17
211
212_LIBCPP_POP_MACROS
213
214#endif // _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H
215