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 CRYPTO_RCU_CB_ITEM *cbi = NULL;
289
290 newmd = OPENSSL_zalloc(sizeof(*newmd));
291 if (newmd == NULL)
292 return 0;
293
294 newmd->neighborhoods = alloc_new_neighborhood_list(DEFAULT_NEIGH_LEN,
295 &newmd->neighborhood_ptr_to_free);
296 if (newmd->neighborhoods == NULL) {
297 OPENSSL_free(newmd);
298 return 0;
299 }
300
301 newmd->neighborhood_mask = DEFAULT_NEIGH_LEN - 1;
302
303 cbi = ossl_rcu_cb_item_new();
304 if (cbi == NULL) {
305 OPENSSL_free(newmd->neighborhood_ptr_to_free);
306 OPENSSL_free(newmd);
307 return 0;
308 }
309
310 /* Swap the old and new mutable data sets */
311 oldmd = ossl_rcu_deref(&h->md);
312 ossl_rcu_assign_ptr(&h->md, &newmd);
313
314 /* Set the number of entries to 0 */
315 h->wpd.value_count = 0;
316 h->wpd.neighborhood_len = DEFAULT_NEIGH_LEN;
317
318 ossl_rcu_call(h->lock, cbi, free_oldmd, oldmd);
319 h->wpd.need_sync = 1;
320
321 return 1;
322 }
323
ossl_ht_flush(HT * h)324 int ossl_ht_flush(HT *h)
325 {
326 return ossl_ht_flush_internal(h);
327 }
328
ossl_ht_free(HT * h)329 void ossl_ht_free(HT *h)
330 {
331 int flush_ok;
332
333 if (h == NULL)
334 return;
335
336 ossl_ht_write_lock(h);
337 flush_ok = ossl_ht_flush_internal(h);
338 ossl_ht_write_unlock(h);
339 /* Freeing the lock does a final sync for us */
340 CRYPTO_THREAD_lock_free(h->atomic_lock);
341 ossl_rcu_lock_free(h->lock);
342 if (flush_ok) {
343 OPENSSL_free(h->md->neighborhood_ptr_to_free);
344 OPENSSL_free(h->md);
345 } else {
346 free_oldmd(h->md);
347 }
348 OPENSSL_free(h);
349 return;
350 }
351
ossl_ht_count(HT * h)352 size_t ossl_ht_count(HT *h)
353 {
354 size_t count;
355
356 count = h->wpd.value_count;
357 return count;
358 }
359
ossl_ht_foreach_until(HT * h,int (* cb)(HT_VALUE * obj,void * arg),void * arg)360 void ossl_ht_foreach_until(HT *h, int (*cb)(HT_VALUE *obj, void *arg),
361 void *arg)
362 {
363 size_t i, j;
364 struct ht_mutable_data_st *md;
365
366 md = ossl_rcu_deref(&h->md);
367 for (i = 0; i < md->neighborhood_mask + 1; i++) {
368 PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
369 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
370 if (md->neighborhoods[i].entries[j].value != NULL) {
371 if (!cb((HT_VALUE *)md->neighborhoods[i].entries[j].value, arg))
372 goto out;
373 }
374 }
375 }
376 out:
377 return;
378 }
379
ossl_ht_filter(HT * h,size_t max_len,int (* filter)(HT_VALUE * obj,void * arg),void * arg)380 HT_VALUE_LIST *ossl_ht_filter(HT *h, size_t max_len,
381 int (*filter)(HT_VALUE *obj, void *arg),
382 void *arg)
383 {
384 struct ht_mutable_data_st *md;
385 HT_VALUE_LIST *list = OPENSSL_zalloc(sizeof(HT_VALUE_LIST)
386 + (sizeof(HT_VALUE *) * max_len));
387 size_t i, j;
388 struct ht_internal_value_st *v;
389
390 if (list == NULL)
391 return NULL;
392
393 /*
394 * The list array lives just beyond the end of
395 * the struct
396 */
397 list->list = (HT_VALUE **)(list + 1);
398
399 md = ossl_rcu_deref(&h->md);
400 for (i = 0; i < md->neighborhood_mask + 1; i++) {
401 PREFETCH_NEIGHBORHOOD(md->neighborhoods[i + 1]);
402 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
403 v = md->neighborhoods[i].entries[j].value;
404 if (v != NULL && filter((HT_VALUE *)v, arg)) {
405 list->list[list->list_len++] = (HT_VALUE *)v;
406 if (list->list_len == max_len)
407 goto out;
408 }
409 }
410 }
411 out:
412 return list;
413 }
414
ossl_ht_value_list_free(HT_VALUE_LIST * list)415 void ossl_ht_value_list_free(HT_VALUE_LIST *list)
416 {
417 OPENSSL_free(list);
418 }
419
compare_hash(uint64_t hash1,uint64_t hash2)420 static int compare_hash(uint64_t hash1, uint64_t hash2)
421 {
422 return (hash1 == hash2);
423 }
424
free_old_neigh_table(void * arg)425 static void free_old_neigh_table(void *arg)
426 {
427 struct ht_mutable_data_st *oldmd = arg;
428
429 OPENSSL_free(oldmd->neighborhood_ptr_to_free);
430 OPENSSL_free(oldmd);
431 }
432
433 /*
434 * Increase hash table bucket list
435 * must be called with write_lock held
436 */
grow_hashtable(HT * h,size_t oldsize)437 static int grow_hashtable(HT *h, size_t oldsize)
438 {
439 struct ht_mutable_data_st *newmd;
440 struct ht_mutable_data_st *oldmd = ossl_rcu_deref(&h->md);
441 CRYPTO_RCU_CB_ITEM *cbi = NULL;
442 int rc = 0;
443 uint64_t oldi, oldj, newi, newj;
444 uint64_t oldhash;
445 struct ht_internal_value_st *oldv;
446 int rehashed;
447 size_t newsize = oldsize * 2;
448
449 if (h->config.lockless_reads)
450 goto out;
451
452 if ((newmd = OPENSSL_zalloc(sizeof(*newmd))) == NULL)
453 goto out;
454
455 /* bucket list is always a power of 2 */
456 newmd->neighborhoods = alloc_new_neighborhood_list(oldsize * 2,
457 &newmd->neighborhood_ptr_to_free);
458 if (newmd->neighborhoods == NULL)
459 goto out_free;
460
461 /* being a power of 2 makes for easy mask computation */
462 newmd->neighborhood_mask = (newsize - 1);
463
464 /*
465 * Now we need to start rehashing entries
466 * Note we don't need to use atomics here as the new
467 * mutable data hasn't been published
468 */
469 for (oldi = 0; oldi < h->wpd.neighborhood_len; oldi++) {
470 PREFETCH_NEIGHBORHOOD(oldmd->neighborhoods[oldi + 1]);
471 for (oldj = 0; oldj < NEIGHBORHOOD_LEN; oldj++) {
472 oldv = oldmd->neighborhoods[oldi].entries[oldj].value;
473 if (oldv == NULL)
474 continue;
475 oldhash = oldmd->neighborhoods[oldi].entries[oldj].hash;
476 newi = oldhash & newmd->neighborhood_mask;
477 rehashed = 0;
478 for (newj = 0; newj < NEIGHBORHOOD_LEN; newj++) {
479 if (newmd->neighborhoods[newi].entries[newj].value == NULL) {
480 newmd->neighborhoods[newi].entries[newj].value = oldv;
481 newmd->neighborhoods[newi].entries[newj].hash = oldhash;
482 rehashed = 1;
483 break;
484 }
485 }
486 if (rehashed == 0) {
487 /* we ran out of space in a neighborhood, grow again */
488 OPENSSL_free(newmd->neighborhood_ptr_to_free);
489 OPENSSL_free(newmd);
490 return grow_hashtable(h, newsize);
491 }
492 }
493 }
494
495 /*
496 * Pre allocate the rcu callback item before assigning the newmd.
497 */
498 cbi = ossl_rcu_cb_item_new();
499 if (cbi == NULL)
500 goto out_free;
501
502 /*
503 * Now that our entries are all hashed into the new bucket list
504 * update our bucket_len and target_max_load
505 */
506 h->wpd.neighborhood_len = newsize;
507
508 /*
509 * Now we replace the old mutable data with the new
510 */
511 ossl_rcu_assign_ptr(&h->md, &newmd);
512 ossl_rcu_call(h->lock, cbi, free_old_neigh_table, oldmd);
513 h->wpd.need_sync = 1;
514 /*
515 * And we're done
516 */
517 rc = 1;
518
519 out:
520 return rc;
521 out_free:
522 OPENSSL_free(newmd->neighborhood_ptr_to_free);
523 OPENSSL_free(newmd);
524 goto out;
525 }
526
free_old_ht_value(void * arg)527 static void free_old_ht_value(void *arg)
528 {
529 HT_VALUE *h = (HT_VALUE *)arg;
530
531 /*
532 * Note, this is only called on replacement,
533 * the caller is responsible for freeing the
534 * held data, we just need to free the wrapping
535 * struct here
536 */
537 OPENSSL_free(h);
538 }
539
match_key(HT_KEY * a,HT_KEY * b)540 static ossl_inline int match_key(HT_KEY *a, HT_KEY *b)
541 {
542 /*
543 * keys match if they are both present, the same size
544 * and compare equal in memory
545 */
546 PREFETCH(a->keybuf);
547 PREFETCH(b->keybuf);
548 if (a->keybuf != NULL && b->keybuf != NULL && a->keysize == b->keysize)
549 return !memcmp(a->keybuf, b->keybuf, a->keysize);
550
551 return 1;
552 }
553
ossl_ht_insert_locked(HT * h,uint64_t hash,struct ht_internal_value_st * newval,HT_VALUE ** olddata)554 static int ossl_ht_insert_locked(HT *h, uint64_t hash,
555 struct ht_internal_value_st *newval,
556 HT_VALUE **olddata)
557 {
558 struct ht_mutable_data_st *md = h->md;
559 uint64_t neigh_idx_start = hash & md->neighborhood_mask;
560 uint64_t neigh_idx = neigh_idx_start;
561 size_t j;
562 uint64_t ihash;
563 HT_VALUE *ival;
564 size_t empty_idx = SIZE_MAX;
565 int lockless_reads = h->config.lockless_reads;
566 CRYPTO_RCU_CB_ITEM *cbi;
567
568 do {
569 PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
570
571 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
572 ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
573 if (ival == NULL) {
574 empty_idx = j;
575 /* lockless_reads implies no deletion, we can break out */
576 if (lockless_reads)
577 goto not_found;
578 continue;
579 }
580 if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
581 &ihash, h->atomic_lock))
582 return 0;
583 if (compare_hash(hash, ihash) && match_key(&newval->value.key, &ival->key)) {
584 if (olddata == NULL) {
585 /* This would insert a duplicate -> fail */
586 return 0;
587 }
588 /* Do a replacement */
589 cbi = ossl_rcu_cb_item_new();
590 if (cbi == NULL)
591 return 0;
592 if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[j].hash,
593 hash, h->atomic_lock))
594 return 0;
595 *olddata = (HT_VALUE *)md->neighborhoods[neigh_idx].entries[j].value;
596 ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[j].value,
597 &newval);
598 ossl_rcu_call(h->lock, cbi, free_old_ht_value, *olddata);
599 h->wpd.need_sync = 1;
600 return 1;
601 }
602 }
603 if (!lockless_reads)
604 break;
605 /* Continue search in subsequent neighborhoods */
606 neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
607 } while (neigh_idx != neigh_idx_start);
608
609 not_found:
610 /* If we get to here, its just an insert */
611 if (empty_idx == SIZE_MAX)
612 return -1; /* out of space */
613 if (!CRYPTO_atomic_store(&md->neighborhoods[neigh_idx].entries[empty_idx].hash,
614 hash, h->atomic_lock))
615 return 0;
616 h->wpd.value_count++;
617 ossl_rcu_assign_ptr(&md->neighborhoods[neigh_idx].entries[empty_idx].value,
618 &newval);
619 return 1;
620 }
621
alloc_new_value(HT * h,HT_KEY * key,void * data,uintptr_t * type)622 static struct ht_internal_value_st *alloc_new_value(HT *h, HT_KEY *key,
623 void *data,
624 uintptr_t *type)
625 {
626 struct ht_internal_value_st *tmp;
627 size_t nvsize = sizeof(*tmp);
628
629 if (h->config.collision_check == 1)
630 nvsize += key->keysize;
631
632 tmp = OPENSSL_malloc(nvsize);
633
634 if (tmp == NULL)
635 return NULL;
636
637 tmp->ht = h;
638 tmp->value.value = data;
639 tmp->value.type_id = type;
640 tmp->value.key.keybuf = NULL;
641 if (h->config.collision_check) {
642 tmp->value.key.keybuf = (uint8_t *)(tmp + 1);
643 tmp->value.key.keysize = key->keysize;
644 memcpy(tmp->value.key.keybuf, key->keybuf, key->keysize);
645 }
646
647 return tmp;
648 }
649
free_value(struct ht_internal_value_st * v)650 static void free_value(struct ht_internal_value_st *v)
651 {
652 OPENSSL_free(v);
653 }
654
ossl_ht_insert(HT * h,HT_KEY * key,HT_VALUE * data,HT_VALUE ** olddata)655 int ossl_ht_insert(HT *h, HT_KEY *key, HT_VALUE *data, HT_VALUE **olddata)
656 {
657 struct ht_internal_value_st *newval = NULL;
658 uint64_t hash;
659 int rc = 0;
660 int i;
661
662 if (data->value == NULL)
663 goto out;
664
665 newval = alloc_new_value(h, key, data->value, data->type_id);
666 if (newval == NULL)
667 goto out;
668
669 /*
670 * we have to take our lock here to prevent other changes
671 * to the bucket list
672 */
673 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
674
675 for (i = 0;
676 (rc = ossl_ht_insert_locked(h, hash, newval, olddata)) == -1
677 && i <= (int)NEIGHBORHOOD_LEN;
678 ++i)
679 if (!grow_hashtable(h, h->wpd.neighborhood_len)) {
680 rc = -1;
681 break;
682 }
683
684 if (rc <= 0)
685 free_value(newval);
686
687 out:
688 return rc;
689 }
690
ossl_ht_get(HT * h,HT_KEY * key)691 HT_VALUE *ossl_ht_get(HT *h, HT_KEY *key)
692 {
693 struct ht_mutable_data_st *md;
694 uint64_t hash;
695 uint64_t neigh_idx_start;
696 uint64_t neigh_idx;
697 struct ht_internal_value_st *ival = NULL;
698 size_t j;
699 uint64_t ehash;
700 int lockless_reads = h->config.lockless_reads;
701
702 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
703
704 md = ossl_rcu_deref(&h->md);
705 neigh_idx = neigh_idx_start = hash & md->neighborhood_mask;
706 do {
707 PREFETCH_NEIGHBORHOOD(md->neighborhoods[neigh_idx]);
708 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
709 ival = ossl_rcu_deref(&md->neighborhoods[neigh_idx].entries[j].value);
710 if (ival == NULL) {
711 if (lockless_reads)
712 /* lockless_reads implies no deletion, we can break out */
713 return NULL;
714 continue;
715 }
716 if (!CRYPTO_atomic_load(&md->neighborhoods[neigh_idx].entries[j].hash,
717 &ehash, h->atomic_lock))
718 return NULL;
719 if (compare_hash(hash, ehash) && match_key(&ival->value.key, key))
720 return (HT_VALUE *)ival;
721 }
722 if (!lockless_reads)
723 break;
724 /* Continue search in subsequent neighborhoods */
725 neigh_idx = (neigh_idx + 1) & md->neighborhood_mask;
726 } while (neigh_idx != neigh_idx_start);
727
728 return NULL;
729 }
730
free_old_entry(void * arg)731 static void free_old_entry(void *arg)
732 {
733 struct ht_internal_value_st *v = arg;
734
735 v->ht->config.ht_free_fn((HT_VALUE *)v);
736 free_value(v);
737 }
738
ossl_ht_delete(HT * h,HT_KEY * key)739 int ossl_ht_delete(HT *h, HT_KEY *key)
740 {
741 uint64_t hash;
742 uint64_t neigh_idx;
743 size_t j;
744 struct ht_internal_value_st *v = NULL;
745 HT_VALUE *nv = NULL;
746 int rc = 0;
747
748 if (h->config.lockless_reads)
749 return 0;
750
751 hash = h->config.ht_hash_fn(key->keybuf, key->keysize);
752
753 neigh_idx = hash & h->md->neighborhood_mask;
754 PREFETCH_NEIGHBORHOOD(h->md->neighborhoods[neigh_idx]);
755 for (j = 0; j < NEIGHBORHOOD_LEN; j++) {
756 v = (struct ht_internal_value_st *)h->md->neighborhoods[neigh_idx].entries[j].value;
757 if (v == NULL)
758 continue;
759 if (compare_hash(hash, h->md->neighborhoods[neigh_idx].entries[j].hash)
760 && match_key(key, &v->value.key)) {
761 CRYPTO_RCU_CB_ITEM *cbi = ossl_rcu_cb_item_new();
762 if (cbi == NULL)
763 break;
764 if (!CRYPTO_atomic_store(&h->md->neighborhoods[neigh_idx].entries[j].hash,
765 0, h->atomic_lock))
766 break;
767 h->wpd.value_count--;
768 ossl_rcu_assign_ptr(&h->md->neighborhoods[neigh_idx].entries[j].value,
769 &nv);
770 ossl_rcu_call(h->lock, cbi, free_old_entry, v);
771 h->wpd.need_sync = 1;
772 rc = 1;
773 break;
774 }
775 }
776 return rc;
777 }
778