2 * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
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
14 #include <openssl/crypto.h>
15 #include "internal/property.h"
16 #include "internal/ctype.h"
17 #include <openssl/lhash.h>
18 #include <openssl/rand.h>
19 #include "internal/thread_once.h"
20 #include "internal/lhash.h"
21 #include "internal/sparse_array.h"
22 #include "property_lcl.h"
24 /* The number of elements in the query cache before we initiate a flush */
25 #define IMPL_CACHE_FLUSH_THRESHOLD 500
28 OSSL_PROPERTY_LIST *properties;
30 void (*implementation_destruct)(void *);
33 DEFINE_STACK_OF(IMPLEMENTATION)
41 DEFINE_LHASH_OF(QUERY);
45 STACK_OF(IMPLEMENTATION) *impls;
46 LHASH_OF(QUERY) *cache;
49 struct ossl_method_store_st {
51 SPARSE_ARRAY_OF(ALGORITHM) *algs;
52 OSSL_PROPERTY_LIST *global_properties;
55 unsigned char rand_bits[(IMPL_CACHE_FLUSH_THRESHOLD + 7) / 8];
60 OSSL_METHOD_STORE *store;
61 LHASH_OF(QUERY) *cache;
65 DEFINE_SPARSE_ARRAY_OF(ALGORITHM);
67 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
68 static void ossl_method_cache_flush_all(OSSL_METHOD_STORE *c);
70 int ossl_property_read_lock(OSSL_METHOD_STORE *p)
72 return p != NULL ? CRYPTO_THREAD_read_lock(p->lock) : 0;
75 int ossl_property_write_lock(OSSL_METHOD_STORE *p)
77 return p != NULL ? CRYPTO_THREAD_write_lock(p->lock) : 0;
80 int ossl_property_unlock(OSSL_METHOD_STORE *p)
82 return p != 0 ? CRYPTO_THREAD_unlock(p->lock) : 0;
85 int ossl_method_store_init(void)
87 if (ossl_property_string_init()
88 && ossl_prop_defn_init()
89 && ossl_property_parse_init())
92 ossl_method_store_cleanup();
96 void ossl_method_store_cleanup(void)
98 ossl_property_string_cleanup();
99 ossl_prop_defn_cleanup();
102 static CRYPTO_ONCE method_store_init_flag = CRYPTO_ONCE_STATIC_INIT;
103 DEFINE_RUN_ONCE_STATIC(do_method_store_init)
105 return OPENSSL_init_crypto(0, NULL)
106 && ossl_method_store_init()
107 && OPENSSL_atexit(&ossl_method_store_cleanup);
110 static unsigned long query_hash(const QUERY *a)
112 return OPENSSL_LH_strhash(a->query);
115 static int query_cmp(const QUERY *a, const QUERY *b)
117 return strcmp(a->query, b->query);
120 static void impl_free(IMPLEMENTATION *impl)
123 if (impl->implementation_destruct)
124 impl->implementation_destruct(impl->implementation);
129 static void impl_cache_free(QUERY *elem)
134 static void alg_cleanup(size_t idx, ALGORITHM *a)
137 sk_IMPLEMENTATION_pop_free(a->impls, &impl_free);
138 lh_QUERY_doall(a->cache, &impl_cache_free);
139 lh_QUERY_free(a->cache);
144 OSSL_METHOD_STORE *ossl_method_store_new(void)
146 OSSL_METHOD_STORE *res = OPENSSL_zalloc(sizeof(*res));
148 if (!RUN_ONCE(&method_store_init_flag, do_method_store_init))
152 if ((res->algs = ossl_sa_ALGORITHM_new()) == NULL) {
156 if ((res->lock = CRYPTO_THREAD_lock_new()) == NULL) {
157 OPENSSL_free(res->algs);
165 void ossl_method_store_free(OSSL_METHOD_STORE *store)
168 ossl_sa_ALGORITHM_doall(store->algs, &alg_cleanup);
169 ossl_sa_ALGORITHM_free(store->algs);
170 ossl_property_free(store->global_properties);
171 CRYPTO_THREAD_lock_free(store->lock);
176 static ALGORITHM *ossl_method_store_retrieve(OSSL_METHOD_STORE *store, int nid)
178 return ossl_sa_ALGORITHM_get(store->algs, nid);
181 static int ossl_method_store_insert(OSSL_METHOD_STORE *store, ALGORITHM *alg)
183 return ossl_sa_ALGORITHM_set(store->algs, alg->nid, alg);
186 int ossl_method_store_add(OSSL_METHOD_STORE *store,
187 int nid, const char *properties,
188 void *implementation,
189 void (*implementation_destruct)(void *))
191 ALGORITHM *alg = NULL;
192 IMPLEMENTATION *impl;
195 if (nid <= 0 || implementation == NULL || store == NULL)
197 if (properties == NULL)
200 /* Create new entry */
201 impl = OPENSSL_malloc(sizeof(*impl));
204 impl->implementation = implementation;
205 impl->implementation_destruct = implementation_destruct;
208 * Insert into the hash table if required.
210 * A write lock is used unconditionally because we wend our way down to the
211 * property string code which isn't locking friendly.
213 ossl_property_write_lock(store);
214 ossl_method_cache_flush(store, nid);
215 if ((impl->properties = ossl_prop_defn_get(properties)) == NULL) {
216 if ((impl->properties = ossl_parse_property(properties)) == NULL)
218 ossl_prop_defn_set(properties, impl->properties);
221 alg = ossl_method_store_retrieve(store, nid);
223 if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
224 || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
225 || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
228 if (!ossl_method_store_insert(store, alg))
232 /* Push onto stack */
233 if (sk_IMPLEMENTATION_push(alg->impls, impl))
235 ossl_property_unlock(store);
241 ossl_property_unlock(store);
247 int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
248 const void *implementation)
250 ALGORITHM *alg = NULL;
253 if (nid <= 0 || implementation == NULL || store == NULL)
256 ossl_property_write_lock(store);
257 ossl_method_cache_flush(store, nid);
258 alg = ossl_method_store_retrieve(store, nid);
260 ossl_property_unlock(store);
265 * A sorting find then a delete could be faster but these stacks should be
266 * relatively small, so we avoid the overhead. Sorting could also surprise
267 * users when result orderings change (even though they are not guaranteed).
269 for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
270 IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
272 if (impl->implementation == implementation) {
273 sk_IMPLEMENTATION_delete(alg->impls, i);
274 ossl_property_unlock(store);
279 ossl_property_unlock(store);
283 int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
284 const char *prop_query, void **result)
287 IMPLEMENTATION *impl;
288 OSSL_PROPERTY_LIST *pq = NULL, *p2;
292 if (nid <= 0 || result == NULL || store == NULL)
296 * This only needs to be a read lock, because queries never create property
297 * names or value and thus don't modify any of the property string layer.
299 ossl_property_read_lock(store);
300 alg = ossl_method_store_retrieve(store, nid);
302 ossl_property_unlock(store);
306 if (prop_query == NULL) {
307 if ((impl = sk_IMPLEMENTATION_value(alg->impls, 0)) != NULL) {
308 *result = impl->implementation;
313 pq = ossl_parse_query(prop_query);
316 if (store->global_properties != NULL) {
317 p2 = ossl_property_merge(pq, store->global_properties);
320 ossl_property_free(pq);
323 for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
324 impl = sk_IMPLEMENTATION_value(alg->impls, j);
326 if (ossl_property_match(pq, impl->properties)) {
327 *result = impl->implementation;
333 ossl_property_unlock(store);
334 ossl_property_free(pq);
338 int ossl_method_store_set_global_properties(OSSL_METHOD_STORE *store,
339 const char *prop_query) {
345 ossl_property_write_lock(store);
346 ossl_method_cache_flush_all(store);
347 if (prop_query == NULL) {
348 ossl_property_free(store->global_properties);
349 store->global_properties = NULL;
350 ossl_property_unlock(store);
353 store->global_properties = ossl_parse_query(prop_query);
354 ret = store->global_properties != NULL;
355 ossl_property_unlock(store);
359 static void impl_cache_flush_alg(size_t idx, ALGORITHM *alg)
361 lh_QUERY_doall(alg->cache, &impl_cache_free);
362 lh_QUERY_flush(alg->cache);
365 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
367 ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
370 store->nelem -= lh_QUERY_num_items(alg->cache);
371 impl_cache_flush_alg(0, alg);
375 static void ossl_method_cache_flush_all(OSSL_METHOD_STORE *store)
377 ossl_sa_ALGORITHM_doall(store->algs, &impl_cache_flush_alg);
381 IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
384 * Flush an element from the query cache (perhaps).
386 * In order to avoid taking a write lock to keep accurate LRU information or
387 * using atomic operations to approximate similar, the procedure used here
388 * is to stochastically flush approximately half the cache. Since generating
389 * random numbers is relatively expensive, we produce them in blocks and
390 * consume them as we go, saving generated bits between generations of flushes.
392 * This procedure isn't ideal, LRU would be better. However, in normal
393 * operation, reaching a full cache would be quite unexpected. It means
394 * that no steady state of algorithm queries has been reached. I.e. it is most
395 * likely an attack of some form. A suboptimal clearance strategy that doesn't
396 * degrade performance of the normal case is preferable to a more refined
397 * approach that imposes a performance impact.
399 static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
401 OSSL_METHOD_STORE *store = state->store;
404 if (store->nbits == 0) {
405 if (!RAND_bytes(store->rand_bits, sizeof(store->rand_bits)))
407 store->nbits = sizeof(store->rand_bits) * 8;
410 if ((store->rand_bits[n >> 3] & (1 << (n & 7))) != 0)
411 OPENSSL_free(lh_QUERY_delete(state->cache, c));
416 static void impl_cache_flush_one_alg(size_t idx, ALGORITHM *alg, void *v)
418 IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
420 state->cache = alg->cache;
421 lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
425 static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
427 IMPL_CACHE_FLUSH state;
431 ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
432 store->need_flush = 0;
433 store->nelem = state.nelem;
436 int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
437 const char *prop_query, void **result)
442 if (nid <= 0 || store == NULL)
445 ossl_property_read_lock(store);
446 alg = ossl_method_store_retrieve(store, nid);
448 ossl_property_unlock(store);
452 elem.query = prop_query;
453 r = lh_QUERY_retrieve(alg->cache, &elem);
455 ossl_property_unlock(store);
459 ossl_property_unlock(store);
463 int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
464 const char *prop_query, void *result)
466 QUERY elem, *old, *p = NULL;
470 if (nid <= 0 || store == NULL)
472 if (prop_query == NULL)
475 ossl_property_write_lock(store);
476 if (store->need_flush)
477 ossl_method_cache_flush_some(store);
478 alg = ossl_method_store_retrieve(store, nid);
480 ossl_property_unlock(store);
484 if (result == NULL) {
485 elem.query = prop_query;
486 lh_QUERY_delete(alg->cache, &elem);
487 ossl_property_unlock(store);
490 p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
494 memcpy((char *)p->query, prop_query, len + 1);
495 if ((old = lh_QUERY_insert(alg->cache, p)) != NULL)
497 if (old != NULL || !lh_QUERY_error(alg->cache)) {
499 if (store->nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
500 store->need_flush = 1;
501 ossl_property_unlock(store);
505 ossl_property_unlock(store);