Repository: mockito/mockito
Issue: Excessive locking in TypeCachingBytecodeGenerator#BOOTSTRAP_LOCK

The TypeCachingBytecodeGenerator#BOOTSTRAP_LOCK is resulting in excessive BLOCKED threads when running several thousand tests concurrently.  Byte-buddy TypeCache's findOrInsert without monitor seems to handle concurrency. Is this global lock needed ?

Mockito-Inline 4.10, Byte-Buddy 1.12.19

`
"ForkJoinPool-1-worker-84" Id=115 RUNNABLE (daemon=TRUE)
	at java.base@17.0.4/java.lang.StringLatin1.replace(StringLatin1.java:322)
	at java.base@17.0.4/java.lang.String.replace(String.java:2806)
	at app//net.bytebuddy.jar.asm.Type.getInternalName(Type.java:510)
	at app//net.bytebuddy.jar.asm.Type.appendDescriptor(Type.java:644)
	at app//net.bytebuddy.jar.asm.Type.getMethodDescriptor(Type.java:585)
	at app//net.bytebuddy.description.method.MethodDescription$ForLoadedMethod.getDescriptor(MethodDescription.java:1288)
	at app//net.bytebuddy.asm.Advice$Dispatcher$Inlining$Resolved$AdviceMethodInliner.visitMethod(Advice.java:8400)
	at app//net.bytebuddy.jar.asm.ClassReader.readMethod(ClassReader.java:1353)
	at app//net.bytebuddy.jar.asm.ClassReader.accept(ClassReader.java:744)
	at app//net.bytebuddy.jar.asm.ClassReader.accept(ClassReader.java:424)
	at app//net.bytebuddy.asm.Advice$Dispatcher$Inlining$Resolved$AdviceMethodInliner.apply(Advice.java:8394)
	at app//net.bytebuddy.asm.Advice$AdviceVisitor$WithExitAdvice.onUserEnd(Advice.java:10904)
	at app//net.bytebuddy.asm.Advice$AdviceVisitor.visitMaxs(Advice.java:10683)
	at app//net.bytebuddy.jar.asm.ClassReader.readCode(ClassReader.java:2665)
	at app//net.bytebuddy.jar.asm.ClassReader.readMethod(ClassReader.java:1514)
	at app//net.bytebuddy.jar.asm.ClassReader.accept(ClassReader.java:744)
	at app//net.bytebuddy.jar.asm.ClassReader.accept(ClassReader.java:424)
	at app//net.bytebuddy.dynamic.scaffold.TypeWriter$Default$ForInlining.create(TypeWriter.java:4014)
	at app//net.bytebuddy.dynamic.scaffold.TypeWriter$Default.make(TypeWriter.java:2224)
	at app//net.bytebuddy.dynamic.DynamicType$Builder$AbstractBase$UsingTypeWriter.make(DynamicType.java:4050)
	at app//net.bytebuddy.dynamic.DynamicType$Builder$AbstractBase.make(DynamicType.java:3734)
	at app//org.mockito.internal.creation.bytebuddy.InlineBytecodeGenerator.transform(InlineBytecodeGenerator.java:401)
	at java.instrument@17.0.4/java.lang.instrument.ClassFileTransformer.transform(ClassFileTransformer.java:244)
	at java.instrument@17.0.4/sun.instrument.TransformerManager.transform(TransformerManager.java:188)
	at java.instrument@17.0.4/sun.instrument.InstrumentationImpl.transform(InstrumentationImpl.java:541)
	at java.instrument@17.0.4/sun.instrument.InstrumentationImpl.retransformClasses0(Native Method)
	at java.instrument@17.0.4/sun.instrument.InstrumentationImpl.retransformClasses(InstrumentationImpl.java:169)
	at app//org.mockito.internal.creation.bytebuddy.InlineBytecodeGenerator.triggerRetransformation(InlineBytecodeGenerator.java:280)
	at app//org.mockito.internal.creation.bytebuddy.InlineBytecodeGenerator.mockClass(InlineBytecodeGenerator.java:217)
	- locked <0x730e33e8> (a org.mockito.internal.creation.bytebuddy.InlineBytecodeGenerator)
	at app//org.mockito.internal.creation.bytebuddy.TypeCachingBytecodeGenerator.lambda$mockClass$0(TypeCachingBytecodeGenerator.java:47)
	at app//org.mockito.internal.creation.bytebuddy.TypeCachingBytecodeGenerator$$Lambda$895/0x0000000801aeaf98.call(Unknown Source)
	at app//net.bytebuddy.TypeCache.findOrInsert(TypeCache.java:168)
	at app//net.bytebuddy.TypeCache$WithInlineExpunction.findOrInsert(TypeCache.java:399)
	at app//net.bytebuddy.TypeCache.findOrInsert(TypeCache.java:190)
	- locked <0x62f72614> (a java.lang.Object)
	at app//net.bytebuddy.TypeCache$WithInlineExpunction.findOrInsert(TypeCache.java:410)
`

