Make `LocalCache` not use `synchronized` to detect recursive loads.

Fixes #6851
Fixes #6845

RELNOTES=n/a
PiperOrigin-RevId: 588778069

4 files changed, 206 insertions, 14 deletions

diff --git a/android/guava-tests/test/com/google/common/cache/LocalCacheTest.java b/android/guava-tests/test/com/google/common/cache/LocalCacheTest.java
index 431c962f4..cd1d340d5 100644
--- a/android/guava-tests/test/com/google/common/cache/LocalCacheTest.java
+++ b/android/guava-tests/test/com/google/common/cache/LocalCacheTest.java
@@ -58,6 +58,7 @@ import com.google.common.testing.FakeTicker;
 import com.google.common.testing.NullPointerTester;
 import com.google.common.testing.SerializableTester;
 import com.google.common.testing.TestLogHandler;
+import com.google.common.util.concurrent.UncheckedExecutionException;
 import java.io.Serializable;
 import java.lang.ref.Reference;
 import java.lang.ref.ReferenceQueue;
@@ -2639,8 +2640,86 @@ public class LocalCacheTest extends TestCase {
     assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
   }
 
+  public void testLoadDifferentKeyInLoader() throws ExecutionException, InterruptedException {
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    String key1 = "key1";
+    String key2 = "key2";
+
+    assertEquals(
+        key2,
+        cache.get(
+            key1,
+            new CacheLoader<String, String>() {
+              @Override
+              public String load(String key) throws Exception {
+                return cache.get(key2, identityLoader()); // loads a different key, should work
+              }
+            }));
+  }
+
+  public void testRecursiveLoad() throws InterruptedException {
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    String key = "key";
+    CacheLoader<String, String> loader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(key, identityLoader()); // recursive load, this should fail
+          }
+        };
+    testLoadThrows(key, cache, loader);
+  }
+
+  public void testRecursiveLoadWithProxy() throws InterruptedException {
+    String key = "key";
+    String otherKey = "otherKey";
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    CacheLoader<String, String> loader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(
+                key,
+                identityLoader()); // recursive load (same as the initial one), this should fail
+          }
+        };
+    CacheLoader<String, String> proxyLoader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(otherKey, loader); // loads another key, is ok
+          }
+        };
+    testLoadThrows(key, cache, proxyLoader);
+  }
+
   // utility methods
 
