raphLock has no timed/try acquisition; polling writers can starve, and a stalled reader plus a queued writer can wedge all graph operations

[MattArtzAnthro]

Problem

I maintain a Gephi plugin (gephi-ai) that runs an HTTP API inside Gephi Desktop and does graph reads and writes from a non-EDT thread while the viz-engine renders. I should say up front that I have been troubleshooting this together with Claude (Anthropic's AI assistant), and the analysis and reproducer below came out of that joint debugging. I have tried to verify everything against the source and a live Gephi 0.11.2 session on macOS (Apple Silicon), but please read it as a good-faith diagnosis, and I am glad to re-check anything.

The symptom: my sessions would eventually wedge the whole application. A lock-free health endpoint kept answering, but every graph operation, reads included, blocked forever, and Gephi's own UI stopped processing graph work. Only a restart recovered. Thread dumps show no lock cycle, so deadlock detection sees nothing. This looks related to gephi/gephi#2546 and to gephi-plugins#250 / #150, though I think the mechanism here is in the lock API rather than in graph/table lock ordering.

I work around it today by reflecting into GraphLockImpl and polling timed tryLock for both locks. That works, but it is reflection into impl internals, which is why I am raising it here.

What the source seems to do

If I am reading it correctly: GraphLockImpl wraps an unfair new ReentrantReadWriteLock() with no fairness option (GraphLockImpl.java L30); readLock()/writeLock() are unbounded, non-interruptible lock() calls; and I could not find any tryLock, timed, or interruptible variant in the public GraphLock/Graph API, though I may have missed one. Iterators hold the read lock from construction (NodeStore.java L654) until exhaustion or doBreak(), and with auto-locking on by default a full-graph read section is proportional to graph size. During rendering, the viz-engine's world updaters appear to re-acquire read locks with essentially no idle gap.

Reproducer results

Standalone single file (collapsed below), depends only on org.gephi:graphstore:0.8.6, runs with mvn -q compile exec:java in about 40 seconds. It builds a 300k-node graph and runs 3 "render" threads that iterate all nodes under the read lock in a tight loop, which I hope is a fair stand-in for the world updaters. Numbers from macOS aarch64, JDK 25.

1. Blocking writeLock() works (the AQS queued-writer heuristic prevents starvation): 47 acquisitions, p50 wait 2.0 ms, max 3.1 ms. Every queued write also stalls new readers for the drain time of in-flight read sections, which grows with graph size.

2. Untimed tryLock() polling starves in my measurements. It barges and never enqueues, so with overlapping readers there may never be a zero-reader instant to succeed in:

untimed tryLock():        0 / 4637 acquisitions in 6s
timed tryLock(120ms):     2116 / 2116 acquisitions in 6s

The timed variant enqueues and worked perfectly in the same test, but neither is reachable through the public API today.

3. One stalled reader plus one queued writer appears to wedge everything permanently. Reader A holds the read lock and waits on another thread; writer W enqueues; every new reader parks behind W (including trivial auto-locked reads like getNodes().toArray()); A never releases, W never acquires:

after 5s:
  reader-A state: WAITING  (holds read lock, awaiting B)
  writer-W state: WAITING  (queued for write lock)
  reader-B state: WAITING  (parked behind queued writer)
  probe getNodes().toArray() returned: false
  → WEDGED: only killing the JVM recovers.

No lock cycle is visible to jstack. This matches what I saw in Gephi Desktop, including "reads hang too", though I cannot be certain every field wedge shares this root.

Field notes

Instrumenting a live session, I believe I caught a variant of scenario 3 in production, and it was my own bug: my endpoint iterated graph.getEdges() and broke out early at a result limit, which (if I understand the iterator contract correctly) leaked the iterator's read hold. The request thread then exited, making the hold permanently unreleasable, since ReentrantReadWriteLock read holds are a shared count with no owner tracking. From then on, one queued writer wedged everything while health kept answering, and a thread dump showed nothing at all, since the holder no longer existed. I confirmed it by reflecting getReadLockCount(), which read 1 while the app was idle. I have fixed this on my side, but a for plus break over an iterable is idiomatic Java, nothing in the API surfaces the consequence, and it may also catch first-party code (GraphSelectionImpl.setSelectedNodes(Graph, NodeIterable, ...) in Gephi's VisualizationImpl appears to take readLock() with no try/finally, so an exception in its consumer could potentially leak the same way).

