aboutsummaryrefslogtreecommitdiffstats
path: root/crypto/hashtable
Commit message (Collapse)AuthorAgeFilesLines
* Optimize hashtable without rcu freeingJakub Zelenka2026-05-211-12/+13
| | | | | | | | | | | | It is not necessary to flush table for hash tables without rcu. This is follow up to https://github.com/openssl/openssl/pull/31163 Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> MergeDate: Thu May 21 09:09:36 2026 (Merged from https://github.com/openssl/openssl/pull/31237)
* Fix memleak in hashtable free if flush failsJakub Zelenka2026-05-141-3/+9
| | | | | | | | | This happens because free_oldmd is not run when flush fails Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Neil Horman <[email protected]> MergeDate: Thu May 14 09:26:11 2026 (Merged from https://github.com/openssl/openssl/pull/31163)
* Fix ignored call in ossl_rcu_call when cb item alloc failsJakub Zelenka2026-05-111-15/+40
| | | | | | | | | | | | | | | Currently when allocation of cb item fails, the actual cb function is not called. The is used just in hashtable when the cb function frees the old item which result in memory leak. To fix this, the allocation needs to be separated and happen before the assign operation is done. Reviewed-by: Nikola Pajkovsky <[email protected]> Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> MergeDate: Mon May 11 08:21:55 2026 (Merged from https://github.com/openssl/openssl/pull/31092)
* Increase the query cache insert grow retryIngo Franzki2026-04-271-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | On s390x, the distribution of the query cache hash values is different compared to other architectures, probably because of endianess and pointer alignment being different (the hash key contains pointer values and integers). This leads to the fact that ossl_ht_cache_QUERY_insert() is not always able to add a query during the FIPS selftests, and thus ossl_ht_cache_QUERY_insert() returns -1 is such cases. Increase the number of retries inside ossl_ht_insert() to at least the number elements per neighborhood plus 1. With this it is able to grow the hash table enough so that the queries used during the FIPS selftest can all be added to the hash table, even on s390x. There is still no guarantee that the number of retries is enough for all possible queries. It can still happen that certain queries can't be added to the cache, even on other architectures. This does not really hurt, such queries will just not be cached and are freshly fetched again the next time. Signed-off-by: Ingo Franzki <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Nikola Pajkovsky <[email protected]> MergeDate: Mon Apr 27 05:56:53 2026 (Merged from https://github.com/openssl/openssl/pull/30903)
* crypto/hashtable/hashtable.c: fix hashtable grow cleanup for aligned allocationMounir IDRASSI2026-04-261-2/+2
| | | | | | | | | | | | | | Update grow_hashtable cleanup to free the neighborhood allocation through newmd->neighborhood_ptr_to_free instead of newmd->neighborhoods. Fixes: cc4ea5e00028 "Introduce new internal hashtable implementation" Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Nikola Pajkovsky <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Eugene Syromiatnikov <[email protected]> MergeDate: Sun Apr 26 14:26:08 2026 (Merged from https://github.com/openssl/openssl/pull/30859)
* Add ability to extract computed hash from hashtableNeil Horman2026-03-241-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | One thing we can do to speed up hash table lookups is to cache/reuse computed hash values when interrogating a hash table multiple times in rapid succession. We follow this pattern frequently when using hashtables: value = lookup_hash(key) if (value == NULL) value = new_value() insert_to_hash(key, value) Note that we use the same key for the lookup and the insert. So if we had a way to preserve the value this key hashed to, we can avoid having to do a second hash computation during the lookup. These new macros give us that. The HT_KEY structure now stores the computed hash value in the key, which can be extracted and reused by the caller with the HT_INIT_KEY_CACHED macro. When set, the cached hash value is used, rather than needing to recompute the hash for any subsequent operations Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> MergeDate: Tue Mar 24 16:23:05 2026 (Merged from https://github.com/openssl/openssl/pull/30254)
* Ensure entries in the neighborhood struct are 8 byte alignedNeil Horman2026-03-101-1/+3
| | | | | | | | | | | | | | | This struct is accessed via atomics, which on some platforms require 8 byte alignment. Generally compilers provide that alignment, since the first element of the struct is a uint64_t, but it appears that not all do. Force the alignment to be correct Reviewed-by: Eugene Syromiatnikov <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> Reviewed-by: Nikola Pajkovsky <[email protected]> MergeDate: Tue Mar 10 18:16:34 2026 (Merged from https://github.com/openssl/openssl/pull/30293)
* 4.0-POST-CLANG-FORMAT-WEBKIT4.0-POST-CLANG-FORMAT-WEBKITBob Beck2025-12-091-40/+36
| | | | | | | Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Nikola Pajkovsky <[email protected]> (Merged from https://github.com/openssl/openssl/pull/29242)
* hashtable: add option to disable RCU locksNikola Pajkovsky2025-10-021-44/+141
| | | | | | | | | | | | | | | | | | | | | | | | 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 <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> Reviewed-by: Neil Horman <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28677)
* hashtable: pass HT into hash functionNikola Pajkovsky2025-10-021-4/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> Reviewed-by: Neil Horman <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28677)
* Move OPENSSL_SMALL_FOOTPRINT-related logic from aligned_alloc to the only callerEugene Syromiatnikov2025-09-161-1/+4
| | | | | | | | | | | | | | | | | | Originally, CRYPTO_aligned_alloc() returned NULL if OpenSSL was built with OPENSSL_SMALL_FOOTPRINT defined, which is a weird place for such a consideration; moreover it means that every caller requires to implement some form of a fallback (and manually over-allocate and then align the returned memory if the alignment is a requirement), which is counter-productive (and outright ridiculous in environments with posix_memalign() available). Move the OPENSSL_SMALL_FOOTPRINT consideration to the only current caller and update the documentation and tests accordingly. Signed-off-by: Eugene Syromiatnikov <[email protected]> Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28295)
* Remove assert in core_namemap.cNeil Horman2025-08-121-0/+1
| | | | | | | | | | | | | | | | | The namemap_add_name function has an assertion to check for the failure os ossl_ht_insert. Its there because we assume the operation can't fail since we're under write lock But it can fail if we get a malloc failure, as thats what we're testing for here. Remove the assert and handle the failure properly. Reviewed-by: Tomas Mraz <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28216)
* Fix failure checking on rcu_read_lockNeil Horman2025-08-091-2/+2
| | | | | | | | | | | | | | | | | | | | | | 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. Fixes openssl/project#1315 Reviewed-by: Paul Yang <[email protected]> Reviewed-by: Dmitry Belyavskiy <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28195)
* crypto: use array memory (re)allocation routinesEugene Syromiatnikov2025-08-081-3/+4
| | | | | | | | | | | Co-Authored-by: Alexandr Nedvedicky <[email protected]> Signed-off-by: Eugene Syromiatnikov <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Neil Horman <[email protected]> (Merged from https://github.com/openssl/openssl/pull/28059)
* Copyright year updatesopenssl-machine2025-03-121-1/+1
| | | | | | Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Matt Caswell <[email protected]> Release: yes
* Rename fnv1a_hash() to ossl_fnv1a_hash()Tomas Mraz2025-02-252-2/+2
| | | | | | | | | | | | It is no longer static. Also add it to libssl only with quic enabled. Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> Reviewed-by: Tim Hudson <[email protected]> (Merged from https://github.com/openssl/openssl/pull/26882)
* de-duplicate fnv1a_hashNeil Horman2025-02-173-13/+25
| | | | | | | | | I cloned a copy of fnv1a_hash from hashtable.c. Deduplicate that so we have common source code. Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Saša Nedvědický <[email protected]> (Merged from https://github.com/openssl/openssl/pull/26517)
* ossl_ht_insert(): Allow for 4 iterations of grow_hashtable()Tomas Mraz2024-08-221-1/+1
| | | | | | Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Neil Horman <[email protected]> (Merged from https://github.com/openssl/openssl/pull/25273)
* hashtable.c: Code style fixesTomas Mraz2024-08-211-6/+6
| | | | | | Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* For lockless reads use the whole hashtable for colliding entriesTomas Mraz2024-08-211-43/+71
| | | | | | | | | | | | 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 <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* hashtable: Support lockless readsTomas Mraz2024-08-212-6/+13
| | | | | | | | | Also build it in the FIPS provider too and properly report error on insert when hashtable cannot be grown. Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* hashtable.c: Avoid infinite loop in ossl_ht_insert()Tomas Mraz2024-08-211-8/+10
| | | | | | Reviewed-by: Neil Horman <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* some performance improvementsNeil Horman2024-08-211-11/+12
| | | | | | Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* alternate collision checking supportNeil Horman2024-08-211-17/+43
| | | | | | | | | | | 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 <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24504)
* Add error checking to CRYPTO_atomic_[load|store] callsNeil Horman2024-07-311-10/+18
| | | | | | | | | 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 <[email protected]> Reviewed-by: Tom Cosgrove <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24969)
* Make ossl_ht_delete use read-once semanticsNeil Horman2024-07-311-7/+7
| | | | | | | | | 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 <[email protected]> Reviewed-by: Tom Cosgrove <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24969)
* Convert hashtable to using ossl_rcu_deref on lookupNeil Horman2024-07-031-2/+1
| | | | | | | | | | | | | | | | 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 <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24682)
* Fix typos found by codespellDimitri Papadopoulos2024-06-241-1/+1
| | | | | | Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Kurt Roeckx <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24691)
* Fix coverity-1596616Neil Horman2024-04-261-1/+2
| | | | | | | | | Need to add a null check prior to derefencing pointer for free Reviewed-by: Matt Caswell <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Tomas Mraz <[email protected]> (Merged from https://github.com/openssl/openssl/pull/24263)
* Introduce new internal hashtable implementationNeil Horman2024-04-242-0/+694
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 <[email protected]> Reviewed-by: Paul Dale <[email protected]> (Merged from https://github.com/openssl/openssl/pull/23671)
generated by cgit (git 2.51.2) at 2026-10-25 16:25:07 +0100