+  private void testLoadThrows(
+      String key, LocalCache<String, String> cache, CacheLoader<String, String> loader)
+      throws InterruptedException {
+    CountDownLatch doneSignal = new CountDownLatch(1);
+    Thread thread =
+        new Thread(
+            () -> {
+              try {
+                cache.get(key, loader);
+              } catch (UncheckedExecutionException | ExecutionException e) {
+                doneSignal.countDown();
+              }
+            });
+    thread.start();
+
+    boolean done = doneSignal.await(1, TimeUnit.SECONDS);
+    if (!done) {
+      StringBuilder builder = new StringBuilder();
+      for (StackTraceElement trace : thread.getStackTrace()) {
+        builder.append("\tat ").append(trace).append('\n');
+      }
+      fail(builder.toString());
+    }
+  }
+
   /**
    * Returns an iterable containing all combinations of maximumSize, expireAfterAccess/Write,
    * weakKeys and weak/softValues.
diff --git a/android/guava/src/com/google/common/cache/LocalCache.java b/android/guava/src/com/google/common/cache/LocalCache.java
index f0a7699e0..6fb3945df 100644
--- a/android/guava/src/com/google/common/cache/LocalCache.java
+++ b/android/guava/src/com/google/common/cache/LocalCache.java
@@ -2180,12 +2180,7 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
 
       if (createNewEntry) {
         try {
-          // Synchronizes on the entry to allow failing fast when a recursive load is
-          // detected. This may be circumvented when an entry is copied, but will fail fast most
-          // of the time.
-          synchronized (e) {
-            return loadSync(key, hash, loadingValueReference, loader);
-          }
+          return loadSync(key, hash, loadingValueReference, loader);
         } finally {
           statsCounter.recordMisses(1);
         }
@@ -2201,7 +2196,22 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
         throw new AssertionError();
       }
 
-      checkState(!Thread.holdsLock(e), "Recursive load of: %s", key);
+      // As of this writing, the only prod ValueReference implementation for which isLoading() is
+      // true is LoadingValueReference. (Note, however, that not all LoadingValueReference instances
+      // have isLoading()==true: LoadingValueReference has a subclass, ComputingValueReference, for
+      // which isLoading() is false!) However, that might change, and we already have a *test*
+      // implementation for which it doesn't hold. So we check instanceof to be safe.
+      if (valueReference instanceof LoadingValueReference) {
+        // We check whether the thread that is loading the entry is our current thread, which would
+        // mean that we are both loading and waiting for the entry. In this case, we fail fast
+        // instead of deadlocking.
+        checkState(
+            ((LoadingValueReference<K, V>) valueReference).getLoadingThread()
+                != Thread.currentThread(),
+            "Recursive load of: %s",
+            key);
+      }
+
       // don't consider expiration as we're concurrent with loading
       try {
         V value = valueReference.waitForValue();
@@ -3427,6 +3437,8 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
     final SettableFuture<V> futureValue = SettableFuture.create();
     final Stopwatch stopwatch = Stopwatch.createUnstarted();
 
+    final Thread loadingThread;
+
     public LoadingValueReference() {
       this(LocalCache.<K, V>unset());
     }
@@ -3438,6 +3450,7 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
      */
     public LoadingValueReference(ValueReference<K, V> oldValue) {
       this.oldValue = oldValue;
+      this.loadingThread = Thread.currentThread();
     }
 
     @Override
@@ -3541,6 +3554,10 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
         ReferenceQueue<V> queue, @CheckForNull V value, ReferenceEntry<K, V> entry) {
       return this;
     }
+
+    Thread getLoadingThread() {
+      return this.loadingThread;
+    }
   }
 
   // Queues
diff --git a/guava-tests/test/com/google/common/cache/LocalCacheTest.java b/guava-tests/test/com/google/common/cache/LocalCacheTest.java
index 7cc67e840..a16c0ab37 100644
--- a/guava-tests/test/com/google/common/cache/LocalCacheTest.java
+++ b/guava-tests/test/com/google/common/cache/LocalCacheTest.java
@@ -58,6 +58,7 @@ import com.google.common.testing.FakeTicker;
 import com.google.common.testing.NullPointerTester;
 import com.google.common.testing.SerializableTester;
 import com.google.common.testing.TestLogHandler;
+import com.google.common.util.concurrent.UncheckedExecutionException;
 import java.io.Serializable;
 import java.lang.ref.Reference;
 import java.lang.ref.ReferenceQueue;
@@ -2688,8 +2689,86 @@ public class LocalCacheTest extends TestCase {
     assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
   }
 
+  public void testLoadDifferentKeyInLoader() throws ExecutionException, InterruptedException {
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    String key1 = "key1";
+    String key2 = "key2";
+
+    assertEquals(
+        key2,
+        cache.get(
+            key1,
+            new CacheLoader<String, String>() {
+              @Override
+              public String load(String key) throws Exception {
+                return cache.get(key2, identityLoader()); // loads a different key, should work
+              }
+            }));
+  }
+
+  public void testRecursiveLoad() throws InterruptedException {
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    String key = "key";
+    CacheLoader<String, String> loader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(key, identityLoader()); // recursive load, this should fail
+          }
+        };
+    testLoadThrows(key, cache, loader);
+  }
+
+  public void testRecursiveLoadWithProxy() throws InterruptedException {
+    String key = "key";
+    String otherKey = "otherKey";
+    LocalCache<String, String> cache = makeLocalCache(createCacheBuilder());
+    CacheLoader<String, String> loader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(
+                key,
+                identityLoader()); // recursive load (same as the initial one), this should fail
+          }
+        };
+    CacheLoader<String, String> proxyLoader =
+        new CacheLoader<String, String>() {
+          @Override
+          public String load(String key) throws Exception {
+            return cache.get(otherKey, loader); // loads another key, is ok
+          }
+        };
+    testLoadThrows(key, cache, proxyLoader);
+  }
+
   // utility methods
 