Ideas, in case they are useful

1. Timed acquisition on GraphLock: tryReadLock(timeout, unit) / tryWriteLock(timeout, unit) delegating to the underlying lock. Looks non-breaking from the outside, removes the reflection workaround, and Add some API methods to check lock integrity (for tests) #145 already extended GraphLock once, if that precedent applies.
2. Queue diagnostics: perhaps hasQueuedWriter() or getQueueLength(), so a watchdog could turn scenario 3 into an actionable error instead of a force-quit.
3. Possibly a fairness flag in Configuration, though it would not fix 1 or 2 (tryLock() barges even on a fair lock) and fair mode usually costs read throughput, so I would benchmark before considering it.
4. A Javadoc note on readLock() and the auto-locked iterables: holding the lock across a cross-thread wait, or abandoning an iterator without exhaustion or doBreak(), can wedge the store once a writer queues.

I may be missing context on why the API is shaped this way, and if there is a recommended pattern for external integrations that I overlooked, I would appreciate the pointer. If the direction sounds reasonable, I am happy to try turning 1 and 2 into a PR with tests based on the reproducer.

Reproducer code

pom.xml + GraphStoreLockRepro.java (click to expand)

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>me.mattartz</groupId>
    <artifactId>graphstore-lock-repro</artifactId>
    <version>1.0.0</version>
    <packaging>jar</packaging>

    <name>graphstore lock starvation / wedge reproducer</name>
    <description>
        Minimal standalone reproducer for writer starvation and reader-wedge behavior
        of org.gephi.graph.impl.GraphLockImpl under a render-style read workload.
        Run: mvn -q compile exec:java                      (all three scenarios)
             mvn -q compile exec:java -Dexec.args=latency  (scenario 1 only)
             mvn -q compile exec:java -Dexec.args=trylock  (scenario 2 only)
             mvn -q compile exec:java -Dexec.args=wedge    (scenario 3 only)
    </description>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <maven.compiler.release>11</maven.compiler.release>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.gephi</groupId>
            <artifactId>graphstore</artifactId>
            <version>0.8.6</version>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.codehaus.mojo</groupId>
                <artifactId>exec-maven-plugin</artifactId>
                <version>3.1.0</version>
                <configuration>
                    <mainClass>GraphStoreLockRepro</mainClass>
                    <!-- Scenario 3 intentionally leaves deadlocked (daemon) threads
                         behind; don't let exec:java hang trying to join them. -->
                    <cleanupDaemonThreads>false</cleanupDaemonThreads>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

src/main/java/GraphStoreLockRepro.java

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import org.gephi.graph.api.Graph;
import org.gephi.graph.api.GraphModel;
import org.gephi.graph.api.Node;

/**
 * Minimal reproducer for lock behavior of org.gephi.graph.impl.GraphLockImpl
 * (graphstore 0.8.6) under a render-style read workload, i.e. what Gephi's
 * viz-engine world updaters do: several threads that iterate the visible graph
 * under the read lock, over and over, with essentially no idle gap.
 *
 * Scenario 1 (latency):  blocking writeLock() vs. continuous readers.
 *                        Measures writer acquisition latency and the reader
 *                        stalls a queued writer causes.
 *
 * Scenario 2 (trylock):  untimed WriteLock.tryLock() polling vs. the same
 *                        readers. This is what an external caller is pushed
 *                        toward, because the GraphLock API has no timed or
 *                        try acquisition. It starves indefinitely: tryLock()
 *                        never enqueues, so it never triggers the AQS
 *                        reader-block heuristic, and with overlapping readers
 *                        there is never a zero-reader instant to barge into.
 *                        A timed tryLock(120ms) control (which does enqueue)
 *                        is run for comparison.
 *
 * Scenario 3 (wedge):    one reader holds the read lock while waiting on a
 *                        second thread that itself needs the read lock (any
 *                        cross-thread handoff under the lock). A single
 *                        writer calls writeLock() and enqueues. Result:
 *                        three-party deadlock, and every subsequent reader
 *                        (including trivial auto-locked calls like
 *                        getNodeCount()) blocks forever. This is the
 *                        "process alive, every graph operation hangs"
 *                        state I observe in Gephi Desktop on macOS.
 *
 * Only public API is used to take locks (Graph.readLock()/writeLock()).
 * Reflection is used solely (a) in scenario 2 to reach the underlying
 * WriteLock for tryLock, the exact workaround external code is forced
 * into today, and (b) to observe hasQueuedThreads() for deterministic
 * sequencing in scenario 3.
 */
