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
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 /*************************************************************//**
47 Creates a hash table with at least n array cells. The actual number
48 of cells is chosen to be a prime number slightly bigger than n.
49 @return own: created table */
50 UNIV_INTERN
51 hash_table_t*
ha_create_func(ulint n,ulint sync_level,ulint n_sync_obj,ulint type)52 ha_create_func(
53 /*===========*/
54 ulint n, /*!< in: number of array cells */
55 #ifdef UNIV_SYNC_DEBUG
56 ulint sync_level, /*!< in: level of the mutexes or rw_locks
57 in the latching order: this is used in the
58 debug version */
59 #endif /* UNIV_SYNC_DEBUG */
60 ulint n_sync_obj, /*!< in: number of mutexes or rw_locks
61 to protect the hash table: must be a
62 power of 2, or 0 */
63 ulint type) /*!< in: type of datastructure for which
64 the memory heap is going to be used e.g.:
65 MEM_HEAP_FOR_BTR_SEARCH or
66 MEM_HEAP_FOR_PAGE_HASH */
67 {
68 hash_table_t* table;
69 ulint i;
70
71 ut_a(type == MEM_HEAP_FOR_BTR_SEARCH
72 || type == MEM_HEAP_FOR_PAGE_HASH);
73
74 ut_ad(ut_is_2pow(n_sync_obj));
75 table = hash_create(n);
76
77 /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
78 but in practise it never should in this case, hence the asserts. */
79
80 if (n_sync_obj == 0) {
81 table->heap = mem_heap_create_typed(
82 ut_min(4096, MEM_MAX_ALLOC_IN_BUF), type);
83 ut_a(table->heap);
84
85 return(table);
86 }
87
88 if (type == MEM_HEAP_FOR_PAGE_HASH) {
89 /* We create a hash table protected by rw_locks for
90 buf_pool->page_hash. */
91 hash_create_sync_obj(table, HASH_TABLE_SYNC_RW_LOCK,
92 n_sync_obj, sync_level);
93 } else {
94 hash_create_sync_obj(table, HASH_TABLE_SYNC_MUTEX,
95 n_sync_obj, sync_level);
96 }
97
98 table->heaps = static_cast<mem_heap_t**>(
99 mem_alloc(n_sync_obj * sizeof(void*)));
100
101 for (i = 0; i < n_sync_obj; i++) {
102 table->heaps[i] = mem_heap_create_typed(4096, type);
103 ut_a(table->heaps[i]);
104 }
105
106 return(table);
107 }
108
109 /*************************************************************//**
110 Empties a hash table and frees the memory heaps. */
111 UNIV_INTERN
112 void
ha_clear(hash_table_t * table)113 ha_clear(
114 /*=====*/
115 hash_table_t* table) /*!< in, own: hash table */
116 {
117 ulint i;
118 ulint n;
119
120 ut_ad(table);
121 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
122 #ifdef UNIV_SYNC_DEBUG
123 ut_ad(!table->adaptive
124 || rw_lock_own(&btr_search_latch, RW_LOCK_EXCLUSIVE));
125 #endif /* UNIV_SYNC_DEBUG */
126
127 /* Free the memory heaps. */
128 n = table->n_sync_obj;
129
130 for (i = 0; i < n; i++) {
131 mem_heap_free(table->heaps[i]);
132 }
133
134 if (table->heaps) {
135 mem_free(table->heaps);
136 }
137
138 switch (table->type) {
139 case HASH_TABLE_SYNC_MUTEX:
140 mem_free(table->sync_obj.mutexes);
141 table->sync_obj.mutexes = NULL;
142 break;
143
144 case HASH_TABLE_SYNC_RW_LOCK:
145 mem_free(table->sync_obj.rw_locks);
146 table->sync_obj.rw_locks = NULL;
147 break;
148
149 case HASH_TABLE_SYNC_NONE:
150 /* do nothing */
151 break;
152 }
153
154 table->n_sync_obj = 0;
155 table->type = HASH_TABLE_SYNC_NONE;
156
157
158 /* Clear the hash table. */
159 n = hash_get_n_cells(table);
160
161 for (i = 0; i < n; i++) {
162 hash_get_nth_cell(table, i)->node = NULL;
163 }
164 }
165
166 /*************************************************************//**
167 Inserts an entry into a hash table. If an entry with the same fold number
168 is found, its node is updated to point to the new data, and no new node
169 is inserted. If btr_search_enabled is set to FALSE, we will only allow
170 updating existing nodes, but no new node is allowed to be added.
171 @return TRUE if succeed, FALSE if no more memory could be allocated */
172 UNIV_INTERN
173 ibool
ha_insert_for_fold_func(hash_table_t * table,ulint fold,buf_block_t * block,const rec_t * data)174 ha_insert_for_fold_func(
175 /*====================*/
176 hash_table_t* table, /*!< in: hash table */
177 ulint fold, /*!< in: folded value of data; if a node with
178 the same fold value already exists, it is
179 updated to point to the same data, and no new
180 node is created! */
181 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
182 buf_block_t* block, /*!< in: buffer block containing the data */
183 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
184 const rec_t* data) /*!< in: data, must not be NULL */
185 {
186 hash_cell_t* cell;
187 ha_node_t* node;
188 ha_node_t* prev_node;
189 ulint hash;
190
191 ut_ad(data);
192 ut_ad(table);
193 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
194 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
195 ut_a(block->frame == page_align(data));
196 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
197 hash_assert_can_modify(table, fold);
198 ut_ad(btr_search_enabled);
199
200 hash = hash_calc_hash(fold, table);
201
202 cell = hash_get_nth_cell(table, hash);
203
204 prev_node = static_cast<ha_node_t*>(cell->node);
205
206 while (prev_node != NULL) {
207 if (prev_node->fold == fold) {
208 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
209 if (table->adaptive) {
210 buf_block_t* prev_block = prev_node->block;
211 ut_a(prev_block->frame
212 == page_align(prev_node->data));
213 ut_a(prev_block->n_pointers > 0);
214 prev_block->n_pointers--;
215 block->n_pointers++;
216 }
217
218 prev_node->block = block;
219 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
220 prev_node->data = data;
221
222 return(TRUE);
223 }
224
225 prev_node = prev_node->next;
226 }
227
228 /* We have to allocate a new chain node */
229
230 node = static_cast<ha_node_t*>(
231 mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t)));
232
233 if (node == NULL) {
234 /* It was a btr search type memory heap and at the moment
235 no more memory could be allocated: return */
236
237 ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
238
239 return(FALSE);
240 }
241
242 ha_node_set_data(node, block, data);
243
244 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
245 if (table->adaptive) {
246 block->n_pointers++;
247 }
248 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
249
250 node->fold = fold;
251
252 node->next = NULL;
253
254 prev_node = static_cast<ha_node_t*>(cell->node);
255
256 if (prev_node == NULL) {
257
258 cell->node = node;
259
260 return(TRUE);
261 }
262
263 while (prev_node->next != NULL) {
264
265 prev_node = prev_node->next;
266 }
267
268 prev_node->next = node;
269
270 return(TRUE);
271 }
272
273 /***********************************************************//**
274 Deletes a hash node. */
275 UNIV_INTERN
276 void
ha_delete_hash_node(hash_table_t * table,ha_node_t * del_node)277 ha_delete_hash_node(
278 /*================*/
279 hash_table_t* table, /*!< in: hash table */
280 ha_node_t* del_node) /*!< in: node to be deleted */
281 {
282 ut_ad(table);
283 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
284 #ifdef UNIV_SYNC_DEBUG
285 ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
286 #endif /* UNIV_SYNC_DEBUG */
287 ut_ad(btr_search_enabled);
288 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
289 if (table->adaptive) {
290 ut_a(del_node->block->frame = page_align(del_node->data));
291 ut_a(del_node->block->n_pointers > 0);
292 del_node->block->n_pointers--;
293 }
294 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
295
296 HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
297 }
298
299 /*********************************************************//**
300 Looks for an element when we know the pointer to the data, and updates
301 the pointer to data, if found.
302 @return TRUE if found */
303 UNIV_INTERN
304 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)305 ha_search_and_update_if_found_func(
306 /*===============================*/
307 hash_table_t* table, /*!< in/out: hash table */
308 ulint fold, /*!< in: folded value of the searched data */
309 const rec_t* data, /*!< in: pointer to the data */
310 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
311 buf_block_t* new_block,/*!< in: block containing new_data */
312 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
313 const rec_t* new_data)/*!< in: new pointer to the data */
314 {
315 ha_node_t* node;
316
317 ut_ad(table);
318 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
319 hash_assert_can_modify(table, fold);
320 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
321 ut_a(new_block->frame == page_align(new_data));
322 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
323 #ifdef UNIV_SYNC_DEBUG
324 ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EX));
325 #endif /* UNIV_SYNC_DEBUG */
326
327 if (!btr_search_enabled) {
328 return(FALSE);
329 }
330
331 node = ha_search_with_data(table, fold, data);
332
333 if (node) {
334 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
335 if (table->adaptive) {
336 ut_a(node->block->n_pointers > 0);
337 node->block->n_pointers--;
338 new_block->n_pointers++;
339 }
340
341 node->block = new_block;
342 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
343 node->data = new_data;
344
345 return(TRUE);
346 }
347
348 return(FALSE);
349 }
350
351 /*****************************************************************//**
352 Removes from the chain determined by fold all nodes whose data pointer
353 points to the page given. */
354 UNIV_INTERN
355 void
ha_remove_all_nodes_to_page(hash_table_t * table,ulint fold,const page_t * page)356 ha_remove_all_nodes_to_page(
357 /*========================*/
358 hash_table_t* table, /*!< in: hash table */
359 ulint fold, /*!< in: fold value */
360 const page_t* page) /*!< in: buffer page */
361 {
362 ha_node_t* node;
363
364 ut_ad(table);
365 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
366 hash_assert_can_modify(table, fold);
367 ut_ad(btr_search_enabled);
368
369 node = ha_chain_get_first(table, fold);
370
371 while (node) {
372 if (page_align(ha_node_get_data(node)) == page) {
373
374 /* Remove the hash node */
375
376 ha_delete_hash_node(table, node);
377
378 /* Start again from the first node in the chain
379 because the deletion may compact the heap of
380 nodes and move other nodes! */
381
382 node = ha_chain_get_first(table, fold);
383 } else {
384 node = ha_chain_get_next(node);
385 }
386 }
387 #ifdef UNIV_DEBUG
388 /* Check that all nodes really got deleted */
389
390 node = ha_chain_get_first(table, fold);
391
392 while (node) {
393 ut_a(page_align(ha_node_get_data(node)) != page);
394
395 node = ha_chain_get_next(node);
396 }
397 #endif
398 }
399
400 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
401 /*************************************************************//**
402 Validates a given range of the cells in hash table.
403 @return TRUE if ok */
404 UNIV_INTERN
405 ibool
ha_validate(hash_table_t * table,ulint start_index,ulint end_index)406 ha_validate(
407 /*========*/
408 hash_table_t* table, /*!< in: hash table */
409 ulint start_index, /*!< in: start index */
410 ulint end_index) /*!< in: end index */
411 {
412 ibool ok = TRUE;
413 ulint i;
414
415 ut_ad(table);
416 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
417 ut_a(start_index <= end_index);
418 ut_a(start_index < hash_get_n_cells(table));
419 ut_a(end_index < hash_get_n_cells(table));
420
421 for (i = start_index; i <= end_index; i++) {
422 ha_node_t* node;
423 hash_cell_t* cell;
424
425 cell = hash_get_nth_cell(table, i);
426
427 for (node = static_cast<ha_node_t*>(cell->node);
428 node != 0;
429 node = node->next) {
430
431 if (hash_calc_hash(node->fold, table) != i) {
432 ut_print_timestamp(stderr);
433 fprintf(stderr,
434 "InnoDB: Error: hash table node"
435 " fold value %lu does not\n"
436 "InnoDB: match the cell number %lu.\n",
437 (ulong) node->fold, (ulong) i);
438
439 ok = FALSE;
440 }
441 }
442 }
443
444 return(ok);
445 }
446 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
447
448 /*************************************************************//**
449 Prints info of a hash table. */
450 UNIV_INTERN
451 void
ha_print_info(FILE * file,hash_table_t * table)452 ha_print_info(
453 /*==========*/
454 FILE* file, /*!< in: file where to print */
455 hash_table_t* table) /*!< in: hash table */
456 {
457 #ifdef UNIV_DEBUG
458 /* Some of the code here is disabled for performance reasons in production
459 builds, see http://bugs.mysql.com/36941 */
460 #define PRINT_USED_CELLS
461 #endif /* UNIV_DEBUG */
462
463 #ifdef PRINT_USED_CELLS
464 hash_cell_t* cell;
465 ulint cells = 0;
466 ulint i;
467 #endif /* PRINT_USED_CELLS */
468 ulint n_bufs;
469
470 ut_ad(table);
471 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
472 #ifdef PRINT_USED_CELLS
473 for (i = 0; i < hash_get_n_cells(table); i++) {
474
475 cell = hash_get_nth_cell(table, i);
476
477 if (cell->node) {
478
479 cells++;
480 }
481 }
482 #endif /* PRINT_USED_CELLS */
483
484 fprintf(file, "Hash table size %lu",
485 (ulong) hash_get_n_cells(table));
486
487 #ifdef PRINT_USED_CELLS
488 fprintf(file, ", used cells %lu", (ulong) cells);
489 #endif /* PRINT_USED_CELLS */
490
491 if (table->heaps == NULL && table->heap != NULL) {
492
493 /* This calculation is intended for the adaptive hash
494 index: how many buffer frames we have reserved? */
495
496 n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
497
498 if (table->heap->free_block) {
499 n_bufs++;
500 }
501
502 fprintf(file, ", node heap has %lu buffer(s)\n",
503 (ulong) n_bufs);
504 }
505 }
506 #endif /* !UNIV_HOTBACKUP */
507