This is an automated email from the ASF dual-hosted git repository. chaokunyang pushed a commit to branch releases-0.11.0 in repository https://gitbox.apache.org/repos/asf/fory.git
commit a4593e0b7a8de0b6ed0f69421ad3d5ba7c847f42 Author: Leo <[email protected]> AuthorDate: Sat Jun 7 15:20:24 2025 +0800 fix(java): Use (long, long, byte) key for MetaStringBytes cache to prevent collisions (#2308) ## What does this PR do? This PR fixes a `ClassCastException` during deserialization caused by an incorrect `MetaStringBytes` being retrieved from the cache. The previous cache key `(long, long)` in `MetaStringResolver` (for small meta strings) didn't include the string's `encoding` byte, leading to collisions when different strings (e.g., "aclass" vs "Aclass") hashed to the same two longs. **Changes:** 1. **Introduced `LongLongByteMap`:** A new map using a `(long k1, long k2, byte k3)` key. 2. **Updated `MetaStringResolver`:** Modified relevant methods (e.g., `createSmallMetaStringBytes`, `readSmallMetaStringBytes`) to use `LongLongByteMap`, incorporating the `encoding` byte into the cache key for small meta strings. 3. **Renamed Test:** `LongLongMapTest.java` renamed to `LongLongByteMapTest.java` and updated to test the new map. ## Related issues - #2307 ## Does this PR introduce any user-facing change? <!-- If any user-facing interface changes, please [open an issue](https://github.com/apache/fory/issues/new/choose) describing the need to do so and update the document if necessary. --> - [ ] Does this PR introduce any public API change? - [ ] Does this PR introduce any binary protocol compatibility change? ## Benchmark <!-- When the PR has an impact on performance (if you don't know whether the PR will have an impact on performance, you can submit the PR first, and if it will have impact on performance, the code reviewer will explain it), be sure to attach a benchmark data here. --> --- LICENSE | 2 +- .../{LongLongMap.java => LongLongByteMap.java} | 65 +++++++++++----------- .../apache/fory/resolver/MetaStringResolver.java | 12 ++-- java/fory-core/src/main/resources/META-INF/LICENSE | 2 +- .../fory-core/native-image.properties | 2 +- ...ngLongMapTest.java => LongLongByteMapTest.java} | 28 +++++----- licenserc.toml | 2 +- 7 files changed, 56 insertions(+), 57 deletions(-) diff --git a/LICENSE b/LICENSE index e7e42105..0a90a1b4 100644 --- a/LICENSE +++ b/LICENSE @@ -270,7 +270,7 @@ The text of each license is also included in licenses/LICENSE-[project].txt. java/fory-core/src/main/java/org/apache/fory/collection/IdentityMap.java java/fory-core/src/main/java/org/apache/fory/collection/IdentityObjectIntMap.java java/fory-core/src/main/java/org/apache/fory/collection/LongMap.java - java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java + java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java java/fory-core/src/main/java/org/apache/fory/collection/ObjectIntMap.java java/fory-core/src/main/java/org/apache/fory/type/Generics.java java/fory-core/src/test/java/org/apache/fory/type/GenericsTest.java diff --git a/java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java b/java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java similarity index 71% rename from java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java rename to java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java index ee4d5257..dd26f794 100644 --- a/java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java +++ b/java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java @@ -19,38 +19,37 @@ package org.apache.fory.collection; -import static org.apache.fory.collection.ForyObjectMap.MASK_NUMBER; - import org.apache.fory.annotation.Internal; import org.apache.fory.util.Preconditions; /** - * A fast linear hash probe based map whose key is two long values `(long k1, long k2)`. This map - * can avoid creating a java object for key to save memory/cpu cost. + * A fast linear hash probe based map whose key is two long and a byte values `(long k1, long k2, + * byte k3)`. This map can avoid creating a java object for key to save memory/cpu cost. */ // The linear probed hash is derived from // https://github.com/EsotericSoftware/kryo/blob/135df69526615bb3f6b34846e58ba3fec3b631c3/src/com/esotericsoftware/kryo/util/IntMap.java. @SuppressWarnings("unchecked") @Internal -public final class LongLongMap<V> { - private static final class LongLongKey { +public final class LongLongByteMap<V> { + private static final class LongLongByteKey { private final long k1; + private final long k2; + private final byte k3; - public LongLongKey(long k1, long k2) { + public LongLongByteKey(long k1, long k2, byte k3) { this.k1 = k1; this.k2 = k2; + this.k3 = k3; } - private final long k2; - @Override public String toString() { - return "LongLongKey{" + "k1=" + k1 + ", k2=" + k2 + '}'; + return "LongLongByteKey{" + "k1=" + k1 + ", k2=" + k2 + ", k3=" + k3 + '}'; } } public int size; - LongLongKey[] keyTable; + LongLongByteKey[] keyTable; V[] valueTable; private final float loadFactor; private int threshold; @@ -65,7 +64,7 @@ public final class LongLongMap<V> { * * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. */ - public LongLongMap(int initialCapacity, float loadFactor) { + public LongLongByteMap(int initialCapacity, float loadFactor) { Preconditions.checkArgument( 0 <= loadFactor && loadFactor <= 1, "loadFactor %s must be > 0 and < 1", loadFactor); this.loadFactor = loadFactor; @@ -73,12 +72,12 @@ public final class LongLongMap<V> { threshold = (int) (tableSize * loadFactor); mask = tableSize - 1; shift = Long.numberOfLeadingZeros(mask); - keyTable = new LongLongKey[tableSize]; + keyTable = new LongLongByteKey[tableSize]; valueTable = (V[]) new Object[tableSize]; } - private int place(long k1, long k2) { - return (int) ((k1 * 31 + k2) * MASK_NUMBER >>> shift); + private int place(long k1, long k2, byte k3) { + return (int) ((k1 * 31 + k2 * 17 + k3) * ForyObjectMap.MASK_NUMBER >>> shift); } /** @@ -86,22 +85,22 @@ public final class LongLongMap<V> { * This can be overridden in this pacakge to compare for equality differently than {@link * Object#equals(Object)}. */ - private int locateKey(long k1, long k2) { - LongLongKey[] keyTable = this.keyTable; + private int locateKey(long k1, long k2, byte k3) { + LongLongByteKey[] keyTable = this.keyTable; int mask = this.mask; - for (int i = place(k1, k2); ; i = i + 1 & mask) { - LongLongKey other = keyTable[i]; + for (int i = place(k1, k2, k3); ; i = i + 1 & mask) { + LongLongByteKey other = keyTable[i]; if (other == null) { return -(i + 1); // Empty space is available. } - if (other.k1 == k1 && other.k2 == k2) { + if (other.k1 == k1 && other.k2 == k2 && other.k3 == k3) { return i; // Same key was found. } } } - public V put(long k1, long k2, V value) { - int i = locateKey(k1, k2); + public V put(long k1, long k2, byte k3, V value) { + int i = locateKey(k1, k2, k3); if (i >= 0) { // Existing key was found. V[] valueTable = this.valueTable; V oldValue = valueTable[i]; @@ -109,7 +108,7 @@ public final class LongLongMap<V> { return oldValue; } i = -(i + 1); // Empty space was found. - keyTable[i] = new LongLongKey(k1, k2); + keyTable[i] = new LongLongByteKey(k1, k2, k3); valueTable[i] = value; if (++size >= threshold) { resize(keyTable.length << 1); @@ -117,14 +116,14 @@ public final class LongLongMap<V> { return null; } - public V get(long k1, long k2) { - LongLongKey[] keyTable = this.keyTable; - for (int i = place(k1, k2); ; i = i + 1 & mask) { - LongLongKey other = keyTable[i]; + public V get(long k1, long k2, byte k3) { + LongLongByteKey[] keyTable = this.keyTable; + for (int i = place(k1, k2, k3); ; i = i + 1 & mask) { + LongLongByteKey other = keyTable[i]; if (other == null) { return null; } - if (other.k1 == k1 && other.k2 == k2) { + if (other.k1 == k1 && other.k2 == k2 && other.k3 == k3) { return valueTable[i]; } } @@ -135,17 +134,17 @@ public final class LongLongMap<V> { threshold = (int) (newSize * loadFactor); mask = newSize - 1; shift = Long.numberOfLeadingZeros(mask); - LongLongKey[] oldKeyTable = keyTable; + LongLongByteKey[] oldKeyTable = keyTable; V[] oldValueTable = valueTable; - keyTable = new LongLongKey[newSize]; + keyTable = new LongLongByteKey[newSize]; valueTable = (V[]) new Object[newSize]; if (size > 0) { for (int i = 0; i < oldCapacity; i++) { - LongLongKey key = oldKeyTable[i]; + LongLongByteKey key = oldKeyTable[i]; if (key != null) { - for (int j = place(key.k1, key.k2); ; j = (j + 1) & mask) { + for (int j = place(key.k1, key.k2, key.k3); ; j = (j + 1) & mask) { if (keyTable[j] == null) { - keyTable[j] = new LongLongKey(key.k1, key.k2); + keyTable[j] = new LongLongByteKey(key.k1, key.k2, key.k3); valueTable[j] = oldValueTable[i]; break; } diff --git a/java/fory-core/src/main/java/org/apache/fory/resolver/MetaStringResolver.java b/java/fory-core/src/main/java/org/apache/fory/resolver/MetaStringResolver.java index 006f18a2..3f070e97 100644 --- a/java/fory-core/src/main/java/org/apache/fory/resolver/MetaStringResolver.java +++ b/java/fory-core/src/main/java/org/apache/fory/resolver/MetaStringResolver.java @@ -20,7 +20,7 @@ package org.apache.fory.resolver; import java.util.Arrays; -import org.apache.fory.collection.LongLongMap; +import org.apache.fory.collection.LongLongByteMap; import org.apache.fory.collection.LongMap; import org.apache.fory.collection.ObjectMap; import org.apache.fory.memory.LittleEndian; @@ -46,8 +46,8 @@ public final class MetaStringResolver { new ObjectMap<>(initialCapacity, foryMapLoadFactor); private final LongMap<MetaStringBytes> hash2MetaStringBytesMap = new LongMap<>(initialCapacity, foryMapLoadFactor); - private final LongLongMap<MetaStringBytes> longLongMap = - new LongLongMap<>(initialCapacity, foryMapLoadFactor); + private final LongLongByteMap<MetaStringBytes> longLongByteMap = + new LongLongByteMap<>(initialCapacity, foryMapLoadFactor); // Every enum bytes should be singleton at every fory, since we keep state in it. private final ObjectMap<MetaString, MetaStringBytes> metaString2BytesMap = new ObjectMap<>(initialCapacity, foryMapLoadFactor); @@ -234,7 +234,7 @@ public final class MetaStringResolver { v1 = buffer.readInt64(); v2 = buffer.readBytesAsInt64(len - 8); } - MetaStringBytes byteString = longLongMap.get(v1, v2); + MetaStringBytes byteString = longLongByteMap.get(v1, v2, encoding); if (byteString == null) { byteString = createSmallMetaStringBytes(len, encoding, v1, v2); } @@ -258,7 +258,7 @@ public final class MetaStringResolver { if (cache.first8Bytes == v1 && cache.second8Bytes == v2) { return cache; } - MetaStringBytes byteString = longLongMap.get(v1, v2); + MetaStringBytes byteString = longLongByteMap.get(v1, v2, encoding); if (byteString == null) { byteString = createSmallMetaStringBytes(len, encoding, v1, v2); } @@ -273,7 +273,7 @@ public final class MetaStringResolver { hashCode = Math.abs(hashCode); hashCode = (hashCode & 0xffffffffffffff00L) | encoding; MetaStringBytes metaStringBytes = new MetaStringBytes(Arrays.copyOf(data, len), hashCode); - longLongMap.put(v1, v2, metaStringBytes); + longLongByteMap.put(v1, v2, encoding, metaStringBytes); return metaStringBytes; } diff --git a/java/fory-core/src/main/resources/META-INF/LICENSE b/java/fory-core/src/main/resources/META-INF/LICENSE index 8833fd92..f909f4fd 100644 --- a/java/fory-core/src/main/resources/META-INF/LICENSE +++ b/java/fory-core/src/main/resources/META-INF/LICENSE @@ -243,7 +243,7 @@ The text of each license is also included in licenses/LICENSE-[project].txt. java/fory-core/src/main/java/org/apache/fory/collection/IdentityMap.java java/fory-core/src/main/java/org/apache/fory/collection/IdentityObjectIntMap.java java/fory-core/src/main/java/org/apache/fory/collection/LongMap.java - java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java + java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java java/fory-core/src/main/java/org/apache/fory/collection/ObjectIntMap.java java/fory-core/src/main/java/org/apache/fory/type/Generics.java diff --git a/java/fory-core/src/main/resources/META-INF/native-image/org.apache.fory/fory-core/native-image.properties b/java/fory-core/src/main/resources/META-INF/native-image/org.apache.fory/fory-core/native-image.properties index c58d5de8..02f5ab3c 100644 --- a/java/fory-core/src/main/resources/META-INF/native-image/org.apache.fory/fory-core/native-image.properties +++ b/java/fory-core/src/main/resources/META-INF/native-image/org.apache.fory/fory-core/native-image.properties @@ -207,7 +207,7 @@ Args=--initialize-at-build-time=org.apache.fory.memory.MemoryBuffer,\ org.apache.fory.collection.IntArray,\ org.apache.fory.collection.LazyMap,\ org.apache.fory.collection.LongMap,\ - org.apache.fory.collection.LongLongMap,\ + org.apache.fory.collection.LongLongByteMap,\ org.apache.fory.collection.MapStatistics,\ org.apache.fory.collection.MultiKeyWeakMap,\ org.apache.fory.collection.ObjectArray,\ diff --git a/java/fory-core/src/test/java/org/apache/fory/collection/LongLongMapTest.java b/java/fory-core/src/test/java/org/apache/fory/collection/LongLongByteMapTest.java similarity index 60% rename from java/fory-core/src/test/java/org/apache/fory/collection/LongLongMapTest.java rename to java/fory-core/src/test/java/org/apache/fory/collection/LongLongByteMapTest.java index 6af16d77..7cc5911f 100644 --- a/java/fory-core/src/test/java/org/apache/fory/collection/LongLongMapTest.java +++ b/java/fory-core/src/test/java/org/apache/fory/collection/LongLongByteMapTest.java @@ -22,24 +22,24 @@ package org.apache.fory.collection; import org.testng.Assert; import org.testng.annotations.Test; -public class LongLongMapTest { +public class LongLongByteMapTest { @Test public void testPut() { - LongLongMap<String> map = new LongLongMap<>(10, 0.5f); - map.put(1, 1, "a"); - map.put(1, 2, "b"); - map.put(1, 3, "c"); - map.put(2, 1, "d"); - map.put(3, 1, "f"); - Assert.assertEquals(map.get(1, 1), "a"); - Assert.assertEquals(map.get(1, 2), "b"); - Assert.assertEquals(map.get(1, 3), "c"); - Assert.assertEquals(map.get(2, 1), "d"); - Assert.assertEquals(map.get(3, 1), "f"); + LongLongByteMap<String> map = new LongLongByteMap<>(10, 0.5f); + map.put(1, 1, (byte) 1, "a"); + map.put(1, 2, (byte) 2, "b"); + map.put(1, 3, (byte) 3, "c"); + map.put(2, 1, (byte) 4, "d"); + map.put(3, 1, (byte) 5, "f"); + Assert.assertEquals(map.get(1, 1, (byte) 1), "a"); + Assert.assertEquals(map.get(1, 2, (byte) 2), "b"); + Assert.assertEquals(map.get(1, 3, (byte) 3), "c"); + Assert.assertEquals(map.get(2, 1, (byte) 4), "d"); + Assert.assertEquals(map.get(3, 1, (byte) 5), "f"); for (int i = 1; i < 100; i++) { - map.put(i, i, "a" + i); - Assert.assertEquals(map.get(i, i), "a" + i); + map.put(i, i, (byte) i, "a" + i); + Assert.assertEquals(map.get(i, i, (byte) i), "a" + i); } } } diff --git a/licenserc.toml b/licenserc.toml index a638f57c..1cdae1e5 100644 --- a/licenserc.toml +++ b/licenserc.toml @@ -40,7 +40,7 @@ excludes = [ "java/fory-core/src/main/java/org/apache/fory/collection/IdentityMap.java", "java/fory-core/src/main/java/org/apache/fory/collection/IdentityObjectIntMap.java", "java/fory-core/src/main/java/org/apache/fory/collection/LongMap.java", - "java/fory-core/src/main/java/org/apache/fory/collection/LongLongMap.java", + "java/fory-core/src/main/java/org/apache/fory/collection/LongLongByteMap.java", "java/fory-core/src/main/java/org/apache/fory/collection/ObjectIntMap.java", "java/fory-core/src/main/java/org/apache/fory/io/ClassLoaderObjectInputStream.java", "java/fory-core/src/main/java/org/apache/fory/memory/MemoryBuffer.java", --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
