1 /*
2  * Copyright 2019-2023 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
4  *
5  * Licensed under the Apache License 2.0 (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10 
11 #include <string.h>
12 #include <stdio.h>
13 #include <stdarg.h>
14 #include <openssl/crypto.h>
15 #include "internal/core.h"
16 #include "internal/property.h"
17 #include "internal/provider.h"
18 #include "internal/tsan_assist.h"
19 #include "crypto/ctype.h"
20 #include <openssl/lhash.h>
21 #include <openssl/rand.h>
22 #include "internal/thread_once.h"
23 #include "crypto/lhash.h"
24 #include "crypto/sparse_array.h"
25 #include "property_local.h"
26 
27 /*
28  * The number of elements in the query cache before we initiate a flush.
29  * If reducing this, also ensure the stochastic test in test/property_test.c
30  * isn't likely to fail.
31  */
32 #define IMPL_CACHE_FLUSH_THRESHOLD  500
33 
34 typedef struct {
35     void *method;
36     int (*up_ref)(void *);
37     void (*free)(void *);
38 } METHOD;
39 
40 typedef struct {
41     const OSSL_PROVIDER *provider;
42     OSSL_PROPERTY_LIST *properties;
43     METHOD method;
44 } IMPLEMENTATION;
45 
46 DEFINE_STACK_OF(IMPLEMENTATION)
47 
48 typedef struct {
49     const OSSL_PROVIDER *provider;
50     const char *query;
51     METHOD method;
52     char body[1];
53 } QUERY;
54 
55 DEFINE_LHASH_OF(QUERY);
56 
57 typedef struct {
58     int nid;
59     STACK_OF(IMPLEMENTATION) *impls;
60     LHASH_OF(QUERY) *cache;
61 } ALGORITHM;
62 
63 struct ossl_method_store_st {
64     OSSL_LIB_CTX *ctx;
65     SPARSE_ARRAY_OF(ALGORITHM) *algs;
66     /*
67      * Lock to protect the |algs| array from concurrent writing, when
68      * individual implementations or queries are inserted.  This is used
69      * by the appropriate functions here.
70      */
71     CRYPTO_RWLOCK *lock;
72     /*
73      * Lock to reserve the whole store.  This is used when fetching a set
74      * of algorithms, via these functions, found in crypto/core_fetch.c:
75      * ossl_method_construct_reserve_store()
76      * ossl_method_construct_unreserve_store()
77      */
78     CRYPTO_RWLOCK *biglock;
79 
80     /* query cache specific values */
81 
82     /* Count of the query cache entries for all algs */
83     size_t cache_nelem;
84 
85     /* Flag: 1 if query cache entries for all algs need flushing */
86     int cache_need_flush;
87 };
88 
89 typedef struct {
90     LHASH_OF(QUERY) *cache;
91     size_t nelem;
92     uint32_t seed;
93     unsigned char using_global_seed;
94 } IMPL_CACHE_FLUSH;
95 
96 DEFINE_SPARSE_ARRAY_OF(ALGORITHM);
97 
98 typedef struct ossl_global_properties_st {
99     OSSL_PROPERTY_LIST *list;
100 #ifndef FIPS_MODULE
101     unsigned int no_mirrored : 1;
102 #endif
103 } OSSL_GLOBAL_PROPERTIES;
104 
105 static void ossl_method_cache_flush_alg(OSSL_METHOD_STORE *store,
106                                         ALGORITHM *alg);
107 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
108 
109 /* Global properties are stored per library context */
ossl_ctx_global_properties_free(void * vglobp)110 static void ossl_ctx_global_properties_free(void *vglobp)
111 {
112     OSSL_GLOBAL_PROPERTIES *globp = vglobp;
113 
114     if (globp != NULL) {
115         ossl_property_free(globp->list);
116         OPENSSL_free(globp);
117     }
118 }
119 
ossl_ctx_global_properties_new(OSSL_LIB_CTX * ctx)120 static void *ossl_ctx_global_properties_new(OSSL_LIB_CTX *ctx)
121 {
122     return OPENSSL_zalloc(sizeof(OSSL_GLOBAL_PROPERTIES));
123 }
124 
125 static const OSSL_LIB_CTX_METHOD ossl_ctx_global_properties_method = {
126     OSSL_LIB_CTX_METHOD_DEFAULT_PRIORITY,
127     ossl_ctx_global_properties_new,
128     ossl_ctx_global_properties_free,
129 };
130 
ossl_ctx_global_properties(OSSL_LIB_CTX * libctx,int loadconfig)131 OSSL_PROPERTY_LIST **ossl_ctx_global_properties(OSSL_LIB_CTX *libctx,
132                                                 int loadconfig)
133 {
134     OSSL_GLOBAL_PROPERTIES *globp;
135 
136 #ifndef FIPS_MODULE
137     if (loadconfig && !OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CONFIG, NULL))
138         return NULL;
139 #endif
140     globp = ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_GLOBAL_PROPERTIES,
141                                   &ossl_ctx_global_properties_method);
142 
143     return globp != NULL ? &globp->list : NULL;
144 }
145 
146 #ifndef FIPS_MODULE
ossl_global_properties_no_mirrored(OSSL_LIB_CTX * libctx)147 int ossl_global_properties_no_mirrored(OSSL_LIB_CTX *libctx)
148 {
149     OSSL_GLOBAL_PROPERTIES *globp
150         = ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_GLOBAL_PROPERTIES,
151                                 &ossl_ctx_global_properties_method);
152 
153     return globp != NULL && globp->no_mirrored ? 1 : 0;
154 }
155 
ossl_global_properties_stop_mirroring(OSSL_LIB_CTX * libctx)156 void ossl_global_properties_stop_mirroring(OSSL_LIB_CTX *libctx)
157 {
158     OSSL_GLOBAL_PROPERTIES *globp
159         = ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_GLOBAL_PROPERTIES,
160                                 &ossl_ctx_global_properties_method);
161 
162     if (globp != NULL)
163         globp->no_mirrored = 1;
164 }
165 #endif
166 
ossl_method_up_ref(METHOD * method)167 static int ossl_method_up_ref(METHOD *method)
168 {
169     return (*method->up_ref)(method->method);
170 }
171 
ossl_method_free(METHOD * method)172 static void ossl_method_free(METHOD *method)
173 {
174     (*method->free)(method->method);
175 }
176 
ossl_property_read_lock(OSSL_METHOD_STORE * p)177 static __owur int ossl_property_read_lock(OSSL_METHOD_STORE *p)
178 {
179     return p != NULL ? CRYPTO_THREAD_read_lock(p->lock) : 0;
180 }
181 
ossl_property_write_lock(OSSL_METHOD_STORE * p)182 static __owur int ossl_property_write_lock(OSSL_METHOD_STORE *p)
183 {
184     return p != NULL ? CRYPTO_THREAD_write_lock(p->lock) : 0;
185 }
186 
ossl_property_unlock(OSSL_METHOD_STORE * p)187 static int ossl_property_unlock(OSSL_METHOD_STORE *p)
188 {
189     return p != 0 ? CRYPTO_THREAD_unlock(p->lock) : 0;
190 }
191 
query_hash(const QUERY * a)192 static unsigned long query_hash(const QUERY *a)
193 {
194     return OPENSSL_LH_strhash(a->query);
195 }
196 
query_cmp(const QUERY * a,const QUERY * b)197 static int query_cmp(const QUERY *a, const QUERY *b)
198 {
199     int res = strcmp(a->query, b->query);
200 
201     if (res == 0 && a->provider != NULL && b->provider != NULL)
202         res = b->provider > a->provider ? 1
203             : b->provider < a->provider ? -1
204             : 0;
205     return res;
206 }
207 
impl_free(IMPLEMENTATION * impl)208 static void impl_free(IMPLEMENTATION *impl)
209 {
210     if (impl != NULL) {
211         ossl_method_free(&impl->method);
212         OPENSSL_free(impl);
213     }
214 }
215 
impl_cache_free(QUERY * elem)216 static void impl_cache_free(QUERY *elem)
217 {
218     if (elem != NULL) {
219         ossl_method_free(&elem->method);
220         OPENSSL_free(elem);
221     }
222 }
223 
impl_cache_flush_alg(ossl_uintmax_t idx,ALGORITHM * alg)224 static void impl_cache_flush_alg(ossl_uintmax_t idx, ALGORITHM *alg)
225 {
226     lh_QUERY_doall(alg->cache, &impl_cache_free);
227     lh_QUERY_flush(alg->cache);
228 }
229 
alg_cleanup(ossl_uintmax_t idx,ALGORITHM * a,void * arg)230 static void alg_cleanup(ossl_uintmax_t idx, ALGORITHM *a, void *arg)
231 {
232     OSSL_METHOD_STORE *store = arg;
233 
234     if (a != NULL) {
235         sk_IMPLEMENTATION_pop_free(a->impls, &impl_free);
236         lh_QUERY_doall(a->cache, &impl_cache_free);
237         lh_QUERY_free(a->cache);
238         OPENSSL_free(a);
239     }
240     if (store != NULL)
241         ossl_sa_ALGORITHM_set(store->algs, idx, NULL);
242 }
243 
244 /*
245  * The OSSL_LIB_CTX param here allows access to underlying property data needed
246  * for computation
247  */
ossl_method_store_new(OSSL_LIB_CTX * ctx)248 OSSL_METHOD_STORE *ossl_method_store_new(OSSL_LIB_CTX *ctx)
249 {
250     OSSL_METHOD_STORE *res;
251 
252     res = OPENSSL_zalloc(sizeof(*res));
253     if (res != NULL) {
254         res->ctx = ctx;
255         if ((res->algs = ossl_sa_ALGORITHM_new()) == NULL
256             || (res->lock = CRYPTO_THREAD_lock_new()) == NULL
257             || (res->biglock = CRYPTO_THREAD_lock_new()) == NULL) {
258             ossl_method_store_free(res);
259             return NULL;
260         }
261     }
262     return res;
263 }
264 
ossl_method_store_free(OSSL_METHOD_STORE * store)265 void ossl_method_store_free(OSSL_METHOD_STORE *store)
266 {
267     if (store != NULL) {
268         if (store->algs != NULL)
269             ossl_sa_ALGORITHM_doall_arg(store->algs, &alg_cleanup, store);
270         ossl_sa_ALGORITHM_free(store->algs);
271         CRYPTO_THREAD_lock_free(store->lock);
272         CRYPTO_THREAD_lock_free(store->biglock);
273         OPENSSL_free(store);
274     }
275 }
276 
ossl_method_lock_store(OSSL_METHOD_STORE * store)277 int ossl_method_lock_store(OSSL_METHOD_STORE *store)
278 {
279     return store != NULL ? CRYPTO_THREAD_write_lock(store->biglock) : 0;
280 }
281 
ossl_method_unlock_store(OSSL_METHOD_STORE * store)282 int ossl_method_unlock_store(OSSL_METHOD_STORE *store)
283 {
284     return store != NULL ? CRYPTO_THREAD_unlock(store->biglock) : 0;
285 }
286 
ossl_method_store_retrieve(OSSL_METHOD_STORE * store,int nid)287 static ALGORITHM *ossl_method_store_retrieve(OSSL_METHOD_STORE *store, int nid)
288 {
289     return ossl_sa_ALGORITHM_get(store->algs, nid);
290 }
291 
ossl_method_store_insert(OSSL_METHOD_STORE * store,ALGORITHM * alg)292 static int ossl_method_store_insert(OSSL_METHOD_STORE *store, ALGORITHM *alg)
293 {
294     return ossl_sa_ALGORITHM_set(store->algs, alg->nid, alg);
295 }
296 
ossl_method_store_add(OSSL_METHOD_STORE * store,const OSSL_PROVIDER * prov,int nid,const char * properties,void * method,int (* method_up_ref)(void *),void (* method_destruct)(void *))297 int ossl_method_store_add(OSSL_METHOD_STORE *store, const OSSL_PROVIDER *prov,
298                           int nid, const char *properties, void *method,
299                           int (*method_up_ref)(void *),
300                           void (*method_destruct)(void *))
301 {
302     ALGORITHM *alg = NULL;
303     IMPLEMENTATION *impl;
304     int ret = 0;
305     int i;
306 
307     if (nid <= 0 || method == NULL || store == NULL)
308         return 0;
309     if (properties == NULL)
310         properties = "";
311 
312     if (!ossl_assert(prov != NULL))
313         return 0;
314 
315     /* Create new entry */
316     impl = OPENSSL_malloc(sizeof(*impl));
317     if (impl == NULL)
318         return 0;
319     impl->method.method = method;
320     impl->method.up_ref = method_up_ref;
321     impl->method.free = method_destruct;
322     if (!ossl_method_up_ref(&impl->method)) {
323         OPENSSL_free(impl);
324         return 0;
325     }
326     impl->provider = prov;
327 
328     /* Insert into the hash table if required */
329     if (!ossl_property_write_lock(store)) {
330         OPENSSL_free(impl);
331         return 0;
332     }
333     ossl_method_cache_flush(store, nid);
334     if ((impl->properties = ossl_prop_defn_get(store->ctx, properties)) == NULL) {
335         impl->properties = ossl_parse_property(store->ctx, properties);
336         if (impl->properties == NULL)
337             goto err;
338         if (!ossl_prop_defn_set(store->ctx, properties, &impl->properties)) {
339             ossl_property_free(impl->properties);
340             impl->properties = NULL;
341             goto err;
342         }
343     }
344 
345     alg = ossl_method_store_retrieve(store, nid);
346     if (alg == NULL) {
347         if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
348                 || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
349                 || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
350             goto err;
351         alg->nid = nid;
352         if (!ossl_method_store_insert(store, alg))
353             goto err;
354     }
355 
356     /* Push onto stack if there isn't one there already */
357     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
358         const IMPLEMENTATION *tmpimpl = sk_IMPLEMENTATION_value(alg->impls, i);
359 
360         if (tmpimpl->provider == impl->provider
361             && tmpimpl->properties == impl->properties)
362             break;
363     }
364     if (i == sk_IMPLEMENTATION_num(alg->impls)
365         && sk_IMPLEMENTATION_push(alg->impls, impl))
366         ret = 1;
367     ossl_property_unlock(store);
368     if (ret == 0)
369         impl_free(impl);
370     return ret;
371 
372 err:
373     ossl_property_unlock(store);
374     alg_cleanup(0, alg, NULL);
375     impl_free(impl);
376     return 0;
377 }
378 
ossl_method_store_remove(OSSL_METHOD_STORE * store,int nid,const void * method)379 int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
380                              const void *method)
381 {
382     ALGORITHM *alg = NULL;
383     int i;
384 
385     if (nid <= 0 || method == NULL || store == NULL)
386         return 0;
387 
388     if (!ossl_property_write_lock(store))
389         return 0;
390     ossl_method_cache_flush(store, nid);
391     alg = ossl_method_store_retrieve(store, nid);
392     if (alg == NULL) {
393         ossl_property_unlock(store);
394         return 0;
395     }
396 
397     /*
398      * A sorting find then a delete could be faster but these stacks should be
399      * relatively small, so we avoid the overhead.  Sorting could also surprise
400      * users when result orderings change (even though they are not guaranteed).
401      */
402     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
403         IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
404 
405         if (impl->method.method == method) {
406             impl_free(impl);
407             (void)sk_IMPLEMENTATION_delete(alg->impls, i);
408             ossl_property_unlock(store);
409             return 1;
410         }
411     }
412     ossl_property_unlock(store);
413     return 0;
414 }
415 
416 struct alg_cleanup_by_provider_data_st {
417     OSSL_METHOD_STORE *store;
418     const OSSL_PROVIDER *prov;
419 };
420 
421 static void
alg_cleanup_by_provider(ossl_uintmax_t idx,ALGORITHM * alg,void * arg)422 alg_cleanup_by_provider(ossl_uintmax_t idx, ALGORITHM *alg, void *arg)
423 {
424     struct alg_cleanup_by_provider_data_st *data = arg;
425     int i, count;
426 
427     /*
428      * We walk the stack backwards, to avoid having to deal with stack shifts
429      * caused by deletion
430      */
431     for (count = 0, i = sk_IMPLEMENTATION_num(alg->impls); i-- > 0;) {
432         IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
433 
434         if (impl->provider == data->prov) {
435             impl_free(impl);
436             (void)sk_IMPLEMENTATION_delete(alg->impls, i);
437             count++;
438         }
439     }
440 
441     /*
442      * If we removed any implementation, we also clear the whole associated
443      * cache, 'cause that's the sensible thing to do.
444      * There's no point flushing the cache entries where we didn't remove
445      * any implementation, though.
446      */
447     if (count > 0)
448         ossl_method_cache_flush_alg(data->store, alg);
449 }
450 
ossl_method_store_remove_all_provided(OSSL_METHOD_STORE * store,const OSSL_PROVIDER * prov)451 int ossl_method_store_remove_all_provided(OSSL_METHOD_STORE *store,
452                                           const OSSL_PROVIDER *prov)
453 {
454     struct alg_cleanup_by_provider_data_st data;
455 
456     if (!ossl_property_write_lock(store))
457         return 0;
458     data.prov = prov;
459     data.store = store;
460     ossl_sa_ALGORITHM_doall_arg(store->algs, &alg_cleanup_by_provider, &data);
461     ossl_property_unlock(store);
462     return 1;
463 }
464 
alg_do_one(ALGORITHM * alg,IMPLEMENTATION * impl,void (* fn)(int id,void * method,void * fnarg),void * fnarg)465 static void alg_do_one(ALGORITHM *alg, IMPLEMENTATION *impl,
466                        void (*fn)(int id, void *method, void *fnarg),
467                        void *fnarg)
468 {
469     fn(alg->nid, impl->method.method, fnarg);
470 }
471 
472 struct alg_do_each_data_st {
473     void (*fn)(int id, void *method, void *fnarg);
474     void *fnarg;
475 };
476 
alg_do_each(ossl_uintmax_t idx,ALGORITHM * alg,void * arg)477 static void alg_do_each(ossl_uintmax_t idx, ALGORITHM *alg, void *arg)
478 {
479     struct alg_do_each_data_st *data = arg;
480     int i, end = sk_IMPLEMENTATION_num(alg->impls);
481 
482     for (i = 0; i < end; i++) {
483         IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
484 
485         alg_do_one(alg, impl, data->fn, data->fnarg);
486     }
487 }
488 
ossl_method_store_do_all(OSSL_METHOD_STORE * store,void (* fn)(int id,void * method,void * fnarg),void * fnarg)489 void ossl_method_store_do_all(OSSL_METHOD_STORE *store,
490                               void (*fn)(int id, void *method, void *fnarg),
491                               void *fnarg)
492 {
493     struct alg_do_each_data_st data;
494 
495     data.fn = fn;
496     data.fnarg = fnarg;
497     if (store != NULL)
498         ossl_sa_ALGORITHM_doall_arg(store->algs, alg_do_each, &data);
499 }
500 
ossl_method_store_fetch(OSSL_METHOD_STORE * store,int nid,const char * prop_query,const OSSL_PROVIDER ** prov_rw,void ** method)501 int ossl_method_store_fetch(OSSL_METHOD_STORE *store,
502                             int nid, const char *prop_query,
503                             const OSSL_PROVIDER **prov_rw, void **method)
504 {
505     OSSL_PROPERTY_LIST **plp;
506     ALGORITHM *alg;
507     IMPLEMENTATION *impl, *best_impl = NULL;
508     OSSL_PROPERTY_LIST *pq = NULL, *p2 = NULL;
509     const OSSL_PROVIDER *prov = prov_rw != NULL ? *prov_rw : NULL;
510     int ret = 0;
511     int j, best = -1, score, optional;
512 
513     if (nid <= 0 || method == NULL || store == NULL)
514         return 0;
515 
516 #ifndef FIPS_MODULE
517     if (ossl_lib_ctx_is_default(store->ctx)
518             && !OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CONFIG, NULL))
519         return 0;
520 #endif
521 
522     /* This only needs to be a read lock, because the query won't create anything */
523     if (!ossl_property_read_lock(store))
524         return 0;
525     alg = ossl_method_store_retrieve(store, nid);
526     if (alg == NULL) {
527         ossl_property_unlock(store);
528         return 0;
529     }
530 
531     if (prop_query != NULL)
532         p2 = pq = ossl_parse_query(store->ctx, prop_query, 0);
533     plp = ossl_ctx_global_properties(store->ctx, 0);
534     if (plp != NULL && *plp != NULL) {
535         if (pq == NULL) {
536             pq = *plp;
537         } else {
538             p2 = ossl_property_merge(pq, *plp);
539             ossl_property_free(pq);
540             if (p2 == NULL)
541                 goto fin;
542             pq = p2;
543         }
544     }
545 
546     if (pq == NULL) {
547         for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
548             if ((impl = sk_IMPLEMENTATION_value(alg->impls, j)) != NULL
549                 && (prov == NULL || impl->provider == prov)) {
550                 best_impl = impl;
551                 ret = 1;
552                 break;
553             }
554         }
555         goto fin;
556     }
557     optional = ossl_property_has_optional(pq);
558     for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
559         if ((impl = sk_IMPLEMENTATION_value(alg->impls, j)) != NULL
560             && (prov == NULL || impl->provider == prov)) {
561             score = ossl_property_match_count(pq, impl->properties);
562             if (score > best) {
563                 best_impl = impl;
564                 best = score;
565                 ret = 1;
566                 if (!optional)
567                     goto fin;
568             }
569         }
570     }
571 fin:
572     if (ret && ossl_method_up_ref(&best_impl->method)) {
573         *method = best_impl->method.method;
574         if (prov_rw != NULL)
575             *prov_rw = best_impl->provider;
576     } else {
577         ret = 0;
578     }
579     ossl_property_unlock(store);
580     ossl_property_free(p2);
581     return ret;
582 }
583 
ossl_method_cache_flush_alg(OSSL_METHOD_STORE * store,ALGORITHM * alg)584 static void ossl_method_cache_flush_alg(OSSL_METHOD_STORE *store,
585                                         ALGORITHM *alg)
586 {
587     store->cache_nelem -= lh_QUERY_num_items(alg->cache);
588     impl_cache_flush_alg(0, alg);
589 }
590 
ossl_method_cache_flush(OSSL_METHOD_STORE * store,int nid)591 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
592 {
593     ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
594 
595     if (alg != NULL)
596         ossl_method_cache_flush_alg(store, alg);
597 }
598 
ossl_method_store_cache_flush_all(OSSL_METHOD_STORE * store)599 int ossl_method_store_cache_flush_all(OSSL_METHOD_STORE *store)
600 {
601     if (!ossl_property_write_lock(store))
602         return 0;
603     ossl_sa_ALGORITHM_doall(store->algs, &impl_cache_flush_alg);
604     store->cache_nelem = 0;
605     ossl_property_unlock(store);
606     return 1;
607 }
608 
609 IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
610 
611 /*
612  * Flush an element from the query cache (perhaps).
613  *
614  * In order to avoid taking a write lock or using atomic operations
615  * to keep accurate least recently used (LRU) or least frequently used
616  * (LFU) information, the procedure used here is to stochastically
617  * flush approximately half the cache.
618  *
619  * This procedure isn't ideal, LRU or LFU would be better.  However,
620  * in normal operation, reaching a full cache would be unexpected.
621  * It means that no steady state of algorithm queries has been reached.
622  * That is, it is most likely an attack of some form.  A suboptimal clearance
623  * strategy that doesn't degrade performance of the normal case is
624  * preferable to a more refined approach that imposes a performance
625  * impact.
626  */
impl_cache_flush_cache(QUERY * c,IMPL_CACHE_FLUSH * state)627 static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
628 {
629     uint32_t n;
630 
631     /*
632      * Implement the 32 bit xorshift as suggested by George Marsaglia in:
633      *      https://doi.org/10.18637/jss.v008.i14
634      *
635      * This is a very fast PRNG so there is no need to extract bits one at a
636      * time and use the entire value each time.
637      */
638     n = state->seed;
639     n ^= n << 13;
640     n ^= n >> 17;
641     n ^= n << 5;
642     state->seed = n;
643 
644     if ((n & 1) != 0)
645         impl_cache_free(lh_QUERY_delete(state->cache, c));
646     else
647         state->nelem++;
648 }
649 
impl_cache_flush_one_alg(ossl_uintmax_t idx,ALGORITHM * alg,void * v)650 static void impl_cache_flush_one_alg(ossl_uintmax_t idx, ALGORITHM *alg,
651                                      void *v)
652 {
653     IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
654 
655     state->cache = alg->cache;
656     lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
657                                     state);
658 }
659 
ossl_method_cache_flush_some(OSSL_METHOD_STORE * store)660 static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
661 {
662     IMPL_CACHE_FLUSH state;
663     static TSAN_QUALIFIER uint32_t global_seed = 1;
664 
665     state.nelem = 0;
666     state.using_global_seed = 0;
667     if ((state.seed = OPENSSL_rdtsc()) == 0) {
668         /* If there is no timer available, seed another way */
669         state.using_global_seed = 1;
670         state.seed = tsan_load(&global_seed);
671     }
672     store->cache_need_flush = 0;
673     ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
674     store->cache_nelem = state.nelem;
675     /* Without a timer, update the global seed */
676     if (state.using_global_seed)
677         tsan_store(&global_seed, state.seed);
678 }
679 
ossl_method_store_cache_get(OSSL_METHOD_STORE * store,OSSL_PROVIDER * prov,int nid,const char * prop_query,void ** method)680 int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, OSSL_PROVIDER *prov,
681                                 int nid, const char *prop_query, void **method)
682 {
683     ALGORITHM *alg;
684     QUERY elem, *r;
685     int res = 0;
686 
687     if (nid <= 0 || store == NULL || prop_query == NULL)
688         return 0;
689 
690     if (!ossl_property_read_lock(store))
691         return 0;
692     alg = ossl_method_store_retrieve(store, nid);
693     if (alg == NULL)
694         goto err;
695 
696     elem.query = prop_query;
697     elem.provider = prov;
698     r = lh_QUERY_retrieve(alg->cache, &elem);
699     if (r == NULL)
700         goto err;
701     if (ossl_method_up_ref(&r->method)) {
702         *method = r->method.method;
703         res = 1;
704     }
705 err:
706     ossl_property_unlock(store);
707     return res;
708 }
709 
ossl_method_store_cache_set(OSSL_METHOD_STORE * store,OSSL_PROVIDER * prov,int nid,const char * prop_query,void * method,int (* method_up_ref)(void *),void (* method_destruct)(void *))710 int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, OSSL_PROVIDER *prov,
711                                 int nid, const char *prop_query, void *method,
712                                 int (*method_up_ref)(void *),
713                                 void (*method_destruct)(void *))
714 {
715     QUERY elem, *old, *p = NULL;
716     ALGORITHM *alg;
717     size_t len;
718     int res = 1;
719 
720     if (nid <= 0 || store == NULL || prop_query == NULL)
721         return 0;
722 
723     if (!ossl_assert(prov != NULL))
724         return 0;
725 
726     if (!ossl_property_write_lock(store))
727         return 0;
728     if (store->cache_need_flush)
729         ossl_method_cache_flush_some(store);
730     alg = ossl_method_store_retrieve(store, nid);
731     if (alg == NULL)
732         goto err;
733 
734     if (method == NULL) {
735         elem.query = prop_query;
736         elem.provider = prov;
737         if ((old = lh_QUERY_delete(alg->cache, &elem)) != NULL) {
738             impl_cache_free(old);
739             store->cache_nelem--;
740         }
741         goto end;
742     }
743     p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
744     if (p != NULL) {
745         p->query = p->body;
746         p->provider = prov;
747         p->method.method = method;
748         p->method.up_ref = method_up_ref;
749         p->method.free = method_destruct;
750         if (!ossl_method_up_ref(&p->method))
751             goto err;
752         memcpy((char *)p->query, prop_query, len + 1);
753         if ((old = lh_QUERY_insert(alg->cache, p)) != NULL) {
754             impl_cache_free(old);
755             goto end;
756         }
757         if (!lh_QUERY_error(alg->cache)) {
758             if (++store->cache_nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
759                 store->cache_need_flush = 1;
760             goto end;
761         }
762         ossl_method_free(&p->method);
763     }
764 err:
765     res = 0;
766     OPENSSL_free(p);
767 end:
768     ossl_property_unlock(store);
769     return res;
770 }
771