release/src/router/mysql/storage/innodb_plugin/ha/ha0ha.c

   1 /*****************************************************************************
   2
   3 Copyright (c) 1994, 2011, Oracle and/or its affiliates. All Rights Reserved.
   4
   5 This program is free software; you can redistribute it and/or modify it under
   6 the terms of the GNU General Public License as published by the Free Software
   7 Foundation; version 2 of the License.
   8
   9 This program is distributed in the hope that it will be useful, but WITHOUT
  10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  11 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  12
  13 You should have received a copy of the GNU General Public License along with
  14 this program; if not, write to the Free Software Foundation, Inc.,
  15 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  16
  17 *****************************************************************************/
  18
  19 /********************************************************************//**
  20 @file ha/ha0ha.c
  21 The hash table with external chains
  22
  23 Created 8/22/1994 Heikki Tuuri
  24 *************************************************************************/
  25
  26 #include "ha0ha.h"
  27 #ifdef UNIV_NONINL
  28 #include "ha0ha.ic"
  29 #endif
  30
  31 #ifdef UNIV_DEBUG
  32 # include "buf0buf.h"
  33 #endif /* UNIV_DEBUG */
  34 #include "btr0sea.h"
  35 #include "page0page.h"
  36
  37 /*************************************************************//**
  38 Creates a hash table with at least n array cells.  The actual number
  39 of cells is chosen to be a prime number slightly bigger than n.
  40 @return own: created table */
  41 UNIV_INTERN
  42 hash_table_t*
  43 ha_create_func(
  44 /*===========*/
  45         ulint   n,              /*!< in: number of array cells */
  46 #ifdef UNIV_SYNC_DEBUG
  47         ulint   mutex_level,    /*!< in: level of the mutexes in the latching
  48                                 order: this is used in the debug version */
  49 #endif /* UNIV_SYNC_DEBUG */
  50         ulint   n_mutexes)      /*!< in: number of mutexes to protect the
  51                                 hash table: must be a power of 2, or 0 */
  52 {
  53         hash_table_t*   table;
  54 #ifndef UNIV_HOTBACKUP
  55         ulint           i;
  56 #endif /* !UNIV_HOTBACKUP */
  57
  58         ut_ad(ut_is_2pow(n_mutexes));
  59         table = hash_create(n);
  60
  61 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
  62 # ifndef UNIV_HOTBACKUP
  63         table->adaptive = TRUE;
  64 # endif /* !UNIV_HOTBACKUP */
  65 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
  66         /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
  67         but in practise it never should in this case, hence the asserts. */
  68
  69         if (n_mutexes == 0) {
  70                 table->heap = mem_heap_create_in_btr_search(
  71                         ut_min(4096, MEM_MAX_ALLOC_IN_BUF));
  72                 ut_a(table->heap);
  73
  74                 return(table);
  75         }
  76
  77 #ifndef UNIV_HOTBACKUP
  78         hash_create_mutexes(table, n_mutexes, mutex_level);
  79
  80         table->heaps = mem_alloc(n_mutexes * sizeof(void*));
  81
  82         for (i = 0; i < n_mutexes; i++) {
  83                 table->heaps[i] = mem_heap_create_in_btr_search(4096);
  84                 ut_a(table->heaps[i]);
  85         }
  86 #endif /* !UNIV_HOTBACKUP */
  87
  88         return(table);
  89 }
  90
  91 /*************************************************************//**
  92 Inserts an entry into a hash table. If an entry with the same fold number
  93 is found, its node is updated to point to the new data, and no new node
  94 is inserted. If btr_search_enabled is set to FALSE, we will only allow
  95 updating existing nodes, but no new node is allowed to be added.
  96 @return TRUE if succeed, FALSE if no more memory could be allocated */
  97 UNIV_INTERN
  98 ibool
  99 ha_insert_for_fold_func(
 100 /*====================*/
 101         hash_table_t*   table,  /*!< in: hash table */
 102         ulint           fold,   /*!< in: folded value of data; if a node with
 103                                 the same fold value already exists, it is
 104                                 updated to point to the same data, and no new
 105                                 node is created! */
 106 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 107         buf_block_t*    block,  /*!< in: buffer block containing the data */
 108 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 109         const rec_t*    data)   /*!< in: data, must not be NULL */
 110 {
 111         hash_cell_t*    cell;
 112         ha_node_t*      node;
 113         ha_node_t*      prev_node;
 114         ulint           hash;
 115
 116         ut_ad(data);
 117         ut_ad(table);
 118         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 119 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 120         ut_a(block->frame == page_align(data));
 121 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 122 #ifdef UNIV_SYNC_DEBUG
 123         ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
 124 #endif /* UNIV_SYNC_DEBUG */
 125         ASSERT_HASH_MUTEX_OWN(table, fold);
 126         ut_ad(btr_search_enabled);
 127
 128         hash = hash_calc_hash(fold, table);
 129
 130         cell = hash_get_nth_cell(table, hash);
 131
 132         prev_node = cell->node;
 133
 134         while (prev_node != NULL) {
 135                 if (prev_node->fold == fold) {
 136 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 137 # ifndef UNIV_HOTBACKUP
 138                         if (table->adaptive) {
 139                                 buf_block_t* prev_block = prev_node->block;
 140                                 ut_a(prev_block->frame
 141                                      == page_align(prev_node->data));
 142                                 ut_a(prev_block->n_pointers > 0);
 143                                 prev_block->n_pointers--;
 144                                 block->n_pointers++;
 145                         }
 146 # endif /* !UNIV_HOTBACKUP */
 147
 148                         prev_node->block = block;
 149 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 150                         prev_node->data = data;
 151
 152                         return(TRUE);
 153                 }
 154
 155                 prev_node = prev_node->next;
 156         }
 157
 158         /* We have to allocate a new chain node */
 159
 160         node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));
 161
 162         if (node == NULL) {
 163                 /* It was a btr search type memory heap and at the moment
 164                 no more memory could be allocated: return */
 165
 166                 ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
 167
 168                 return(FALSE);
 169         }
 170
 171         ha_node_set_data(node, block, data);
 172
 173 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 174 # ifndef UNIV_HOTBACKUP
 175         if (table->adaptive) {
 176                 block->n_pointers++;
 177         }
 178 # endif /* !UNIV_HOTBACKUP */
 179 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 180
 181         node->fold = fold;
 182
 183         node->next = NULL;
 184
 185         prev_node = cell->node;
 186
 187         if (prev_node == NULL) {
 188
 189                 cell->node = node;
 190
 191                 return(TRUE);
 192         }
 193
 194         while (prev_node->next != NULL) {
 195
 196                 prev_node = prev_node->next;
 197         }
 198
 199         prev_node->next = node;
 200
 201         return(TRUE);
 202 }
 203
 204 /***********************************************************//**
 205 Deletes a hash node. */
 206 UNIV_INTERN
 207 void
 208 ha_delete_hash_node(
 209 /*================*/
 210         hash_table_t*   table,          /*!< in: hash table */
 211         ha_node_t*      del_node)       /*!< in: node to be deleted */
 212 {
 213         ut_ad(table);
 214         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 215 #ifdef UNIV_SYNC_DEBUG
 216         ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
 217 #endif /* UNIV_SYNC_DEBUG */
 218         ut_ad(btr_search_enabled);
 219 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 220 # ifndef UNIV_HOTBACKUP
 221         if (table->adaptive) {
 222                 ut_a(del_node->block->frame = page_align(del_node->data));
 223                 ut_a(del_node->block->n_pointers > 0);
 224                 del_node->block->n_pointers--;
 225         }
 226 # endif /* !UNIV_HOTBACKUP */
 227 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 228
 229         HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
 230 }
 231
 232 /*********************************************************//**
 233 Looks for an element when we know the pointer to the data, and updates
 234 the pointer to data, if found. */
 235 UNIV_INTERN
 236 void
 237 ha_search_and_update_if_found_func(
 238 /*===============================*/
 239         hash_table_t*   table,  /*!< in/out: hash table */
 240         ulint           fold,   /*!< in: folded value of the searched data */
 241         const rec_t*    data,   /*!< in: pointer to the data */
 242 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 243         buf_block_t*    new_block,/*!< in: block containing new_data */
 244 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 245         const rec_t*    new_data)/*!< in: new pointer to the data */
 246 {
 247         ha_node_t*      node;
 248
 249         ut_ad(table);
 250         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 251         ASSERT_HASH_MUTEX_OWN(table, fold);
 252 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 253         ut_a(new_block->frame == page_align(new_data));
 254 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 255 #ifdef UNIV_SYNC_DEBUG
 256         ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
 257 #endif /* UNIV_SYNC_DEBUG */
 258
 259         if (!btr_search_enabled) {
 260                 return;
 261         }
 262
 263         node = ha_search_with_data(table, fold, data);
 264
 265         if (node) {
 266 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 267 # ifndef UNIV_HOTBACKUP
 268                 if (table->adaptive) {
 269                         ut_a(node->block->n_pointers > 0);
 270                         node->block->n_pointers--;
 271                         new_block->n_pointers++;
 272                 }
 273 # endif /* !UNIV_HOTBACKUP */
 274
 275                 node->block = new_block;
 276 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 277                 node->data = new_data;
 278         }
 279 }
 280
 281 #ifndef UNIV_HOTBACKUP
 282 /*****************************************************************//**
 283 Removes from the chain determined by fold all nodes whose data pointer
 284 points to the page given. */
 285 UNIV_INTERN
 286 void
 287 ha_remove_all_nodes_to_page(
 288 /*========================*/
 289         hash_table_t*   table,  /*!< in: hash table */
 290         ulint           fold,   /*!< in: fold value */
 291         const page_t*   page)   /*!< in: buffer page */
 292 {
 293         ha_node_t*      node;
 294
 295         ut_ad(table);
 296         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 297         ASSERT_HASH_MUTEX_OWN(table, fold);
 298 #ifdef UNIV_SYNC_DEBUG
 299         ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
 300 #endif /* UNIV_SYNC_DEBUG */
 301         ut_ad(btr_search_enabled);
 302
 303         node = ha_chain_get_first(table, fold);
 304
 305         while (node) {
 306                 if (page_align(ha_node_get_data(node)) == page) {
 307
 308                         /* Remove the hash node */
 309
 310                         ha_delete_hash_node(table, node);
 311
 312                         /* Start again from the first node in the chain
 313                         because the deletion may compact the heap of
 314                         nodes and move other nodes! */
 315
 316                         node = ha_chain_get_first(table, fold);
 317                 } else {
 318                         node = ha_chain_get_next(node);
 319                 }
 320         }
 321 #ifdef UNIV_DEBUG
 322         /* Check that all nodes really got deleted */
 323
 324         node = ha_chain_get_first(table, fold);
 325
 326         while (node) {
 327                 ut_a(page_align(ha_node_get_data(node)) != page);
 328
 329                 node = ha_chain_get_next(node);
 330         }
 331 #endif
 332 }
 333
 334 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 335 /*************************************************************//**
 336 Validates a given range of the cells in hash table.
 337 @return TRUE if ok */
 338 UNIV_INTERN
 339 ibool
 340 ha_validate(
 341 /*========*/
 342         hash_table_t*   table,          /*!< in: hash table */
 343         ulint           start_index,    /*!< in: start index */
 344         ulint           end_index)      /*!< in: end index */
 345 {
 346         hash_cell_t*    cell;
 347         ha_node_t*      node;
 348         ibool           ok      = TRUE;
 349         ulint           i;
 350
 351         ut_ad(table);
 352         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 353         ut_a(start_index <= end_index);
 354         ut_a(start_index < hash_get_n_cells(table));
 355         ut_a(end_index < hash_get_n_cells(table));
 356
 357         for (i = start_index; i <= end_index; i++) {
 358
 359                 cell = hash_get_nth_cell(table, i);
 360
 361                 node = cell->node;
 362
 363                 while (node) {
 364                         if (hash_calc_hash(node->fold, table) != i) {
 365                                 ut_print_timestamp(stderr);
 366                                 fprintf(stderr,
 367                                         "InnoDB: Error: hash table node"
 368                                         " fold value %lu does not\n"
 369                                         "InnoDB: match the cell number %lu.\n",
 370                                         (ulong) node->fold, (ulong) i);
 371
 372                                 ok = FALSE;
 373                         }
 374
 375                         node = node->next;
 376                 }
 377         }
 378
 379         return(ok);
 380 }
 381 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
 382
 383 /*************************************************************//**
 384 Prints info of a hash table. */
 385 UNIV_INTERN
 386 void
 387 ha_print_info(
 388 /*==========*/
 389         FILE*           file,   /*!< in: file where to print */
 390         hash_table_t*   table)  /*!< in: hash table */
 391 {
 392 #ifdef UNIV_DEBUG
 393 /* Some of the code here is disabled for performance reasons in production
 394 builds, see http://bugs.mysql.com/36941 */
 395 #define PRINT_USED_CELLS
 396 #endif /* UNIV_DEBUG */
 397
 398 #ifdef PRINT_USED_CELLS
 399         hash_cell_t*    cell;
 400         ulint           cells   = 0;
 401         ulint           i;
 402 #endif /* PRINT_USED_CELLS */
 403         ulint           n_bufs;
 404
 405         ut_ad(table);
 406         ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 407 #ifdef PRINT_USED_CELLS
 408         for (i = 0; i < hash_get_n_cells(table); i++) {
 409
 410                 cell = hash_get_nth_cell(table, i);
 411
 412                 if (cell->node) {
 413
 414                         cells++;
 415                 }
 416         }
 417 #endif /* PRINT_USED_CELLS */
 418
 419         fprintf(file, "Hash table size %lu",
 420                 (ulong) hash_get_n_cells(table));
 421
 422 #ifdef PRINT_USED_CELLS
 423         fprintf(file, ", used cells %lu", (ulong) cells);
 424 #endif /* PRINT_USED_CELLS */
 425
 426         if (table->heaps == NULL && table->heap != NULL) {
 427
 428                 /* This calculation is intended for the adaptive hash
 429                 index: how many buffer frames we have reserved? */
 430
 431                 n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
 432
 433                 if (table->heap->free_block) {
 434                         n_bufs++;
 435                 }
 436
 437                 fprintf(file, ", node heap has %lu buffer(s)\n",
 438                         (ulong) n_bufs);
 439         }
 440 }
 441 #endif /* !UNIV_HOTBACKUP */