+  private void testLoadThrows(
+      String key, LocalCache<String, String> cache, CacheLoader<String, String> loader)
+      throws InterruptedException {
+    CountDownLatch doneSignal = new CountDownLatch(1);
+    Thread thread =
+        new Thread(
+            () -> {
+              try {
+                cache.get(key, loader);
+              } catch (UncheckedExecutionException | ExecutionException e) {
+                doneSignal.countDown();
+              }
+            });
+    thread.start();
+
+    boolean done = doneSignal.await(1, TimeUnit.SECONDS);
+    if (!done) {
+      StringBuilder builder = new StringBuilder();
+      for (StackTraceElement trace : thread.getStackTrace()) {
+        builder.append("\tat ").append(trace).append('\n');
+      }
+      fail(builder.toString());
+    }
+  }
+
   /**
    * Returns an iterable containing all combinations of maximumSize, expireAfterAccess/Write,
    * weakKeys and weak/softValues.
diff --git a/guava/src/com/google/common/cache/LocalCache.java b/guava/src/com/google/common/cache/LocalCache.java
index a38543dbb..dd3590357 100644
--- a/guava/src/com/google/common/cache/LocalCache.java
+++ b/guava/src/com/google/common/cache/LocalCache.java
@@ -2184,12 +2184,7 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
 
       if (createNewEntry) {
         try {
-          // Synchronizes on the entry to allow failing fast when a recursive load is
-          // detected. This may be circumvented when an entry is copied, but will fail fast most
-          // of the time.
-          synchronized (e) {
-            return loadSync(key, hash, loadingValueReference, loader);
-          }
+          return loadSync(key, hash, loadingValueReference, loader);
         } finally {
           statsCounter.recordMisses(1);
         }
@@ -2205,7 +2200,22 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
         throw new AssertionError();
       }
 
-      checkState(!Thread.holdsLock(e), "Recursive load of: %s", key);
+      // As of this writing, the only prod ValueReference implementation for which isLoading() is
+      // true is LoadingValueReference. (Note, however, that not all LoadingValueReference instances
+      // have isLoading()==true: LoadingValueReference has a subclass, ComputingValueReference, for
+      // which isLoading() is false!) However, that might change, and we already have a *test*
+      // implementation for which it doesn't hold. So we check instanceof to be safe.
+      if (valueReference instanceof LoadingValueReference) {
+        // We check whether the thread that is loading the entry is our current thread, which would
+        // mean that we are both loading and waiting for the entry. In this case, we fail fast
+        // instead of deadlocking.
+        checkState(
+            ((LoadingValueReference<K, V>) valueReference).getLoadingThread()
+                != Thread.currentThread(),
+            "Recursive load of: %s",
+            key);
+      }
+
       // don't consider expiration as we're concurrent with loading
       try {
         V value = valueReference.waitForValue();
@@ -3517,12 +3527,15 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
     final SettableFuture<V> futureValue = SettableFuture.create();
     final Stopwatch stopwatch = Stopwatch.createUnstarted();
 
+    final Thread loadingThread;
+
     public LoadingValueReference() {
       this(null);
     }
 
     public LoadingValueReference(@CheckForNull ValueReference<K, V> oldValue) {
       this.oldValue = (oldValue == null) ? LocalCache.unset() : oldValue;
+      this.loadingThread = Thread.currentThread();
     }
 
     @Override
@@ -3647,6 +3660,10 @@ class LocalCache<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>
         ReferenceQueue<V> queue, @CheckForNull V value, ReferenceEntry<K, V> entry) {
       return this;
     }
+
+    Thread getLoadingThread() {
+      return this.loadingThread;
+    }
   }
 
   static class ComputingValueReference<K, V> extends LoadingValueReference<K, V> {