a new config option _no_rcu_ is added into HT_CONFIG. When _no_rcu_ is
set then hashtable can be guarded with any other locking primitives,
and behives as ordinary hashtable. Also, all the impact of the
atomics used internally to the hash table was mitigated.
RCU performance
# INFO: @ test/lhash_test.c:747
# multithread stress runs 40000 ops in 40.779656 seconds
No RCU, guarded with RWLOCK
# INFO: @ test/lhash_test.c:747
# multithread stress runs 40000 ops in 36.976926 seconds
Signed-off-by: Nikola Pajkovsky <nikolap@openssl.org>
Reviewed-by: Saša Nedvědický <sashan@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/28677)
When defining a custom hash function for a hashtable key, you typically start with:
HT_START_KEY_DEFN(key)
HT_DEF_KEY_FIELD(k, unsigned char *)
HT_END_KEY_DEFN(KEY)
In this setup, the hash function signature requires keybuf and len as
parameters rather than the hashtable key itself. As a result,
accessing members of the hashtable structure becomes awkward, since
you must do something like:
#define FROM_KEYBUF_TO_HT_KEY(keybuf, type) (type)((keybuf) - sizeof(HT_KEY))
static uint64_t ht_hash(uint8_t *keybuf, size_t keylen)
{
KEY *k = FROM_KEYBUF_TO_HT_KEY(keybuf, KEY *);
...
}
This kind of pointer arithmetic is both unnecessary and error-prone.
A cleaner approach is to pass the HT pointer directly into the hash
function. From there, you can safely cast it to the required type
without the pointer gymnastics.
Signed-off-by: Nikola Pajkovsky <nikolap@openssl.org>
Reviewed-by: Saša Nedvědický <sashan@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/28677)
during memfail testing:
https://github.com/openssl/openssl/actions/runs/16794088536/job/47561223902
We get lots of test failures in ossl_rcu_read_lock. This occurs
because we have a few cases in the read lock path that attempt mallocs,
which, if they fail, trigger an assert or a silent failure, which isn't
really appropriate. We should instead fail gracefully, by informing the
caller that the lock failed, like we do for CRYPTO_THREAD_read_lock.
Fortunately, these are all internal apis, so we can convert
ossl_rcu_read_lock to return an int indicating success/failure, and fail
gracefully during the test, rather than hitting an assert abort.
Fixesopenssl/project#1315
Reviewed-by: Paul Yang <paulyang.inf@gmail.com>
Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/28195)
lhash_test uses a hashtable that may not be empty at the end of the test
Given that the free function frees the elements in the list and uses the
atomic worker_lock to do so, we need to free the hash table prior to
freeing the working lock to avoid the use of unallocated memory.
Fixes#26798
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/26800)
We must set pending_delete before the actual deletion as another inserting
or deleting thread can pick up the delete callback before the
ossl_ht_write_unlock() call.
This can happen only if no read locks are pending and only on Windows where
we do not use the write mutex to get the callback list.
Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/26152)
Instead of just using the neighborhood, fill
subsequent neighborhoods with colliding entries.
If the hashtable is properly sized, it won't degrade
performance too much.
Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/24504)
Also build it in the FIPS provider too and properly
report error on insert when hashtable cannot be grown.
Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/24504)
Add full key matching to hashtable
the idea is that on a hash value match we do a full memory comparison of
the unhashed key to validate that its actually the key we're looking for
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/24504)
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)
Apart from ssltest_old.c, the test suite relied on e_os.h for the
OSSL_NELEM macro and nothing else.
The ssltest_old.c also requires EXIT and some socket macros.
Create a new header to define the OSSL_NELEM macro and use that instead.
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/4186)
that needed test_main now works using the same infrastructure as tests that used
register_tests.
This meant:
* renaming register_tests to setup_tests and giving it a success/failure return.
* renaming the init_test function to setup_test_framework.
* renaming the finish_test function to pulldown_test_framework.
* adding a user provided global_init function that runs before the test frame
work is initialised. It returns a failure indication that stops the stest.
* adding helper functions that permit tests to access their command line args.
* spliting the BIO initialisation and finalisation out from the test setup and
teardown.
* hiding some of the now test internal functions.
* fix the comments in testutil.h
Reviewed-by: Richard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/3953)
Signed-off-by: Paul Yang <paulyang.inf@gmail.com>
Reviewed-by: Kurt Roeckx <kurt@openssl.org>
Reviewed-by: Ben Kaduk <kaduk@mit.edu>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/3622)
Nikola Pajkovsky
Neil Horman
Tomas Mraz
openssl-machine
Hugo Landau
Matt Caswell
Pauli
Richard Levitte
Rich Salz
Paul Yang