Introduce new internal hashtable implementation

Create a new hashtable that is more efficient than the existing LHASH_OF
implementation.  the new ossl_ht api offers several new features that
improve performance opportunistically

* A more generalized hash function.  Currently using fnv1a, provides a
  more general hash function, but can still be overridden where needed

* Improved locking and reference counting.  This hash table is
  internally locked with an RCU lock, and optionally reference counts
  elements, allowing for users to not have to create and manage their
  own read/write locks

* Lockless operation.  The hash table can be configured to operate
  locklessly on the read side, improving performance, at the sacrifice
  of the ability to grow the hash table or delete elements from it

* A filter function allowing for the retrieval of several elements at a
  time matching a given criteria without having to hold a lock
  permanently

* a doall_until iterator variant, that allows callers which need to
  iterate over the entire hash table until a given condition is met (as
  defined by the return value of the iterator callback).  This allows
  for callers attempting to do expensive cache searches for a small
  number of elements to terminate the iteration early, saving cpu cycles

* Dynamic type safety.  The hash table provides operations to set and
  get data of a specific type without having to define a type at the
  instatiation point

* Multiple data type storage.  The hash table can store multiple data
  types allowing for more flexible usage

* Ubsan safety.  Because the API deals with concrete single types
  (HT_KEY and HT_VALUE), leaving specific type casting to the call
  recipient with dynamic type validation, this implementation is safe
  from the ubsan undefined behavior warnings that require additional
  thunking on callbacks.

Testing of this new hashtable with an equivalent hash function, I can
observe approximately a 6% performance improvement in the lhash_test

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/23671)

3 files changed, 400 insertions, 5 deletions

