Deadlock in Structure constructor introduced in 5.16.0

[jjanowsk]

Overview

The Structure class constructor contains a deadlock scenario. The particular scenario we found can occur during the creation of two ByValue structures both containing a member of a type Structure.ByValue. I have prepared a minimal reproducible example. Running it multiple times should produce the attached output.

Random notes on the problem

This deadlock was introduced in this PR: #1626
I don't think the scenario we've encountered is the only possible one, given the multitude of execution paths in this file, its recursive nature, and the fact that there are 4 explicit locks + additional synchronization on the typeInfoMap object. Given those factors, I think it's extremely hard to rule out deadlocks only by manual verification, and I would recommend using a single reentrant read-write lock for the whole file, if performance allows it.

Deadlocked stacktraces

Thread: Thread-1 (State: WAITING)
  at java.base@11.0.28/jdk.internal.misc.Unsafe.park(Native Method)
  at java.base@11.0.28/java.util.concurrent.locks.LockSupport.park(LockSupport.java:194)
  at java.base@11.0.28/java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:885)
  at java.base@11.0.28/java.util.concurrent.locks.AbstractQueuedSynchronizer.doAcquireShared(AbstractQueuedSynchronizer.java:1009)
  at java.base@11.0.28/java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireShared(AbstractQueuedSynchronizer.java:1324)
  at java.base@11.0.28/java.util.concurrent.locks.ReentrantReadWriteLock$ReadLock.lock(ReentrantReadWriteLock.java:738)
  at com.sun.jna.Structure.validateFields(Structure.java:1310)
  at com.sun.jna.Structure.<init>(Structure.java:218)
  at com.sun.jna.Structure.<init>(Structure.java:211)
  at com.sun.jna.Structure.<init>(Structure.java:198)
  at com.sun.jna.Structure.<init>(Structure.java:190)
  at com.sun.jna.Structure$FFIType.<init>(Structure.java:2137)
  at com.sun.jna.Structure$FFIType.get(Structure.java:2249)
  at com.sun.jna.Structure$FFIType.get(Structure.java:2222)
  at com.sun.jna.Structure.getTypeInfo(Structure.java:1914)
  at com.sun.jna.Structure.getTypeInfo(Structure.java:1847)
  at com.sun.jna.Structure.deriveLayout(Structure.java:1468)
  at com.sun.jna.Structure.calculateSize(Structure.java:1237)
  at com.sun.jna.Structure.calculateSize(Structure.java:1183)
  at com.sun.jna.Structure.allocateMemory(Structure.java:433)
  at com.sun.jna.Structure.<init>(Structure.java:223)
  at com.sun.jna.Structure.<init>(Structure.java:211)
  at com.sun.jna.Structure.<init>(Structure.java:198)
  at com.sun.jna.Structure.<init>(Structure.java:190)
  at com.example.jna.JnaDeadlock$s1.<init>(JnaDeadlock.java:17)
  at com.example.jna.JnaDeadlock$s1$ByValue.<init>(JnaDeadlock.java:20)
  at com.example.jna.JnaDeadlock.runT1(JnaDeadlock.java:67)
  at com.example.jna.JnaDeadlock.lambda$0(JnaDeadlock.java:45)
  at com.example.jna.JnaDeadlock$$Lambda$36/0x00000008401bec40.run(Unknown Source)
  at java.base@11.0.28/java.lang.Thread.run(Thread.java:829)

Thread: Thread-2 (State: BLOCKED)
  at com.sun.jna.Structure$FFIType.get(Structure.java:2234)
  at com.sun.jna.Structure$FFIType.get(Structure.java:2222)
  at com.sun.jna.Structure.getTypeInfo(Structure.java:1914)
  at com.sun.jna.Structure.getTypeInfo(Structure.java:1847)
  at com.sun.jna.Structure.deriveLayout(Structure.java:1468)
  at com.sun.jna.Structure.calculateSize(Structure.java:1237)
  at com.sun.jna.Structure.calculateSize(Structure.java:1183)
  at com.sun.jna.Structure.allocateMemory(Structure.java:433)
  at com.sun.jna.Structure.<init>(Structure.java:223)
  at com.sun.jna.Structure.<init>(Structure.java:211)
  at com.sun.jna.Structure.<init>(Structure.java:198)
  at com.sun.jna.Structure.<init>(Structure.java:190)
  at com.example.jna.JnaDeadlock$s2_embedded.<init>(JnaDeadlock.java:25)
  at com.example.jna.JnaDeadlock$s2_embedded$ByValue.<init>(JnaDeadlock.java:28)
  at java.base@11.0.28/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
  at java.base@11.0.28/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
  at java.base@11.0.28/jdk.internal.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
  at java.base@11.0.28/java.lang.reflect.Constructor.newInstance(Constructor.java:490)
  at com.sun.jna.Klass.newInstance(Klass.java:48)
  at com.sun.jna.Structure.newInstance(Structure.java:1979)
  at com.sun.jna.Structure.newInstance(Structure.java:1965)
  at com.sun.jna.Structure.size(Structure.java:1210)
  at com.sun.jna.Native.getNativeSize(Native.java:1400)
  at com.sun.jna.Structure.getNativeSize(Structure.java:2385)
  at com.sun.jna.Structure.getNativeSize(Structure.java:2375)
  at com.sun.jna.Structure.validateField(Structure.java:1298)
  at com.sun.jna.Structure.lambda$validateFields$2(Structure.java:1325)
  at com.sun.jna.Structure$$Lambda$39/0x00000008401bc040.apply(Unknown Source)
  at java.base@11.0.28/java.util.Map.computeIfAbsent(Map.java:1003)
  at com.sun.jna.Structure.validateFields(Structure.java:1323)
  at com.sun.jna.Structure.<init>(Structure.java:218)
  at com.sun.jna.Structure.<init>(Structure.java:211)
  at com.sun.jna.Structure.<init>(Structure.java:198)
  at com.sun.jna.Structure.<init>(Structure.java:190)
  at com.example.jna.JnaDeadlock$s2.<init>(JnaDeadlock.java:33)
  at com.example.jna.JnaDeadlock$s2$ByValue.<init>(JnaDeadlock.java:36)
  at com.example.jna.JnaDeadlock.runT2(JnaDeadlock.java:75)
  at com.example.jna.JnaDeadlock.lambda$1(JnaDeadlock.java:48)
  at com.example.jna.JnaDeadlock$$Lambda$37/0x00000008401be040.run(Unknown Source)
  at java.base@11.0.28/java.lang.Thread.run(Thread.java:829)

