A query-cache history of 715,827,883 entries overflows an int, and the second distinct query loops forever

FrequencyTrackingRingBuffer, the history behind UsageTrackingQueryCachingPolicy, checks only maxSize >= 2 and sizes its open-addressing counting table as Math.max(2, maxSize * 3 / 2) in int. For maxSize = 715,827,883 the product maxSize * 3 = 2^31 + 1 wraps negative, so the table gets 2 slots. The constructor fills one with the filler value (Integer.MIN_VALUE for the policy), the first query's hash code takes the other, and IntBag.add for the next distinct hash code (distinct from the filler and from the first, as in the repro) has no free slot to stop at. onUse calls it inside synchronized (this), so with assertions disabled the second distinct cacheable query never returns, and every other thread that calls onUse or shouldCache on the policy for a cacheable query blocks; through IndexSearcher.search with an LRUQueryCache the second search hangs and a parallel search is BLOCKED. With assertions enabled, assert capacity > maxSize fails in the constructor. Every accepted size from 715,827,883 up gets a table no larger than the history (2 slots up to 1,431,655,767); 715,827,882 works, and Integer.MAX_VALUE fails loudly with OutOfMemoryError. The trigger needs the expert constructor with a history 2.8 million times the default (256) and a 2.86 GB history array; on main a query cache (for example LRUQueryCache) must also be installed (9.x and 10.x cache by default). Every release from 5.0.0 through 10.6.0, and main, is affected; rejecting sizes above Integer.MAX_VALUE / 3 in the constructor fixes it.

FrequencyTrackingRingBuffer.java:45-59 on main 645d4fe14a20: the constructor rejects only maxSize < 2, allocates the int[maxSize] history, builds IntBag(maxSize) and adds the filler (sentinel) maxSize times.

FrequencyTrackingRingBuffer.java:108-117 (end-of-line comments added):

IntBag(int maxSize) {
  // load factor of 2/3
  int capacity = Math.max(2, maxSize * 3 / 2);           // 715,827,883 * 3 wraps: -1,073,741,823 -> 2
  // round up to the next power of two
  capacity = Integer.highestOneBit(capacity - 1) << 1;   // 2
  assert capacity > maxSize;                              // fails only with -ea
  keys = new int[capacity];
  freqs = new int[capacity];
  mask = capacity - 1;                                    // 1
}

FrequencyTrackingRingBuffer.java:136-145: open addressing with no exit when every slot holds another key.

int add(int key) {
  for (int slot = key & mask; ; slot = (slot + 1) & mask) {
    if (freqs[slot] == 0) {
      keys[slot] = key;
      return freqs[slot] = 1;
    } else if (keys[slot] == key) {
      return ++freqs[slot];
    }
  }
}

frequency(int) (:125-133) has the same shape, so a shouldCache that got the lock could spin too (by reading; in the runs shouldCache blocks on the monitor).

1. After the constructor: table length 2; slot 0 holds Integer.MIN_VALUE with count 715,827,883, slot 1 is empty. ramBytesUsed() is 2,863,311,656 bytes, 4.000 bytes per entry, against the 16 to 28 the class javadoc promises.
2. onUse(f:a): the hash code -1,030,110,316 starts at slot 0 (taken by the filler) and lands in slot 1. Both slots are now taken.
3. onUse(f:b): FrequencyTrackingRingBuffer.add first drops the oldest history entry, a filler, which only lowers slot 0's count and frees nothing; then the hash code -1,744,932,716 starts at slot 0 and probes 0, 1, 0, 1, ... forever. A second thread calling shouldCache(f:a) is BLOCKED.

UsageTrackingQueryCachingPolicy.onUse (:141-159) computes the hash code outside the lock and calls recentlyUsedFilters.add(hashCode) inside synchronized (this) (:156-158); frequency (:161-172), used by shouldCache, takes the same monitor. LRUQueryCache calls onUse once per query and search (LRUQueryCache.java:812-813). The loop has no blocking call and checks nothing, so neither Thread.interrupt() nor a query timeout can end it (by reading).