diff --git a/doc/internal/man3/ossl_ht_new.pod b/doc/internal/man3/ossl_ht_new.pod
new file mode 100644
index 0000000000..f90ecc2258
--- /dev/null
+++ b/doc/internal/man3/ossl_ht_new.pod
@@ -0,0 +1,374 @@
+=pod
+
+=head1 NAME
+
+ossl_ht_new, ossl_ht_free,
+ossl_ht_read_lock, ossl_ht_read_unlock,
+ossl_ht_write_lock, ossl_ht_write_unlock,
+ossl_ht_flush, ossl_ht_insert,
+ossl_ht_delete, ossl_ht_count,
+ossl_ht_foreach_until, ossl_ht_filter,
+ossl_ht_value_list_free, ossl_ht_get,
+ossl_ht_put, HT_START_KEY_DEFN,
+HT_END_KEY_DEFN, HT_DEF_KEY_FIELD_CHAR_ARRAY,
+HT_DEF_KEY_FIELD_UINT8T_ARRAY, HT_DEF_KEY_FIELD,
+HT_INIT_KEY, HT_KEY_RESET, HT_SET_KEY_FIELD,
+HT_SET_KEY_STRING, HT_SET_KEY_BLOB,
+TO_HT_KEY, FROM_HT_KEY,
+IMPLEMENT_HT_VALUE_TYPE_FNS
+- internal rcu locked hashtables
+
+=head1 SYNOPSIS
+
+ HT *ossl_ht_new(HT_CONFIG *conf);
+ void ossl_ht_free(HT *htable);
+ void ossl_ht_read_lock(HT *htable);
+ void ossl_ht_read_unlock(HT *htable);
+ void ossl_ht_write_lock(HT *htable);
+ void ossl_ht_write_unlock(HT *htable);
+ int  ossl_ht_flush(HT *htable);
+ int  ossl_ht_insert(HT *htable, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata);
+ int ossl_ht_delete(HT *htable, HT_KEY *key);
+ size_t ossl_ht_count(HT *htable);
+ void ossl_ht_foreach_until(HT *htable, int (*cb)(HT_VALUE *obj, void *arg), void *arg);
+ HT_VALUE_LIST *ossl_ht_filter(HT *htable, size_t max_len, int (*filter)(HT_VALUE *obj));
+ void ossl_ht_value_list_free(HT_VALUE_LIST *list);
+ HT_VALUE *ossl_ht_get(HT *htable, HT_KEY *key);
+ void ossl_ht_put(HT_VALUE *value);
+ HT_START_KEY_DEFN(keyname);
+ HT_END_KEY_DEFN(keyname);
+ HT_DEF_KEY_FIELD(name, type);
+ HT_DEF_KEY_FIELD_CHAR_ARRAY(name, size);
+ HT_DEF_KEY_FIELD_UINT8T_ARRAY(name, size);
+ HT_INIT_KEY(key);
+ HT_KEY_RESET(key);
+ HT_SET_KEY_FIELD(key, member, value);
+ HT_SET_KEY_STRING(key, member, value);
+ HT_SET_KEY_BLOB(key, member, value, len);
+ TO_HT_KEY(key);
+ FROM_HT_KEY(key, type);
+ IMPLEMENT_HT_VALUE_TYPE_FNS(vtype, name, pfx);
+
+=head1 DESCRIPTION
+
+This API provides a library-internal implementation of a hashtable that provides
+reference counted object retrieval under the protection of an rcu lock.  API
+type safety is offered via conversion macros to and from the generic HT_VALUE
+type.
+
+=over 2
+
+=item *
+
+ossl_ht_new() returns a new HT (hashtable object) used to store data
+elements based on a defined key.  The call accepts an HT_CONFIG pointer which
+contains configurations options for hashtable.  Current config options consist
+of:
+    I<ht_free_fn> The function to call to free a value, may be B<NULL>.
+    I<ht_hash_fn> The function to generate a hash value for a key, may be B<NULL>.
+    I<init_neighborhood_len> The initial number of neighborhoods in the hash table.
+
+Note that init_bucket_len may be set to zero, which will use the default initial
+bucket size, which will be automatically expanded with the hash table load
+average reaches 0.75.
+
+Note that lockless_read operation implies behavioral restrictions.  Specifically
+    Only element additions are allowed, deletion operations will fail
+    Hash table growth is inhibited.  init_bucket_len should be set to an
+    appropriate value to prevent performance degradation
+    The table owner is responsible for ensuring there are no readers during a
+    freeing of the table.
+
+Note that lockless_write operations are done at your own risk.  Lockless
+    operation in a multithreaded environment will cause data corruption.  It
+    is the callers responsibility in this mode of operation to provide thread
+    synchronization.
+
+=item *
+
+ossl_ht_free() frees an allocated hash table.  Each element in the table
+will have its reference count dropped, and, if said count reaches zero, the hash
+tables registered free function will be called to release the element data.
+
+=item *
+
+ossl_ht_read_lock(), ossl_ht_read_unlock(), ossl_ht_write_lock() and
+ossl_ht_write_unlock() lock the table for reading and writing/modification.
+These function are not required for use in the event a table is to be used in a
+lockless fashion, but if they are not used, it is the responsibility of the caller
+to ensure thread synchronization.  Note that an rcu lock is used internally for these
+operations, so for table modifying actions (ossl_ht_flush() and ossl_ht_delete()
+the write lock must be taken and released to ensure rcu synchronization takes
+place.
+
+=item *
+
+ossl_ht_flush() empties a hash table.  All elements will have their
+reference counts decremented, and, on reaching zero, the free function will be
+called to release the element data.
+
+=item *
+
+ossl_ht_insert() inserts an HT_VALUE element into the hash table, to be
+hashed using the corresponding HT_KEY value.
+
+=item *
+
+ossl_ht_delete() deletes an entry from the hashtable indexed by the passed
+HT_KEY value.
+
+=item *
+
+ossl_ht_count() returns the number of elements within the hash table.
+
+=item *
+
+ossl_ht_foreach_until() iterates over all elements in the hash table, calling
+the passed callback function for each. The return value of the callback
+indicates if the iteration should continue or not.  Returning 1 indicates
+iteration should continue, while returning 0 indicates that iteration should
+terminate.
+
+Note that the iteration is done under read lock protection, and as such
+modifications to the table are disallowed in the callback function.
+Modification to the value content are permitted, if the caller is able to
+properly synchronize such modifications with other threads.
+
+=item *
+
+ossl_ht_filter() iterates over all elements of the hash table, calling
+the filter callback for each element.  If the callback returns 1, the
+corresponding HT_VALUE is placed on a list, and its reference count incremented.
+The completed list is returned to the caller as an HT_VALUE_LIST object
+
+=item *
+
+ossl_ht_value_list_free() frees an HT_VALUE_LIST.  For each element on
+the list, its reference count is decremented, and after traversing the list, the
+list object is freed.  Note, NULL elements are allowed on the list, but for any
+element which is taken from the list by a caller, they must call
+ossl_ht_put on the HT_VALUE to prevent memory leaks.
+
+=item *
+
+ossl_ht_get() preforms a lookup of an HT_KEY in the hashtable, returning
+its corresponding value.
+
+=item *
+
+HT_START_KEY_DEFN() Begins the definition of a key type.  the keyname parameter
+defines the structure name, and presets a common key header.
+
+=item *
+
+HT_END_KEY_DEFN() Finalizes a key definition.  the keyname parameter (which may
+differ from the name passed in HT_START_KEY_DEFN(), defines the key type name.
+The resulting type may be converted to an HT_KEY variable via the HT_TO_KEY()
+macro, and back using the HT_FROM_KEY() macro.
+
+=item *
+
+HT_DEF_KEY_FIELD() Allows for the creation of data fields within a key. Note,
+this macro can be used for any data type, but it is recommended that strings and
+binary arrays be created with the HT_DEF_KEY_FIELD_CHAR_ARRAY() and
+HT_DEF_KEY_FIELD_UINT8T_ARRAY() macros to ensure proper in-lining of key data.
+
+=item *
+
+HT_DEF_KEY_FIELD_CHAR_ARRAY() Creates a string field of fixed size
+within a key definition. Note these items will be NULL terminated.
+
+=item *
+
+HT_DEF_KEY_FIELD_UINT8T_ARRAY() Creates an array of uint8_t elements within a
+key.
+
+=item *
+
+HT_INIT_KEY() Initializes a key for use.  Can be called multiple times, but must
+be called at least once before using in any hashtable method.
+
+=item *
+
+HT_KEY_RESET() Resets a key's data to all zeros.
+
+=item *
+
+HT_SET_KEY_FIELD() Sets a field in a key (as defined by HT_DEF_KEY_FIELD()) to a
+given value.
+
+=item *
+
+HT_SET_KEY_STRING() Preforms a strncpy() of a source string to the destination
+key field.
+
+=item *
+
+HT_SET_KEY_BLOB() Preforms a memcpy() of a source uint8_t buffer to a
+destination key field.
+
+=item *
+
+TO_HT_KEY() Converts a key type as defined by HT_START_KEY_DEFN() and
+HE_END_KEY_DEFN() to the generic HT_KEY type
+
+=item *
+
+FROM_HT_KEY() Converts an HT_KEY back to a specific key type as defined by
+HT_START_KEY_DEFN() and HT_END_KEY_DEFN()
+
+=item *
+
+IMPLEMENT_HT_VALUE_TYPE_FNS() creates template conversion functions for
+manipulating the hashtable using specific data types.  This macro accepts two
+parameters, a NAME, which is used to prefix the hashtable function so that it
+may be associated with a specific hash table, and TYPE which defines the type of
+data the instantiated function accepts.  The list of functions instantiated by
+this macro are below.
+
+=over 2
+
+=item *
+
+int ossl_ht_NAME_TYPE_insert(HT* h, HT_KEY *key, <type> *value, HT_VALUE **olddata)
+Inserts a value to the hash table of type TYPE into the hash table using the
+provided key.  If olddata is not NULL, and a matching key already exists in the
+table, the operation is a replacement, and the old data is returned in this
+pointer
+
+=item *
+
+<TYPE> ossl_ht_NAME_TYPE_get(HT *h, HT_KEY *key, HT_VALUE **v)
+Looks up an item in the hash table based on key, and returns the data it found,
+if any.  v holds a pointer to the HT_VALUE associated with the data.
+
+=item *
+
+<TYPE> *ossl_ht_NAME_TYPE_from_value(HT_VALUE *v)
+Validates that the HT_VALUE provided matches the TYPE specified, and returns the
+value data.  If there is a type mismatch, NULL is returned
+
+=item *
+
+HT_VALUE *ossl_ht_NAME_TYPE_to_value(<TYPE> *data)
+Converts the data pointer provided to an HT_VALUE object
+
+=item *
+
+int ossl_ht_NAME_TYPE_type(HT_VALUE *v)
+Returns true if the HT_VALUE object passed in is of type <TYPE>
+
+=back
+
+=back
+
+=head1 RETURN VALUES
+
+ossl_ht_new() returns an HT* struct on success and NULL on error
+
+void ossl_ht_free(HT *htable);
+
+ossl_ht_flush() and ossl_ht_insert() return 1 on success and 0 on error
+
+ossl_ht_delete() returns 1 if the key was successfully deleted, and 0 if the
+key was not found. 
+
+ossl_ht_count() returns the number of elements in the hash table
+
+ossl_ht_filter() returns an HT_VALUE_LIST of all elements matching the
+provided filter
+
+ossl_ht_get() returns an HT_VALUE pointer, or NULL if the element was not
+found.
+
+=head1 EXAMPLES
+
+#include <stdio.h>
+#include <string.h>
+
+#include <openssl/err.h>
+#include <openssl/crypto.h>
+#include <internal/hashtable.h>
+
+HT_START_KEY_DEFN(intkey)
+HT_DEF_KEY_FIELD(myintkey, int)
+HT_END_KEY_DEFN(INTKEY)
+
+IMPLEMENT_HT_VALUE_TYPE_FNS(int, test, static)
+
+static void int_free_fn(HT_VALUE *v)
+{
+    int *i = ossl_crypto_test_int_from_value(v);
+
+    fprintf(stderr, "Freeing an element\n");
+    OPENSSL_free(i);
+}
+
+static int test_int_hashtable(void)
+{
+    /*
+     * our config says:
+     * int_free_fn - Our free handler
+     * NULL - Use default hash fn
+     * 0 - use default initial bucket size
+     */
+    HT_CONFIG hash_conf = {
+        int_free_fn,
+        NULL,
+        0
+    };
+    INTKEY key;
+    HT *ht = NULL;
+    HT_VALUE *v;
+    int rc;
+    int *newval = OPENSSL_malloc(sizeof(int));
+
+    ht = ossl_ht_new(&hash_conf);
+
+    if (ht == NULL)
+        return 0;
+
+    if (newval == NULL)
+        goto out;
+
+    *newval = 1;
+
+    /* insert */
+    HT_INIT_KEY(&key);
+    HT_SET_KEY_FIELD(&key, myintkey, 47);
+    ossl_ht_write_lock(ht);
+    rc = ossl_ht_test_int_insert(ht, TO_HT_KEY(&key), newval, NULL);
+    ossl_ht_write_unlock(ht);
+    if (rc == 0)
+        goto out;
+
+    /* num_items */
+    if (ossl_ht_count(ht) != 1)
+        goto out;
+
+    /* lookup */
+    HT_RESET_KEY(&key);
+    HT_SET_KEY_FIELD(&key, myintkey, 47);
+    ossl_ht_read_lock(ht);
+    v = ossl_ht_get(ht, TO_HT_KEY(&key);
+    fprintf(stderr, "found element with key 47 holding value %d\n",
+            *ossl_ht_test_int_from_value(v));
+    ossl_ht_read_unlock(ht);
+
+    rc = 1;
+end:
+    /* this will call the free function for our element */
+    ossl_ht_free(ht);
+    return rc;
+}
+
+=head1 COPYRIGHT
+
+Copyright 2024 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
+L<https://www.openssl.org/source/license.html>.
+
+=cut
diff --git a/doc/man3/CRYPTO_THREAD_run_once.pod b/doc/man3/CRYPTO_THREAD_run_once.pod
index 3658a39278..9d7eefb5d3 100644
--- a/doc/man3/CRYPTO_THREAD_run_once.pod
+++ b/doc/man3/CRYPTO_THREAD_run_once.pod
@@ -238,6 +238,10 @@ repeatedly load/unload shared libraries that allocate locks.
 
 L<crypto(7)>, L<openssl-threads(7)>.
 
+=head1 HISTORY
+
+CRYPTO_atomic_store() was added in OpenSSL 3.4.0
+
 =head1 COPYRIGHT
 
 Copyright 2000-2023 The OpenSSL Project Authors. All Rights Reserved.
diff --git a/doc/man3/OPENSSL_malloc.pod b/doc/man3/OPENSSL_malloc.pod
index 7dc6468f0e..9e8e0eebc0 100644
--- a/doc/man3/OPENSSL_malloc.pod
+++ b/doc/man3/OPENSSL_malloc.pod
@@ -3,9 +3,9 @@
 =head1 NAME
 
 OPENSSL_malloc_init,
-OPENSSL_malloc, OPENSSL_zalloc, OPENSSL_realloc, OPENSSL_free,
-OPENSSL_clear_realloc, OPENSSL_clear_free, OPENSSL_cleanse,
-CRYPTO_malloc, CRYPTO_zalloc, CRYPTO_realloc, CRYPTO_free,
+OPENSSL_malloc, OPENSSL_aligned_alloc, OPENSSL_zalloc, OPENSSL_realloc,
+OPENSSL_free, OPENSSL_clear_realloc, OPENSSL_clear_free, OPENSSL_cleanse,
+CRYPTO_malloc, CRYPTO_aligned_alloc, CRYPTO_zalloc, CRYPTO_realloc, CRYPTO_free,
 OPENSSL_strdup, OPENSSL_strndup,
 OPENSSL_memdup, OPENSSL_strlcpy, OPENSSL_strlcat,
 CRYPTO_strdup, CRYPTO_strndup,
@@ -28,6 +28,7 @@ OPENSSL_MALLOC_FD
  int OPENSSL_malloc_init(void);
 
  void *OPENSSL_malloc(size_t num);
+ void *OPENSSL_aligned_alloc(size_t num, size_t alignment, void **freeptr);
  void *OPENSSL_zalloc(size_t num);
  void *OPENSSL_realloc(void *addr, size_t num);
  void OPENSSL_free(void *addr);
@@ -41,6 +42,8 @@ OPENSSL_MALLOC_FD
  void OPENSSL_cleanse(void *ptr, size_t len);
 
  void *CRYPTO_malloc(size_t num, const char *file, int line);
+ void *CRYPTO_aligned_alloc(size_t num, size_t align, void **freeptr, 
+                            const char *file, int line);
  void *CRYPTO_zalloc(size_t num, const char *file, int line);
  void *CRYPTO_realloc(void *p, size_t num, const char *file, int line);
  void CRYPTO_free(void *str, const char *, int);
@@ -96,6 +99,20 @@ OPENSSL_malloc(), OPENSSL_realloc(), and OPENSSL_free() are like the
 C malloc(), realloc(), and free() functions.
 OPENSSL_zalloc() calls memset() to zero the memory before returning.
 
+OPENSSL_aligned_alloc() operates just as OPENSSL_malloc does, but it
+allows for the caller to specify an alignment value, for instances in
+which the default alignment of malloc is insufficient for the callers
+needs.  Note, the alignment value must be a power of 2, and the size
+specified must be a multiple of the alignment.
+NOTE: The call to OPENSSL_aligned_alloc() accepts a 3rd argument, I<freeptr>
+which must point to a void pointer.  On some platforms, there is no available
+library call to obtain memory allocations greater than what malloc provides.  In
+this case, OPENSSL_aligned_alloc implements its own alignment routine,
+allocating additional memory and offsetting the returned pointer to be on the
+requested alignment boundary.  In order to safely free allocations made by this
+method, the caller must return the value in the I<freeptr> variable, rather than
+the returned pointer.
+
 OPENSSL_clear_realloc() and OPENSSL_clear_free() should be used
 when the buffer at B<addr> holds sensitive information.
 The old buffer is filled with zero's by calling OPENSSL_cleanse()
@@ -168,7 +185,7 @@ OPENSSL_malloc_init(), OPENSSL_free(), OPENSSL_clear_free()
 CRYPTO_free(), CRYPTO_clear_free() and CRYPTO_get_mem_functions()
 return no value.
 
-OPENSSL_malloc(), OPENSSL_zalloc(), OPENSSL_realloc(),
+OPENSSL_malloc(), OPENSSL_aligned_alloc(), OPENSSL_zalloc(), OPENSSL_realloc(),
 OPENSSL_clear_realloc(),
 CRYPTO_malloc(), CRYPTO_zalloc(), CRYPTO_realloc(),
 CRYPTO_clear_realloc(),
@@ -194,7 +211,7 @@ CRYPTO_mem_leaks_cb(), CRYPTO_set_mem_debug(), CRYPTO_mem_ctrl()
 were deprecated in OpenSSL 3.0.
 The memory-leak checking has been deprecated in OpenSSL 3.0 in favor of
 clang's memory and leak sanitizer.
-
+OPENSSL_aligned_alloc(), CRYPTO_aligned_alloc() were added in OpenSSL 3.4.0
 
 =head1 COPYRIGHT