--- a/toolkit/components/resistfingerprinting/nsRFPService.cpp
+++ b/toolkit/components/resistfingerprinting/nsRFPService.cpp
@@ -6,16 +6,17 @@
 #include "nsRFPService.h"
 
 #include <algorithm>
 #include <memory>
 #include <time.h>
 
 #include "mozilla/ClearOnShutdown.h"
 #include "mozilla/Logging.h"
+#include "mozilla/Mutex.h"
 #include "mozilla/Preferences.h"
 #include "mozilla/Services.h"
 #include "mozilla/StaticPtr.h"
 #include "mozilla/TextEvents.h"
 #include "mozilla/dom/KeyboardEventBinding.h"
 
 #include "nsCOMPtr.h"
 #include "nsCoord.h"
@@ -135,78 +136,108 @@ nsRFPService::IsTimerPrecisionReductionE
 
   return (sPrivacyTimerPrecisionReduction || IsResistFingerprintingEnabled()) &&
          TimerResolution() > 0;
 }
 
 /*
  * The below is a simple time-based Least Recently Used cache used to store the
  * result of a cryptographic hash function. It has LRU_CACHE_SIZE slots, and will
- * be used from multiple threads. It will be thread-safe in a future commit.
+ * be used from multiple threads. It is thread-safe.
  */
 #define LRU_CACHE_SIZE         (45)
 #define HASH_DIGEST_SIZE_BITS  (256)
 #define HASH_DIGEST_SIZE_BYTES (HASH_DIGEST_SIZE_BITS / 8)
 
-// TODO: Fix Race Conditions
 class LRUCache
 {
 public:
-  LRUCache() {
+  LRUCache()
+    : mLock("mozilla.resistFingerprinting.LRUCache") {
     this->cache.SetLength(LRU_CACHE_SIZE);
   }
 
   nsCString Get(long long aKey) {
     for (auto & cacheEntry : this->cache) {
+      // Read optimistically befor locking
       if (cacheEntry.key == aKey) {
+        MutexAutoLock lock(mLock);
+
+        // Double check after we have a lock
+        if (MOZ_UNLIKELY(cacheEntry.key != aKey)) {
+          // Got evicted in a race
+#if defined(DEBUG)
+          long long tmp_key = cacheEntry.key;
+          MOZ_LOG(gResistFingerprintingLog, LogLevel::Verbose,
+            ("LRU Cache HIT-MISS with %lli != %lli", aKey, tmp_key));
+#endif
+          return EmptyCString();
+        }
+
         cacheEntry.accessTime = PR_Now();
 
 #if defined(DEBUG)
         MOZ_LOG(gResistFingerprintingLog, LogLevel::Verbose,
-          ("LRU Cache HIT with %lli == %lli", aKey, cacheEntry.key));
+          ("LRU Cache HIT with %lli", aKey));
 #endif
         return cacheEntry.data;
       }
     }
+
     return EmptyCString();
   }
 
   void Store(long long aKey, const nsCString& aValue) {
     MOZ_DIAGNOSTIC_ASSERT(aValue.Length() == HASH_DIGEST_SIZE_BYTES);
+    MutexAutoLock lock(mLock);
 
     CacheEntry* lowestKey = &this->cache[0];
     for (auto & cacheEntry : this->cache) {
+      if (MOZ_UNLIKELY(cacheEntry.key == aKey)) {
+        // Another thread inserted before us, don't insert twice
+#if defined(DEBUG)
+        MOZ_LOG(gResistFingerprintingLog, LogLevel::Verbose,
+          ("LRU Cache DOUBLE STORE with %lli", aKey));
+#endif
+        return;
+      }
       if (cacheEntry.accessTime < lowestKey->accessTime) {
         lowestKey = &cacheEntry;
       }
     }
 
     lowestKey->key = aKey;
     lowestKey->data = aValue;
     lowestKey->accessTime = PR_Now();
 #if defined(DEBUG)
     MOZ_LOG(gResistFingerprintingLog, LogLevel::Verbose, ("LRU Cache STORE with %lli", aKey));
 #endif
   }
 
 
 private:
   struct CacheEntry {
-    long long key;
+    Atomic<long long, Relaxed> key;
     PRTime accessTime = 0;
     nsCString data;
 
     CacheEntry() {
       this->key = 0xFFFFFFFFFFFFFFFF;
       this->accessTime = 0;
       this->data = nullptr;
     }
+    CacheEntry(const CacheEntry &obj) {
+      this->key.exchange(obj.key);
+      this->accessTime = obj.accessTime;
+      this->data = obj.data;
+    }
   };
 
   AutoTArray<CacheEntry, LRU_CACHE_SIZE> cache;
+  mozilla::Mutex mLock;
 };
 
 /**
  * The purpose of this function is to deterministicly generate a random midpoint
  * between a lower clamped value and an upper clamped value. Assuming a clamping
  * resolution of 100, here is an example:
  *
  * |---------------------------------------|--------------------------|