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 42static size_t 43lookup (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 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 77static int 78insert_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 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. */ 184static 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. */ 258static void 259resize_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. */ 303static void 304resize_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 346int 347#define INIT(name) _INIT (name) 348#define _INIT(name) \ 349 name##_init 350INIT(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 382int 383#define FREE(name) _FREE (name) 384#define _FREE(name) \ 385name##_free 386FREE(NAME) (NAME *htab) 387{ 388 pthread_rwlock_destroy(&htab->resize_rwl); 389 free (htab->table); 390 return 0; 391} 392 393 394int 395#define INSERT(name) _INSERT (name) 396#define _INSERT(name) \ 397name##_insert 398INSERT(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 467TYPE 468#define FIND(name) _FIND (name) 469#define _FIND(name) \ 470 name##_find 471FIND(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