ossl_ht_insert(): Allow for 4 iterations of grow_hashtable()

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.c

ossl_ht_insert(): Allow for 4 iterations of grow_hashtable()

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/25273)

show more ...

hashtable.c: Code style fixes

Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/24504)

For lockless reads use the whole hashtable for colliding entries

Instead of just using the neighborhood, fill
subsequent neighborhoods with colliding entries.

If the hashtable i

For lockless reads use the whole hashtable for colliding entries

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)

show more ...

hashtable: Support lockless reads

Also build it in the FIPS provider too and properly
report error on insert when hashtable cannot be grown.

Reviewed-by: Neil Horman <nhorman@op

hashtable: Support lockless reads

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)

show more ...

hashtable.c: Avoid infinite loop in ossl_ht_insert()

Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/

hashtable.c: Avoid infinite loop in ossl_ht_insert()

Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/24504)

show more ...

some performance improvements

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

alternate collision checking support

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 tha

alternate collision checking support

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)

show more ...

Add error checking to CRYPTO_atomic_[load|store] calls

Noted that we didn't check return codes of the atomic loads/stores in
the new hashtable, and they can fail

Reviewed-by: To

Add error checking to CRYPTO_atomic_[load|store] calls

Noted that we didn't check return codes of the atomic loads/stores in
the new hashtable, and they can fail

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Tom Cosgrove <tom.cosgrove@arm.com>
(Merged from https://github.com/openssl/openssl/pull/24969)

show more ...

Make ossl_ht_delete use read-once semantics

To ensure that the value of h->md doesn't get recomputed during a delete
operation use ossl_rcu_deref on it

Reviewed-by: Tomas Mraz <

Make ossl_ht_delete use read-once semantics

To ensure that the value of h->md doesn't get recomputed during a delete
operation use ossl_rcu_deref on it

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Tom Cosgrove <tom.cosgrove@arm.com>
(Merged from https://github.com/openssl/openssl/pull/24969)

show more ...

Convert hashtable to using ossl_rcu_deref on lookup

The new hashtable has an issue on non-64 bit builds. We use
CRYPTO_atomic_load to load a pointer value when doing lookups, but that

Convert hashtable to using ossl_rcu_deref on lookup

The new hashtable has an issue on non-64 bit builds. We use
CRYPTO_atomic_load to load a pointer value when doing lookups, but that
API relies on the expectation that pointers are 64 bits wide. On 32 bit
systems, we try to load 64 bits using CRYPTO_atomic_load into a 32 bit
pointer, which overruns our stack

Fix this by no longer using CRYPTO_atomic_load for value fetches from
the hashtable. Instead use ossl_rcu_deref, whcih operates on void
pointers and is safe on all arches

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

show more ...

Fix typos found by codespell

Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Reviewed-by: Kurt Roeckx <kurt@roeckx.be>
(Merged from https://github.com/openssl/openssl/pull/24691)

Fix coverity-1596616

Need to add a null check prior to derefencing pointer for free

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Re

Fix coverity-1596616

Need to add a null check prior to derefencing pointer for free

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/24263)

show more ...

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

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)

show more ...