public final class GraphStoreLockRepro {

    static final int NODE_COUNT = 300_000;
    static final int READER_THREADS = 3;          // viz-engine world updater pool is typically 2-4
    static final int SCENARIO_SECONDS = 12;

    public static void main(String[] args) throws Exception {
        String which = args.length > 0 ? args[0] : "all";
        System.out.println("graphstore-lock-repro | graphstore 0.8.6 | java "
                + System.getProperty("java.version") + " | " + System.getProperty("os.name")
                + " " + System.getProperty("os.arch"));
        System.out.println("graph: " + NODE_COUNT + " nodes, readers: " + READER_THREADS
                + ", each scenario ~" + SCENARIO_SECONDS + "s");
        System.out.println();

        if (which.equals("all") || which.equals("latency")) scenarioWriterLatency();
        if (which.equals("all") || which.equals("trylock")) scenarioTryLockStarvation();
        if (which.equals("all") || which.equals("wedge"))   scenarioReaderWedge();
    }

    // ─────────────────────────────────────────────────────────────────────
    // Shared plumbing
    // ─────────────────────────────────────────────────────────────────────

    static Graph buildGraph() {
        GraphModel model = GraphModel.Factory.newInstance();
        Graph graph = model.getDirectedGraph();
        List<Node> nodes = new ArrayList<>(NODE_COUNT);
        for (int i = 0; i < NODE_COUNT; i++) {
            Node n = model.factory().newNode(String.valueOf(i));
            n.setPosition((float) Math.random(), (float) Math.random());
            nodes.add(n);
        }
        graph.addAllNodes(nodes);
        return graph;
    }

    /**
     * One "frame" of render-style read work: iterate every node under the
     * read lock and read its position, like a world updater filling vertex
     * buffers. Returns elapsed nanos of the read section.
     */
    static long renderFrame(Graph graph, double[] sink) {
        long t0 = System.nanoTime();
        graph.readLock();
        try {
            double s = 0;
            for (Node n : graph.getNodes()) {
                s += n.x() + n.y();
            }
            sink[0] = s;
        } finally {
            graph.readUnlock();
        }
        return System.nanoTime() - t0;
    }

    /** Starts continuous reader threads; returns the stop flag. */
    static AtomicBoolean startReaders(Graph graph, AtomicLong maxReaderAcquireNanos) {
        AtomicBoolean stop = new AtomicBoolean(false);
        for (int i = 0; i < READER_THREADS; i++) {
            Thread t = new Thread(() -> {
                double[] sink = new double[1];
                while (!stop.get()) {
                    long a0 = System.nanoTime();
                    graph.readLock();                 // measure acquisition alone
                    long acq = System.nanoTime() - a0;
                    maxReaderAcquireNanos.accumulateAndGet(acq, Math::max);
                    try {
                        double s = 0;
                        for (Node n : graph.getNodes()) {
                            s += n.x() + n.y();
                        }
                        sink[0] = s;
                    } finally {
                        graph.readUnlock();
                    }
                    // no sleep: world updates are rescheduled as soon as the
                    // previous ones finish (CONCURRENT_ASYNCHRONOUS)
                }
            }, "render-reader-" + i);
            t.setDaemon(true);
            t.start();
        }
        return stop;
    }

    static ReentrantReadWriteLock underlyingLock(Graph graph) {
        try {
            Object lock = graph.getLock();                       // GraphLockImpl
            Field f = lock.getClass().getDeclaredField("readWriteLock");
            f.setAccessible(true);
            return (ReentrantReadWriteLock) f.get(lock);
        } catch (ReflectiveOperationException e) {
            throw new IllegalStateException("cannot reflect GraphLockImpl.readWriteLock", e);
        }
    }

    static String ms(long nanos) {
        return String.format("%.1f ms", nanos / 1_000_000.0);
    }

