This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch 9.1.X in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 5061899e0965fb6e9e5d1479a1b51c75f73f0fe3 Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 15:05:34 2026 -0700 VarOpt: check region counts and the image size - Check the region counts against k: a sketch in sampling mode holds exactly k items, and one in warm-up holds at most k. - Check that the image holds the H-region weights. - Size the weight array to hCount, and the item, weight and mark lists to the items in the image. The ArrayLists grow as needed, so this does not change behavior. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../datasketches/sampling/VarOptItemsSketch.java | 18 ++-- .../sampling/VarOptCorruptImageTest.java | 98 ++++++++++++++++++++++ 2 files changed, 111 insertions(+), 5 deletions(-) diff --git a/src/main/java/org/apache/datasketches/sampling/VarOptItemsSketch.java b/src/main/java/org/apache/datasketches/sampling/VarOptItemsSketch.java index 121b6678a..1f3c05a9b 100644 --- a/src/main/java/org/apache/datasketches/sampling/VarOptItemsSketch.java +++ b/src/main/java/org/apache/datasketches/sampling/VarOptItemsSketch.java @@ -345,6 +345,11 @@ public final class VarOptItemsSketch<T> { final int preLongBytes = numPreLongs << 3; + // In sampling mode the sketch holds exactly k items; while warming up it holds at most k. + if (((rCount > 0) && (((long) hCount + rCount) != k)) || ((rCount == 0) && (hCount > k))) { + throw new SketchesArgumentException("Possible Corruption: H and R region counts " + hCount + " and " + + rCount + " are not valid for k = " + k); + } final int totalItems = hCount + rCount; int allocatedItems = k + 1; // default to full @@ -361,10 +366,13 @@ public final class VarOptItemsSketch<T> { } } - // allocate full-sized ArrayLists, but we store only hCount weights at any moment + // The ArrayLists grow as needed, so size them to the items in the image rather than to k. + // We store only hCount weights at any moment. final long weightOffsetBytes = TOTAL_WEIGHT_R_DOUBLE + (rCount > 0 ? Double.BYTES : 0); - final ArrayList<Double> weightList = new ArrayList<>(allocatedItems); - final double[] wts = new double[allocatedItems]; + Util.checkBounds(weightOffsetBytes, (long) hCount * Double.BYTES, srcSeg.byteSize()); + final int listCapacity = (int) Math.min(allocatedItems, (long) totalItems + 1); + final ArrayList<Double> weightList = new ArrayList<>(listCapacity); + final double[] wts = new double[hCount]; MemorySegment.copy(srcSeg, JAVA_DOUBLE_UNALIGNED, weightOffsetBytes, wts, 0, hCount); // can't use Arrays.asList(wts) since double[] rather than Double[] @@ -383,7 +391,7 @@ public final class VarOptItemsSketch<T> { if (isGadget) { final long markOffsetBytes = preLongBytes + ((long) hCount * Double.BYTES); markBytes = ArrayOfBooleansSerDe.computeBytesNeeded(hCount); - markList = new ArrayList<>(allocatedItems); + markList = new ArrayList<>(listCapacity); final ArrayOfBooleansSerDe booleansSerDe = new ArrayOfBooleansSerDe(); final Boolean[] markArray = booleansSerDe.deserializeFromMemorySegment( @@ -398,7 +406,7 @@ public final class VarOptItemsSketch<T> { final long offsetBytes = preLongBytes + ((long) hCount * Double.BYTES) + markBytes; final T[] data = serDe.deserializeFromMemorySegment(srcSeg.asSlice(offsetBytes), 0, totalItems); final List<T> wrappedData = Arrays.asList(data); - final ArrayList<T> dataList = new ArrayList<>(allocatedItems); + final ArrayList<T> dataList = new ArrayList<>(listCapacity); dataList.addAll(wrappedData.subList(0, hCount)); // Load items in R as needed diff --git a/src/test/java/org/apache/datasketches/sampling/VarOptCorruptImageTest.java b/src/test/java/org/apache/datasketches/sampling/VarOptCorruptImageTest.java new file mode 100644 index 000000000..706b58d85 --- /dev/null +++ b/src/test/java/org/apache/datasketches/sampling/VarOptCorruptImageTest.java @@ -0,0 +1,98 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.sampling; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.expectThrows; + +import java.lang.foreign.MemorySegment; + +import org.apache.datasketches.common.AllocationTracker; +import org.apache.datasketches.common.ArrayOfLongsSerDe; +import org.apache.datasketches.common.ByteArrayUtil; +import org.apache.datasketches.common.ResizeFactor; +import org.apache.datasketches.common.SketchesArgumentException; +import org.testng.annotations.Test; + +/** + * Checks that corrupt VarOptItemsSketch images are rejected without large allocations. + */ +public class VarOptCorruptImageTest { + private static final int K_INT = 4; + private static final int H_COUNT_INT = 16; + private final ArrayOfLongsSerDe serDe = new ArrayOfLongsSerDe(); + + private byte[] image(final int k, final int n, final ResizeFactor rf) { + final VarOptItemsSketch<Long> sk = VarOptItemsSketch.newInstance(k, rf); + for (long i = 0; i < n; i++) { sk.update(i, 1.0 + (i % 7)); } + return sk.toByteArray(serDe); + } + + private void checkRejected(final byte[] bytes) { + final long allocated = AllocationTracker.allocatedBytes( + () -> VarOptItemsSketch.heapify(MemorySegment.ofArray(bytes), serDe)); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + expectThrows(SketchesArgumentException.class, () -> VarOptItemsSketch.heapify(MemorySegment.ofArray(bytes), serDe)); + } + + @Test + public void checkValidImagesStillWork() { + for (final ResizeFactor rf : ResizeFactor.values()) { + for (final int n : new int[] {1, 10, 32, 50, 1000}) { + final VarOptItemsSketch<Long> sk = VarOptItemsSketch.heapify(MemorySegment.ofArray(image(32, n, rf)), serDe); + assertEquals(sk.getN(), n); + for (long i = 0; i < 100; i++) { sk.update(i, 2.0); } //grows as needed + assertEquals(sk.getN(), n + 100); + } + } + } + + @Test + public void checkLargeKInSamplingMode() { + final byte[] bytes = image(32, 1000, ResizeFactor.X8); + ByteArrayUtil.putIntLE(bytes, K_INT, 1 << 28); + checkRejected(bytes); + } + + @Test + public void checkLargeKInWarmupMode() { + final byte[] bytes = image(32, 10, ResizeFactor.X1); //X1 would allocate the full k at once + ByteArrayUtil.putIntLE(bytes, K_INT, 1 << 28); + final long allocated = AllocationTracker.allocatedBytes( + () -> VarOptItemsSketch.heapify(MemorySegment.ofArray(bytes), serDe)); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + final VarOptItemsSketch<Long> sk = VarOptItemsSketch.heapify(MemorySegment.ofArray(bytes), serDe); + assertEquals(sk.getK(), 1 << 28); + assertEquals(sk.getNumSamples(), 10); + sk.update(100L, 1.0); + assertEquals(sk.getNumSamples(), 11); + } + + @Test + public void checkCountsBeyondImage() { + final byte[] h = image(32, 10, ResizeFactor.X8); + ByteArrayUtil.putIntLE(h, H_COUNT_INT, 1 << 28); //more than k + checkRejected(h); + final byte[] h2 = image(1 << 30, 10, ResizeFactor.X8); //large legal k, so only the image size limits hCount + ByteArrayUtil.putIntLE(h2, H_COUNT_INT, 1 << 28); + checkRejected(h2); + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
