Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cycle detection in a multi-thread environment leads to OutOfMemoryError #1510

Closed
gvisco opened this issue Apr 8, 2021 · 7 comments
Closed

Comments

@gvisco
Copy link

gvisco commented Apr 8, 2021

In some scenario the cycle detection leads the application to an OutOfMemoryError.
Specifically, this seems to happen if:

  • At least one object O involved in a cyclic dependency is a Singleton
  • O has not been initialized yet
  • Multiple threads require the injection of O at the same time

The following test reproduces the issue (not always but often)

import java.util.concurrent.CountDownLatch;

import org.junit.Test;

import com.google.inject.AbstractModule;
import com.google.inject.Guice;
import com.google.inject.Inject;
import com.google.inject.Injector;
import com.google.inject.Singleton;

public class GuiceCircularDependenciesIT extends AbstractModule {

    static interface Store {
        void sell();
    }
    
    static interface Customer {
        void buy();
    }
    
    static class StoreImpl implements Store {
        private final Customer customer;

        @Inject public StoreImpl(Customer customer) {
            this.customer = customer;
        }

        @Override
        public void sell() { }
    }

    static class CustomerImpl implements Customer {

        private Store store;

        @Inject public CustomerImpl(Store store) {
            this.store = store;
        }
        
        @Override
        public void buy() {
            store.sell();
        }
    }
    
    @Override
    protected void configure() {
        bind(Store.class).to(StoreImpl.class);
        bind(Customer.class).to(CustomerImpl.class).in(Singleton.class);
    }
    
    @Test
    public void testCircularDependencies() {
        for (int j = 0; j < 100; ++j) {
            Injector injector = Guice.createInjector(this);
            CountDownLatch latch = new CountDownLatch(8);
            for (int i = 0; i < 8; ++i) {
                Thread thread = new Thread(() -> {
                    try {
                        Customer instance = injector.getInstance(Customer.class);
                        instance.buy();
                    } catch (Exception e) {
                        System.out.println(e);
                    } finally {
                        latch.countDown();
                    }
                });
                thread.setDaemon(true);
                thread.start();
            }
            try {
                latch.await();
                System.out.println("DONE: " + j);
            } catch (InterruptedException e) {
            }
        }

    }
}

a sample output, when the issue occurs, is

DONE: 0
DONE: 1
DONE: 2
DONE: 3
DONE: 4
Exception in thread "Thread-47" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3689)
    at java.base/java.util.ArrayList.grow(ArrayList.java:238)
    at java.base/java.util.ArrayList.grow(ArrayList.java:243)
    at java.base/java.util.ArrayList.add(ArrayList.java:486)
    at java.base/java.util.ArrayList.add(ArrayList.java:499)
    at com.google.common.collect.AbstractMapBasedMultimap.put(AbstractMapBasedMultimap.java:195)
    at com.google.common.collect.AbstractListMultimap.put(AbstractListMultimap.java:115)
    at com.google.inject.internal.CycleDetectingLock$CycleDetectingLockFactory$ReentrantCycleDetectingLock.addAllLockIdsAfter(CycleDetectingLock.java:290)
    at com.google.inject.internal.CycleDetectingLock$CycleDetectingLockFactory$ReentrantCycleDetectingLock.detectPotentialLocksCycle(CycleDetectingLock.java:257)
    at com.google.inject.internal.CycleDetectingLock$CycleDetectingLockFactory$ReentrantCycleDetectingLock.lockOrDetectPotentialLocksCycle(CycleDetectingLock.java:149)
    at com.google.inject.internal.SingletonScope$1.get(SingletonScope.java:159)
    at com.google.inject.internal.InternalFactoryToProviderAdapter.get(InternalFactoryToProviderAdapter.java:39)
    at com.google.inject.internal.InjectorImpl$1.get(InjectorImpl.java:1094)
    at com.google.inject.internal.InjectorImpl.getInstance(InjectorImpl.java:1131)
    at foo.GuiceCircularDependenciesIT.lambda$0(GuiceCircularDependenciesIT.java:63)
    at foo.GuiceCircularDependenciesIT$$Lambda$30/0x00000008000b9040.run(Unknown Source)
    at java.base/java.lang.Thread.run(Thread.java:834)