    static long percentile(List<Long> sorted, double p) {
        if (sorted.isEmpty()) return 0;
        int idx = (int) Math.min(sorted.size() - 1, Math.round(p * (sorted.size() - 1)));
        return sorted.get(idx);
    }

    // ─────────────────────────────────────────────────────────────────────
    // Scenario 1: blocking writeLock() latency under continuous readers
    // ─────────────────────────────────────────────────────────────────────

    static void scenarioWriterLatency() throws Exception {
        System.out.println("── Scenario 1: blocking writeLock() under " + READER_THREADS
                + " continuous readers ──");
        Graph graph = buildGraph();
        double[] sink = new double[1];
        long frame = renderFrame(graph, sink);
        System.out.println("single read pass (one 'frame') over " + NODE_COUNT + " nodes: " + ms(frame));

        AtomicLong maxReaderAcquire = new AtomicLong();
        AtomicBoolean stop = startReaders(graph, maxReaderAcquire);
        Thread.sleep(500); // let readers reach steady state

        GraphModel model = graph.getModel();
        List<Long> waits = new ArrayList<>();
        long end = System.nanoTime() + SCENARIO_SECONDS * 1_000_000_000L;
        int i = 0;
        while (System.nanoTime() < end) {
            long t0 = System.nanoTime();
            graph.writeLock();
            long waited = System.nanoTime() - t0;
            try {
                Node n = model.factory().newNode("w" + (i++));
                graph.addNode(n);
                graph.removeNode(n);
            } finally {
                graph.writeUnlock();
            }
            waits.add(waited);
            Thread.sleep(250); // interactive mutation pace: a few writes per second
        }
        stop.set(true);
        Thread.sleep(200);

        Collections.sort(waits);
        System.out.println("writer writeLock() acquisitions: " + waits.size());
        System.out.println("  p50 wait: " + ms(percentile(waits, 0.50))
                + " | p95: " + ms(percentile(waits, 0.95))
                + " | max: " + ms(percentile(waits, 1.0)));
        System.out.println("  max reader acquisition stall (reader parked behind queued writer): "
                + ms(maxReaderAcquire.get()));
        System.out.println("  → writer latency is bounded by the in-flight read sections, i.e. it");
        System.out.println("    scales with graph size; every queued write also stalls the renderer");
        System.out.println("    for the same duration (readers park behind the queued writer).");
        System.out.println();
    }

    // ─────────────────────────────────────────────────────────────────────
    // Scenario 2: untimed tryLock() starvation (what external code is
    // pushed toward, since GraphLock has no try/timed acquisition)
    // ─────────────────────────────────────────────────────────────────────

    static void scenarioTryLockStarvation() throws Exception {
        System.out.println("── Scenario 2: WriteLock.tryLock() polling under the same readers ──");
        Graph graph = buildGraph();
        AtomicLong maxReaderAcquire = new AtomicLong();
        AtomicBoolean stop = startReaders(graph, maxReaderAcquire);
        Thread.sleep(500);

        ReentrantReadWriteLock rrwl = underlyingLock(graph);

        // 2a: untimed tryLock(), never enqueues, so readers are never asked
        // to yield; with overlapping readers it may never find a gap.
        long attempts = 0, successes = 0;
        long half = SCENARIO_SECONDS / 2 * 1_000_000_000L;
        long end = System.nanoTime() + half;
        while (System.nanoTime() < end) {
            attempts++;
            if (rrwl.writeLock().tryLock()) {
                successes++;
                rrwl.writeLock().unlock();
            }
            Thread.sleep(1);
        }
        System.out.println("untimed tryLock():        " + successes + " / " + attempts
                + " acquisitions in " + (SCENARIO_SECONDS / 2) + "s");

        // 2b: timed tryLock(120ms), enqueues, so the AQS heuristic blocks
        // new readers behind it and it acquires once in-flight readers drain.
        attempts = 0;
        successes = 0;
        end = System.nanoTime() + half;
        while (System.nanoTime() < end) {
            attempts++;
            if (rrwl.writeLock().tryLock(120, TimeUnit.MILLISECONDS)) {
                successes++;
                rrwl.writeLock().unlock();
            }
            Thread.sleep(1);
        }
        System.out.println("timed tryLock(120ms):     " + successes + " / " + attempts
                + " acquisitions in " + (SCENARIO_SECONDS / 2) + "s");
        stop.set(true);
        Thread.sleep(200);
        System.out.println("  → the non-blocking strategy an external integration would naturally");
        System.out.println("    use (poll tryLock to avoid wedging its own thread) starves");
        System.out.println("    indefinitely under a render-style read stream. Only the timed,");
        System.out.println("    queue-entering variant makes progress, and neither is reachable");
        System.out.println("    through the public GraphLock API without reflection.");
        System.out.println();
    }

