Optimise PKEY decoders

The most expensive part of using a PKEY decoder is the
OSSL_DECODER_CTX_new_for_pkey() call. This builds up all of the decoder
chains, which is a complex and time consuming operation. However, if no
new providers have been loaded/unloaded since the last time it was called
we can expect the same results for the same parameters. Note that this
operation takes place *before* we event parse the data for decoding so it
is not dependent on the parsed data at all.

We introduce a cache for OSSL_DECODER_CTX objects. If we have been called
with the same parameters then we just duplicate an existing
OSSL_DECODER_CTX. This should be significantly faster than creating a new
one every time.

Partially addressed the issue in #15199

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/21426)

9 files changed, 479 insertions, 34 deletions

diff --git a/crypto/context.c b/crypto/context.c
index b097b58cd5..f84a00566c 100644
--- a/crypto/context.c
+++ b/crypto/context.c
@@ -14,6 +14,7 @@
 #include "internal/core.h"
 #include "internal/bio.h"
 #include "internal/provider.h"
+#include "internal/decoder.h"
 #include "crypto/context.h"
 
 struct ossl_lib_ctx_st {
@@ -33,6 +34,7 @@ struct ossl_lib_ctx_st {
     void *bio_core;
     void *child_provider;
     OSSL_METHOD_STORE *decoder_store;
+    void *decoder_cache;
     OSSL_METHOD_STORE *encoder_store;
     OSSL_METHOD_STORE *store_loader_store;
     void *self_test_cb;
@@ -110,10 +112,16 @@ static int context_init(OSSL_LIB_CTX *ctx)
         goto err;
 
 #ifndef FIPS_MODULE
-    /* P2. We want decoder_store to be cleaned up before the provider store */
+    /*
+     * P2. We want decoder_store/decoder_cache to be cleaned up before the
+     * provider store
+     */
     ctx->decoder_store = ossl_method_store_new(ctx);
     if (ctx->decoder_store == NULL)
         goto err;
+    ctx->decoder_cache = ossl_decoder_cache_new(ctx);
+    if (ctx->decoder_cache == NULL)
+        goto err;
 
     /* P2. We want encoder_store to be cleaned up before the provider store */
     ctx->encoder_store = ossl_method_store_new(ctx);
@@ -226,11 +234,19 @@ static void context_deinit_objs(OSSL_LIB_CTX *ctx)
         ctx->provider_conf = NULL;
     }
 
-    /* P2. We want decoder_store to be cleaned up before the provider store */
+    /*
+     * P2. We want decoder_store/decoder_cache to be cleaned up before the
+     * provider store
+     */
     if (ctx->decoder_store != NULL) {
         ossl_method_store_free(ctx->decoder_store);
         ctx->decoder_store = NULL;
     }
+    if (ctx->decoder_cache != NULL) {
+        ossl_decoder_cache_free(ctx->decoder_cache);
+        ctx->decoder_cache = NULL;
+    }
+
 
     /* P2. We want encoder_store to be cleaned up before the provider store */
     if (ctx->encoder_store != NULL) {
@@ -559,6 +575,8 @@ void *ossl_lib_ctx_get_data(OSSL_LIB_CTX *ctx, int index)
         return ctx->child_provider;
     case OSSL_LIB_CTX_DECODER_STORE_INDEX:
         return ctx->decoder_store;
+    case OSSL_LIB_CTX_DECODER_CACHE_INDEX:
+        return ctx->decoder_cache;
     case OSSL_LIB_CTX_ENCODER_STORE_INDEX:
         return ctx->encoder_store;
     case OSSL_LIB_CTX_STORE_LOADER_STORE_INDEX:
diff --git a/crypto/encode_decode/decoder_lib.c b/crypto/encode_decode/decoder_lib.c
index 8e19532b8e..d239536175 100644
--- a/crypto/encode_decode/decoder_lib.c
+++ b/crypto/encode_decode/decoder_lib.c
@@ -281,6 +281,37 @@ void ossl_decoder_instance_free(OSSL_DECODER_INSTANCE *decoder_inst)
     }
 }
 
