path: root/lib/dynamicsizehash_concurrent.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;
}