    // ─────────────────────────────────────────────────────────────────────
    // Scenario 3: queued writer + reader-side cross-thread wait = total wedge
    // ─────────────────────────────────────────────────────────────────────

    static void scenarioReaderWedge() throws Exception {
        System.out.println("── Scenario 3: queued writer converts one stalled reader into a global wedge ──");
        Graph graph = buildGraph();
        ReentrantReadWriteLock rrwl = underlyingLock(graph);

        CountDownLatch aHoldsReadLock = new CountDownLatch(1);
        CountDownLatch bFinished = new CountDownLatch(1);

        // Reader A: takes the read lock, then waits for helper B to complete a
        // read-locked pass of its own before releasing. Any cross-thread
        // handoff while holding the read lock has this shape (worker pools,
        // producer/consumer over an iterable, a render thread waiting on a
        // sub-task, an EDT paint waiting on a background computation, ...).
        Thread readerA = new Thread(() -> {
            graph.readLock();
            try {
                aHoldsReadLock.countDown();
                bFinished.await();                    // ← never returns
            } catch (InterruptedException ignored) {
            } finally {
                graph.readUnlock();
            }
        }, "reader-A");
        readerA.setDaemon(true);
        readerA.start();
        aHoldsReadLock.await();

        // Writer W: ordinary blocking writeLock(), enqueues behind A's hold.
        Thread writerW = new Thread(graph::writeLock, "writer-W");
        writerW.setDaemon(true);
        writerW.start();
        long spin = System.nanoTime() + 2_000_000_000L;
        while (!rrwl.hasQueuedThreads() && System.nanoTime() < spin) {
            Thread.sleep(5);
        }
        System.out.println("writer-W parked in the lock queue: " + rrwl.hasQueuedThreads());

        // Helper B: a plain reader. Read lock is held only by A (a reader!),
        // yet B parks: the queued writer makes readerShouldBlock() true for
        // every new, non-reentrant reader.
        Thread readerB = new Thread(() -> {
            graph.readLock();
            try {
                bFinished.countDown();                // never reached
            } finally {
                graph.readUnlock();
            }
        }, "reader-B");
        readerB.setDaemon(true);
        readerB.start();

        // Probe: what any other component now experiences, a trivial read
        // through the auto-locking public API (NodeStore.toArray() acquires
        // the read lock). This is my "project info" HTTP endpoint, Gephi's
        // own UI, everything.
        AtomicBoolean probeReturned = new AtomicBoolean(false);
        Thread probe = new Thread(() -> {
            graph.getNodes().toArray();               // auto read lock
            probeReturned.set(true);
        }, "probe-trivial-read");
        probe.setDaemon(true);
        probe.start();

        Thread.sleep(5000);

        System.out.println("after 5s:");
        System.out.println("  reader-A state: " + readerA.getState() + "  (holds read lock, awaiting B)");
        System.out.println("  writer-W state: " + writerW.getState() + "  (queued for write lock)");
        System.out.println("  reader-B state: " + readerB.getState() + "  (parked behind queued writer)");
        System.out.println("  probe getNodes().toArray() returned: " + probeReturned.get()
                + "  (state: " + probe.getState() + ")");
        boolean wedged = !probeReturned.get() && writerW.getState() == Thread.State.WAITING
                && readerB.getState() == Thread.State.WAITING;
        System.out.println(wedged
                ? "  → WEDGED: no reader or writer can ever make progress; only killing the JVM recovers."
                : "  → not wedged (unexpected on an unfair ReentrantReadWriteLock)");
        System.out.println();
        // Deadlocked daemon threads remain; exiting main() ends the demo.
    }
}