1 /* Copyright (C) 2000-2019 Red Hat, Inc.
2 This file is part of elfutils.
3 Written by Srdan Milakovic <[email protected]>, 2019.
4 Derived from Ulrich Drepper <[email protected]>, 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
lookup(NAME * htab,HASHTYPE hval)43 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 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
48
49 HASHTYPE hash;
50
51 hash = atomic_load_explicit(&htab->table[idx].hashval,
52 memory_order_acquire);
53 if (hash == hval)
54 return idx;
55 else if (hash == 0)
56 return 0;
57
58 /* Second hash function as suggested in [Knuth]. */
59 HASHTYPE second_hash = 1 + hval % (htab->size - 2);
60
61 for(;;)
62 {
63 if (idx <= second_hash)
64 idx = htab->size + idx - second_hash;
65 else
66 idx -= second_hash;
67
68 hash = atomic_load_explicit(&htab->table[idx].hashval,
69 memory_order_acquire);
70 if (hash == hval)
71 return idx;
72 else if (hash == 0)
73 return 0;
74 }
75 }
76
77 static int
insert_helper(NAME * htab,HASHTYPE hval,TYPE val)78 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 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
83
84 TYPE val_ptr;
85 HASHTYPE hash;
86
87 hash = atomic_load_explicit(&htab->table[idx].hashval,
88 memory_order_acquire);
89 if (hash == hval)
90 return -1;
91 else if (hash == 0)
92 {
93 val_ptr = NULL;
94 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 if (val_ptr == NULL)
101 {
102 atomic_store_explicit(&htab->table[idx].hashval, hval,
103 memory_order_release);
104 return 0;
105 }
106 else
107 {
108 do
109 {
110 hash = atomic_load_explicit(&htab->table[idx].hashval,
111 memory_order_acquire);
112 }
113 while (hash == 0);
114 if (hash == hval)
115 return -1;
116 }
117 }
118
119 /* Second hash function as suggested in [Knuth]. */
120 HASHTYPE second_hash = 1 + hval % (htab->size - 2);
121
122 for(;;)
123 {
124 if (idx <= second_hash)
125 idx = htab->size + idx - second_hash;
126 else
127 idx -= second_hash;
128
129 hash = atomic_load_explicit(&htab->table[idx].hashval,
130 memory_order_acquire);
131 if (hash == hval)
132 return -1;
133 else if (hash == 0)
134 {
135 val_ptr = NULL;
136 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 if (val_ptr == NULL)
143 {
144 atomic_store_explicit(&htab->table[idx].hashval, hval,
145 memory_order_release);
146 return 0;
147 }
148 else
149 {
150 do
151 {
152 hash = atomic_load_explicit(&htab->table[idx].hashval,
153 memory_order_acquire);
154 }
155 while (hash == 0);
156 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. */
resize_helper(NAME * htab,int blocking)184 static void resize_helper(NAME *htab, int blocking)
185 {
186 size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
187 size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
188
189 size_t my_block;
190 size_t num_finished_blocks = 0;
191
192 while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
193 memory_order_acquire))
194 < num_new_blocks)
195 {
196 size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
197 size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
198 if (record_end > htab->size)
199 record_end = htab->size;
200
201 while (record_it++ != record_end)
202 {
203 atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
204 atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
205 }
206
207 num_finished_blocks++;
208 }
209
210 atomic_fetch_add_explicit(&htab->num_initialized_blocks,
211 num_finished_blocks, memory_order_release);
212 while (atomic_load_explicit(&htab->num_initialized_blocks,
213 memory_order_acquire) != num_new_blocks);
214
215 /* All block are initialized, start moving */
216 num_finished_blocks = 0;
217 while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
218 memory_order_acquire))
219 < num_old_blocks)
220 {
221 size_t record_it = my_block * MOVE_BLOCK_SIZE;
222 size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
223 if (record_end > htab->old_size)
224 record_end = htab->old_size;
225
226 while (record_it++ != record_end)
227 {
228 TYPE val_ptr = (TYPE) atomic_load_explicit(
229 &htab->old_table[record_it].val_ptr,
230 memory_order_acquire);
231 if (val_ptr == NULL)
232 continue;
233
234 HASHTYPE hashval = atomic_load_explicit(
235 &htab->old_table[record_it].hashval,
236 memory_order_acquire);
237 assert(hashval);
238
239 insert_helper(htab, hashval, val_ptr);
240 }
241
242 num_finished_blocks++;
243 }
244
245 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 if (blocking)
251 while (atomic_load_explicit(&htab->num_moved_blocks,
252 memory_order_acquire) != num_old_blocks);
253 }
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
resize_coordinator(NAME * htab)259 resize_coordinator(NAME *htab)
260 {
261 htab->old_size = htab->size;
262 htab->old_table = htab->table;
263
264 htab->size = next_prime(htab->size * 2);
265 htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
266 assert(htab->table);
267
268 /* Change state from ALLOCATING_MEMORY to MOVING_DATA */
269 atomic_fetch_xor_explicit(&htab->resizing_state,
270 ALLOCATING_MEMORY ^ MOVING_DATA,
271 memory_order_release);
272
273 resize_helper(htab, 1);
274
275 /* Change state from MOVING_DATA to CLEANING */
276 size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
277 MOVING_DATA ^ CLEANING,
278 memory_order_acq_rel);
279 while (GET_ACTIVE_WORKERS(resize_state) != 0)
280 resize_state = atomic_load_explicit(&htab->resizing_state,
281 memory_order_acquire);
282
283 /* There are no more active workers */
284 atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
285 atomic_store_explicit(&htab->num_initialized_blocks, 0,
286 memory_order_relaxed);
287
288 atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
289 atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
290
291 free(htab->old_table);
292
293 /* Change state to NO_RESIZING */
294 atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
295 memory_order_relaxed);
296
297 }
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
resize_worker(NAME * htab)304 resize_worker(NAME *htab)
305 {
306 size_t resize_state = atomic_load_explicit(&htab->resizing_state,
307 memory_order_acquire);
308
309 /* If the resize has finished */
310 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 resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
315 STATE_INCREMENT,
316 memory_order_acquire);
317 if (IS_NO_RESIZE_OR_CLEANING(resize_state))
318 {
319 atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
320 memory_order_relaxed);
321 return;
322 }
323
324 /* Wait while the new table is being allocated. */
325 while (GET_STATE(resize_state) == ALLOCATING_MEMORY)
326 resize_state = atomic_load_explicit(&htab->resizing_state,
327 memory_order_acquire);
328
329 /* Check if the resize is done */
330 assert(GET_STATE(resize_state) != NO_RESIZING);
331 if (GET_STATE(resize_state) == CLEANING)
332 {
333 atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
334 memory_order_relaxed);
335 return;
336 }
337
338 resize_helper(htab, 0);
339
340 /* Deregister worker */
341 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
INIT(NAME)350 INIT(NAME) (NAME *htab, size_t init_size)
351 {
352 /* We need the size to be a prime. */
353 init_size = next_prime (init_size);
354
355 /* Initialize the data structure. */
356 htab->size = init_size;
357 atomic_init(&htab->filled, 0);
358 atomic_init(&htab->resizing_state, 0);
359
360 atomic_init(&htab->next_init_block, 0);
361 atomic_init(&htab->num_initialized_blocks, 0);
362
363 atomic_init(&htab->next_move_block, 0);
364 atomic_init(&htab->num_moved_blocks, 0);
365
366 pthread_rwlock_init(&htab->resize_rwl, NULL);
367
368 htab->table = malloc ((init_size + 1) * sizeof (htab->table[0]));
369 if (htab->table == NULL)
370 return -1;
371
372 for (size_t i = 0; i <= init_size; i++)
373 {
374 atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
375 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
FREE(NAME)386 FREE(NAME) (NAME *htab)
387 {
388 pthread_rwlock_destroy(&htab->resize_rwl);
389 free (htab->table);
390 return 0;
391 }
392
393
394 int
395 #define INSERT(name) _INSERT (name)
396 #define _INSERT(name) \
397 name##_insert
INSERT(NAME)398 INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
399 {
400 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 while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
407 resize_worker(htab);
408
409 size_t filled;
410 if (!incremented)
411 {
412 filled = atomic_fetch_add_explicit(&htab->filled, 1,
413 memory_order_acquire);
414 incremented = 1;
415 }
416 else
417 {
418 filled = atomic_load_explicit(&htab->filled,
419 memory_order_acquire);
420 }
421
422
423 if (100 * filled > 90 * htab->size)
424 {
425 /* Table is filled more than 90%. Resize the table. */
426
427 size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
428 memory_order_acquire);
429 if (resizing_state == 0 &&
430 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 pthread_rwlock_unlock(&htab->resize_rwl);
438
439 pthread_rwlock_wrlock(&htab->resize_rwl);
440 resize_coordinator(htab);
441 pthread_rwlock_unlock(&htab->resize_rwl);
442
443 }
444 else
445 {
446 /* Worker thread, will help moving data. */
447 pthread_rwlock_unlock(&htab->resize_rwl);
448 resize_worker(htab);
449 }
450 }
451 else
452 {
453 /* Lock acquired, no need for resize*/
454 break;
455 }
456 }
457
458 int ret_val = insert_helper(htab, hval, data);
459 if (ret_val == -1)
460 atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
461 pthread_rwlock_unlock(&htab->resize_rwl);
462 return ret_val;
463 }
464
465
466
467 TYPE
468 #define FIND(name) _FIND (name)
469 #define _FIND(name) \
470 name##_find
FIND(NAME)471 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 while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
476 resize_worker(htab);
477
478 size_t idx;
479
480 /* Make the hash data nonzero. */
481 hval = hval ?: 1;
482 idx = lookup(htab, hval);
483
484 if (idx == 0)
485 {
486 pthread_rwlock_unlock(&htab->resize_rwl);
487 return NULL;
488 }
489
490 /* get a copy before unlocking the lock */
491 TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
492 memory_order_relaxed);
493
494 pthread_rwlock_unlock(&htab->resize_rwl);
495 return ret_val;
496 }
497