crypto/hashtable/hashtable.c - third_party/openssl - Git at Google

 /*
  * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
  * in the file LICENSE in the source distribution or at
  * https://www.openssl.org/source/license.html
  *
  *
  *
  * Notes On hash table design and layout
  * This hashtable uses a hopscotch algorithm to do indexing.  The data structure
  * looks as follows:
  *
  *   hash          +--------------+
  *   value+------->+ HT_VALUE     |
  *      +          +--------------+
  *  +-------+
  *  |       |
  *  +---------------------------------------------------------+
  *  |       |       |       |       |                         |
  *  | entry | entry | entry | entry |                         |
  *  |       |       |       |       |                         |
  *  +---------------------------------------------------------+
  *  |                               |                         |
  *  |                               |                         |
  *  +---------------------------------------------------------+
  *  |              +                             +            +
  *  |        neighborhood[0]               neighborhood[1]    |
  *  |                                                         |
  *  |                                                         |
  *  +---------------------------------------------------------+
  *                              |
  *                              +
  *                         neighborhoods
  *
  * On lookup/insert/delete, the items key is hashed to a 64 bit value
  * and the result is masked to provide an index into the neighborhoods
  * table.  Once a neighborhood is determined, an in-order search is done
  * of the elements in the neighborhood indexes entries for a matching hash
  * value, if found, the corresponding HT_VALUE is used for the respective
  * operation.  The number of entries in a neighborhood is determined at build
  * time based on the cacheline size of the target CPU.  The intent is for a
  * neighborhood to have all entries in the neighborhood fit into a single cache
  * line to speed up lookups.  If all entries in a neighborhood are in use at the
  * time of an insert, the table is expanded and rehashed.
  *
  * Lockless reads hash table is based on the same design but does not
  * allow growing and deletion. Thus subsequent neighborhoods are always
  * searched for a match until an empty entry is found.
  */

 #include <string.h>
 #include <internal/rcu.h>
 #include <internal/hashtable.h>
 #include <internal/hashfunc.h>
 #include <openssl/rand.h>

 /*
  * gcc defines __SANITIZE_THREAD__
  * but clang uses the feature attributes api
  * map the latter to the former
  */
 #if defined(__clang__) && defined(__has_feature)
 # if __has_feature(thread_sanitizer)
 #  define __SANITIZE_THREADS__
 # endif
 #endif

 #ifdef __SANITIZE_THREADS__
 # include <sanitizer/tsan_interface.h>
 #endif

 #include "internal/numbers.h"
 /*
  * When we do a lookup/insert/delete, there is a high likelihood
  * that we will iterate over at least part of the neighborhood list
  * As such, because we design a neighborhood entry to fit into a single
  * cache line it is advantageous, when supported to fetch the entire
  * structure for faster lookups
  */
 #if defined(__GNUC__) || defined(__CLANG__)
 # define PREFETCH_NEIGHBORHOOD(x) __builtin_prefetch(x.entries)
 # define PREFETCH(x) __builtin_prefetch(x)
 #else
 # define PREFETCH_NEIGHBORHOOD(x)
 # define PREFETCH(x)
 #endif

 /*
  * Define our neighborhood list length
  * Note: It should always be a power of 2
  */
 #define DEFAULT_NEIGH_LEN_LOG 4
 #define DEFAULT_NEIGH_LEN (1 << DEFAULT_NEIGH_LEN_LOG)

 /*
  * For now assume cache line size is 64 bytes
  */
 #define CACHE_LINE_BYTES 64
 #define CACHE_LINE_ALIGNMENT CACHE_LINE_BYTES

 #define NEIGHBORHOOD_LEN (CACHE_LINE_BYTES / sizeof(struct ht_neighborhood_entry_st))
 /*
  * Defines our chains of values
  */
 struct ht_internal_value_st {
     HT_VALUE value;
     HT *ht;
 };

 struct ht_neighborhood_entry_st {
     uint64_t hash;
     struct ht_internal_value_st *value;
 };

 struct ht_neighborhood_st {
     struct ht_neighborhood_entry_st entries[NEIGHBORHOOD_LEN];
 };

 /*
  * Updates to data in this struct
  * require an rcu sync after modification
  * prior to free
  */
 struct ht_mutable_data_st {
     struct ht_neighborhood_st *neighborhoods;
     void *neighborhood_ptr_to_free;
     uint64_t neighborhood_mask;
 };

 /*
  * Private data may be updated on the write
  * side only, and so do not require rcu sync
  */
 struct ht_write_private_data_st {
     size_t neighborhood_len;
     size_t value_count;
     int need_sync;
 };

 struct ht_internal_st {
     HT_CONFIG config;
     CRYPTO_RCU_LOCK *lock;
     CRYPTO_RWLOCK *atomic_lock;
     struct ht_mutable_data_st *md;
     struct ht_write_private_data_st wpd;
 };

 static void free_value(struct ht_internal_value_st *v);

 static struct ht_neighborhood_st *alloc_new_neighborhood_list(size_t len,
                                                               void **freeptr)
 {
     struct ht_neighborhood_st *ret;

     ret = OPENSSL_aligned_alloc(sizeof(struct ht_neighborhood_st) * len,
                                 CACHE_LINE_BYTES, freeptr);

     /* fall back to regular malloc */
     if (ret == NULL) {
         ret = *freeptr = OPENSSL_malloc(sizeof(struct ht_neighborhood_st) * len);
         if (ret == NULL)
             return NULL;
     }
     memset(ret, 0, sizeof(struct ht_neighborhood_st) * len);
     return ret;
 }

 static void internal_free_nop(HT_VALUE *v)
 {
     return;
 }

 HT *ossl_ht_new(const HT_CONFIG *conf)
 {
     HT *new = OPENSSL_zalloc(sizeof(*new));

     if (new == NULL)
         return NULL;

     new->atomic_lock = CRYPTO_THREAD_lock_new();
     if (new->atomic_lock == NULL)
         goto err;

     memcpy(&new->config, conf, sizeof(*conf));

     if (new->config.init_neighborhoods != 0) {
         new->wpd.neighborhood_len = new->config.init_neighborhoods;
         /* round up to the next power of 2 */
         new->wpd.neighborhood_len--;
         new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 1;
         new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 2;
         new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 4;
         new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 8;
         new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 16;
         new->wpd.neighborhood_len++;
     } else {
         new->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;
     }

     if (new->config.ht_free_fn == NULL)
         new->config.ht_free_fn = internal_free_nop;

     new->md = OPENSSL_zalloc(sizeof(*new->md));
     if (new->md == NULL)
         goto err;

     new->md->neighborhoods =
         alloc_new_neighborhood_list(new->wpd.neighborhood_len,
                                     &new->md->neighborhood_ptr_to_free);
     if (new->md->neighborhoods == NULL)
         goto err;
     new->md->neighborhood_mask = new->wpd.neighborhood_len - 1;

     new->lock = ossl_rcu_lock_new(1, conf->ctx);
     if (new->lock == NULL)
         goto err;

     if (new->config.ht_hash_fn == NULL)
         new->config.ht_hash_fn = ossl_fnv1a_hash;

     return new;

 err:
     CRYPTO_THREAD_lock_free(new->atomic_lock);
     ossl_rcu_lock_free(new->lock);
     if (new->md != NULL)
         OPENSSL_free(new->md->neighborhood_ptr_to_free);
     OPENSSL_free(new->md);
     OPENSSL_free(new);
     return NULL;
 }

 void ossl_ht_read_lock(HT *htable)
 {
     ossl_rcu_read_lock(htable->lock);
 }

 void ossl_ht_read_unlock(HT *htable)
 {
     ossl_rcu_read_unlock(htable->lock);
 }

 void ossl_ht_write_lock(HT *htable)
 {
     ossl_rcu_write_lock(htable->lock);
     htable->wpd.need_sync = 0;
 }

 void ossl_ht_write_unlock(HT *htable)
 {
     int need_sync = htable->wpd.need_sync;

     htable->wpd.need_sync = 0;
     ossl_rcu_write_unlock(htable->lock);
     if (need_sync)
         ossl_synchronize_rcu(htable->lock);
 }

 static void free_oldmd(void *arg)
 {
     struct ht_mutable_data_st *oldmd = arg;
     size_t i, j;
     size_t neighborhood_len = (size_t)oldmd->neighborhood_mask + 1;
     struct ht_internal_value_st *v;

     for (i = 0; i < neighborhood_len; i++) {
         PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[i + 1]);
         for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
             if (oldmd->neighborhoods[i].entries[j].value != NULL) {
                 v = oldmd->neighborhoods[i].entries[j].value;
                 v->ht->config.ht_free_fn((HT_VALUE *)v);
                 free_value(v);
             }
         }
     }

     OPENSSL_free(oldmd->neighborhood_ptr_to_free);
     OPENSSL_free(oldmd);
 }

 static int ossl_ht_flush_internal(HT *h)
 {
     struct ht_mutable_data_st *newmd = NULL;
     struct ht_mutable_data_st *oldmd = NULL;

     newmd = OPENSSL_zalloc(sizeof(*newmd));
     if (newmd == NULL)
         return 0;

     newmd->neighborhoods = alloc_new_neighborhood_list(DEFAULT_NEIGH_LEN,
                                                        &newmd->neighborhood_ptr_to_free);
     if (newmd->neighborhoods == NULL) {
         OPENSSL_free(newmd);
         return 0;
     }

     newmd->neighborhood_mask = DEFAULT_NEIGH_LEN - 1;

     /* Swap the old and new mutable data sets */
     oldmd = ossl_rcu_deref(&h->md);
     ossl_rcu_assign_ptr(&h->md, &newmd);

     /* Set the number of entries to 0 */
     h->wpd.value_count = 0;
     h->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;

     ossl_rcu_call(h->lock, free_oldmd, oldmd);
     h->wpd.need_sync = 1;
     return 1;
 }

 int ossl_ht_flush(HT *h)
 {
     return ossl_ht_flush_internal(h);
 }

 void ossl_ht_free(HT *h)
 {
     if (h == NULL)
         return;

     ossl_ht_write_lock(h);
     ossl_ht_flush_internal(h);
     ossl_ht_write_unlock(h);
     /* Freeing the lock does a final sync for us */
     CRYPTO_THREAD_lock_free(h->atomic_lock);
     ossl_rcu_lock_free(h->lock);
     OPENSSL_free(h->md->neighborhood_ptr_to_free);
     OPENSSL_free(h->md);
     OPENSSL_free(h);
     return;
 }

 size_t ossl_ht_count(HT *h)
 {
     size_t count;

     count = h->wpd.value_count;
     return count;
 }

 void ossl_ht_foreach_until(HT *h, int (*cb)(HT_VALUE *obj, void *arg),
                            void *arg)
 {
     size_t i, j;
     struct ht_mutable_data_st *md;

     md = ossl_rcu_deref(&h->md);
     for (i = 0; i < md->neighborhood_mask + 1; i++) {
         PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
         for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
             if (md->neighborhoods[i].entries[j].value != NULL) {
                 if (!cb((HT_VALUE *)md->neighborhoods[i].entries[j].value, arg))
                     goto out;
             }
         }
     }
 out:
     return;
 }

 HT_VALUE_LIST *ossl_ht_filter(HT *h, size_t max_len,
                                      int (*filter)(HT_VALUE *obj, void *arg),
                                      void *arg)
 {
     struct ht_mutable_data_st *md;
     HT_VALUE_LIST *list = OPENSSL_zalloc(sizeof(HT_VALUE_LIST)
                                          + (sizeof(HT_VALUE *) * max_len));
     size_t i, j;
     struct ht_internal_value_st *v;

     if (list == NULL)
         return NULL;

     /*
      * The list array lives just beyond the end of
      * the struct
      */
     list->list = (HT_VALUE **)(list + 1);

     md = ossl_rcu_deref(&h->md);
     for (i = 0; i < md->neighborhood_mask + 1; i++) {
         PREFETCH_NEIGHBORHOOD(md->neighborhoods[i+1]);
         for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
             v = md->neighborhoods[i].entries[j].value;
             if (v != NULL && filter((HT_VALUE *)v, arg)) {
                 list->list[list->list_len++] = (HT_VALUE *)v;
                 if (list->list_len == max_len)
                     goto out;
             }
         }
     }
 out:
     return list;
 }

 void ossl_ht_value_list_free(HT_VALUE_LIST *list)
 {
     OPENSSL_free(list);
 }

 static int compare_hash(uint64_t hash1, uint64_t hash2)
 {
     return (hash1 == hash2);
 }

 static void free_old_neigh_table(void *arg)
 {
     struct ht_mutable_data_st *oldmd = arg;

     OPENSSL_free(oldmd->neighborhood_ptr_to_free);
     OPENSSL_free(oldmd);
 }

 /*
  * Increase hash table bucket list
  * must be called with write_lock held
  */
 static int grow_hashtable(HT *h, size_t oldsize)
 {
     struct ht_mutable_data_st *newmd;
     struct ht_mutable_data_st *oldmd = ossl_rcu_deref(&h->md);
     int rc = 0;
     uint64_t oldi, oldj, newi, newj;
     uint64_t oldhash;
     struct ht_internal_value_st *oldv;
     int rehashed;
     size_t newsize = oldsize * 2;

     if (h->config.lockless_reads)
         goto out;

     if ((newmd = OPENSSL_zalloc(sizeof(*newmd))) == NULL)
         goto out;

     /* bucket list is always a power of 2 */
     newmd->neighborhoods = alloc_new_neighborhood_list(oldsize * 2,
                                                        &newmd->neighborhood_ptr_to_free);
     if (newmd->neighborhoods == NULL)
         goto out_free;

     /* being a power of 2 makes for easy mask computation */
     newmd->neighborhood_mask = (newsize - 1);

     /*
      * Now we need to start rehashing entries
      * Note we don't need to use atomics here as the new
      * mutable data hasn't been published
      */
     for (oldi = 0; oldi < h->wpd.neighborhood_len; oldi++) {
         PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[oldi + 1]);
         for (oldj = 0; oldj < NEIGHBORHOOD_LEN; oldj++) {
             oldv = oldmd->neighborhoods[oldi].entries[oldj].value;
             if (oldv == NULL)
                 continue;
             oldhash = oldmd->neighborhoods[oldi].entries[oldj].hash;
             newi = oldhash & newmd->neighborhood_mask;
             rehashed = 0;
             for (newj = 0; newj < NEIGHBORHOOD_LEN; newj++) {
                 if (newmd->neighborhoods[newi].entries[newj].value == NULL) {
                     newmd->neighborhoods[newi].entries[newj].value = oldv;
                     newmd->neighborhoods[newi].entries[newj].hash = oldhash;
                     rehashed = 1;
                     break;
                 }
             }
             if (rehashed == 0) {
                 /* we ran out of space in a neighborhood, grow again */
                 OPENSSL_free(newmd->neighborhoods);
                 OPENSSL_free(newmd);
                 return grow_hashtable(h, newsize);
             }
         }
     }
     /*
      * Now that our entries are all hashed into the new bucket list
      * update our bucket_len and target_max_load
      */
     h->wpd.neighborhood_len = newsize;

     /*
      * Now we replace the old mutable data with the new
      */
     ossl_rcu_assign_ptr(&h->md, &newmd);
     ossl_rcu_call(h->lock, free_old_neigh_table, oldmd);
     h->wpd.need_sync = 1;
     /*
      * And we're done
      */
     rc = 1;

 out:
     return rc;
 out_free:
     OPENSSL_free(newmd->neighborhoods);
     OPENSSL_free(newmd);
     goto out;
 }

 static void free_old_ht_value(void *arg)
 {
     HT_VALUE *h = (HT_VALUE *)arg;

     /*
      * Note, this is only called on replacement,
      * the caller is responsible for freeing the
      * held data, we just need to free the wrapping
      * struct here
      */
     OPENSSL_free(h);
 }

 static ossl_inline int match_key(HT_KEY *a, HT_KEY *b)
 {
     /*
      * keys match if they are both present, the same size
      * and compare equal in memory
      */
     PREFETCH(a->keybuf);
     PREFETCH(b->keybuf);
     if (a->keybuf != NULL && b->keybuf != NULL && a->keysize == b->keysize)
         return !memcmp(a->keybuf, b->keybuf, a->keysize);

     return 1;
 }

 static int ossl_ht_insert_locked(HT *h, uint64_t hash,
                                  struct ht_internal_value_st *newval,
                                  HT_VALUE **olddata)
 {
     struct ht_mutable_data_st *md = h->md;
     uint64_t neigh_idx_start = hash & md->neighborhood_mask;
     uint64_t neigh_idx = neigh_idx_start;
     size_t j;
     uint64_t ihash;
     HT_VALUE *ival;
     size_t empty_idx = SIZE_MAX;
     int lockless_reads = h->config.lockless_reads;

     do {
         PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);

         for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
             ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
             if (ival == NULL) {
                 empty_idx = j;
                 /* lockless_reads implies no deletion, we can break out */
                 if (lockless_reads)
                     goto not_found;
                 continue;
             }
             if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
                                     &ihash, h->atomic_lock))
                 return 0;
             if (compare_hash(hash, ihash) && match_key(&newval->value.key,
                                                        &ival->key)) {
                 if (olddata == NULL) {
                     /* This would insert a duplicate -> fail */
                     return 0;
                 }
                 /* Do a replacement */
                 if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[j].hash,
                                          hash, h->atomic_lock))
                     return 0;
                 *olddata = (HT_VALUE *)md->neighborhoods[neigh_idx].entries[j].value;
                 ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[j].value,
                                     &newval);
                 ossl_rcu_call(h->lock, free_old_ht_value, *olddata);
                 h->wpd.need_sync = 1;
                 return 1;
             }
         }
         if (!lockless_reads)
             break;
         /* Continue search in subsequent neighborhoods */
         neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
     } while (neigh_idx != neigh_idx_start);

  not_found:
     /* If we get to here, its just an insert */
     if (empty_idx == SIZE_MAX)
         return -1; /* out of space */
     if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[empty_idx].hash,
                              hash, h->atomic_lock))
         return 0;
     h->wpd.value_count++;
     ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[empty_idx].value,
                         &newval);
     return 1;
 }

 static struct ht_internal_value_st *alloc_new_value(HT *h, HT_KEY *key,
                                                     void *data,
                                                     uintptr_t *type)
 {
     struct ht_internal_value_st *tmp;
     size_t nvsize = sizeof(*tmp);

     if (h->config.collision_check == 1)
         nvsize += key->keysize;

     tmp = OPENSSL_malloc(nvsize);

     if (tmp == NULL)
         return NULL;

     tmp->ht = h;
     tmp->value.value = data;
     tmp->value.type_id = type;
     tmp->value.key.keybuf = NULL;
     if (h->config.collision_check) {
         tmp->value.key.keybuf = (uint8_t *)(tmp + 1);
         tmp->value.key.keysize = key->keysize;
         memcpy(tmp->value.key.keybuf, key->keybuf, key->keysize);
     }


     return tmp;
 }

 static void free_value(struct ht_internal_value_st *v)
 {
     OPENSSL_free(v);
 }

 int ossl_ht_insert(HT *h, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata)
 {
     struct ht_internal_value_st *newval = NULL;
     uint64_t hash;
     int rc = 0;
     int i;

     if (data->value == NULL)
         goto out;

     newval = alloc_new_value(h, key, data->value, data->type_id);
     if (newval == NULL)
         goto out;

     /*
      * we have to take our lock here to prevent other changes
      * to the bucket list
      */
     hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

     for (i = 0;
          (rc = ossl_ht_insert_locked(h, hash, newval, olddata)) == -1
          && i < 4;
          ++i)
         if (!grow_hashtable(h, h->wpd.neighborhood_len)) {
             rc = -1;
             break;
         }

     if (rc <= 0)
         free_value(newval);

 out:
     return rc;
 }

 HT_VALUE *ossl_ht_get(HT *h, HT_KEY *key)
 {
     struct ht_mutable_data_st *md;
     uint64_t hash;
     uint64_t neigh_idx_start;
     uint64_t neigh_idx;
     struct ht_internal_value_st *ival = NULL;
     size_t j;
     uint64_t ehash;
     int lockless_reads = h->config.lockless_reads;

     hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

     md = ossl_rcu_deref(&h->md);
     neigh_idx = neigh_idx_start = hash & md->neighborhood_mask;
     do {
         PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
         for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
             ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
             if (ival == NULL) {
                 if (lockless_reads)
                     /* lockless_reads implies no deletion, we can break out */
                     return NULL;
                 continue;
             }
             if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
                                     &ehash, h->atomic_lock))
                 return NULL;
             if (compare_hash(hash, ehash) && match_key(&ival->value.key, key))
                 return (HT_VALUE *)ival;
         }
         if (!lockless_reads)
             break;
         /* Continue search in subsequent neighborhoods */
         neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
     } while (neigh_idx != neigh_idx_start);

     return NULL;
 }

 static void free_old_entry(void *arg)
 {
     struct ht_internal_value_st *v = arg;

     v->ht->config.ht_free_fn((HT_VALUE *)v);
     free_value(v);
 }

 int ossl_ht_delete(HT *h, HT_KEY *key)
 {
     uint64_t hash;
     uint64_t neigh_idx;
     size_t j;
     struct ht_internal_value_st *v = NULL;
     HT_VALUE *nv = NULL;
     int rc = 0;

     if (h->config.lockless_reads)
         return 0;

     hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

     neigh_idx = hash & h->md->neighborhood_mask;
     PREFETCH_NEIGHBORHOOD(h->md->neighborhoods[neigh_idx]);
     for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
         v = (struct ht_internal_value_st *)h->md->neighborhoods[neigh_idx].entries[j].value;
         if (v == NULL)
             continue;
         if (compare_hash(hash, h->md->neighborhoods[neigh_idx].entries[j].hash)
             && match_key(key, &v->value.key)) {
             if (!CRYPTO_atomic_store(&h->md->neighborhoods[neigh_idx].entries[j].hash,
                                      0, h->atomic_lock))
                 break;
             h->wpd.value_count--;
             ossl_rcu_assign_ptr(&h->md->neighborhoods[neigh_idx].entries[j].value,
                                 &nv);
             rc = 1;
             break;
         }
     }
     if (rc == 1) {
         ossl_rcu_call(h->lock, free_old_entry, v);
         h->wpd.need_sync = 1;
     }
     return rc;
 }
	/*
	* Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
	*
	* Licensed under the Apache License 2.0 (the "License"). You may not use
	* this file except in compliance with the License. You can obtain a copy
	* in the file LICENSE in the source distribution or at
	* https://www.openssl.org/source/license.html
	*
	*
	*
	* Notes On hash table design and layout
	* This hashtable uses a hopscotch algorithm to do indexing. The data structure
	* looks as follows:
	*
	* hash +--------------+
	* value+------->+ HT_VALUE \|
	* + +--------------+
	* +-------+
	* \| \|
	* +---------------------------------------------------------+
	* \| \| \| \| \| \|
	* \| entry \| entry \| entry \| entry \| \|
	* \| \| \| \| \| \|
	* +---------------------------------------------------------+
	* \| \| \|
	* \| \| \|
	* +---------------------------------------------------------+
	* \| + + +
	* \| neighborhood[0] neighborhood[1] \|
	* \| \|
	* \| \|
	* +---------------------------------------------------------+
	* \|
	* +
	* neighborhoods
	*
	* On lookup/insert/delete, the items key is hashed to a 64 bit value
	* and the result is masked to provide an index into the neighborhoods
	* table. Once a neighborhood is determined, an in-order search is done
	* of the elements in the neighborhood indexes entries for a matching hash
	* value, if found, the corresponding HT_VALUE is used for the respective
	* operation. The number of entries in a neighborhood is determined at build
	* time based on the cacheline size of the target CPU. The intent is for a
	* neighborhood to have all entries in the neighborhood fit into a single cache
	* line to speed up lookups. If all entries in a neighborhood are in use at the
	* time of an insert, the table is expanded and rehashed.
	*
	* Lockless reads hash table is based on the same design but does not
	* allow growing and deletion. Thus subsequent neighborhoods are always
	* searched for a match until an empty entry is found.
	*/

	#include <string.h>
	#include <internal/rcu.h>
	#include <internal/hashtable.h>
	#include <internal/hashfunc.h>
	#include <openssl/rand.h>

	/*
	* gcc defines __SANITIZE_THREAD__
	* but clang uses the feature attributes api
	* map the latter to the former
	*/
	#if defined(__clang__) && defined(__has_feature)
	# if __has_feature(thread_sanitizer)
	# define __SANITIZE_THREADS__
	# endif
	#endif

	#ifdef __SANITIZE_THREADS__
	# include <sanitizer/tsan_interface.h>
	#endif

	#include "internal/numbers.h"
	/*
	* When we do a lookup/insert/delete, there is a high likelihood
	* that we will iterate over at least part of the neighborhood list
	* As such, because we design a neighborhood entry to fit into a single
	* cache line it is advantageous, when supported to fetch the entire
	* structure for faster lookups
	*/
	#if defined(__GNUC__) \|\| defined(__CLANG__)
	# define PREFETCH_NEIGHBORHOOD(x) __builtin_prefetch(x.entries)
	# define PREFETCH(x) __builtin_prefetch(x)
	#else
	# define PREFETCH_NEIGHBORHOOD(x)
	# define PREFETCH(x)
	#endif

	/*
	* Define our neighborhood list length
	* Note: It should always be a power of 2
	*/
	#define DEFAULT_NEIGH_LEN_LOG 4
	#define DEFAULT_NEIGH_LEN (1 << DEFAULT_NEIGH_LEN_LOG)

	/*
	* For now assume cache line size is 64 bytes
	*/
	#define CACHE_LINE_BYTES 64
	#define CACHE_LINE_ALIGNMENT CACHE_LINE_BYTES

	#define NEIGHBORHOOD_LEN (CACHE_LINE_BYTES / sizeof(struct ht_neighborhood_entry_st))
	/*
	* Defines our chains of values
	*/
	struct ht_internal_value_st {
	HT_VALUE value;
	HT *ht;
	};

	struct ht_neighborhood_entry_st {
	uint64_t hash;
	struct ht_internal_value_st *value;
	};

	struct ht_neighborhood_st {
	struct ht_neighborhood_entry_st entries[NEIGHBORHOOD_LEN];
	};

	/*
	* Updates to data in this struct
	* require an rcu sync after modification
	* prior to free
	*/
	struct ht_mutable_data_st {
	struct ht_neighborhood_st *neighborhoods;
	void *neighborhood_ptr_to_free;
	uint64_t neighborhood_mask;
	};

	/*
	* Private data may be updated on the write
	* side only, and so do not require rcu sync
	*/
	struct ht_write_private_data_st {
	size_t neighborhood_len;
	size_t value_count;
	int need_sync;
	};

	struct ht_internal_st {
	HT_CONFIG config;
	CRYPTO_RCU_LOCK *lock;
	CRYPTO_RWLOCK *atomic_lock;
	struct ht_mutable_data_st *md;
	struct ht_write_private_data_st wpd;
	};

	static void free_value(struct ht_internal_value_st *v);

	static struct ht_neighborhood_st *alloc_new_neighborhood_list(size_t len,
	void **freeptr)
	{
	struct ht_neighborhood_st *ret;

	ret = OPENSSL_aligned_alloc(sizeof(struct ht_neighborhood_st) * len,
	CACHE_LINE_BYTES, freeptr);

	/* fall back to regular malloc */
	if (ret == NULL) {
	ret = freeptr = OPENSSL_malloc(sizeof(struct ht_neighborhood_st) len);
	if (ret == NULL)
	return NULL;
	}
	memset(ret, 0, sizeof(struct ht_neighborhood_st) * len);
	return ret;
	}

	static void internal_free_nop(HT_VALUE *v)
	{
	return;
	}

	HT ossl_ht_new(const HT_CONFIG conf)
	{
	HT new = OPENSSL_zalloc(sizeof(new));

	if (new == NULL)
	return NULL;

	new->atomic_lock = CRYPTO_THREAD_lock_new();
	if (new->atomic_lock == NULL)
	goto err;

	memcpy(&new->config, conf, sizeof(*conf));

	if (new->config.init_neighborhoods != 0) {
	new->wpd.neighborhood_len = new->config.init_neighborhoods;
	/* round up to the next power of 2 */
	new->wpd.neighborhood_len--;
	new->wpd.neighborhood_len \|= new->wpd.neighborhood_len >> 1;
	new->wpd.neighborhood_len \|= new->wpd.neighborhood_len >> 2;
	new->wpd.neighborhood_len \|= new->wpd.neighborhood_len >> 4;
	new->wpd.neighborhood_len \|= new->wpd.neighborhood_len >> 8;
	new->wpd.neighborhood_len \|= new->wpd.neighborhood_len >> 16;
	new->wpd.neighborhood_len++;
	} else {
	new->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;
	}

	if (new->config.ht_free_fn == NULL)
	new->config.ht_free_fn = internal_free_nop;

	new->md = OPENSSL_zalloc(sizeof(*new->md));
	if (new->md == NULL)
	goto err;

	new->md->neighborhoods =
	alloc_new_neighborhood_list(new->wpd.neighborhood_len,
	&new->md->neighborhood_ptr_to_free);
	if (new->md->neighborhoods == NULL)
	goto err;
	new->md->neighborhood_mask = new->wpd.neighborhood_len - 1;

	new->lock = ossl_rcu_lock_new(1, conf->ctx);
	if (new->lock == NULL)
	goto err;

	if (new->config.ht_hash_fn == NULL)
	new->config.ht_hash_fn = ossl_fnv1a_hash;

	return new;

	err:
	CRYPTO_THREAD_lock_free(new->atomic_lock);
	ossl_rcu_lock_free(new->lock);
	if (new->md != NULL)
	OPENSSL_free(new->md->neighborhood_ptr_to_free);
	OPENSSL_free(new->md);
	OPENSSL_free(new);
	return NULL;
	}

	void ossl_ht_read_lock(HT *htable)
	{
	ossl_rcu_read_lock(htable->lock);
	}

	void ossl_ht_read_unlock(HT *htable)
	{
	ossl_rcu_read_unlock(htable->lock);
	}

	void ossl_ht_write_lock(HT *htable)
	{
	ossl_rcu_write_lock(htable->lock);
	htable->wpd.need_sync = 0;
	}

	void ossl_ht_write_unlock(HT *htable)
	{
	int need_sync = htable->wpd.need_sync;

	htable->wpd.need_sync = 0;
	ossl_rcu_write_unlock(htable->lock);
	if (need_sync)
	ossl_synchronize_rcu(htable->lock);
	}

	static void free_oldmd(void *arg)
	{
	struct ht_mutable_data_st *oldmd = arg;
	size_t i, j;
	size_t neighborhood_len = (size_t)oldmd->neighborhood_mask + 1;
	struct ht_internal_value_st *v;

	for (i = 0; i < neighborhood_len; i++) {
	PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[i + 1]);
	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	if (oldmd->neighborhoods[i].entries[j].value != NULL) {
	v = oldmd->neighborhoods[i].entries[j].value;
	v->ht->config.ht_free_fn((HT_VALUE *)v);
	free_value(v);
	}
	}
	}

	OPENSSL_free(oldmd->neighborhood_ptr_to_free);
	OPENSSL_free(oldmd);
	}

	static int ossl_ht_flush_internal(HT *h)
	{
	struct ht_mutable_data_st *newmd = NULL;
	struct ht_mutable_data_st *oldmd = NULL;

	newmd = OPENSSL_zalloc(sizeof(*newmd));
	if (newmd == NULL)
	return 0;

	newmd->neighborhoods = alloc_new_neighborhood_list(DEFAULT_NEIGH_LEN,
	&newmd->neighborhood_ptr_to_free);
	if (newmd->neighborhoods == NULL) {
	OPENSSL_free(newmd);
	return 0;
	}

	newmd->neighborhood_mask = DEFAULT_NEIGH_LEN - 1;

	/* Swap the old and new mutable data sets */
	oldmd = ossl_rcu_deref(&h->md);
	ossl_rcu_assign_ptr(&h->md, &newmd);

	/* Set the number of entries to 0 */
	h->wpd.value_count = 0;
	h->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;

	ossl_rcu_call(h->lock, free_oldmd, oldmd);
	h->wpd.need_sync = 1;
	return 1;
	}

	int ossl_ht_flush(HT *h)
	{
	return ossl_ht_flush_internal(h);
	}

	void ossl_ht_free(HT *h)
	{
	if (h == NULL)
	return;

	ossl_ht_write_lock(h);
	ossl_ht_flush_internal(h);
	ossl_ht_write_unlock(h);
	/* Freeing the lock does a final sync for us */
	CRYPTO_THREAD_lock_free(h->atomic_lock);
	ossl_rcu_lock_free(h->lock);
	OPENSSL_free(h->md->neighborhood_ptr_to_free);
	OPENSSL_free(h->md);
	OPENSSL_free(h);
	return;
	}

	size_t ossl_ht_count(HT *h)
	{
	size_t count;

	count = h->wpd.value_count;
	return count;
	}

	void ossl_ht_foreach_until(HT h, int (cb)(HT_VALUE obj, void arg),
	void *arg)
	{
	size_t i, j;
	struct ht_mutable_data_st *md;

	md = ossl_rcu_deref(&h->md);
	for (i = 0; i < md->neighborhood_mask + 1; i++) {
	PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	if (md->neighborhoods[i].entries[j].value != NULL) {
	if (!cb((HT_VALUE *)md->neighborhoods[i].entries[j].value, arg))
	goto out;
	}
	}
	}
	out:
	return;
	}

	HT_VALUE_LIST ossl_ht_filter(HT h, size_t max_len,
	int (filter)(HT_VALUE obj, void *arg),
	void *arg)
	{
	struct ht_mutable_data_st *md;
	HT_VALUE_LIST *list = OPENSSL_zalloc(sizeof(HT_VALUE_LIST)
	+ (sizeof(HT_VALUE ) max_len));
	size_t i, j;
	struct ht_internal_value_st *v;

	if (list == NULL)
	return NULL;

	/*
	* The list array lives just beyond the end of
	* the struct
	*/
	list->list = (HT_VALUE **)(list + 1);

	md = ossl_rcu_deref(&h->md);
	for (i = 0; i < md->neighborhood_mask + 1; i++) {
	PREFETCH_NEIGHBORHOOD(md->neighborhoods[i+1]);
	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	v = md->neighborhoods[i].entries[j].value;
	if (v != NULL && filter((HT_VALUE *)v, arg)) {
	list->list[list->list_len++] = (HT_VALUE *)v;
	if (list->list_len == max_len)
	goto out;
	}
	}
	}
	out:
	return list;
	}

	void ossl_ht_value_list_free(HT_VALUE_LIST *list)
	{
	OPENSSL_free(list);
	}

	static int compare_hash(uint64_t hash1, uint64_t hash2)
	{
	return (hash1 == hash2);
	}

	static void free_old_neigh_table(void *arg)
	{
	struct ht_mutable_data_st *oldmd = arg;

	OPENSSL_free(oldmd->neighborhood_ptr_to_free);
	OPENSSL_free(oldmd);
	}

	/*
	* Increase hash table bucket list
	* must be called with write_lock held
	*/
	static int grow_hashtable(HT *h, size_t oldsize)
	{
	struct ht_mutable_data_st *newmd;
	struct ht_mutable_data_st *oldmd = ossl_rcu_deref(&h->md);
	int rc = 0;
	uint64_t oldi, oldj, newi, newj;
	uint64_t oldhash;
	struct ht_internal_value_st *oldv;
	int rehashed;
	size_t newsize = oldsize * 2;

	if (h->config.lockless_reads)
	goto out;

	if ((newmd = OPENSSL_zalloc(sizeof(*newmd))) == NULL)
	goto out;

	/* bucket list is always a power of 2 */
	newmd->neighborhoods = alloc_new_neighborhood_list(oldsize * 2,
	&newmd->neighborhood_ptr_to_free);
	if (newmd->neighborhoods == NULL)
	goto out_free;

	/* being a power of 2 makes for easy mask computation */
	newmd->neighborhood_mask = (newsize - 1);

	/*
	* Now we need to start rehashing entries
	* Note we don't need to use atomics here as the new
	* mutable data hasn't been published
	*/
	for (oldi = 0; oldi < h->wpd.neighborhood_len; oldi++) {
	PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[oldi + 1]);
	for (oldj = 0; oldj < NEIGHBORHOOD_LEN; oldj++) {
	oldv = oldmd->neighborhoods[oldi].entries[oldj].value;
	if (oldv == NULL)
	continue;
	oldhash = oldmd->neighborhoods[oldi].entries[oldj].hash;
	newi = oldhash & newmd->neighborhood_mask;
	rehashed = 0;
	for (newj = 0; newj < NEIGHBORHOOD_LEN; newj++) {
	if (newmd->neighborhoods[newi].entries[newj].value == NULL) {
	newmd->neighborhoods[newi].entries[newj].value = oldv;
	newmd->neighborhoods[newi].entries[newj].hash = oldhash;
	rehashed = 1;
	break;
	}
	}
	if (rehashed == 0) {
	/* we ran out of space in a neighborhood, grow again */
	OPENSSL_free(newmd->neighborhoods);
	OPENSSL_free(newmd);
	return grow_hashtable(h, newsize);
	}
	}
	}
	/*
	* Now that our entries are all hashed into the new bucket list
	* update our bucket_len and target_max_load
	*/
	h->wpd.neighborhood_len = newsize;

	/*
	* Now we replace the old mutable data with the new
	*/
	ossl_rcu_assign_ptr(&h->md, &newmd);
	ossl_rcu_call(h->lock, free_old_neigh_table, oldmd);
	h->wpd.need_sync = 1;
	/*
	* And we're done
	*/
	rc = 1;

	out:
	return rc;
	out_free:
	OPENSSL_free(newmd->neighborhoods);
	OPENSSL_free(newmd);
	goto out;
	}

	static void free_old_ht_value(void *arg)
	{
	HT_VALUE h = (HT_VALUE )arg;

	/*
	* Note, this is only called on replacement,
	* the caller is responsible for freeing the
	* held data, we just need to free the wrapping
	* struct here
	*/
	OPENSSL_free(h);
	}

	static ossl_inline int match_key(HT_KEY a, HT_KEY b)
	{
	/*
	* keys match if they are both present, the same size
	* and compare equal in memory
	*/
	PREFETCH(a->keybuf);
	PREFETCH(b->keybuf);
	if (a->keybuf != NULL && b->keybuf != NULL && a->keysize == b->keysize)
	return !memcmp(a->keybuf, b->keybuf, a->keysize);

	return 1;
	}

	static int ossl_ht_insert_locked(HT *h, uint64_t hash,
	struct ht_internal_value_st *newval,
	HT_VALUE **olddata)
	{
	struct ht_mutable_data_st *md = h->md;
	uint64_t neigh_idx_start = hash & md->neighborhood_mask;
	uint64_t neigh_idx = neigh_idx_start;
	size_t j;
	uint64_t ihash;
	HT_VALUE *ival;
	size_t empty_idx = SIZE_MAX;
	int lockless_reads = h->config.lockless_reads;

	do {
	PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);

	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
	if (ival == NULL) {
	empty_idx = j;
	/* lockless_reads implies no deletion, we can break out */
	if (lockless_reads)
	goto not_found;
	continue;
	}
	if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
	&ihash, h->atomic_lock))
	return 0;
	if (compare_hash(hash, ihash) && match_key(&newval->value.key,
	&ival->key)) {
	if (olddata == NULL) {
	/* This would insert a duplicate -> fail */
	return 0;
	}
	/* Do a replacement */
	if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[j].hash,
	hash, h->atomic_lock))
	return 0;
	olddata = (HT_VALUE )md->neighborhoods[neigh_idx].entries[j].value;
	ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[j].value,
	&newval);
	ossl_rcu_call(h->lock, free_old_ht_value, *olddata);
	h->wpd.need_sync = 1;
	return 1;
	}
	}
	if (!lockless_reads)
	break;
	/* Continue search in subsequent neighborhoods */
	neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
	} while (neigh_idx != neigh_idx_start);

	not_found:
	/* If we get to here, its just an insert */
	if (empty_idx == SIZE_MAX)
	return -1; /* out of space */
	if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[empty_idx].hash,
	hash, h->atomic_lock))
	return 0;
	h->wpd.value_count++;
	ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[empty_idx].value,
	&newval);
	return 1;
	}

	static struct ht_internal_value_st alloc_new_value(HT h, HT_KEY *key,
	void *data,
	uintptr_t *type)
	{
	struct ht_internal_value_st *tmp;
	size_t nvsize = sizeof(*tmp);

	if (h->config.collision_check == 1)
	nvsize += key->keysize;

	tmp = OPENSSL_malloc(nvsize);

	if (tmp == NULL)
	return NULL;

	tmp->ht = h;
	tmp->value.value = data;
	tmp->value.type_id = type;
	tmp->value.key.keybuf = NULL;
	if (h->config.collision_check) {
	tmp->value.key.keybuf = (uint8_t *)(tmp + 1);
	tmp->value.key.keysize = key->keysize;
	memcpy(tmp->value.key.keybuf, key->keybuf, key->keysize);
	}


	return tmp;
	}

	static void free_value(struct ht_internal_value_st *v)
	{
	OPENSSL_free(v);
	}

	int ossl_ht_insert(HT h, HT_KEY key, HT_VALUE data, HT_VALUE *olddata)
	{
	struct ht_internal_value_st *newval = NULL;
	uint64_t hash;
	int rc = 0;
	int i;

	if (data->value == NULL)
	goto out;

	newval = alloc_new_value(h, key, data->value, data->type_id);
	if (newval == NULL)
	goto out;

	/*
	* we have to take our lock here to prevent other changes
	* to the bucket list
	*/
	hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

	for (i = 0;
	(rc = ossl_ht_insert_locked(h, hash, newval, olddata)) == -1
	&& i < 4;
	++i)
	if (!grow_hashtable(h, h->wpd.neighborhood_len)) {
	rc = -1;
	break;
	}

	if (rc <= 0)
	free_value(newval);

	out:
	return rc;
	}

	HT_VALUE ossl_ht_get(HT h, HT_KEY *key)
	{
	struct ht_mutable_data_st *md;
	uint64_t hash;
	uint64_t neigh_idx_start;
	uint64_t neigh_idx;
	struct ht_internal_value_st *ival = NULL;
	size_t j;
	uint64_t ehash;
	int lockless_reads = h->config.lockless_reads;

	hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

	md = ossl_rcu_deref(&h->md);
	neigh_idx = neigh_idx_start = hash & md->neighborhood_mask;
	do {
	PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
	if (ival == NULL) {
	if (lockless_reads)
	/* lockless_reads implies no deletion, we can break out */
	return NULL;
	continue;
	}
	if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
	&ehash, h->atomic_lock))
	return NULL;
	if (compare_hash(hash, ehash) && match_key(&ival->value.key, key))
	return (HT_VALUE *)ival;
	}
	if (!lockless_reads)
	break;
	/* Continue search in subsequent neighborhoods */
	neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
	} while (neigh_idx != neigh_idx_start);

	return NULL;
	}

	static void free_old_entry(void *arg)
	{
	struct ht_internal_value_st *v = arg;

	v->ht->config.ht_free_fn((HT_VALUE *)v);
	free_value(v);
	}

	int ossl_ht_delete(HT h, HT_KEY key)
	{
	uint64_t hash;
	uint64_t neigh_idx;
	size_t j;
	struct ht_internal_value_st *v = NULL;
	HT_VALUE *nv = NULL;
	int rc = 0;

	if (h->config.lockless_reads)
	return 0;

	hash = h->config.ht_hash_fn(key->keybuf, key->keysize);

	neigh_idx = hash & h->md->neighborhood_mask;
	PREFETCH_NEIGHBORHOOD(h->md->neighborhoods[neigh_idx]);
	for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
	v = (struct ht_internal_value_st *)h->md->neighborhoods[neigh_idx].entries[j].value;
	if (v == NULL)
	continue;
	if (compare_hash(hash, h->md->neighborhoods[neigh_idx].entries[j].hash)
	&& match_key(key, &v->value.key)) {
	if (!CRYPTO_atomic_store(&h->md->neighborhoods[neigh_idx].entries[j].hash,
	0, h->atomic_lock))
	break;
	h->wpd.value_count--;
	ossl_rcu_assign_ptr(&h->md->neighborhoods[neigh_idx].entries[j].value,
	&nv);
	rc = 1;
	break;
	}
	}
	if (rc == 1) {
	ossl_rcu_call(h->lock, free_old_entry, v);
	h->wpd.need_sync = 1;
	}
	return rc;
	}