Bug 1425462 Sprinkle some thread safety on the LRU Cache r=handyman
☠☠ backed out by eec4330cfdb3 ☠ ☠
authorTom Ritter <tom@mozilla.com>
Sat, 24 Feb 2018 08:21:15 -0600
changeset 762453 85896ea96faf2f55b4401674b1c469c7d9be513d
parent 762452 127b5d2e6779a4e94f7e939210a99b12e0c32f5f
child 762454 7d440e52e3a4862bfd981c0f0d09d13d03689581
push id101169
push userluca.greco@alcacoop.it
push dateFri, 02 Mar 2018 12:32:00 +0000
reviewershandyman
bugs1425462
milestone60.0a1
Bug 1425462 Sprinkle some thread safety on the LRU Cache r=handyman We use a mozilla:Mutex to avoid race conditions in the LRU Cache MozReview-Commit-ID: DyeK4RUnGhP
toolkit/components/resistfingerprinting/nsRFPService.cpp
--- 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:
  *
  * |---------------------------------------|--------------------------|