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 #include "oneapi/tbb/detail/_assert.h"
18 #include "oneapi/tbb/detail/_rtm_rw_mutex.h"
19 #include "itt_notify.h"
20 #include "governor.h"
21 #include "misc.h"
22
23 #include <atomic>
24
25 namespace tbb {
26 namespace detail {
27 namespace r1 {
28
29 struct rtm_rw_mutex_impl {
30 // maximum number of times to retry
31 // TODO: experiment on retry values.
32 static constexpr int retry_threshold_read = 10;
33 static constexpr int retry_threshold_write = 10;
34 using transaction_result_type = decltype(begin_transaction());
35
36 //! Release speculative mutex
releasetbb::detail::r1::rtm_rw_mutex_impl37 static void release(d1::rtm_rw_mutex::scoped_lock& s) {
38 switch(s.m_transaction_state) {
39 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer:
40 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader:
41 __TBB_ASSERT(is_in_transaction(), "m_transaction_state && not speculating");
42 end_transaction();
43 s.m_mutex = nullptr;
44 break;
45 case d1::rtm_rw_mutex::rtm_type::rtm_real_reader:
46 __TBB_ASSERT(!s.m_mutex->write_flag.load(std::memory_order_relaxed), "write_flag set but read lock acquired");
47 s.m_mutex->unlock_shared();
48 s.m_mutex = nullptr;
49 break;
50 case d1::rtm_rw_mutex::rtm_type::rtm_real_writer:
51 __TBB_ASSERT(s.m_mutex->write_flag.load(std::memory_order_relaxed), "write_flag unset but write lock acquired");
52 s.m_mutex->write_flag.store(false, std::memory_order_relaxed);
53 s.m_mutex->unlock();
54 s.m_mutex = nullptr;
55 break;
56 case d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex:
57 __TBB_ASSERT(false, "rtm_not_in_mutex, but in release");
58 break;
59 default:
60 __TBB_ASSERT(false, "invalid m_transaction_state");
61 }
62 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex;
63 }
64
65 //! Acquire write lock on the given mutex.
acquire_writertbb::detail::r1::rtm_rw_mutex_impl66 static void acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) {
67 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, "scoped_lock already in transaction");
68 if(governor::speculation_enabled()) {
69 int num_retries = 0;
70 transaction_result_type abort_code = 0;
71 do {
72 if(m.m_state.load(std::memory_order_acquire)) {
73 if(only_speculate) return;
74 spin_wait_until_eq(m.m_state, d1::rtm_rw_mutex::state_type(0));
75 }
76 // _xbegin returns -1 on success or the abort code, so capture it
77 if((abort_code = begin_transaction()) == transaction_result_type(speculation_successful_begin))
78 {
79 // started speculation
80 if(m.m_state.load(std::memory_order_relaxed)) { // add spin_rw_mutex to read-set.
81 // reader or writer grabbed the lock, so abort.
82 abort_transaction();
83 }
84 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer;
85 // Don not wrap the following assignment to a function,
86 // because it can abort the transaction in debug. Need mutex for release().
87 s.m_mutex = &m;
88 return; // successfully started speculation
89 }
90 ++num_retries;
91 } while((abort_code & speculation_retry) != 0 && (num_retries < retry_threshold_write));
92 }
93
94 if(only_speculate) return;
95 s.m_mutex = &m; // should apply a real try_lock...
96 s.m_mutex->lock(); // kill transactional writers
97 __TBB_ASSERT(!m.write_flag.load(std::memory_order_relaxed), "After acquire for write, write_flag already true");
98 m.write_flag.store(true, std::memory_order_relaxed); // kill transactional readers
99 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_writer;
100 return;
101 }
102
103 //! Acquire read lock on given mutex.
104 // only_speculate : true if we are doing a try_acquire. If true and we fail to speculate, don't
105 // really acquire the lock, return and do a try_acquire on the contained spin_rw_mutex. If
106 // the lock is already held by a writer, just return.
acquire_readertbb::detail::r1::rtm_rw_mutex_impl107 static void acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) {
108 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, "scoped_lock already in transaction");
109 if(governor::speculation_enabled()) {
110 int num_retries = 0;
111 transaction_result_type abort_code = 0;
112 do {
113 // if in try_acquire, and lock is held as writer, don't attempt to speculate.
114 if(m.write_flag.load(std::memory_order_acquire)) {
115 if(only_speculate) return;
116 spin_wait_while_eq(m.write_flag, true);
117 }
118 // _xbegin returns -1 on success or the abort code, so capture it
119 if((abort_code = begin_transaction()) == transaction_result_type(speculation_successful_begin))
120 {
121 // started speculation
122 if(m.write_flag.load(std::memory_order_relaxed)) { // add write_flag to read-set.
123 abort_transaction(); // writer grabbed the lock, so abort.
124 }
125 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader;
126 // Don not wrap the following assignment to a function,
127 // because it can abort the transaction in debug. Need mutex for release().
128 s.m_mutex = &m;
129 return; // successfully started speculation
130 }
131 // fallback path
132 // retry only if there is any hope of getting into a transaction soon
133 // Retry in the following cases (from Section 8.3.5 of
134 // Intel(R) Architecture Instruction Set Extensions Programming Reference):
135 // 1. abort caused by XABORT instruction (bit 0 of EAX register is set)
136 // 2. the transaction may succeed on a retry (bit 1 of EAX register is set)
137 // 3. if another logical processor conflicted with a memory address
138 // that was part of the transaction that aborted (bit 2 of EAX register is set)
139 // That is, retry if (abort_code & 0x7) is non-zero
140 ++num_retries;
141 } while((abort_code & speculation_retry) != 0 && (num_retries < retry_threshold_read));
142 }
143
144 if(only_speculate) return;
145 s.m_mutex = &m;
146 s.m_mutex->lock_shared();
147 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader;
148 }
149
150 //! Upgrade reader to become a writer.
151 /** Returns whether the upgrade happened without releasing and re-acquiring the lock */
upgradetbb::detail::r1::rtm_rw_mutex_impl152 static bool upgrade(d1::rtm_rw_mutex::scoped_lock& s) {
153 switch(s.m_transaction_state) {
154 case d1::rtm_rw_mutex::rtm_type::rtm_real_reader: {
155 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_writer;
156 bool no_release = s.m_mutex->upgrade();
157 __TBB_ASSERT(!s.m_mutex->write_flag.load(std::memory_order_relaxed), "After upgrade, write_flag already true");
158 s.m_mutex->write_flag.store(true, std::memory_order_relaxed);
159 return no_release;
160 }
161 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader: {
162 d1::rtm_rw_mutex& m = *s.m_mutex;
163 if(m.m_state.load(std::memory_order_acquire)) { // add spin_rw_mutex to read-set.
164 // Real reader or writer holds the lock; so commit the read and re-acquire for write.
165 release(s);
166 acquire_writer(m, s, false);
167 return false;
168 } else
169 {
170 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer;
171 return true;
172 }
173 }
174 default:
175 __TBB_ASSERT(false, "Invalid state for upgrade");
176 return false;
177 }
178 }
179
180 //! Downgrade writer to a reader.
downgradetbb::detail::r1::rtm_rw_mutex_impl181 static bool downgrade(d1::rtm_rw_mutex::scoped_lock& s) {
182 switch (s.m_transaction_state) {
183 case d1::rtm_rw_mutex::rtm_type::rtm_real_writer:
184 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader;
185 __TBB_ASSERT(s.m_mutex->write_flag.load(std::memory_order_relaxed), "Before downgrade write_flag not true");
186 s.m_mutex->write_flag.store(false, std::memory_order_relaxed);
187 s.m_mutex->downgrade();
188 return true;
189 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer:
190 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader;
191 return true;
192 default:
193 __TBB_ASSERT(false, "Invalid state for downgrade");
194 return false;
195 }
196 }
197
198 //! Try to acquire write lock on the given mutex.
199 // There may be reader(s) which acquired the spin_rw_mutex, as well as possibly
200 // transactional reader(s). If this is the case, the acquire will fail, and assigning
201 // write_flag will kill the transactors. So we only assign write_flag if we have successfully
202 // acquired the lock.
try_acquire_writertbb::detail::r1::rtm_rw_mutex_impl203 static bool try_acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) {
204 acquire_writer(m, s, /*only_speculate=*/true);
205 if (s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer) {
206 return true;
207 }
208 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, NULL);
209 // transacting write acquire failed. try_lock the real mutex
210 if (m.try_lock()) {
211 s.m_mutex = &m;
212 // only shoot down readers if we're not transacting ourselves
213 __TBB_ASSERT(!m.write_flag.load(std::memory_order_relaxed), "After try_acquire_writer, write_flag already true");
214 m.write_flag.store(true, std::memory_order_relaxed);
215 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_writer;
216 return true;
217 }
218 return false;
219 }
220
221 //! Try to acquire read lock on the given mutex.
try_acquire_readertbb::detail::r1::rtm_rw_mutex_impl222 static bool try_acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) {
223 // speculatively acquire the lock. If this fails, do try_lock_shared on the spin_rw_mutex.
224 acquire_reader(m, s, /*only_speculate=*/true);
225 if (s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader) {
226 return true;
227 }
228 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, NULL);
229 // transacting read acquire failed. try_lock_shared the real mutex
230 if (m.try_lock_shared()) {
231 s.m_mutex = &m;
232 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader;
233 return true;
234 }
235 return false;
236 }
237 };
238
acquire_writer(d1::rtm_rw_mutex & m,d1::rtm_rw_mutex::scoped_lock & s,bool only_speculate)239 void __TBB_EXPORTED_FUNC acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) {
240 rtm_rw_mutex_impl::acquire_writer(m, s, only_speculate);
241 }
242 //! Internal acquire read lock.
243 // only_speculate == true if we're doing a try_lock, else false.
acquire_reader(d1::rtm_rw_mutex & m,d1::rtm_rw_mutex::scoped_lock & s,bool only_speculate)244 void __TBB_EXPORTED_FUNC acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) {
245 rtm_rw_mutex_impl::acquire_reader(m, s, only_speculate);
246 }
247 //! Internal upgrade reader to become a writer.
upgrade(d1::rtm_rw_mutex::scoped_lock & s)248 bool __TBB_EXPORTED_FUNC upgrade(d1::rtm_rw_mutex::scoped_lock& s) {
249 return rtm_rw_mutex_impl::upgrade(s);
250 }
251 //! Internal downgrade writer to become a reader.
downgrade(d1::rtm_rw_mutex::scoped_lock & s)252 bool __TBB_EXPORTED_FUNC downgrade(d1::rtm_rw_mutex::scoped_lock& s) {
253 return rtm_rw_mutex_impl::downgrade(s);
254 }
255 //! Internal try_acquire write lock.
try_acquire_writer(d1::rtm_rw_mutex & m,d1::rtm_rw_mutex::scoped_lock & s)256 bool __TBB_EXPORTED_FUNC try_acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) {
257 return rtm_rw_mutex_impl::try_acquire_writer(m, s);
258 }
259 //! Internal try_acquire read lock.
try_acquire_reader(d1::rtm_rw_mutex & m,d1::rtm_rw_mutex::scoped_lock & s)260 bool __TBB_EXPORTED_FUNC try_acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) {
261 return rtm_rw_mutex_impl::try_acquire_reader(m, s);
262 }
263 //! Internal release lock.
release(d1::rtm_rw_mutex::scoped_lock & s)264 void __TBB_EXPORTED_FUNC release(d1::rtm_rw_mutex::scoped_lock& s) {
265 rtm_rw_mutex_impl::release(s);
266 }
267
268 } // namespace r1
269 } // namespace detail
270 } // namespace tbb
271
272
273