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 37 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. 66 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 } 101 102 //! Acquire read lock on given mutex. 103 // only_speculate : true if we are doing a try_acquire. If true and we fail to speculate, don't 104 // really acquire the lock, return and do a try_acquire on the contained spin_rw_mutex. If 105 // the lock is already held by a writer, just return. 106 static void acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) { 107 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, "scoped_lock already in transaction"); 108 if(governor::speculation_enabled()) { 109 int num_retries = 0; 110 transaction_result_type abort_code = 0; 111 do { 112 // if in try_acquire, and lock is held as writer, don't attempt to speculate. 113 if(m.write_flag.load(std::memory_order_acquire)) { 114 if(only_speculate) return; 115 spin_wait_while_eq(m.write_flag, true); 116 } 117 // _xbegin returns -1 on success or the abort code, so capture it 118 if((abort_code = begin_transaction()) == transaction_result_type(speculation_successful_begin)) 119 { 120 // started speculation 121 if(m.write_flag.load(std::memory_order_relaxed)) { // add write_flag to read-set. 122 abort_transaction(); // writer grabbed the lock, so abort. 123 } 124 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader; 125 // Don not wrap the following assignment to a function, 126 // because it can abort the transaction in debug. Need mutex for release(). 127 s.m_mutex = &m; 128 return; // successfully started speculation 129 } 130 // fallback path 131 // retry only if there is any hope of getting into a transaction soon 132 // Retry in the following cases (from Section 8.3.5 of 133 // Intel(R) Architecture Instruction Set Extensions Programming Reference): 134 // 1. abort caused by XABORT instruction (bit 0 of EAX register is set) 135 // 2. the transaction may succeed on a retry (bit 1 of EAX register is set) 136 // 3. if another logical processor conflicted with a memory address 137 // that was part of the transaction that aborted (bit 2 of EAX register is set) 138 // That is, retry if (abort_code & 0x7) is non-zero 139 ++num_retries; 140 } while((abort_code & speculation_retry) != 0 && (num_retries < retry_threshold_read)); 141 } 142 143 if(only_speculate) return; 144 s.m_mutex = &m; 145 s.m_mutex->lock_shared(); 146 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader; 147 } 148 149 //! Upgrade reader to become a writer. 150 /** Returns whether the upgrade happened without releasing and re-acquiring the lock */ 151 static bool upgrade(d1::rtm_rw_mutex::scoped_lock& s) { 152 switch(s.m_transaction_state) { 153 case d1::rtm_rw_mutex::rtm_type::rtm_real_reader: { 154 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_writer; 155 bool no_release = s.m_mutex->upgrade(); 156 __TBB_ASSERT(!s.m_mutex->write_flag.load(std::memory_order_relaxed), "After upgrade, write_flag already true"); 157 s.m_mutex->write_flag.store(true, std::memory_order_relaxed); 158 return no_release; 159 } 160 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader: { 161 d1::rtm_rw_mutex& m = *s.m_mutex; 162 if(m.m_state.load(std::memory_order_acquire)) { // add spin_rw_mutex to read-set. 163 // Real reader or writer holds the lock; so commit the read and re-acquire for write. 164 release(s); 165 acquire_writer(m, s, false); 166 return false; 167 } else 168 { 169 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer; 170 return true; 171 } 172 } 173 default: 174 __TBB_ASSERT(false, "Invalid state for upgrade"); 175 return false; 176 } 177 } 178 179 //! Downgrade writer to a reader. 180 static bool downgrade(d1::rtm_rw_mutex::scoped_lock& s) { 181 switch (s.m_transaction_state) { 182 case d1::rtm_rw_mutex::rtm_type::rtm_real_writer: 183 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader; 184 __TBB_ASSERT(s.m_mutex->write_flag.load(std::memory_order_relaxed), "Before downgrade write_flag not true"); 185 s.m_mutex->write_flag.store(false, std::memory_order_relaxed); 186 s.m_mutex->downgrade(); 187 return true; 188 case d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer: 189 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader; 190 return true; 191 default: 192 __TBB_ASSERT(false, "Invalid state for downgrade"); 193 return false; 194 } 195 } 196 197 //! Try to acquire write lock on the given mutex. 198 // There may be reader(s) which acquired the spin_rw_mutex, as well as possibly 199 // transactional reader(s). If this is the case, the acquire will fail, and assigning 200 // write_flag will kill the transactors. So we only assign write_flag if we have successfully 201 // acquired the lock. 202 static bool try_acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) { 203 acquire_writer(m, s, /*only_speculate=*/true); 204 if (s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_transacting_writer) { 205 return true; 206 } 207 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, nullptr); 208 // transacting write acquire failed. try_lock the real mutex 209 if (m.try_lock()) { 210 s.m_mutex = &m; 211 // only shoot down readers if we're not transacting ourselves 212 __TBB_ASSERT(!m.write_flag.load(std::memory_order_relaxed), "After try_acquire_writer, write_flag already true"); 213 m.write_flag.store(true, std::memory_order_relaxed); 214 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_writer; 215 return true; 216 } 217 return false; 218 } 219 220 //! Try to acquire read lock on the given mutex. 221 static bool try_acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) { 222 // speculatively acquire the lock. If this fails, do try_lock_shared on the spin_rw_mutex. 223 acquire_reader(m, s, /*only_speculate=*/true); 224 if (s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_transacting_reader) { 225 return true; 226 } 227 __TBB_ASSERT(s.m_transaction_state == d1::rtm_rw_mutex::rtm_type::rtm_not_in_mutex, nullptr); 228 // transacting read acquire failed. try_lock_shared the real mutex 229 if (m.try_lock_shared()) { 230 s.m_mutex = &m; 231 s.m_transaction_state = d1::rtm_rw_mutex::rtm_type::rtm_real_reader; 232 return true; 233 } 234 return false; 235 } 236 }; 237 238 void __TBB_EXPORTED_FUNC acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) { 239 rtm_rw_mutex_impl::acquire_writer(m, s, only_speculate); 240 } 241 //! Internal acquire read lock. 242 // only_speculate == true if we're doing a try_lock, else false. 243 void __TBB_EXPORTED_FUNC acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s, bool only_speculate) { 244 rtm_rw_mutex_impl::acquire_reader(m, s, only_speculate); 245 } 246 //! Internal upgrade reader to become a writer. 247 bool __TBB_EXPORTED_FUNC upgrade(d1::rtm_rw_mutex::scoped_lock& s) { 248 return rtm_rw_mutex_impl::upgrade(s); 249 } 250 //! Internal downgrade writer to become a reader. 251 bool __TBB_EXPORTED_FUNC downgrade(d1::rtm_rw_mutex::scoped_lock& s) { 252 return rtm_rw_mutex_impl::downgrade(s); 253 } 254 //! Internal try_acquire write lock. 255 bool __TBB_EXPORTED_FUNC try_acquire_writer(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) { 256 return rtm_rw_mutex_impl::try_acquire_writer(m, s); 257 } 258 //! Internal try_acquire read lock. 259 bool __TBB_EXPORTED_FUNC try_acquire_reader(d1::rtm_rw_mutex& m, d1::rtm_rw_mutex::scoped_lock& s) { 260 return rtm_rw_mutex_impl::try_acquire_reader(m, s); 261 } 262 //! Internal release lock. 263 void __TBB_EXPORTED_FUNC release(d1::rtm_rw_mutex::scoped_lock& s) { 264 rtm_rw_mutex_impl::release(s); 265 } 266 267 } // namespace r1 268 } // namespace detail 269 } // namespace tbb 270 271 272