483 lines
14 KiB
C
483 lines
14 KiB
C
|
/* Copyright (C) 2000-2019 Red Hat, Inc.
|
||
|
|
This file is part of elfutils.
|
||
|
|
Written by Srdan Milakovic <sm108@rice.edu>, 2019.
|
||
|
|
Derived from Ulrich Drepper <drepper@redhat.com>, 2000.
|
||
|
|
|
||
|
|
This file is free software; you can redistribute it and/or modify
|
||
|
|
it under the terms of either
|
||
|
|
|
||
|
|
* the GNU Lesser General Public License as published by the Free
|
||
|
|
Software Foundation; either version 3 of the License, or (at
|
||
|
|
your option) any later version
|
||
|
|
|
||
|
|
or
|
||
|
|
|
||
|
|
* the GNU General Public License as published by the Free
|
||
|
|
Software Foundation; either version 2 of the License, or (at
|
||
|
|
your option) any later version
|
||
|
|
|
||
|
|
or both in parallel, as here.
|
||
|
|
|
||
|
|
elfutils is distributed in the hope that it will be useful, but
|
||
|
|
WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
||
|
|
General Public License for more details.
|
||
|
|
|
||
|
|
You should have received copies of the GNU General Public License and
|
||
|
|
the GNU Lesser General Public License along with this program. If
|
||
|
|
not, see <http://www.gnu.org/licenses/>. */
|
||
|
|
|
||
|
|
#include <assert.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <system.h>
|
||
|
|
#include <pthread.h>
|
||
|
|
|
||
|
|
/* Before including this file the following macros must be defined:
|
||
|
|
|
||
|
|
NAME name of the hash table structure.
|
||
|
|
TYPE data type of the hash table entries
|
||
|
|
*/
|
||
|
|
|
||
|
|
|
||
|
|
static size_t
|
||
|
|
lookup (NAME *htab, HASHTYPE hval)
|
||
|
|
{
|
||
|
|
/* First hash function: simply take the modul but prevent zero. Small values
|
||
|
|
can skip the division, which helps performance when this is common. */
|
||
|
|
size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
|
||
|
|
|
||
|
|
HASHTYPE hash;
|
||
|
|
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (hash == hval)
|
||
|
|
return idx;
|
||
|
|
else if (hash == 0)
|
||
|
|
return 0;
|
||
|
|
|
||
|
|
/* Second hash function as suggested in [Knuth]. */
|
||
|
|
HASHTYPE second_hash = 1 + hval % (htab->size - 2);
|
||
|
|
|
||
|
|
for(;;)
|
||
|
|
{
|
||
|
|
if (idx <= second_hash)
|
||
|
|
idx = htab->size + idx - second_hash;
|
||
|
|
else
|
||
|
|
idx -= second_hash;
|
||
|
|
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (hash == hval)
|
||
|
|
return idx;
|
||
|
|
else if (hash == 0)
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
static int
|
||
|
|
insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
|
||
|
|
{
|
||
|
|
/* First hash function: simply take the modul but prevent zero. Small values
|
||
|
|
can skip the division, which helps performance when this is common. */
|
||
|
|
size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
|
||
|
|
|
||
|
|
TYPE val_ptr;
|
||
|
|
HASHTYPE hash;
|
||
|
|
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (hash == hval)
|
||
|
|
return -1;
|
||
|
|
else if (hash == 0)
|
||
|
|
{
|
||
|
|
val_ptr = NULL;
|
||
|
|
atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
|
||
|
|
(uintptr_t *) &val_ptr,
|
||
|
|
(uintptr_t) val,
|
||
|
|
memory_order_acquire,
|
||
|
|
memory_order_acquire);
|
||
|
|
|
||
|
|
if (val_ptr == NULL)
|
||
|
|
{
|
||
|
|
atomic_store_explicit(&htab->table[idx].hashval, hval,
|
||
|
|
memory_order_release);
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
do
|
||
|
|
{
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
}
|
||
|
|
while (hash == 0);
|
||
|
|
if (hash == hval)
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Second hash function as suggested in [Knuth]. */
|
||
|
|
HASHTYPE second_hash = 1 + hval % (htab->size - 2);
|
||
|
|
|
||
|
|
for(;;)
|
||
|
|
{
|
||
|
|
if (idx <= second_hash)
|
||
|
|
idx = htab->size + idx - second_hash;
|
||
|
|
else
|
||
|
|
idx -= second_hash;
|
||
|
|
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (hash == hval)
|
||
|
|
return -1;
|
||
|
|
else if (hash == 0)
|
||
|
|
{
|
||
|
|
val_ptr = NULL;
|
||
|
|
atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
|
||
|
|
(uintptr_t *) &val_ptr,
|
||
|
|
(uintptr_t) val,
|
||
|
|
memory_order_acquire,
|
||
|
|
memory_order_acquire);
|
||
|
|
|
||
|
|
if (val_ptr == NULL)
|
||
|
|
{
|
||
|
|
atomic_store_explicit(&htab->table[idx].hashval, hval,
|
||
|
|
memory_order_release);
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
do
|
||
|
|
{
|
||
|
|
hash = atomic_load_explicit(&htab->table[idx].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
}
|
||
|
|
while (hash == 0);
|
||
|
|
if (hash == hval)
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
#define NO_RESIZING 0u
|
||
|
|
#define ALLOCATING_MEMORY 1u
|
||
|
|
#define MOVING_DATA 3u
|
||
|
|
#define CLEANING 2u
|
||
|
|
|
||
|
|
#define STATE_BITS 2u
|
||
|
|
#define STATE_INCREMENT (1u << STATE_BITS)
|
||
|
|
#define STATE_MASK (STATE_INCREMENT - 1)
|
||
|
|
#define GET_STATE(A) ((A) & STATE_MASK)
|
||
|
|
|
||
|
|
#define IS_NO_RESIZE_OR_CLEANING(A) (((A) & 0x1u) == 0)
|
||
|
|
|
||
|
|
#define GET_ACTIVE_WORKERS(A) ((A) >> STATE_BITS)
|
||
|
|
|
||
|
|
#define INITIALIZATION_BLOCK_SIZE 256
|
||
|
|
#define MOVE_BLOCK_SIZE 256
|
||
|
|
#define CEIL(A, B) (((A) + (B) - 1) / (B))
|
||
|
|
|
||
|
|
/* Initializes records and copies the data from the old table.
|
||
|
|
It can share work with other threads */
|
||
|
|
static void resize_helper(NAME *htab, int blocking)
|
||
|
|
{
|
||
|
|
size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
|
||
|
|
size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
|
||
|
|
|
||
|
|
size_t my_block;
|
||
|
|
size_t num_finished_blocks = 0;
|
||
|
|
|
||
|
|
while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
|
||
|
|
memory_order_acquire))
|
||
|
|
< num_new_blocks)
|
||
|
|
{
|
||
|
|
size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
|
||
|
|
size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
|
||
|
|
if (record_end > htab->size)
|
||
|
|
record_end = htab->size;
|
||
|
|
|
||
|
|
while (record_it++ != record_end)
|
||
|
|
{
|
||
|
|
atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
|
||
|
|
atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
|
||
|
|
}
|
||
|
|
|
||
|
|
num_finished_blocks++;
|
||
|
|
}
|
||
|
|
|
||
|
|
atomic_fetch_add_explicit(&htab->num_initialized_blocks,
|
||
|
|
num_finished_blocks, memory_order_release);
|
||
|
|
while (atomic_load_explicit(&htab->num_initialized_blocks,
|
||
|
|
memory_order_acquire) != num_new_blocks);
|
||
|
|
|
||
|
|
/* All block are initialized, start moving */
|
||
|
|
num_finished_blocks = 0;
|
||
|
|
while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
|
||
|
|
memory_order_acquire))
|
||
|
|
< num_old_blocks)
|
||
|
|
{
|
||
|
|
size_t record_it = my_block * MOVE_BLOCK_SIZE;
|
||
|
|
size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
|
||
|
|
if (record_end > htab->old_size)
|
||
|
|
record_end = htab->old_size;
|
||
|
|
|
||
|
|
while (record_it++ != record_end)
|
||
|
|
{
|
||
|
|
TYPE val_ptr = (TYPE) atomic_load_explicit(
|
||
|
|
&htab->old_table[record_it].val_ptr,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (val_ptr == NULL)
|
||
|
|
continue;
|
||
|
|
|
||
|
|
HASHTYPE hashval = atomic_load_explicit(
|
||
|
|
&htab->old_table[record_it].hashval,
|
||
|
|
memory_order_acquire);
|
||
|
|
assert(hashval);
|
||
|
|
|
||
|
|
insert_helper(htab, hashval, val_ptr);
|
||
|
|
}
|
||
|
|
|
||
|
|
num_finished_blocks++;
|
||
|
|
}
|
||
|
|
|
||
|
|
atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
|
||
|
|
memory_order_release);
|
||
|
|
|
||
|
|
if (blocking)
|
||
|
|
while (atomic_load_explicit(&htab->num_moved_blocks,
|
||
|
|
memory_order_acquire) != num_old_blocks);
|
||
|
|
}
|
||
|
|
|
||
|
|
static void
|
||
|
|
resize_master(NAME *htab)
|
||
|
|
{
|
||
|
|
htab->old_size = htab->size;
|
||
|
|
htab->old_table = htab->table;
|
||
|
|
|
||
|
|
htab->size = next_prime(htab->size * 2);
|
||
|
|
htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
|
||
|
|
assert(htab->table);
|
||
|
|
|
||
|
|
/* Change state from ALLOCATING_MEMORY to MOVING_DATA */
|
||
|
|
atomic_fetch_xor_explicit(&htab->resizing_state,
|
||
|
|
ALLOCATING_MEMORY ^ MOVING_DATA,
|
||
|
|
memory_order_release);
|
||
|
|
|
||
|
|
resize_helper(htab, 1);
|
||
|
|
|
||
|
|
/* Change state from MOVING_DATA to CLEANING */
|
||
|
|
size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
|
||
|
|
MOVING_DATA ^ CLEANING,
|
||
|
|
memory_order_acq_rel);
|
||
|
|
while (GET_ACTIVE_WORKERS(resize_state) != 0)
|
||
|
|
resize_state = atomic_load_explicit(&htab->resizing_state,
|
||
|
|
memory_order_acquire);
|
||
|
|
|
||
|
|
/* There are no more active workers */
|
||
|
|
atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
|
||
|
|
atomic_store_explicit(&htab->num_initialized_blocks, 0,
|
||
|
|
memory_order_relaxed);
|
||
|
|
|
||
|
|
atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
|
||
|
|
atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
|
||
|
|
|
||
|
|
free(htab->old_table);
|
||
|
|
|
||
|
|
/* Change state to NO_RESIZING */
|
||
|
|
atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
|
||
|
|
memory_order_relaxed);
|
||
|
|
|
||
|
|
}
|
||
|
|
|
||
|
|
static void
|
||
|
|
resize_worker(NAME *htab)
|
||
|
|
{
|
||
|
|
size_t resize_state = atomic_load_explicit(&htab->resizing_state,
|
||
|
|
memory_order_acquire);
|
||
|
|
|
||
|
|
/* If the resize has finished */
|
||
|
|
if (IS_NO_RESIZE_OR_CLEANING(resize_state))
|
||
|
|
return;
|
||
|
|
|
||
|
|
/* Register as worker and check if the resize has finished in the meantime*/
|
||
|
|
resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
|
||
|
|
STATE_INCREMENT,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (IS_NO_RESIZE_OR_CLEANING(resize_state))
|
||
|
|
{
|
||
|
|
atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
|
||
|
|
memory_order_relaxed);
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Wait while the new table is being allocated. */
|
||
|
|
while (GET_STATE(resize_state) == ALLOCATING_MEMORY)
|
||
|
|
resize_state = atomic_load_explicit(&htab->resizing_state,
|
||
|
|
memory_order_acquire);
|
||
|
|
|
||
|
|
/* Check if the resize is done */
|
||
|
|
assert(GET_STATE(resize_state) != NO_RESIZING);
|
||
|
|
if (GET_STATE(resize_state) == CLEANING)
|
||
|
|
{
|
||
|
|
atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
|
||
|
|
memory_order_relaxed);
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
resize_helper(htab, 0);
|
||
|
|
|
||
|
|
/* Deregister worker */
|
||
|
|
atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
|
||
|
|
memory_order_release);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int
|
||
|
|
#define INIT(name) _INIT (name)
|
||
|
|
#define _INIT(name) \
|
||
|
|
name##_init
|
||
|
|
INIT(NAME) (NAME *htab, size_t init_size)
|
||
|
|
{
|
||
|
|
/* We need the size to be a prime. */
|
||
|
|
init_size = next_prime (init_size);
|
||
|
|
|
||
|
|
/* Initialize the data structure. */
|
||
|
|
htab->size = init_size;
|
||
|
|
atomic_init(&htab->filled, 0);
|
||
|
|
atomic_init(&htab->resizing_state, 0);
|
||
|
|
|
||
|
|
atomic_init(&htab->next_init_block, 0);
|
||
|
|
atomic_init(&htab->num_initialized_blocks, 0);
|
||
|
|
|
||
|
|
atomic_init(&htab->next_move_block, 0);
|
||
|
|
atomic_init(&htab->num_moved_blocks, 0);
|
||
|
|
|
||
|
|
pthread_rwlock_init(&htab->resize_rwl, NULL);
|
||
|
|
|
||
|
|
htab->table = (void *) malloc ((init_size + 1) * sizeof (htab->table[0]));
|
||
|
|
if (htab->table == NULL)
|
||
|
|
return -1;
|
||
|
|
|
||
|
|
for (size_t i = 0; i <= init_size; i++)
|
||
|
|
{
|
||
|
|
atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
|
||
|
|
atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL);
|
||
|
|
}
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int
|
||
|
|
#define FREE(name) _FREE (name)
|
||
|
|
#define _FREE(name) \
|
||
|
|
name##_free
|
||
|
|
FREE(NAME) (NAME *htab)
|
||
|
|
{
|
||
|
|
pthread_rwlock_destroy(&htab->resize_rwl);
|
||
|
|
free (htab->table);
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int
|
||
|
|
#define INSERT(name) _INSERT (name)
|
||
|
|
#define _INSERT(name) \
|
||
|
|
name##_insert
|
||
|
|
INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
|
||
|
|
{
|
||
|
|
int incremented = 0;
|
||
|
|
|
||
|
|
for(;;)
|
||
|
|
{
|
||
|
|
while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
|
||
|
|
resize_worker(htab);
|
||
|
|
|
||
|
|
size_t filled;
|
||
|
|
if (!incremented)
|
||
|
|
{
|
||
|
|
filled = atomic_fetch_add_explicit(&htab->filled, 1,
|
||
|
|
memory_order_acquire);
|
||
|
|
incremented = 1;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
filled = atomic_load_explicit(&htab->filled,
|
||
|
|
memory_order_acquire);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
if (100 * filled > 90 * htab->size)
|
||
|
|
{
|
||
|
|
/* Table is filled more than 90%. Resize the table. */
|
||
|
|
|
||
|
|
size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
|
||
|
|
memory_order_acquire);
|
||
|
|
if (resizing_state == 0 &&
|
||
|
|
atomic_compare_exchange_strong_explicit(&htab->resizing_state,
|
||
|
|
&resizing_state,
|
||
|
|
ALLOCATING_MEMORY,
|
||
|
|
memory_order_acquire,
|
||
|
|
memory_order_acquire))
|
||
|
|
{
|
||
|
|
/* Master thread */
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
|
||
|
|
pthread_rwlock_wrlock(&htab->resize_rwl);
|
||
|
|
resize_master(htab);
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
/* Worker thread */
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
resize_worker(htab);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
/* Lock acquired, no need for resize*/
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int ret_val = insert_helper(htab, hval, data);
|
||
|
|
if (ret_val == -1)
|
||
|
|
atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
return ret_val;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
TYPE
|
||
|
|
#define FIND(name) _FIND (name)
|
||
|
|
#define _FIND(name) \
|
||
|
|
name##_find
|
||
|
|
FIND(NAME) (NAME *htab, HASHTYPE hval)
|
||
|
|
{
|
||
|
|
while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
|
||
|
|
resize_worker(htab);
|
||
|
|
|
||
|
|
size_t idx;
|
||
|
|
|
||
|
|
/* Make the hash data nonzero. */
|
||
|
|
hval = hval ?: 1;
|
||
|
|
idx = lookup(htab, hval);
|
||
|
|
|
||
|
|
if (idx == 0)
|
||
|
|
{
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
return NULL;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* get a copy before unlocking the lock */
|
||
|
|
TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
|
||
|
|
memory_order_relaxed);
|
||
|
|
|
||
|
|
pthread_rwlock_unlock(&htab->resize_rwl);
|
||
|
|
return ret_val;
|
||
|
|
}
|