Every accepted maxSize from 715,827,883 up gets a table no larger than maxSize: exactly 2 slots up to 1,431,655,767, then a power of two below maxSize (4 at 1,431,655,768, 134,217,728 for 1.5e9, 2^30 for 2e9). Above 1,431,655,767 the second distinct query still returns; by reading, a later one spins once the table is full (not executed). 715,827,882 is the largest size whose table is right (2^30 slots); it was run with a 13 GB heap and gave correct shouldCache answers. Integer.MAX_VALUE fails loudly, with OutOfMemoryError: Requested array size exceeds VM limit while allocating the history.

• Who. An application that calls new UsageTrackingQueryCachingPolicy(historySize) with 715,827,883 or more, on a heap that holds the 2.86 GB history (about 4 GB with the default G1 collector). On main the query cache is off by default (GITHUB#14187), so it must also install a query cache (for example LRUQueryCache); 9.x and 10.x install an LRUQueryCache by default, so setting the policy is enough there. Direct users of the public @lucene.internal FrequencyTrackingRingBuffer are hit the same way.
• Safe. IndexSearcher's default policy uses a history of 256, and every size from 2 to 715,827,882 gets a correctly sized table, given the heap for it (715,827,882 needed a 13 GB heap).
• Effect, assertions off. The search that records the second distinct cacheable query never returns and keeps one core busy; every other search that consults the same policy about a cacheable query blocks in onUse or shouldCache (a policy set with IndexSearcher.setDefaultQueryCachingPolicy is shared by every searcher created afterwards). Lucene throws nothing and logs nothing, and the stuck thread keeps its core until the JVM exits. The stuck search returns no result; the index is not touched.
• Effect, assertions on. A message-less AssertionError from the constructor.
• Likelihood: contrived. Nobody picks a history of 716 million queries by accident: the javadoc already warns about large histories, Integer.MAX_VALUE fails loudly with OutOfMemoryError, the downstream engines checked use the default constructor, and the documented searches found no public report since 5.0.0 (2015).

One JUnit Jupiter class, one method, public API only (it sits in org.apache.lucene.search but uses nothing package-private). No index, no searcher, no random values. assertTimeoutPreemptively runs the body on one daemon thread, because a hang can only be shown by bounding the wait; the spinning thread cannot be interrupted. The class does not extend Lucene's test base class, whose thread-leak checker would add a second, suite-level failure for that thread. PrefixQuery is used because onUse ignores TermQuery and other never-cached queries; 715,827,883 is the smallest overflowing size.

Heap. Under Lucene's gradle runner use -Ptests.heapsize=5g: with 4g the test JVM, which runs ParallelGC, failed with OutOfMemoryError while allocating the history array. A plain JVM with the default G1 collector needs about 4 GB.

Regression test: this same test, with one change for Lucene's build: its comment line is longer than 100 columns, so checkGoogleJavaFormat asks to wrap it after onUse(b). With the fix it passes even at the default 512 MB test heap, because the size is rejected before anything is allocated; without the fix it fails, by a timeout or AssertionError with enough heap, or by OutOfMemoryError with too little.

At the searcher level (an independent probe, not the repro): with setQueryCache(new LRUQueryCache(256, 50 MB)) and this policy on an IndexSearcher, the second search(new ConstantScoreQuery(new PrefixQuery(...)), 10) hangs and a parallel search is BLOCKED, on main and 10.5.2; with a history of 1,000,000 all searches return.

cp $REPRO/TestUsageTrackingPolicyHugeHistory.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestUsageTrackingPolicyHugeHistory -Ptests.seed=DEADBEEF -Ptests.heapsize=5g -Ptests.asserts=false
# 46 s in the recorded run (which also passed --no-daemon --offline -Ptests.jvms=1, on a built worktree); without -Ptests.asserts=false (assertions on) it fails with AssertionError (36 s)

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.heapsize=5g -Ptests.asserts=false
TestUsageTrackingPolicyHugeHistory > testSecondDistinctQueryReturns() FAILED
    org.opentest4j.AssertionFailedError: onUse must return ==> execution timed out after 30000 ms
        at app//org.junit.jupiter.api.Assertions.assertTimeoutPreemptively(Assertions.java:3590)
        at app//org.apache.lucene.search.TestUsageTrackingPolicyHugeHistory.testSecondDistinctQueryReturns(TestUsageTrackingPolicyHugeHistory.java:30)

        Caused by:
        org.junit.jupiter.api.timeout.PreemptiveTimeoutUtils$ExecutionTimeoutException: Execution timed out in thread junit-timeout-thread-1
            at app//org.apache.lucene.util.FrequencyTrackingRingBuffer$IntBag.add(FrequencyTrackingRingBuffer.java:137)
            at app//org.apache.lucene.util.FrequencyTrackingRingBuffer.add(FrequencyTrackingRingBuffer.java:77)
            at app//org.apache.lucene.search.UsageTrackingQueryCachingPolicy.onUse(UsageTrackingQueryCachingPolicy.java:157)
            at app//org.apache.lucene.search.TestUsageTrackingPolicyHugeHistory.lambda$testSecondDistinctQueryReturns$0(TestUsageTrackingPolicyHugeHistory.java:40)
1 test completed, 1 failed

# the same, assertions on (default)
TestUsageTrackingPolicyHugeHistory > testSecondDistinctQueryReturns() FAILED
    java.lang.AssertionError
        at org.apache.lucene.util.FrequencyTrackingRingBuffer$IntBag.<init>(FrequencyTrackingRingBuffer.java:113)
        at org.apache.lucene.util.FrequencyTrackingRingBuffer.<init>(FrequencyTrackingRingBuffer.java:52)
        at org.apache.lucene.search.UsageTrackingQueryCachingPolicy.<init>(UsageTrackingQueryCachingPolicy.java:105)
        at org.apache.lucene.search.TestUsageTrackingPolicyHugeHistory.lambda$testSecondDistinctQueryReturns$0(TestUsageTrackingPolicyHugeHistory.java:35)
1 test completed, 1 failed

# line 40 is the second onUse; the first (line 39) returned.
# release 10.6.0 (standalone runner): the same timeout in IntBag.add:137, and the same AssertionError at IntBag.<init>:113

• The class's own invariant breaks. IntBag's assert capacity > maxSize (FrequencyTrackingRingBuffer.java:113) states the invariant the int product breaks, and its javadoc says the maximum size "is known up-front" so there is "no need to worry about resizing" (:96-97). The class javadoc says it "requires 22 bytes per entry on average (between 16 and 28)" (:27); at 715,827,883 it allocates 4.000 bytes per entry. The buffer "will contain at most maxSize items" (:42-43); that still holds for the ring itself, but no javadoc states an upper limit, and the constructor checks only maxSize < 2.
• The warning is about tuning. "Beware of passing too large values for the size of the history": rarely used filters get cached, or filters are "slow to make it to the cache" (UsageTrackingQueryCachingPolicy.java:95-102). @param historySize gives no bound.
• Lucene rejects sizes it cannot handle elsewhere. PriorityQueue (PriorityQueue.java:121-124) and LongHeap (LongHeap.java:57-63) throw IllegalArgumentException "to prevent confusing OOME"; the internal hppc HashContainers throws BufferAllocationException when a table would exceed its maximum length (HashContainers.java:92-93). LUCENE-10607 (#11643), an int overflow at an extreme input size, was labelled type:bug and fixed in 9.3.
• Nothing covers it. TestFrequencyTrackingRingBuffer uses sizes up to 10,001; no Lucene code or test passes a history size other than the default 256 (the no-arg constructor's this(256)); the LUCENE-6118 review discussed only IntBag.remove.
• Out of scope, but a valid hardening fix. Lucene's SECURITY.md (line 46) says issues outside its security scope "are still valid bug reports and hardening suggestions"; its example, "a change that prevents an endless loop", is framed around broken indexes, and robustness improvements "must not slow down the hot paths". The recommended check runs once per constructor call, off the hot path.

The strongest case for "not a bug" (the devil's-advocate verifier): the javadoc already says "Beware of passing too large values"; the policy is @lucene.experimental and the buffer @lucene.internal; the size is absurd; the assert makes Lucene's own tests, which run with assertions on, fail fast; and on main the query cache is off by default. A committer could answer "don't do that". The hunt's own noise audit made this objection first ("absurd parameter") and then kept the bug, because the failure is a silent spin under a lock, not a loud one.

Why it fails: the warning names tuning costs, not a limit or a failure; @lucene.experimental is about API stability, not permission to hang, and the trigger is the public policy constructor; "absurd" argues for low impact, not for intent; an assertion is not argument validation, and production runs with assertions off, where the accepted value becomes a silent spin under a lock instead of an honest failure such as the OutOfMemoryError that Integer.MAX_VALUE gives. Verdict: a defect, small and low priority.

One fix was built and validated through gradle in a scratch worktree of 645d4fe14a20; the other options are sketches, not built.

Add a bound next to the existing maxSize < 2 check, before the history is allocated. It is the finder's fix (bound (1 << 30) / 3 * 2, the same 715,827,882) with the bound written as Integer.MAX_VALUE / 3 and the comment fitted to google-java-format.

  /** Largest supported {@code maxSize}: {@code IntBag} computes {@code maxSize * 3} as an int. */
  static final int MAX_SIZE = Integer.MAX_VALUE / 3;
  ...
    if (maxSize > MAX_SIZE) {
      throw new IllegalArgumentException(
          "maxSize must be at most " + MAX_SIZE + ", got " + maxSize);
    }

Trade-offs

• Changes only sizes whose table is no larger than the history. Before the fix they construct (assertions off) but work only while the table has a free slot: up to 1,431,655,767 that is one distinct hash code besides the filler, so the first onUse returns and the next distinct one spins. Now they fail at construction with "maxSize must be at most 715827882, got 715827883", without allocating the 2.86 GB history. 715,827,882 still works.
• Compatibility: it rejects one size a long-based sizing could serve, 715,827,883 (exact table 2^30 slots; the long-arithmetic option below). Every larger size would need 2^31 slots or more.
• One check covers the policy, direct users of the class and the StripedFrequencyTracker that open PR #16306 builds from it.
• No hot-path cost: the check runs once per constructor call. The limit could also be documented on the policy constructor's @param historySize (not written).

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle, OpenJDK 25.0.3, seed DEADBEEF. Stock: the repro fails with assertions on and off.
• With the fix: the repro, TestFrequencyTrackingRingBuffer, TestUsageTrackingFilterCachingPolicy and TestLRUQueryCache run 48 tests, 3 skipped (@AwaitsFix in TestLRUQueryCache), 0 failures, with assertions on and off; the repro alone passes at the default 512 MB test heap.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest of :lucene:core pass with the regression-test form of the repro (comment wrapped); that form fails on stock main both ways. The full upstream test suite was not run.

long capacity = Math.max(2, (long) maxSize * 3 / 2), round up with Long.highestOneBit, reject when it exceeds 2^30.

Trade-offs

Accepts exactly one more size, 715,827,883 (table 2^30), and rejects 715,827,884 and up, whose table would need 2^31 slots. Capping the table at 2^30 slots instead would accept sizes up to 2^30 - 1 but let the table run almost full, with long probe chains. Neither buys anything real over the recommended option. Not built.

Reject historySize above the bound in the policy constructor.

Trade-offs

Removes the public policy trigger but leaves the public @lucene.internal FrequencyTrackingRingBuffer, and the StripedFrequencyTracker of #16306, accepting broken sizes. Not built.

Defensive: throw instead of spinning when a probe comes back to its start slot.

Trade-offs

Guards against any future sizing slip, but adds work to every onUse and shouldCache and on its own still lets the constructor accept a size it cannot serve; if used, combine it with the recommended option. Not built.

Method: non-formal (bounded code reading with the array limits as preconditions, then dynamic checks).

• Reading. The sweep went through public API classes and the internal helpers behind them that no issue or PR had named, and checked every size computation against int range and the maximum array length. IntBag's maxSize * 3 / 2 overflows exactly above floor((2^31 - 1) / 3) = 715,827,882, well below the maximum array length, so the history array can still be allocated.
• Confirmation. A public-API program (new UsageTrackingQueryCachingPolicy(715_827_883), three distinct PrefixQuerys through onUse, bounded wait) hung at IntBag.add with assertions off on main, 10.5.2 and 9.12.3, and threw AssertionError with assertions on (main; the independent reproducer later ran -ea on 10.5.2 and 9.12.3); a size check made it pass.
• Earlier miss. An earlier hunt unit probed the class only with small sizes and with sizes of 2^30 and more, where allocation fails with OutOfMemoryError (judged expected); the window from 715,827,883 to about 1.07e9, where allocation succeeds and the table wraps, was not probed.
• Then an independent reproducer, a cross-model review (OpenAI GPT-5.6), a devil's-advocate verifier, an adjudication, a follow-up (history, prior reports, security), a credibility audit and a repro minimization followed.