OfflineSorter loses a partition permit when its executor rejects a task; once none are left, sort() on the same sorter waits until interrupted

OfflineSorter, Lucene's external sorter in org.apache.lucene.util, can sort partitions concurrently on an ExecutorService you pass in, holding at most maxPartitionsInRAM partitions in memory. It enforces that cap with a semaphore owned by the sorter: readPartition takes a permit for each partition, and only the finally of the task that sorts the partition gives it back. sort() submits that task with no guard, so when the executor rejects it (shut down, or bounded and full), sort() throws RejectedExecutionException and the permit is lost for good. Each rejection lowers the sorter's concurrency by one; once all permits are gone, every later sort() on that instance parks in Semaphore.acquire until interrupted, even with an idle executor, and a shut-down executor's fail-fast exception becomes an indefinite wait. Results are never wrong and nothing is written to the index. The default constructors cannot hit it and no in-tree caller passes an executor. Every release from 6.6.0 to 10.6.0 and main is affected.

• A permit per partition: readPartition starts with partitionsInRAM.acquire() (OfflineSorter.java:430-433) and, on success, returns the partition still holding the permit (:478).
• Who gives it back. Three places, and only one for a partition with data: the empty last read in sort() (:301-304), readPartition's own failure path (:479-484), and the finally of SortPartitionTask.call (:652-656).
• The unguarded hand-off (:309-311):

Callable<Partition> job = new SortPartitionTask(trackingDir, part);

segments.add(exec.submit(job));

• If submit throws, call() never runs, so its finally never runs. The catch (Throwable t) of sort() (:366-369) deletes the temp files and rethrows; it does not touch the semaphore.
• The loss outlives the call: partitionsInRAM is a private final Semaphore (:76) created once per instance (:250). sort() resets its per-call state (sortInfo = new SortInfo(), :289); there is no close() and no "already used" check. The next call opens its input (:298) and parks in acquire (:432), holding that input open.
• Not affected: the merge hand-off (:398) holds no permit. The 2- and 3-argument constructors pass null, so the sorter creates its own SameThreadExecutorService with one permit (:246-249); nothing outside the sorter can reach that executor, and it rejects only after shutdown().

• maxPartitionsInRAM = 1, one-record input, executor already shut down: the first sort() throws RejectedExecutionException; the second is still blocked after 10 s, in Semaphore.acquire <- OfflineSorter.readPartition(OfflineSorter.java:432) <- OfflineSorter.sort(OfflineSorter.java:300).
• A bounded pool instead (1 thread, queue of 16, default AbortPolicy, filled by other work): the retry after the pool has drained waits with executor active=0 queued=0.
• maxPartitionsInRAM = 2: after one rejection the next sort still returns correctly sorted output (one permit left); after a second rejection the next sort waits.
• An interrupt ends the wait: sort() throws ThreadInterruptedException (:363-365). A new sorter on the same executor fails fast; only the old instance is broken.

• Who. Code using the 8-argument constructor with an ExecutorService that can reject: one that has been shut down, or a bounded ThreadPoolExecutor with the default AbortPolicy that other work has filled. It then has to call sort() again on the same OfflineSorter after the RejectedExecutionException.
• Effect. Each rejected partition task silently removes one of the maxPartitionsInRAM permits. Before the last is gone, sorting is only less concurrent and stays correct. After that, every later sort() on the instance parks without CPU use, holding one thread and one open input file, until interrupted (a probe: 8 parked calls used 0 ms of CPU over 2 s and held 8 open inputs; interrupting them closed all 8 and left no temp files). With a shut-down executor, a call that should fail fast waits instead.
• Not hit. The 2- and 3-argument constructors (their private same-thread executor is never shut down). No in-tree caller passes an executor: the hunspell SortingStrategy, FSTCompletionLookup, SortedInputIterator and AnalyzingSuggester use the default constructors, and BKDWriter passed null, 0 back in 6.x and 7.x. A read-only, non-exhaustive code search found no downstream use of the executor constructor. One in-tree public API does take a sorter the application built: ExternalRefSorter (lucene/suggest, also @lucene.internal) calls sort() from iterator(), so it can be hit only if the application hands it an executor-backed sorter and reuses that sorter after a rejection.
• Scale. Any input size: the repro sorts one record. The class is tagged @lucene.experimental and @lucene.internal.
• Likelihood: rare. It needs a rejecting executor plus reuse of the failed sorter; nobody has reported it since 2017.

