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 c95fb7c9019b342a3406feafa4d2daf39791979f Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 14:28:46 2026 -0700 Frequencies: check map sizes and item counts in binary images In FrequentLongsSketch.getInstance(MemorySegment) and FrequentItemsSketch.getInstance(MemorySegment, serDe): - Check that LG_MIN_MAP_SIZE <= lgCurMapSize <= lgMaxMapSize, and that activeItems is between 0 and the capacity of the current map, as C++ check_size() does. - Check, in long arithmetic, that the image holds the declared arrays. - Rebuild the sketch into a map just large enough for the active items. The map grows as needed. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../frequencies/FrequentItemsSketch.java | 15 ++++--- .../frequencies/FrequentLongsSketch.java | 15 ++++--- .../org/apache/datasketches/frequencies/Util.java | 36 +++++++++++++++ .../datasketches/frequencies/ItemsSketchTest.java | 33 ++++++++++++++ .../datasketches/frequencies/LongsSketchTest.java | 51 ++++++++++++++++++++++ 5 files changed, 138 insertions(+), 12 deletions(-) diff --git a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java index 29967491f..a662a9e10 100644 --- a/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java +++ b/src/main/java/org/apache/datasketches/frequencies/FrequentItemsSketch.java @@ -43,6 +43,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs; import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer; import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE; import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE; +import static org.apache.datasketches.frequencies.Util.checkMapSizes; import static org.apache.datasketches.frequencies.Util.checkStreamWeight; import java.lang.foreign.MemorySegment; @@ -275,17 +276,19 @@ public class FrequentItemsSketch<T> { MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs); checkStreamWeight(preArr[2]); - final FrequentItemsSketch<T> fis = new FrequentItemsSketch<>(lgMaxMapSize, lgCurMapSize); - fis.streamWeight = 0; //update after - fis.offset = preArr[3]; - final int preBytes = preLongs << 3; final int activeItems = extractActiveItems(preArr[1]); + final int lgStartMapSize = + checkMapSizes(lgMaxMapSize, lgCurMapSize, activeItems, ReversePurgeItemHashMap.getLoadFactor()); + final long reqBytes = (preBytes + ((long)activeItems * Long.BYTES)); //count Arr only + checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity before allocating + + final FrequentItemsSketch<T> fis = new FrequentItemsSketch<>(lgMaxMapSize, lgStartMapSize); + fis.streamWeight = 0; //update after + fis.offset = preArr[3]; //Get countArray final long[] countArray = new long[activeItems]; - final long reqBytes = (preBytes + ((long)activeItems * Long.BYTES)); //count Arr only - checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, preBytes, countArray, 0, activeItems); diff --git a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java index 4d5935d76..81da5c8b9 100644 --- a/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java +++ b/src/main/java/org/apache/datasketches/frequencies/FrequentLongsSketch.java @@ -42,6 +42,7 @@ import static org.apache.datasketches.frequencies.PreambleUtil.insertPreLongs; import static org.apache.datasketches.frequencies.PreambleUtil.insertSerVer; import static org.apache.datasketches.frequencies.Util.LG_MIN_MAP_SIZE; import static org.apache.datasketches.frequencies.Util.SAMPLE_SIZE; +import static org.apache.datasketches.frequencies.Util.checkMapSizes; import static org.apache.datasketches.frequencies.Util.checkStreamWeight; import java.lang.foreign.MemorySegment; @@ -278,17 +279,19 @@ public class FrequentLongsSketch { MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, 0, preArr, 0, preLongs); checkStreamWeight(preArr[2]); - final FrequentLongsSketch fls = new FrequentLongsSketch(lgMaxMapSize, lgCurMapSize); - fls.streamWeight = 0; //update after - fls.offset = preArr[3]; - final int preBytes = preLongs << 3; final int activeItems = extractActiveItems(preArr[1]); + final int lgStartMapSize = + checkMapSizes(lgMaxMapSize, lgCurMapSize, activeItems, ReversePurgeLongHashMap.getLoadFactor()); + final long reqBytes = preBytes + (2L * activeItems * Long.BYTES); //count Arr + Items Arr + checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity before allocating + + final FrequentLongsSketch fls = new FrequentLongsSketch(lgMaxMapSize, lgStartMapSize); + fls.streamWeight = 0; //update after + fls.offset = preArr[3]; //Get countArray final long[] countArray = new long[activeItems]; - final int reqBytes = preBytes + (2 * activeItems * Long.BYTES); //count Arr + Items Arr - checkBounds(0, reqBytes, srcSeg.byteSize()); //check MemorySegment capacity MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, preBytes, countArray, 0, activeItems); //Get itemArray diff --git a/src/main/java/org/apache/datasketches/frequencies/Util.java b/src/main/java/org/apache/datasketches/frequencies/Util.java index f17d98402..bbdadd59a 100644 --- a/src/main/java/org/apache/datasketches/frequencies/Util.java +++ b/src/main/java/org/apache/datasketches/frequencies/Util.java @@ -53,6 +53,42 @@ final class Util { return key; } + /** + * Checks the map sizes and the number of active items read from the serialized image of a + * non-empty sketch, and returns the log2 size of the map to rebuild the sketch into. + * + * <p>The returned size is just large enough to hold the active items, and no larger than + * <i>lgCurMapSize</i>. The map then grows as needed while the items are inserted, so the memory + * allocated is bounded by the size of the image, not by the declared map size.</p> + * + * @param lgMaxMapSize log2 of the maximum map size + * @param lgCurMapSize log2 of the current map size + * @param activeItems the number of active items + * @param loadFactor the load factor of the hash map + * @return log2 of the map size to rebuild into + * @throws SketchesArgumentException if the values are not consistent + */ + static int checkMapSizes(final int lgMaxMapSize, final int lgCurMapSize, final int activeItems, + final double loadFactor) { + if (lgCurMapSize < LG_MIN_MAP_SIZE) { + throw new SketchesArgumentException( + "Possible Corruption: LgCurMapSize must be at least " + LG_MIN_MAP_SIZE + ": " + lgCurMapSize); + } + if (lgCurMapSize > lgMaxMapSize) { + throw new SketchesArgumentException( + "Possible Corruption: LgCurMapSize must not exceed LgMaxMapSize: " + + lgCurMapSize + " > " + lgMaxMapSize); + } + final long maxActive = (long) ((1L << Math.min(lgCurMapSize, 62)) * loadFactor); + if ((activeItems < 0) || (activeItems > maxActive)) { + throw new SketchesArgumentException( + "Possible Corruption: ActiveItems exceeds map capacity: " + activeItems); + } + int lgStart = LG_MIN_MAP_SIZE; + while ((lgStart < lgCurMapSize) && (((1L << lgStart) * loadFactor) < activeItems)) { lgStart++; } + return lgStart; + } + /** * Checks the stream weight read from the serialized image of a non-empty sketch. * @param streamWeight the stream weight diff --git a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java index 73583a3ae..d0507f768 100644 --- a/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java +++ b/src/test/java/org/apache/datasketches/frequencies/ItemsSketchTest.java @@ -506,4 +506,37 @@ public class ItemsSketchTest { static void println(final String s) { //System.out.println(s); //disable here } + + private static byte[] itemsImage() { + final FrequentItemsSketch<Long> fis = new FrequentItemsSketch<>(1 << 10); + for (long i = 0; i < 5; i++) { fis.update(i, i + 1); } + return fis.toByteArray(new ArrayOfLongsSerDe()); + } + + @Test + public void checkBinaryDeserLargeDeclaredMapDoesNotAllocate() { + final byte[] bytes = itemsImage(); + bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30; + bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30; + final MemorySegment seg = MemorySegment.ofArray(bytes); + final long allocated = org.apache.datasketches.common.AllocationTracker.allocatedBytes( + () -> FrequentItemsSketch.getInstance(seg, new ArrayOfLongsSerDe())); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + final FrequentItemsSketch<Long> fis = FrequentItemsSketch.getInstance(seg, new ArrayOfLongsSerDe()); + assertEquals(fis.getNumActiveItems(), 5); + assertEquals(fis.getEstimate(4L), 5); + } + + @Test + public void checkBinaryDeserInconsistentSizes() { + final byte[] curTooBig = itemsImage(); + curTooBig[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = (byte) (curTooBig[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] + 1); + final byte[] tooManyActive = itemsImage(); + org.apache.datasketches.common.ByteArrayUtil.putIntLE(tooManyActive, 8, 1 << 20); + for (final byte[] b : new byte[][] {curTooBig, tooManyActive}) { + try { FrequentItemsSketch.getInstance(MemorySegment.ofArray(b), new ArrayOfLongsSerDe()); fail(); } + catch (final SketchesArgumentException e) { } + } + } + } diff --git a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java index b6527b178..6326f499e 100644 --- a/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java +++ b/src/test/java/org/apache/datasketches/frequencies/LongsSketchTest.java @@ -796,4 +796,55 @@ public class LongsSketchTest { return new FrequentLongsSketch(maxMapSize); } + + private static byte[] longsImage() { + final FrequentLongsSketch fls = new FrequentLongsSketch(1 << 10); + for (int i = 0; i < 5; i++) { fls.update(i, i + 1); } + return fls.toByteArray(); + } + + @Test + public void checkBinaryDeserLargeDeclaredMapDoesNotAllocate() { + final byte[] bytes = longsImage(); + bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30; + bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30; + final MemorySegment seg = MemorySegment.ofArray(bytes); + final long allocated = org.apache.datasketches.common.AllocationTracker.allocatedBytes( + () -> FrequentLongsSketch.getInstance(seg)); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + final FrequentLongsSketch fls = FrequentLongsSketch.getInstance(seg); + assertEquals(fls.getNumActiveItems(), 5); + assertEquals(fls.getEstimate(4), 5); + } + + @Test + public void checkBinaryDeserInconsistentSizes() { + final byte[] curTooBig = longsImage(); + curTooBig[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = (byte) (curTooBig[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] + 1); + final byte[] curTooSmall = longsImage(); + curTooSmall[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 2; + final byte[] tooManyActive = longsImage(); + org.apache.datasketches.common.ByteArrayUtil.putIntLE(tooManyActive, 8, 1 << 20); + final byte[] negActive = longsImage(); + org.apache.datasketches.common.ByteArrayUtil.putIntLE(negActive, 8, -1); + for (final byte[] b : new byte[][] {curTooBig, curTooSmall, tooManyActive, negActive}) { + try { FrequentLongsSketch.getInstance(MemorySegment.ofArray(b)); fail(); } + catch (final SketchesArgumentException e) { } + } + } + + @Test + public void checkBinaryDeserActiveItemsBeyondImage() { + final byte[] bytes = longsImage(); + bytes[PreambleUtil.LG_MAX_MAP_SIZE_BYTE] = 30; + bytes[PreambleUtil.LG_CUR_MAP_SIZE_BYTE] = 30; + org.apache.datasketches.common.ByteArrayUtil.putIntLE(bytes, 8, 1 << 28); //more items than the image holds + final MemorySegment seg = MemorySegment.ofArray(bytes); + final long allocated = org.apache.datasketches.common.AllocationTracker.allocatedBytes( + () -> FrequentLongsSketch.getInstance(seg)); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + try { FrequentLongsSketch.getInstance(seg); fail(); } + catch (final SketchesArgumentException e) { } + } + } --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
