diff options
Diffstat (limited to 'storage/innodb_plugin/ha')
| -rw-r--r-- | storage/innodb_plugin/ha/ha0ha.c | 441 | ||||
| -rw-r--r-- | storage/innodb_plugin/ha/ha0storage.c | 184 | ||||
| -rw-r--r-- | storage/innodb_plugin/ha/hash0hash.c | 174 |
3 files changed, 799 insertions, 0 deletions
diff --git a/storage/innodb_plugin/ha/ha0ha.c b/storage/innodb_plugin/ha/ha0ha.c new file mode 100644 index 00000000000..cb5e541b55d --- /dev/null +++ b/storage/innodb_plugin/ha/ha0ha.c @@ -0,0 +1,441 @@ +/***************************************************************************** + +Copyright (c) 1994, 2009, Innobase Oy. 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., 59 Temple +Place, Suite 330, Boston, MA 02111-1307 USA + +*****************************************************************************/ + +/********************************************************************//** +@file ha/ha0ha.c +The hash table with external chains + +Created 8/22/1994 Heikki Tuuri +*************************************************************************/ + +#include "ha0ha.h" +#ifdef UNIV_NONINL +#include "ha0ha.ic" +#endif + +#ifdef UNIV_DEBUG +# include "buf0buf.h" +#endif /* UNIV_DEBUG */ +#ifdef UNIV_SYNC_DEBUG +# include "btr0sea.h" +#endif /* UNIV_SYNC_DEBUG */ +#include "page0page.h" + +/*************************************************************//** +Creates a hash table with at least n array cells. The actual number +of cells is chosen to be a prime number slightly bigger than n. +@return own: created table */ +UNIV_INTERN +hash_table_t* +ha_create_func( +/*===========*/ + ulint n, /*!< in: number of array cells */ +#ifdef UNIV_SYNC_DEBUG + ulint mutex_level, /*!< in: level of the mutexes in the latching + order: this is used in the debug version */ +#endif /* UNIV_SYNC_DEBUG */ + ulint n_mutexes) /*!< in: number of mutexes to protect the + hash table: must be a power of 2, or 0 */ +{ + hash_table_t* table; +#ifndef UNIV_HOTBACKUP + ulint i; +#endif /* !UNIV_HOTBACKUP */ + + ut_ad(ut_is_2pow(n_mutexes)); + table = hash_create(n); + +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG +# ifndef UNIV_HOTBACKUP + table->adaptive = TRUE; +# endif /* !UNIV_HOTBACKUP */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail, + but in practise it never should in this case, hence the asserts. */ + + if (n_mutexes == 0) { + table->heap = mem_heap_create_in_btr_search( + ut_min(4096, MEM_MAX_ALLOC_IN_BUF)); + ut_a(table->heap); + + return(table); + } + +#ifndef UNIV_HOTBACKUP + hash_create_mutexes(table, n_mutexes, mutex_level); + + table->heaps = mem_alloc(n_mutexes * sizeof(void*)); + + for (i = 0; i < n_mutexes; i++) { + table->heaps[i] = mem_heap_create_in_btr_search(4096); + ut_a(table->heaps[i]); + } +#endif /* !UNIV_HOTBACKUP */ + + return(table); +} + +/*************************************************************//** +Empties a hash table and frees the memory heaps. */ +UNIV_INTERN +void +ha_clear( +/*=====*/ + hash_table_t* table) /*!< in, own: hash table */ +{ + ulint i; + ulint n; + +#ifdef UNIV_SYNC_DEBUG + ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EXCLUSIVE)); +#endif /* UNIV_SYNC_DEBUG */ + +#ifndef UNIV_HOTBACKUP + /* Free the memory heaps. */ + n = table->n_mutexes; + + for (i = 0; i < n; i++) { + mem_heap_free(table->heaps[i]); + } +#endif /* !UNIV_HOTBACKUP */ + + /* Clear the hash table. */ + n = hash_get_n_cells(table); + + for (i = 0; i < n; i++) { + hash_get_nth_cell(table, i)->node = NULL; + } +} + +/*************************************************************//** +Inserts an entry into a hash table. If an entry with the same fold number +is found, its node is updated to point to the new data, and no new node +is inserted. +@return TRUE if succeed, FALSE if no more memory could be allocated */ +UNIV_INTERN +ibool +ha_insert_for_fold_func( +/*====================*/ + hash_table_t* table, /*!< in: hash table */ + ulint fold, /*!< in: folded value of data; if a node with + the same fold value already exists, it is + updated to point to the same data, and no new + node is created! */ +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + buf_block_t* block, /*!< in: buffer block containing the data */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + void* data) /*!< in: data, must not be NULL */ +{ + hash_cell_t* cell; + ha_node_t* node; + ha_node_t* prev_node; + ulint hash; + + ut_ad(table && data); +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + ut_a(block->frame == page_align(data)); +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + ASSERT_HASH_MUTEX_OWN(table, fold); + + hash = hash_calc_hash(fold, table); + + cell = hash_get_nth_cell(table, hash); + + prev_node = cell->node; + + while (prev_node != NULL) { + if (prev_node->fold == fold) { +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG +# ifndef UNIV_HOTBACKUP + if (table->adaptive) { + buf_block_t* prev_block = prev_node->block; + ut_a(prev_block->frame + == page_align(prev_node->data)); + ut_a(prev_block->n_pointers > 0); + prev_block->n_pointers--; + block->n_pointers++; + } +# endif /* !UNIV_HOTBACKUP */ + + prev_node->block = block; +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + prev_node->data = data; + + return(TRUE); + } + + prev_node = prev_node->next; + } + + /* We have to allocate a new chain node */ + + node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t)); + + if (node == NULL) { + /* It was a btr search type memory heap and at the moment + no more memory could be allocated: return */ + + ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH); + + return(FALSE); + } + + ha_node_set_data(node, block, data); + +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG +# ifndef UNIV_HOTBACKUP + if (table->adaptive) { + block->n_pointers++; + } +# endif /* !UNIV_HOTBACKUP */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + + node->fold = fold; + + node->next = NULL; + + prev_node = cell->node; + + if (prev_node == NULL) { + + cell->node = node; + + return(TRUE); + } + + while (prev_node->next != NULL) { + + prev_node = prev_node->next; + } + + prev_node->next = node; + + return(TRUE); +} + +/***********************************************************//** +Deletes a hash node. */ +UNIV_INTERN +void +ha_delete_hash_node( +/*================*/ + hash_table_t* table, /*!< in: hash table */ + ha_node_t* del_node) /*!< in: node to be deleted */ +{ +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG +# ifndef UNIV_HOTBACKUP + if (table->adaptive) { + ut_a(del_node->block->frame = page_align(del_node->data)); + ut_a(del_node->block->n_pointers > 0); + del_node->block->n_pointers--; + } +# endif /* !UNIV_HOTBACKUP */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + + HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node); +} + +/*********************************************************//** +Looks for an element when we know the pointer to the data, and updates +the pointer to data, if found. */ +UNIV_INTERN +void +ha_search_and_update_if_found_func( +/*===============================*/ + hash_table_t* table, /*!< in/out: hash table */ + ulint fold, /*!< in: folded value of the searched data */ + void* data, /*!< in: pointer to the data */ +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + buf_block_t* new_block,/*!< in: block containing new_data */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + void* new_data)/*!< in: new pointer to the data */ +{ + ha_node_t* node; + + ASSERT_HASH_MUTEX_OWN(table, fold); +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + ut_a(new_block->frame == page_align(new_data)); +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + + node = ha_search_with_data(table, fold, data); + + if (node) { +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG +# ifndef UNIV_HOTBACKUP + if (table->adaptive) { + ut_a(node->block->n_pointers > 0); + node->block->n_pointers--; + new_block->n_pointers++; + } +# endif /* !UNIV_HOTBACKUP */ + + node->block = new_block; +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + node->data = new_data; + } +} + +#ifndef UNIV_HOTBACKUP +/*****************************************************************//** +Removes from the chain determined by fold all nodes whose data pointer +points to the page given. */ +UNIV_INTERN +void +ha_remove_all_nodes_to_page( +/*========================*/ + hash_table_t* table, /*!< in: hash table */ + ulint fold, /*!< in: fold value */ + const page_t* page) /*!< in: buffer page */ +{ + ha_node_t* node; + + ASSERT_HASH_MUTEX_OWN(table, fold); + + node = ha_chain_get_first(table, fold); + + while (node) { + if (page_align(ha_node_get_data(node)) == page) { + + /* Remove the hash node */ + + ha_delete_hash_node(table, node); + + /* Start again from the first node in the chain + because the deletion may compact the heap of + nodes and move other nodes! */ + + node = ha_chain_get_first(table, fold); + } else { + node = ha_chain_get_next(node); + } + } +#ifdef UNIV_DEBUG + /* Check that all nodes really got deleted */ + + node = ha_chain_get_first(table, fold); + + while (node) { + ut_a(page_align(ha_node_get_data(node)) != page); + + node = ha_chain_get_next(node); + } +#endif +} + +/*************************************************************//** +Validates a given range of the cells in hash table. +@return TRUE if ok */ +UNIV_INTERN +ibool +ha_validate( +/*========*/ + hash_table_t* table, /*!< in: hash table */ + ulint start_index, /*!< in: start index */ + ulint end_index) /*!< in: end index */ +{ + hash_cell_t* cell; + ha_node_t* node; + ibool ok = TRUE; + ulint i; + + ut_a(start_index <= end_index); + ut_a(start_index < hash_get_n_cells(table)); + ut_a(end_index < hash_get_n_cells(table)); + + for (i = start_index; i <= end_index; i++) { + + cell = hash_get_nth_cell(table, i); + + node = cell->node; + + while (node) { + if (hash_calc_hash(node->fold, table) != i) { + ut_print_timestamp(stderr); + fprintf(stderr, + "InnoDB: Error: hash table node" + " fold value %lu does not\n" + "InnoDB: match the cell number %lu.\n", + (ulong) node->fold, (ulong) i); + + ok = FALSE; + } + + node = node->next; + } + } + + return(ok); +} + +/*************************************************************//** +Prints info of a hash table. */ +UNIV_INTERN +void +ha_print_info( +/*==========*/ + FILE* file, /*!< in: file where to print */ + hash_table_t* table) /*!< in: hash table */ +{ +#ifdef UNIV_DEBUG +/* Some of the code here is disabled for performance reasons in production +builds, see http://bugs.mysql.com/36941 */ +#define PRINT_USED_CELLS +#endif /* UNIV_DEBUG */ + +#ifdef PRINT_USED_CELLS + hash_cell_t* cell; + ulint cells = 0; + ulint i; +#endif /* PRINT_USED_CELLS */ + ulint n_bufs; + +#ifdef PRINT_USED_CELLS + for (i = 0; i < hash_get_n_cells(table); i++) { + + cell = hash_get_nth_cell(table, i); + + if (cell->node) { + + cells++; + } + } +#endif /* PRINT_USED_CELLS */ + + fprintf(file, "Hash table size %lu", + (ulong) hash_get_n_cells(table)); + +#ifdef PRINT_USED_CELLS + fprintf(file, ", used cells %lu", (ulong) cells); +#endif /* PRINT_USED_CELLS */ + + if (table->heaps == NULL && table->heap != NULL) { + + /* This calculation is intended for the adaptive hash + index: how many buffer frames we have reserved? */ + + n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1; + + if (table->heap->free_block) { + n_bufs++; + } + + fprintf(file, ", node heap has %lu buffer(s)\n", + (ulong) n_bufs); + } +} +#endif /* !UNIV_HOTBACKUP */ diff --git a/storage/innodb_plugin/ha/ha0storage.c b/storage/innodb_plugin/ha/ha0storage.c new file mode 100644 index 00000000000..698e34f1166 --- /dev/null +++ b/storage/innodb_plugin/ha/ha0storage.c @@ -0,0 +1,184 @@ +/***************************************************************************** + +Copyright (c) 2007, 2009, Innobase Oy. 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., 59 Temple +Place, Suite 330, Boston, MA 02111-1307 USA + +*****************************************************************************/ + +/**************************************************//** +@file ha/ha0storage.c +Hash storage. +Provides a data structure that stores chunks of data in +its own storage, avoiding duplicates. + +Created September 22, 2007 Vasil Dimov +*******************************************************/ + +#include "univ.i" +#include "ha0storage.h" +#include "hash0hash.h" +#include "mem0mem.h" +#include "ut0rnd.h" + +#ifdef UNIV_NONINL +#include "ha0storage.ic" +#endif + +/*******************************************************************//** +Retrieves a data from a storage. If it is present, a pointer to the +stored copy of data is returned, otherwise NULL is returned. */ +static +const void* +ha_storage_get( +/*===========*/ + ha_storage_t* storage, /*!< in: hash storage */ + const void* data, /*!< in: data to check for */ + ulint data_len) /*!< in: data length */ +{ + ha_storage_node_t* node; + ulint fold; + + /* avoid repetitive calls to ut_fold_binary() in the HASH_SEARCH + macro */ + fold = ut_fold_binary(data, data_len); + +#define IS_FOUND \ + node->data_len == data_len && memcmp(node->data, data, data_len) == 0 + + HASH_SEARCH( + next, /* node->"next" */ + storage->hash, /* the hash table */ + fold, /* key */ + ha_storage_node_t*, /* type of node->next */ + node, /* auxiliary variable */ + , /* assertion */ + IS_FOUND); /* search criteria */ + + if (node == NULL) { + + return(NULL); + } + /* else */ + + return(node->data); +} + +/*******************************************************************//** +Copies data into the storage and returns a pointer to the copy. If the +same data chunk is already present, then pointer to it is returned. +Data chunks are considered to be equal if len1 == len2 and +memcmp(data1, data2, len1) == 0. If "data" is not present (and thus +data_len bytes need to be allocated) and the size of storage is going to +become more than "memlim" then "data" is not added and NULL is returned. +To disable this behavior "memlim" can be set to 0, which stands for +"no limit". */ +UNIV_INTERN +const void* +ha_storage_put_memlim( +/*==================*/ + ha_storage_t* storage, /*!< in/out: hash storage */ + const void* data, /*!< in: data to store */ + ulint data_len, /*!< in: data length */ + ulint memlim) /*!< in: memory limit to obey */ +{ + void* raw; + ha_storage_node_t* node; + const void* data_copy; + ulint fold; + + /* check if data chunk is already present */ + data_copy = ha_storage_get(storage, data, data_len); + if (data_copy != NULL) { + + return(data_copy); + } + + /* not present */ + + /* check if we are allowed to allocate data_len bytes */ + if (memlim > 0 + && ha_storage_get_size(storage) + data_len > memlim) { + + return(NULL); + } + + /* we put the auxiliary node struct and the data itself in one + continuous block */ + raw = mem_heap_alloc(storage->heap, + sizeof(ha_storage_node_t) + data_len); + + node = (ha_storage_node_t*) raw; + data_copy = (byte*) raw + sizeof(*node); + + memcpy((byte*) raw + sizeof(*node), data, data_len); + + node->data_len = data_len; + node->data = data_copy; + + /* avoid repetitive calls to ut_fold_binary() in the HASH_INSERT + macro */ + fold = ut_fold_binary(data, data_len); + + HASH_INSERT( + ha_storage_node_t, /* type used in the hash chain */ + next, /* node->"next" */ + storage->hash, /* the hash table */ + fold, /* key */ + node); /* add this data to the hash */ + + /* the output should not be changed because it will spoil the + hash table */ + return(data_copy); +} + +#ifdef UNIV_COMPILE_TEST_FUNCS + +void +test_ha_storage() +{ + ha_storage_t* storage; + char buf[1024]; + int i; + const void* stored[256]; + const void* p; + + storage = ha_storage_create(0, 0); + + for (i = 0; i < 256; i++) { + + memset(buf, i, sizeof(buf)); + stored[i] = ha_storage_put(storage, buf, sizeof(buf)); + } + + //ha_storage_empty(&storage); + + for (i = 255; i >= 0; i--) { + + memset(buf, i, sizeof(buf)); + p = ha_storage_put(storage, buf, sizeof(buf)); + + if (p != stored[i]) { + + fprintf(stderr, "ha_storage_put() returned %p " + "instead of %p, i=%d\n", p, stored[i], i); + return; + } + } + + fprintf(stderr, "all ok\n"); + + ha_storage_free(storage); +} + +#endif /* UNIV_COMPILE_TEST_FUNCS */ diff --git a/storage/innodb_plugin/ha/hash0hash.c b/storage/innodb_plugin/ha/hash0hash.c new file mode 100644 index 00000000000..2800d7793f8 --- /dev/null +++ b/storage/innodb_plugin/ha/hash0hash.c @@ -0,0 +1,174 @@ +/***************************************************************************** + +Copyright (c) 1997, 2009, Innobase Oy. 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., 59 Temple +Place, Suite 330, Boston, MA 02111-1307 USA + +*****************************************************************************/ + +/**************************************************//** +@file ha/hash0hash.c +The simple hash table utility + +Created 5/20/1997 Heikki Tuuri +*******************************************************/ + +#include "hash0hash.h" +#ifdef UNIV_NONINL +#include "hash0hash.ic" +#endif + +#include "mem0mem.h" + +#ifndef UNIV_HOTBACKUP +/************************************************************//** +Reserves the mutex for a fold value in a hash table. */ +UNIV_INTERN +void +hash_mutex_enter( +/*=============*/ + hash_table_t* table, /*!< in: hash table */ + ulint fold) /*!< in: fold */ +{ + mutex_enter(hash_get_mutex(table, fold)); +} + +/************************************************************//** +Releases the mutex for a fold value in a hash table. */ +UNIV_INTERN +void +hash_mutex_exit( +/*============*/ + hash_table_t* table, /*!< in: hash table */ + ulint fold) /*!< in: fold */ +{ + mutex_exit(hash_get_mutex(table, fold)); +} + +/************************************************************//** +Reserves all the mutexes of a hash table, in an ascending order. */ +UNIV_INTERN +void +hash_mutex_enter_all( +/*=================*/ + hash_table_t* table) /*!< in: hash table */ +{ + ulint i; + + for (i = 0; i < table->n_mutexes; i++) { + + mutex_enter(table->mutexes + i); + } +} + +/************************************************************//** +Releases all the mutexes of a hash table. */ +UNIV_INTERN +void +hash_mutex_exit_all( +/*================*/ + hash_table_t* table) /*!< in: hash table */ +{ + ulint i; + + for (i = 0; i < table->n_mutexes; i++) { + + mutex_exit(table->mutexes + i); + } +} +#endif /* !UNIV_HOTBACKUP */ + +/*************************************************************//** +Creates a hash table with >= n array cells. The actual number of cells is +chosen to be a prime number slightly bigger than n. +@return own: created table */ +UNIV_INTERN +hash_table_t* +hash_create( +/*========*/ + ulint n) /*!< in: number of array cells */ +{ + hash_cell_t* array; + ulint prime; + hash_table_t* table; + + prime = ut_find_prime(n); + + table = mem_alloc(sizeof(hash_table_t)); + + array = ut_malloc(sizeof(hash_cell_t) * prime); + + table->array = array; + table->n_cells = prime; +#ifndef UNIV_HOTBACKUP +# if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + table->adaptive = FALSE; +# endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + table->n_mutexes = 0; + table->mutexes = NULL; + table->heaps = NULL; +#endif /* !UNIV_HOTBACKUP */ + table->heap = NULL; + table->magic_n = HASH_TABLE_MAGIC_N; + + /* Initialize the cell array */ + hash_table_clear(table); + + return(table); +} + +/*************************************************************//** +Frees a hash table. */ +UNIV_INTERN +void +hash_table_free( +/*============*/ + hash_table_t* table) /*!< in, own: hash table */ +{ +#ifndef UNIV_HOTBACKUP + ut_a(table->mutexes == NULL); +#endif /* !UNIV_HOTBACKUP */ + + ut_free(table->array); + mem_free(table); +} + +#ifndef UNIV_HOTBACKUP +/*************************************************************//** +Creates a mutex array to protect a hash table. */ +UNIV_INTERN +void +hash_create_mutexes_func( +/*=====================*/ + hash_table_t* table, /*!< in: hash table */ +#ifdef UNIV_SYNC_DEBUG + ulint sync_level, /*!< in: latching order level of the + mutexes: used in the debug version */ +#endif /* UNIV_SYNC_DEBUG */ + ulint n_mutexes) /*!< in: number of mutexes, must be a + power of 2 */ +{ + ulint i; + + ut_a(n_mutexes > 0); + ut_a(ut_is_2pow(n_mutexes)); + + table->mutexes = mem_alloc(n_mutexes * sizeof(mutex_t)); + + for (i = 0; i < n_mutexes; i++) { + mutex_create(table->mutexes + i, sync_level); + } + + table->n_mutexes = n_mutexes; +} +#endif /* !UNIV_HOTBACKUP */ |