The class sits in org.apache.lucene.util so it can live next to TestOfflineSorter; it uses no package-private member (an independent test in another package reproduced it through the public API alone). Smallest input: one record (the byte 42), one partition, ByteBuffersDirectory, a 1 MB buffer, maxPartitionsInRAM = 1, and a single-thread executor shut down before use, so it never starts a thread (NamedThreadFactory is there only because forbidden-apis bans the factory-less Executors.newSingleThreadExecutor()). The second sort() runs on its own thread only because a hang cannot be bounded on the calling thread: after up to 10 s the test records whether it is still running, interrupts it (which ends the wait, so no thread leaks), and fails if it was blocked or ended with anything but RejectedExecutionException.

./gradlew tidy re-wraps two lines of this file that are over the column limit; the copy that ran through gradle has the same code, with that comment shortened instead of wrapped.

Regression test: this same class (or its one method added to TestOfflineSorter); with the recommended fix it passes at once (0.07 s for the method in a gradle re-run). It pins the fail-fast behaviour of the recommended fix; with the run-on-caller alternative the first sort() would succeed, so the test would assert success twice instead.

cp $REPRO/TestOfflineSorterRejectedSubmit.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.TestOfflineSorterRejectedSubmit -Ptests.seed=DEADBEEF
# fails after about 10 s; assertions off fails the same way: -Ptests.asserts=false (the recorded runs added --offline)

# gradle, stock 645d4fe14a20, -Ptests.seed=DEADBEEF (stack trimmed); the same with -Ptests.asserts=false
TestOfflineSorterRejectedSubmit > testSortAfterRejectedSubmit FAILED
    java.lang.AssertionError: second sort() still blocked after 10 s, expected RejectedExecutionException
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:871EC74E6A158128]:0)
        at org.apache.lucene.util.TestOfflineSorterRejectedSubmit.testSortAfterRejectedSubmit(TestOfflineSorterRejectedSubmit.java:61)

# where the blocked call sits (an independent public-API test, identical OfflineSorter.java, assertions off)
second sort() on shut-down executor: sort() did not return within 30 s; thread state=WAITING,
  blocked in Semaphore.acquire from OfflineSorter.readPartition=true, executor active=0 queued=0
    at java.base/java.util.concurrent.Semaphore.acquire(Semaphore.java:318)
    at org.apache.lucene.util.OfflineSorter.readPartition(OfflineSorter.java:432)
    at org.apache.lucene.util.OfflineSorter.sort(OfflineSorter.java:300)

# standalone runner, seed DEADBEEF: main 645d4fe14a20 fails with -ea and -da (about 11 s); release 10.6.0 fails;
# with the fix the test passes

