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 : 17035009 : lookup (NAME *htab, HASHTYPE hval)
44 : : {
45 : : /* First hash function: simply take the modul but prevent zero. Small values
46 : : can skip the division, which helps performance when this is common. */
47 [ + + ]: 17035009 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
48 : :
49 : 17035009 : HASHTYPE hash;
50 : :
51 : 17035009 : hash = atomic_load_explicit(&htab->table[idx].hashval,
52 : : memory_order_acquire);
53 [ + + ]: 17035009 : if (hash == hval)
54 : : return idx;
55 [ + + ]: 1094331 : else if (hash == 0)
56 : : return 0;
57 : :
58 : : /* Second hash function as suggested in [Knuth]. */
59 : 1320 : HASHTYPE second_hash = 1 + hval % (htab->size - 2);
60 : :
61 : 1320 : for(;;)
62 : : {
63 [ + - ]: 1320 : if (idx <= second_hash)
64 : 1320 : idx = htab->size + idx - second_hash;
65 : : else
66 : 0 : idx -= second_hash;
67 : :
68 : 1320 : hash = atomic_load_explicit(&htab->table[idx].hashval,
69 : : memory_order_acquire);
70 [ - + ]: 1320 : if (hash == hval)
71 : 0 : return idx;
72 [ - + ]: 1320 : else if (hash == 0)
73 : : return 0;
74 : : }
75 : : }
76 : :
77 : : static int
78 : 1035498 : insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
79 : : {
80 : : /* First hash function: simply take the modul but prevent zero. Small values
81 : : can skip the division, which helps performance when this is common. */
82 [ + + ]: 1035498 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
83 : :
84 : 1035498 : TYPE val_ptr;
85 : 1035498 : HASHTYPE hash;
86 : :
87 : 1035498 : hash = atomic_load_explicit(&htab->table[idx].hashval,
88 : : memory_order_acquire);
89 [ + - ]: 1035498 : if (hash == hval)
90 : : return -1;
91 [ + - ]: 1035498 : else if (hash == 0)
92 : : {
93 : 1035498 : val_ptr = NULL;
94 : 1035498 : 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 [ + - ]: 1035498 : if (val_ptr == NULL)
101 : : {
102 : 1035498 : atomic_store_explicit(&htab->table[idx].hashval, hval,
103 : : memory_order_release);
104 : 1035498 : 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 */
183 : 9437 : static void resize_helper(NAME *htab, int blocking)
184 : : {
185 : 9437 : size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
186 : 9437 : size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
187 : :
188 : 9437 : size_t my_block;
189 : 9437 : size_t num_finished_blocks = 0;
190 : :
191 [ + + ]: 18876 : while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
192 : : memory_order_acquire))
193 : : < num_new_blocks)
194 : : {
195 : 9439 : size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
196 : 9439 : size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
197 : 9439 : if (record_end > htab->size)
198 : : record_end = htab->size;
199 : :
200 [ + + ]: 905190 : while (record_it++ != record_end)
201 : : {
202 : 895751 : atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
203 : 895751 : atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
204 : : }
205 : :
206 : 9439 : num_finished_blocks++;
207 : : }
208 : :
209 : 9437 : atomic_fetch_add_explicit(&htab->num_initialized_blocks,
210 : : num_finished_blocks, memory_order_release);
211 : 9437 : while (atomic_load_explicit(&htab->num_initialized_blocks,
212 [ - + ]: 9437 : memory_order_acquire) != num_new_blocks);
213 : :
214 : : /* All block are initialized, start moving */
215 : : num_finished_blocks = 0;
216 [ + + ]: 18874 : while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
217 : : memory_order_acquire))
218 : : < num_old_blocks)
219 : : {
220 : 9437 : size_t record_it = my_block * MOVE_BLOCK_SIZE;
221 : 9437 : size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
222 : 9437 : if (record_end > htab->old_size)
223 : : record_end = htab->old_size;
224 : :
225 [ + + ]: 452592 : while (record_it++ != record_end)
226 : : {
227 : 443155 : TYPE val_ptr = (TYPE) atomic_load_explicit(
228 : : &htab->old_table[record_it].val_ptr,
229 : : memory_order_acquire);
230 [ + + ]: 443155 : if (val_ptr == NULL)
231 : 43104 : continue;
232 : :
233 : 400051 : HASHTYPE hashval = atomic_load_explicit(
234 : : &htab->old_table[record_it].hashval,
235 : : memory_order_acquire);
236 [ - + ]: 400051 : assert(hashval);
237 : :
238 : 400051 : insert_helper(htab, hashval, val_ptr);
239 : : }
240 : :
241 : 9437 : num_finished_blocks++;
242 : : }
243 : :
244 : 9437 : atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
245 : : memory_order_release);
246 : :
247 [ + - ]: 9437 : if (blocking)
248 : 9437 : while (atomic_load_explicit(&htab->num_moved_blocks,
249 [ - + ]: 9437 : memory_order_acquire) != num_old_blocks);
250 : 9437 : }
251 : :
252 : : static void
253 : 9437 : resize_master(NAME *htab)
254 : : {
255 : 9437 : htab->old_size = htab->size;
256 : 9437 : htab->old_table = htab->table;
257 : :
258 : 9437 : htab->size = next_prime(htab->size * 2);
259 : 9437 : htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
260 [ - + ]: 9437 : assert(htab->table);
261 : :
262 : : /* Change state from ALLOCATING_MEMORY to MOVING_DATA */
263 : 9437 : atomic_fetch_xor_explicit(&htab->resizing_state,
264 : : ALLOCATING_MEMORY ^ MOVING_DATA,
265 : : memory_order_release);
266 : :
267 : 9437 : resize_helper(htab, 1);
268 : :
269 : : /* Change state from MOVING_DATA to CLEANING */
270 : 9437 : size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
271 : : MOVING_DATA ^ CLEANING,
272 : : memory_order_acq_rel);
273 [ - + ]: 9437 : while (GET_ACTIVE_WORKERS(resize_state) != 0)
274 : 0 : resize_state = atomic_load_explicit(&htab->resizing_state,
275 : : memory_order_acquire);
276 : :
277 : : /* There are no more active workers */
278 : 9437 : atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
279 : 9437 : atomic_store_explicit(&htab->num_initialized_blocks, 0,
280 : : memory_order_relaxed);
281 : :
282 : 9437 : atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
283 : 9437 : atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
284 : :
285 : 9437 : free(htab->old_table);
286 : :
287 : : /* Change state to NO_RESIZING */
288 : 9437 : atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
289 : : memory_order_relaxed);
290 : :
291 : 9437 : }
292 : :
293 : : static void
294 : 0 : resize_worker(NAME *htab)
295 : : {
296 : 0 : size_t resize_state = atomic_load_explicit(&htab->resizing_state,
297 : : memory_order_acquire);
298 : :
299 : : /* If the resize has finished */
300 [ # # ]: 0 : if (IS_NO_RESIZE_OR_CLEANING(resize_state))
301 : : return;
302 : :
303 : : /* Register as worker and check if the resize has finished in the meantime*/
304 : 0 : resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
305 : : STATE_INCREMENT,
306 : : memory_order_acquire);
307 [ # # ]: 0 : if (IS_NO_RESIZE_OR_CLEANING(resize_state))
308 : : {
309 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
310 : : memory_order_relaxed);
311 : 0 : return;
312 : : }
313 : :
314 : : /* Wait while the new table is being allocated. */
315 [ # # ]: 0 : while (GET_STATE(resize_state) == ALLOCATING_MEMORY)
316 : 0 : resize_state = atomic_load_explicit(&htab->resizing_state,
317 : : memory_order_acquire);
318 : :
319 : : /* Check if the resize is done */
320 [ # # ]: 0 : assert(GET_STATE(resize_state) != NO_RESIZING);
321 [ # # ]: 0 : if (GET_STATE(resize_state) == CLEANING)
322 : : {
323 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
324 : : memory_order_relaxed);
325 : 0 : return;
326 : : }
327 : :
328 : 0 : resize_helper(htab, 0);
329 : :
330 : : /* Deregister worker */
331 : 0 : atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
332 : : memory_order_release);
333 : : }
334 : :
335 : :
336 : : int
337 : : #define INIT(name) _INIT (name)
338 : : #define _INIT(name) \
339 : : name##_init
340 : 26975 : INIT(NAME) (NAME *htab, size_t init_size)
341 : : {
342 : : /* We need the size to be a prime. */
343 : 26975 : init_size = next_prime (init_size);
344 : :
345 : : /* Initialize the data structure. */
346 : 26975 : htab->size = init_size;
347 : 26975 : atomic_init(&htab->filled, 0);
348 : 26975 : atomic_init(&htab->resizing_state, 0);
349 : :
350 : 26975 : atomic_init(&htab->next_init_block, 0);
351 : 26975 : atomic_init(&htab->num_initialized_blocks, 0);
352 : :
353 : 26975 : atomic_init(&htab->next_move_block, 0);
354 : 26975 : atomic_init(&htab->num_moved_blocks, 0);
355 : :
356 : 26975 : pthread_rwlock_init(&htab->resize_rwl, NULL);
357 : :
358 : 26975 : htab->table = (void *) malloc ((init_size + 1) * sizeof (htab->table[0]));
359 [ + - ]: 26975 : if (htab->table == NULL)
360 : : return -1;
361 : :
362 [ + + ]: 987275 : for (size_t i = 0; i <= init_size; i++)
363 : : {
364 : 960300 : atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
365 : 960300 : atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL);
366 : : }
367 : :
368 : : return 0;
369 : : }
370 : :
371 : :
372 : : int
373 : : #define FREE(name) _FREE (name)
374 : : #define _FREE(name) \
375 : : name##_free
376 : 26975 : FREE(NAME) (NAME *htab)
377 : : {
378 : 26975 : pthread_rwlock_destroy(&htab->resize_rwl);
379 : 26975 : free (htab->table);
380 : 26975 : return 0;
381 : : }
382 : :
383 : :
384 : : int
385 : : #define INSERT(name) _INSERT (name)
386 : : #define _INSERT(name) \
387 : : name##_insert
388 : 635447 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
389 : : {
390 : 635447 : int incremented = 0;
391 : :
392 : : for(;;)
393 : : {
394 [ - + ]: 644884 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
395 : 0 : resize_worker(htab);
396 : :
397 : 644884 : size_t filled;
398 [ + + ]: 644884 : if (!incremented)
399 : : {
400 : 635447 : filled = atomic_fetch_add_explicit(&htab->filled, 1,
401 : : memory_order_acquire);
402 : 635447 : incremented = 1;
403 : : }
404 : : else
405 : : {
406 : 9437 : filled = atomic_load_explicit(&htab->filled,
407 : : memory_order_acquire);
408 : : }
409 : :
410 : :
411 [ + + ]: 644884 : if (100 * filled > 90 * htab->size)
412 : : {
413 : : /* Table is filled more than 90%. Resize the table. */
414 : :
415 : 9437 : size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
416 : : memory_order_acquire);
417 [ + - + - ]: 18874 : if (resizing_state == 0 &&
418 : 9437 : atomic_compare_exchange_strong_explicit(&htab->resizing_state,
419 : : &resizing_state,
420 : : ALLOCATING_MEMORY,
421 : : memory_order_acquire,
422 : : memory_order_acquire))
423 : : {
424 : : /* Master thread */
425 : 9437 : pthread_rwlock_unlock(&htab->resize_rwl);
426 : :
427 : 9437 : pthread_rwlock_wrlock(&htab->resize_rwl);
428 : 9437 : resize_master(htab);
429 : 9437 : pthread_rwlock_unlock(&htab->resize_rwl);
430 : :
431 : : }
432 : : else
433 : : {
434 : : /* Worker thread */
435 : 0 : pthread_rwlock_unlock(&htab->resize_rwl);
436 : 0 : resize_worker(htab);
437 : : }
438 : : }
439 : : else
440 : : {
441 : : /* Lock acquired, no need for resize*/
442 : : break;
443 : : }
444 : : }
445 : :
446 : 635447 : int ret_val = insert_helper(htab, hval, data);
447 [ - + ]: 635447 : if (ret_val == -1)
448 : 0 : atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
449 : 635447 : pthread_rwlock_unlock(&htab->resize_rwl);
450 : 635447 : return ret_val;
451 : : }
452 : :
453 : :
454 : :
455 : : TYPE
456 : : #define FIND(name) _FIND (name)
457 : : #define _FIND(name) \
458 : : name##_find
459 : 17035009 : FIND(NAME) (NAME *htab, HASHTYPE hval)
460 : : {
461 [ - + ]: 17035009 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
462 : 0 : resize_worker(htab);
463 : :
464 : 17035009 : size_t idx;
465 : :
466 : : /* Make the hash data nonzero. */
467 : 17035009 : hval = hval ?: 1;
468 : 17035009 : idx = lookup(htab, hval);
469 : :
470 [ + + ]: 17035009 : if (idx == 0)
471 : : {
472 : 1094331 : pthread_rwlock_unlock(&htab->resize_rwl);
473 : 1094331 : return NULL;
474 : : }
475 : :
476 : : /* get a copy before unlocking the lock */
477 : 15940678 : TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
478 : : memory_order_relaxed);
479 : :
480 : 15940678 : pthread_rwlock_unlock(&htab->resize_rwl);
481 : 15940678 : return ret_val;
482 : : }
|