+OSSL_DECODER_INSTANCE *ossl_decoder_instance_dup(const OSSL_DECODER_INSTANCE *src)
+{
+    OSSL_DECODER_INSTANCE *dest;
+    const OSSL_PROVIDER *prov;
+    void *provctx;
+
+    if ((dest = OPENSSL_zalloc(sizeof(*dest))) == NULL)
+        return NULL;
+
+    *dest = *src;
+    if (!OSSL_DECODER_up_ref(dest->decoder)) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_INTERNAL_ERROR);
+        goto err;
+    }
+    prov = OSSL_DECODER_get0_provider(dest->decoder);
+    provctx = OSSL_PROVIDER_get0_provider_ctx(prov);
+
+    dest->decoderctx = dest->decoder->newctx(provctx);
+    if (dest->decoderctx == NULL) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_INTERNAL_ERROR);
+        OSSL_DECODER_free(dest->decoder);
+        goto err;
+    }
+
+    return dest;
+
+ err:
+    OPENSSL_free(dest);
+    return NULL;
+}
+
 int ossl_decoder_ctx_add_decoder_inst(OSSL_DECODER_CTX *ctx,
                                       OSSL_DECODER_INSTANCE *di)
 {
diff --git a/crypto/encode_decode/decoder_pkey.c b/crypto/encode_decode/decoder_pkey.c
index 79b120b95c..49c90a81a6 100644
--- a/crypto/encode_decode/decoder_pkey.c
+++ b/crypto/encode_decode/decoder_pkey.c
@@ -18,8 +18,11 @@
 #include "crypto/evp.h"
 #include "crypto/decoder.h"
 #include "crypto/evp/evp_local.h"
+#include "crypto/lhash.h"
 #include "encoder_local.h"
 #include "internal/namemap.h"
+#include "internal/sizes.h"
+#include "internal/decoder.h"
 
 int OSSL_DECODER_CTX_set_passphrase(OSSL_DECODER_CTX *ctx,
                                     const unsigned char *kstr,
@@ -369,10 +372,10 @@ static void collect_keymgmt(EVP_KEYMGMT *keymgmt, void *arg)
  * searches for decoders matching 'keytype', which is a string like "RSA", "DH",
  * etc. If 'keytype' is NULL, decoders for all keytypes are bound.
  */
-int ossl_decoder_ctx_setup_for_pkey(OSSL_DECODER_CTX *ctx,
-                                    EVP_PKEY **pkey, const char *keytype,
-                                    OSSL_LIB_CTX *libctx,
-                                    const char *propquery)
+static int ossl_decoder_ctx_setup_for_pkey(OSSL_DECODER_CTX *ctx,
+                                           const char *keytype,
+                                           OSSL_LIB_CTX *libctx,
+                                           const char *propquery)
 {
     int ok = 0;
     struct decoder_pkey_data_st *process_data = NULL;
@@ -408,7 +411,7 @@ int ossl_decoder_ctx_setup_for_pkey(OSSL_DECODER_CTX *ctx,
         goto err;
     }
 
-    process_data->object    = (void **)pkey;
+    process_data->object    = NULL;
     process_data->libctx    = libctx;
     process_data->selection = ctx->selection;
     process_data->keymgmts  = keymgmts;
@@ -470,6 +473,267 @@ int ossl_decoder_ctx_setup_for_pkey(OSSL_DECODER_CTX *ctx,
     return ok;
 }
 
+/* Only const here because deep_copy requires it */
+static EVP_KEYMGMT *keymgmt_dup(const EVP_KEYMGMT *keymgmt)
+{
+    if (!EVP_KEYMGMT_up_ref((EVP_KEYMGMT *)keymgmt))
+        return NULL;
+
+    return (EVP_KEYMGMT *)keymgmt;
+}
+
+/*
+ * Duplicates a template OSSL_DECODER_CTX that has been setup for an EVP_PKEY
+ * operation and sets up the duplicate for a new operation.
+ * It does not duplicate the pwdata on the assumption that this does not form
+ * part of the template. That is set up later.
+ */
+static OSSL_DECODER_CTX *
+ossl_decoder_ctx_for_pkey_dup(OSSL_DECODER_CTX *src,
+                              EVP_PKEY **pkey,
+                              const char *input_type,
+                              const char *input_structure)
+{
+    OSSL_DECODER_CTX *dest;
+    struct decoder_pkey_data_st *process_data_src, *process_data_dest = NULL;
+
+    if (src == NULL)
+        return NULL;
+
+    if ((dest = OSSL_DECODER_CTX_new()) == NULL) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        return NULL;
+    }
+
+    if (!OSSL_DECODER_CTX_set_input_type(dest, input_type)
+            || !OSSL_DECODER_CTX_set_input_structure(dest, input_structure)) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        goto err;
+    }
+    dest->selection = src->selection;
+
+    if (src->decoder_insts != NULL) {
+        dest->decoder_insts
+            = sk_OSSL_DECODER_INSTANCE_deep_copy(src->decoder_insts,
+                                                 ossl_decoder_instance_dup,
+                                                 ossl_decoder_instance_free);
+        if (dest->decoder_insts == NULL) {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+            goto err;
+        }
+    }
+
+    if (!OSSL_DECODER_CTX_set_construct(dest,
+                                        OSSL_DECODER_CTX_get_construct(src))) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        goto err;
+    }
+
+    process_data_src = OSSL_DECODER_CTX_get_construct_data(src);
+    if (process_data_src != NULL) {
+        process_data_dest = OPENSSL_zalloc(sizeof(*process_data_dest));
+        if (process_data_dest == NULL) {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_CRYPTO_LIB);
+            goto err;
+        }
+        if (process_data_src->propq != NULL) {
+            process_data_dest->propq = OPENSSL_strdup(process_data_src->propq);
+            if (process_data_dest->propq == NULL) {
+                ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_CRYPTO_LIB);
+                goto err;
+            }
+        }
+
+        if (process_data_src->keymgmts != NULL) {
+            process_data_dest->keymgmts
+                = sk_EVP_KEYMGMT_deep_copy(process_data_src->keymgmts,
+                                           keymgmt_dup,
+                                           EVP_KEYMGMT_free);
+            if (process_data_dest->keymgmts == NULL) {
+                ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_EVP_LIB);
+                goto err;
+            }
+        }
+
+        process_data_dest->object    = (void **)pkey;
+        process_data_dest->libctx    = process_data_src->libctx;
+        process_data_dest->selection = process_data_src->selection;
+        if (!OSSL_DECODER_CTX_set_construct_data(dest, process_data_dest)) {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+            goto err;
+        }
+        process_data_dest = NULL;
+    }
+
+    if (!OSSL_DECODER_CTX_set_cleanup(dest,
+                                      OSSL_DECODER_CTX_get_cleanup(src))) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        goto err;
+    }
+
+    return dest;
+ err:
+    if (process_data_dest != NULL) {
+        OPENSSL_free(process_data_dest->propq);
+        sk_EVP_KEYMGMT_pop_free(process_data_dest->keymgmts, EVP_KEYMGMT_free);
+    }
+    OSSL_DECODER_CTX_free(dest);
+    return NULL;
+}
+
+typedef struct {
+    char *input_type;
+    char *input_structure;
+    char *keytype;
+    int selection;
+    char *propquery;
+    OSSL_DECODER_CTX *template;
+} DECODER_CACHE_ENTRY;
+
+DEFINE_LHASH_OF_EX(DECODER_CACHE_ENTRY);
+
+typedef struct {
+    CRYPTO_RWLOCK *lock;
+    LHASH_OF(DECODER_CACHE_ENTRY) *hashtable;
+} DECODER_CACHE;
+
+static void decoder_cache_entry_free(DECODER_CACHE_ENTRY *entry)
+{
+    if (entry == NULL)
+        return;
+    OPENSSL_free(entry->input_type);
+    OPENSSL_free(entry->input_structure);
+    OPENSSL_free(entry->keytype);
+    OPENSSL_free(entry->propquery);
+    OSSL_DECODER_CTX_free(entry->template);
+    OPENSSL_free(entry);
+}
+
+static unsigned long decoder_cache_entry_hash(const DECODER_CACHE_ENTRY *cache)
+{
+    unsigned long hash = 17;
+
+    hash = (hash * 23)
+           + (cache->propquery == NULL
+              ? 0 : ossl_lh_strcasehash(cache->propquery));
+    hash = (hash * 23)
+           + (cache->input_structure == NULL
+              ? 0  : ossl_lh_strcasehash(cache->input_structure));
+    hash = (hash * 23)
+           + (cache->input_type == NULL
+              ? 0  : ossl_lh_strcasehash(cache->input_type));
+    hash = (hash * 23)
+           + (cache->keytype == NULL
+              ? 0  : ossl_lh_strcasehash(cache->keytype));
+
+    hash ^= cache->selection;
+
+    return hash;
+}
+
+static ossl_inline int nullstrcmp(const char *a, const char *b, int casecmp)
+{
+    if (a == NULL || b == NULL) {
+        if (a == NULL) {
+            if (b == NULL)
+                return 0;
+            else
+                return 1;
+        } else {
+            return -1;
+        }
+    } else {
+        if (casecmp)
+            return OPENSSL_strcasecmp(a, b);
+        else
+            return strcmp(a, b);
+    }
+}
+
+static int decoder_cache_entry_cmp(const DECODER_CACHE_ENTRY *a,
+                                   const DECODER_CACHE_ENTRY *b)
+{
+    int cmp;
+
+    if (a->selection != b->selection)
+        return (a->selection < b->selection) ? -1 : 1;
+
+    cmp = nullstrcmp(a->keytype, b->keytype, 1);
+    if (cmp != 0)
+        return cmp;
+
+    cmp = nullstrcmp(a->input_type, b->input_type, 1);
+    if (cmp != 0)
+        return cmp;
+
+    cmp = nullstrcmp(a->input_structure, b->input_structure, 1);
+    if (cmp != 0)
+        return cmp;
+
+    cmp = nullstrcmp(a->propquery, b->propquery, 0);
+
+    return cmp;
+}
+
+void *ossl_decoder_cache_new(OSSL_LIB_CTX *ctx)
+{
+    DECODER_CACHE *cache = OPENSSL_malloc(sizeof(*cache));
+
+    if (cache == NULL)
+        return NULL;
+
+    cache->lock = CRYPTO_THREAD_lock_new();
+    if (cache->lock == NULL) {
+        OPENSSL_free(cache);
+        return NULL;
+    }
+    cache->hashtable = lh_DECODER_CACHE_ENTRY_new(decoder_cache_entry_hash,
+                                                  decoder_cache_entry_cmp);
+    if (cache->hashtable == NULL) {
+        CRYPTO_THREAD_lock_free(cache->lock);
+        OPENSSL_free(cache);
+        return NULL;
+    }
+
+    return cache;
+}
+
+void ossl_decoder_cache_free(void *vcache)
+{
+    DECODER_CACHE *cache = (DECODER_CACHE *)vcache;
+
+    lh_DECODER_CACHE_ENTRY_doall(cache->hashtable, decoder_cache_entry_free);
+    lh_DECODER_CACHE_ENTRY_free(cache->hashtable);
+    CRYPTO_THREAD_lock_free(cache->lock);
+    OPENSSL_free(cache);
+}
+
+/*
+ * Called whenever a provider gets activated/deactivated. In that case the
+ * decoders that are available might change so we flush our cache.
+ */
+int ossl_decoder_cache_flush(OSSL_LIB_CTX *libctx)
+{
+    DECODER_CACHE *cache
+        = ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_DECODER_CACHE_INDEX);
+
+    if (cache == NULL) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        return 0;
+    }
+
+    if (!CRYPTO_THREAD_write_lock(cache->lock)) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+        return 0;
+    }
+
+    lh_DECODER_CACHE_ENTRY_doall(cache->hashtable, decoder_cache_entry_free);
+    lh_DECODER_CACHE_ENTRY_flush(cache->hashtable);
+
+    CRYPTO_THREAD_unlock(cache->lock);
+    return 1;
+}
+
 OSSL_DECODER_CTX *
 OSSL_DECODER_CTX_new_for_pkey(EVP_PKEY **pkey,
                               const char *input_type,
@@ -478,33 +742,120 @@ OSSL_DECODER_CTX_new_for_pkey(EVP_PKEY **pkey,
                               OSSL_LIB_CTX *libctx, const char *propquery)
 {
     OSSL_DECODER_CTX *ctx = NULL;
+    DECODER_CACHE *cache
+        = ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_DECODER_CACHE_INDEX);
+    DECODER_CACHE_ENTRY cacheent, *res, *newcache = NULL;
 
-    if ((ctx = OSSL_DECODER_CTX_new()) == NULL) {
+    if (cache == NULL) {
         ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
         return NULL;
     }
 
-    OSSL_TRACE_BEGIN(DECODER) {
-        BIO_printf(trc_out,
-                   "(ctx %p) Looking for %s decoders with selection %d\n",
-                   (void *)ctx, keytype, selection);
-        BIO_printf(trc_out, "    input type: %s, input structure: %s\n",
-                   input_type, input_structure);
-    } OSSL_TRACE_END(DECODER);
+    /* It is safe to cast away the const here */
+    cacheent.input_type = (char *)input_type;
+    cacheent.input_structure = (char *)input_structure;
+    cacheent.keytype = (char *)keytype;
+    cacheent.selection = selection;
+    cacheent.propquery = (char *)propquery;
+
+    if (!CRYPTO_THREAD_read_lock(cache->lock)) {
+        ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_CRYPTO_LIB);
+        return NULL;
+    }
+
+    /* First see if we have a template OSSL_DECODER_CTX */
+    res = lh_DECODER_CACHE_ENTRY_retrieve(cache->hashtable, &cacheent);
+
+    if (res == NULL) {
+        /*
+         * There is no template so we will have to construct one. This will be
+         * time consuming so release the lock and we will later upgrade it to a
+         * write lock.
+         */
+        CRYPTO_THREAD_unlock(cache->lock);
+
+        if ((ctx = OSSL_DECODER_CTX_new()) == NULL) {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+            return NULL;
+        }
 
-    if (OSSL_DECODER_CTX_set_input_type(ctx, input_type)
-        && OSSL_DECODER_CTX_set_input_structure(ctx, input_structure)
-        && OSSL_DECODER_CTX_set_selection(ctx, selection)
-        && ossl_decoder_ctx_setup_for_pkey(ctx, pkey, keytype,
-                                           libctx, propquery)
-        && OSSL_DECODER_CTX_add_extra(ctx, libctx, propquery)) {
         OSSL_TRACE_BEGIN(DECODER) {
-            BIO_printf(trc_out, "(ctx %p) Got %d decoders\n",
-                       (void *)ctx, OSSL_DECODER_CTX_get_num_decoders(ctx));
+            BIO_printf(trc_out,
+                    "(ctx %p) Looking for %s decoders with selection %d\n",
+                    (void *)ctx, keytype, selection);
+            BIO_printf(trc_out, "    input type: %s, input structure: %s\n",
+                    input_type, input_structure);
         } OSSL_TRACE_END(DECODER);
-        return ctx;
+
+        if (OSSL_DECODER_CTX_set_input_type(ctx, input_type)
+            && OSSL_DECODER_CTX_set_input_structure(ctx, input_structure)
+            && OSSL_DECODER_CTX_set_selection(ctx, selection)
+            && ossl_decoder_ctx_setup_for_pkey(ctx, keytype, libctx, propquery)
+            && OSSL_DECODER_CTX_add_extra(ctx, libctx, propquery)) {
+            OSSL_TRACE_BEGIN(DECODER) {
+                BIO_printf(trc_out, "(ctx %p) Got %d decoders\n",
+                        (void *)ctx, OSSL_DECODER_CTX_get_num_decoders(ctx));
+            } OSSL_TRACE_END(DECODER);
+        } else {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_OSSL_DECODER_LIB);
+            OSSL_DECODER_CTX_free(ctx);
+            return NULL;
+        }
+
+        newcache = OPENSSL_zalloc(sizeof(*newcache));
+        if (newcache == NULL) {
+            OSSL_DECODER_CTX_free(ctx);
+            return NULL;
+        }
+
+        if (input_type != NULL) {
+            newcache->input_type = OPENSSL_strdup(input_type);
+            if (newcache->input_type == NULL)
+                goto err;
+        }
+        if (input_structure != NULL) {
+            newcache->input_structure = OPENSSL_strdup(input_structure);
+            if (newcache->input_structure == NULL)
+                goto err;
+        }
+        if (keytype != NULL) {
+            newcache->keytype = OPENSSL_strdup(keytype);
+            if (newcache->keytype == NULL)
+                goto err;
+        }
+        if (propquery != NULL) {
+            newcache->propquery = OPENSSL_strdup(propquery);
+            if (newcache->propquery == NULL)
+                goto err;
+        }
+        newcache->selection = selection;
+        newcache->template = ctx;
+
+        if (!CRYPTO_THREAD_write_lock(cache->lock)) {
+            ERR_raise(ERR_LIB_OSSL_DECODER, ERR_R_CRYPTO_LIB);
+            return NULL;
+        }
+        res = lh_DECODER_CACHE_ENTRY_retrieve(cache->hashtable, &cacheent);
+        if (res == NULL) {
+            lh_DECODER_CACHE_ENTRY_insert(cache->hashtable, newcache);
+        } else {
+            /*
+             * We raced with another thread to construct this and lost. Free
+             * what we just created and use the entry from the hashtable instead
+             */
+            decoder_cache_entry_free(newcache);
+            ctx = res->template;
+        }
+    } else {
+        ctx = res->template;
     }
 
+    ctx = ossl_decoder_ctx_for_pkey_dup(ctx, pkey, input_type, input_structure);
+    CRYPTO_THREAD_unlock(cache->lock);
+
+    return ctx;
+ err:
+    decoder_cache_entry_free(newcache);
     OSSL_DECODER_CTX_free(ctx);
     return NULL;
 }