• Intent, from the history: 25f1dd2f9b2 ("LUCENE-7792: add try/finally to make sure semaphore is released on exceptions", 2017-04-26, about three hours after the feature commit) added the releases now at OfflineSorter.java:301-304 and :479-484 and moved the task's release into finally (it wrote the readPartition release as a success flag checked in finally; #14913 rewrote it as a catch in 2025, with the same behaviour). Within one sort() call nothing acquires after either new release (the loop breaks, or sort() rethrows), so they only matter to later calls on the same instance: keeping the permits balanced across calls, failed ones included, was the intent. The rejected submit is the one exception path it missed.
• Contract: the constructor javadoc (:225-229): "If you pass a non-null ExecutorService then it will be used to run sorting operations that can be run concurrently, and maxPartitionsInRAM is the maximum concurrent in-memory partitions." The leak lowers that maximum silently, down to 0. ExecutorService.submit throws RejectedExecutionException "if the task cannot be scheduled for execution".
• Nothing says single use: sort() resets its state per call (:289), there is no close() and no "already used" check, and the sort() javadoc is only "Sort input to a new temp file, returning its name." (:286).
• Precedent: TaskExecutor catches RejectedExecutionException and runs the task on the caller "to ensure a rejecting executor only reduces parallelism and does not result in failure" (TaskExecutor.java:55-67; #10032 / LUCENE-8989, #13622).
• Tests: TestOfflineSorter uses only unbounded pools (LinkedBlockingQueue), builds a fresh sorter per test and covers neither a rejection nor reuse after a failure.

The strongest case for "intended" (rated moderate by the cross-model reviews; the devil's-advocate verifier found that none of its parts holds, the internal tag lowering only the priority): OfflineSorter is @lucene.experimental and @lucene.internal, the caller owns the executor and its capacity, every in-tree use is one-shot, and a maintainer could declare that a sorter must be thrown away after any exception; shutting down the executor you handed in is arguably misuse.

Why it fails: the internal tag speaks to API stability, not to the documented executor mode misbehaving; the 2017 follow-up shows the permits were meant to stay balanced across calls on exceptions; and even if reuse after a failure were declared unsupported, a silent, permanent drop of the documented concurrency limit (with k > 1 there is no exception at all) and a fail-fast exception turning into an indefinite wait are hard to call design. A docs-only resolution is still a plausible upstream outcome.

One fix was validated through gradle in a scratch worktree of 645d4fe14a20; running a rejected task on the caller is an alternative that was not run; a javadoc note is a complement only.

Wrap segments.add(exec.submit(job)) (OfflineSorter.java:311): when submit throws, the task will never run, so give its permit back before rethrowing. The merge hand-off (:398) needs no change: it holds no permit.

Callable<Partition> job = new SortPartitionTask(trackingDir, part);

Future<Partition> future;
try {
  future = exec.submit(job);
} catch (Throwable t) {
  // the task will never run, so its finally clause cannot release the permit
  if (partitionsInRAM != null) {
    partitionsInRAM.release();
  }
  throw t;
}
segments.add(future);

Trade-offs

• Only the path that leaks today changes; the failing call still throws the executor's exception, and the next call behaves like the first.
• Catching Throwable also covers an OutOfMemoryError thrown by submit (the same leak, by code reading only); catching only RejectedExecutionException would be narrower.
• An executor that threw from submit after it had already accepted the task would get a double release; the ExecutorService contract says rejection means the task "cannot be scheduled for execution", so this is theoretical.
• partitionsInRAM is never null (:250); the null check only mirrors the existing release sites.
• Scope: it covers a submit that throws. A rejection handler that drops the task without throwing (DiscardPolicy, DiscardOldestPolicy, or CallerRunsPolicy once the pool is shut down, as the JDK's ThreadPoolExecutor javadoc documents), or tasks removed by shutdownNow(), leave a future that never completes and a permit that never comes back; the sort() call that submitted the task then waits itself (for the future in getPartition, OfflineSorter.java:660-662, or for the permit in the next readPartition). By code reading, not run. No change at the submit site can see that; it is the documented effect of those handlers, not this bug.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF (2026-10-31): stock, the minimal test fails with assertions on and off. With the fix: the minimal test passes and TestOfflineSorter runs 15 tests, 2 nightly-only skipped, 0 failures, with assertions on and off (an independent re-run in another worktree gave the same result, the minimal test method taking 0.07 s); checkGoogleJavaFormat, forbiddenApisMain, forbiddenApisTest, ecjLintMain and ecjLintTest pass.
• Earlier checks: the same fix with the finder's test 20/20 over 10 iterations and in the standalone runner on 645d4fe14a20 with assertions on and off; an independent verifier's equivalent patch (same code, another variable name) with its 4-test class (including two rejections with maxPartitionsInRAM = 2 and the shut-down case) 12/12, and 4/4 at the adjudication.

On RejectedExecutionException, call the SortPartitionTask in sort() and wrap the result in a completed future; its finally then releases the permit. Treat the merge hand-off (:398) the same way for consistency.

Trade-offs

A rejecting executor then only reduces parallelism, as in TaskExecutor (TaskExecutor.java:55-67), and the first sort() succeeds too. But it changes visible behaviour: sort() would succeed on an executor that was shut down, which callers may use to stop work, and the regression test would have to assert success instead of the exception. Not validated.

A javadoc note on sort() or the 8-argument constructor.

Trade-offs

Leaves the silent loss of concurrency for maxPartitionsInRAM > 1 and the indefinite wait in place.

Method: formal (TLA+ model checking, then a public-API JUnit).

• Model. OfflineSortProto.tla models the main thread, the partitionsInRAM semaphore, a FIFO executor with W workers, the partition-sort and merge tasks, the merge cascade and the failure cleanup. Invariant PermitsBack: once sort() has ended and every task has finished, the permits equal maxPartitionsInRAM.
• Result. With "submit may be rejected" on, TLC reports a 4-state violation (acquire, submit rejected, cleanup, failed with 0 permits) in all 4 rejection configurations (W in {0, 1}, maxPartitionsInRAM in {1, 2}); without rejection it holds in all 24 configurations with one injected I/O error or interrupt.
• Confirmation. A JUnit on the stock main jar (a saturated bounded pool, then a retry) failed with assertions on and off and on releases back to 6.6.0. An independent reproducer, a devil's-advocate verifier, read-only cross-model reviews (OpenAI GPT-5.6), an adjudication and a credibility audit checked it; a follow-up ran the version history, a prior-report search and a security screen.