SERVER-47916 Make InvalidatingLRUCache use an 'epoch' when invalidating evicted checked-out values

10 files changed, 143 insertions, 63 deletions

diff --git a/src/mongo/client/dbclient_base.cpp b/src/mongo/client/dbclient_base.cpp
index daa10d3888d..87947613ad6 100644
--- a/src/mongo/client/dbclient_base.cpp
+++ b/src/mongo/client/dbclient_base.cpp
@@ -48,7 +48,6 @@
 #include "mongo/client/constants.h"
 #include "mongo/client/dbclient_cursor.h"
 #include "mongo/config.h"
-#include "mongo/db/auth/authorization_manager.h"
 #include "mongo/db/commands.h"
 #include "mongo/db/json.h"
 #include "mongo/db/namespace_string.h"
diff --git a/src/mongo/db/auth/authorization_manager_impl.cpp b/src/mongo/db/auth/authorization_manager_impl.cpp
index 5b79c377f05..e3552ae7332 100644
--- a/src/mongo/db/auth/authorization_manager_impl.cpp
+++ b/src/mongo/db/auth/authorization_manager_impl.cpp
@@ -655,11 +655,16 @@ AuthorizationManagerImpl::AuthSchemaVersionCache::AuthSchemaVersionCache(
     ServiceContext* service,
     ThreadPoolInterface& threadPool,
     AuthzManagerExternalState* externalState)
-    : ReadThroughCache(_mutex, service, threadPool, 1 /* cacheSize */),
+    : ReadThroughCache(
+          _mutex,
+          service,
+          threadPool,
+          [this](OperationContext* opCtx, int unusedKey) { return _lookup(opCtx, unusedKey); },
+          1 /* cacheSize */),
       _externalState(externalState) {}
 
