diff options
Diffstat (limited to 'storage/innobase/ut')
| -rw-r--r-- | storage/innobase/ut/ut0dbg.cc | 61 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0list.cc | 151 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0mem.cc | 54 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0new.cc | 112 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0rbt.cc | 1140 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0rnd.cc | 93 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0ut.cc | 648 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0vec.cc | 73 | ||||
| -rw-r--r-- | storage/innobase/ut/ut0wqueue.cc | 133 |
9 files changed, 2465 insertions, 0 deletions
diff --git a/storage/innobase/ut/ut0dbg.cc b/storage/innobase/ut/ut0dbg.cc new file mode 100644 index 00000000..fc51cce9 --- /dev/null +++ b/storage/innobase/ut/ut0dbg.cc @@ -0,0 +1,61 @@ +/***************************************************************************** + +Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2017, 2018, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/*****************************************************************//** +@file ut/ut0dbg.cc +Debug utilities for Innobase. + +Created 1/30/1994 Heikki Tuuri +**********************************************************************/ + +#include "univ.i" +#include "ut0dbg.h" + +/*************************************************************//** +Report a failed assertion. */ +ATTRIBUTE_NORETURN +void +ut_dbg_assertion_failed( +/*====================*/ + const char* expr, /*!< in: the failed assertion (optional) */ + const char* file, /*!< in: source file containing the assertion */ + unsigned line) /*!< in: line number of the assertion */ +{ + ut_print_timestamp(stderr); + fprintf(stderr, " InnoDB: Assertion failure in file %s line %u\n", + file, line); + if (expr) { + fprintf(stderr, + "InnoDB: Failing assertion: %s\n", expr); + } + + fputs("InnoDB: We intentionally generate a memory trap.\n" + "InnoDB: Submit a detailed bug report" + " to https://jira.mariadb.org/\n" + "InnoDB: If you get repeated assertion failures" + " or crashes, even\n" + "InnoDB: immediately after the mysqld startup, there may be\n" + "InnoDB: corruption in the InnoDB tablespace. Please refer to\n" + "InnoDB: https://mariadb.com/kb/en/library/innodb-recovery-modes/\n" + "InnoDB: about forcing recovery.\n", stderr); + + fflush(stderr); + fflush(stdout); + abort(); +} diff --git a/storage/innobase/ut/ut0list.cc b/storage/innobase/ut/ut0list.cc new file mode 100644 index 00000000..370c18d4 --- /dev/null +++ b/storage/innobase/ut/ut0list.cc @@ -0,0 +1,151 @@ +/***************************************************************************** + +Copyright (c) 2006, 2016, Oracle and/or its affiliates. All Rights Reserved. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/*******************************************************************//** +@file ut/ut0list.cc +A double-linked list + +Created 4/26/2006 Osku Salerma +************************************************************************/ + +#include "ut0list.h" + +/****************************************************************//** +Create a new list. +@return list */ +ib_list_t* +ib_list_create(void) +/*=================*/ +{ + return(static_cast<ib_list_t*>(ut_zalloc_nokey(sizeof(ib_list_t)))); +} + +/****************************************************************//** +Free a list. */ +void +ib_list_free( +/*=========*/ + ib_list_t* list) /*!< in: list */ +{ + /* We don't check that the list is empty because it's entirely valid + to e.g. have all the nodes allocated from a single heap that is then + freed after the list itself is freed. */ + + ut_free(list); +} + +/****************************************************************//** +Add the data after the indicated node. +@return new list node */ +static +ib_list_node_t* +ib_list_add_after( +/*==============*/ + ib_list_t* list, /*!< in: list */ + ib_list_node_t* prev_node, /*!< in: node preceding new node (can + be NULL) */ + void* data, /*!< in: data */ + mem_heap_t* heap) /*!< in: memory heap to use */ +{ + ib_list_node_t* node; + + node = static_cast<ib_list_node_t*>( + mem_heap_alloc(heap, sizeof(*node))); + + node->data = data; + + if (!list->first) { + /* Empty list. */ + + ut_a(!prev_node); + + node->prev = NULL; + node->next = NULL; + + list->first = node; + list->last = node; + } else if (!prev_node) { + /* Start of list. */ + + node->prev = NULL; + node->next = list->first; + + list->first->prev = node; + + list->first = node; + } else { + /* Middle or end of list. */ + + node->prev = prev_node; + node->next = prev_node->next; + + prev_node->next = node; + + if (node->next) { + node->next->prev = node; + } else { + list->last = node; + } + } + + return(node); +} + +/****************************************************************//** +Add the data to the end of the list. +@return new list node */ +ib_list_node_t* +ib_list_add_last( +/*=============*/ + ib_list_t* list, /*!< in: list */ + void* data, /*!< in: data */ + mem_heap_t* heap) /*!< in: memory heap to use */ +{ + return(ib_list_add_after(list, ib_list_get_last(list), data, heap)); +} + +/****************************************************************//** +Remove the node from the list. */ +void +ib_list_remove( +/*===========*/ + ib_list_t* list, /*!< in: list */ + ib_list_node_t* node) /*!< in: node to remove */ +{ + if (node->prev) { + node->prev->next = node->next; + } else { + /* First item in list. */ + + ut_ad(list->first == node); + + list->first = node->next; + } + + if (node->next) { + node->next->prev = node->prev; + } else { + /* Last item in list. */ + + ut_ad(list->last == node); + + list->last = node->prev; + } + + node->prev = node->next = NULL; +} diff --git a/storage/innobase/ut/ut0mem.cc b/storage/innobase/ut/ut0mem.cc new file mode 100644 index 00000000..faade827 --- /dev/null +++ b/storage/innobase/ut/ut0mem.cc @@ -0,0 +1,54 @@ +/***************************************************************************** + +Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2019, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/********************************************************************//** +@file ut/ut0mem.cc +Memory primitives + +Created 5/11/1994 Heikki Tuuri +*************************************************************************/ + +#include "ut0mem.h" + +/******************************************************************** +Concatenate 3 strings.*/ +char* +ut_str3cat( +/*=======*/ + /* out, own: concatenated string, must be + freed with ut_free() */ + const char* s1, /* in: string 1 */ + const char* s2, /* in: string 2 */ + const char* s3) /* in: string 3 */ +{ + char* s; + ulint s1_len = strlen(s1); + ulint s2_len = strlen(s2); + ulint s3_len = strlen(s3); + + s = static_cast<char*>(ut_malloc_nokey(s1_len + s2_len + s3_len + 1)); + + memcpy(s, s1, s1_len); + memcpy(s + s1_len, s2, s2_len); + memcpy(s + s1_len + s2_len, s3, s3_len); + + s[s1_len + s2_len + s3_len] = '\0'; + + return(s); +} diff --git a/storage/innobase/ut/ut0new.cc b/storage/innobase/ut/ut0new.cc new file mode 100644 index 00000000..5e00a4ca --- /dev/null +++ b/storage/innobase/ut/ut0new.cc @@ -0,0 +1,112 @@ +/***************************************************************************** + +Copyright (c) 2014, 2016, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2019, 2020, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/**************************************************//** +@file ut/ut0new.cc +Instrumented memory allocator. + +Created May 26, 2014 Vasil Dimov +*******************************************************/ + +#include "univ.i" +#include <algorithm> +/** The total amount of memory currently allocated from the operating +system with allocate_large(). */ +Atomic_counter<ulint> os_total_large_mem_allocated; + +/** Maximum number of retries to allocate memory. */ +const size_t alloc_max_retries = 60; + +/** Keys for registering allocations with performance schema. +Keep this list alphabetically sorted. */ +#ifdef BTR_CUR_HASH_ADAPT +PSI_memory_key mem_key_ahi; +#endif /* BTR_CUR_HASH_ADAPT */ +PSI_memory_key mem_key_buf_buf_pool; +PSI_memory_key mem_key_dict_stats_bg_recalc_pool_t; +PSI_memory_key mem_key_dict_stats_index_map_t; +PSI_memory_key mem_key_dict_stats_n_diff_on_level; +PSI_memory_key mem_key_other; +PSI_memory_key mem_key_row_log_buf; +PSI_memory_key mem_key_row_merge_sort; +PSI_memory_key mem_key_std; + +#ifdef UNIV_PFS_MEMORY + +/** Auxiliary array of performance schema 'PSI_memory_info'. +Each allocation appears in +performance_schema.memory_summary_global_by_event_name (and alike) in the form +of e.g. 'memory/innodb/NAME' where the last component NAME is picked from +the list below: +1. If key is specified, then the respective name is used +2. Without a specified key, allocations from inside std::* containers use + mem_key_std +3. Without a specified key, allocations from outside std::* pick up the key + based on the file name, and if file name is not found in the predefined list + (in ut_new_boot()) then mem_key_other is used. +Keep this list alphabetically sorted. */ +static PSI_memory_info pfs_info[] = { +#ifdef BTR_CUR_HASH_ADAPT + {&mem_key_ahi, "adaptive hash index", 0}, +#endif /* BTR_CUR_HASH_ADAPT */ + {&mem_key_buf_buf_pool, "buf_buf_pool", 0}, + {&mem_key_dict_stats_bg_recalc_pool_t, "dict_stats_bg_recalc_pool_t", 0}, + {&mem_key_dict_stats_index_map_t, "dict_stats_index_map_t", 0}, + {&mem_key_dict_stats_n_diff_on_level, "dict_stats_n_diff_on_level", 0}, + {&mem_key_other, "other", 0}, + {&mem_key_row_log_buf, "row_log_buf", 0}, + {&mem_key_row_merge_sort, "row_merge_sort", 0}, + {&mem_key_std, "std", 0}, +}; + +static const int NKEYS = static_cast<int>UT_ARR_SIZE(auto_event_names)-1; +static PSI_memory_key auto_event_keys[NKEYS]; + +/** Setup the internal objects needed for UT_NEW() to operate. +This must be called before the first call to UT_NEW(). */ +void ut_new_boot() +{ + PSI_MEMORY_CALL(register_memory)("innodb", pfs_info, static_cast<int> + UT_ARR_SIZE(pfs_info)); + + PSI_memory_info pfs_info_auto[NKEYS]; + for (int i= 0; i < NKEYS; i++) + { + pfs_info_auto[i]= {&auto_event_keys[i], auto_event_names[i], 0}; + } + + PSI_MEMORY_CALL(register_memory)("innodb", pfs_info_auto,NKEYS); +} + +/** Retrieve a memory key (registered with PFS), corresponding to source file . + +@param[in] autoevent_idx - offset to the auto_event_names corresponding to the +file name of the caller. + +@return registered memory key or PSI_NOT_INSTRUMENTED +*/ +PSI_memory_key ut_new_get_key_by_file(uint32_t autoevent_idx) +{ + ut_ad(autoevent_idx < NKEYS); + return auto_event_keys[autoevent_idx]; +} + +#else /* UNIV_PFS_MEMORY */ +void ut_new_boot(){} +#endif diff --git a/storage/innobase/ut/ut0rbt.cc b/storage/innobase/ut/ut0rbt.cc new file mode 100644 index 00000000..cdd1ef06 --- /dev/null +++ b/storage/innobase/ut/ut0rbt.cc @@ -0,0 +1,1140 @@ +/***************************************************************************//** + +Copyright (c) 2007, 2015, Oracle and/or its affiliates. All Rights Reserved. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ +/********************************************************************//** +Red-Black tree implementation + +(c) 2007 Oracle/Innobase Oy + +Created 2007-03-20 Sunny Bains +***********************************************************************/ + +#include "ut0rbt.h" + +/**********************************************************************//** +Definition of a red-black tree +============================== + +A red-black tree is a binary search tree which has the following +red-black properties: + + 1. Every node is either red or black. + 2. Every leaf (NULL - in our case tree->nil) is black. + 3. If a node is red, then both its children are black. + 4. Every simple path from a node to a descendant leaf contains the + same number of black nodes. + + from (3) above, the implication is that on any path from the root + to a leaf, red nodes must not be adjacent. + + However, any number of black nodes may appear in a sequence. + */ + +#if defined(IB_RBT_TESTING) +#warning "Testing enabled!" +#endif + +#define ROOT(t) (t->root->left) +#define SIZEOF_NODE(t) ((sizeof(ib_rbt_node_t) + t->sizeof_value) - 1) + +#if defined UNIV_DEBUG || defined IB_RBT_TESTING +/**********************************************************************//** +Verify that the keys are in order. +@return TRUE of OK. FALSE if not ordered */ +static +ibool +rbt_check_ordering( +/*===============*/ + const ib_rbt_t* tree) /*!< in: tree to verfify */ +{ + const ib_rbt_node_t* node; + const ib_rbt_node_t* prev = NULL; + + /* Iterate over all the nodes, comparing each node with the prev */ + for (node = rbt_first(tree); node; node = rbt_next(tree, prev)) { + + if (prev) { + int result; + + if (tree->cmp_arg) { + result = tree->compare_with_arg( + tree->cmp_arg, prev->value, + node->value); + } else { + result = tree->compare( + prev->value, node->value); + } + + if (result >= 0) { + return(FALSE); + } + } + + prev = node; + } + + return(TRUE); +} + +/**********************************************************************//** +Check that every path from the root to the leaves has the same count. +Count is expressed in the number of black nodes. +@return 0 on failure else black height of the subtree */ +static +ibool +rbt_count_black_nodes( +/*==================*/ + const ib_rbt_t* tree, /*!< in: tree to verify */ + const ib_rbt_node_t* node) /*!< in: start of sub-tree */ +{ + ulint result; + + if (node != tree->nil) { + ulint left_height = rbt_count_black_nodes(tree, node->left); + + ulint right_height = rbt_count_black_nodes(tree, node->right); + + if (left_height == 0 + || right_height == 0 + || left_height != right_height) { + + result = 0; + } else if (node->color == IB_RBT_RED) { + + /* Case 3 */ + if (node->left->color != IB_RBT_BLACK + || node->right->color != IB_RBT_BLACK) { + + result = 0; + } else { + result = left_height; + } + /* Check if it's anything other than RED or BLACK. */ + } else if (node->color != IB_RBT_BLACK) { + + result = 0; + } else { + + result = right_height + 1; + } + } else { + result = 1; + } + + return(result); +} +#endif /* UNIV_DEBUG || IB_RBT_TESTING */ + +/**********************************************************************//** +Turn the node's right child's left sub-tree into node's right sub-tree. +This will also make node's right child it's parent. */ +static +void +rbt_rotate_left( +/*============*/ + const ib_rbt_node_t* nil, /*!< in: nil node of the tree */ + ib_rbt_node_t* node) /*!< in: node to rotate */ +{ + ib_rbt_node_t* right = node->right; + + node->right = right->left; + + if (right->left != nil) { + right->left->parent = node; + } + + /* Right's new parent was node's parent. */ + right->parent = node->parent; + + /* Since root's parent is tree->nil and root->parent->left points + back to root, we can avoid the check. */ + if (node == node->parent->left) { + /* Node was on the left of its parent. */ + node->parent->left = right; + } else { + /* Node must have been on the right. */ + node->parent->right = right; + } + + /* Finally, put node on right's left. */ + right->left = node; + node->parent = right; +} + +/**********************************************************************//** +Turn the node's left child's right sub-tree into node's left sub-tree. +This also make node's left child it's parent. */ +static +void +rbt_rotate_right( +/*=============*/ + const ib_rbt_node_t* nil, /*!< in: nil node of tree */ + ib_rbt_node_t* node) /*!< in: node to rotate */ +{ + ib_rbt_node_t* left = node->left; + + node->left = left->right; + + if (left->right != nil) { + left->right->parent = node; + } + + /* Left's new parent was node's parent. */ + left->parent = node->parent; + + /* Since root's parent is tree->nil and root->parent->left points + back to root, we can avoid the check. */ + if (node == node->parent->right) { + /* Node was on the left of its parent. */ + node->parent->right = left; + } else { + /* Node must have been on the left. */ + node->parent->left = left; + } + + /* Finally, put node on left's right. */ + left->right = node; + node->parent = left; +} + +/**********************************************************************//** +Append a node to the tree. */ +static +ib_rbt_node_t* +rbt_tree_add_child( +/*===============*/ + const ib_rbt_t* tree, + ib_rbt_bound_t* parent, + ib_rbt_node_t* node) +{ + /* Cast away the const. */ + ib_rbt_node_t* last = (ib_rbt_node_t*) parent->last; + + if (last == tree->root || parent->result < 0) { + last->left = node; + } else { + /* FIXME: We don't handle duplicates (yet)! */ + ut_a(parent->result != 0); + + last->right = node; + } + + node->parent = last; + + return(node); +} + +/**********************************************************************//** +Generic binary tree insert */ +static +ib_rbt_node_t* +rbt_tree_insert( +/*============*/ + ib_rbt_t* tree, + const void* key, + ib_rbt_node_t* node) +{ + ib_rbt_bound_t parent; + ib_rbt_node_t* current = ROOT(tree); + + parent.result = 0; + parent.last = tree->root; + + /* Regular binary search. */ + while (current != tree->nil) { + + parent.last = current; + + if (tree->cmp_arg) { + parent.result = tree->compare_with_arg( + tree->cmp_arg, key, current->value); + } else { + parent.result = tree->compare(key, current->value); + } + + if (parent.result < 0) { + current = current->left; + } else { + current = current->right; + } + } + + ut_a(current == tree->nil); + + rbt_tree_add_child(tree, &parent, node); + + return(node); +} + +/**********************************************************************//** +Balance a tree after inserting a node. */ +static +void +rbt_balance_tree( +/*=============*/ + const ib_rbt_t* tree, /*!< in: tree to balance */ + ib_rbt_node_t* node) /*!< in: node that was inserted */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* parent = node->parent; + + /* Restore the red-black property. */ + node->color = IB_RBT_RED; + + while (node != ROOT(tree) && parent->color == IB_RBT_RED) { + ib_rbt_node_t* grand_parent = parent->parent; + + if (parent == grand_parent->left) { + ib_rbt_node_t* uncle = grand_parent->right; + + if (uncle->color == IB_RBT_RED) { + + /* Case 1 - change the colors. */ + uncle->color = IB_RBT_BLACK; + parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + /* Move node up the tree. */ + node = grand_parent; + + } else { + + if (node == parent->right) { + /* Right is a black node and node is + to the right, case 2 - move node + up and rotate. */ + node = parent; + rbt_rotate_left(nil, node); + } + + grand_parent = node->parent->parent; + + /* Case 3. */ + node->parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + rbt_rotate_right(nil, grand_parent); + } + + } else { + ib_rbt_node_t* uncle = grand_parent->left; + + if (uncle->color == IB_RBT_RED) { + + /* Case 1 - change the colors. */ + uncle->color = IB_RBT_BLACK; + parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + /* Move node up the tree. */ + node = grand_parent; + + } else { + + if (node == parent->left) { + /* Left is a black node and node is to + the right, case 2 - move node up and + rotate. */ + node = parent; + rbt_rotate_right(nil, node); + } + + grand_parent = node->parent->parent; + + /* Case 3. */ + node->parent->color = IB_RBT_BLACK; + grand_parent->color = IB_RBT_RED; + + rbt_rotate_left(nil, grand_parent); + } + } + + parent = node->parent; + } + + /* Color the root black. */ + ROOT(tree)->color = IB_RBT_BLACK; +} + +/**********************************************************************//** +Find the given node's successor. +@return successor node or NULL if no successor */ +static +ib_rbt_node_t* +rbt_find_successor( +/*===============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current) /*!< in: this is declared const + because it can be called via + rbt_next() */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* next = current->right; + + /* Is there a sub-tree to the right that we can follow. */ + if (next != nil) { + + /* Follow the left most links of the current right child. */ + while (next->left != nil) { + next = next->left; + } + + } else { /* We will have to go up the tree to find the successor. */ + ib_rbt_node_t* parent = current->parent; + + /* Cast away the const. */ + next = (ib_rbt_node_t*) current; + + while (parent != tree->root && next == parent->right) { + next = parent; + parent = next->parent; + } + + next = (parent == tree->root) ? NULL : parent; + } + + return(next); +} + +/**********************************************************************//** +Find the given node's precedecessor. +@return predecessor node or NULL if no predecesor */ +static +ib_rbt_node_t* +rbt_find_predecessor( +/*=================*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current) /*!< in: this is declared const + because it can be called via + rbt_prev() */ +{ + const ib_rbt_node_t* nil = tree->nil; + ib_rbt_node_t* prev = current->left; + + /* Is there a sub-tree to the left that we can follow. */ + if (prev != nil) { + + /* Follow the right most links of the current left child. */ + while (prev->right != nil) { + prev = prev->right; + } + + } else { /* We will have to go up the tree to find the precedecessor. */ + ib_rbt_node_t* parent = current->parent; + + /* Cast away the const. */ + prev = (ib_rbt_node_t*) current; + + while (parent != tree->root && prev == parent->left) { + prev = parent; + parent = prev->parent; + } + + prev = (parent == tree->root) ? NULL : parent; + } + + return(prev); +} + +/**********************************************************************//** +Replace node with child. After applying transformations eject becomes +an orphan. */ +static +void +rbt_eject_node( +/*===========*/ + ib_rbt_node_t* eject, /*!< in: node to eject */ + ib_rbt_node_t* node) /*!< in: node to replace with */ +{ + /* Update the to be ejected node's parent's child pointers. */ + if (eject->parent->left == eject) { + eject->parent->left = node; + } else if (eject->parent->right == eject) { + eject->parent->right = node; + } else { + ut_a(0); + } + /* eject is now an orphan but otherwise its pointers + and color are left intact. */ + + node->parent = eject->parent; +} + +/**********************************************************************//** +Replace a node with another node. */ +static +void +rbt_replace_node( +/*=============*/ + ib_rbt_node_t* replace, /*!< in: node to replace */ + ib_rbt_node_t* node) /*!< in: node to replace with */ +{ + ib_rbt_color_t color = node->color; + + /* Update the node pointers. */ + node->left = replace->left; + node->right = replace->right; + + /* Update the child node pointers. */ + node->left->parent = node; + node->right->parent = node; + + /* Make the parent of replace point to node. */ + rbt_eject_node(replace, node); + + /* Swap the colors. */ + node->color = replace->color; + replace->color = color; +} + +/**********************************************************************//** +Detach node from the tree replacing it with one of it's children. +@return the child node that now occupies the position of the detached node */ +static +ib_rbt_node_t* +rbt_detach_node( +/*============*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_node_t* node) /*!< in: node to detach */ +{ + ib_rbt_node_t* child; + const ib_rbt_node_t* nil = tree->nil; + + if (node->left != nil && node->right != nil) { + /* Case where the node to be deleted has two children. */ + ib_rbt_node_t* successor = rbt_find_successor(tree, node); + + ut_a(successor != nil); + ut_a(successor->parent != nil); + ut_a(successor->left == nil); + + child = successor->right; + + /* Remove the successor node and replace with its child. */ + rbt_eject_node(successor, child); + + /* Replace the node to delete with its successor node. */ + rbt_replace_node(node, successor); + } else { + ut_a(node->left == nil || node->right == nil); + + child = (node->left != nil) ? node->left : node->right; + + /* Replace the node to delete with one of it's children. */ + rbt_eject_node(node, child); + } + + /* Reset the node links. */ + node->parent = node->right = node->left = tree->nil; + + return(child); +} + +/**********************************************************************//** +Rebalance the right sub-tree after deletion. +@return node to rebalance if more rebalancing required else NULL */ +static +ib_rbt_node_t* +rbt_balance_right( +/*==============*/ + const ib_rbt_node_t* nil, /*!< in: rb tree nil node */ + ib_rbt_node_t* parent, /*!< in: parent node */ + ib_rbt_node_t* sibling) /*!< in: sibling node */ +{ + ib_rbt_node_t* node = NULL; + + ut_a(sibling != nil); + + /* Case 3. */ + if (sibling->color == IB_RBT_RED) { + + parent->color = IB_RBT_RED; + sibling->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, parent); + + sibling = parent->right; + + ut_a(sibling != nil); + } + + /* Since this will violate case 3 because of the change above. */ + if (sibling->left->color == IB_RBT_BLACK + && sibling->right->color == IB_RBT_BLACK) { + + node = parent; /* Parent needs to be rebalanced too. */ + sibling->color = IB_RBT_RED; + + } else { + if (sibling->right->color == IB_RBT_BLACK) { + + ut_a(sibling->left->color == IB_RBT_RED); + + sibling->color = IB_RBT_RED; + sibling->left->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, sibling); + + sibling = parent->right; + ut_a(sibling != nil); + } + + sibling->color = parent->color; + sibling->right->color = IB_RBT_BLACK; + + parent->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, parent); + } + + return(node); +} + +/**********************************************************************//** +Rebalance the left sub-tree after deletion. +@return node to rebalance if more rebalancing required else NULL */ +static +ib_rbt_node_t* +rbt_balance_left( +/*=============*/ + const ib_rbt_node_t* nil, /*!< in: rb tree nil node */ + ib_rbt_node_t* parent, /*!< in: parent node */ + ib_rbt_node_t* sibling) /*!< in: sibling node */ +{ + ib_rbt_node_t* node = NULL; + + ut_a(sibling != nil); + + /* Case 3. */ + if (sibling->color == IB_RBT_RED) { + + parent->color = IB_RBT_RED; + sibling->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, parent); + sibling = parent->left; + + ut_a(sibling != nil); + } + + /* Since this will violate case 3 because of the change above. */ + if (sibling->right->color == IB_RBT_BLACK + && sibling->left->color == IB_RBT_BLACK) { + + node = parent; /* Parent needs to be rebalanced too. */ + sibling->color = IB_RBT_RED; + + } else { + if (sibling->left->color == IB_RBT_BLACK) { + + ut_a(sibling->right->color == IB_RBT_RED); + + sibling->color = IB_RBT_RED; + sibling->right->color = IB_RBT_BLACK; + + rbt_rotate_left(nil, sibling); + + sibling = parent->left; + + ut_a(sibling != nil); + } + + sibling->color = parent->color; + sibling->left->color = IB_RBT_BLACK; + + parent->color = IB_RBT_BLACK; + + rbt_rotate_right(nil, parent); + } + + return(node); +} + +/**********************************************************************//** +Delete the node and rebalance the tree if necessary */ +static +void +rbt_remove_node_and_rebalance( +/*==========================*/ + ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_node_t* node) /*!< in: node to remove */ +{ + /* Detach node and get the node that will be used + as rebalance start. */ + ib_rbt_node_t* child = rbt_detach_node(tree, node); + + if (node->color == IB_RBT_BLACK) { + ib_rbt_node_t* last = child; + + ROOT(tree)->color = IB_RBT_RED; + + while (child && child->color == IB_RBT_BLACK) { + ib_rbt_node_t* parent = child->parent; + + /* Did the deletion cause an imbalance in the + parents left sub-tree. */ + if (parent->left == child) { + + child = rbt_balance_right( + tree->nil, parent, parent->right); + + } else if (parent->right == child) { + + child = rbt_balance_left( + tree->nil, parent, parent->left); + + } else { + ut_error; + } + + if (child) { + last = child; + } + } + + ut_a(last); + + last->color = IB_RBT_BLACK; + ROOT(tree)->color = IB_RBT_BLACK; + } + + /* Note that we have removed a node from the tree. */ + --tree->n_nodes; +} + +/**********************************************************************//** +Recursively free the nodes. */ +static +void +rbt_free_node( +/*==========*/ + ib_rbt_node_t* node, /*!< in: node to free */ + ib_rbt_node_t* nil) /*!< in: rb tree nil node */ +{ + if (node != nil) { + rbt_free_node(node->left, nil); + rbt_free_node(node->right, nil); + + ut_free(node); + } +} + +/**********************************************************************//** +Free all the nodes and free the tree. */ +void +rbt_free( +/*=====*/ + ib_rbt_t* tree) /*!< in: rb tree to free */ +{ + rbt_free_node(tree->root, tree->nil); + ut_free(tree->nil); + ut_free(tree); +} + +/**********************************************************************//** +Create an instance of a red black tree, whose comparison function takes +an argument +@return an empty rb tree */ +ib_rbt_t* +rbt_create_arg_cmp( +/*===============*/ + size_t sizeof_value, /*!< in: sizeof data item */ + ib_rbt_arg_compare + compare, /*!< in: fn to compare items */ + void* cmp_arg) /*!< in: compare fn arg */ +{ + ib_rbt_t* tree; + + ut_a(cmp_arg); + + tree = rbt_create(sizeof_value, NULL); + tree->cmp_arg = cmp_arg; + tree->compare_with_arg = compare; + + return(tree); +} + +/**********************************************************************//** +Create an instance of a red black tree. +@return an empty rb tree */ +ib_rbt_t* +rbt_create( +/*=======*/ + size_t sizeof_value, /*!< in: sizeof data item */ + ib_rbt_compare compare) /*!< in: fn to compare items */ +{ + ib_rbt_t* tree; + ib_rbt_node_t* node; + + tree = (ib_rbt_t*) ut_zalloc_nokey(sizeof(*tree)); + + tree->sizeof_value = sizeof_value; + + /* Create the sentinel (NIL) node. */ + node = tree->nil = (ib_rbt_node_t*) ut_zalloc_nokey(sizeof(*node)); + + node->color = IB_RBT_BLACK; + node->parent = node->left = node->right = node; + + /* Create the "fake" root, the real root node will be the + left child of this node. */ + node = tree->root = (ib_rbt_node_t*) ut_zalloc_nokey(sizeof(*node)); + + node->color = IB_RBT_BLACK; + node->parent = node->left = node->right = tree->nil; + + tree->compare = compare; + + return(tree); +} + +/**********************************************************************//** +Generic insert of a value in the rb tree. +@return inserted node */ +const ib_rbt_node_t* +rbt_insert( +/*=======*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const void* key, /*!< in: key for ordering */ + const void* value) /*!< in: value of key, this value + is copied to the node */ +{ + ib_rbt_node_t* node; + + /* Create the node that will hold the value data. */ + node = (ib_rbt_node_t*) ut_malloc_nokey(SIZEOF_NODE(tree)); + + memcpy(node->value, value, tree->sizeof_value); + node->parent = node->left = node->right = tree->nil; + + /* Insert in the tree in the usual way. */ + rbt_tree_insert(tree, key, node); + rbt_balance_tree(tree, node); + + ++tree->n_nodes; + + return(node); +} + +/**********************************************************************//** +Add a new node to the tree, useful for data that is pre-sorted. +@return appended node */ +const ib_rbt_node_t* +rbt_add_node( +/*=========*/ + ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: bounds */ + const void* value) /*!< in: this value is copied + to the node */ +{ + ib_rbt_node_t* node; + + /* Create the node that will hold the value data */ + node = (ib_rbt_node_t*) ut_malloc_nokey(SIZEOF_NODE(tree)); + + memcpy(node->value, value, tree->sizeof_value); + node->parent = node->left = node->right = tree->nil; + + /* If tree is empty */ + if (parent->last == NULL) { + parent->last = tree->root; + } + + /* Append the node, the hope here is that the caller knows + what s/he is doing. */ + rbt_tree_add_child(tree, parent, node); + rbt_balance_tree(tree, node); + + ++tree->n_nodes; + +#if defined UNIV_DEBUG || defined IB_RBT_TESTING + ut_a(rbt_validate(tree)); +#endif + return(node); +} + +/**********************************************************************//** +Find a matching node in the rb tree. +@return NULL if not found else the node where key was found */ +static +const ib_rbt_node_t* +rbt_lookup( +/*=======*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to use for search */ +{ + const ib_rbt_node_t* current = ROOT(tree); + + /* Regular binary search. */ + while (current != tree->nil) { + int result; + + if (tree->cmp_arg) { + result = tree->compare_with_arg( + tree->cmp_arg, key, current->value); + } else { + result = tree->compare(key, current->value); + } + + if (result < 0) { + current = current->left; + } else if (result > 0) { + current = current->right; + } else { + break; + } + } + + return(current != tree->nil ? current : NULL); +} + +/**********************************************************************//** +Delete a node indentified by key. +@return TRUE if success FALSE if not found */ +ibool +rbt_delete( +/*=======*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const void* key) /*!< in: key to delete */ +{ + ibool deleted = FALSE; + ib_rbt_node_t* node = (ib_rbt_node_t*) rbt_lookup(tree, key); + + if (node) { + rbt_remove_node_and_rebalance(tree, node); + + ut_free(node); + deleted = TRUE; + } + + return(deleted); +} + +/**********************************************************************//** +Remove a node from the rb tree, the node is not free'd, that is the +callers responsibility. +@return deleted node but without the const */ +ib_rbt_node_t* +rbt_remove_node( +/*============*/ + ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* const_node) /*!< in: node to delete, this + is a fudge and declared const + because the caller can access + only const nodes */ +{ + /* Cast away the const. */ + rbt_remove_node_and_rebalance(tree, (ib_rbt_node_t*) const_node); + + /* This is to make it easier to do something like this: + ut_free(rbt_remove_node(node)); + */ + + return((ib_rbt_node_t*) const_node); +} + +/**********************************************************************//** +Find the node that has the greatest key that is <= key. +@return value of result */ +int +rbt_search( +/*=======*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: search bounds */ + const void* key) /*!< in: key to search */ +{ + ib_rbt_node_t* current = ROOT(tree); + + /* Every thing is greater than the NULL root. */ + parent->result = 1; + parent->last = NULL; + + while (current != tree->nil) { + + parent->last = current; + + if (tree->cmp_arg) { + parent->result = tree->compare_with_arg( + tree->cmp_arg, key, current->value); + } else { + parent->result = tree->compare(key, current->value); + } + + if (parent->result > 0) { + current = current->right; + } else if (parent->result < 0) { + current = current->left; + } else { + break; + } + } + + return(parent->result); +} + +/**********************************************************************//** +Find the node that has the greatest key that is <= key. But use the +supplied comparison function. +@return value of result */ +int +rbt_search_cmp( +/*===========*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + ib_rbt_bound_t* parent, /*!< in: search bounds */ + const void* key, /*!< in: key to search */ + ib_rbt_compare compare, /*!< in: fn to compare items */ + ib_rbt_arg_compare + arg_compare) /*!< in: fn to compare items + with argument */ +{ + ib_rbt_node_t* current = ROOT(tree); + + /* Every thing is greater than the NULL root. */ + parent->result = 1; + parent->last = NULL; + + while (current != tree->nil) { + + parent->last = current; + + if (arg_compare) { + ut_ad(tree->cmp_arg); + parent->result = arg_compare( + tree->cmp_arg, key, current->value); + } else { + parent->result = compare(key, current->value); + } + + if (parent->result > 0) { + current = current->right; + } else if (parent->result < 0) { + current = current->left; + } else { + break; + } + } + + return(parent->result); +} + +/**********************************************************************//** +Return the left most node in the tree. */ +const ib_rbt_node_t* +rbt_first( +/*======*/ + /* out leftmost node or NULL */ + const ib_rbt_t* tree) /* in: rb tree */ +{ + ib_rbt_node_t* first = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + first = current; + current = current->left; + } + + return(first); +} + +/**********************************************************************//** +Return the right most node in the tree. +@return the rightmost node or NULL */ +const ib_rbt_node_t* +rbt_last( +/*=====*/ + const ib_rbt_t* tree) /*!< in: rb tree */ +{ + ib_rbt_node_t* last = NULL; + ib_rbt_node_t* current = ROOT(tree); + + while (current != tree->nil) { + last = current; + current = current->right; + } + + return(last); +} + +/**********************************************************************//** +Return the next node. +@return node next from current */ +const ib_rbt_node_t* +rbt_next( +/*=====*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current) /*!< in: current node */ +{ + return(current ? rbt_find_successor(tree, current) : NULL); +} + +/**********************************************************************//** +Return the previous node. +@return node prev from current */ +const ib_rbt_node_t* +rbt_prev( +/*=====*/ + const ib_rbt_t* tree, /*!< in: rb tree */ + const ib_rbt_node_t* current) /*!< in: current node */ +{ + return(current ? rbt_find_predecessor(tree, current) : NULL); +} + +/**********************************************************************//** +Merge the node from dst into src. Return the number of nodes merged. +@return no. of recs merged */ +ulint +rbt_merge_uniq( +/*===========*/ + ib_rbt_t* dst, /*!< in: dst rb tree */ + const ib_rbt_t* src) /*!< in: src rb tree */ +{ + ib_rbt_bound_t parent; + ulint n_merged = 0; + const ib_rbt_node_t* src_node = rbt_first(src); + + if (rbt_empty(src) || dst == src) { + return(0); + } + + for (/* No op */; src_node; src_node = rbt_next(src, src_node)) { + + if (rbt_search(dst, &parent, src_node->value) != 0) { + rbt_add_node(dst, &parent, src_node->value); + ++n_merged; + } + } + + return(n_merged); +} + +#if defined UNIV_DEBUG || defined IB_RBT_TESTING +/**********************************************************************//** +Check that every path from the root to the leaves has the same count and +the tree nodes are in order. +@return TRUE if OK FALSE otherwise */ +ibool +rbt_validate( +/*=========*/ + const ib_rbt_t* tree) /*!< in: RB tree to validate */ +{ + if (rbt_count_black_nodes(tree, ROOT(tree)) > 0) { + return(rbt_check_ordering(tree)); + } + + return(FALSE); +} +#endif /* UNIV_DEBUG || IB_RBT_TESTING */ diff --git a/storage/innobase/ut/ut0rnd.cc b/storage/innobase/ut/ut0rnd.cc new file mode 100644 index 00000000..a2e56951 --- /dev/null +++ b/storage/innobase/ut/ut0rnd.cc @@ -0,0 +1,93 @@ +/***************************************************************************** + +Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2019, 2020, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/***************************************************************//** +@file ut/ut0rnd.cc +Random numbers and hashing + +Created 5/11/1994 Heikki Tuuri +********************************************************************/ + +#include "ut0rnd.h" + +/** Seed value of ut_rnd_gen() */ +std::atomic<uint32_t> ut_rnd_current; + +/** These random numbers are used in ut_find_prime */ +/*@{*/ +#define UT_RANDOM_1 1.0412321 +#define UT_RANDOM_2 1.1131347 +#define UT_RANDOM_3 1.0132677 +/*@}*/ + +/***********************************************************//** +Looks for a prime number slightly greater than the given argument. +The prime is chosen so that it is not near any power of 2. +@return prime */ +ulint +ut_find_prime( +/*==========*/ + ulint n) /*!< in: positive number > 100 */ +{ + ulint pow2; + ulint i; + + n += 100; + + pow2 = 1; + while (pow2 * 2 < n) { + pow2 = 2 * pow2; + } + + if ((double) n < 1.05 * (double) pow2) { + n = (ulint) ((double) n * UT_RANDOM_1); + } + + pow2 = 2 * pow2; + + if ((double) n > 0.95 * (double) pow2) { + n = (ulint) ((double) n * UT_RANDOM_2); + } + + if (n > pow2 - 20) { + n += 30; + } + + /* Now we have n far enough from powers of 2. To make + n more random (especially, if it was not near + a power of 2), we then multiply it by a random number. */ + + n = (ulint) ((double) n * UT_RANDOM_3); + + for (;; n++) { + i = 2; + while (i * i <= n) { + if (n % i == 0) { + goto next_n; + } + i++; + } + + /* Found a prime */ + break; +next_n: ; + } + + return(n); +} diff --git a/storage/innobase/ut/ut0ut.cc b/storage/innobase/ut/ut0ut.cc new file mode 100644 index 00000000..1dd1cff6 --- /dev/null +++ b/storage/innobase/ut/ut0ut.cc @@ -0,0 +1,648 @@ +/***************************************************************************** + +Copyright (c) 1994, 2017, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2017, 2021, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/***************************************************************//** +@file ut/ut0ut.cc +Various utilities for Innobase. + +Created 5/11/1994 Heikki Tuuri +********************************************************************/ + +#include "ha_prototypes.h" + +#if HAVE_SYS_TIME_H +#include <sys/time.h> +#endif + +#ifndef UNIV_INNOCHECKSUM +#include <mysql_com.h> +#include "os0thread.h" +#include "ut0ut.h" +#include "trx0trx.h" +#include <string> +#include "log.h" +#include "my_cpu.h" +#ifndef DBUG_OFF +#include "rem0rec.h" +#endif + +/**********************************************************//** +Returns the number of milliseconds since some epoch. The +value may wrap around. It should only be used for heuristic +purposes. +@return ms since epoch */ +ulint +ut_time_ms(void) +/*============*/ +{ + return static_cast<ulint>(my_interval_timer() / 1000000); +} +#endif /* !UNIV_INNOCHECKSUM */ + +/**********************************************************//** +Prints a timestamp to a file. */ +void +ut_print_timestamp( +/*===============*/ + FILE* file) /*!< in: file where to print */ +{ +#ifdef _WIN32 + SYSTEMTIME cal_tm; + GetLocalTime(&cal_tm); +#else + time_t tm; + struct tm cal_tm; + time(&tm); + localtime_r(&tm, &cal_tm); +#endif + fprintf(file, + IF_WIN("%u-%02u-%02u %02u:%02u:%02u %#zx", + "%d-%02d-%02d %02d:%02d:%02d %#zx"), +#ifdef _WIN32 + cal_tm.wYear, + cal_tm.wMonth, + cal_tm.wDay, + cal_tm.wHour, + cal_tm.wMinute, + cal_tm.wSecond, +#else + cal_tm.tm_year + 1900, + cal_tm.tm_mon + 1, + cal_tm.tm_mday, + cal_tm.tm_hour, + cal_tm.tm_min, + cal_tm.tm_sec, +#endif +#ifdef UNIV_INNOCHECKSUM + ulint{0} +#else + ulint(os_thread_get_curr_id()) +#endif + ); +} + +#ifndef UNIV_INNOCHECKSUM + +/**********************************************************//** +Sprintfs a timestamp to a buffer, 13..14 chars plus terminating NUL. */ +void +ut_sprintf_timestamp( +/*=================*/ + char* buf) /*!< in: buffer where to sprintf */ +{ +#ifdef _WIN32 + SYSTEMTIME cal_tm; + GetLocalTime(&cal_tm); + + sprintf(buf, "%02u%02u%02u %2u:%02u:%02u", + cal_tm.wYear % 100, + cal_tm.wMonth, + cal_tm.wDay, + cal_tm.wHour, + cal_tm.wMinute, + cal_tm.wSecond); +#else + time_t tm; + struct tm cal_tm; + time(&tm); + localtime_r(&tm, &cal_tm); + sprintf(buf, "%02d%02d%02d %2d:%02d:%02d", + cal_tm.tm_year % 100, + cal_tm.tm_mon + 1, + cal_tm.tm_mday, + cal_tm.tm_hour, + cal_tm.tm_min, + cal_tm.tm_sec); +#endif +} + +/*************************************************************//** +Prints the contents of a memory buffer in hex and ascii. */ +void +ut_print_buf( +/*=========*/ + FILE* file, /*!< in: file where to print */ + const void* buf, /*!< in: memory buffer */ + ulint len) /*!< in: length of the buffer */ +{ + const byte* data; + ulint i; + + fprintf(file, " len " ULINTPF "; hex ", len); + + for (data = (const byte*) buf, i = 0; i < len; i++) { + fprintf(file, "%02x", *data++); + } + + fputs("; asc ", file); + + data = (const byte*) buf; + + for (i = 0; i < len; i++) { + int c = (int) *data++; + putc(isprint(c) ? c : ' ', file); + } + + putc(';', file); +} + +/*************************************************************//** +Prints the contents of a memory buffer in hex. */ +void +ut_print_buf_hex( +/*=============*/ + std::ostream& o, /*!< in/out: output stream */ + const void* buf, /*!< in: memory buffer */ + ulint len) /*!< in: length of the buffer */ +{ + const byte* data; + ulint i; + + static const char hexdigit[16] = { + '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' + }; + + o << "(0x"; + + for (data = static_cast<const byte*>(buf), i = 0; i < len; i++) { + byte b = *data++; + o << hexdigit[int(b) >> 4] << hexdigit[b & 15]; + } + + o << ")"; +} + +/*************************************************************//** +Prints the contents of a memory buffer in hex and ascii. */ +void +ut_print_buf( +/*=========*/ + std::ostream& o, /*!< in/out: output stream */ + const void* buf, /*!< in: memory buffer */ + ulint len) /*!< in: length of the buffer */ +{ + const byte* data; + ulint i; + + for (data = static_cast<const byte*>(buf), i = 0; i < len; i++) { + int c = static_cast<int>(*data++); + o << (isprint(c) ? static_cast<char>(c) : ' '); + } + + ut_print_buf_hex(o, buf, len); +} + +/** Get a fixed-length string, quoted as an SQL identifier. +If the string contains a slash '/', the string will be +output as two identifiers separated by a period (.), +as in SQL database_name.identifier. + @param [in] trx transaction (NULL=no quotes). + @param [in] name table name. + @retval String quoted as an SQL identifier. +*/ +std::string +ut_get_name( + const trx_t* trx, + const char* name) +{ + /* 2 * NAME_LEN for database and table name, + and some slack for the #mysql50# prefix and quotes */ + char buf[3 * NAME_LEN]; + const char* bufend; + + bufend = innobase_convert_name(buf, sizeof buf, + name, strlen(name), + trx ? trx->mysql_thd : NULL); + buf[bufend - buf] = '\0'; + return(std::string(buf, 0, size_t(bufend - buf))); +} + +/**********************************************************************//** +Outputs a fixed-length string, quoted as an SQL identifier. +If the string contains a slash '/', the string will be +output as two identifiers separated by a period (.), +as in SQL database_name.identifier. */ +void +ut_print_name( +/*==========*/ + FILE* f, /*!< in: output stream */ + const trx_t* trx, /*!< in: transaction */ + const char* name) /*!< in: name to print */ +{ + /* 2 * NAME_LEN for database and table name, + and some slack for the #mysql50# prefix and quotes */ + char buf[3 * NAME_LEN]; + const char* bufend; + + bufend = innobase_convert_name(buf, sizeof buf, + name, strlen(name), + trx ? trx->mysql_thd : NULL); + + if (fwrite(buf, 1, size_t(bufend - buf), f) != size_t(bufend - buf)) { + perror("fwrite"); + } +} + +/** Format a table name, quoted as an SQL identifier. +If the name contains a slash '/', the result will contain two +identifiers separated by a period (.), as in SQL +database_name.table_name. +@see table_name_t +@param[in] name table or index name +@param[out] formatted formatted result, will be NUL-terminated +@param[in] formatted_size size of the buffer in bytes +@return pointer to 'formatted' */ +char* +ut_format_name( + const char* name, + char* formatted, + ulint formatted_size) +{ + switch (formatted_size) { + case 1: + formatted[0] = '\0'; + /* FALL-THROUGH */ + case 0: + return(formatted); + } + + char* end; + + end = innobase_convert_name(formatted, formatted_size, + name, strlen(name), NULL); + + /* If the space in 'formatted' was completely used, then sacrifice + the last character in order to write '\0' at the end. */ + if ((ulint) (end - formatted) == formatted_size) { + end--; + } + + ut_a((ulint) (end - formatted) < formatted_size); + + *end = '\0'; + + return(formatted); +} + +/**********************************************************************//** +Catenate files. */ +void +ut_copy_file( +/*=========*/ + FILE* dest, /*!< in: output file */ + FILE* src) /*!< in: input file to be appended to output */ +{ + long len = ftell(src); + char buf[4096]; + + rewind(src); + do { + size_t maxs = len < (long) sizeof buf + ? (size_t) len + : sizeof buf; + size_t size = fread(buf, 1, maxs, src); + if (fwrite(buf, 1, size, dest) != size) { + perror("fwrite"); + } + len -= (long) size; + if (size < maxs) { + break; + } + } while (len > 0); +} + +/** Convert an error number to a human readable text message. +The returned string is static and should not be freed or modified. +@param[in] num InnoDB internal error number +@return string, describing the error */ +const char* +ut_strerr( + dberr_t num) +{ + switch (num) { + case DB_SUCCESS: + return("Success"); + case DB_SUCCESS_LOCKED_REC: + return("Success, record lock created"); + case DB_ERROR: + return("Generic error"); + case DB_READ_ONLY: + return("Read only transaction"); + case DB_INTERRUPTED: + return("Operation interrupted"); + case DB_OUT_OF_MEMORY: + return("Cannot allocate memory"); + case DB_OUT_OF_FILE_SPACE: + return("Out of disk space"); + case DB_LOCK_WAIT: + return("Lock wait"); + case DB_DEADLOCK: + return("Deadlock"); + case DB_ROLLBACK: + return("Rollback"); + case DB_DUPLICATE_KEY: + return("Duplicate key"); + case DB_MISSING_HISTORY: + return("Required history data has been deleted"); + case DB_CLUSTER_NOT_FOUND: + return("Cluster not found"); + case DB_TABLE_NOT_FOUND: + return("Table not found"); + case DB_MUST_GET_MORE_FILE_SPACE: + return("More file space needed"); + case DB_TABLE_IS_BEING_USED: + return("Table is being used"); + case DB_TOO_BIG_RECORD: + return("Record too big"); + case DB_TOO_BIG_INDEX_COL: + return("Index columns size too big"); + case DB_LOCK_WAIT_TIMEOUT: + return("Lock wait timeout"); + case DB_NO_REFERENCED_ROW: + return("Referenced key value not found"); + case DB_ROW_IS_REFERENCED: + return("Row is referenced"); + case DB_CANNOT_ADD_CONSTRAINT: + return("Cannot add constraint"); + case DB_CORRUPTION: + return("Data structure corruption"); + case DB_CANNOT_DROP_CONSTRAINT: + return("Cannot drop constraint"); + case DB_NO_SAVEPOINT: + return("No such savepoint"); + case DB_TABLESPACE_EXISTS: + return("Tablespace already exists"); + case DB_TABLESPACE_DELETED: + return("Tablespace deleted or being deleted"); + case DB_TABLESPACE_NOT_FOUND: + return("Tablespace not found"); + case DB_LOCK_TABLE_FULL: + return("Lock structs have exhausted the buffer pool"); + case DB_FOREIGN_DUPLICATE_KEY: + return("Foreign key activated with duplicate keys"); + case DB_FOREIGN_EXCEED_MAX_CASCADE: + return("Foreign key cascade delete/update exceeds max depth"); + case DB_TOO_MANY_CONCURRENT_TRXS: + return("Too many concurrent transactions"); + case DB_UNSUPPORTED: + return("Unsupported"); + case DB_INVALID_NULL: + return("NULL value encountered in NOT NULL column"); + case DB_STATS_DO_NOT_EXIST: + return("Persistent statistics do not exist"); + case DB_FAIL: + return("Failed, retry may succeed"); + case DB_OVERFLOW: + return("Overflow"); + case DB_UNDERFLOW: + return("Underflow"); + case DB_STRONG_FAIL: + return("Failed, retry will not succeed"); + case DB_ZIP_OVERFLOW: + return("Zip overflow"); + case DB_RECORD_NOT_FOUND: + return("Record not found"); + case DB_CHILD_NO_INDEX: + return("No index on referencing keys in referencing table"); + case DB_PARENT_NO_INDEX: + return("No index on referenced keys in referenced table"); + case DB_FTS_INVALID_DOCID: + return("FTS Doc ID cannot be zero"); + case DB_INDEX_CORRUPT: + return("Index corrupted"); + case DB_UNDO_RECORD_TOO_BIG: + return("Undo record too big"); + case DB_END_OF_INDEX: + return("End of index"); + case DB_IO_ERROR: + return("I/O error"); + case DB_TABLE_IN_FK_CHECK: + return("Table is being used in foreign key check"); + case DB_NOT_FOUND: + return("not found"); + case DB_ONLINE_LOG_TOO_BIG: + return("Log size exceeded during online index creation"); + case DB_IDENTIFIER_TOO_LONG: + return("Identifier name is too long"); + case DB_FTS_EXCEED_RESULT_CACHE_LIMIT: + return("FTS query exceeds result cache limit"); + case DB_TEMP_FILE_WRITE_FAIL: + return("Temp file write failure"); + case DB_CANT_CREATE_GEOMETRY_OBJECT: + return("Can't create specificed geometry data object"); + case DB_CANNOT_OPEN_FILE: + return("Cannot open a file"); + case DB_TABLE_CORRUPT: + return("Table is corrupted"); + case DB_FTS_TOO_MANY_WORDS_IN_PHRASE: + return("Too many words in a FTS phrase or proximity search"); + case DB_DECRYPTION_FAILED: + return("Table is encrypted but decrypt failed."); + case DB_IO_PARTIAL_FAILED: + return("Partial IO failed"); + case DB_FORCED_ABORT: + return("Transaction aborted by another higher priority " + "transaction"); + case DB_COMPUTE_VALUE_FAILED: + return("Compute generated column failed"); + case DB_NO_FK_ON_S_BASE_COL: + return("Cannot add foreign key on the base column " + "of stored column"); + case DB_IO_NO_PUNCH_HOLE: + return ("File system does not support punch hole (trim) operation."); + case DB_PAGE_CORRUPTED: + return("Page read from tablespace is corrupted."); + + /* do not add default: in order to produce a warning if new code + is added to the enum but not added here */ + } + + /* we abort here because if unknown error code is given, this could + mean that memory corruption has happened and someone's error-code + variable has been overwritten with bogus data */ + ut_error; + + /* NOT REACHED */ + return("Unknown error"); +} + +#ifdef UNIV_PFS_MEMORY + +/** Extract the basename of a file without its extension. +For example, extract "foo0bar" out of "/path/to/foo0bar.cc". +@param[in] file file path, e.g. "/path/to/foo0bar.cc" +@param[out] base result, e.g. "foo0bar" +@param[in] base_size size of the output buffer 'base', if there +is not enough space, then the result will be truncated, but always +'\0'-terminated +@return number of characters that would have been printed if the size +were unlimited (not including the final ‘\0’) */ +size_t +ut_basename_noext( + const char* file, + char* base, + size_t base_size) +{ + /* Assuming 'file' contains something like the following, + extract the file name without the extenstion out of it by + setting 'beg' and 'len'. + ...mysql-trunk/storage/innobase/dict/dict0dict.cc:302 + ^-- beg, len=9 + */ + + const char* beg = strrchr(file, OS_PATH_SEPARATOR); + + if (beg == NULL) { + beg = file; + } else { + beg++; + } + + size_t len = strlen(beg); + + const char* end = strrchr(beg, '.'); + + if (end != NULL) { + len = end - beg; + } + + const size_t copy_len = std::min(len, base_size - 1); + + memcpy(base, beg, copy_len); + + base[copy_len] = '\0'; + + return(len); +} + +#endif /* UNIV_PFS_MEMORY */ + +namespace ib { + +ATTRIBUTE_COLD logger& logger::operator<<(dberr_t err) +{ + m_oss << ut_strerr(err); + return *this; +} + +info::~info() +{ + sql_print_information("InnoDB: %s", m_oss.str().c_str()); +} + +warn::~warn() +{ + sql_print_warning("InnoDB: %s", m_oss.str().c_str()); +} + +/** true if error::~error() was invoked, false otherwise */ +bool error::logged; + +error::~error() +{ + sql_print_error("InnoDB: %s", m_oss.str().c_str()); + logged = true; +} + +#ifdef _MSC_VER +/* disable warning + "ib::fatal::~fatal': destructor never returns, potential memory leak" + on Windows. +*/ +#pragma warning (push) +#pragma warning (disable : 4722) +#endif + +ATTRIBUTE_NORETURN +fatal::~fatal() +{ + sql_print_error("[FATAL] InnoDB: %s", m_oss.str().c_str()); + abort(); +} + +#ifdef _MSC_VER +#pragma warning (pop) +#endif + +error_or_warn::~error_or_warn() +{ + if (m_error) { + sql_print_error("InnoDB: %s", m_oss.str().c_str()); + } else { + sql_print_warning("InnoDB: %s", m_oss.str().c_str()); + } +} + +fatal_or_error::~fatal_or_error() +{ + sql_print_error(m_fatal ? "[FATAL] InnoDB: %s" : "InnoDB: %s", + m_oss.str().c_str()); + if (m_fatal) { + abort(); + } +} + +} // namespace ib + +#ifndef DBUG_OFF +static char dbug_print_buf[1024]; + +const char * dbug_print_rec(const rec_t* rec, const rec_offs* offsets) +{ + rec_printer r(rec, offsets); + strmake(dbug_print_buf, r.str().c_str(), sizeof(dbug_print_buf) - 1); + return dbug_print_buf; +} + +const char * dbug_print_rec(const rec_t* rec, ulint info, const rec_offs* offsets) +{ + rec_printer r(rec, info, offsets); + strmake(dbug_print_buf, r.str().c_str(), sizeof(dbug_print_buf) - 1); + return dbug_print_buf; +} + +const char * dbug_print_rec(const dtuple_t* tuple) +{ + rec_printer r(tuple); + strmake(dbug_print_buf, r.str().c_str(), sizeof(dbug_print_buf) - 1); + return dbug_print_buf; +} + +const char * dbug_print_rec(const dfield_t* field, ulint n) +{ + rec_printer r(field, n); + strmake(dbug_print_buf, r.str().c_str(), sizeof(dbug_print_buf) - 1); + return dbug_print_buf; +} + +const char * dbug_print_rec(const rec_t* rec, dict_index_t* index) +{ + rec_offs offsets_[REC_OFFS_NORMAL_SIZE]; + rec_offs* offsets = offsets_; + rec_offs_init(offsets_); + mem_heap_t* tmp_heap = NULL; + offsets = rec_get_offsets(rec, index, offsets, index->n_core_fields, + ULINT_UNDEFINED, &tmp_heap); + rec_printer r(rec, offsets); + strmake(dbug_print_buf, r.str().c_str(), sizeof(dbug_print_buf) - 1); + return dbug_print_buf; +} +#endif /* !DBUG_OFF */ + +#endif /* !UNIV_INNOCHECKSUM */ diff --git a/storage/innobase/ut/ut0vec.cc b/storage/innobase/ut/ut0vec.cc new file mode 100644 index 00000000..c9262bc9 --- /dev/null +++ b/storage/innobase/ut/ut0vec.cc @@ -0,0 +1,73 @@ +/***************************************************************************** + +Copyright (c) 2006, 2016, Oracle and/or its affiliates. All Rights Reserved. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +/*******************************************************************//** +@file ut/ut0vec.cc +A vector of pointers to data items + +Created 4/6/2006 Osku Salerma +************************************************************************/ + +#include "ut0vec.h" +#include "mem0mem.h" + +/******************************************************************** +Create a new vector with the given initial size. */ +ib_vector_t* +ib_vector_create( +/*=============*/ + /* out: vector */ + ib_alloc_t* allocator, /* in: vector allocator */ + ulint sizeof_value, /* in: size of data item */ + ulint size) /* in: initial size */ +{ + ib_vector_t* vec; + + ut_a(size > 0); + + vec = static_cast<ib_vector_t*>( + allocator->mem_malloc(allocator, sizeof(*vec))); + + vec->used = 0; + vec->total = size; + vec->allocator = allocator; + vec->sizeof_value = sizeof_value; + + vec->data = static_cast<void*>( + allocator->mem_malloc(allocator, vec->sizeof_value * size)); + + return(vec); +} + +/******************************************************************** +Resize the vector, currently the vector can only grow and we +expand the number of elements it can hold by 2 times. */ +void +ib_vector_resize( +/*=============*/ + ib_vector_t* vec) /* in: vector */ +{ + ulint new_total = vec->total * 2; + ulint old_size = vec->used * vec->sizeof_value; + ulint new_size = new_total * vec->sizeof_value; + + vec->data = static_cast<void*>(vec->allocator->mem_resize( + vec->allocator, vec->data, old_size, new_size)); + + vec->total = new_total; +} diff --git a/storage/innobase/ut/ut0wqueue.cc b/storage/innobase/ut/ut0wqueue.cc new file mode 100644 index 00000000..53bb0c8b --- /dev/null +++ b/storage/innobase/ut/ut0wqueue.cc @@ -0,0 +1,133 @@ +/***************************************************************************** + +Copyright (c) 2006, 2015, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2019, 2020, MariaDB Corporation. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +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 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 Street, Fifth Floor, Boston, MA 02110-1335 USA + +*****************************************************************************/ + +#include "ut0list.h" +#include "mem0mem.h" +#include "ut0wqueue.h" + +/*******************************************************************//** +@file ut/ut0wqueue.cc +A work queue + +Created 4/26/2006 Osku Salerma +************************************************************************/ + +/****************************************************************//** +Create a new work queue. +@return work queue */ +ib_wqueue_t* +ib_wqueue_create(void) +/*===================*/ +{ + ib_wqueue_t* wq = static_cast<ib_wqueue_t*>( + ut_malloc_nokey(sizeof(*wq))); + + /* Function ib_wqueue_create() has not been used anywhere, + not necessary to instrument this mutex */ + + mutex_create(LATCH_ID_WORK_QUEUE, &wq->mutex); + + wq->items = ib_list_create(); + + return(wq); +} + +/****************************************************************//** +Free a work queue. */ +void +ib_wqueue_free( +/*===========*/ + ib_wqueue_t* wq) /*!< in: work queue */ +{ + mutex_free(&wq->mutex); + ib_list_free(wq->items); + + ut_free(wq); +} + +/** Add a work item to the queue. +@param[in,out] wq work queue +@param[in] item work item +@param[in,out] heap memory heap to use for allocating list node +@param[in] wq_locked work queue mutex locked */ +void +ib_wqueue_add(ib_wqueue_t* wq, void* item, mem_heap_t* heap, bool wq_locked) +{ + if (!wq_locked) { + mutex_enter(&wq->mutex); + } + + ib_list_add_last(wq->items, item, heap); + + if (!wq_locked) { + mutex_exit(&wq->mutex); + } +} + +/******************************************************************** +Return first item on work queue or NULL if queue is empty +@return work item or NULL */ +void* +ib_wqueue_nowait( +/*=============*/ + ib_wqueue_t* wq) /*<! in: work queue */ +{ + ib_list_node_t* node = NULL; + + mutex_enter(&wq->mutex); + + if(!ib_list_is_empty(wq->items)) { + node = ib_list_get_first(wq->items); + + if (node) { + ib_list_remove(wq->items, node); + } + } + + mutex_exit(&wq->mutex); + + return (node ? node->data : NULL); +} +/** Check if queue is empty. +@param wq wait queue +@return whether the queue is empty */ +bool ib_wqueue_is_empty(ib_wqueue_t* wq) +{ + mutex_enter(&wq->mutex); + bool is_empty = ib_list_is_empty(wq->items); + mutex_exit(&wq->mutex); + return is_empty; +} + +/******************************************************************** +Get number of items on queue. +@return number of items on queue */ +ulint +ib_wqueue_len( +/*==========*/ + ib_wqueue_t* wq) /*<! in: work queue */ +{ + ulint len = 0; + + mutex_enter(&wq->mutex); + len = ib_list_len(wq->items); + mutex_exit(&wq->mutex); + + return(len); +} |