tbb/detail/_utils.h

0001 /*
0002     Copyright (c) 2005-2023 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_detail__utils_H
0018 #define __TBB_detail__utils_H
0019
0020 #include <type_traits>
0021 #include <cstdint>
0022 #include <atomic>
0023 #include <functional>
0024
0025 #include "_config.h"
0026 #include "_assert.h"
0027 #include "_machine.h"
0028
0029 namespace tbb {
0030 namespace detail {
0031 inline namespace d0 {
0032
0033 //! Utility template function to prevent "unused" warnings by various compilers.
0034 template<typename... T> void suppress_unused_warning(T&&...) {}
0035
0036 //! Compile-time constant that is upper bound on cache line/sector size.
0037 /** It should be used only in situations where having a compile-time upper
0038   bound is more useful than a run-time exact answer.
0039   @ingroup memory_allocation */
0040 constexpr size_t max_nfs_size = 128;
0041 constexpr std::size_t max_nfs_size_exp = 7;
0042 static_assert(1 << max_nfs_size_exp == max_nfs_size, "max_nfs_size_exp must be a log2(max_nfs_size)");
0043
0044 //! Class that implements exponential backoff.
0045 class atomic_backoff {
0046     //! Time delay, in units of "pause" instructions.
0047     /** Should be equal to approximately the number of "pause" instructions
0048       that take the same time as an context switch. Must be a power of two.*/
0049     static constexpr std::int32_t LOOPS_BEFORE_YIELD = 16;
0050     std::int32_t count;
0051
0052 public:
0053     // In many cases, an object of this type is initialized eagerly on hot path,
0054     // as in for(atomic_backoff b; ; b.pause()) { /*loop body*/ }
0055     // For this reason, the construction cost must be very small!
0056     atomic_backoff() : count(1) {}
0057     // This constructor pauses immediately; do not use on hot paths!
0058     atomic_backoff(bool) : count(1) { pause(); }
0059
0060     //! No Copy
0061     atomic_backoff(const atomic_backoff&) = delete;
0062     atomic_backoff& operator=(const atomic_backoff&) = delete;
0063
0064     //! Pause for a while.
0065     void pause() {
0066         if (count <= LOOPS_BEFORE_YIELD) {
0067             machine_pause(count);
0068             // Pause twice as long the next time.
0069             count *= 2;
0070         } else {
0071             // Pause is so long that we might as well yield CPU to scheduler.
0072             yield();
0073         }
0074     }
0075
0076     //! Pause for a few times and return false if saturated.
0077     bool bounded_pause() {
0078         machine_pause(count);
0079         if (count < LOOPS_BEFORE_YIELD) {
0080             // Pause twice as long the next time.
0081             count *= 2;
0082             return true;
0083         } else {
0084             return false;
0085         }
0086     }
0087
0088     void reset() {
0089         count = 1;
0090     }
0091 };
0092
0093 //! Spin WHILE the condition is true.
0094 /** T and U should be comparable types. */
0095 template <typename T, typename C>
0096 T spin_wait_while(const std::atomic<T>& location, C comp, std::memory_order order) {
0097     atomic_backoff backoff;
0098     T snapshot = location.load(order);
0099     while (comp(snapshot)) {
0100         backoff.pause();
0101         snapshot = location.load(order);
0102     }
0103     return snapshot;
0104 }
0105
0106 //! Spin WHILE the value of the variable is equal to a given value
0107 /** T and U should be comparable types. */
0108 template <typename T, typename U>
0109 T spin_wait_while_eq(const std::atomic<T>& location, const U value, std::memory_order order = std::memory_order_acquire) {
0110     return spin_wait_while(location, [&value](T t) { return t == value; }, order);
0111 }
0112
0113 //! Spin UNTIL the value of the variable is equal to a given value
0114 /** T and U should be comparable types. */
0115 template<typename T, typename U>
0116 T spin_wait_until_eq(const std::atomic<T>& location, const U value, std::memory_order order = std::memory_order_acquire) {
0117     return spin_wait_while(location, [&value](T t) { return t != value; }, order);
0118 }
0119
0120 //! Spin UNTIL the condition returns true or spinning time is up.
0121 /** Returns what the passed functor returned last time it was invoked. */
0122 template <typename Condition>
0123 bool timed_spin_wait_until(Condition condition) {
0124     // 32 pauses + 32 yields are meausered as balanced spin time before sleep.
0125     bool finish = condition();
0126     for (int i = 1; !finish && i < 32; finish = condition(), i *= 2) {
0127         machine_pause(i);
0128     }
0129     for (int i = 32; !finish && i < 64; finish = condition(), ++i) {
0130         yield();
0131     }
0132     return finish;
0133 }
0134
0135 template <typename T>
0136 T clamp(T value, T lower_bound, T upper_bound) {
0137     __TBB_ASSERT(lower_bound <= upper_bound, "Incorrect bounds");
0138     return value > lower_bound ? (value > upper_bound ? upper_bound : value) : lower_bound;
0139 }
0140
0141 template <typename T>
0142 std::uintptr_t log2(T in) {
0143     __TBB_ASSERT(in > 0, "The logarithm of a non-positive value is undefined.");
0144     return machine_log2(in);
0145 }
0146
0147 template<typename T>
0148 T reverse_bits(T src) {
0149     return machine_reverse_bits(src);
0150 }
0151
0152 template<typename T>
0153 T reverse_n_bits(T src, std::size_t n) {
0154     __TBB_ASSERT(n != 0, "Reverse for 0 bits is undefined behavior.");
0155     return reverse_bits(src) >> (number_of_bits<T>() - n);
0156 }
0157
0158 // A function to check if passed integer is a power of two
0159 template <typename IntegerType>
0160 constexpr bool is_power_of_two( IntegerType arg ) {
0161     static_assert(std::is_integral<IntegerType>::value,
0162                   "An argument for is_power_of_two should be integral type");
0163     return arg && (0 == (arg & (arg - 1)));
0164 }
0165
0166 // A function to determine if passed integer is a power of two
0167 // at least as big as another power of two, i.e. for strictly positive i and j,
0168 // with j being a power of two, determines whether i==j<<k for some nonnegative k
0169 template <typename ArgIntegerType, typename DivisorIntegerType>
0170 constexpr bool is_power_of_two_at_least(ArgIntegerType arg, DivisorIntegerType divisor) {
0171     // Divisor should be a power of two
0172     static_assert(std::is_integral<ArgIntegerType>::value,
0173                   "An argument for is_power_of_two_at_least should be integral type");
0174     return 0 == (arg & (arg - divisor));
0175 }
0176
0177 // A function to compute arg modulo divisor where divisor is a power of 2.
0178 template<typename ArgIntegerType, typename DivisorIntegerType>
0179 inline ArgIntegerType modulo_power_of_two(ArgIntegerType arg, DivisorIntegerType divisor) {
0180     __TBB_ASSERT( is_power_of_two(divisor), "Divisor should be a power of two" );
0181     return arg & (divisor - 1);
0182 }
0183
0184 //! A function to check if passed in pointer is aligned on a specific border
0185 template<typename T>
0186 constexpr bool is_aligned(T* pointer, std::uintptr_t alignment) {
0187     return 0 == (reinterpret_cast<std::uintptr_t>(pointer) & (alignment - 1));
0188 }
0189
0190 #if TBB_USE_ASSERT
0191 static void* const poisoned_ptr = reinterpret_cast<void*>(-1);
0192
0193 //! Set p to invalid pointer value.
0194 template<typename T>
0195 inline void poison_pointer( T* &p ) { p = reinterpret_cast<T*>(poisoned_ptr); }
0196
0197 template<typename T>
0198 inline void poison_pointer(std::atomic<T*>& p) { p.store(reinterpret_cast<T*>(poisoned_ptr), std::memory_order_relaxed); }
0199
0200 /** Expected to be used in assertions only, thus no empty form is defined. **/
0201 template<typename T>
0202 inline bool is_poisoned( T* p ) { return p == reinterpret_cast<T*>(poisoned_ptr); }
0203
0204 template<typename T>
0205 inline bool is_poisoned(const std::atomic<T*>& p) { return is_poisoned(p.load(std::memory_order_relaxed)); }
0206 #else
0207 template<typename T>
0208 inline void poison_pointer(T&) {/*do nothing*/}
0209 #endif /* !TBB_USE_ASSERT */
0210
0211 template <std::size_t alignment = 0, typename T>
0212 bool assert_pointer_valid(T* p, const char* comment = nullptr) {
0213     suppress_unused_warning(p, comment);
0214     __TBB_ASSERT(p != nullptr, comment);
0215     __TBB_ASSERT(!is_poisoned(p), comment);
0216 #if !(_MSC_VER && _MSC_VER <= 1900 && !__INTEL_COMPILER)
0217     __TBB_ASSERT(is_aligned(p, alignment == 0 ? alignof(T) : alignment), comment);
0218 #endif
0219     // Returns something to simplify assert_pointers_valid implementation.
0220     return true;
0221 }
0222
0223 template <typename... Args>
0224 void assert_pointers_valid(Args*... p) {
0225     // suppress_unused_warning is used as an evaluation context for the variadic pack.
0226     suppress_unused_warning(assert_pointer_valid(p)...);
0227 }
0228
0229 //! Base class for types that should not be assigned.
0230 class no_assign {
0231 public:
0232     void operator=(const no_assign&) = delete;
0233     no_assign(const no_assign&) = default;
0234     no_assign() = default;
0235 };
0236
0237 //! Base class for types that should not be copied or assigned.
0238 class no_copy: no_assign {
0239 public:
0240     no_copy(const no_copy&) = delete;
0241     no_copy() = default;
0242 };
0243
0244 template <typename T>
0245 void swap_atomics_relaxed(std::atomic<T>& lhs, std::atomic<T>& rhs){
0246     T tmp = lhs.load(std::memory_order_relaxed);
0247     lhs.store(rhs.load(std::memory_order_relaxed), std::memory_order_relaxed);
0248     rhs.store(tmp, std::memory_order_relaxed);
0249 }
0250
0251 //! One-time initialization states
0252 enum class do_once_state {
0253     uninitialized = 0,      ///< No execution attempts have been undertaken yet
0254     pending,                ///< A thread is executing associated do-once routine
0255     executed,               ///< Do-once routine has been executed
0256     initialized = executed  ///< Convenience alias
0257 };
0258
0259 //! One-time initialization function
0260 /** /param initializer Pointer to function without arguments
0261            The variant that returns bool is used for cases when initialization can fail
0262            and it is OK to continue execution, but the state should be reset so that
0263            the initialization attempt was repeated the next time.
0264     /param state Shared state associated with initializer that specifies its
0265             initialization state. Must be initially set to #uninitialized value
0266             (e.g. by means of default static zero initialization). **/
0267 template <typename F>
0268 void atomic_do_once( const F& initializer, std::atomic<do_once_state>& state ) {
0269     // The loop in the implementation is necessary to avoid race when thread T2
0270     // that arrived in the middle of initialization attempt by another thread T1
0271     // has just made initialization possible.
0272     // In such a case T2 has to rely on T1 to initialize, but T1 may already be past
0273     // the point where it can recognize the changed conditions.
0274     do_once_state expected_state;
0275     while ( state.load( std::memory_order_acquire ) != do_once_state::executed ) {
0276         if( state.load( std::memory_order_relaxed ) == do_once_state::uninitialized ) {
0277             expected_state = do_once_state::uninitialized;
0278 #if defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 1910
0279             using enum_type = typename std::underlying_type<do_once_state>::type;
0280             if( ((std::atomic<enum_type>&)state).compare_exchange_strong( (enum_type&)expected_state, (enum_type)do_once_state::pending ) ) {
0281 #else
0282             if( state.compare_exchange_strong( expected_state, do_once_state::pending ) ) {
0283 #endif
0284                 run_initializer( initializer, state );
0285                 break;
0286             }
0287         }
0288         spin_wait_while_eq( state, do_once_state::pending );
0289     }
0290 }
0291
0292 // Run the initializer which can not fail
0293 template<typename Functor>
0294 void run_initializer(const Functor& f, std::atomic<do_once_state>& state ) {
0295     f();
0296     state.store(do_once_state::executed, std::memory_order_release);
0297 }
0298
0299 #if __TBB_CPP20_CONCEPTS_PRESENT
0300 template <typename T>
0301 concept boolean_testable_impl = std::convertible_to<T, bool>;
0302
0303 template <typename T>
0304 concept boolean_testable = boolean_testable_impl<T> && requires( T&& t ) {
0305                                { !std::forward<T>(t) } -> boolean_testable_impl;
0306                            };
0307
0308 #if __TBB_CPP20_COMPARISONS_PRESENT
0309 struct synthesized_three_way_comparator {
0310     template <typename T1, typename T2>
0311     auto operator()( const T1& lhs, const T2& rhs ) const
0312         requires requires {
0313             { lhs < rhs } -> boolean_testable;
0314             { rhs < lhs } -> boolean_testable;
0315         }
0316     {
0317         if constexpr (std::three_way_comparable_with<T1, T2>) {
0318             return lhs <=> rhs;
0319         } else {
0320             if (lhs < rhs) {
0321                 return std::weak_ordering::less;
0322             }
0323             if (rhs < lhs) {
0324                 return std::weak_ordering::greater;
0325             }
0326             return std::weak_ordering::equivalent;
0327         }
0328     }
0329 }; // struct synthesized_three_way_comparator
0330
0331 template <typename T1, typename T2 = T1>
0332 using synthesized_three_way_result = decltype(synthesized_three_way_comparator{}(std::declval<T1&>(),
0333                                                                                  std::declval<T2&>()));
0334
0335 #endif // __TBB_CPP20_COMPARISONS_PRESENT
0336
0337 // Check if the type T is implicitly OR explicitly convertible to U
0338 template <typename T, typename U>
0339 concept relaxed_convertible_to = std::constructible_from<U, T>;
0340
0341 template <typename T, typename U>
0342 concept adaptive_same_as =
0343 #if __TBB_STRICT_CONSTRAINTS
0344     std::same_as<T, U>;
0345 #else
0346     std::convertible_to<T, U>;
0347 #endif
0348 #endif // __TBB_CPP20_CONCEPTS_PRESENT
0349
0350 template <typename F, typename... Args>
0351 auto invoke(F&& f, Args&&... args)
0352 #if __TBB_CPP17_INVOKE_PRESENT
0353     noexcept(std::is_nothrow_invocable_v<F, Args...>)
0354     -> std::invoke_result_t<F, Args...>
0355 {
0356     return std::invoke(std::forward<F>(f), std::forward<Args>(args)...);
0357 }
0358 #else // __TBB_CPP17_INVOKE_PRESENT
0359     noexcept(noexcept(std::forward<F>(f)(std::forward<Args>(args)...)))
0360     -> decltype(std::forward<F>(f)(std::forward<Args>(args)...))
0361 {
0362     return std::forward<F>(f)(std::forward<Args>(args)...);
0363 }
0364 #endif // __TBB_CPP17_INVOKE_PRESENT
0365
0366 } // namespace d0
0367
0368 namespace d1 {
0369
0370 class delegate_base {
0371 public:
0372     virtual bool operator()() const = 0;
0373     virtual ~delegate_base() {}
0374 };
0375
0376 template <typename FuncType>
0377 class delegated_function : public delegate_base {
0378 public:
0379     delegated_function(FuncType& f) : my_func(f) {}
0380
0381     bool operator()() const override {
0382         return my_func();
0383     }
0384
0385 private:
0386     FuncType &my_func;
0387 };
0388 } // namespace d1
0389
0390 } // namespace detail
0391 } // namespace tbb
0392
0393 #endif // __TBB_detail__utils_H