1 /*
2 * Copyright 2024-2026 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 *
9 *
10 *
11 * Notes On hash table design and layout
12 * This hashtable uses a hopscotch algorithm to do indexing. The data structure
13 * looks as follows:
14 *
15 * hash +--------------+
16 * value+------->+ HT_VALUE |
17 * + +--------------+
18 * +-------+
19 * | |
20 * +---------------------------------------------------------+
21 * | | | | | |
22 * | entry | entry | entry | entry | |
23 * | | | | | |
24 * +---------------------------------------------------------+
25 * | | |
26 * | | |
27 * +---------------------------------------------------------+
28 * | + + +
29 * | neighborhood[0] neighborhood[1] |
30 * | |
31 * | |
32 * +---------------------------------------------------------+
33 * |
34 * +
35 * neighborhoods
36 *
37 * On lookup/insert/delete, the items key is hashed to a 64 bit value
38 * and the result is masked to provide an index into the neighborhoods
39 * table. Once a neighborhood is determined, an in-order search is done
40 * of the elements in the neighborhood indexes entries for a matching hash
41 * value, if found, the corresponding HT_VALUE is used for the respective
42 * operation. The number of entries in a neighborhood is determined at build
43 * time based on the cacheline size of the target CPU. The intent is for a
44 * neighborhood to have all entries in the neighborhood fit into a single cache
45 * line to speed up lookups. If all entries in a neighborhood are in use at the
46 * time of an insert, the table is expanded and rehashed.
47 *
48 * Lockless reads hash table is based on the same design but does not
49 * allow growing and deletion. Thus subsequent neighborhoods are always
50 * searched for a match until an empty entry is found.
51 */
52
53 #include <string.h>
54 #include <internal/rcu.h>
55 #include <internal/hashtable.h>
56 #include <internal/hashfunc.h>
57 #include <openssl/rand.h>
58
59 /*
60 * gcc defines __SANITIZE_THREAD__
61 * but clang uses the feature attributes api
62 * map the latter to the former
63 */
64 #if defined(__clang__) && defined(__has_feature)
65 #if __has_feature(thread_sanitizer)
66 #define __SANITIZE_THREADS__
67 #endif
68 #endif
69
70 #ifdef __SANITIZE_THREADS__
71 #include <sanitizer/tsan_interface.h>
72 #endif
73
74 #include "internal/numbers.h"
75 /*
76 * When we do a lookup/insert/delete, there is a high likelihood
77 * that we will iterate over at least part of the neighborhood list
78 * As such, because we design a neighborhood entry to fit into a single
79 * cache line it is advantageous, when supported to fetch the entire
80 * structure for faster lookups
81 */
82 #if defined(__GNUC__) || defined(__CLANG__)
83 #define PREFETCH_NEIGHBORHOOD(x) __builtin_prefetch(x.entries)
84 #define PREFETCH(x) __builtin_prefetch(x)
85 #define ALIGN __attribute__((aligned(8)))
86 #else
87 #define PREFETCH_NEIGHBORHOOD(x)
88 #define PREFETCH(x)
89 #define ALIGN
90 #endif
91
92 /*
93 * Define our neighborhood list length
94 * Note: It should always be a power of 2
95 */
96 #define DEFAULT_NEIGH_LEN_LOG 4
97 #define DEFAULT_NEIGH_LEN (1 << DEFAULT_NEIGH_LEN_LOG)
98
99 /*
100 * For now assume cache line size is 64 bytes
101 */
102 #define CACHE_LINE_BYTES 64
103 #define CACHE_LINE_ALIGNMENT CACHE_LINE_BYTES
104
105 #define NEIGHBORHOOD_LEN (CACHE_LINE_BYTES / sizeof(struct ht_neighborhood_entry_st))
106 /*
107 * Defines our chains of values
108 */
109 struct ht_internal_value_st {
110 HT_VALUE value;
111 HT *ht;
112 };
113
114 struct ht_neighborhood_entry_st {
115 uint64_t hash;
116 struct ht_internal_value_st *value;
117 } ALIGN;
118
119 struct ht_neighborhood_st {
120 struct ht_neighborhood_entry_st entries[NEIGHBORHOOD_LEN];
121 };
122
123 /*
124 * Updates to data in this struct
125 * require an rcu sync after modification
126 * prior to free
127 */
128 struct ht_mutable_data_st {
129 struct ht_neighborhood_st *neighborhoods;
130 void *neighborhood_ptr_to_free;
131 uint64_t neighborhood_mask;
132 };
133
134 /*
135 * Private data may be updated on the write
136 * side only, and so do not require rcu sync
137 */
138 struct ht_write_private_data_st {
139 size_t neighborhood_len;
140 size_t value_count;
141 int need_sync;
142 };
143
144 struct ht_internal_st {
145 HT_CONFIG config;
146 CRYPTO_RCU_LOCK *lock;
147 CRYPTO_RWLOCK *atomic_lock;
148 struct ht_mutable_data_st *md;
149 struct ht_write_private_data_st wpd;
150 };
151
152 static void free_value(struct ht_internal_value_st *v);
153
alloc_new_neighborhood_list(size_t len,void ** freeptr)154 static struct ht_neighborhood_st *alloc_new_neighborhood_list(size_t len,
155 void **freeptr)
156 {
157 struct ht_neighborhood_st *ret;
158
159 ret = OPENSSL_aligned_alloc(sizeof(struct ht_neighborhood_st) * len,
160 CACHE_LINE_BYTES, freeptr);
161
162 /* fall back to regular malloc */
163 if (ret == NULL) {
164 ret = *freeptr = OPENSSL_malloc(sizeof(struct ht_neighborhood_st) * len);
165 if (ret == NULL)
166 return NULL;
167 }
168 memset(ret, 0, sizeof(struct ht_neighborhood_st) * len);
169 return ret;
170 }
171
internal_free_nop(HT_VALUE * v)172 static void internal_free_nop(HT_VALUE *v)
173 {
174 return;
175 }
176
ossl_ht_new(const HT_CONFIG * conf)177 HT *ossl_ht_new(const HT_CONFIG *conf)
178 {
179 HT *new = OPENSSL_zalloc(sizeof(*new));
180
181 if (new == NULL)
182 return NULL;
183
184 new->atomic_lock = CRYPTO_THREAD_lock_new();
185 if (new->atomic_lock == NULL)
186 goto err;
187
188 memcpy(&new->config, conf, sizeof(*conf));
189
190 if (new->config.init_neighborhoods != 0) {
191 new->wpd.neighborhood_len = new->config.init_neighborhoods;
192 /* round up to the next power of 2 */
193 new->wpd.neighborhood_len--;
194 new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 1;
195 new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 2;
196 new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 4;
197 new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 8;
198 new->wpd.neighborhood_len |= new->wpd.neighborhood_len >> 16;
199 new->wpd.neighborhood_len++;
200 } else {
201 new->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;
202 }
203
204 if (new->config.ht_free_fn == NULL)
205 new->config.ht_free_fn = internal_free_nop;
206
207 new->md = OPENSSL_zalloc(sizeof(*new->md));
208 if (new->md == NULL)
209 goto err;
210
211 new->md->neighborhoods = alloc_new_neighborhood_list(new->wpd.neighborhood_len,
212 &new->md->neighborhood_ptr_to_free);
213 if (new->md->neighborhoods == NULL)
214 goto err;
215 new->md->neighborhood_mask = new->wpd.neighborhood_len - 1;
216
217 new->lock = ossl_rcu_lock_new(1, conf->ctx);
218 if (new->lock == NULL)
219 goto err;
220
221 if (new->config.ht_hash_fn == NULL)
222 new->config.ht_hash_fn = ossl_fnv1a_hash;
223
224 return new;
225
226 err:
227 CRYPTO_THREAD_lock_free(new->atomic_lock);
228 ossl_rcu_lock_free(new->lock);
229 if (new->md != NULL)
230 OPENSSL_free(new->md->neighborhood_ptr_to_free);
231 OPENSSL_free(new->md);
232 OPENSSL_free(new);
233 return NULL;
234 }
235
ossl_ht_read_lock(HT * htable)236 void ossl_ht_read_lock(HT *htable)
237 {
238 ossl_rcu_read_lock(htable->lock);
239 }
240
ossl_ht_read_unlock(HT * htable)241 void ossl_ht_read_unlock(HT *htable)
242 {
243 ossl_rcu_read_unlock(htable->lock);
244 }
245
ossl_ht_write_lock(HT * htable)246 void ossl_ht_write_lock(HT *htable)
247 {
248 ossl_rcu_write_lock(htable->lock);
249 htable->wpd.need_sync = 0;
250 }
251
ossl_ht_write_unlock(HT * htable)252 void ossl_ht_write_unlock(HT *htable)
253 {
254 int need_sync = htable->wpd.need_sync;
255
256 htable->wpd.need_sync = 0;
257 ossl_rcu_write_unlock(htable->lock);
258 if (need_sync)
259 ossl_synchronize_rcu(htable->lock);
260 }
261
free_oldmd(void * arg)262 static void free_oldmd(void *arg)
263 {
264 struct ht_mutable_data_st *oldmd = arg;
265 size_t i, j;
266 size_t neighborhood_len = (size_t)oldmd->neighborhood_mask + 1;
267 struct ht_internal_value_st *v;
268
269 for (i = 0; i < neighborhood_len; i++) {
270 PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[i + 1]);
271 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
272 if (oldmd->neighborhoods[i].entries[j].value != NULL) {
273 v = oldmd->neighborhoods[i].entries[j].value;
274 v->ht->config.ht_free_fn((HT_VALUE *)v);
275 free_value(v);
276 }
277 }
278 }
279
280 OPENSSL_free(oldmd->neighborhood_ptr_to_free);
281 OPENSSL_free(oldmd);
282 }
283
ossl_ht_flush_internal(HT * h)284 static int ossl_ht_flush_internal(HT *h)
285 {
286 struct ht_mutable_data_st *newmd = NULL;
287 struct ht_mutable_data_st *oldmd = NULL;
288
289 newmd = OPENSSL_zalloc(sizeof(*newmd));
290 if (newmd == NULL)
291 return 0;
292
293 newmd->neighborhoods = alloc_new_neighborhood_list(DEFAULT_NEIGH_LEN,
294 &newmd->neighborhood_ptr_to_free);
295 if (newmd->neighborhoods == NULL) {
296 OPENSSL_free(newmd);
297 return 0;
298 }
299
300 newmd->neighborhood_mask = DEFAULT_NEIGH_LEN - 1;
301
302 /* Swap the old and new mutable data sets */
303 oldmd = ossl_rcu_deref(&h->md);
304 ossl_rcu_assign_ptr(&h->md, &newmd);
305
306 /* Set the number of entries to 0 */
307 h->wpd.value_count = 0;
308 h->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;
309
310 ossl_rcu_call(h->lock, free_oldmd, oldmd);
311 h->wpd.need_sync = 1;
312 return 1;
313 }
314
ossl_ht_flush(HT * h)315 int ossl_ht_flush(HT *h)
316 {
317 return ossl_ht_flush_internal(h);
318 }
319
ossl_ht_free(HT * h)320 void ossl_ht_free(HT *h)
321 {
322 if (h == NULL)
323 return;
324
325 ossl_ht_write_lock(h);
326 ossl_ht_flush_internal(h);
327 ossl_ht_write_unlock(h);
328 /* Freeing the lock does a final sync for us */
329 CRYPTO_THREAD_lock_free(h->atomic_lock);
330 ossl_rcu_lock_free(h->lock);
331 OPENSSL_free(h->md->neighborhood_ptr_to_free);
332 OPENSSL_free(h->md);
333 OPENSSL_free(h);
334 return;
335 }
336
ossl_ht_count(HT * h)337 size_t ossl_ht_count(HT *h)
338 {
339 size_t count;
340
341 count = h->wpd.value_count;
342 return count;
343 }
344
ossl_ht_foreach_until(HT * h,int (* cb)(HT_VALUE * obj,void * arg),void * arg)345 void ossl_ht_foreach_until(HT *h, int (*cb)(HT_VALUE *obj, void *arg),
346 void *arg)
347 {
348 size_t i, j;
349 struct ht_mutable_data_st *md;
350
351 md = ossl_rcu_deref(&h->md);
352 for (i = 0; i < md->neighborhood_mask + 1; i++) {
353 PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
354 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
355 if (md->neighborhoods[i].entries[j].value != NULL) {
356 if (!cb((HT_VALUE *)md->neighborhoods[i].entries[j].value, arg))
357 goto out;
358 }
359 }
360 }
361 out:
362 return;
363 }
364
ossl_ht_filter(HT * h,size_t max_len,int (* filter)(HT_VALUE * obj,void * arg),void * arg)365 HT_VALUE_LIST *ossl_ht_filter(HT *h, size_t max_len,
366 int (*filter)(HT_VALUE *obj, void *arg),
367 void *arg)
368 {
369 struct ht_mutable_data_st *md;
370 HT_VALUE_LIST *list = OPENSSL_zalloc(sizeof(HT_VALUE_LIST)
371 + (sizeof(HT_VALUE *) * max_len));
372 size_t i, j;
373 struct ht_internal_value_st *v;
374
375 if (list == NULL)
376 return NULL;
377
378 /*
379 * The list array lives just beyond the end of
380 * the struct
381 */
382 list->list = (HT_VALUE **)(list + 1);
383
384 md = ossl_rcu_deref(&h->md);
385 for (i = 0; i < md->neighborhood_mask + 1; i++) {
386 PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
387 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
388 v = md->neighborhoods[i].entries[j].value;
389 if (v != NULL && filter((HT_VALUE *)v, arg)) {
390 list->list[list->list_len++] = (HT_VALUE *)v;
391 if (list->list_len == max_len)
392 goto out;
393 }
394 }
395 }
396 out:
397 return list;
398 }
399
ossl_ht_value_list_free(HT_VALUE_LIST * list)400 void ossl_ht_value_list_free(HT_VALUE_LIST *list)
401 {
402 OPENSSL_free(list);
403 }
404
compare_hash(uint64_t hash1,uint64_t hash2)405 static int compare_hash(uint64_t hash1, uint64_t hash2)
406 {
407 return (hash1 == hash2);
408 }
409
free_old_neigh_table(void * arg)410 static void free_old_neigh_table(void *arg)
411 {
412 struct ht_mutable_data_st *oldmd = arg;
413
414 OPENSSL_free(oldmd->neighborhood_ptr_to_free);
415 OPENSSL_free(oldmd);
416 }
417
418 /*
419 * Increase hash table bucket list
420 * must be called with write_lock held
421 */
grow_hashtable(HT * h,size_t oldsize)422 static int grow_hashtable(HT *h, size_t oldsize)
423 {
424 struct ht_mutable_data_st *newmd;
425 struct ht_mutable_data_st *oldmd = ossl_rcu_deref(&h->md);
426 int rc = 0;
427 uint64_t oldi, oldj, newi, newj;
428 uint64_t oldhash;
429 struct ht_internal_value_st *oldv;
430 int rehashed;
431 size_t newsize = oldsize * 2;
432
433 if (h->config.lockless_reads)
434 goto out;
435
436 if ((newmd = OPENSSL_zalloc(sizeof(*newmd))) == NULL)
437 goto out;
438
439 /* bucket list is always a power of 2 */
440 newmd->neighborhoods = alloc_new_neighborhood_list(oldsize * 2,
441 &newmd->neighborhood_ptr_to_free);
442 if (newmd->neighborhoods == NULL)
443 goto out_free;
444
445 /* being a power of 2 makes for easy mask computation */
446 newmd->neighborhood_mask = (newsize - 1);
447
448 /*
449 * Now we need to start rehashing entries
450 * Note we don't need to use atomics here as the new
451 * mutable data hasn't been published
452 */
453 for (oldi = 0; oldi < h->wpd.neighborhood_len; oldi++) {
454 PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[oldi + 1]);
455 for (oldj = 0; oldj < NEIGHBORHOOD_LEN; oldj++) {
456 oldv = oldmd->neighborhoods[oldi].entries[oldj].value;
457 if (oldv == NULL)
458 continue;
459 oldhash = oldmd->neighborhoods[oldi].entries[oldj].hash;
460 newi = oldhash & newmd->neighborhood_mask;
461 rehashed = 0;
462 for (newj = 0; newj < NEIGHBORHOOD_LEN; newj++) {
463 if (newmd->neighborhoods[newi].entries[newj].value == NULL) {
464 newmd->neighborhoods[newi].entries[newj].value = oldv;
465 newmd->neighborhoods[newi].entries[newj].hash = oldhash;
466 rehashed = 1;
467 break;
468 }
469 }
470 if (rehashed == 0) {
471 /* we ran out of space in a neighborhood, grow again */
472 OPENSSL_free(newmd->neighborhoods);
473 OPENSSL_free(newmd);
474 return grow_hashtable(h, newsize);
475 }
476 }
477 }
478 /*
479 * Now that our entries are all hashed into the new bucket list
480 * update our bucket_len and target_max_load
481 */
482 h->wpd.neighborhood_len = newsize;
483
484 /*
485 * Now we replace the old mutable data with the new
486 */
487 ossl_rcu_assign_ptr(&h->md, &newmd);
488 ossl_rcu_call(h->lock, free_old_neigh_table, oldmd);
489 h->wpd.need_sync = 1;
490 /*
491 * And we're done
492 */
493 rc = 1;
494
495 out:
496 return rc;
497 out_free:
498 OPENSSL_free(newmd->neighborhoods);
499 OPENSSL_free(newmd);
500 goto out;
501 }
502
free_old_ht_value(void * arg)503 static void free_old_ht_value(void *arg)
504 {
505 HT_VALUE *h = (HT_VALUE *)arg;
506
507 /*
508 * Note, this is only called on replacement,
509 * the caller is responsible for freeing the
510 * held data, we just need to free the wrapping
511 * struct here
512 */
513 OPENSSL_free(h);
514 }
515
match_key(HT_KEY * a,HT_KEY * b)516 static ossl_inline int match_key(HT_KEY *a, HT_KEY *b)
517 {
518 /*
519 * keys match if they are both present, the same size
520 * and compare equal in memory
521 */
522 PREFETCH(a->keybuf);
523 PREFETCH(b->keybuf);
524 if (a->keybuf != NULL && b->keybuf != NULL && a->keysize == b->keysize)
525 return !memcmp(a->keybuf, b->keybuf, a->keysize);
526
527 return 1;
528 }
529
ossl_ht_insert_locked(HT * h,uint64_t hash,struct ht_internal_value_st * newval,HT_VALUE ** olddata)530 static int ossl_ht_insert_locked(HT *h, uint64_t hash,
531 struct ht_internal_value_st *newval,
532 HT_VALUE **olddata)
533 {
534 struct ht_mutable_data_st *md = h->md;
535 uint64_t neigh_idx_start = hash & md->neighborhood_mask;
536 uint64_t neigh_idx = neigh_idx_start;
537 size_t j;
538 uint64_t ihash;
539 HT_VALUE *ival;
540 size_t empty_idx = SIZE_MAX;
541 int lockless_reads = h->config.lockless_reads;
542
543 do {
544 PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
545
546 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
547 ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
548 if (ival == NULL) {
549 empty_idx = j;
550 /* lockless_reads implies no deletion, we can break out */
551 if (lockless_reads)
552 goto not_found;
553 continue;
554 }
555 if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
556 &ihash, h->atomic_lock))
557 return 0;
558 if (compare_hash(hash, ihash) && match_key(&newval->value.key, &ival->key)) {
559 if (olddata == NULL) {
560 /* This would insert a duplicate -> fail */
561 return 0;
562 }
563 /* Do a replacement */
564 if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[j].hash,
565 hash, h->atomic_lock))
566 return 0;
567 *olddata = (HT_VALUE *)md->neighborhoods[neigh_idx].entries[j].value;
568 ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[j].value,
569 &newval);
570 ossl_rcu_call(h->lock, free_old_ht_value, *olddata);
571 h->wpd.need_sync = 1;
572 return 1;
573 }
574 }
575 if (!lockless_reads)
576 break;
577 /* Continue search in subsequent neighborhoods */
578 neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
579 } while (neigh_idx != neigh_idx_start);
580
581 not_found:
582 /* If we get to here, its just an insert */
583 if (empty_idx == SIZE_MAX)
584 return -1; /* out of space */
585 if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[empty_idx].hash,
586 hash, h->atomic_lock))
587 return 0;
588 h->wpd.value_count++;
589 ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[empty_idx].value,
590 &newval);
591 return 1;
592 }
593
alloc_new_value(HT * h,HT_KEY * key,void * data,uintptr_t * type)594 static struct ht_internal_value_st *alloc_new_value(HT *h, HT_KEY *key,
595 void *data,
596 uintptr_t *type)
597 {
598 struct ht_internal_value_st *tmp;
599 size_t nvsize = sizeof(*tmp);
600
601 if (h->config.collision_check == 1)
602 nvsize += key->keysize;
603
604 tmp = OPENSSL_malloc(nvsize);
605
606 if (tmp == NULL)
607 return NULL;
608
609 tmp->ht = h;
610 tmp->value.value = data;
611 tmp->value.type_id = type;
612 tmp->value.key.keybuf = NULL;
613 if (h->config.collision_check) {
614 tmp->value.key.keybuf = (uint8_t *)(tmp + 1);
615 tmp->value.key.keysize = key->keysize;
616 memcpy(tmp->value.key.keybuf, key->keybuf, key->keysize);
617 }
618
619 return tmp;
620 }
621
free_value(struct ht_internal_value_st * v)622 static void free_value(struct ht_internal_value_st *v)
623 {
624 OPENSSL_free(v);
625 }
626
ossl_ht_insert(HT * h,HT_KEY * key,HT_VALUE * data,HT_VALUE ** olddata)627 int ossl_ht_insert(HT *h, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata)
628 {
629 struct ht_internal_value_st *newval = NULL;
630 uint64_t hash;
631 int rc = 0;
632 int i;
633
634 if (data->value == NULL)
635 goto out;
636
637 newval = alloc_new_value(h, key, data->value, data->type_id);
638 if (newval == NULL)
639 goto out;
640
641 /*
642 * we have to take our lock here to prevent other changes
643 * to the bucket list
644 */
645 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
646
647 for (i = 0;
648 (rc = ossl_ht_insert_locked(h, hash, newval, olddata)) == -1
649 && i < 4;
650 ++i)
651 if (!grow_hashtable(h, h->wpd.neighborhood_len)) {
652 rc = -1;
653 break;
654 }
655
656 if (rc <= 0)
657 free_value(newval);
658
659 out:
660 return rc;
661 }
662
ossl_ht_get(HT * h,HT_KEY * key)663 HT_VALUE *ossl_ht_get(HT *h, HT_KEY *key)
664 {
665 struct ht_mutable_data_st *md;
666 uint64_t hash;
667 uint64_t neigh_idx_start;
668 uint64_t neigh_idx;
669 struct ht_internal_value_st *ival = NULL;
670 size_t j;
671 uint64_t ehash;
672 int lockless_reads = h->config.lockless_reads;
673
674 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
675
676 md = ossl_rcu_deref(&h->md);
677 neigh_idx = neigh_idx_start = hash & md->neighborhood_mask;
678 do {
679 PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
680 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
681 ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
682 if (ival == NULL) {
683 if (lockless_reads)
684 /* lockless_reads implies no deletion, we can break out */
685 return NULL;
686 continue;
687 }
688 if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
689 &ehash, h->atomic_lock))
690 return NULL;
691 if (compare_hash(hash, ehash) && match_key(&ival->value.key, key))
692 return (HT_VALUE *)ival;
693 }
694 if (!lockless_reads)
695 break;
696 /* Continue search in subsequent neighborhoods */
697 neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
698 } while (neigh_idx != neigh_idx_start);
699
700 return NULL;
701 }
702
free_old_entry(void * arg)703 static void free_old_entry(void *arg)
704 {
705 struct ht_internal_value_st *v = arg;
706
707 v->ht->config.ht_free_fn((HT_VALUE *)v);
708 free_value(v);
709 }
710
ossl_ht_delete(HT * h,HT_KEY * key)711 int ossl_ht_delete(HT *h, HT_KEY *key)
712 {
713 uint64_t hash;
714 uint64_t neigh_idx;
715 size_t j;
716 struct ht_internal_value_st *v = NULL;
717 HT_VALUE *nv = NULL;
718 int rc = 0;
719
720 if (h->config.lockless_reads)
721 return 0;
722
723 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
724
725 neigh_idx = hash & h->md->neighborhood_mask;
726 PREFETCH_NEIGHBORHOOD(h->md->neighborhoods[neigh_idx]);
727 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
728 v = (struct ht_internal_value_st *)h->md->neighborhoods[neigh_idx].entries[j].value;
729 if (v == NULL)
730 continue;
731 if (compare_hash(hash, h->md->neighborhoods[neigh_idx].entries[j].hash)
732 && match_key(key, &v->value.key)) {
733 if (!CRYPTO_atomic_store(&h->md->neighborhoods[neigh_idx].entries[j].hash,
734 0, h->atomic_lock))
735 break;
736 h->wpd.value_count--;
737 ossl_rcu_assign_ptr(&h->md->neighborhoods[neigh_idx].entries[j].value,
738 &nv);
739 rc = 1;
740 break;
741 }
742 }
743 if (rc == 1) {
744 ossl_rcu_call(h->lock, free_old_entry, v);
745 h->wpd.need_sync = 1;
746 }
747 return rc;
748 }
749