1 /***************************************************************************** 2 3 Copyright (c) 2020, Oracle and/or its affiliates. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify it under 6 the terms of the GNU General Public License, version 2.0, as published by the 7 Free Software Foundation. 8 9 This program is also distributed with certain software (including but not 10 limited to OpenSSL) that is licensed under separate terms, as designated in a 11 particular file or component or in included license documentation. The authors 12 of MySQL hereby grant you an additional permission to link the program and 13 your derivative works with the separately licensed software that they have 14 included with MySQL. 15 16 This program is distributed in the hope that it will be useful, but WITHOUT 17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 18 FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0, 19 for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 24 25 *****************************************************************************/ 26 #ifndef lock0latches_h 27 #define lock0latches_h 28 29 #include "sync0sharded_rw.h" 30 #include "ut0cpu_cache.h" 31 #include "ut0mutex.h" 32 33 /* Forward declarations */ 34 struct dict_table_t; 35 class page_id_t; 36 37 namespace locksys { 38 /** 39 The class which handles the logic of latching of lock_sys queues themselves. 40 The lock requests for table locks and record locks are stored in queues, and to 41 allow concurrent operations on these queues, we need a mechanism to latch these 42 queues in safe and quick fashion. 43 In the past we had a single latch which protected access to all of them. 44 Now, we use more granular approach. 45 In extreme, one could imagine protecting each queue with a separate latch. 46 To avoid having too many latch objects, and having to create and remove them on 47 demand, we use a more conservative approach. 48 The queues are grouped into a fixed number of shards, and each shard is 49 protected by its own mutex. 50 51 However, there are several rare events in which we need to "stop the world" - 52 latch all queues, to prevent any activity inside lock-sys. 53 One way to accomplish this would be to simply latch all the shards one by one, 54 but it turns out to be way too slow in debug runs, where such "stop the world" 55 events are very frequent due to lock_sys validation. 56 57 To allow for efficient latching of everything, we've introduced a global_latch, 58 which is a read-write latch. 59 Most of the time, we operate on one or two shards, in which case it is 60 sufficient to s-latch the global_latch and then latch shard's mutex. 61 For the "stop the world" operations, we x-latch the global_latch, which prevents 62 any other thread from latching any shard. 63 64 However, it turned out that on ARM architecture, the default implementation of 65 read-write latch (rw_lock_t) is too slow because increments and decrements of 66 the number of s-latchers is implemented as read-update-try-to-write loop, which 67 means multiple threads try to modify the same cache line disrupting each other. 68 Therefore, we use a sharded version of read-write latch (Sharded_rw_lock), which 69 internally uses multiple instances of rw_lock_t, spreading the load over several 70 cache lines. Note that this sharding is a technical internal detail of the 71 global_latch, which for all other purposes can be treated as a single entity. 72 73 This his how this conceptually looks like: 74 ``` 75 [ global latch ] 76 | 77 v 78 [table shard 1] ... [table shard 512] [page shard 1] ... [page shard 512] 79 80 ``` 81 82 So, for example access two queues for two records involves following steps: 83 1. s-latch the global_latch 84 2. identify the 2 pages to which the records belong 85 3. identify the lock_sys 2 hash buckets which contain the queues for given pages 86 4. identify the 2 shard ids which contain these two buckets 87 5. latch mutexes for the two shards in the order of their addresses 88 89 All of the steps above (except 2, as we usually know the page already) are 90 accomplished with the help of single line: 91 92 locksys::Shard_latches_guard guard{*block_a, *block_b}; 93 94 And to "stop the world" one can simply x-latch the global latch by using: 95 96 locksys::Global_exclusive_latch_guard guard{}; 97 98 This class does not expose too many public functions, as the intention is to 99 rather use friend guard classes, like the Shard_latches_guard demonstrated. 100 */ 101 class Latches { 102 private: 103 using Lock_mutex = ib_mutex_t; 104 105 /** A helper wrapper around Shared_rw_lock which simplifies: 106 - lifecycle by providing constructor and destructor, and 107 - s-latching and s-unlatching by keeping track of the shard id used for 108 spreading the contention. 109 There must be at most one instance of this class (the one in the lock_sys), as 110 it uses thread_local-s to remember which shard of sharded rw lock was used by 111 this thread to perform s-latching (so, hypothetical other instances would 112 share this field, overwriting it and leading to errors). */ 113 class Unique_sharded_rw_lock { 114 /** The actual rw_lock implementation doing the heavy lifting */ 115 Sharded_rw_lock rw_lock; 116 117 /** The value used for m_shard_id to indicate that current thread did not 118 s-latch any of the rw_lock's shards */ 119 static constexpr size_t NOT_IN_USE = std::numeric_limits<size_t>::max(); 120 121 /** The id of the rw_lock's shard which this thread has s-latched, or 122 NOT_IN_USE if it has not s-latched any*/ 123 static thread_local size_t m_shard_id; 124 125 public: 126 Unique_sharded_rw_lock(); 127 ~Unique_sharded_rw_lock(); try_x_lock()128 bool try_x_lock() { return rw_lock.try_x_lock(); } x_lock()129 void x_lock() { rw_lock.x_lock(); } x_unlock()130 void x_unlock() { rw_lock.x_unlock(); } s_lock()131 void s_lock() { 132 ut_ad(m_shard_id == NOT_IN_USE); 133 m_shard_id = rw_lock.s_lock(); 134 } s_unlock()135 void s_unlock() { 136 ut_ad(m_shard_id != NOT_IN_USE); 137 rw_lock.s_unlock(m_shard_id); 138 m_shard_id = NOT_IN_USE; 139 } 140 #ifdef UNIV_DEBUG x_own()141 bool x_own() const { return rw_lock.x_own(); } s_own()142 bool s_own() const { 143 return m_shard_id != NOT_IN_USE && rw_lock.s_own(m_shard_id); 144 } 145 #endif 146 }; 147 148 using Padded_mutex = ut::Cacheline_padded<Lock_mutex>; 149 150 /** Number of page shards, and also number of table shards. 151 Must be a power of two */ 152 static constexpr size_t SHARDS_COUNT = 512; 153 154 /* 155 Functions related to sharding by page (containing records to lock). 156 157 This must be done in such a way that two pages which share a single lock 158 queue fall into the same shard. We accomplish this by reusing hash function 159 used to determine lock queue, and then group multiple queues into single 160 shard. 161 */ 162 class Page_shards { 163 /** Each shard is protected by a separate mutex. Mutexes are padded to avoid 164 false sharing issues with cache. */ 165 Padded_mutex mutexes[SHARDS_COUNT]; 166 /** 167 Identifies the page shard which contains record locks for records from the 168 given page. 169 @param[in] page_id The space_id and page_no of the page 170 @return Integer in the range [0..lock_sys_t::SHARDS_COUNT) 171 */ 172 static size_t get_shard(const page_id_t &page_id); 173 174 public: 175 Page_shards(); 176 ~Page_shards(); 177 178 /** 179 Returns the mutex which (together with the global latch) protects the page 180 shard which contains record locks for records from the given page. 181 @param[in] page_id The space_id and page_no of the page 182 @return The mutex responsible for the shard containing the page 183 */ 184 const Lock_mutex &get_mutex(const page_id_t &page_id) const; 185 186 /** 187 Returns the mutex which (together with the global latch) protects the page 188 shard which contains record locks for records from the given page. 189 @param[in] page_id The space_id and page_no of the page 190 @return The mutex responsible for the shard containing the page 191 */ 192 Lock_mutex &get_mutex(const page_id_t &page_id); 193 }; 194 195 /* 196 Functions related to sharding by table 197 198 We identify tables by their id. Each table has its own lock queue, so we 199 simply group several such queues into single shard. 200 */ 201 class Table_shards { 202 /** Each shard is protected by a separate mutex. Mutexes are padded to avoid 203 false sharing issues with cache. */ 204 Padded_mutex mutexes[SHARDS_COUNT]; 205 /** 206 Identifies the table shard which contains locks for the given table. 207 @param[in] table The table 208 @return Integer in the range [0..lock_sys_t::SHARDS_COUNT) 209 */ 210 static size_t get_shard(const dict_table_t &table); 211 212 public: 213 Table_shards(); 214 ~Table_shards(); 215 216 /** Returns the mutex which (together with the global latch) protects the 217 table shard which contains table locks for the given table. 218 @param[in] table The table 219 @return The mutex responsible for the shard containing the table 220 */ 221 Lock_mutex &get_mutex(const dict_table_t &table); 222 223 /** Returns the mutex which (together with the global latch) protects the 224 table shard which contains table locks for the given table. 225 @param[in] table The table 226 @return The mutex responsible for the shard containing the table 227 */ 228 const Lock_mutex &get_mutex(const dict_table_t &table) const; 229 }; 230 231 /** padding to prevent other memory update hotspots from residing on the same 232 memory cache line */ 233 char pad1[ut::INNODB_CACHE_LINE_SIZE] = {}; 234 235 Unique_sharded_rw_lock global_latch; 236 237 Page_shards page_shards; 238 239 Table_shards table_shards; 240 241 public: 242 /* You should use following RAII guards to modify the state of Latches. */ 243 friend class Global_exclusive_latch_guard; 244 friend class Global_exclusive_try_latch; 245 friend class Global_shared_latch_guard; 246 friend class Shard_naked_latch_guard; 247 friend class Shard_naked_latches_guard; 248 249 /** You should not use this functionality in new code. 250 Instead use Global_exclusive_latch_guard. 251 This is intended only to be use within lock0* module, thus this class is only 252 accessible through lock0priv.h. 253 It is only used by lock_rec_fetch_page() as a workaround. */ 254 friend class Unsafe_global_latch_manipulator; 255 256 /** For some reason clang 6.0.0 and 7.0.0 (but not 8.0.0) fail at linking 257 stage if we completely omit the destructor declaration, or use 258 259 ~Latches() = default; 260 261 This might be somehow connected to one of these: 262 https://bugs.llvm.org/show_bug.cgi?id=28280 263 https://github.com/android/ndk/issues/143 264 https://reviews.llvm.org/D45898 265 So, this declaration is just to make clang 6.0.0 and 7.0.0 happy. 266 */ ~Latches()267 ~Latches() {} 268 269 #ifdef UNIV_DEBUG 270 /** 271 Tests if lock_sys latch is exclusively owned by the current thread. 272 @return true iff the current thread owns exclusive global lock_sys latch 273 */ owns_exclusive_global_latch()274 bool owns_exclusive_global_latch() const { return global_latch.x_own(); } 275 276 /** 277 Tests if lock_sys latch is owned in shared mode by the current thread. 278 @return true iff the current thread owns shared global lock_sys latch 279 */ owns_shared_global_latch()280 bool owns_shared_global_latch() const { return global_latch.s_own(); } 281 282 /** 283 Tests if given page shard can be safely accessed by the current thread. 284 @param[in] page_id The space_id and page_no of the page 285 @return true iff the current thread owns exclusive global lock_sys latch or 286 both a shared global lock_sys latch and mutex protecting the page shard 287 */ owns_page_shard(const page_id_t & page_id)288 bool owns_page_shard(const page_id_t &page_id) const { 289 return owns_exclusive_global_latch() || 290 (page_shards.get_mutex(page_id).is_owned() && 291 owns_shared_global_latch()); 292 } 293 294 /** 295 Tests if given table shard can be safely accessed by the current thread. 296 @param table the table 297 @return true iff the current thread owns exclusive global lock_sys latch or 298 both a shared global lock_sys latch and mutex protecting the table shard 299 */ owns_table_shard(const dict_table_t & table)300 bool owns_table_shard(const dict_table_t &table) const { 301 return owns_exclusive_global_latch() || 302 (table_shards.get_mutex(table).is_owned() && 303 owns_shared_global_latch()); 304 } 305 #endif /* UNIV_DEBUG */ 306 }; 307 } // namespace locksys 308 309 #endif /* lock0latches_h */ 310