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 (*method_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->method_destruct)
124 impl->method_destruct(impl->method);
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 *method, void (*method_destruct)(void *))
190 ALGORITHM *alg = NULL;
191 IMPLEMENTATION *impl;
194 if (nid <= 0 || method == NULL || store == NULL)
196 if (properties == NULL)
199 /* Create new entry */
200 impl = OPENSSL_malloc(sizeof(*impl));
203 impl->method = method;
204 impl->method_destruct = method_destruct;
207 * Insert into the hash table if required.
209 * A write lock is used unconditionally because we wend our way down to the
210 * property string code which isn't locking friendly.
212 ossl_property_write_lock(store);
213 ossl_method_cache_flush(store, nid);
214 if ((impl->properties = ossl_prop_defn_get(properties)) == NULL) {
215 if ((impl->properties = ossl_parse_property(properties)) == NULL)
217 ossl_prop_defn_set(properties, impl->properties);
220 alg = ossl_method_store_retrieve(store, nid);
222 if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
223 || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
224 || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
227 if (!ossl_method_store_insert(store, alg))
231 /* Push onto stack */
232 if (sk_IMPLEMENTATION_push(alg->impls, impl))
234 ossl_property_unlock(store);
240 ossl_property_unlock(store);
246 int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
249 ALGORITHM *alg = NULL;
252 if (nid <= 0 || method == NULL || store == NULL)
255 ossl_property_write_lock(store);
256 ossl_method_cache_flush(store, nid);
257 alg = ossl_method_store_retrieve(store, nid);
259 ossl_property_unlock(store);
264 * A sorting find then a delete could be faster but these stacks should be
265 * relatively small, so we avoid the overhead. Sorting could also surprise
266 * users when result orderings change (even though they are not guaranteed).
268 for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
269 IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
271 if (impl->method == method) {
272 sk_IMPLEMENTATION_delete(alg->impls, i);
273 ossl_property_unlock(store);
278 ossl_property_unlock(store);
282 int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
283 const char *prop_query, void **method)
286 IMPLEMENTATION *impl;
287 OSSL_PROPERTY_LIST *pq = NULL, *p2;
291 if (nid <= 0 || method == NULL || store == NULL)
295 * This only needs to be a read lock, because queries never create property
296 * names or value and thus don't modify any of the property string layer.
298 ossl_property_read_lock(store);
299 alg = ossl_method_store_retrieve(store, nid);
301 ossl_property_unlock(store);
305 if (prop_query == NULL) {
306 if ((impl = sk_IMPLEMENTATION_value(alg->impls, 0)) != NULL) {
307 *method = impl->method;
312 pq = ossl_parse_query(prop_query);
315 if (store->global_properties != NULL) {
316 p2 = ossl_property_merge(pq, store->global_properties);
319 ossl_property_free(pq);
322 for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
323 impl = sk_IMPLEMENTATION_value(alg->impls, j);
325 if (ossl_property_match(pq, impl->properties)) {
326 *method = impl->method;
332 ossl_property_unlock(store);
333 ossl_property_free(pq);
337 int ossl_method_store_set_global_properties(OSSL_METHOD_STORE *store,
338 const char *prop_query) {
344 ossl_property_write_lock(store);
345 ossl_method_cache_flush_all(store);
346 if (prop_query == NULL) {
347 ossl_property_free(store->global_properties);
348 store->global_properties = NULL;
349 ossl_property_unlock(store);
352 store->global_properties = ossl_parse_query(prop_query);
353 ret = store->global_properties != NULL;
354 ossl_property_unlock(store);
358 static void impl_cache_flush_alg(size_t idx, ALGORITHM *alg)
360 lh_QUERY_doall(alg->cache, &impl_cache_free);
361 lh_QUERY_flush(alg->cache);
364 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
366 ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
369 store->nelem -= lh_QUERY_num_items(alg->cache);
370 impl_cache_flush_alg(0, alg);
374 static void ossl_method_cache_flush_all(OSSL_METHOD_STORE *store)
376 ossl_sa_ALGORITHM_doall(store->algs, &impl_cache_flush_alg);
380 IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
383 * Flush an element from the query cache (perhaps).
385 * In order to avoid taking a write lock to keep accurate LRU information or
386 * using atomic operations to approximate similar, the procedure used here
387 * is to stochastically flush approximately half the cache. Since generating
388 * random numbers is relatively expensive, we produce them in blocks and
389 * consume them as we go, saving generated bits between generations of flushes.
391 * This procedure isn't ideal, LRU would be better. However, in normal
392 * operation, reaching a full cache would be quite unexpected. It means
393 * that no steady state of algorithm queries has been reached. I.e. it is most
394 * likely an attack of some form. A suboptimal clearance strategy that doesn't
395 * degrade performance of the normal case is preferable to a more refined
396 * approach that imposes a performance impact.
398 static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
400 OSSL_METHOD_STORE *store = state->store;
403 if (store->nbits == 0) {
404 if (!RAND_bytes(store->rand_bits, sizeof(store->rand_bits)))
406 store->nbits = sizeof(store->rand_bits) * 8;
409 if ((store->rand_bits[n >> 3] & (1 << (n & 7))) != 0)
410 OPENSSL_free(lh_QUERY_delete(state->cache, c));
415 static void impl_cache_flush_one_alg(size_t idx, ALGORITHM *alg, void *v)
417 IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
419 state->cache = alg->cache;
420 lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
424 static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
426 IMPL_CACHE_FLUSH state;
430 ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
431 store->need_flush = 0;
432 store->nelem = state.nelem;
435 int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
436 const char *prop_query, void **method)
441 if (nid <= 0 || store == NULL)
444 ossl_property_read_lock(store);
445 alg = ossl_method_store_retrieve(store, nid);
447 ossl_property_unlock(store);
451 elem.query = prop_query;
452 r = lh_QUERY_retrieve(alg->cache, &elem);
454 ossl_property_unlock(store);
458 ossl_property_unlock(store);
462 int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
463 const char *prop_query, void *method)
465 QUERY elem, *old, *p = NULL;
469 if (nid <= 0 || store == NULL)
471 if (prop_query == NULL)
474 ossl_property_write_lock(store);
475 if (store->need_flush)
476 ossl_method_cache_flush_some(store);
477 alg = ossl_method_store_retrieve(store, nid);
479 ossl_property_unlock(store);
483 if (method == NULL) {
484 elem.query = prop_query;
485 lh_QUERY_delete(alg->cache, &elem);
486 ossl_property_unlock(store);
489 p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
493 memcpy((char *)p->query, prop_query, len + 1);
494 if ((old = lh_QUERY_insert(alg->cache, p)) != NULL)
496 if (old != NULL || !lh_QUERY_error(alg->cache)) {
498 if (store->nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
499 store->need_flush = 1;
500 ossl_property_unlock(store);
504 ossl_property_unlock(store);