diff --git a/crypto/evp/evp_fetch.c b/crypto/evp/evp_fetch.c
index 9e4f80d218..b21c6f283b 100644
--- a/crypto/evp/evp_fetch.c
+++ b/crypto/evp/evp_fetch.c
@@ -17,6 +17,7 @@
 #include "internal/core.h"
 #include "internal/provider.h"
 #include "internal/namemap.h"
+#include "internal/decoder.h"
 #include "crypto/evp.h"    /* evp_local.h needs it */
 #include "evp_local.h"
 
@@ -422,6 +423,7 @@ static int evp_set_parsed_default_properties(OSSL_LIB_CTX *libctx,
     OSSL_PROPERTY_LIST **plp = ossl_ctx_global_properties(libctx, loadconfig);
 
     if (plp != NULL && store != NULL) {
+        int ret;
 #ifndef FIPS_MODULE
         char *propstr = NULL;
         size_t strsz;
@@ -455,8 +457,12 @@ static int evp_set_parsed_default_properties(OSSL_LIB_CTX *libctx,
 #endif
         ossl_property_free(*plp);
         *plp = def_prop;
-        if (store != NULL)
-            return ossl_method_store_cache_flush_all(store);
+
+        ret = ossl_method_store_cache_flush_all(store);
+#ifndef FIPS_MODULE
+        ossl_decoder_cache_flush(libctx);
+#endif
+        return ret;
     }
     ERR_raise(ERR_LIB_EVP, ERR_R_INTERNAL_ERROR);
     return 0;
diff --git a/crypto/provider_core.c b/crypto/provider_core.c
index 49a0eb8c46..39b11629fc 100644
--- a/crypto/provider_core.c
+++ b/crypto/provider_core.c
@@ -28,6 +28,7 @@
 #include "internal/refcount.h"
 #include "internal/bio.h"
 #include "internal/core.h"
+#include "internal/decoder.h"
 #include "provider_local.h"
 #include "crypto/context.h"
 #ifndef FIPS_MODULE
@@ -657,6 +658,15 @@ int ossl_provider_add_to_store(OSSL_PROVIDER *prov, OSSL_PROVIDER **actualprov,
         ossl_provider_deactivate(prov, 0);
         ossl_provider_free(prov);
     }
+#ifndef FIPS_MODULE
+    else {
+        /*
+         * This can be done outside the lock. We tolerate other threads getting
+         * the wrong result briefly when creating OSSL_DECODER_CTXs.
+         */
+        ossl_decoder_cache_flush(prov->libctx);
+    }
+#endif
 
     return 1;
 
@@ -1103,6 +1113,14 @@ static int provider_deactivate(OSSL_PROVIDER *prov, int upcalls,
     if (lock) {
         CRYPTO_THREAD_unlock(prov->flag_lock);
         CRYPTO_THREAD_unlock(store->lock);
+        /*
+         * This can be done outside the lock. We tolerate other threads getting
+         * the wrong result briefly when creating OSSL_DECODER_CTXs.
+         */
+#ifndef FIPS_MODULE
+        if (count < 1)
+            ossl_decoder_cache_flush(prov->libctx);
+#endif
     }
 #ifndef FIPS_MODULE
     if (freeparent)
@@ -1165,6 +1183,14 @@ static int provider_activate(OSSL_PROVIDER *prov, int lock, int upcalls)
     if (lock) {
         CRYPTO_THREAD_unlock(prov->flag_lock);
         CRYPTO_THREAD_unlock(store->lock);
+        /*
+         * This can be done outside the lock. We tolerate other threads getting
+         * the wrong result briefly when creating OSSL_DECODER_CTXs.
+         */
+#ifndef FIPS_MODULE
+        if (count == 1)
+            ossl_decoder_cache_flush(prov->libctx);
+#endif
     }
 
     if (!ret)
diff --git a/include/crypto/decoder.h b/include/crypto/decoder.h
index a496f23e49..514190fca2 100644
--- a/include/crypto/decoder.h
+++ b/include/crypto/decoder.h
@@ -25,14 +25,10 @@ void *ossl_decoder_from_algorithm(int id, const OSSL_ALGORITHM *algodef,
 OSSL_DECODER_INSTANCE *
 ossl_decoder_instance_new(OSSL_DECODER *decoder, void *decoderctx);
 void ossl_decoder_instance_free(OSSL_DECODER_INSTANCE *decoder_inst);
+OSSL_DECODER_INSTANCE *ossl_decoder_instance_dup(const OSSL_DECODER_INSTANCE *src);
 int ossl_decoder_ctx_add_decoder_inst(OSSL_DECODER_CTX *ctx,
                                       OSSL_DECODER_INSTANCE *di);
 
-int ossl_decoder_ctx_setup_for_pkey(OSSL_DECODER_CTX *ctx,
-                                    EVP_PKEY **pkey, const char *keytype,
-                                    OSSL_LIB_CTX *libctx,
-                                    const char *propquery);
-
 int ossl_decoder_get_number(const OSSL_DECODER *encoder);
 int ossl_decoder_store_cache_flush(OSSL_LIB_CTX *libctx);
 int ossl_decoder_store_remove_all_provided(const OSSL_PROVIDER *prov);
diff --git a/include/internal/cryptlib.h b/include/internal/cryptlib.h
index 5aeb4fe0f2..fd2eb5d56c 100644
--- a/include/internal/cryptlib.h
+++ b/include/internal/cryptlib.h
@@ -117,6 +117,7 @@ typedef struct ossl_ex_data_global_st {
 # define OSSL_LIB_CTX_BIO_CORE_INDEX                17
 # define OSSL_LIB_CTX_CHILD_PROVIDER_INDEX          18
 # define OSSL_LIB_CTX_THREAD_INDEX                  19
+# define OSSL_LIB_CTX_DECODER_CACHE_INDEX           20
 # define OSSL_LIB_CTX_MAX_INDEXES                   20
 
 OSSL_LIB_CTX *ossl_lib_ctx_get_concrete(OSSL_LIB_CTX *ctx);
diff --git a/include/internal/decoder.h b/include/internal/decoder.h
new file mode 100644
index 0000000000..bfe1429ffb
--- /dev/null
+++ b/include/internal/decoder.h
@@ -0,0 +1,18 @@
+/*
+ * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#ifndef OSSL_INTERNAL_DECODER_H
+# define OSSL_INTERNAL_DECODER_H
+# pragma once
+
+void *ossl_decoder_cache_new(OSSL_LIB_CTX *ctx);
+void ossl_decoder_cache_free(void *vcache);
+int ossl_decoder_cache_flush(OSSL_LIB_CTX *libctx);
+
+#endif
diff --git a/providers/implementations/storemgmt/file_store.c b/providers/implementations/storemgmt/file_store.c
index bcc037c6d4..e7added1a9 100644
--- a/providers/implementations/storemgmt/file_store.c
+++ b/providers/implementations/storemgmt/file_store.c
@@ -55,9 +55,7 @@ static OSSL_FUNC_store_close_fn file_close;
  * passes that on to the data callback; this decoder is created with
  * internal OpenSSL functions, thereby bypassing the need for a surrounding
  * provider.  This is ok, since this is a local decoder, not meant for
- * public consumption.  It also uses the libcrypto internal decoder
- * setup function ossl_decoder_ctx_setup_for_pkey(), to allow the
- * last resort decoder to be added first (and thereby be executed last).
+ * public consumption.
  * Finally, it sets up its own construct and cleanup functions.
  *
  * Essentially, that makes this implementation a kind of glorified decoder.