property: Move global default properties to the library context.
[openssl.git] / crypto / property / property.c
1 /*
2  * Copyright 2019-2020 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/property.h"
16 #include "crypto/ctype.h"
17 #include <openssl/lhash.h>
18 #include <openssl/rand.h>
19 #include "internal/thread_once.h"
20 #include "crypto/lhash.h"
21 #include "crypto/sparse_array.h"
22 #include "property_local.h"
23
24 /*
25  * The number of elements in the query cache before we initiate a flush.
26  * If reducing this, also ensure the stochastic test in test/property_test.c
27  * isn't likely to fail.
28  */
29 #define IMPL_CACHE_FLUSH_THRESHOLD  500
30
31 typedef struct {
32     void *method;
33     int (*up_ref)(void *);
34     void (*free)(void *);
35 } METHOD;
36
37 typedef struct {
38     const OSSL_PROVIDER *provider;
39     OSSL_PROPERTY_LIST *properties;
40     METHOD method;
41 } IMPLEMENTATION;
42
43 DEFINE_STACK_OF(IMPLEMENTATION)
44
45 typedef struct {
46     const char *query;
47     METHOD method;
48     char body[1];
49 } QUERY;
50
51 DEFINE_LHASH_OF(QUERY);
52
53 typedef struct {
54     int nid;
55     STACK_OF(IMPLEMENTATION) *impls;
56     LHASH_OF(QUERY) *cache;
57 } ALGORITHM;
58
59 struct ossl_method_store_st {
60     OPENSSL_CTX *ctx;
61     size_t nelem;
62     SPARSE_ARRAY_OF(ALGORITHM) *algs;
63     int need_flush;
64     CRYPTO_RWLOCK *lock;
65 };
66
67 typedef struct {
68     LHASH_OF(QUERY) *cache;
69     size_t nelem;
70     uint32_t seed;
71 } IMPL_CACHE_FLUSH;
72
73 DEFINE_SPARSE_ARRAY_OF(ALGORITHM);
74
75 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
76
77 /* Global properties are stored per library context */
78 static void ossl_ctx_global_properties_free(void *vstore)
79 {
80     OSSL_PROPERTY_LIST **plp = vstore;
81
82     if (plp != NULL) {
83         ossl_property_free(*plp);
84         OPENSSL_free(plp);
85     }
86 }
87
88 static void *ossl_ctx_global_properties_new(OPENSSL_CTX *ctx)
89 {
90     return OPENSSL_zalloc(sizeof(OSSL_PROPERTY_LIST **));
91 }
92
93
94 static const OPENSSL_CTX_METHOD ossl_ctx_global_properties_method = {
95     ossl_ctx_global_properties_new,
96     ossl_ctx_global_properties_free,
97 };
98
99 OSSL_PROPERTY_LIST **ossl_ctx_global_properties(OPENSSL_CTX *libctx)
100 {
101     return openssl_ctx_get_data(libctx, OPENSSL_CTX_GLOBAL_PROPERTIES,
102                                 &ossl_ctx_global_properties_method);
103 }
104
105 static int ossl_method_up_ref(METHOD *method)
106 {
107     return (*method->up_ref)(method->method);
108 }
109
110 static void ossl_method_free(METHOD *method)
111 {
112     (*method->free)(method->method);
113 }
114
115 int ossl_property_read_lock(OSSL_METHOD_STORE *p)
116 {
117     return p != NULL ? CRYPTO_THREAD_read_lock(p->lock) : 0;
118 }
119
120 int ossl_property_write_lock(OSSL_METHOD_STORE *p)
121 {
122     return p != NULL ? CRYPTO_THREAD_write_lock(p->lock) : 0;
123 }
124
125 int ossl_property_unlock(OSSL_METHOD_STORE *p)
126 {
127     return p != 0 ? CRYPTO_THREAD_unlock(p->lock) : 0;
128 }
129
130 static unsigned long query_hash(const QUERY *a)
131 {
132     return OPENSSL_LH_strhash(a->query);
133 }
134
135 static int query_cmp(const QUERY *a, const QUERY *b)
136 {
137     return strcmp(a->query, b->query);
138 }
139
140 static void impl_free(IMPLEMENTATION *impl)
141 {
142     if (impl != NULL) {
143         ossl_method_free(&impl->method);
144         OPENSSL_free(impl);
145     }
146 }
147
148 static void impl_cache_free(QUERY *elem)
149 {
150     if (elem != NULL) {
151         ossl_method_free(&elem->method);
152         OPENSSL_free(elem);
153     }
154 }
155
156 static void alg_cleanup(ossl_uintmax_t idx, ALGORITHM *a)
157 {
158     if (a != NULL) {
159         sk_IMPLEMENTATION_pop_free(a->impls, &impl_free);
160         lh_QUERY_doall(a->cache, &impl_cache_free);
161         lh_QUERY_free(a->cache);
162         OPENSSL_free(a);
163     }
164 }
165
166 /*
167  * The OPENSSL_CTX param here allows access to underlying property data needed
168  * for computation
169  */
170 OSSL_METHOD_STORE *ossl_method_store_new(OPENSSL_CTX *ctx)
171 {
172     OSSL_METHOD_STORE *res;
173
174     res = OPENSSL_zalloc(sizeof(*res));
175     if (res != NULL) {
176         res->ctx = ctx;
177         if ((res->algs = ossl_sa_ALGORITHM_new()) == NULL) {
178             OPENSSL_free(res);
179             return NULL;
180         }
181         if ((res->lock = CRYPTO_THREAD_lock_new()) == NULL) {
182             ossl_sa_ALGORITHM_free(res->algs);
183             OPENSSL_free(res);
184             return NULL;
185         }
186     }
187     return res;
188 }
189
190 void ossl_method_store_free(OSSL_METHOD_STORE *store)
191 {
192     if (store != NULL) {
193         ossl_sa_ALGORITHM_doall(store->algs, &alg_cleanup);
194         ossl_sa_ALGORITHM_free(store->algs);
195         CRYPTO_THREAD_lock_free(store->lock);
196         OPENSSL_free(store);
197     }
198 }
199
200 static ALGORITHM *ossl_method_store_retrieve(OSSL_METHOD_STORE *store, int nid)
201 {
202     return ossl_sa_ALGORITHM_get(store->algs, nid);
203 }
204
205 static int ossl_method_store_insert(OSSL_METHOD_STORE *store, ALGORITHM *alg)
206 {
207         return ossl_sa_ALGORITHM_set(store->algs, alg->nid, alg);
208 }
209
210 int ossl_method_store_add(OSSL_METHOD_STORE *store, const OSSL_PROVIDER *prov,
211                           int nid, const char *properties, void *method,
212                           int (*method_up_ref)(void *),
213                           void (*method_destruct)(void *))
214 {
215     ALGORITHM *alg = NULL;
216     IMPLEMENTATION *impl;
217     int ret = 0;
218     int i;
219
220     if (nid <= 0 || method == NULL || store == NULL)
221         return 0;
222     if (properties == NULL)
223         properties = "";
224
225     /* Create new entry */
226     impl = OPENSSL_malloc(sizeof(*impl));
227     if (impl == NULL)
228         return 0;
229     impl->method.method = method;
230     impl->method.up_ref = method_up_ref;
231     impl->method.free = method_destruct;
232     if (!ossl_method_up_ref(&impl->method)) {
233         OPENSSL_free(impl);
234         return 0;
235     }
236     impl->provider = prov;
237
238     /*
239      * Insert into the hash table if required.
240      *
241      * A write lock is used unconditionally because we wend our way down to the
242      * property string code which isn't locking friendly.
243      */
244     ossl_property_write_lock(store);
245     ossl_method_cache_flush(store, nid);
246     if ((impl->properties = ossl_prop_defn_get(store->ctx, properties)) == NULL) {
247         impl->properties = ossl_parse_property(store->ctx, properties);
248         if (impl->properties == NULL)
249             goto err;
250         ossl_prop_defn_set(store->ctx, properties, impl->properties);
251     }
252
253     alg = ossl_method_store_retrieve(store, nid);
254     if (alg == NULL) {
255         if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
256                 || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
257                 || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
258             goto err;
259         alg->nid = nid;
260         if (!ossl_method_store_insert(store, alg))
261             goto err;
262     }
263
264     /* Push onto stack if there isn't one there already */
265     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
266         const IMPLEMENTATION *tmpimpl = sk_IMPLEMENTATION_value(alg->impls, i);
267
268         if (tmpimpl->provider == impl->provider
269             && tmpimpl->properties == impl->properties)
270             break;
271     }
272     if (i == sk_IMPLEMENTATION_num(alg->impls)
273         && sk_IMPLEMENTATION_push(alg->impls, impl))
274         ret = 1;
275     ossl_property_unlock(store);
276     if (ret == 0)
277         impl_free(impl);
278     return ret;
279
280 err:
281     ossl_property_unlock(store);
282     alg_cleanup(0, alg);
283     impl_free(impl);
284     return 0;
285 }
286
287 int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
288                              const void *method)
289 {
290     ALGORITHM *alg = NULL;
291     int i;
292
293     if (nid <= 0 || method == NULL || store == NULL)
294         return 0;
295
296     ossl_property_write_lock(store);
297     ossl_method_cache_flush(store, nid);
298     alg = ossl_method_store_retrieve(store, nid);
299     if (alg == NULL) {
300         ossl_property_unlock(store);
301         return 0;
302     }
303
304     /*
305      * A sorting find then a delete could be faster but these stacks should be
306      * relatively small, so we avoid the overhead.  Sorting could also surprise
307      * users when result orderings change (even though they are not guaranteed).
308      */
309     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
310         IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
311
312         if (impl->method.method == method) {
313             impl_free(impl);
314             sk_IMPLEMENTATION_delete(alg->impls, i);
315             ossl_property_unlock(store);
316             return 1;
317         }
318     }
319     ossl_property_unlock(store);
320     return 0;
321 }
322
323 int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
324                             const char *prop_query,
325                             void **method)
326 {
327     OSSL_PROPERTY_LIST **plp = ossl_ctx_global_properties(store->ctx);
328     ALGORITHM *alg;
329     IMPLEMENTATION *impl;
330     OSSL_PROPERTY_LIST *pq = NULL, *p2 = NULL;
331     METHOD *best_method = NULL;
332     int ret = 0;
333     int j, best = -1, score, optional;
334
335 #ifndef FIPS_MODULE
336     OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CONFIG, NULL);
337 #endif
338
339     if (nid <= 0 || method == NULL || store == NULL)
340         return 0;
341
342     /*
343      * This only needs to be a read lock, because queries never create property
344      * names or value and thus don't modify any of the property string layer.
345      */
346     ossl_property_read_lock(store);
347     alg = ossl_method_store_retrieve(store, nid);
348     if (alg == NULL) {
349         ossl_property_unlock(store);
350         return 0;
351     }
352
353     if (prop_query != NULL) {
354         p2 = pq = ossl_parse_query(store->ctx, prop_query);
355     }
356     if (plp != NULL && *plp != NULL) {
357         if (pq == NULL) {
358             pq = *plp;
359         } else {
360             p2 = ossl_property_merge(pq, *plp);
361             if (p2 == NULL)
362                 goto fin;
363             ossl_property_free(pq);
364             pq = p2;
365         }
366     }
367
368     if (pq == NULL) {
369         if ((impl = sk_IMPLEMENTATION_value(alg->impls, 0)) != NULL) {
370             best_method = &impl->method;
371             ret = 1;
372         }
373         goto fin;
374     }
375     optional = ossl_property_has_optional(pq);
376     for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
377         impl = sk_IMPLEMENTATION_value(alg->impls, j);
378         score = ossl_property_match_count(pq, impl->properties);
379         if (score > best) {
380             best_method = &impl->method;
381             best = score;
382             ret = 1;
383             if (!optional)
384                 goto fin;
385         }
386     }
387 fin:
388     if (ret && ossl_method_up_ref(best_method))
389         *method = best_method->method;
390     else
391         ret = 0;
392     ossl_property_unlock(store);
393     ossl_property_free(p2);
394     return ret;
395 }
396
397 static void impl_cache_flush_alg(ossl_uintmax_t idx, ALGORITHM *alg)
398 {
399     lh_QUERY_doall(alg->cache, &impl_cache_free);
400     lh_QUERY_flush(alg->cache);
401 }
402
403 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
404 {
405     ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
406
407     if (alg != NULL) {
408         store->nelem -= lh_QUERY_num_items(alg->cache);
409         impl_cache_flush_alg(0, alg);
410     }
411 }
412
413 void ossl_method_store_flush_cache(OSSL_METHOD_STORE *store)
414 {
415     ossl_property_write_lock(store);
416     ossl_sa_ALGORITHM_doall(store->algs, &impl_cache_flush_alg);
417     store->nelem = 0;
418     ossl_property_unlock(store);
419 }
420
421 IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
422
423 /*
424  * Flush an element from the query cache (perhaps).
425  *
426  * In order to avoid taking a write lock or using atomic operations
427  * to keep accurate least recently used (LRU) or least frequently used
428  * (LFU) information, the procedure used here is to stochastically
429  * flush approximately half the cache.
430  *
431  * This procedure isn't ideal, LRU or LFU would be better.  However,
432  * in normal operation, reaching a full cache would be unexpected.
433  * It means that no steady state of algorithm queries has been reached.
434  * That is, it is most likely an attack of some form.  A suboptimal clearance
435  * strategy that doesn't degrade performance of the normal case is
436  * preferable to a more refined approach that imposes a performance
437  * impact.
438  */
439 static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
440 {
441     uint32_t n;
442
443     /*
444      * Implement the 32 bit xorshift as suggested by George Marsaglia in:
445      *      https://doi.org/10.18637/jss.v008.i14
446      *
447      * This is a very fast PRNG so there is no need to extract bits one at a
448      * time and use the entire value each time.
449      */
450     n = state->seed;
451     n ^= n << 13;
452     n ^= n >> 17;
453     n ^= n << 5;
454     state->seed = n;
455
456     if ((n & 1) != 0)
457         impl_cache_free(lh_QUERY_delete(state->cache, c));
458     else
459         state->nelem++;
460 }
461
462 static void impl_cache_flush_one_alg(ossl_uintmax_t idx, ALGORITHM *alg,
463                                      void *v)
464 {
465     IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
466
467     state->cache = alg->cache;
468     lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
469                                     state);
470 }
471
472 static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
473 {
474     IMPL_CACHE_FLUSH state;
475
476     state.nelem = 0;
477     if ((state.seed = OPENSSL_rdtsc()) == 0)
478         state.seed = 1;
479     store->need_flush = 0;
480     ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
481     store->nelem = state.nelem;
482 }
483
484 int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
485                                 const char *prop_query, void **method)
486 {
487     ALGORITHM *alg;
488     QUERY elem, *r;
489     int res = 0;
490
491     if (nid <= 0 || store == NULL)
492         return 0;
493
494     ossl_property_read_lock(store);
495     alg = ossl_method_store_retrieve(store, nid);
496     if (alg == NULL)
497         goto err;
498
499     elem.query = prop_query != NULL ? prop_query : "";
500     r = lh_QUERY_retrieve(alg->cache, &elem);
501     if (r == NULL)
502         goto err;
503     if (ossl_method_up_ref(&r->method)) {
504         *method = r->method.method;
505         res = 1;
506     }
507 err:
508     ossl_property_unlock(store);
509     return res;
510 }
511
512 int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
513                                 const char *prop_query, void *method,
514                                 int (*method_up_ref)(void *),
515                                 void (*method_destruct)(void *))
516 {
517     QUERY elem, *old, *p = NULL;
518     ALGORITHM *alg;
519     size_t len;
520     int res = 1;
521
522     if (nid <= 0 || store == NULL)
523         return 0;
524     if (prop_query == NULL)
525         return 1;
526
527     ossl_property_write_lock(store);
528     if (store->need_flush)
529         ossl_method_cache_flush_some(store);
530     alg = ossl_method_store_retrieve(store, nid);
531     if (alg == NULL)
532         goto err;
533
534     if (method == NULL) {
535         elem.query = prop_query;
536         if ((old = lh_QUERY_delete(alg->cache, &elem)) != NULL) {
537             impl_cache_free(old);
538             store->nelem--;
539         }
540         goto end;
541     }
542     p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
543     if (p != NULL) {
544         p->query = p->body;
545         p->method.method = method;
546         p->method.up_ref = method_up_ref;
547         p->method.free = method_destruct;
548         if (!ossl_method_up_ref(&p->method))
549             goto err;
550         memcpy((char *)p->query, prop_query, len + 1);
551         if ((old = lh_QUERY_insert(alg->cache, p)) != NULL) {
552             impl_cache_free(old);
553             goto end;
554         }
555         if (!lh_QUERY_error(alg->cache)) {
556             if (++store->nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
557                 store->need_flush = 1;
558             goto end;
559         }
560         ossl_method_free(&p->method);
561     }
562 err:
563     res = 0;
564     OPENSSL_free(p);
565 end:
566     ossl_property_unlock(store);
567     return res;
568 }