`
"ForkJoinPool-1-worker-51" Id=82 BLOCKED on java.lang.Object@62f72614 owned by "ForkJoinPool-1-worker-84" Id=115115 (daemon=TRUE)
	at app//net.bytebuddy.TypeCache.findOrInsert(TypeCache.java:189)
	at app//net.bytebuddy.TypeCache$WithInlineExpunction.findOrInsert(TypeCache.java:410)
	at app//org.mockito.internal.creation.bytebuddy.TypeCachingBytecodeGenerator.mockClass(TypeCachingBytecodeGenerator.java:40)
	at app//org.mockito.internal.creation.bytebuddy.InlineDelegateByteBuddyMockMaker.createMockType(InlineDelegateByteBuddyMockMaker.java:396)
	at app//org.mockito.internal.creation.bytebuddy.InlineDelegateByteBuddyMockMaker.doCreateMock(InlineDelegateByteBuddyMockMaker.java:355)
	at app//org.mockito.internal.creation.bytebuddy.InlineDelegateByteBuddyMockMaker.createMock(InlineDelegateByteBuddyMockMaker.java:334)
	at app//org.mockito.internal.creation.bytebuddy.InlineByteBuddyMockMaker.createMock(InlineByteBuddyMockMaker.java:56)
	at app//org.mockito.internal.util.MockUtil.createMock(MockUtil.java:99)
`