Minimal reproducible example

package com.example.jna;

import com.sun.jna.Structure;
import com.sun.jna.Structure.FieldOrder;
import java.util.concurrent.CountDownLatch;

public class JnaDeadlock {
    @FieldOrder({ "f" })
    public static class s1_embedded extends Structure {
        public int f;

        public static class ByValue extends s1_embedded implements Structure.ByValue {
        }
    }

    @FieldOrder({ "embeddedByValue" })
    public static class s1 extends Structure {
        public s1_embedded.ByValue embeddedByValue;

        public static class ByValue extends s1 implements Structure.ByValue {
        }
    }

    @FieldOrder({ "f" })
    public static class s2_embedded extends Structure {
        public int f;

        public static class ByValue extends s2_embedded implements Structure.ByValue {
        }
    }

    @FieldOrder({ "embeddedByValue" })
    public static class s2 extends Structure {
        public s2_embedded.ByValue embeddedByValue;

        public static class ByValue extends s2 implements Structure.ByValue {
        }
    }

    public static void main(String[] args) throws Exception {
        CountDownLatch startLatch = new CountDownLatch(1);

        Thread[] threads = new Thread[2];
        threads[0] = new Thread(() -> {
            runT1(startLatch);
        });
        threads[1] = new Thread(() -> {
            runT2(startLatch);
        });

        threads[0].start();
        threads[1].start();

        Thread monitorThread = new Thread(() -> {
            monitorThread(threads);
        });
        monitorThread.setDaemon(true);
        monitorThread.start();

        // Release all threads to start at the same time
        startLatch.countDown();
    }

    private static void runT1(CountDownLatch startLatch) {
        try {
            startLatch.await();
            new s1.ByValue();
        } catch (InterruptedException e) {
        }
    }

    private static void runT2(CountDownLatch startLatch) {
        try {
            startLatch.await();
            new s2.ByValue();
        } catch (InterruptedException e) {
        }
    }

    private static void monitorThread(Thread[] workers) {
        try {
            Thread.sleep(2000);

            for (Thread worker : workers) {
                StackTraceElement[] stackTrace = worker.getStackTrace();

                System.out.println("\nThread: " + worker.getName() +
                        " (State: " + worker.getState() + ")");

                for (StackTraceElement element : stackTrace) {
                    System.out.println("  at " + element);
                }
            }
        } catch (InterruptedException e) {
        }
    }
}

[matthiasblaesing]

@brettwooldridge could you please check this?

[brettwooldridge]

@jjanowsk @matthiasblaesing I agree that the safest and most maintainable solution is a single reentrant read-write lock and the elimination of synchronized blocks. I also believe that whatever the impact of using a single lock guarding all structures, it is greatly outweighed by the performance gains of the cached collections. Particularly because reads allow uncontented (reentrant) multi-threaded access and only writes to the caches need to be serialized.

I will look at this.

[brettwooldridge]

@jjanowsk I don't know if you have the ability to build JNA locally for test, but I have committed a fix to master on my fork here:

https://github.com/brettwooldridge/jna

This employs a single reentrant read-write lock across the Structure class and removes all relevant synchronized blocks.

I am able to execute the test case above 1000 times without deadlock:

for i in {1..1000}; do java -cp "./lib/*:." com.example.jna.JnaDeadlock; done

Are you able to test it locally before I submit a pull request?

EDIT: In A/B testing between this code and 5.15.0, there is no measurable difference in 1000 executions of the above test between the two on the performance side.

[brettwooldridge]

@jjanowsk @matthiasblaesing As you can see above, I have created a pull request to address this issue.

I even ran tests on a dual-CPU server, because I have seen subtle race conditions in the past that rarely occur on single CPU systems but surface almost immediately on multi-CPU systems.

[jjanowsk]

@brettwooldridge Thanks for the PR. I've also tested the code from your fork on my machine and it does not reproduce after 10000 executions (seems obvious given the changes you've made, but always worth double checking). I've reviewed your changes. They look good in my opinion. Thanks again for addressing it so swiftly.

@matthiasblaesing Do you know when we can expect a new version of JNA with the fix included?