/* Copyright (c) 2011, 2021, Oracle and/or its affiliates. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License, version 2.0, as published by the Free Software Foundation. This program is also distributed with certain software (including but not limited to OpenSSL) that is licensed under separate terms, as designated in a particular file or component or in included license documentation. The authors of MySQL hereby grant you an additional permission to link the program and your derivative works with the separately licensed software that they have included with MySQL. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0, for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef NDB_CONFLICT_TRANS_H #define NDB_CONFLICT_TRANS_H #include #ifdef HAVE_NDB_BINLOG #include #include #include /* This file defines structures for detecting dependencies between transactions based on the rows they update. It is used when applying row updates as part of the MySQLD slave. */ /** * st_row_event_key_info * * This struct describes a row event applied by the Slave, based * on its table, key and transaction id. * Instances of this struct are placed in a hash structure where * the {table, key} are the key, and the transaction id is the * 'data'. * This hash is used to detect when different transactions in an * epoch affect the same row, which implies a dependency between * the transactions. */ class st_row_event_key_info { public: /** * User api */ st_row_event_key_info(const NdbDictionary::Table* _table, const uchar* _key_buff, Uint32 _key_buff_len, Uint64 _transaction_id); Uint64 getTransactionId() const; void updateRowTransactionId(Uint64 mostRecentTransId); /** * Hash Api */ Uint32 hashValue() const; bool equal(const st_row_event_key_info* other) const; st_row_event_key_info* getNext() const; void setNext(st_row_event_key_info* _next); private: /* Key : Table and Primary Key */ const NdbDictionary::Table* tableObj; const uchar* packed_key; Uint32 packed_key_len; /* Data : Transaction id */ Uint64 transaction_id; /* Next ptr for hash */ st_row_event_key_info* hash_next; }; class st_transaction; /** st_trans_dependency Entry in dependency hash. Describes inter-transaction dependency, and comprises part of list of other dependents of target_transaction */ class st_trans_dependency { public: /* User Api */ st_trans_dependency(st_transaction* _target_transaction, st_transaction* _dependent_transaction, const st_trans_dependency* _next); st_transaction* getTargetTransaction() const; st_transaction* getDependentTransaction() const; const st_trans_dependency* getNextDependency() const; /* Hash Api */ Uint32 hashValue() const; bool equal(const st_trans_dependency* other) const; st_trans_dependency* getNext() const; void setNext(st_trans_dependency* _next); private: /* Key */ st_transaction* target_transaction; st_transaction* dependent_transaction; /* Rest of co-dependents of target_transaction */ const st_trans_dependency* next_entry; st_trans_dependency* hash_next; }; /** st_transaction Entry in transaction hash, indicates whether transaction is in conflict, and has list of dependents */ class st_transaction { public: /* User Api */ st_transaction(Uint64 _transaction_id); Uint64 getTransactionId() const; bool getInConflict() const; void setInConflict(); const st_trans_dependency* getDependencyListHead() const; void setDependencyListHead(st_trans_dependency* head); /* Hash Api */ Uint32 hashValue() const; bool equal(const st_transaction* other) const; st_transaction* getNext() const; void setNext(st_transaction* _next); private: /* Key */ Uint64 transaction_id; /* Data */ /* Is this transaction (and therefore its dependents) in conflict? */ bool in_conflict; /* Head of list of dependencies */ st_trans_dependency* dependency_list_head; /* Hash ptr */ st_transaction* hash_next; }; typedef struct st_mem_root MEM_ROOT; /** * Allocator type which internally uses a MySQLD mem_root * Used as a template parameter for Ndb ADTs */ struct st_mem_root_allocator { MEM_ROOT* mem_root; static void* alloc(void* ctx, size_t bytes); static void* mem_calloc(void* ctx, size_t nelem, size_t bytes); static void mem_free(void* ctx, void* mem); st_mem_root_allocator(MEM_ROOT* _mem_root); }; class DependencyTracker { public: static const Uint64 InvalidTransactionId = ~Uint64(0); /** newDependencyTracker Factory method to get a DependencyTracker object, using memory from the passed mem_root. To discard dependency tracker, just free the passed mem_root. */ static DependencyTracker* newDependencyTracker(MEM_ROOT* mem_root); /** track_operation This method records the operation on the passed table + primary key as belonging to the passed transaction. If there is already a recorded operation on the passed table + primary key from a different transaction then a transaction dependency is recorded. */ int track_operation(const NdbDictionary::Table* table, const NdbRecord* key_rec, const uchar* row, Uint64 transaction_id); /** mark_conflict Record that a particular transaction is in conflict. This will also mark any dependent transactions as in conflict. */ int mark_conflict(Uint64 trans_id); /** in_conflict Returns true if the supplied transaction_id is marked as in conflict */ bool in_conflict(Uint64 trans_id); /** get_error_text Returns string containing error description. NULL if no error. */ const char* get_error_text() const; /** get_conflict_count Returns number of transactions marked as in-conflict */ Uint32 get_conflict_count() const; private: DependencyTracker(MEM_ROOT* mem_root); /** get_or_create_transaction Get or create the transaction object for the given transaction id. Returns Null on allocation failure. */ st_transaction* get_or_create_transaction(Uint64 trans_id); /** add_dependency This method records a dependency between the two passed transaction ids */ int add_dependency(Uint64 trans_id, Uint64 dependent_trans_id); /** reset_dependency_iterator Reset dependency iterator. Required before using get_next_dependency() */ void reset_dependency_iterator(); /** get_next_dependency Gets next dependency in dependency graph. Performs breadth first search from start node. include_dependents_of_current = false causes the traversal to skip dependents of the current node. */ st_transaction* get_next_dependency(const st_transaction* current, bool include_dependents_of_current = true); /** dump_dependents Debugging function */ void dump_dependents(Uint64 trans_id); /** verify_graph Internal invariant checking function. */ bool verify_graph(); /* MemRoot allocator class instance */ st_mem_root_allocator mra; /* key_hash Map of {Table, PK} -> TransID Used to find inter-transaction dependencies Attempt to add duplicate entry to the key_hash indicates transaction dependency from existing entry to duplicate. */ HashMap2 key_hash; /* trans_hash Map of {TransId} -> {in_conflict, List of dependents} Used to record which transactions are in-conflict, and what their dependencies are. Transactions not marked in-conflict, and with no dependencies or dependents, are not placed in this hash. */ HashMap2 trans_hash; /* dependency_hash Map of {TransIdFrom, TransIdTo} Used to ensure dependencies are added only once, for efficiency. Elements are linked from the trans_hash entry for TransIdFrom. */ HashMap2 dependency_hash; /* iteratorTodo Stack of transaction Ids to be visited during breadth first search when marking dependents as in conflict. */ static const Uint32 ITERATOR_STACK_BLOCKSIZE = 10; LinkedStack iteratorTodo; Uint32 conflicting_trans_count; const char* error_text; }; /* ifdef HAVE_NDB_BINLOG */ #endif // #ifndef NDB_CONFLICT_TRANS_H #endif