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