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