-boost::optional<int> AuthorizationManagerImpl::AuthSchemaVersionCache::lookup(
-    OperationContext* opCtx, const int& unusedKey) {
+boost::optional<int> AuthorizationManagerImpl::AuthSchemaVersionCache::_lookup(
+    OperationContext* opCtx, int unusedKey) {
     invariant(unusedKey == 0);
 
     int authzVersion;
@@ -674,12 +679,18 @@ AuthorizationManagerImpl::UserCacheImpl::UserCacheImpl(
     int cacheSize,
     AuthSchemaVersionCache* authSchemaVersionCache,
     AuthzManagerExternalState* externalState)
-    : UserCache(_mutex, service, threadPool, cacheSize),
+    : UserCache(_mutex,
+                service,
+                threadPool,
+                [this](OperationContext* opCtx, const UserRequest& userReq) {
+                    return _lookup(opCtx, userReq);
+                },
+                cacheSize),
       _authSchemaVersionCache(authSchemaVersionCache),
       _externalState(externalState) {}
 
-boost::optional<User> AuthorizationManagerImpl::UserCacheImpl::lookup(OperationContext* opCtx,
-                                                                      const UserRequest& userReq) {
+boost::optional<User> AuthorizationManagerImpl::UserCacheImpl::_lookup(OperationContext* opCtx,
+                                                                       const UserRequest& userReq) {
     LOGV2_DEBUG(20238, 1, "Getting user record", "user"_attr = userReq.name);
 
     // Number of times to retry a user document that fetches due to transient AuthSchemaIncompatible
diff --git a/src/mongo/db/auth/authorization_manager_impl.h b/src/mongo/db/auth/authorization_manager_impl.h
index ede04f148a9..17a3d731f1f 100644
--- a/src/mongo/db/auth/authorization_manager_impl.h
+++ b/src/mongo/db/auth/authorization_manager_impl.h
@@ -154,12 +154,12 @@ private:
                                ThreadPoolInterface& threadPool,
                                AuthzManagerExternalState* externalState);
 
+    private:
         // Even though the dist cache permits for lookup to return boost::none for non-existent
         // values, the contract of the authorization manager is that it should throw an exception if
         // the value can not be loaded, so if it returns, the value will always be set.
-        boost::optional<int> lookup(OperationContext* opCtx, const int& unusedKey) override;
+        boost::optional<int> _lookup(OperationContext* opCtx, int unusedKey);
 
-    private:
         Mutex _mutex =
             MONGO_MAKE_LATCH("AuthorizationManagerImpl::AuthSchemaVersionDistCache::_mutex");
 
@@ -177,12 +177,12 @@ private:
                       AuthSchemaVersionCache* authSchemaVersionCache,
                       AuthzManagerExternalState* externalState);
 
+    private:
         // Even though the dist cache permits for lookup to return boost::none for non-existent
         // values, the contract of the authorization manager is that it should throw an exception if
         // the value can not be loaded, so if it returns, the value will always be set.
-        boost::optional<User> lookup(OperationContext* opCtx, const UserRequest& user) override;
+        boost::optional<User> _lookup(OperationContext* opCtx, const UserRequest& user);
 
-    private:
         Mutex _mutex = MONGO_MAKE_LATCH("AuthorizationManagerImpl::UserDistCacheImpl::_mutex");
 
         AuthSchemaVersionCache* const _authSchemaVersionCache;
diff --git a/src/mongo/db/read_write_concern_defaults.cpp b/src/mongo/db/read_write_concern_defaults.cpp
index 1667670bc4b..f33c78215a3 100644
--- a/src/mongo/db/read_write_concern_defaults.cpp
+++ b/src/mongo/db/read_write_concern_defaults.cpp
@@ -166,7 +166,7 @@ void ReadWriteConcernDefaults::setDefault(OperationContext* opCtx, RWConcernDefa
 }
 
 void ReadWriteConcernDefaults::refreshIfNecessary(OperationContext* opCtx) {
-    auto possibleNewDefaults = _defaults.lookup(opCtx, Type::kReadWriteConcernEntry);
+    auto possibleNewDefaults = _defaults.lookup(opCtx);
     if (!possibleNewDefaults) {
         return;
     }
@@ -216,16 +216,12 @@ ReadWriteConcernDefaults& ReadWriteConcernDefaults::get(OperationContext* opCtx)
 }
 
 void ReadWriteConcernDefaults::create(ServiceContext* service, FetchDefaultsFn fetchDefaultsFn) {
-    getReadWriteConcernDefaults(service).emplace(service, fetchDefaultsFn);
+    getReadWriteConcernDefaults(service).emplace(service, std::move(fetchDefaultsFn));
 }
 
 ReadWriteConcernDefaults::ReadWriteConcernDefaults(ServiceContext* service,
                                                    FetchDefaultsFn fetchDefaultsFn)
-    : _defaults(service,
-                _threadPool,
-                [fetchDefaultsFn = std::move(fetchDefaultsFn)](
-                    OperationContext* opCtx, const Type&) { return fetchDefaultsFn(opCtx); }),
-      _threadPool([] {
+    : _defaults(service, _threadPool, std::move(fetchDefaultsFn)), _threadPool([] {
           ThreadPool::Options options;
           options.poolName = "ReadWriteConcernDefaults";
           options.minThreads = 0;
@@ -240,14 +236,16 @@ ReadWriteConcernDefaults::~ReadWriteConcernDefaults() = default;
 
 ReadWriteConcernDefaults::Cache::Cache(ServiceContext* service,
                                        ThreadPoolInterface& threadPool,
-                                       LookupFn lookupFn)
-    : ReadThroughCache(_mutex, service, threadPool, 1 /* cacheSize */),
-      _lookupFn(std::move(lookupFn)) {}
-
-boost::optional<RWConcernDefault> ReadWriteConcernDefaults::Cache::lookup(
-    OperationContext* opCtx, const ReadWriteConcernDefaults::Type& key) {
-    invariant(key == Type::kReadWriteConcernEntry);
-    return _lookupFn(opCtx, key);
+                                       FetchDefaultsFn fetchDefaultsFn)
+    : ReadThroughCache(_mutex,
+                       service,
+                       threadPool,
+                       [this](OperationContext* opCtx, Type) { return lookup(opCtx); },
+                       1 /* cacheSize */),
+      _fetchDefaultsFn(std::move(fetchDefaultsFn)) {}
+
+boost::optional<RWConcernDefault> ReadWriteConcernDefaults::Cache::lookup(OperationContext* opCtx) {
+    return _fetchDefaultsFn(opCtx);
 }
 
 }  // namespace mongo
diff --git a/src/mongo/db/read_write_concern_defaults.h b/src/mongo/db/read_write_concern_defaults.h
index 282ee810a27..ff29c9df300 100644
--- a/src/mongo/db/read_write_concern_defaults.h
+++ b/src/mongo/db/read_write_concern_defaults.h
@@ -54,7 +54,7 @@ public:
     using ReadConcern = repl::ReadConcernArgs;
     using WriteConcern = WriteConcernOptions;
 
-    using FetchDefaultsFn = std::function<boost::optional<RWConcernDefault>(OperationContext*)>;
+    using FetchDefaultsFn = unique_function<boost::optional<RWConcernDefault>(OperationContext*)>;
 
     static constexpr StringData readConcernFieldName = ReadConcern::kReadConcernFieldName;
     static constexpr StringData writeConcernFieldName = WriteConcern::kWriteConcernField;
@@ -162,15 +162,17 @@ private:
         Cache& operator=(const Cache&) = delete;
 
     public:
-        Cache(ServiceContext* service, ThreadPoolInterface& threadPool, LookupFn lookupFn);
+        Cache(ServiceContext* service,
+              ThreadPoolInterface& threadPool,
+              FetchDefaultsFn fetchDefaultsFn);
         virtual ~Cache() = default;
 
-        boost::optional<RWConcernDefault> lookup(OperationContext* opCtx, const Type& key) override;
+        boost::optional<RWConcernDefault> lookup(OperationContext* opCtx);
 
     private:
         Mutex _mutex = MONGO_MAKE_LATCH("ReadWriteConcernDefaults::Cache");
 
-        LookupFn _lookupFn;
+        FetchDefaultsFn _fetchDefaultsFn;
     };
 
     Cache _defaults;
diff --git a/src/mongo/util/invalidating_lru_cache.h b/src/mongo/util/invalidating_lru_cache.h
index 534c08d2114..8c80185f3f8 100644
--- a/src/mongo/util/invalidating_lru_cache.h
+++ b/src/mongo/util/invalidating_lru_cache.h
@@ -55,23 +55,60 @@ class InvalidatingLRUCache {
          * The 'owningCache' and 'key' values can be nullptr/boost::none in order to support the
          * detached mode of ValueHandle below.
          */
-        StoredValue(InvalidatingLRUCache* in_owningCache,
-                    boost::optional<Key> in_key,
-                    Value&& in_value)
-            : owningCache(in_owningCache), key(in_key), value(std::move(in_value)) {}
+        StoredValue(InvalidatingLRUCache* owningCache,
+                    uint64_t epoch,
+                    boost::optional<Key>&& key,
+                    Value&& value)
+            : owningCache(owningCache),
+              epoch(epoch),
+              key(std::move(key)),
+              value(std::move(value)) {}
 
         ~StoredValue() {
-            if (owningCache) {
-                stdx::lock_guard<Latch> lg(owningCache->_mutex);
-                owningCache->_evictedCheckedOutValues.erase(*key);
+            if (!owningCache)
+                return;
+
+            stdx::unique_lock<Latch> ul(owningCache->_mutex);
+            auto& evictedCheckedOutValues = owningCache->_evictedCheckedOutValues;
+            auto it = evictedCheckedOutValues.find(*key);
+
+            // The lookup above can encounter the following cases:
+            //
+            // 1) The 'key' is not on the evictedCheckedOutValues map, because a second value for it
+            // was inserted, which was also evicted and all its handles expired (so it got removed)
+            if (it == evictedCheckedOutValues.end())
+                return;
+            auto storedValue = it->second.lock();
+            // 2) There are no more references to 'key', but it is stil on the map, which means
+            // either we are running its destrutor, or some other thread is running the destructor
+            // of a different epoch. In either case it is fine to remove the 'it' because we are
+            // under a mutex.
+            if (!storedValue) {
+                evictedCheckedOutValues.erase(it);
+                return;
             }
+            ul.unlock();
+            // 3) The value for 'key' is for a different epoch, in which case we must dereference
+            // the '.lock()'ed storedValue outside of the mutex in order to avoid reentrancy while
+            // holding a mutex.
+            invariant(storedValue->epoch != epoch);
         }
 
+        // Copy and move constructors need to be deleted in order to avoid having to make the
+        // destructor to account for the object having been moved
+        StoredValue(StoredValue&) = delete;
+        StoredValue& operator=(StoredValue&) = delete;
+        StoredValue(StoredValue&&) = delete;
+        StoredValue& operator=(StoredValue&&) = delete;
+
         // The cache which stores this key/value pair
-        InvalidatingLRUCache* owningCache;
+        InvalidatingLRUCache* const owningCache;
+
+        // Identity associated with this value. See the destructor for its usage.
+        const uint64_t epoch;
 
         // The key/value pair. See the comments on the constructor about why the key is optional.
-        boost::optional<Key> key;
+        const boost::optional<Key> key;
         Value value;
 
         // Initially set to true to indicate that the entry is valid and can be read without
@@ -105,7 +142,7 @@ public:
         // support pinning items. Their only usage must be in the authorization mananager for the
         // internal authentication user.
         explicit ValueHandle(Value&& value)
-            : _value(std::make_shared<StoredValue>(nullptr, boost::none, std::move(value))) {}
+            : _value(std::make_shared<StoredValue>(nullptr, 0, boost::none, std::move(value))) {}
 
         ValueHandle() = default;
 
@@ -159,7 +196,8 @@ public:
         LockGuardWithPostUnlockDestructor guard(_mutex);
         _invalidate(&guard, key, _cache.find(key));
         if (auto evicted = _cache.add(
-                key, std::make_shared<StoredValue>(this, key, std::forward<Value>(value)))) {
+                key,
+                std::make_shared<StoredValue>(this, ++_epoch, key, std::forward<Value>(value)))) {
             const auto& evictedKey = evicted->first;
             auto& evictedValue = evicted->second;
 
@@ -192,7 +230,8 @@ public:
         LockGuardWithPostUnlockDestructor guard(_mutex);
         _invalidate(&guard, key, _cache.find(key));
         if (auto evicted = _cache.add(
-                key, std::make_shared<StoredValue>(this, key, std::forward<Value>(value)))) {
+                key,
+                std::make_shared<StoredValue>(this, ++_epoch, key, std::forward<Value>(value)))) {
             const auto& evictedKey = evicted->first;
             auto& evictedValue = evicted->second;
 
@@ -373,6 +412,10 @@ private:
     using EvictedCheckedOutValuesMap = stdx::unordered_map<Key, std::weak_ptr<StoredValue>>;
     EvictedCheckedOutValuesMap _evictedCheckedOutValues;
 
+    // An always-incrementing counter from which to obtain "identities" for each value stored in the
+    // cache, so that different instantiations for the same key can be differentiated
+    uint64_t _epoch{0};
+
     Cache _cache;
 };
 
diff --git a/src/mongo/util/invalidating_lru_cache_test.cpp b/src/mongo/util/invalidating_lru_cache_test.cpp
index dfe546f933c..eea916ab4df 100644
--- a/src/mongo/util/invalidating_lru_cache_test.cpp
+++ b/src/mongo/util/invalidating_lru_cache_test.cpp
@@ -229,6 +229,34 @@ TEST(InvalidatingLRUCacheTest, CheckedOutItemsAreInvalidatedWithPredicateWhenEvi
     }
 }
 
+TEST(InvalidatingLRUCacheTest, OrderOfDestructionOfHandlesDiffersFromOrderOfInsertion) {
+    TestValueCache cache(1);
+
+    boost::optional<TestValueCache::ValueHandle> firstValue(
+        cache.insertOrAssignAndGet(100, {"Key 100, Value 1"}));
+    ASSERT(*firstValue);
+    ASSERT(firstValue->isValid());
+
+    // This will invalidate the first value of key 100
+    auto secondValue = cache.insertOrAssignAndGet(100, {"Key 100, Value 2"});
+    ASSERT(secondValue);
+    ASSERT(secondValue.isValid());
+    ASSERT(!firstValue->isValid());
+
+    // This will evict the second value of key 100
+    cache.insertOrAssignAndGet(200, {"Key 200, Value 1"});
+    ASSERT(secondValue);
+    ASSERT(secondValue.isValid());
+    ASSERT(!firstValue->isValid());
+
+    // This makes the first value of 100's handle go away before the second value's hande
+    firstValue.reset();
+    ASSERT(secondValue.isValid());
+
+    cache.invalidate(100);
+    ASSERT(!secondValue.isValid());
+}
+
 TEST(InvalidatingLRUCacheTest, AssignWhileValueIsCheckedOutInvalidatesFirstValue) {
     TestValueCache cache(1);
 
diff --git a/src/mongo/util/net/ssl_manager_openssl.cpp b/src/mongo/util/net/ssl_manager_openssl.cpp
index 03d728ab5d3..67f29f435a9 100644
--- a/src/mongo/util/net/ssl_manager_openssl.cpp
+++ b/src/mongo/util/net/ssl_manager_openssl.cpp
@@ -931,7 +931,7 @@ StatusWith<OCSPValidationContext> extractOcspUris(SSL_CTX* context,
 class OCSPCache : public ReadThroughCache<OCSPCacheKey, OCSPFetchResponse> {
 public:
     OCSPCache(ServiceContext* service)
-        : ReadThroughCache(_mutex, service, _threadPool, tlsOCSPCacheSize) {
+        : ReadThroughCache(_mutex, service, _threadPool, _lookup, tlsOCSPCacheSize) {
         _threadPool.startup();
     }
 
@@ -948,8 +948,8 @@ public:
     }
 
 private:
-    boost::optional<OCSPFetchResponse> lookup(OperationContext* opCtx,
-                                              const OCSPCacheKey& key) final {
+    static boost::optional<OCSPFetchResponse> _lookup(OperationContext* opCtx,
+                                                      const OCSPCacheKey& key) {
         // If there is a CRL file, we expect the CRL file to cover the certificate status
         // information, and therefore we don't need to make a roundtrip.
         if (!getSSLGlobalParams().sslCRLFile.empty()) {
diff --git a/src/mongo/util/read_through_cache.h b/src/mongo/util/read_through_cache.h
index 17dd48d703f..a8ab84ae19f 100644
--- a/src/mongo/util/read_through_cache.h
+++ b/src/mongo/util/read_through_cache.h
@@ -115,8 +115,6 @@ class ReadThroughCache : public ReadThroughCacheBase {
     using Cache = InvalidatingLRUCache<Key, StoredValue>;
 
 public:
-    using LookupFn = std::function<boost::optional<Value>(OperationContext*, const Key&)>;
-
     /**
      * Common type for values returned from the cache.
      */
@@ -177,6 +175,14 @@ public:
     };
 
     /**
+     * Signature for a blocking function to provide the value for a key when there is a cache miss.
+     *
+     * The implementation must throw a uassertion to indicate an error while looking up the value,
+     * return boost::none if the key is not found, or return an actual value.
+     */
+    using LookupFn = unique_function<boost::optional<Value>(OperationContext*, const Key&)>;
+
+    /**
      * If 'key' is found in the cache, returns a set ValueHandle (its operator bool will be true).
      * Otherwise, either causes the blocking 'lookup' below to be asynchronously invoked to fetch
      * 'key' from the backing store (or joins an already scheduled invocation) and returns a future
@@ -337,21 +343,17 @@ protected:
     ReadThroughCache(Mutex& mutex,
                      ServiceContext* service,
                      ThreadPoolInterface& threadPool,
+                     LookupFn lookupFn,
                      int cacheSize)
-        : ReadThroughCacheBase(mutex, service, threadPool), _cache(cacheSize) {}
+        : ReadThroughCacheBase(mutex, service, threadPool),
+          _lookupFn(std::move(lookupFn)),
+          _cache(cacheSize) {}
 
     ~ReadThroughCache() {
         invariant(_inProgressLookups.empty());
     }
 
 private:
-    /**
-     * Provide the value for a key when there is a cache miss.  Sub-classes must implement this
-     * function appropriately.  Throw a uassertion to indicate an error while looking up the value,
-     * or return value for this key, or boost::none if this key has no value.
-     */
-    virtual boost::optional<Value> lookup(OperationContext* opCtx, const Key& key) = 0;
-
     // Refer to the comments on '_asyncLookupWhileInvalidated' for more detail on how this structure
     // is used.
     struct InProgressLookup {
@@ -414,7 +416,7 @@ private:
                 OperationContext * opCtx, const Status& status) mutable noexcept {
                 p->setWith([&]() mutable {
                     uassertStatusOK(status);
-                    auto value = lookup(opCtx, inProgressLookup.key);
+                    auto value = _lookupFn(opCtx, inProgressLookup.key);
                     uassert(ErrorCodes::ReadThroughCacheKeyNotFound,
                             "Internal only: key not found",
                             value);
@@ -433,6 +435,9 @@ private:
         return std::move(future);
     };
 
+    // Blocking function which will be invoked to retrieve entries from the backing store
+    const LookupFn _lookupFn;
+
     // Contains all the currently cached keys. This structure is self-synchronising and doesn't
     // require a mutex. However, on cache miss it is accessed under '_mutex', which is safe, because
     // _cache's mutex itself is at level 0.
diff --git a/src/mongo/util/read_through_cache_test.cpp b/src/mongo/util/read_through_cache_test.cpp
index 520eb3fedf5..169606cfbdb 100644
--- a/src/mongo/util/read_through_cache_test.cpp
+++ b/src/mongo/util/read_through_cache_test.cpp
@@ -51,16 +51,10 @@ struct CachedValue {
 class Cache : public ReadThroughCache<std::string, CachedValue> {
 public:
     Cache(ServiceContext* service, ThreadPoolInterface& threadPool, size_t size, LookupFn lookupFn)
-        : ReadThroughCache(_mutex, service, threadPool, size), _lookupFn(std::move(lookupFn)) {}
+        : ReadThroughCache(_mutex, service, threadPool, std::move(lookupFn), size) {}
 
 private:
-    boost::optional<CachedValue> lookup(OperationContext* opCtx, const std::string& key) override {
-        return _lookupFn(opCtx, key);
-    }
-
     Mutex _mutex = MONGO_MAKE_LATCH("ReadThroughCacheTest::Cache");
-
-    LookupFn _lookupFn;
 };
 
 /**