You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2022/08/11 13:29:08 UTC
[lucene] branch branch_9_3 updated: LUCENE-10678: Fix potential overflow when computing the partition point on the BKD tree (#1065)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_9_3
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_9_3 by this push:
new 21f892d0969 LUCENE-10678: Fix potential overflow when computing the partition point on the BKD tree (#1065)
21f892d0969 is described below
commit 21f892d09698208ce146775e5b7641c554410002
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Thu Aug 11 15:25:53 2022 +0200
LUCENE-10678: Fix potential overflow when computing the partition point on the BKD tree (#1065)
We currently compute the partition point for a set of points by multiplying the number of nodes that needs to be on
the left of the BKD tree by the maxPointsInLeafNode. This multiplication is done on the integer space so if the partition point is bigger than Integer.MAX_VALUE it will overflow. This commit moves the multiplication to the long space so it doesn't overflow.
# Conflicts:
# lucene/CHANGES.txt
---
lucene/CHANGES.txt | 4 +++-
.../src/java/org/apache/lucene/util/bkd/BKDWriter.java | 2 +-
.../bkd/{Test2BBKDPoints.java => Test4BBKDPoints.java} | 14 +++++++-------
3 files changed, 11 insertions(+), 9 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 5bedb3fe497..662440ea113 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -7,7 +7,9 @@ http://s.apache.org/luceneversions
Bug Fixes
---------------------
-(No changes)
+
+* LUCENE-10678: Fix potential overflow when building a BKD tree with more than 4 billion points. The overflow
+ occurs when computing the partition point. (Ignacio Vera)
======================== Lucene 9.3.0 =======================
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
index 58f45df4077..16af10e2cd0 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
@@ -2018,7 +2018,7 @@ public class BKDWriter implements Closeable {
// How many leaves will be in the left tree:
final int numLeftLeafNodes = getNumLeftLeafNodes(numLeaves);
// How many points will be in the left tree:
- final long leftCount = numLeftLeafNodes * config.maxPointsInLeafNode;
+ final long leftCount = numLeftLeafNodes * (long) config.maxPointsInLeafNode;
BKDRadixSelector.PathSlice[] slices = new BKDRadixSelector.PathSlice[2];
diff --git a/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java b/lucene/core/src/test/org/apache/lucene/util/bkd/Test4BBKDPoints.java
similarity index 92%
rename from lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
rename to lucene/core/src/test/org/apache/lucene/util/bkd/Test4BBKDPoints.java
index 28bbf2da0ce..da20f914ad1 100644
--- a/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
+++ b/lucene/core/src/test/org/apache/lucene/util/bkd/Test4BBKDPoints.java
@@ -28,19 +28,19 @@ import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.tests.util.LuceneTestCase.Monster;
import org.apache.lucene.util.NumericUtils;
-// e.g. run like this: ant test -Dtestcase=Test2BBKDPoints -Dtests.nightly=true -Dtests.verbose=true
+// e.g. run like this: ant test -Dtestcase=Test4BBKDPoints -Dtests.nightly=true -Dtests.verbose=true
// -Dtests.monster=true
//
// or: python -u /l/util/src/python/repeatLuceneTest.py -heap 4g -once -nolog -tmpDir /b/tmp
-// -logDir /l/logs Test2BBKDPoints.test2D -verbose
+// -logDir /l/logs Test4BBKDPoints.test2D -verbose
@TimeoutSuite(millis = Integer.MAX_VALUE) // hopefully ~24 days is long enough ;)
@Monster("takes at least 4 hours and consumes many GB of temp disk space")
-public class Test2BBKDPoints extends LuceneTestCase {
+public class Test4BBKDPoints extends LuceneTestCase {
public void test1D() throws Exception {
- Directory dir = FSDirectory.open(createTempDir("2BBKDPoints1D"));
+ Directory dir = FSDirectory.open(createTempDir("4BBKDPoints1D"));
- final int numDocs = (Integer.MAX_VALUE / 26) + 100;
+ final int numDocs = (Integer.MAX_VALUE / 13) + 100;
BKDWriter w =
new BKDWriter(
@@ -83,9 +83,9 @@ public class Test2BBKDPoints extends LuceneTestCase {
}
public void test2D() throws Exception {
- Directory dir = FSDirectory.open(createTempDir("2BBKDPoints2D"));
+ Directory dir = FSDirectory.open(createTempDir("4BBKDPoints2D"));
- final int numDocs = (Integer.MAX_VALUE / 26) + 100;
+ final int numDocs = (Integer.MAX_VALUE / 13) + 100;
BKDWriter w =
new BKDWriter(