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 0 : 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 0 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
48 :
49 0 : HASHTYPE hash;
50 :
51 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
52 : memory_order_acquire);
53 0 : if (hash == hval)
54 0 : return idx;
55 0 : else if (hash == 0)
56 0 : return 0;
57 :
58 : /* Second hash function as suggested in [Knuth]. */
59 0 : HASHTYPE second_hash = 1 + hval % (htab->size - 2);
60 :
61 0 : for(;;)
62 : {
63 0 : if (idx <= second_hash)
64 0 : idx = htab->size + idx - second_hash;
65 : else
66 0 : idx -= second_hash;
67 :
68 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
69 : memory_order_acquire);
70 0 : if (hash == hval)
71 0 : return idx;
72 0 : else if (hash == 0)
73 0 : return 0;
74 : }
75 : }
76 :
77 : static int
78 0 : 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 0 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
83 :
84 0 : TYPE val_ptr;
85 0 : HASHTYPE hash;
86 :
87 0 : hash = atomic_load_explicit(&htab->table[idx].hashval,
88 : memory_order_acquire);
89 0 : if (hash == hval)
90 0 : return -1;
91 0 : else if (hash == 0)
92 : {
93 0 : val_ptr = NULL;
94 0 : 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 0 : if (val_ptr == NULL)
101 : {
102 0 : atomic_store_explicit(&htab->table[idx].hashval, hval,
103 : memory_order_release);
104 0 : 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 0 : 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 0 : 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 0 : 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 12496 : static void resize_helper(NAME *htab, int blocking)
184 : {
185 12496 : size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
186 12496 : size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
187 :
188 12496 : size_t my_block;
189 12496 : size_t num_finished_blocks = 0;
190 :
191 24996 : while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
192 : memory_order_acquire))
193 : < num_new_blocks)
194 : {
195 12500 : size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
196 12500 : size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
197 12500 : if (record_end > htab->size)
198 12496 : record_end = htab->size;
199 :
200 1229184 : while (record_it++ != record_end)
201 : {
202 1216684 : atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
203 1216684 : atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
204 : }
205 :
206 12500 : num_finished_blocks++;
207 : }
208 :
209 12496 : atomic_fetch_add_explicit(&htab->num_initialized_blocks,
210 : num_finished_blocks, memory_order_release);
211 12496 : while (atomic_load_explicit(&htab->num_initialized_blocks,
212 12496 : memory_order_acquire) != num_new_blocks);
213 :
214 : /* All block are initialized, start moving */
215 : num_finished_blocks = 0;
216 24992 : while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
217 : memory_order_acquire))
218 : < num_old_blocks)
219 : {
220 12496 : size_t record_it = my_block * MOVE_BLOCK_SIZE;
221 12496 : size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
222 12496 : if (record_end > htab->old_size)
223 12496 : record_end = htab->old_size;
224 :
225 614586 : while (record_it++ != record_end)
226 : {
227 602090 : TYPE val_ptr = (TYPE) atomic_load_explicit(
228 : &htab->old_table[record_it].val_ptr,
229 : memory_order_acquire);
230 602090 : if (val_ptr == NULL)
231 : continue;
232 :
233 543558 : HASHTYPE hashval = atomic_load_explicit(
234 : &htab->old_table[record_it].hashval,
235 : memory_order_acquire);
236 543558 : assert(hashval);
237 :
238 543558 : insert_helper(htab, hashval, val_ptr);
239 : }
240 :
241 12496 : num_finished_blocks++;
242 : }
243 :
244 12496 : atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
245 : memory_order_release);
246 :
247 12496 : if (blocking)
248 12496 : while (atomic_load_explicit(&htab->num_moved_blocks,
249 12496 : memory_order_acquire) != num_old_blocks);
250 12496 : }
251 :
252 : static void
253 12496 : resize_master(NAME *htab)
254 : {
255 12496 : htab->old_size = htab->size;
256 12496 : htab->old_table = htab->table;
257 :
258 12496 : htab->size = next_prime(htab->size * 2);
259 12496 : htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
260 12496 : assert(htab->table);
261 :
262 : /* Change state from ALLOCATING_MEMORY to MOVING_DATA */
263 12496 : atomic_fetch_xor_explicit(&htab->resizing_state,
264 : ALLOCATING_MEMORY ^ MOVING_DATA,
265 : memory_order_release);
266 :
267 12496 : resize_helper(htab, 1);
268 :
269 : /* Change state from MOVING_DATA to CLEANING */
270 12496 : size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
271 : MOVING_DATA ^ CLEANING,
272 : memory_order_acq_rel);
273 12496 : 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 12496 : atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
279 12496 : atomic_store_explicit(&htab->num_initialized_blocks, 0,
280 : memory_order_relaxed);
281 :
282 12496 : atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
283 12496 : atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
284 :
285 12496 : free(htab->old_table);
286 :
287 : /* Change state to NO_RESIZING */
288 12496 : atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
289 : memory_order_relaxed);
290 :
291 12496 : }
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 27364 : INIT(NAME) (NAME *htab, size_t init_size)
341 : {
342 : /* We need the size to be a prime. */
343 27364 : init_size = next_prime (init_size);
344 :
345 : /* Initialize the data structure. */
346 27364 : htab->size = init_size;
347 27364 : atomic_init(&htab->filled, 0);
348 27364 : atomic_init(&htab->resizing_state, 0);
349 :
350 27364 : atomic_init(&htab->next_init_block, 0);
351 27364 : atomic_init(&htab->num_initialized_blocks, 0);
352 :
353 27364 : atomic_init(&htab->next_move_block, 0);
354 27364 : atomic_init(&htab->num_moved_blocks, 0);
355 :
356 27364 : pthread_rwlock_init(&htab->resize_rwl, NULL);
357 :
358 27364 : htab->table = (void *) malloc ((init_size + 1) * sizeof (htab->table[0]));
359 27364 : if (htab->table == NULL)
360 : return -1;
361 :
362 1004242 : for (size_t i = 0; i <= init_size; i++)
363 : {
364 976878 : atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
365 976878 : 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 27364 : FREE(NAME) (NAME *htab)
377 : {
378 27364 : pthread_rwlock_destroy(&htab->resize_rwl);
379 27364 : free (htab->table);
380 27364 : return 0;
381 : }
382 :
383 :
384 : int
385 : #define INSERT(name) _INSERT (name)
386 : #define _INSERT(name) \
387 : name##_insert
388 747277 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
389 : {
390 747277 : int incremented = 0;
391 :
392 : for(;;)
393 : {
394 759773 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
395 0 : resize_worker(htab);
396 :
397 759773 : size_t filled;
398 759773 : if (!incremented)
399 : {
400 747277 : filled = atomic_fetch_add_explicit(&htab->filled, 1,
401 : memory_order_acquire);
402 747277 : incremented = 1;
403 : }
404 : else
405 : {
406 12496 : filled = atomic_load_explicit(&htab->filled,
407 : memory_order_acquire);
408 : }
409 :
410 :
411 759773 : if (100 * filled > 90 * htab->size)
412 : {
413 : /* Table is filled more than 90%. Resize the table. */
414 :
415 12496 : size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
416 : memory_order_acquire);
417 24992 : if (resizing_state == 0 &&
418 12496 : 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 12496 : pthread_rwlock_unlock(&htab->resize_rwl);
426 :
427 12496 : pthread_rwlock_wrlock(&htab->resize_rwl);
428 12496 : resize_master(htab);
429 12496 : 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 747277 : int ret_val = insert_helper(htab, hval, data);
447 747277 : if (ret_val == -1)
448 0 : atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
449 747277 : pthread_rwlock_unlock(&htab->resize_rwl);
450 747277 : return ret_val;
451 : }
452 :
453 :
454 :
455 : TYPE
456 : #define FIND(name) _FIND (name)
457 : #define _FIND(name) \
458 : name##_find
459 19143837 : FIND(NAME) (NAME *htab, HASHTYPE hval)
460 : {
461 19143837 : while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
462 0 : resize_worker(htab);
463 :
464 19143837 : size_t idx;
465 :
466 : /* Make the hash data nonzero. */
467 19143837 : hval = hval ?: 1;
468 19143837 : idx = lookup(htab, hval);
469 :
470 19143837 : if (idx == 0)
471 : {
472 1287009 : pthread_rwlock_unlock(&htab->resize_rwl);
473 1287009 : return NULL;
474 : }
475 :
476 : /* get a copy before unlocking the lock */
477 17856828 : TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
478 : memory_order_relaxed);
479 :
480 17856828 : pthread_rwlock_unlock(&htab->resize_rwl);
481 17856828 : return ret_val;
482 : }
|