I'm running version 4.2.3

Please note that, unless I'm doing something wrong, this makes Guice default settings harmful if you are running it in a multi-thread application.
As a matter of fact, the only way to fix the code above is to remove the cyclic dependency, and with the circular proxy feature enabled (and it is by default) it becomes harder to spot it. Nobody (running a multi-thread application) reasonably wants to take the risk of getting an OutOfMemory Error - which is typically fatal for the application - based on race conditions - which can be hard to find while testing.
Most likely, as long as the bug is there, whoever runs a multi-thread application may want to disable the feature completely, for example calling Binder::disableCircularProxies(), to override the default behavior.

@gvisco gvisco changed the title Cycle detection in a multi-threaded environment leads to OutOfMemoryError Cycle detection in a multi-thread environment leads to OutOfMemoryError Apr 12, 2021
@cdietrich
Copy link

we are also affected by this issue

@cdietrich
Copy link

any update here?

@trancexpress
Copy link

Using the reproducer from the description, bisected this to:

5e6c933

This is the first commit I see the OOM with, I imagine something in the changes in com.google.inject.internal.SingletonScope is causing the OOM. I can do partial reverts, to not see the OOM:

diff --git a/core/src/com/google/inject/internal/InheritingState.java b/core/src/com/google/inject/internal/InheritingState.java
index 18363f483..db6a7a67a 100644
--- a/core/src/com/google/inject/internal/InheritingState.java
+++ b/core/src/com/google/inject/internal/InheritingState.java
@@ -60,10 +60,13 @@ final class InheritingState implements State {
   private final List<ModuleAnnotatedMethodScannerBinding> scannerBindings = Lists.newArrayList();
   private final WeakKeySet blacklistedKeys;
   private final Object lock;
+  private final Object singletonCreationLock;
 
   InheritingState(State parent) {
     this.parent = checkNotNull(parent, "parent");
     this.lock = (parent == State.NONE) ? this : parent.lock();
+    this.singletonCreationLock =
+        (parent == State.NONE) ? new Object() : parent.singletonCreationLock();
     this.blacklistedKeys = new WeakKeySet(lock);
   }
 
@@ -187,6 +190,10 @@ final class InheritingState implements State {
     return lock;
   }
 
+  public Object singletonCreationLock() {
+    return singletonCreationLock;
+  }
+
   public Map<Class<? extends Annotation>, Scope> getScopes() {
     ImmutableMap.Builder<Class<? extends Annotation>, Scope> builder = ImmutableMap.builder();
     for (Map.Entry<Class<? extends Annotation>, ScopeBinding> entry : scopes.entrySet()) {
diff --git a/core/src/com/google/inject/internal/Scoping.java b/core/src/com/google/inject/internal/Scoping.java
index 334aaef40..10afcba34 100644
--- a/core/src/com/google/inject/internal/Scoping.java
+++ b/core/src/com/google/inject/internal/Scoping.java
@@ -239,9 +239,14 @@ public abstract class Scoping {
 
     Scope scope = scoping.getScopeInstance();
 
-    Provider<T> scoped
-        = scope.scope(key, new ProviderToInternalFactoryAdapter<T>(injector, creator));
-    return new InternalFactoryToProviderAdapter<T>(scoped, source);
+    try {
+      SingletonScope.singletonCreationPerRootInjectorLock.set(injector.state.singletonCreationLock());
+      Provider<T> scoped
+          = scope.scope(key, new ProviderToInternalFactoryAdapter<T>(injector, creator));
+      return new InternalFactoryToProviderAdapter<T>(scoped, source);
+    } finally {
+      SingletonScope.singletonCreationPerRootInjectorLock.set(null);
+    }
   }
 
   /**
diff --git a/core/src/com/google/inject/internal/SingletonScope.java b/core/src/com/google/inject/internal/SingletonScope.java
index fe6287aa8..e98a0303e 100644
--- a/core/src/com/google/inject/internal/SingletonScope.java
+++ b/core/src/com/google/inject/internal/SingletonScope.java
@@ -1,73 +1,16 @@
 package com.google.inject.internal;
 
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ListMultimap;
-import com.google.common.collect.Lists;
-import com.google.common.collect.Maps;
 import com.google.inject.Injector;
 import com.google.inject.Key;
+import com.google.inject.OutOfScopeException;
 import com.google.inject.Provider;
 import com.google.inject.ProvisionException;
 import com.google.inject.Scope;
 import com.google.inject.Scopes;
 import com.google.inject.Singleton;
-import com.google.inject.internal.CycleDetectingLock.CycleDetectingLockFactory;
-import com.google.inject.spi.Dependency;
-import com.google.inject.spi.DependencyAndSource;
-import com.google.inject.spi.Message;
-
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
 
 /**
  * One instance per {@link Injector}. Also see {@code @}{@link Singleton}.
- *
- * Introduction from the author:
- * Implementation of this class seems unreasonably complicated at the first sight.
- * I fully agree with you, that the beast below is very complex
- * and it's hard to reason on how does it work or not.
- * Still I want to assure you that hundreds(?) of hours were thrown
- * into making this code simple, while still maintaining Singleton contract.
- *
- * Anyway, why is it so complex? Singleton scope does not seem to be that unique.
- * 1) Guice has never truly expected to be used in multi threading environment
- *    with many Injectors working alongside each other. There is almost no
- *    code with Guice that propagates state between threads. And Singleton
- *    scope is The exception.
- * 2) Guice supports circular dependencies and thus manages proxy objects.
- *    There is no interface that allows user defined Scopes to create proxies,
- *    it is expected to be done by Guice. Singleton scope needs to be
- *    able to detect circular dependencies spanning several threads,
- *    therefore Singleton scope needs to be able to create these proxies.
- * 3) To make things worse, Guice has a very tricky definition for a binding
- *    resolution when Injectors are in in a parent/child relationship.
- *    And Scope does not have access to this information by design,
- *    the only real action that Scope can do is to call or not to call a creator.
- * 4) There is no readily available code in Guice that can detect a potential
- *    deadlock, and no code for handling dependency cycles spanning several threads.
- *    This is significantly harder as all the dependencies in a thread at runtime
- *    can be represented with a list, where in a multi threaded environment
- *    we have more complex dependency trees.
- * 5) Guice has a pretty strong contract regarding Garbage Collection,
- *    which often prevents us from linking objects directly.
- *    So simple domain specific code can not be written and intermediary
- *    id objects need to be managed.
- * 6) Guice is relatively fast and we should not make things worse.
- *    We're trying our best to optimize synchronization for speed and memory.
- *    Happy path should be almost as fast as in a single threaded solution
- *    and should not take much more memory.
- * 7) Error message generation in Guice was not meant to be used like this and to work around
- *    its APIs we need a lot of code. Additional complexity comes from inherent data races
- *    as message is only generated when failure occurs on proxy object generation.
- * Things get ugly pretty fast.
- *
- * @see #scope(Key, Provider)
- * @see CycleDetectingLock
- *
- * @author timofeyb (Timothy Basanov)
  */
 public class SingletonScope implements Scope {
 
@@ -75,259 +18,70 @@ public class SingletonScope implements Scope {
   private static final Object NULL = new Object();
 
   /**
-   * Allows us to detect when circular proxies are necessary. It's only used during singleton
-   * instance initialization, after initialization direct access through volatile field is used.
+   * Lock to use for new instances creation. This allows a per-root-Injector singleton lock,
+   * instead of a global lock across the JVM. Is set only during call to {@link #scope}.
    *
-   * NB: Factory uses {@link Key}s as a user locks ids, different injectors can
-   * share them. Cycles are detected properly as cycle detection does not rely on user locks ids,
-   * but error message generated could be less than ideal.
+   * This is necessary because users have coded to a single {@link Scopes#SINGLETON} instance, 
+   * and we cannot change that.  Additionally, we can't reference the injector from a Key or
+   * Provider (the only variables available to the {@link #scope} method).  Therefore, we rely
+   * on the injector implementation to explicitly set/unset the lock surrounding
+   * creation of the Provider the scope creates.
    *
-   * TODO(user): we may use one factory per injector tree for optimization reasons
+   * @see {@link Scoping#scope(Key, InjectorImpl, InternalFactory, Object, Scoping)} for details.
    */
-  private static final CycleDetectingLockFactory<Key<?>> cycleDetectingLockFactory =
-      new CycleDetectingLockFactory<Key<?>>();
+  static final ThreadLocal<Object> singletonCreationPerRootInjectorLock =
+      new ThreadLocal<Object>();
 
-  /**
-   * Provides singleton scope with the following properties:
-   * - creates no more than one instance per Key as a creator is used no more than once,
-   * - result is cached and returned quickly on subsequent calls,
-   * - exception in a creator is not treated as instance creation and is not cached,
-   * - creates singletons in parallel whenever possible,
-   * - waits for dependent singletons to be created even across threads and when dependencies
-   *   are shared as long as no circular dependencies are detected,
-   * - returns circular proxy only when circular dependencies are detected,
-   * - aside from that, blocking synchronization is only used for proxy creation and initialization,
-   * @see CycleDetectingLockFactory
-   */
   public <T> Provider<T> scope(final Key<T> key, final Provider<T> creator) {
-    /**
-     * Locking strategy:
-     * - volatile instance: double-checked locking for quick exit when scope is initialized,
-     * - constructionContext: manipulations with proxies list or instance initialization
-     * - creationLock: singleton instance creation,
-     *   -- allows to guarantee only one instance per singleton,
-     *   -- special type of a lock, that prevents potential deadlocks,
-     *   -- guards constructionContext for all operations except proxy creation
-     */
+    // lock is referenced from anonymous class instance
+    final Object rootInjectorLock = singletonCreationPerRootInjectorLock.get();
+    if (rootInjectorLock == null) {
+      throw new OutOfScopeException("Singleton scope should only be used from Injector");
+    }
     return new Provider<T>() {
-      /**
+      /*
        * The lazily initialized singleton instance. Once set, this will either have type T or will
-       * be equal to NULL. Would never be reset to null.
-       */
-      volatile Object instance;
-
-      /**
-       * Circular proxies are used when potential deadlocks are detected. Guarded by itself.
-       * ConstructionContext is not thread-safe, so each call should be synchronized.
+       * be equal to NULL.
        */
-      final ConstructionContext<T> constructionContext = new ConstructionContext<T>();
-
-      /** For each binding there is a separate lock that we hold during object creation. */
-      final CycleDetectingLock<Key<?>> creationLock = cycleDetectingLockFactory.create(key);
+      private volatile Object instance;
 
+      // DCL on a volatile is safe as of Java 5, which we obviously require.
       @SuppressWarnings("DoubleCheckedLocking")
       public T get() {
-        // cache volatile variable for the usual case of already initialized object
-        final Object initialInstance = instance;
-        if (initialInstance == null) {
-          // instance is not initialized yet
-
-          // acquire lock for current binding to initialize an instance
-          final ListMultimap<Long, Key<?>> locksCycle =
-              creationLock.lockOrDetectPotentialLocksCycle();
-          if (locksCycle.isEmpty()) {
-            // this thread now owns creation of an instance
-            try {
-              // intentionally reread volatile variable to prevent double initialization
-              if (instance == null) {
-                // creator throwing an exception can cause circular proxies created in
-                // different thread to never be resolved, just a warning
-                T provided = creator.get();
-                Object providedNotNull = provided == null ? NULL : provided;
-
-                // scope called recursively can initialize instance as a side effect
-                if (instance == null) {
-                  // instance is still not initialized, se we can proceed
-
-                  // don't remember proxies created by Guice on circular dependency
-                  // detection within the same thread; they are not real instances to cache
-                  if (Scopes.isCircularProxy(provided)) {
-                    return provided;
-                  }
-
-                  synchronized (constructionContext) {
-                    // guarantee thread-safety for instance and proxies initialization
-                    instance = providedNotNull;
-                    constructionContext.setProxyDelegates(provided);
-                  }
-                } else {
-                  // safety assert in case instance was initialized
-                  Preconditions.checkState(instance == providedNotNull,
-                      "Singleton is called recursively returning different results");
-                }
+        if (instance == null) {
+          /*
+           * Use a pretty coarse lock. We don't want to run into deadlocks
+           * when two threads try to load circularly-dependent objects.
+           * Maybe one of these days we will identify independent graphs of
+           * objects and offer to load them in parallel.
+           *
+           * This block is re-entrant for circular dependencies.
+           */
+          synchronized (rootInjectorLock) {
+            if (instance == null) {
+              T provided = creator.get();
+
+              // don't remember proxies; these exist only to serve circular dependencies
+              if (Scopes.isCircularProxy(provided)) {
+                return provided;
               }
-            } catch (RuntimeException e) {
-              // something went wrong, be sure to clean a construction context
-              // this helps to prevent potential memory leaks in circular proxies list
-              synchronized (constructionContext) {
-                constructionContext.finishConstruction();
-              }
-              throw e;
-            } finally {
-              // always release our creation lock, even on failures
-              creationLock.unlock();
-            }
-          } else {
-            // potential deadlock detected, creation lock is not taken by this thread
-            synchronized (constructionContext) {
-              // guarantee thread-safety for instance and proxies initialization
-              if (instance == null) {
-                // InjectorImpl.callInContext() sets this context when scope is called from Guice
-                Map<Thread, InternalContext> globalInternalContext =
-                    InjectorImpl.getGlobalInternalContext();
-                InternalContext internalContext = globalInternalContext.get(Thread.currentThread());
 
-                // creating a proxy to satisfy circular dependency across several threads
-                Dependency<?> dependency = Preconditions.checkNotNull(
-                    internalContext.getDependency(),
-                    "globalInternalContext.get(currentThread()).getDependency()");
-                Class<?> rawType = dependency.getKey().getTypeLiteral().getRawType();
-
-                try {
-                  @SuppressWarnings("unchecked")
-                  T proxy = (T) constructionContext.createProxy(
-                      new Errors(), internalContext.getInjectorOptions(), rawType);
-                  return proxy;
-                } catch (ErrorsException e) {
-                  // best effort to create a rich error message
-                  List<Message> exceptionErrorMessages = e.getErrors().getMessages();
-                  // we expect an error thrown
-                  Preconditions.checkState(exceptionErrorMessages.size() == 1);
-                  // explicitly copy the map to guarantee iteration correctness
-                  // it's ok to have a data race with other threads that are locked
-                  Message cycleDependenciesMessage = createCycleDependenciesMessage(
-                      ImmutableMap.copyOf(globalInternalContext),
-                      locksCycle,
-                      exceptionErrorMessages.get(0));
-                  // adding stack trace generated by us in addition to a standard one
-                  throw new ProvisionException(ImmutableList.of(
-                      cycleDependenciesMessage, exceptionErrorMessages.get(0)));
-                }
+              Object providedOrSentinel = (provided == null) ? NULL : provided;
+              if (instance != null && instance != providedOrSentinel) {
+                throw new ProvisionException(
+                    "Provider was reentrant while creating a singleton");
               }
-            }
-          }
-          // at this point we're sure that singleton was initialized,
-          // reread volatile variable to catch all corner cases
 
-          // caching volatile variable to minimize number of reads performed
-          final Object initializedInstance = instance;
-          Preconditions.checkState(initializedInstance != null,
-              "Internal error: Singleton is not initialized contrary to our expectations");
-          @SuppressWarnings("unchecked")
-          T initializedTypedInstance = (T) initializedInstance;
-          return initializedInstance == NULL ? null : initializedTypedInstance;
-        } else {
-          // singleton is already initialized and local cache can be used
-          @SuppressWarnings("unchecked")
-          T typedInitialIntance = (T) initialInstance;
-          return initialInstance == NULL ? null : typedInitialIntance;
-        }
-      }
-
-      /**
-       * Helper method to create beautiful and rich error descriptions. Best effort and slow.
-       * Tries its best to provide dependency information from injectors currently available
-       * in a global internal context.
-       *
-       * <p>The main thing being done is creating a list of Dependencies involved into
-       * lock cycle across all the threads involved. This is a structure we're creating:
-       * <pre>
-       * { Current Thread, C.class, B.class, Other Thread, B.class, C.class, Current Thread }
-       * To be inserted in the beginning by Guice: { A.class, B.class, C.class }
-       * </pre>
-       * When we're calling Guice to create A and it fails in the deadlock while trying to
-       * create C, which is being created by another thread, which waits for B. List would
-       * be reversed before printing it to the end user.
-       */
-      private Message createCycleDependenciesMessage(
-          Map<Thread, InternalContext> globalInternalContext,
-          ListMultimap<Long, Key<?>> locksCycle,
-          Message proxyCreationError) {
-        // this is the main thing that we'll show in an error message,
-        // current thread is populate by Guice
-        List<Object> sourcesCycle = Lists.newArrayList();
-        sourcesCycle.add(Thread.currentThread());
-        // temp map to speed up look ups
-        Map<Long, Thread> threadById = Maps.newHashMap();
-        for (Thread thread : globalInternalContext.keySet()) {
-          threadById.put(thread.getId(), thread);
-        }
-        for (long lockedThreadId : locksCycle.keySet()) {
-          Thread lockedThread = threadById.get(lockedThreadId);
-          List<Key<?>> lockedKeys = Collections.unmodifiableList(locksCycle.get(lockedThreadId));
-          if (lockedThread == null) {
-            // thread in a lock cycle is already terminated
-            continue;
-          }
-          List<DependencyAndSource> dependencyChain = null;
-          boolean allLockedKeysAreFoundInDependencies = false;
-          // thread in a cycle is still present
-          InternalContext lockedThreadInternalContext = globalInternalContext.get(lockedThread);
-          if (lockedThreadInternalContext != null) {
-            dependencyChain = lockedThreadInternalContext.getDependencyChain();
-
-            // check that all of the keys are still present in dependency chain in order
-            List<Key<?>> lockedKeysToFind = Lists.newLinkedList(lockedKeys);
-            // check stack trace of the thread
-            for (DependencyAndSource d : dependencyChain) {
-              Dependency<?> dependency = d.getDependency();
-              if (dependency == null) {
-                continue;
-              }
-              if (dependency.getKey().equals(lockedKeysToFind.get(0))) {
-                lockedKeysToFind.remove(0);
-                if (lockedKeysToFind.isEmpty()) {
-                  // everything is found!
-                  allLockedKeysAreFoundInDependencies = true;
-                  break;
-                }
-              }
+              instance = providedOrSentinel;
             }
           }
-          if (allLockedKeysAreFoundInDependencies) {
-            // all keys are present in a dependency chain of a thread's last injector,
-            // highly likely that we just have discovered a dependency
-            // chain that is part of a lock cycle starting with the first lock owned
-            Key<?> firstLockedKey = lockedKeys.get(0);
-            boolean firstLockedKeyFound = false;
-            for (DependencyAndSource d : dependencyChain) {
-              Dependency<?> dependency = d.getDependency();
-              if (dependency == null) {
-                continue;
-              }
-              if (firstLockedKeyFound) {
-                sourcesCycle.add(dependency);
-                sourcesCycle.add(d.getBindingSource());
-              } else if (dependency.getKey().equals(firstLockedKey)) {
-                firstLockedKeyFound = true;
-                // for the very first one found we don't care why, so no dependency is added
-                sourcesCycle.add(d.getBindingSource());
-              }
-            }
-          } else {
-            // something went wrong and not all keys are present in a state of an injector
-            // that was used last for a current thread.
-            // let's add all keys we're aware of, still better than nothing
-            sourcesCycle.addAll(lockedKeys);
-          }
-          // mentions that a tread is a part of a cycle
-          sourcesCycle.add(lockedThread);
         }
-        return new Message(
-            sourcesCycle,
-            String.format("Encountered circular dependency spanning several threads. %s",
-                proxyCreationError.getMessage()),
-            null);
+
+        Object localInstance = instance;
+        // This is safe because instance has type T or is equal to NULL
+        @SuppressWarnings("unchecked")
+        T returnedInstance = (localInstance != NULL) ? (T) localInstance : null;
+        return returnedInstance;
       }
 
       @Override
diff --git a/core/src/com/google/inject/internal/State.java b/core/src/com/google/inject/internal/State.java
index 32c2da617..8a828f2ee 100644
--- a/core/src/com/google/inject/internal/State.java
+++ b/core/src/com/google/inject/internal/State.java
@@ -202,6 +202,12 @@ interface State {
    */
   Object lock();
 
+  /**
+   * Returns the shared lock for all injector's singletons. This is a low-granularity lock
+   * to guarantee singleton creation semantics.
+   */
+  Object singletonCreationLock();
+
   /**
    * Returns all the scope bindings at this level and parent levels.
    */

@trancexpress
Copy link

Hi @sameb ,

I see you are still active and were part of the original PR that caused this OOM: #915

Could you take a look here? Is there maybe some oversight, that causes an endless loop in ReentrantCycleDetectingLock.detectPotentialLocksCycle()? I'll try to check myself but this will likely take a while.

Best regards and thanks,
Simeon Andreev

trancexpress added a commit to trancexpress/guice that referenced this issue Jun 10, 2022
This change prevents an endless loop in:
ReentrantCycleDetectingLock.addAllLockIdsAfter()

For reasons that are not yet clear, according to
CycleDetectingLockFactory.locksOwnedByThread and
ReentrantCycleDetectingLock.lockOwnerThread, a thread both owns a lock
and waits on that same lock. This leads to an endless loop in the cycle
detection.

The change adds a workaround, forcing the cycle detection to exit if the
above condition is met.
trancexpress added a commit to trancexpress/guice that referenced this issue Jun 10, 2022
…detectPotentialLocksCycle()

Due to how code in ReentrantCycleDetectingLock.lockOrDetectPotentialLocksCycle() is synchronized,
its possible for a thread to both own/hold a lock (according to ReentrantCycleDetectingLock.lockOwnerThread)
and wait on the same lock (according to CycleDetectingLock.lockThreadIsWaitingOn).
In this state, if another thread tries to hold the same lock an endless loop will occur when calling detectPotentialLocksCycle().

The change adds a workaround, forcing the cycle detection to exit if the above condition is met.

Workaround for: google#1510
trancexpress added a commit to trancexpress/guice that referenced this issue Jun 10, 2022
…detectPotentialLocksCycle()

Due to how code in ReentrantCycleDetectingLock.lockOrDetectPotentialLocksCycle() is synchronized,
its possible for a thread to both own/hold a lock (according to ReentrantCycleDetectingLock.lockOwnerThread)
and wait on the same lock (according to CycleDetectingLock.lockThreadIsWaitingOn).
In this state, if another thread tries to hold the same lock an endless loop will occur when calling detectPotentialLocksCycle().

With this change detectPotentialLocksCycle() removes the lock owning thread from
ReentrantCycleDetectingLock.lockOwnerThread, before chekcing for lock cycles.
This prevents the endless loop during cycle detection.

Fix for: google#1510
trancexpress added a commit to trancexpress/guice that referenced this issue Jun 11, 2022
…detectPotentialLocksCycle()

Due to how code in ReentrantCycleDetectingLock.lockOrDetectPotentialLocksCycle() is synchronized,
its possible for a thread to both own/hold a lock (according to ReentrantCycleDetectingLock.lockOwnerThread)
and wait on the same lock (according to CycleDetectingLock.lockThreadIsWaitingOn).
In this state, if another thread tries to hold the same lock an endless loop will occur when calling detectPotentialLocksCycle().

With this change detectPotentialLocksCycle() removes the lock owning thread from
ReentrantCycleDetectingLock.lockOwnerThread,
if it detects that "this" lock is both waited on and owned by the same thread.
This prevents the endless loop during cycle detection.

Fix for: google#1510
copybara-service bot pushed a commit that referenced this issue Apr 18, 2023
…would previously fail:

 * T1: Enter `lockOrDetectPotentialLocksCycle`:
    - Lock CAF.class, add itself to `lockThreadIsWaitingOn`, unlock CAF.class
    - Lock the cycle detecting lock (CDL)
    - Lock CAF.class, mark itself as `lockOwnerThread`, remove itself from `lockThreadIsWaitingOn`
    - Exit `lockOrDetectPotentialLocksCycle`
 * T1: Re-enter `lockOrDetectPotentialLocksCycle`:
    - Lock CAF.class, add itself to `lockThreadIsWaitingOn`, unlock CAF.class
 T2: Enter `lockOrDetectPotentialLocksCycle`
    - Lock CAF.class, invoke `detectPotentialLocksCycle`.

At this point, `detectPotentialLocksCycle` will now loop forever, because the `lockOwnerThread` is also in `lockThreadIsWaitingOn`. During the course of looping forever, it will OOM, because it's building up an in-memory structure of what it thinks are cycles.

The solution is to avoid the re-entrant T1 from adding itself to `lockThreadIsWaitingOn` if it's already the `lockOwnerThread`. It's guaranteed that it won't relinquish the lock concurrently, because it's the exact same thread that owns it.

Fixes #1635 and Fixes #1510

PiperOrigin-RevId: 524376697
copybara-service bot pushed a commit that referenced this issue Apr 18, 2023
…would previously fail:

 * T1: Enter `lockOrDetectPotentialLocksCycle`:
    - Lock CAF.class, add itself to `lockThreadIsWaitingOn`, unlock CAF.class
    - Lock the cycle detecting lock (CDL)
    - Lock CAF.class, mark itself as `lockOwnerThread`, remove itself from `lockThreadIsWaitingOn`
    - Exit `lockOrDetectPotentialLocksCycle`
 * T1: Re-enter `lockOrDetectPotentialLocksCycle`:
    - Lock CAF.class, add itself to `lockThreadIsWaitingOn`, unlock CAF.class
 T2: Enter `lockOrDetectPotentialLocksCycle`
    - Lock CAF.class, invoke `detectPotentialLocksCycle`.

At this point, `detectPotentialLocksCycle` will now loop forever, because the `lockOwnerThread` is also in `lockThreadIsWaitingOn`. During the course of looping forever, it will OOM, because it's building up an in-memory structure of what it thinks are cycles.

The solution is to avoid the re-entrant T1 from adding itself to `lockThreadIsWaitingOn` if it's already the `lockOwnerThread`. It's guaranteed that it won't relinquish the lock concurrently, because it's the exact same thread that owns it.

Fixes #1635 and Fixes #1510

PiperOrigin-RevId: 524376697
@trancexpress
Copy link

Thanks for fixing this!

@sameb
Copy link
Member

sameb commented Apr 18, 2023

You're welcome. Sorry this was left unfixed for so long. I'm spending this & next week cleaning up Guice's PR and issue backlog, as a tribute to @crazybob.

@trancexpress
Copy link

I'm spending this & next week cleaning up Guice's PR and issue backlog, as a tribute to @crazybob.

I did not know, this is very saddening :(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
4 participants