Branch data Line data Source code
1 : : /* Copyright (C) 2000-2019 Red Hat, Inc.
2 : : This file is part of elfutils.
3 : : Written by Srdan Milakovic <sm108@rice.edu>, 2019.
4 : : Derived from Ulrich Drepper <drepper@redhat.com>, 2000.
5 : :
6 : : This file is free software; you can redistribute it and/or modify
7 : : it under the terms of either
8 : :
9 : : * the GNU Lesser General Public License as published by the Free
10 : : Software Foundation; either version 3 of the License, or (at
11 : : your option) any later version
12 : :
13 : : or
14 : :
15 : : * the GNU General Public License as published by the Free
16 : : Software Foundation; either version 2 of the License, or (at
17 : : your option) any later version
18 : :
19 : : or both in parallel, as here.
20 : :
21 : : elfutils is distributed in the hope that it will be useful, but
22 : : WITHOUT ANY WARRANTY; without even the implied warranty of
23 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24 : : General Public License for more details.
25 : :
26 : : You should have received copies of the GNU General Public License and
27 : : the GNU Lesser General Public License along with this program. If
28 : : not, see <http://www.gnu.org/licenses/>. */
29 : :
30 : : #include <assert.h>
31 : : #include <stdlib.h>
32 : : #include <system.h>
33 : : #include <pthread.h>
34 : :
35 : : /* Before including this file the following macros must be defined:
36 : :
37 : : NAME name of the hash table structure.
38 : : TYPE data type of the hash table entries
39 : : */
40 : :
41 : :
42 : : static size_t
43 : 15916201 : lookup (NAME *htab, HASHTYPE hval)
44 : : {
45 : : /* First hash function: simply take the modulus but prevent zero. Small values
46 : : can skip the division, which helps performance when this is common. */
47 [ + + ]: 15916201 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
48 : :
49 : 15916201 : HASHTYPE hash;
50 : :
51 : 15916201 : hash = atomic_load_explicit(&htab->table[idx].hashval,
52 : : memory_order_acquire);
53 [ + + ]: 15916201 : if (hash == hval)
54 : : return idx;
55 [ + + ]: 1110543 : else if (hash == 0)
56 : : return 0;
57 : :
58 : : /* Second hash function as suggested in [Knuth]. */
59 : 1584 : HASHTYPE second_hash = 1 + hval % (htab->size - 2);
60 : :
61 : 1584 : for(;;)
62 : : {
63 [ + - ]: 1584 : if (idx <= second_hash)
64 : 1584 : idx = htab->size + idx - second_hash;
65 : : else
66 : 0 : idx -= second_hash;
67 : :
68 : 1584 : hash = atomic_load_explicit(&htab->table[idx].hashval,
69 : : memory_order_acquire);
70 [ - + ]: 1584 : if (hash == hval)
71 : 0 : return idx;
72 [ - + ]: 1584 : else if (hash == 0)
73 : : return 0;
74 : : }
75 : : }
76 : :
77 : : static int
78 : 1056028 : insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
79 : : {
80 : : /* First hash function: simply take the modulus but prevent zero. Small values
81 : : can skip the division, which helps performance when this is common. */
82 [ + + ]: 1056028 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
83 : :
84 : 1056028 : TYPE val_ptr;
85 : 1056028 : HASHTYPE hash;
86 : :
87 : 1056028 : hash = atomic_load_explicit(&htab->table[idx].hashval,
88 : : memory_order_acquire);
89 [ + - ]: 1056028 : if (hash == hval)
90 : : return -1;
91 [ + - ]: 1056028 : else if (hash == 0)
92 : : {
93 : 1056028 : val_ptr = NULL;
94 : 1056028 : atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
95 : : (uintptr_t *) &val_ptr,
96 : : (uintptr_t) val,
97 : : memory_order_acquire,
98 : : memory_order_acquire);
99 : :
100 [ + - ]: 1056028 : if (val_ptr == NULL)
101 : : {
102 : 1056028 : atomic_store_explicit(&htab->table[idx].hashval, hval,
103 : : memory_order_release);
104 : 1056028 : return 0;
105 : : }
106 : : else
107 : : {
108 : 0 : do
109 : : {
110 : 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
111 : : memory_order_acquire);
112 : : }
113 [ # # ]: 0 : while (hash == 0);
114 [ # # ]: 0 : if (hash == hval)
115 : : return -1;
116 : : }
117 : : }
118 : :
119 : : /* Second hash function as suggested in [Knuth]. */
120 : 0 : HASHTYPE second_hash = 1 + hval % (htab->size - 2);
121 : :
122 : 0 : for(;;)
123 : : {
124 [ # # ]: 0 : if (idx <= second_hash)
125 : 0 : idx = htab->size + idx - second_hash;
126 : : else
127 : 0 : idx -= second_hash;
128 : :
129 : 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
130 : : memory_order_acquire);
131 [ # # ]: 0 : if (hash == hval)
132 : : return -1;
133 [ # # ]: 0 : else if (hash == 0)
134 : : {
135 : 0 : val_ptr = NULL;
136 : 0 : atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
137 : : (uintptr_t *) &val_ptr,
138 : : (uintptr_t) val,
139 : : memory_order_acquire,
140 : : memory_order_acquire);
141 : :
142 [ # # ]: 0 : if (val_ptr == NULL)
143 : : {
144 : 0 : atomic_store_explicit(&htab->table[idx].hashval, hval,
145 : : memory_order_release);
146 : 0 : return 0;
147 : : }
148 : : else
149 : : {
150 : 0 : do
151 : : {
152 : 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
153 : : memory_order_acquire);
154 : : }
155 [ # # ]: 0 : while (hash == 0);
156 [ # # ]: 0 : if (hash == hval)
157 : : return -1;
158 : : }
159 : : }
160 : : }
161 : : }
162 : :
163 : : #define NO_RESIZING 0u
164 : : #define ALLOCATING_MEMORY 1u
165 : : #define MOVING_DATA 3u
166 : : #define CLEANING 2u
167 : :
168 : : #define STATE_BITS 2u
169 : : #define STATE_INCREMENT (1u << STATE_BITS)
170 : : #define STATE_MASK (STATE_INCREMENT - 1)
171 : : #define GET_STATE(A) ((A) & STATE_MASK)
172 : :
173 : : #define IS_NO_RESIZE_OR_CLEANING(A) (((A) & 0x1u) == 0)
174 : :
175 : : #define GET_ACTIVE_WORKERS(A) ((A) >> STATE_BITS)
176 : :
177 : : #define INITIALIZATION_BLOCK_SIZE 256
178 : : #define MOVE_BLOCK_SIZE 256
179 : : #define CEIL(A, B) (((A) + (B) - 1) / (B))
180 : :
181 : : /* Initializes records and copies the data from the old table.
182 : : It can share work with other threads. Only the coordinator
183 : : will pass blocking as 1, other worker threads pass 0. */
184 : 9624 : static void resize_helper(NAME *htab, int blocking)
185 : : {
186 : 9624 : size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
187 : 9624 : size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
188 : :
189 : 9624 : size_t my_block;
190 : 9624 : size_t num_finished_blocks = 0;
191 : :
192 [ + + ]: 19250 : while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
193 : : memory_order_acquire))
194 : : < num_new_blocks)
195 : : {
196 : 9626 : size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
197 : 9626 : size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
198 : 9626 : if (record_end > htab->size)
199 : : record_end = htab->size;
200 : :
201 [ + + ]: 929634 : while (record_it++ != record_end)
202 : : {
203 : 920008 : atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
204 : 920008 : atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
205 : : }
206 : :
207 : 9626 : num_finished_blocks++;
208 : : }
209 : :
210 : 9624 : atomic_fetch_add_explicit(&htab->num_initialized_blocks,
211 : : num_finished_blocks, memory_order_release);
212 : 9624 : while (atomic_load_explicit(&htab->num_initialized_blocks,
213 [ - + ]: 9624 : memory_order_acquire) != num_new_blocks);
214 : :
215 : : /* All block are initialized, start moving */
216 : : num_finished_blocks = 0;
217 [ + + ]: 19248 : while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
218 : : memory_order_acquire))
219 : : < num_old_blocks)
220 : : {
221 : 9624 : size_t record_it = my_block * MOVE_BLOCK_SIZE;
222 : 9624 : size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
223 : 9624 : if (record_end > htab->old_size)
224 : : record_end = htab->old_size;
225 : :
226 [ + + ]: 464814 : while (record_it++ != record_end)
227 : : {
228 : 455190 : TYPE val_ptr = (TYPE) atomic_load_explicit(
229 : : &htab->old_table[record_it].val_ptr,
230 : : memory_order_acquire);
231 [ + + ]: 455190 : if (val_ptr == NULL)
232 : 44268 : continue;
233 : :
234 : 410922 : HASHTYPE hashval = atomic_load_explicit(
235 : : &htab->old_table[record_it].hashval,
236 : : memory_order_acquire);
237 [ - + ]: 410922 : assert(hashval);
238 : :
239 : 410922 : insert_helper(htab, hashval, val_ptr);
240 : : }
241 : :
242 : 9624 : num_finished_blocks++;
243 : : }
244 : :
245 : 9624 : atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
246 : : memory_order_release);
247 : :
248 : : /* The coordinating thread will block here waiting for all blocks to
249 : : be moved. */
250 [ + - ]: 9624 : if (blocking)
251 : 9624 : while (atomic_load_explicit(&htab->num_moved_blocks,
252 [ - + ]: 9624 : memory_order_acquire) != num_old_blocks);
253 : 9624 : }
254 : :
255 : : /* Called by the main thread holding the htab->resize_rwl lock to
256 : : coordinate the moving of hash table data. Allocates the new hash
257 : : table and frees the old one when moving all data is done. */
258 : : static void
259 : 9624 : resize_coordinator(NAME *htab)
260 : : {
261 : 9624 : htab->old_size = htab->size;
262 : 9624 : htab->old_table = htab->table;
263 : :
264 : 9624 : htab->size = next_prime(htab->size * 2);
265 : 9624 : htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
266 [ - + ]: 9624 : assert(htab->table);
267 : :
268 : : /* Change state from ALLOCATING_MEMORY to MOVING_DATA */
269 : 9624 : atomic_fetch_xor_explicit(&htab->resizing_state,
270 : : ALLOCATING_MEMORY ^ MOVING_DATA,
271 : : memory_order_release);
272 : :
273 : 9624 : resize_helper(htab, 1);
274 : :
275 : : /* Change state from MOVING_DATA to CLEANING */
276 : 9624 : size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
277 : : MOVING_DATA ^ CLEANING,
278 : : memory_order_acq_rel);
279 [ - + ]: 9624 : while (GET_ACTIVE_WORKERS(resize_state) != 0)
280 : 0 : resize_state = atomic_load_explicit(&htab->resizing_state,
281 : : memory_order_acquire);
282 : :
283 : : /* There are no more active workers */
284 : 9624 : atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
285 : 9624 : atomic_store_explicit(&htab->num_initialized_blocks, 0,
286 : : memory_order_relaxed);
287 : :
288 : 9624 : atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
289 : 9624 : atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
290 : :
291 : 9624 : free(htab->old_table);
292 : :
293 : : /* Change state to NO_RESIZING */
294 : 9624 : atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
295 : : memory_order_relaxed);
296 : :
297 : 9624 : }
298 : :
299 : : /* Called by any thread that wants to do an insert or find operation
300 : : but notices it cannot get the htab->resize_rwl lock because another
301 : : thread is resizing the hash table. Try to help out by moving table
302 : : data if still necessary. */
303 : : static void
304 : 0 : resize_worker(NAME *htab)
305 : : {
306 : 0 : size_t resize_state = atomic_load_explicit(&htab->resizing_state,
307 : : memory_order_acquire);
308 : :
309 : : /* If the resize has finished */
310 [ # # ]: 0 : if (IS_NO_RESIZE_OR_CLEANING(resize_state))
311 : : return;
312 : :
313 : : /* Register as worker and check if the resize has finished in the meantime*/
314 : 0 : resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
315 : : STATE_INCREMENT,
316 : : memory_order_acquire);
317 [ # # ]: 0 : if (IS_NO_RESIZE_OR_CLEANING(resize_state))
318 : : {
319 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
320 : : memory_order_relaxed);
321 : 0 : return;
322 : : }
323 : :
324 : : /* Wait while the new table is being allocated. */
325 [ # # ]: 0 : while (GET_STATE(resize_state) == ALLOCATING_MEMORY)
326 : 0 : resize_state = atomic_load_explicit(&htab->resizing_state,
327 : : memory_order_acquire);
328 : :
329 : : /* Check if the resize is done */
330 [ # # ]: 0 : assert(GET_STATE(resize_state) != NO_RESIZING);
331 [ # # ]: 0 : if (GET_STATE(resize_state) == CLEANING)
332 : : {
333 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
334 : : memory_order_relaxed);
335 : 0 : return;
336 : : }
337 : :
338 : 0 : resize_helper(htab, 0);
339 : :
340 : : /* Deregister worker */
341 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
342 : : memory_order_release);
343 : : }
344 : :
345 : :
346 : : int
347 : : #define INIT(name) _INIT (name)
348 : : #define _INIT(name) \
349 : : name##_init
350 : 28368 : INIT(NAME) (NAME *htab, size_t init_size)
351 : : {
352 : : /* We need the size to be a prime. */
353 : 28368 : init_size = next_prime (init_size);
354 : :
355 : : /* Initialize the data structure. */
356 : 28368 : htab->size = init_size;
357 : 28368 : atomic_init(&htab->filled, 0);
358 : 28368 : atomic_init(&htab->resizing_state, 0);
359 : :
360 : 28368 : atomic_init(&htab->next_init_block, 0);
361 : 28368 : atomic_init(&htab->num_initialized_blocks, 0);
362 : :
363 : 28368 : atomic_init(&htab->next_move_block, 0);
364 : 28368 : atomic_init(&htab->num_moved_blocks, 0);
365 : :
366 : 28368 : pthread_rwlock_init(&htab->resize_rwl, NULL);
367 : :
368 : 28368 : htab->table = malloc ((init_size + 1) * sizeof (htab->table[0]));
369 [ + - ]: 28368 : if (htab->table == NULL)
370 : : return -1;
371 : :
372 [ + + ]: 1041264 : for (size_t i = 0; i <= init_size; i++)
373 : : {
374 : 1012896 : atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
375 : 1012896 : atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL);
376 : : }
377 : :
378 : : return 0;
379 : : }
380 : :
381 : :
382 : : int
383 : : #define FREE(name) _FREE (name)
384 : : #define _FREE(name) \
385 : : name##_free
386 : 28368 : FREE(NAME) (NAME *htab)
387 : : {
388 : 28368 : pthread_rwlock_destroy(&htab->resize_rwl);
389 : 28368 : free (htab->table);
390 : 28368 : return 0;
391 : : }
392 : :
393 : :
394 : : int
395 : : #define INSERT(name) _INSERT (name)
396 : : #define _INSERT(name) \
397 : : name##_insert
398 : 645106 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
399 : : {
400 : 645106 : int incremented = 0;
401 : :
402 : : for(;;)
403 : : {
404 : : /* If we cannot get the resize_rwl lock someone is resizing
405 : : hash table, try to help out by moving table data. */
406 [ - + ]: 654730 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
407 : 0 : resize_worker(htab);
408 : :
409 : 654730 : size_t filled;
410 [ + + ]: 654730 : if (!incremented)
411 : : {
412 : 645106 : filled = atomic_fetch_add_explicit(&htab->filled, 1,
413 : : memory_order_acquire);
414 : 645106 : incremented = 1;
415 : : }
416 : : else
417 : : {
418 : 9624 : filled = atomic_load_explicit(&htab->filled,
419 : : memory_order_acquire);
420 : : }
421 : :
422 : :
423 [ + + ]: 654730 : if (100 * filled > 90 * htab->size)
424 : : {
425 : : /* Table is filled more than 90%. Resize the table. */
426 : :
427 : 9624 : size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
428 : : memory_order_acquire);
429 [ + - + - ]: 19248 : if (resizing_state == 0 &&
430 : 9624 : atomic_compare_exchange_strong_explicit(&htab->resizing_state,
431 : : &resizing_state,
432 : : ALLOCATING_MEMORY,
433 : : memory_order_acquire,
434 : : memory_order_acquire))
435 : : {
436 : : /* Main resizing thread, will coordinate moving data. */
437 : 9624 : pthread_rwlock_unlock(&htab->resize_rwl);
438 : :
439 : 9624 : pthread_rwlock_wrlock(&htab->resize_rwl);
440 : 9624 : resize_coordinator(htab);
441 : 9624 : pthread_rwlock_unlock(&htab->resize_rwl);
442 : :
443 : : }
444 : : else
445 : : {
446 : : /* Worker thread, will help moving data. */
447 : 0 : pthread_rwlock_unlock(&htab->resize_rwl);
448 : 0 : resize_worker(htab);
449 : : }
450 : : }
451 : : else
452 : : {
453 : : /* Lock acquired, no need for resize*/
454 : : break;
455 : : }
456 : : }
457 : :
458 : 645106 : int ret_val = insert_helper(htab, hval, data);
459 [ - + ]: 645106 : if (ret_val == -1)
460 : 0 : atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
461 : 645106 : pthread_rwlock_unlock(&htab->resize_rwl);
462 : 645106 : return ret_val;
463 : : }
464 : :
465 : :
466 : :
467 : : TYPE
468 : : #define FIND(name) _FIND (name)
469 : : #define _FIND(name) \
470 : : name##_find
471 : 15916201 : FIND(NAME) (NAME *htab, HASHTYPE hval)
472 : : {
473 : : /* If we cannot get the resize_rwl lock someone is resizing
474 : : the hash table, try to help out by moving table data. */
475 [ - + ]: 15916201 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
476 : 0 : resize_worker(htab);
477 : :
478 : 15916201 : size_t idx;
479 : :
480 : : /* Make the hash data nonzero. */
481 : 15916201 : hval = hval ?: 1;
482 : 15916201 : idx = lookup(htab, hval);
483 : :
484 [ + + ]: 15916201 : if (idx == 0)
485 : : {
486 : 1110543 : pthread_rwlock_unlock(&htab->resize_rwl);
487 : 1110543 : return NULL;
488 : : }
489 : :
490 : : /* get a copy before unlocking the lock */
491 : 14805658 : TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
492 : : memory_order_relaxed);
493 : :
494 : 14805658 : pthread_rwlock_unlock(&htab->resize_rwl);
495 : 14805658 : return ret_val;
496 : : }
|
