tbb/detail/_utils.h

/*
    Copyright (c) 2005-2021 Intel Corporation

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

        http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
*/

#ifndef __TBB_detail__utils_H
#define __TBB_detail__utils_H

#include <type_traits>
#include <cstdint>
#include <atomic>

#include "_config.h"
#include "_assert.h"
#include "_machine.h"

namespace tbb {
namespace detail {
inline namespace d0 {

//! Utility template function to prevent "unused" warnings by various compilers.
template<typename... T> void suppress_unused_warning(T&&...) {}

//! Compile-time constant that is upper bound on cache line/sector size.
/** It should be used only in situations where having a compile-time upper
  bound is more useful than a run-time exact answer.
  @ingroup memory_allocation */
constexpr size_t max_nfs_size = 128;
constexpr std::size_t max_nfs_size_exp = 7;
static_assert(1 << max_nfs_size_exp == max_nfs_size, "max_nfs_size_exp must be a log2(max_nfs_size)");

//! Class that implements exponential backoff.
class atomic_backoff {
    //! Time delay, in units of "pause" instructions.
    /** Should be equal to approximately the number of "pause" instructions
      that take the same time as an context switch. Must be a power of two.*/
    static constexpr std::int32_t LOOPS_BEFORE_YIELD = 16;
    std::int32_t count;

public:
    // In many cases, an object of this type is initialized eagerly on hot path,
    // as in for(atomic_backoff b; ; b.pause()) { /*loop body*/ }
    // For this reason, the construction cost must be very small!
    atomic_backoff() : count(1) {}
    // This constructor pauses immediately; do not use on hot paths!
    atomic_backoff(bool) : count(1) { pause(); }

    //! No Copy
    atomic_backoff(const atomic_backoff&) = delete;
    atomic_backoff& operator=(const atomic_backoff&) = delete;

    //! Pause for a while.
    void pause() {
        if (count <= LOOPS_BEFORE_YIELD) {
            machine_pause(count);
            // Pause twice as long the next time.
            count *= 2;
        } else {
            // Pause is so long that we might as well yield CPU to scheduler.
            yield();
        }
    }

    //! Pause for a few times and return false if saturated.
    bool bounded_pause() {
        machine_pause(count);
        if (count < LOOPS_BEFORE_YIELD) {
            // Pause twice as long the next time.
            count *= 2;
            return true;
        } else {
            return false;
        }
    }

    void reset() {
        count = 1;
    }
};

//! Spin WHILE the condition is true.
/** T and U should be comparable types. */
template <typename T, typename C>
T spin_wait_while(const std::atomic<T>& location, C comp, std::memory_order order) {
    atomic_backoff backoff;
    T snapshot = location.load(order);
    while (comp(snapshot)) {
        backoff.pause();
        snapshot = location.load(order);
    }
    return snapshot;
}

//! Spin WHILE the value of the variable is equal to a given value
/** T and U should be comparable types. */
template <typename T, typename U>
T spin_wait_while_eq(const std::atomic<T>& location, const U value, std::memory_order order = std::memory_order_acquire) {
    return spin_wait_while(location, [&value](T t) { return t == value; }, order);
}

//! Spin UNTIL the value of the variable is equal to a given value
/** T and U should be comparable types. */
template<typename T, typename U>
T spin_wait_until_eq(const std::atomic<T>& location, const U value, std::memory_order order = std::memory_order_acquire) {
    return spin_wait_while(location, [&value](T t) { return t != value; }, order);
}

//! Spin UNTIL the condition returns true or spinning time is up.
/** Returns what the passed functor returned last time it was invoked. */
template <typename Condition>
bool timed_spin_wait_until(Condition condition) {
    // 32 pauses + 32 yields are meausered as balanced spin time before sleep.
    bool finish = condition();
    for (int i = 1; !finish && i < 32; finish = condition(), i *= 2) {
        machine_pause(i);
    }
    for (int i = 32; !finish && i < 64; finish = condition(), ++i) {
        yield();
    }
    return finish;
}

template <typename T>
std::uintptr_t log2(T in) {
    __TBB_ASSERT(in > 0, "The logarithm of a non-positive value is undefined.");
    return machine_log2(in);
}

template<typename T>
T reverse_bits(T src) {
    return machine_reverse_bits(src);
}

template<typename T>
T reverse_n_bits(T src, std::size_t n) {
    __TBB_ASSERT(n != 0, "Reverse for 0 bits is undefined behavior.");
    return reverse_bits(src) >> (number_of_bits<T>() - n);
}

// A function to check if passed integer is a power of two
template <typename IntegerType>
constexpr bool is_power_of_two( IntegerType arg ) {
    static_assert(std::is_integral<IntegerType>::value,
                  "An argument for is_power_of_two should be integral type");
    return arg && (0 == (arg & (arg - 1)));
}

// A function to determine if passed integer is a power of two
// at least as big as another power of two, i.e. for strictly positive i and j,
// with j being a power of two, determines whether i==j<<k for some nonnegative k
template <typename ArgIntegerType, typename DivisorIntegerType>
constexpr bool is_power_of_two_at_least(ArgIntegerType arg, DivisorIntegerType divisor) {
    // Divisor should be a power of two
    static_assert(std::is_integral<ArgIntegerType>::value,
                  "An argument for is_power_of_two_at_least should be integral type");
    return 0 == (arg & (arg - divisor));
}

// A function to compute arg modulo divisor where divisor is a power of 2.
template<typename ArgIntegerType, typename DivisorIntegerType>
inline ArgIntegerType modulo_power_of_two(ArgIntegerType arg, DivisorIntegerType divisor) {
    __TBB_ASSERT( is_power_of_two(divisor), "Divisor should be a power of two" );
    return arg & (divisor - 1);
}

//! A function to check if passed in pointer is aligned on a specific border
template<typename T>
constexpr bool is_aligned(T* pointer, std::uintptr_t alignment) {
    return 0 == ((std::uintptr_t)pointer & (alignment - 1));
}

#if TBB_USE_ASSERT
static void* const poisoned_ptr = reinterpret_cast<void*>(-1);

//! Set p to invalid pointer value.
template<typename T>
inline void poison_pointer( T* &p ) { p = reinterpret_cast<T*>(poisoned_ptr); }

template<typename T>
inline void poison_pointer(std::atomic<T*>& p) { p.store(reinterpret_cast<T*>(poisoned_ptr), std::memory_order_relaxed); }

/** Expected to be used in assertions only, thus no empty form is defined. **/
template<typename T>
inline bool is_poisoned( T* p ) { return p == reinterpret_cast<T*>(poisoned_ptr); }

template<typename T>
inline bool is_poisoned(const std::atomic<T*>& p) { return is_poisoned(p.load(std::memory_order_relaxed)); }
#else
template<typename T>
inline void poison_pointer(T* &) {/*do nothing*/}

template<typename T>
inline void poison_pointer(std::atomic<T*>&) { /* do nothing */}
#endif /* !TBB_USE_ASSERT */

template <std::size_t alignment = 0, typename T>
bool assert_pointer_valid(T* p, const char* comment = nullptr) {
    suppress_unused_warning(p, comment);
    __TBB_ASSERT(p != nullptr, comment);
    __TBB_ASSERT(!is_poisoned(p), comment);
#if !(_MSC_VER && _MSC_VER <= 1900 && !__INTEL_COMPILER)
    __TBB_ASSERT(is_aligned(p, alignment == 0 ? alignof(T) : alignment), comment);
#endif
    // Returns something to simplify assert_pointers_valid implementation.
    return true;
}

template <typename... Args>
void assert_pointers_valid(Args*... p) {
    // suppress_unused_warning is used as an evaluation context for the variadic pack.
    suppress_unused_warning(assert_pointer_valid(p)...);
}

//! Base class for types that should not be assigned.
class no_assign {
public:
    void operator=(const no_assign&) = delete;
    no_assign(const no_assign&) = default;
    no_assign() = default;
};

//! Base class for types that should not be copied or assigned.
class no_copy: no_assign {
public:
    no_copy(const no_copy&) = delete;
    no_copy() = default;
};

template <typename T>
void swap_atomics_relaxed(std::atomic<T>& lhs, std::atomic<T>& rhs){
    T tmp = lhs.load(std::memory_order_relaxed);
    lhs.store(rhs.load(std::memory_order_relaxed), std::memory_order_relaxed);
    rhs.store(tmp, std::memory_order_relaxed);
}

//! One-time initialization states
enum class do_once_state {
    uninitialized = 0,      ///< No execution attempts have been undertaken yet
    pending,                ///< A thread is executing associated do-once routine
    executed,               ///< Do-once routine has been executed
    initialized = executed  ///< Convenience alias
};

//! One-time initialization function
/** /param initializer Pointer to function without arguments
           The variant that returns bool is used for cases when initialization can fail
           and it is OK to continue execution, but the state should be reset so that
           the initialization attempt was repeated the next time.
    /param state Shared state associated with initializer that specifies its
            initialization state. Must be initially set to #uninitialized value
            (e.g. by means of default static zero initialization). **/
template <typename F>
void atomic_do_once( const F& initializer, std::atomic<do_once_state>& state ) {
    // The loop in the implementation is necessary to avoid race when thread T2
    // that arrived in the middle of initialization attempt by another thread T1
    // has just made initialization possible.
    // In such a case T2 has to rely on T1 to initialize, but T1 may already be past
    // the point where it can recognize the changed conditions.
    do_once_state expected_state;
    while ( state.load( std::memory_order_acquire ) != do_once_state::executed ) {
        if( state.load( std::memory_order_relaxed ) == do_once_state::uninitialized ) {
            expected_state = do_once_state::uninitialized;
#if defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 1910
            using enum_type = typename std::underlying_type<do_once_state>::type;
            if( ((std::atomic<enum_type>&)state).compare_exchange_strong( (enum_type&)expected_state, (enum_type)do_once_state::pending ) ) {
#else
            if( state.compare_exchange_strong( expected_state, do_once_state::pending ) ) {
#endif
                run_initializer( initializer, state );
                break;
            }
        }
        spin_wait_while_eq( state, do_once_state::pending );
    }
}

// Run the initializer which can not fail
template<typename Functor>
void run_initializer(const Functor& f, std::atomic<do_once_state>& state ) {
    f();
    state.store(do_once_state::executed, std::memory_order_release);
}

#if __TBB_CPP20_CONCEPTS_PRESENT
template <typename T>
concept boolean_testable_impl = std::convertible_to<T, bool>;

template <typename T>
concept boolean_testable = boolean_testable_impl<T> && requires( T&& t ) {
                               { !std::forward<T>(t) } -> boolean_testable_impl;
                           };

#if __TBB_CPP20_COMPARISONS_PRESENT
struct synthesized_three_way_comparator {
    template <typename T1, typename T2>
    auto operator()( const T1& lhs, const T2& rhs ) const
        requires requires {
            { lhs < rhs } -> boolean_testable;
            { rhs < lhs } -> boolean_testable;
        }
    {
        if constexpr (std::three_way_comparable_with<T1, T2>) {
            return lhs <=> rhs;
        } else {
            if (lhs < rhs) {
                return std::weak_ordering::less;
            }
            if (rhs < lhs) {
                return std::weak_ordering::greater;
            }
            return std::weak_ordering::equivalent;
        }
    }
}; // struct synthesized_three_way_comparator

template <typename T1, typename T2 = T1>
using synthesized_three_way_result = decltype(synthesized_three_way_comparator{}(std::declval<T1&>(),
                                                                                 std::declval<T2&>()));

#endif // __TBB_CPP20_COMPARISONS_PRESENT

// Check if the type T is implicitly OR explicitly convertible to U
template <typename T, typename U>
concept relaxed_convertible_to = std::constructible_from<U, T>;

template <typename T, typename U>
concept adaptive_same_as =
#if __TBB_STRICT_CONSTRAINTS
    std::same_as<T, U>;
#else
    std::convertible_to<T, U>;
#endif
#endif // __TBB_CPP20_CONCEPTS_PRESENT

} // namespace d0

namespace d1 {

class delegate_base {
public:
    virtual bool operator()() const = 0;
    virtual ~delegate_base() {}
};

template <typename FuncType>
class delegated_function : public delegate_base {
public:
    delegated_function(FuncType& f) : my_func(f) {}

    bool operator()() const override {
        return my_func();
    }

private:
    FuncType &my_func;
};
} // namespace d1

} // namespace detail
} // namespace tbb

#endif // __TBB_detail__utils_H