1 /*
2 Copyright (c) 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 #include "oneapi/tbb/detail/_utils.h"
18 #include "governor.h"
19 #include "concurrent_monitor.h"
20 #include "oneapi/tbb/detail/_waitable_atomic.h"
21
22 #include <type_traits>
23
24 namespace tbb {
25 namespace detail {
26 namespace r1 {
27
28 struct address_context {
29 address_context() = default;
30
address_contexttbb::detail::r1::address_context31 address_context(void* address, std::uintptr_t contex) :
32 my_address(address), my_contex(contex)
33 {}
34
35 void* my_address{nullptr};
36 std::uintptr_t my_contex{0};
37 };
38
39 class address_waiter : public concurrent_monitor_base<address_context> {
40 using base_type = concurrent_monitor_base<address_context>;
41 public:
42 using base_type::base_type;
43 /** per-thread descriptor for concurrent_monitor */
44 using thread_context = sleep_node<address_context>;
45 };
46
47 // 1024 is a rough estimate based on two assumptions:
48 // 1) there are no more than 1000 threads in the application;
49 // 2) the mutexes are optimized for short critical sections less than a couple of microseconds,
50 // which is less than 1/1000 of a time slice.
51 // In the worst case, we have single mutex that is locked and its thread is preempted.
52 // Therefore, the probability of a collision while taking unrelated mutex is about 1/size of a table.
53 static constexpr std::size_t num_address_waiters = 2 << 10;
54 static_assert(std::is_standard_layout<address_waiter>::value,
55 "address_waiter must be with standard layout");
56 static address_waiter address_waiter_table[num_address_waiters];
57
clear_address_waiter_table()58 void clear_address_waiter_table() {
59 for (std::size_t i = 0; i < num_address_waiters; ++i) {
60 address_waiter_table[i].destroy();
61 }
62 }
63
get_address_waiter(void * address)64 static address_waiter& get_address_waiter(void* address) {
65 std::uintptr_t tag = std::uintptr_t(address);
66 return address_waiter_table[((tag >> 5) ^ tag) % num_address_waiters];
67 }
68
wait_on_address(void * address,d1::delegate_base & predicate,std::uintptr_t context)69 void wait_on_address(void* address, d1::delegate_base& predicate, std::uintptr_t context) {
70 address_waiter& waiter = get_address_waiter(address);
71 waiter.wait<address_waiter::thread_context>(predicate, address_context{address, context});
72 }
73
notify_by_address(void * address,std::uintptr_t target_context)74 void notify_by_address(void* address, std::uintptr_t target_context) {
75 address_waiter& waiter = get_address_waiter(address);
76
77 auto predicate = [address, target_context] (address_context ctx) {
78 return ctx.my_address == address && ctx.my_contex == target_context;
79 };
80
81 waiter.notify_relaxed(predicate);
82 }
83
notify_by_address_one(void * address)84 void notify_by_address_one(void* address) {
85 address_waiter& waiter = get_address_waiter(address);
86
87 auto predicate = [address] (address_context ctx) {
88 return ctx.my_address == address;
89 };
90
91 waiter.notify_one_relaxed(predicate);
92 }
93
notify_by_address_all(void * address)94 void notify_by_address_all(void* address) {
95 address_waiter& waiter = get_address_waiter(address);
96
97 auto predicate = [address] (address_context ctx) {
98 return ctx.my_address == address;
99 };
100
101 waiter.notify_relaxed(predicate);
102 }
103
104 } // namespace r1
105 } // namespace detail
106 } // namespace tbb
107