check that

 - [X] The mockito message in the stacktrace have useful information, but it didn't help
 - [X] The problematic code (if that's possible) is copied here;
       Note that some configuration are impossible to mock via Mockito
 - [X] Provide versions (mockito / jdk / os / any other relevant information)
 - [X] Provide a [Short, Self Contained, Correct (Compilable), Example](http://sscce.org) of the issue
       (same as any question on stackoverflow.com)
 - [X] Read the [contributing guide](https://github.com/mockito/mockito/blob/main/.github/CONTRIBUTING.md)




Issue comments:
I have opened the PR #3095, which would ease this issue, by changing the locking scheme in TypeCachingBytecodeGenerator from a single global lock to cacheLocks with size 16.
The used TypeCachingLock from cacheLocks depends on the hashcode of MockitoMockKey, which aggregates the types and
settings to mock.

So this will spread the Locks over 16 instances, assuming that the hashcodes of the class to mock are more or less evenly distributed.


Pull request review comments:

Patch that resolved the issue:
diff --git a/src/main/java/org/mockito/internal/creation/bytebuddy/TypeCachingBytecodeGenerator.java b/src/main/java/org/mockito/internal/creation/bytebuddy/TypeCachingBytecodeGenerator.java
index 30ed949bf5..3a8af3afa7 100644
--- a/src/main/java/org/mockito/internal/creation/bytebuddy/TypeCachingBytecodeGenerator.java
+++ b/src/main/java/org/mockito/internal/creation/bytebuddy/TypeCachingBytecodeGenerator.java
@@ -6,6 +6,7 @@
 
 import java.lang.ref.ReferenceQueue;
 import java.util.Set;
+import java.util.concurrent.Callable;
 import java.util.concurrent.locks.ReadWriteLock;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 
@@ -14,8 +15,17 @@
 
 class TypeCachingBytecodeGenerator extends ReferenceQueue<ClassLoader>
         implements BytecodeGenerator {
-
-    private static final Object BOOTSTRAP_LOCK = new Object();
+    /**
+     * The size of the {@link #cacheLocks}.
+     * <p>Caution: This must match the {@link #CACHE_LOCK_MASK}.
+     */
+    private static final int CACHE_LOCK_SIZE = 16;
+
+    /**
+     * The mask to use to mask out the {@link MockitoMockKey#hashCode()} to find the {@link #cacheLocks}.
+     * <p>Caution: this must match the bits of the {@link #CACHE_LOCK_SIZE}.
+     */
+    private static final int CACHE_LOCK_MASK = 0x0F;
 
     private final BytecodeGenerator bytecodeGenerator;
 
@@ -23,11 +33,29 @@ class TypeCachingBytecodeGenerator extends ReferenceQueue<ClassLoader>
 
     private final ReadWriteLock lock = new ReentrantReadWriteLock();
 
+    /**
+     * This array contains {@link TypeCachingLock} instances, which are used as java monitor locks for
+     * {@link TypeCache#findOrInsert(ClassLoader, Object, Callable, Object)}.
+     * The locks spread the lock to acquire over multiple locks instead of using a single lock
+     * {@code BOOTSTRAP_LOCK} for all {@link MockitoMockKey}.
+     *
+     * <p>Note: We can't simply use the mockedType class lock as a lock,
+     * because the {@link MockitoMockKey}, will be the same for different mockTypes + interfaces.
+     *
+     * <p>#3035: Excessive locking in TypeCachingBytecodeGenerator#BOOTSTRAP_LOCK
+     */
+    private final TypeCachingLock[] cacheLocks;
+
     public TypeCachingBytecodeGenerator(BytecodeGenerator bytecodeGenerator, boolean weak) {
         this.bytecodeGenerator = bytecodeGenerator;
         typeCache =
                 new TypeCache.WithInlineExpunction<>(
                         weak ? TypeCache.Sort.WEAK : TypeCache.Sort.SOFT);
+
+        this.cacheLocks = new TypeCachingLock[CACHE_LOCK_SIZE];
+        for (int i = 0; i < CACHE_LOCK_SIZE; i++) {
+            cacheLocks[i] = new TypeCachingLock();
+        }
     }
 
     @SuppressWarnings("unchecked")
@@ -35,17 +63,20 @@ public TypeCachingBytecodeGenerator(BytecodeGenerator bytecodeGenerator, boolean
     public <T> Class<T> mockClass(final MockFeatures<T> params) {
         lock.readLock().lock();
         try {
-            ClassLoader classLoader = params.mockedType.getClassLoader();
+            Class<T> mockedType = params.mockedType;
+            ClassLoader classLoader = mockedType.getClassLoader();
+            MockitoMockKey key =
+                    new MockitoMockKey(
+                            mockedType,
+                            params.interfaces,
+                            params.serializableMode,
+                            params.stripAnnotations);
             return (Class<T>)
                     typeCache.findOrInsert(
                             classLoader,
-                            new MockitoMockKey(
-                                    params.mockedType,
-                                    params.interfaces,
-                                    params.serializableMode,
-                                    params.stripAnnotations),
+                            key,
                             () -> bytecodeGenerator.mockClass(params),
-                            BOOTSTRAP_LOCK);
+                            getCacheLockForKey(key));
         } catch (IllegalArgumentException exception) {
             Throwable cause = exception.getCause();
             if (cause instanceof RuntimeException) {
@@ -58,6 +89,20 @@ public <T> Class<T> mockClass(final MockFeatures<T> params) {
         }
     }
 
+    /**
+     * Returns a {@link TypeCachingLock}, which locks the {@link TypeCache#findOrInsert(ClassLoader, Object, Callable, Object)}.
+     *
+     * @param key the key to lock
+     * @return the {@link TypeCachingLock} to use to lock the {@link TypeCache}
+     */
+    private TypeCachingLock getCacheLockForKey(MockitoMockKey key) {
+        int hashCode = key.hashCode();
+        // Try to spread some higher bits with XOR to lower bits, because we only use lower bits.
+        hashCode = hashCode ^ (hashCode >>> 16);
+        int index = hashCode & CACHE_LOCK_MASK;
+        return cacheLocks[index];
+    }
+
     @Override
     public void mockClassStatic(Class<?> type) {
         bytecodeGenerator.mockClassStatic(type);
@@ -79,6 +124,8 @@ public void clearAllCaches() {
         }
     }
 
+    private static final class TypeCachingLock {}
+
     private static class MockitoMockKey extends TypeCache.SimpleKey {
 
         private final SerializableMode serializableMode;


Test patch:
diff --git a/src/test/java/org/mockito/internal/creation/bytebuddy/TypeCachingMockBytecodeGeneratorTest.java b/src/test/java/org/mockito/internal/creation/bytebuddy/TypeCachingMockBytecodeGeneratorTest.java
index 026fba3bfb..56878b8cc8 100644
--- a/src/test/java/org/mockito/internal/creation/bytebuddy/TypeCachingMockBytecodeGeneratorTest.java
+++ b/src/test/java/org/mockito/internal/creation/bytebuddy/TypeCachingMockBytecodeGeneratorTest.java
@@ -13,10 +13,17 @@
 import java.lang.ref.Reference;
 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
+import java.util.Arrays;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.Set;
 import java.util.WeakHashMap;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+import java.util.function.Function;
 
 import org.junit.Before;
 import org.junit.Test;
@@ -208,6 +215,134 @@ public void ensure_cache_returns_same_instance_defaultAnswer() throws Exception
         assertThat(cache).isEmpty();
     }
 
+    @Test
+    public void cacheLockingStressTest_same_hashcode_different_interface()
+            throws InterruptedException, TimeoutException {
+        Class<?>[] classes = cacheLockingInMemClassLoaderClasses();
+        Class<?> ifA = classes[0];
+        Class<?> ifB = classes[1];
+        var featA = newMockFeatures(ifA, ifB);
+        var featB = newMockFeatures(ifB, ifA);
+        cacheLockingStressTestImpl(featA, featB);
+    }
+
+    @Test
+    public void cacheLockingStressTest_same_hashcode_same_interface()
+            throws InterruptedException, TimeoutException {
+        Class<?>[] classes = cacheLockingInMemClassLoaderClasses();
+        Class<?> ifA = classes[0];
+        var featA = newMockFeatures(ifA);
+        cacheLockingStressTestImpl(featA, featA);
+    }
+
+    @Test
+    public void cacheLockingStressTest_different_hashcode()
+            throws InterruptedException, TimeoutException {
+        Class<?>[] classes = cacheLockingInMemClassLoaderClasses();
+        Class<?> ifA = classes[0];
+        Class<?> ifB = classes[1];
+        Class<?> ifC = classes[2];
+        var featA = newMockFeatures(ifA, ifB);
+        var featB = newMockFeatures(ifB, ifC);
+        cacheLockingStressTestImpl(featA, featB);
+    }
+
+    @Test
+    public void cacheLockingStressTest_unrelated_classes()
+            throws InterruptedException, TimeoutException {
+        Class<?>[] classes = cacheLockingInMemClassLoaderClasses();
+        Class<?> ifA = classes[0];
+        Class<?> ifB = classes[1];
+        var featA = newMockFeatures(ifA);
+        var featB = newMockFeatures(ifB);
+        cacheLockingStressTestImpl(featA, featB);
+    }
+
+    private void cacheLockingStressTestImpl(MockFeatures<?> featA, MockFeatures<?> featB)
+            throws InterruptedException, TimeoutException {
+        int iterations = 10_000;
+
+        TypeCachingBytecodeGenerator bytecodeGenerator =
+                new TypeCachingBytecodeGenerator(new SubclassBytecodeGenerator(), true);
+
+        Phaser phaser = new Phaser(4);
+        Function<Runnable, CompletableFuture<Void>> runCode =
+                code ->
+                        CompletableFuture.runAsync(
+                                () -> {
+                                    phaser.arriveAndAwaitAdvance();
+                                    try {
+                                        for (int i = 0; i < iterations; i++) {
+                                            code.run();
+                                        }
+                                    } finally {
+                                        phaser.arrive();
+                                    }
+                                });
+        var mockFeatAFuture =
+                runCode.apply(
+                        () -> {
+                            Class<?> mockClass = bytecodeGenerator.mockClass(featA);
+                            assertValidMockClass(featA, mockClass);
+                        });
+
+        var mockFeatBFuture =
+                runCode.apply(
+                        () -> {
+                            Class<?> mockClass = bytecodeGenerator.mockClass(featB);
+                            assertValidMockClass(featB, mockClass);
+                        });
+        var cacheFuture = runCode.apply(bytecodeGenerator::clearAllCaches);
+        // Start test
+        phaser.arriveAndAwaitAdvance();
+        // Wait for test to end
+        int phase = phaser.arrive();
+        try {
+
+            phaser.awaitAdvanceInterruptibly(phase, 30, TimeUnit.SECONDS);
+        } finally {
+            // Collect exceptions from the futures, to make issues visible.
+            mockFeatAFuture.getNow(null);
+            mockFeatBFuture.getNow(null);
+            cacheFuture.getNow(null);
+        }
+    }
+
+    private static <T> MockFeatures<T> newMockFeatures(
+            Class<T> mockedType, Class<?>... interfaces) {
+        return MockFeatures.withMockFeatures(
+                mockedType,
+                new HashSet<>(Arrays.asList(interfaces)),
+                SerializableMode.NONE,
+                false,
+                null);
+    }
+
+    private static Class<?>[] cacheLockingInMemClassLoaderClasses() {
+        ClassLoader inMemClassLoader =
+                inMemoryClassLoader()
+                        .withClassDefinition("foo.IfA", makeMarkerInterface("foo.IfA"))
+                        .withClassDefinition("foo.IfB", makeMarkerInterface("foo.IfB"))
+                        .withClassDefinition("foo.IfC", makeMarkerInterface("foo.IfC"))
+                        .build();
+        try {
+            return new Class[] {
+                inMemClassLoader.loadClass("foo.IfA"),
+                inMemClassLoader.loadClass("foo.IfB"),
+                inMemClassLoader.loadClass("foo.IfC")
+            };
+        } catch (ClassNotFoundException e) {
+            throw new IllegalStateException(e);
+        }
+    }
+
+    private void assertValidMockClass(MockFeatures<?> mockFeature, Class<?> mockClass) {
+        assertThat(mockClass).isAssignableTo(mockFeature.mockedType);
+        for (Class<?> anInterface : mockFeature.interfaces) {
+            assertThat(mockClass).isAssignableTo(anInterface);
+        }
+    }
+
     static class HoldingAReference {
         final WeakReference<Class<?>> a;