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