1 /* 2 Copyright (c) 2011, 2021, Oracle and/or its affiliates. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License, version 2.0, 6 as published by the Free Software Foundation. 7 8 This program is also distributed with certain software (including 9 but not limited to OpenSSL) that is licensed under separate terms, 10 as designated in a particular file or component or in included license 11 documentation. The authors of MySQL hereby grant you an additional 12 permission to link the program and your derivative works with the 13 separately licensed software that they have included with MySQL. 14 15 This program is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License, version 2.0, for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with this program; if not, write to the Free Software 22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 23 */ 24 25 #ifndef NDB_CONFLICT_TRANS_H 26 #define NDB_CONFLICT_TRANS_H 27 28 #include <my_global.h> 29 30 #ifdef HAVE_NDB_BINLOG 31 #include <ndbapi/NdbApi.hpp> 32 #include <util/HashMap2.hpp> 33 #include <util/LinkedStack.hpp> 34 35 /* 36 This file defines structures for detecting dependencies between 37 transactions based on the rows they update. 38 It is used when applying row updates as part of the MySQLD slave. 39 */ 40 41 /** 42 * st_row_event_key_info 43 * 44 * This struct describes a row event applied by the Slave, based 45 * on its table, key and transaction id. 46 * Instances of this struct are placed in a hash structure where 47 * the {table, key} are the key, and the transaction id is the 48 * 'data'. 49 * This hash is used to detect when different transactions in an 50 * epoch affect the same row, which implies a dependency between 51 * the transactions. 52 */ 53 class st_row_event_key_info 54 { 55 public: 56 /** 57 * User api 58 */ 59 st_row_event_key_info(const NdbDictionary::Table* _table, 60 const uchar* _key_buff, 61 Uint32 _key_buff_len, 62 Uint64 _transaction_id); 63 Uint64 getTransactionId() const; 64 void updateRowTransactionId(Uint64 mostRecentTransId); 65 66 /** 67 * Hash Api 68 */ 69 Uint32 hashValue() const; 70 bool equal(const st_row_event_key_info* other) const; 71 st_row_event_key_info* getNext() const; 72 void setNext(st_row_event_key_info* _next); 73 74 private: 75 /* Key : Table and Primary Key */ 76 const NdbDictionary::Table* tableObj; 77 const uchar* packed_key; 78 Uint32 packed_key_len; 79 80 /* Data : Transaction id */ 81 Uint64 transaction_id; 82 83 /* Next ptr for hash */ 84 st_row_event_key_info* hash_next; 85 }; 86 87 88 class st_transaction; 89 90 /** 91 st_trans_dependency 92 Entry in dependency hash. 93 Describes inter-transaction dependency, and comprises part 94 of list of other dependents of target_transaction 95 */ 96 class st_trans_dependency 97 { 98 public: 99 /* User Api */ 100 st_trans_dependency(st_transaction* _target_transaction, 101 st_transaction* _dependent_transaction, 102 const st_trans_dependency* _next); 103 104 st_transaction* getTargetTransaction() const; 105 st_transaction* getDependentTransaction() const; 106 const st_trans_dependency* getNextDependency() const; 107 108 109 /* Hash Api */ 110 Uint32 hashValue() const; 111 bool equal(const st_trans_dependency* other) const; 112 st_trans_dependency* getNext() const; 113 void setNext(st_trans_dependency* _next); 114 115 private: 116 /* Key */ 117 st_transaction* target_transaction; 118 st_transaction* dependent_transaction; 119 120 /* Rest of co-dependents of target_transaction */ 121 const st_trans_dependency* next_entry; 122 123 st_trans_dependency* hash_next; 124 }; 125 126 127 128 /** 129 st_transaction 130 Entry in transaction hash, indicates whether transaction 131 is in conflict, and has list of dependents 132 */ 133 class st_transaction 134 { 135 public: 136 /* User Api */ 137 st_transaction(Uint64 _transaction_id); 138 139 Uint64 getTransactionId() const; 140 bool getInConflict() const; 141 void setInConflict(); 142 const st_trans_dependency* getDependencyListHead() const; 143 void setDependencyListHead(st_trans_dependency* head); 144 145 /* Hash Api */ 146 Uint32 hashValue() const; 147 bool equal(const st_transaction* other) const; 148 st_transaction* getNext() const; 149 void setNext(st_transaction* _next); 150 151 private: 152 /* Key */ 153 Uint64 transaction_id; 154 155 /* Data */ 156 /* Is this transaction (and therefore its dependents) in conflict? */ 157 bool in_conflict; 158 /* Head of list of dependencies */ 159 st_trans_dependency* dependency_list_head; 160 161 /* Hash ptr */ 162 st_transaction* hash_next; 163 }; 164 165 typedef struct st_mem_root MEM_ROOT; 166 167 /** 168 * Allocator type which internally uses a MySQLD mem_root 169 * Used as a template parameter for Ndb ADTs 170 */ 171 struct st_mem_root_allocator 172 { 173 MEM_ROOT* mem_root; 174 175 static void* alloc(void* ctx, size_t bytes); 176 static void* mem_calloc(void* ctx, size_t nelem, size_t bytes); 177 static void mem_free(void* ctx, void* mem); 178 st_mem_root_allocator(MEM_ROOT* _mem_root); 179 }; 180 181 182 class DependencyTracker 183 { 184 public: 185 static const Uint64 InvalidTransactionId = ~Uint64(0); 186 187 /** 188 newDependencyTracker 189 190 Factory method to get a DependencyTracker object, using 191 memory from the passed mem_root. 192 To discard dependency tracker, just free the passed mem_root. 193 */ 194 static DependencyTracker* newDependencyTracker(MEM_ROOT* mem_root); 195 196 /** 197 track_operation 198 199 This method records the operation on the passed 200 table + primary key as belonging to the passed 201 transaction. 202 203 If there is already a recorded operation on the 204 passed table + primary key from a different transaction 205 then a transaction dependency is recorded. 206 */ 207 int track_operation(const NdbDictionary::Table* table, 208 const NdbRecord* key_rec, 209 const uchar* row, 210 Uint64 transaction_id); 211 212 /** 213 mark_conflict 214 215 Record that a particular transaction is in conflict. 216 This will also mark any dependent transactions as in 217 conflict. 218 */ 219 int mark_conflict(Uint64 trans_id); 220 221 /** 222 in_conflict 223 224 Returns true if the supplied transaction_id is marked as 225 in conflict 226 */ 227 bool in_conflict(Uint64 trans_id); 228 229 /** 230 get_error_text 231 232 Returns string containing error description. 233 NULL if no error. 234 */ 235 const char* get_error_text() const; 236 237 /** 238 get_conflict_count 239 240 Returns number of transactions marked as in-conflict 241 */ 242 Uint32 get_conflict_count() const; 243 244 private: 245 DependencyTracker(MEM_ROOT* mem_root); 246 247 /** 248 get_or_create_transaction 249 250 Get or create the transaction object for the 251 given transaction id. 252 Returns Null on allocation failure. 253 */ 254 st_transaction* get_or_create_transaction(Uint64 trans_id); 255 256 /** 257 add_dependency 258 259 This method records a dependency between the two 260 passed transaction ids 261 */ 262 int add_dependency(Uint64 trans_id, Uint64 dependent_trans_id); 263 264 /** 265 reset_dependency_iterator 266 267 Reset dependency iterator. 268 Required before using get_next_dependency() 269 */ 270 void reset_dependency_iterator(); 271 272 /** 273 get_next_dependency 274 Gets next dependency in dependency graph. 275 Performs breadth first search from start node. 276 277 include_dependents_of_current = false causes the traversal to skip 278 dependents of the current node. 279 */ 280 st_transaction* get_next_dependency(const st_transaction* current, 281 bool include_dependents_of_current = true); 282 283 /** 284 dump_dependents 285 286 Debugging function 287 */ 288 void dump_dependents(Uint64 trans_id); 289 290 /** 291 verify_graph 292 293 Internal invariant checking function. 294 */ 295 bool verify_graph(); 296 297 /* MemRoot allocator class instance */ 298 st_mem_root_allocator mra; 299 300 /* 301 key_hash 302 Map of {Table, PK} -> TransID 303 Used to find inter-transaction dependencies 304 Attempt to add duplicate entry to the key_hash indicates 305 transaction dependency from existing entry to duplicate. 306 */ 307 HashMap2<st_row_event_key_info, true, st_mem_root_allocator> key_hash; 308 309 /* 310 trans_hash 311 Map of {TransId} -> {in_conflict, List of dependents} 312 Used to record which transactions are in-conflict, and what 313 their dependencies are. 314 Transactions not marked in-conflict, and with no dependencies or 315 dependents, are not placed in this hash. 316 */ 317 HashMap2<st_transaction, true, st_mem_root_allocator> trans_hash; 318 319 /* 320 dependency_hash 321 Map of {TransIdFrom, TransIdTo} 322 Used to ensure dependencies are added only once, for efficiency. 323 Elements are linked from the trans_hash entry for TransIdFrom. 324 */ 325 HashMap2<st_trans_dependency, true, st_mem_root_allocator> dependency_hash; 326 327 /* 328 iteratorTodo 329 Stack of transaction Ids to be visited during breadth first search 330 when marking dependents as in conflict. 331 */ 332 static const Uint32 ITERATOR_STACK_BLOCKSIZE = 10; 333 LinkedStack<Uint64, st_mem_root_allocator> iteratorTodo; 334 335 Uint32 conflicting_trans_count; 336 337 const char* error_text; 338 }; 339 340 /* ifdef HAVE_NDB_BINLOG */ 341 #endif 342 343 // #ifndef NDB_CONFLICT_TRANS_H 344 #endif 345