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