1 /*****************************************************************************
2
3 Copyright (c) 1997, 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/hash0hash.cc
29 The simple hash table utility
30
31 Created 5/20/1997 Heikki Tuuri
32 *******************************************************/
33
34 #include "hash0hash.h"
35 #ifdef UNIV_NONINL
36 #include "hash0hash.ic"
37 #endif
38
39 #include "mem0mem.h"
40
41 #ifndef UNIV_HOTBACKUP
42
43 # ifdef UNIV_PFS_MUTEX
44 UNIV_INTERN mysql_pfs_key_t hash_table_mutex_key;
45 # endif /* UNIV_PFS_MUTEX */
46
47 # ifdef UNIV_PFS_RWLOCK
48 UNIV_INTERN mysql_pfs_key_t hash_table_rw_lock_key;
49 # endif /* UNIV_PFS_RWLOCK */
50 /************************************************************//**
51 Reserves the mutex for a fold value in a hash table. */
52 UNIV_INTERN
53 void
hash_mutex_enter(hash_table_t * table,ulint fold)54 hash_mutex_enter(
55 /*=============*/
56 hash_table_t* table, /*!< in: hash table */
57 ulint fold) /*!< in: fold */
58 {
59 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
60 mutex_enter(hash_get_mutex(table, fold));
61 }
62
63 /************************************************************//**
64 Releases the mutex for a fold value in a hash table. */
65 UNIV_INTERN
66 void
hash_mutex_exit(hash_table_t * table,ulint fold)67 hash_mutex_exit(
68 /*============*/
69 hash_table_t* table, /*!< in: hash table */
70 ulint fold) /*!< in: fold */
71 {
72 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
73 mutex_exit(hash_get_mutex(table, fold));
74 }
75
76 /************************************************************//**
77 Reserves all the mutexes of a hash table, in an ascending order. */
78 UNIV_INTERN
79 void
hash_mutex_enter_all(hash_table_t * table)80 hash_mutex_enter_all(
81 /*=================*/
82 hash_table_t* table) /*!< in: hash table */
83 {
84 ulint i;
85
86 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
87 for (i = 0; i < table->n_sync_obj; i++) {
88
89 mutex_enter(table->sync_obj.mutexes + i);
90 }
91 }
92
93 /************************************************************//**
94 Releases all the mutexes of a hash table. */
95 UNIV_INTERN
96 void
hash_mutex_exit_all(hash_table_t * table)97 hash_mutex_exit_all(
98 /*================*/
99 hash_table_t* table) /*!< in: hash table */
100 {
101 ulint i;
102
103 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
104 for (i = 0; i < table->n_sync_obj; i++) {
105
106 mutex_exit(table->sync_obj.mutexes + i);
107 }
108 }
109
110 /************************************************************//**
111 Releases all but the passed in mutex of a hash table. */
112 UNIV_INTERN
113 void
hash_mutex_exit_all_but(hash_table_t * table,ib_mutex_t * keep_mutex)114 hash_mutex_exit_all_but(
115 /*====================*/
116 hash_table_t* table, /*!< in: hash table */
117 ib_mutex_t* keep_mutex) /*!< in: mutex to keep */
118 {
119 ulint i;
120
121 ut_ad(table->type == HASH_TABLE_SYNC_MUTEX);
122 for (i = 0; i < table->n_sync_obj; i++) {
123
124 ib_mutex_t* mutex = table->sync_obj.mutexes + i;
125 if (UNIV_LIKELY(keep_mutex != mutex)) {
126 mutex_exit(mutex);
127 }
128 }
129
130 ut_ad(mutex_own(keep_mutex));
131 }
132
133 /************************************************************//**
134 s-lock a lock for a fold value in a hash table. */
135 UNIV_INTERN
136 void
hash_lock_s(hash_table_t * table,ulint fold)137 hash_lock_s(
138 /*========*/
139 hash_table_t* table, /*!< in: hash table */
140 ulint fold) /*!< in: fold */
141 {
142
143 rw_lock_t* lock = hash_get_lock(table, fold);
144
145 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
146 ut_ad(lock);
147
148 #ifdef UNIV_SYNC_DEBUG
149 ut_ad(!rw_lock_own(lock, RW_LOCK_SHARED));
150 ut_ad(!rw_lock_own(lock, RW_LOCK_EX));
151 #endif /* UNIV_SYNC_DEBUG */
152
153 rw_lock_s_lock(lock);
154 }
155
156 /************************************************************//**
157 x-lock a lock for a fold value in a hash table. */
158 UNIV_INTERN
159 void
hash_lock_x(hash_table_t * table,ulint fold)160 hash_lock_x(
161 /*========*/
162 hash_table_t* table, /*!< in: hash table */
163 ulint fold) /*!< in: fold */
164 {
165
166 rw_lock_t* lock = hash_get_lock(table, fold);
167
168 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
169 ut_ad(lock);
170
171 #ifdef UNIV_SYNC_DEBUG
172 ut_ad(!rw_lock_own(lock, RW_LOCK_SHARED));
173 ut_ad(!rw_lock_own(lock, RW_LOCK_EX));
174 #endif /* UNIV_SYNC_DEBUG */
175
176 rw_lock_x_lock(lock);
177 }
178
179 /************************************************************//**
180 unlock an s-lock for a fold value in a hash table. */
181 UNIV_INTERN
182 void
hash_unlock_s(hash_table_t * table,ulint fold)183 hash_unlock_s(
184 /*==========*/
185
186 hash_table_t* table, /*!< in: hash table */
187 ulint fold) /*!< in: fold */
188 {
189
190 rw_lock_t* lock = hash_get_lock(table, fold);
191
192 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
193 ut_ad(lock);
194
195 #ifdef UNIV_SYNC_DEBUG
196 ut_ad(rw_lock_own(lock, RW_LOCK_SHARED));
197 #endif /* UNIV_SYNC_DEBUG */
198
199 rw_lock_s_unlock(lock);
200 }
201
202 /************************************************************//**
203 unlock x-lock for a fold value in a hash table. */
204 UNIV_INTERN
205 void
hash_unlock_x(hash_table_t * table,ulint fold)206 hash_unlock_x(
207 /*==========*/
208 hash_table_t* table, /*!< in: hash table */
209 ulint fold) /*!< in: fold */
210 {
211 rw_lock_t* lock = hash_get_lock(table, fold);
212
213 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
214 ut_ad(lock);
215
216 #ifdef UNIV_SYNC_DEBUG
217 ut_ad(rw_lock_own(lock, RW_LOCK_EX));
218 #endif /* UNIV_SYNC_DEBUG */
219
220 rw_lock_x_unlock(lock);
221 }
222
223 /************************************************************//**
224 Reserves all the locks of a hash table, in an ascending order. */
225 UNIV_INTERN
226 void
hash_lock_x_all(hash_table_t * table)227 hash_lock_x_all(
228 /*============*/
229 hash_table_t* table) /*!< in: hash table */
230 {
231 ulint i;
232
233 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
234 for (i = 0; i < table->n_sync_obj; i++) {
235
236 rw_lock_t* lock = table->sync_obj.rw_locks + i;
237 #ifdef UNIV_SYNC_DEBUG
238 ut_ad(!rw_lock_own(lock, RW_LOCK_SHARED));
239 ut_ad(!rw_lock_own(lock, RW_LOCK_EX));
240 #endif /* UNIV_SYNC_DEBUG */
241
242 rw_lock_x_lock(lock);
243 }
244 }
245
246 /************************************************************//**
247 Releases all the locks of a hash table, in an ascending order. */
248 UNIV_INTERN
249 void
hash_unlock_x_all(hash_table_t * table)250 hash_unlock_x_all(
251 /*==============*/
252 hash_table_t* table) /*!< in: hash table */
253 {
254 ulint i;
255
256 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
257 for (i = 0; i < table->n_sync_obj; i++) {
258
259 rw_lock_t* lock = table->sync_obj.rw_locks + i;
260 #ifdef UNIV_SYNC_DEBUG
261 ut_ad(rw_lock_own(lock, RW_LOCK_EX));
262 #endif /* UNIV_SYNC_DEBUG */
263
264 rw_lock_x_unlock(lock);
265 }
266 }
267
268 /************************************************************//**
269 Releases all but passed in lock of a hash table, */
270 UNIV_INTERN
271 void
hash_unlock_x_all_but(hash_table_t * table,rw_lock_t * keep_lock)272 hash_unlock_x_all_but(
273 /*==================*/
274 hash_table_t* table, /*!< in: hash table */
275 rw_lock_t* keep_lock) /*!< in: lock to keep */
276 {
277 ulint i;
278
279 ut_ad(table->type == HASH_TABLE_SYNC_RW_LOCK);
280 for (i = 0; i < table->n_sync_obj; i++) {
281
282 rw_lock_t* lock = table->sync_obj.rw_locks + i;
283 #ifdef UNIV_SYNC_DEBUG
284 ut_ad(rw_lock_own(lock, RW_LOCK_EX));
285 #endif /* UNIV_SYNC_DEBUG */
286
287 if (UNIV_LIKELY(keep_lock != lock)) {
288 rw_lock_x_unlock(lock);
289 }
290 }
291 }
292
293 #endif /* !UNIV_HOTBACKUP */
294
295 /*************************************************************//**
296 Creates a hash table with >= n array cells. The actual number of cells is
297 chosen to be a prime number slightly bigger than n.
298 @return own: created table */
299 UNIV_INTERN
300 hash_table_t*
hash_create(ulint n)301 hash_create(
302 /*========*/
303 ulint n) /*!< in: number of array cells */
304 {
305 hash_cell_t* array;
306 ulint prime;
307 hash_table_t* table;
308
309 prime = ut_find_prime(n);
310
311 table = static_cast<hash_table_t*>(mem_alloc(sizeof(hash_table_t)));
312
313 array = static_cast<hash_cell_t*>(
314 ut_malloc(sizeof(hash_cell_t) * prime));
315
316 /* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
317 the caller is responsible for access control to the table. */
318 table->type = HASH_TABLE_SYNC_NONE;
319 table->array = array;
320 table->n_cells = prime;
321 #ifndef UNIV_HOTBACKUP
322 # if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
323 table->adaptive = FALSE;
324 # endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
325 table->n_sync_obj = 0;
326 table->sync_obj.mutexes = NULL;
327 table->heaps = NULL;
328 #endif /* !UNIV_HOTBACKUP */
329 table->heap = NULL;
330 ut_d(table->magic_n = HASH_TABLE_MAGIC_N);
331
332 /* Initialize the cell array */
333 hash_table_clear(table);
334
335 return(table);
336 }
337
338 /*************************************************************//**
339 Frees a hash table. */
340 UNIV_INTERN
341 void
hash_table_free(hash_table_t * table)342 hash_table_free(
343 /*============*/
344 hash_table_t* table) /*!< in, own: hash table */
345 {
346 ut_ad(table);
347 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
348
349 ut_free(table->array);
350 mem_free(table);
351 }
352
353 #ifndef UNIV_HOTBACKUP
354 /*************************************************************//**
355 Creates a sync object array to protect a hash table.
356 ::sync_obj can be mutexes or rw_locks depening on the type of
357 hash table. */
358 UNIV_INTERN
359 void
hash_create_sync_obj_func(hash_table_t * table,enum hash_table_sync_t type,ulint sync_level,ulint n_sync_obj)360 hash_create_sync_obj_func(
361 /*======================*/
362 hash_table_t* table, /*!< in: hash table */
363 enum hash_table_sync_t type, /*!< in: HASH_TABLE_SYNC_MUTEX
364 or HASH_TABLE_SYNC_RW_LOCK */
365 #ifdef UNIV_SYNC_DEBUG
366 ulint sync_level,/*!< in: latching order level
367 of the mutexes: used in the
368 debug version */
369 #endif /* UNIV_SYNC_DEBUG */
370 ulint n_sync_obj)/*!< in: number of sync objects,
371 must be a power of 2 */
372 {
373 ulint i;
374
375 ut_ad(table);
376 ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
377 ut_a(n_sync_obj > 0);
378 ut_a(ut_is_2pow(n_sync_obj));
379
380 table->type = type;
381
382 switch (type) {
383 case HASH_TABLE_SYNC_MUTEX:
384 table->sync_obj.mutexes = static_cast<ib_mutex_t*>(
385 mem_alloc(n_sync_obj * sizeof(ib_mutex_t)));
386
387 for (i = 0; i < n_sync_obj; i++) {
388 mutex_create(hash_table_mutex_key,
389 table->sync_obj.mutexes + i, sync_level);
390 }
391
392 break;
393
394 case HASH_TABLE_SYNC_RW_LOCK:
395 table->sync_obj.rw_locks = static_cast<rw_lock_t*>(
396 mem_alloc(n_sync_obj * sizeof(rw_lock_t)));
397
398 for (i = 0; i < n_sync_obj; i++) {
399 rw_lock_create(hash_table_rw_lock_key,
400 table->sync_obj.rw_locks + i, sync_level);
401 }
402
403 break;
404
405 case HASH_TABLE_SYNC_NONE:
406 ut_error;
407 }
408
409 table->n_sync_obj = n_sync_obj;
410 }
411 #endif /* !UNIV_HOTBACKUP */
412