1 /*****************************************************************************
2
3 Copyright (c) 1994, 2021, Oracle and/or its affiliates.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26
27 /********************************************************************//**
28 @file ha/ha0ha.cc
29 The hash table with external chains
30
31 Created 8/22/1994 Heikki Tuuri
32 *************************************************************************/
33
34 #include "ha0ha.h"
35 #ifdef UNIV_NONINL
36 #include "ha0ha.ic"
37 #endif
38
39 #ifndef UNIV_HOTBACKUP
40 #ifdef UNIV_DEBUG
41 # include "buf0buf.h"
42 #endif /* UNIV_DEBUG */
43 # include "btr0sea.h"
44 #include "page0page.h"
45
46 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
47 /** Maximum number of records in a page */
48 static const ulint MAX_N_POINTERS
49 = UNIV_PAGE_SIZE_MAX / REC_N_NEW_EXTRA_BYTES;
50 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
51
52 /*************************************************************//**
53 Creates a hash table with at least n array cells. The actual number
54 of cells is chosen to be a prime number slightly bigger than n.
55 @return own: created table */
56 hash_table_t*
ib_create(ulint n,latch_id_t id,ulint n_sync_obj,ulint type)57 ib_create(
58 /*======*/
59 ulint n, /*!< in: number of array cells */
60 latch_id_t id, /*!< in: latch ID */
61 ulint n_sync_obj,
62 /*!< in: number of mutexes to protect the
63 hash table: must be a power of 2, or 0 */
64 ulint type) /*!< in: type of datastructure for which
65 MEM_HEAP_FOR_PAGE_HASH */
66 {
67 hash_table_t* table;
68
69 ut_a(type == MEM_HEAP_FOR_BTR_SEARCH
70 || type == MEM_HEAP_FOR_PAGE_HASH);
71
72 ut_ad(ut_is_2pow(n_sync_obj));
73 table = hash_create(n);
74
75 /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
76 but in practise it never should in this case, hence the asserts. */
77
78 if (n_sync_obj == 0) {
79 table->heap = mem_heap_create_typed(
80 ut_min(static_cast<ulint>(4096),
81 MEM_MAX_ALLOC_IN_BUF / 2
82 - MEM_BLOCK_HEADER_SIZE - MEM_SPACE_NEEDED(0)),
83 type);
84 ut_a(table->heap);
85
86 return(table);
87 }
88
89 if (type == MEM_HEAP_FOR_PAGE_HASH) {
90 /* We create a hash table protected by rw_locks for
91 buf_pool->page_hash. */
92 hash_create_sync_obj(
93 table, HASH_TABLE_SYNC_RW_LOCK, id, n_sync_obj);
94 } else {
95 hash_create_sync_obj(
96 table, HASH_TABLE_SYNC_MUTEX, id, n_sync_obj);
97 }
98
99 table->heaps = static_cast<mem_heap_t**>(
100 ut_malloc_nokey(n_sync_obj * sizeof(void*)));
101
102 for (ulint i = 0; i < n_sync_obj; i++) {
103 table->heaps[i] = mem_heap_create_typed(
104 ut_min(static_cast<ulint>(4096),
105 MEM_MAX_ALLOC_IN_BUF / 2
106 - MEM_BLOCK_HEADER_SIZE - MEM_SPACE_NEEDED(0)),
107 type);
108 ut_a(table->heaps[i]);
109 }
110
111 return(table);
112 }
113
114 /** Recreate a hash table with at least n array cells. The actual number
115 of cells is chosen to be a prime number slightly bigger than n.
116 The new cells are all cleared. The heaps are recreated.
117 The sync objects are reused.
118 @param[in,out] table hash table to be resuzed (to be freed later)
119 @param[in] n number of array cells
120 @return resized new table */
121 hash_table_t*
ib_recreate(hash_table_t * table,ulint n)122 ib_recreate(
123 hash_table_t* table,
124 ulint n)
125 {
126 /* This function is for only page_hash for now */
127 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
128 ut_ad(table->n_sync_obj > 0);
129
130 hash_table_t* new_table = hash_create(n);
131
132 new_table->type = table->type;
133 new_table->n_sync_obj = table->n_sync_obj;
134 new_table->sync_obj = table->sync_obj;
135
136 for (ulint i = 0; i < table->n_sync_obj; i++) {
137 mem_heap_free(table->heaps[i]);
138 }
139 ut_free(table->heaps);
140
141 new_table->heaps = static_cast<mem_heap_t**>(
142 ut_malloc_nokey(new_table->n_sync_obj * sizeof(void*)));
143
144 for (ulint i = 0; i < new_table->n_sync_obj; i++) {
145 new_table->heaps[i] = mem_heap_create_typed(
146 ut_min(static_cast<ulint>(4096),
147 MEM_MAX_ALLOC_IN_BUF / 2
148 - MEM_BLOCK_HEADER_SIZE - MEM_SPACE_NEEDED(0)),
149 MEM_HEAP_FOR_PAGE_HASH);
150 ut_a(new_table->heaps[i]);
151 }
152
153 return(new_table);
154 }
155
156 /*************************************************************//**
157 Empties a hash table and frees the memory heaps. */
158 void
ha_clear(hash_table_t * table)159 ha_clear(
160 /*=====*/
161 hash_table_t* table) /*!< in, own: hash table */
162 {
163 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
164 ut_ad(!table->adaptive || btr_search_own_all(RW_LOCK_X));
165
166 for (ulint i = 0; i < table->n_sync_obj; i++) {
167 mem_heap_free(table->heaps[i]);
168 }
169
170 ut_free(table->heaps);
171
172 switch (table->type) {
173 case HASH_TABLE_SYNC_MUTEX:
174 for (ulint i = 0; i < table->n_sync_obj; ++i) {
175 mutex_destroy(&table->sync_obj.mutexes[i]);
176 }
177 ut_free(table->sync_obj.mutexes);
178 table->sync_obj.mutexes = NULL;
179 break;
180
181 case HASH_TABLE_SYNC_RW_LOCK:
182 for (ulint i = 0; i < table->n_sync_obj; ++i) {
183 rw_lock_free(&table->sync_obj.rw_locks[i]);
184 }
185
186 ut_free(table->sync_obj.rw_locks);
187 table->sync_obj.rw_locks = NULL;
188 break;
189
190 case HASH_TABLE_SYNC_NONE:
191 /* do nothing */
192 break;
193 }
194
195 table->n_sync_obj = 0;
196 table->type = HASH_TABLE_SYNC_NONE;
197
198
199 /* Clear the hash table. */
200 ulint n = hash_get_n_cells(table);
201
202 for (ulint i = 0; i < n; i++) {
203 hash_get_nth_cell(table, i)->node = NULL;
204 }
205 }
206
207 /*************************************************************//**
208 Inserts an entry into a hash table. If an entry with the same fold number
209 is found, its node is updated to point to the new data, and no new node
210 is inserted. If btr_search_enabled is set to FALSE, we will only allow
211 updating existing nodes, but no new node is allowed to be added.
212 @return TRUE if succeed, FALSE if no more memory could be allocated */
213 ibool
ha_insert_for_fold_func(hash_table_t * table,ulint fold,buf_block_t * block,const rec_t * data)214 ha_insert_for_fold_func(
215 /*====================*/
216 hash_table_t* table, /*!< in: hash table */
217 ulint fold, /*!< in: folded value of data; if a node with
218 the same fold value already exists, it is
219 updated to point to the same data, and no new
220 node is created! */
221 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
222 buf_block_t* block, /*!< in: buffer block containing the data */
223 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
224 const rec_t* data) /*!< in: data, must not be NULL */
225 {
226 hash_cell_t* cell;
227 ha_node_t* node;
228 ha_node_t* prev_node;
229 ulint hash;
230
231 ut_ad(data);
232 ut_ad(table);
233 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
234 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
235 ut_a(block->frame == page_align(data));
236 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
237 hash_assert_can_modify(table, fold);
238 ut_ad(btr_search_enabled);
239
240 hash = hash_calc_hash(fold, table);
241
242 cell = hash_get_nth_cell(table, hash);
243
244 prev_node = static_cast<ha_node_t*>(cell->node);
245
246 while (prev_node != NULL) {
247 if (prev_node->fold == fold) {
248 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
249 if (table->adaptive) {
250 buf_block_t* prev_block = prev_node->block;
251 ut_a(prev_block->frame
252 == page_align(prev_node->data));
253 ut_a(os_atomic_decrement_ulint(
254 &prev_block->n_pointers, 1)
255 < MAX_N_POINTERS);
256 ut_a(os_atomic_increment_ulint(
257 &block->n_pointers, 1)
258 < MAX_N_POINTERS);
259 }
260
261 prev_node->block = block;
262 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
263 prev_node->data = data;
264
265 return(TRUE);
266 }
267
268 prev_node = prev_node->next;
269 }
270
271 /* We have to allocate a new chain node */
272
273 node = static_cast<ha_node_t*>(
274 mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t)));
275
276 if (node == NULL) {
277 /* It was a btr search type memory heap and at the moment
278 no more memory could be allocated: return */
279
280 ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
281
282 return(FALSE);
283 }
284
285 ha_node_set_data(node, block, data);
286
287 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
288 if (table->adaptive) {
289 ut_a(os_atomic_increment_ulint(&block->n_pointers, 1)
290 < MAX_N_POINTERS);
291 }
292 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
293
294 node->fold = fold;
295
296 node->next = NULL;
297
298 prev_node = static_cast<ha_node_t*>(cell->node);
299
300 if (prev_node == NULL) {
301
302 cell->node = node;
303
304 return(TRUE);
305 }
306
307 while (prev_node->next != NULL) {
308
309 prev_node = prev_node->next;
310 }
311
312 prev_node->next = node;
313
314 return(TRUE);
315 }
316
317 #ifdef UNIV_DEBUG
318 /** Verify if latch corresponding to the hash table is x-latched
319 @param[in] table hash table */
320 static
321 void
ha_btr_search_latch_x_locked(const hash_table_t * table)322 ha_btr_search_latch_x_locked(const hash_table_t* table)
323 {
324 ulint i;
325 for (i = 0; i < btr_ahi_parts; ++i) {
326 if (btr_search_sys->hash_tables[i] == table) {
327 break;
328 }
329 }
330
331 ut_ad(i < btr_ahi_parts);
332 ut_ad(rw_lock_own(btr_search_latches[i], RW_LOCK_X));
333 }
334 #endif /* UNIV_DEBUG */
335
336 /***********************************************************//**
337 Deletes a hash node. */
338 void
ha_delete_hash_node(hash_table_t * table,ha_node_t * del_node)339 ha_delete_hash_node(
340 /*================*/
341 hash_table_t* table, /*!< in: hash table */
342 ha_node_t* del_node) /*!< in: node to be deleted */
343 {
344 ut_ad(table);
345 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
346 ut_d(ha_btr_search_latch_x_locked(table));
347 ut_ad(btr_search_enabled);
348 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
349 if (table->adaptive) {
350 ut_a(del_node->block->frame = page_align(del_node->data));
351 ut_a(os_atomic_decrement_ulint(&del_node->block->n_pointers, 1)
352 < MAX_N_POINTERS);
353 }
354 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
355
356 HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
357 }
358
359 /*********************************************************//**
360 Looks for an element when we know the pointer to the data, and updates
361 the pointer to data, if found.
362 @return TRUE if found */
363 ibool
ha_search_and_update_if_found_func(hash_table_t * table,ulint fold,const rec_t * data,buf_block_t * new_block,const rec_t * new_data)364 ha_search_and_update_if_found_func(
365 /*===============================*/
366 hash_table_t* table, /*!< in/out: hash table */
367 ulint fold, /*!< in: folded value of the searched data */
368 const rec_t* data, /*!< in: pointer to the data */
369 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
370 buf_block_t* new_block,/*!< in: block containing new_data */
371 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
372 const rec_t* new_data)/*!< in: new pointer to the data */
373 {
374 ha_node_t* node;
375
376 ut_ad(table);
377 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
378 hash_assert_can_modify(table, fold);
379 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
380 ut_a(new_block->frame == page_align(new_data));
381 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
382
383 ut_d(ha_btr_search_latch_x_locked(table));
384
385 if (!btr_search_enabled) {
386 return(FALSE);
387 }
388
389 node = ha_search_with_data(table, fold, data);
390
391 if (node) {
392 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
393 if (table->adaptive) {
394 ut_a(os_atomic_decrement_ulint(&node->block->n_pointers, 1)
395 < MAX_N_POINTERS);
396 ut_a(os_atomic_increment_ulint(&new_block->n_pointers, 1)
397 < MAX_N_POINTERS);
398 }
399
400 node->block = new_block;
401 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
402 node->data = new_data;
403
404 return(TRUE);
405 }
406
407 return(FALSE);
408 }
409
410 /*****************************************************************//**
411 Removes from the chain determined by fold all nodes whose data pointer
412 points to the page given. */
413 void
ha_remove_all_nodes_to_page(hash_table_t * table,ulint fold,const page_t * page)414 ha_remove_all_nodes_to_page(
415 /*========================*/
416 hash_table_t* table, /*!< in: hash table */
417 ulint fold, /*!< in: fold value */
418 const page_t* page) /*!< in: buffer page */
419 {
420 ha_node_t* node;
421
422 ut_ad(table);
423 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
424 hash_assert_can_modify(table, fold);
425 ut_ad(btr_search_enabled);
426
427 node = ha_chain_get_first(table, fold);
428
429 while (node) {
430 if (page_align(ha_node_get_data(node)) == page) {
431
432 /* Remove the hash node */
433
434 ha_delete_hash_node(table, node);
435
436 /* Start again from the first node in the chain
437 because the deletion may compact the heap of
438 nodes and move other nodes! */
439
440 node = ha_chain_get_first(table, fold);
441 } else {
442 node = ha_chain_get_next(node);
443 }
444 }
445 #ifdef UNIV_DEBUG
446 /* Check that all nodes really got deleted */
447
448 node = ha_chain_get_first(table, fold);
449
450 while (node) {
451 ut_a(page_align(ha_node_get_data(node)) != page);
452
453 node = ha_chain_get_next(node);
454 }
455 #endif /* UNIV_DEBUG */
456 }
457
458 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
459 /*************************************************************//**
460 Validates a given range of the cells in hash table.
461 @return TRUE if ok */
462 ibool
ha_validate(hash_table_t * table,ulint start_index,ulint end_index)463 ha_validate(
464 /*========*/
465 hash_table_t* table, /*!< in: hash table */
466 ulint start_index, /*!< in: start index */
467 ulint end_index) /*!< in: end index */
468 {
469 ibool ok = TRUE;
470 ulint i;
471
472 ut_ad(table);
473 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
474 ut_a(start_index <= end_index);
475 ut_a(start_index < hash_get_n_cells(table));
476 ut_a(end_index < hash_get_n_cells(table));
477
478 for (i = start_index; i <= end_index; i++) {
479 ha_node_t* node;
480 hash_cell_t* cell;
481
482 cell = hash_get_nth_cell(table, i);
483
484 for (node = static_cast<ha_node_t*>(cell->node);
485 node != 0;
486 node = node->next) {
487
488 if (hash_calc_hash(node->fold, table) != i) {
489 ib::error() << "Hash table node fold value "
490 << node->fold << " does not match the"
491 " cell number " << i << ".";
492
493 ok = FALSE;
494 }
495 }
496 }
497
498 return(ok);
499 }
500 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
501
502 /*************************************************************//**
503 Prints info of a hash table. */
504 void
ha_print_info(FILE * file,hash_table_t * table)505 ha_print_info(
506 /*==========*/
507 FILE* file, /*!< in: file where to print */
508 hash_table_t* table) /*!< in: hash table */
509 {
510 #ifdef UNIV_DEBUG
511 /* Some of the code here is disabled for performance reasons in production
512 builds, see http://bugs.mysql.com/36941 */
513 #define PRINT_USED_CELLS
514 #endif /* UNIV_DEBUG */
515
516 #ifdef PRINT_USED_CELLS
517 hash_cell_t* cell;
518 ulint cells = 0;
519 ulint i;
520 #endif /* PRINT_USED_CELLS */
521 ulint n_bufs;
522
523 ut_ad(table);
524 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
525 #ifdef PRINT_USED_CELLS
526 for (i = 0; i < hash_get_n_cells(table); i++) {
527
528 cell = hash_get_nth_cell(table, i);
529
530 if (cell->node) {
531
532 cells++;
533 }
534 }
535 #endif /* PRINT_USED_CELLS */
536
537 fprintf(file, "Hash table size %lu",
538 (ulong) hash_get_n_cells(table));
539
540 #ifdef PRINT_USED_CELLS
541 fprintf(file, ", used cells %lu", (ulong) cells);
542 #endif /* PRINT_USED_CELLS */
543
544 if (table->heaps == NULL && table->heap != NULL) {
545
546 /* This calculation is intended for the adaptive hash
547 index: how many buffer frames we have reserved? */
548
549 n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
550
551 if (table->heap->free_block) {
552 n_bufs++;
553 }
554
555 fprintf(file, ", node heap has %lu buffer(s)\n",
556 (ulong) n_bufs);
557 }
558 }
559 #endif /* !UNIV_HOTBACKUP */
560