1 /* 2 Copyright (c) 2005-2021 Intel Corporation 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 #ifndef __TBB_test_common_utils_H 18 #define __TBB_test_common_utils_H 19 20 #include "config.h" 21 22 #include <oneapi/tbb/detail/_template_helpers.h> 23 #include <oneapi/tbb/detail/_config.h> 24 #include <oneapi/tbb/blocked_range.h> 25 #include <thread> 26 #include <type_traits> 27 #include <memory> 28 #include <array> 29 #include <cstdint> 30 #include <vector> 31 #include <limits> 32 #include <algorithm> 33 #include <cstring> 34 #include <chrono> 35 36 #if HARNESS_TBBMALLOC_THREAD_SHUTDOWN && __TBB_SOURCE_DIRECTLY_INCLUDED && (_WIN32 || _WIN64) 37 #include "../../src/tbbmalloc/tbbmalloc_internal_api.h" 38 #endif 39 40 #include "dummy_body.h" 41 #include "utils_yield.h" 42 #include "utils_assert.h" 43 44 namespace utils { 45 46 #define utils_fallthrough __TBB_fallthrough 47 48 using tbb::detail::try_call; 49 50 template<typename It> 51 typename std::iterator_traits<It>::value_type median(It first, It last) { 52 std::sort(first, last); 53 typename std::iterator_traits<It>::difference_type distance = std::distance(first, last); 54 std::advance(first, distance / 2 - 1); 55 if (distance % 2 == 0) { 56 // Wrote iterators in variables because of warning: <sequence-point> 57 auto curr_element = first; 58 auto next_element = ++first; 59 return typename std::iterator_traits<It>::value_type((*curr_element + *(++next_element)) / 2); 60 } else { 61 return typename std::iterator_traits<It>::value_type(*first); 62 } 63 } 64 65 static constexpr std::uint8_t MinThread = 1; 66 static constexpr std::uint8_t MaxThread = 4; 67 68 //! Simple native parallel loop where each iteration is executed in a different thread 69 template <typename Index, typename Body> 70 void NativeParallelFor( Index Number, const Body& body ) { 71 std::vector<std::thread> thread_pool; 72 for (Index idx = 0; idx < Number; ++idx) { 73 thread_pool.emplace_back([&body, idx] { 74 body(idx); 75 #if HARNESS_TBBMALLOC_THREAD_SHUTDOWN && __TBB_SOURCE_DIRECTLY_INCLUDED && (_WIN32 || _WIN64) 76 // in those cases can't release per-thread cache automatically, so do it manually 77 // TODO: investigate less-intrusive way to do it, for example via FLS keys 78 __TBB_mallocThreadShutdownNotification(); 79 #endif 80 }); 81 } 82 83 for (auto& thread : thread_pool) { 84 thread.join(); 85 } 86 } 87 88 //! Native parallel loop with grainsize (like tbb::blocked_range) 89 template <typename Index, typename Body> 90 void NativeParallelFor( Index Number, Index block_size, const Body& body ) { 91 NativeParallelFor(Number / block_size, [block_size, &body] (Index idx) { 92 for (Index i = idx * block_size; i < (idx + 1) * block_size; ++i) { 93 body(i); 94 } 95 }); 96 } 97 98 //! Utility template function to prevent "unused" warnings by various compilers. 99 template<typename... T> void suppress_unused_warning(T&&...) {} 100 101 namespace detail { 102 103 template <std::size_t size> 104 struct fixed_width_uint; 105 106 template <> struct fixed_width_uint<1>{ using type = uint8_t; }; 107 template <> struct fixed_width_uint<2>{ using type = uint16_t; }; 108 template <> struct fixed_width_uint<4>{ using type = uint32_t; }; 109 template <> struct fixed_width_uint<8>{ using type = uint64_t; }; 110 111 template <typename In> 112 typename fixed_width_uint<sizeof(In)>::type fixed_width_cast(In in) { 113 return static_cast<typename fixed_width_uint<sizeof(In)>::type>(in); 114 } 115 116 117 static constexpr std::array<uint64_t, 64> Primes = {{ 118 0x9e3779b13346320e, 0xffe6cc5974101cb7, 0x2109f6dd6aaac9c9, 0x43977ab5f3dbca42, 119 0xba5703f59405b746, 0xb495a877a86fb54e, 0xe1626741ae21caf5, 0x79695e6bc8febd31, 120 0xbc98c09f76a304e0, 0xd5bee2b3513a491d, 0x287488f9933e6cb9, 0x3af18231269a8b29, 121 0x9677cd4ddbc9d5b1, 0xbe3a6929ddd2a556, 0xadc6a877a2f30f00, 0xdcf0674bb6968d97, 122 0xbe4d6fe991c0538d, 0x5f15e201c9cc571e, 0x99afc3fd0f27f767, 0xf3f16801361d4489, 123 0xe222cfffee1eec74, 0x24ba5fdb21098d07, 0x0620452d45401c7f, 0x79f149e30a92241f, 124 0xc8b93f49e4fe3077, 0x972702cd3aac3d56, 0xb07dd827a9126d73, 0x6c97d5ed60811c65, 125 0x085a3d61d2e858f8, 0x46eb5ea7ce433ba1, 0x3d9910edfc8bb30a, 0x2e687b5b6226023c, 126 0x296092277d3fd038, 0x6eb081f199767dbe, 0x0954c4e114d147dd, 0x9d114db92a2a629a, 127 0x542acfa9232adfb9, 0xb3e6bd7bddd0e31e, 0x0742d917c18e24dc, 0xe9f3ffa78ba59fab, 128 0x54581edb3717eaf7, 0xf2480f45494a28c9, 0x0bb9288ff4884f1b, 0xef1affc7bb0a5916, 129 0x85fa0ca7da978b79, 0x3ccc14db2137131b, 0xe6baf34b9bb9ade8, 0x343377f7e00c0852, 130 0x5ca190311bef1612, 0xe6d9293bc4c93e07, 0xf0a9f391680e1894, 0x5d2e980bb090bd62, 131 0xfc41107323c82d43, 0xc3749363812d28e8, 0xb892d829b0357953, 0x3549366b9e23bb94, 132 0x629750ad007fd05c, 0xb98294e53416fada, 0x892d9483bb3deae3, 0xc235baf386c925e4, 133 0x3d2402a37346a4b0, 0x6bdef3c95be05f43, 0xbec333cd1928a169, 0x40c9520f59e003fa 134 }}; 135 } 136 137 //! A fast random number generator. 138 /* Uses linear congruential method. */ 139 template <std::size_t size = 2> 140 class FastRandom { 141 public: 142 using result_type = typename ::utils::detail::fixed_width_uint<size>::type; 143 144 //! Construct a random number generator. 145 explicit FastRandom( uint64_t seed ) 146 : my_seed(seed), 147 my_prime(detail::Primes[my_seed % detail::Primes.size()]) {} 148 149 static constexpr result_type max() { 150 return my_max; 151 } 152 153 static constexpr result_type min() { 154 return my_min; 155 } 156 //! Get a random number for the given seed; update the seed for next use. 157 result_type get( uint64_t seed ) { 158 result_type random_number = static_cast<result_type>(my_seed >> (64 - size * CHAR_BIT)); 159 my_seed = seed * my_prime + 1; 160 return random_number; 161 } 162 163 //! Get a random number 164 result_type get( ) { return get(my_seed); } 165 166 result_type operator() () { 167 return static_cast<result_type>(my_seed >> (64 - size * CHAR_BIT)) % my_max; 168 } 169 170 private: 171 uint64_t my_seed, my_prime; 172 static constexpr result_type my_max = std::numeric_limits<result_type>::max(); 173 static constexpr result_type my_min = std::numeric_limits<result_type>::min(); 174 }; 175 176 namespace iterator_type_traits { 177 178 template <typename T> using iterator_traits_value_type = typename std::iterator_traits<T>::value_type; 179 template <typename T> using iterator_traits_difference_type = typename std::iterator_traits<T>::difference_type; 180 template <typename T> using iterator_traits_pointer = typename std::iterator_traits<T>::pointer; 181 template <typename T> using iterator_traits_iterator_category = typename std::iterator_traits<T>::iterator_category; 182 183 using std::swap; 184 template <typename T> using is_swappable = decltype(swap(std::declval<T&>(), std::declval<T&>())); 185 186 template <typename T> using is_dereferenceable_by_asterisk = decltype(*std::declval<T>()); 187 template <typename T> using is_dereferenceable_by_arrow = decltype(std::declval<T>().operator->()); 188 template <typename T> using is_preincrementable = decltype(++std::declval<T>()); 189 template <typename T> using is_postincrementable = decltype(std::declval<T>()++); 190 191 template <typename T> using is_equality_comparable = decltype(std::declval<T>() == std::declval<T>()); 192 template <typename T> using is_unequality_comparable = decltype(std::declval<T>() != std::declval<T>()); 193 194 template <typename T> using is_predecrementable = decltype(--std::declval<T>()); 195 template <typename T> using is_postdecrementable = decltype(std::declval<T>()--); 196 197 template <typename T> using is_add_assignable = decltype(std::declval<T>() += std::declval<typename T::difference_type>()); 198 template <typename T> using is_sub_assignable = decltype(std::declval<T>() -= std::declval<typename T::difference_type>()); 199 200 template <typename T> using have_operator_plus = decltype(std::declval<T>() + std::declval<typename T::difference_type>()); 201 template <typename T> using have_operator_minus = decltype(std::declval<T>() + std::declval<typename T::difference_type>()); 202 203 template <typename T> using have_operator_access = decltype(std::declval<T>()[std::declval<typename T::difference_type>()]); 204 205 template <typename T> using have_operator_less = decltype(std::declval<T>() < std::declval<T>()); 206 template <typename T> using have_operator_great = decltype(std::declval<T>() > std::declval<T>()); 207 template <typename T> using have_operator_not_less = decltype(std::declval<T>() <= std::declval<T>()); 208 template <typename T> using have_operator_not_great = decltype(std::declval<T>() >= std::declval<T>()); 209 210 template <typename T> 211 using supports_iterator = tbb::detail::supports<T, iterator_traits_value_type, 212 iterator_traits_difference_type, 213 iterator_traits_pointer, 214 iterator_traits_iterator_category, 215 is_swappable, 216 is_dereferenceable_by_asterisk, 217 is_preincrementable>; 218 219 template <typename T> 220 using supports_input_iterator = tbb::detail::supports<T, is_equality_comparable, 221 is_unequality_comparable, 222 is_dereferenceable_by_arrow, 223 is_postincrementable>; 224 template <typename T> 225 using supports_bidirectional_iterator = tbb::detail::supports<T, is_predecrementable, 226 is_postdecrementable>; 227 228 template <typename T> 229 using supports_random_access_iterator = tbb::detail::supports<T, is_add_assignable, 230 is_sub_assignable, 231 have_operator_plus, 232 have_operator_minus, 233 have_operator_access, 234 have_operator_less, 235 have_operator_great, 236 have_operator_not_less, 237 have_operator_not_great>; 238 } // namespace iterator_type_traits 239 240 template <typename T> 241 struct is_iterator : std::integral_constant<bool, 242 std::is_copy_constructible<T>::value && 243 std::is_copy_assignable<T>::value && 244 std::is_destructible<T>::value && 245 iterator_type_traits::supports_iterator<T>::value> {}; 246 247 template <typename T> 248 struct is_input_iterator : std::integral_constant<bool, 249 is_iterator<T>::value && 250 iterator_type_traits::supports_input_iterator<T>::value> {}; 251 252 template <typename T> 253 struct is_forward_iterator : std::integral_constant<bool, 254 is_input_iterator<T>::value && 255 std::is_default_constructible<T>::value> {}; 256 257 template <typename T> 258 struct is_bidirectional_iterator : std::integral_constant<bool, 259 is_forward_iterator<T>::value && 260 iterator_type_traits::supports_bidirectional_iterator<T>::value> {}; 261 262 template <typename T> 263 struct is_random_access_iterator : std::integral_constant<bool, 264 is_bidirectional_iterator<T>::value && 265 iterator_type_traits::supports_random_access_iterator<T>::value> {}; 266 // The function to zero-initialize arrays; useful to avoid warnings 267 template <typename T> 268 void zero_fill( void* array, std::size_t n ) { 269 std::memset(array, 0, sizeof(T) * n); 270 } 271 272 //! Base class that asserts that no operations are made with the object after its destruction. 273 class NoAfterlife { 274 protected: 275 enum state_t { 276 LIVE = 0x56781234, 277 DEAD = 0xDEADBEEF 278 } m_state; 279 280 public: 281 NoAfterlife() : m_state(LIVE) {} 282 NoAfterlife(const NoAfterlife& src) : m_state(LIVE) { 283 CHECK_FAST_MESSAGE(src.IsLive(), "Constructing from the dead source"); 284 } 285 ~NoAfterlife() { 286 CHECK_FAST_MESSAGE(IsLive(), "Repeated destructor call"); 287 m_state = DEAD; 288 } 289 const NoAfterlife& operator=(const NoAfterlife& src) { 290 CHECK_FAST(IsLive()); 291 CHECK_FAST(src.IsLive()); 292 return *this; 293 } 294 void AssertLive() const { 295 CHECK_FAST_MESSAGE(IsLive(), "Already dead"); 296 } 297 bool IsLive() const { 298 return m_state == LIVE; 299 } 300 }; // NoAfterlife 301 302 //! Base class for types that should not be assigned. 303 class NoAssign { 304 public: 305 NoAssign& operator=(const NoAssign&) = delete; 306 NoAssign(const NoAssign&) = default; 307 NoAssign() = default; 308 }; 309 310 //! Base class for types that should not be copied or assigned. 311 class NoCopy : NoAssign { 312 public: 313 NoCopy(const NoCopy&) = delete; 314 NoCopy() = default; 315 }; 316 317 //! Base class for objects which support move ctors 318 class Movable { 319 public: 320 Movable() : alive(true) {} 321 void Reset() { alive = true; } 322 Movable(Movable&& other) { 323 CHECK_MESSAGE(other.alive, "Moving from a dead object"); 324 alive = true; 325 other.alive = false; 326 } 327 Movable& operator=(Movable&& other) { 328 CHECK_MESSAGE(alive, "Assignment to a dead object"); 329 CHECK_MESSAGE(other.alive, "Assignment of a dead object"); 330 other.alive = false; 331 return *this; 332 } 333 Movable& operator=(const Movable& other) { 334 CHECK_MESSAGE(alive, "Assignment to a dead object"); 335 CHECK_MESSAGE(other.alive, "Assignment of a dead object"); 336 return *this; 337 } 338 Movable(const Movable& other) { 339 CHECK_MESSAGE(other.alive, "Const reference to a dead object"); 340 alive = true; 341 } 342 ~Movable() { alive = false; } 343 volatile bool alive; 344 }; 345 346 class MoveOnly : Movable, NoCopy { 347 public: 348 MoveOnly() : Movable() {} 349 MoveOnly(MoveOnly&& other) : Movable(std::move(other)) {} 350 }; 351 352 void Sleep ( int ms ) { 353 std::chrono::milliseconds sleep_time( ms ); 354 std::this_thread::sleep_for( sleep_time ); 355 } 356 357 template<typename T, typename U> 358 auto max(const T& left, const U& right) -> decltype(left > right ? left : right) 359 { 360 return left > right ? left : right; 361 } 362 template<typename T, typename U> 363 auto min(const T& left, const U& right) -> decltype(left < right ? left : right) 364 { 365 return left < right ? left : right; 366 } 367 368 template<typename T, std::size_t N> 369 inline std::size_t array_length(const T(&)[N]) { 370 return N; 371 } 372 373 // TODO: consider adding a common comparator with member functions is_equal, is_less, is_greater, etc. 374 struct IsEqual { 375 template <typename T> 376 static bool compare( const std::weak_ptr<T> &t1, const std::weak_ptr<T> &t2 ) { 377 // Compare real pointers. 378 return t1.lock().get() == t2.lock().get(); 379 } 380 381 template <typename T> 382 static bool compare( const std::unique_ptr<T> &t1, const std::unique_ptr<T> &t2 ) { 383 // Compare real values. 384 return *t1 == *t2; 385 } 386 template <typename T1, typename T2> 387 static bool compare( const std::pair< const std::weak_ptr<T1>, std::weak_ptr<T2> > &t1, 388 const std::pair< const std::weak_ptr<T1>, std::weak_ptr<T2> > &t2 ) { 389 // Compare real pointers. 390 return t1.first.lock().get() == t2.first.lock().get() && 391 t1.second.lock().get() == t2.second.lock().get(); 392 } 393 template <typename T1, typename T2> 394 static bool compare( const T1 &t1, const T2 &t2 ) { 395 return t1 == t2; 396 } 397 template <typename T1, typename T2> 398 bool operator()( T1 &t1, T2 &t2) const { 399 return compare( (const T1&)t1, (const T2&)t2 ); 400 } 401 }; // struct IsEqual 402 403 template <typename T, std::size_t N> 404 tbb::blocked_range<T*> make_blocked_range( T(& array)[N] ) { 405 return tbb::blocked_range<T*>(array, array + N); 406 } 407 408 template <typename T> 409 void check_range_bounds_after_splitting( const tbb::blocked_range<T>& original, const tbb::blocked_range<T>& first, 410 const tbb::blocked_range<T>& second, const T& expected_first_end ) 411 { 412 REQUIRE(first.begin() == original.begin()); 413 REQUIRE(first.end() == expected_first_end); 414 REQUIRE(second.begin() == expected_first_end); 415 REQUIRE(second.end() == original.end()); 416 REQUIRE(first.size() + second.size() == original.size()); 417 } 418 419 template<typename M> 420 struct Counter { 421 using mutex_type = M; 422 M mutex; 423 volatile long value; 424 }; 425 426 template<typename M> 427 struct AtomicCounter { 428 using mutex_type = M; 429 M mutex; 430 std::atomic<long> value; 431 }; 432 433 #if __TBB_CPP20_CONCEPTS_PRESENT 434 template <template <typename...> class Template, typename... Types> 435 concept well_formed_instantiation = requires { 436 typename Template<Types...>; 437 }; 438 #endif // __TBB_CPP20_CONCEPTS_PRESENT 439 440 } // namespace utils 441 442 #endif // __TBB_test_common_utils_H 443