From: Robert Varga Date: Sat, 6 Nov 2021 15:04:48 +0000 (+0100) Subject: Add UnsignedLongBitmap X-Git-Tag: v4.0.7~40 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=3402cfce32b05957219e54754dd7ca5b0a54cd0e;hp=26b290518d362a85311c5b5591e3ef72e0772cf2 Add UnsignedLongBitmap Rather than using a ImmutableMap, we can do have a much denser representation with a specialized class. Here we are introducing an explicit UnsignedLongBitmap, which stores an array of longs and an array of booleans, ditching the intermediate objects. Also clean up error reporting, throwing an IOException instead of a VerifyException when things should go south unexpectedly. JIRA: CONTROLLER-2013 Change-Id: Ie64da0af68ea2898dc77368afd4fce8abd2cccea Signed-off-by: Robert Varga --- diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java index 72bab449f4..b00d25da68 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java @@ -19,6 +19,7 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata; import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap; import org.opendaylight.yangtools.concepts.Builder; import org.opendaylight.yangtools.concepts.Identifiable; @@ -39,7 +40,7 @@ final class FrontendHistoryMetadataBuilder implements Builder(meta.getClosedTransactions()); + closedTransactions = meta.getClosedTransactions().mutableCopy(); purgedTransactions = meta.getPurgedTransactions().mutableCopy(); closed = meta.isClosed(); } @@ -52,7 +53,7 @@ final class FrontendHistoryMetadataBuilder implements Builder closedTransactions; + private final @NonNull UnsignedLongBitmap closedTransactions; private final long historyId; private final long cookie; private final boolean closed; public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed, - final Map closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) { + final UnsignedLongBitmap closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) { this.historyId = historyId; this.cookie = cookie; this.closed = closed; - this.closedTransactions = ImmutableMap.copyOf(closedTransactions); + this.closedTransactions = requireNonNull(closedTransactions); this.purgedTransactions = requireNonNull(purgedTransactions); } @@ -52,7 +47,7 @@ public final class FrontendHistoryMetadata implements WritableObject { return closed; } - public ImmutableMap getClosedTransactions() { + public UnsignedLongBitmap getClosedTransactions() { return closedTransactions; } @@ -65,45 +60,43 @@ public final class FrontendHistoryMetadata implements WritableObject { WritableObjects.writeLongs(out, historyId, cookie); out.writeBoolean(closed); + final int closedSize = closedTransactions.size(); final int purgedSize = purgedTransactions.size(); - WritableObjects.writeLongs(out, closedTransactions.size(), purgedSize); - for (Entry e : closedTransactions.entrySet()) { - WritableObjects.writeLong(out, e.getKey().longValue()); - out.writeBoolean(e.getValue()); - } + WritableObjects.writeLongs(out, closedSize, purgedSize); + closedTransactions.writeEntriesTo(out, closedSize); purgedTransactions.writeRangesTo(out, purgedSize); } public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException { - byte header = WritableObjects.readLongHeader(in); - final long historyId = WritableObjects.readFirstLong(in, header); - final long cookie = WritableObjects.readSecondLong(in, header); + final byte firstHdr = WritableObjects.readLongHeader(in); + final long historyId = WritableObjects.readFirstLong(in, firstHdr); + final long cookie = WritableObjects.readSecondLong(in, firstHdr); final boolean closed = in.readBoolean(); - header = WritableObjects.readLongHeader(in); - long ls = WritableObjects.readFirstLong(in, header); - Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE); - final int csize = (int) ls; - - ls = WritableObjects.readSecondLong(in, header); - Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE); - final int psize = (int) ls; - - final Map closedTransactions = new HashMap<>(csize); - for (int i = 0; i < csize; ++i) { - final UnsignedLong key = UnsignedLong.fromLongBits(WritableObjects.readLong(in)); - final Boolean value = in.readBoolean(); - closedTransactions.put(key, value); - } - final var purgedTransactions = ImmutableUnsignedLongSet.readFrom(in, psize); + final byte secondHdr = WritableObjects.readLongHeader(in); + final int csize = verifySize(WritableObjects.readFirstLong(in, secondHdr)); + final int psize = verifySize(WritableObjects.readSecondLong(in, secondHdr)); - return new FrontendHistoryMetadata(historyId, cookie, closed, closedTransactions, purgedTransactions); + return new FrontendHistoryMetadata(historyId, cookie, closed, + UnsignedLongBitmap.readFrom(in, csize), + ImmutableUnsignedLongSet.readFrom(in, psize)); } @Override public String toString() { - return MoreObjects.toStringHelper(FrontendHistoryMetadata.class).add("historyId", historyId) - .add("cookie", cookie).add("closed", closed).add("closedTransactions", closedTransactions) - .add("purgedTransactions", purgedTransactions).toString(); + return MoreObjects.toStringHelper(FrontendHistoryMetadata.class) + .add("historyId", historyId) + .add("cookie", cookie) + .add("closed", closed) + .add("closedTransactions", closedTransactions) + .add("purgedTransactions", purgedTransactions) + .toString(); + } + + private static int verifySize(final long size) throws IOException { + if (size < 0 || size > Integer.MAX_VALUE) { + throw new IOException("Invalid size " + size); + } + return (int) size; } } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java new file mode 100644 index 0000000000..1d64e10e83 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java @@ -0,0 +1,281 @@ +/* + * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.cluster.datastore.utils; + +import static com.google.common.base.Verify.verify; +import static java.util.Objects.requireNonNull; + +import com.google.common.annotations.Beta; +import com.google.common.annotations.VisibleForTesting; +import com.google.common.collect.Maps; +import com.google.common.primitives.UnsignedLong; +import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; +import java.util.HashMap; +import java.util.Map; +import java.util.Map.Entry; +import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.concepts.WritableObjects; + +/** + * A more efficient equivalent of {@code ImmutableMap}. + */ +@Beta +public abstract class UnsignedLongBitmap implements Immutable { + @VisibleForTesting + static final class Regular extends UnsignedLongBitmap { + private final long[] keys; + private final boolean[] values; + + Regular(final long[] keys, final boolean[] values) { + this.keys = requireNonNull(keys); + this.values = requireNonNull(values); + verify(keys.length == values.length); + } + + @Override + public boolean isEmpty() { + return keys.length == 0; + } + + @Override + public int size() { + return keys.length; + } + + @Override + void writeEntriesTo(final DataOutput out) throws IOException { + for (int i = 0; i < keys.length; ++i) { + writeEntry(out, keys[i], values[i]); + } + } + + @Override + StringBuilder appendEntries(final StringBuilder sb) { + final int last = keys.length - 1; + for (int i = 0; i < last; ++i) { + appendEntry(sb, keys[i], values[i]).append(", "); + } + return appendEntry(sb, keys[last], values[last]); + } + + @Override + void putEntries(final HashMap ret) { + for (int i = 0; i < keys.length; ++i) { + ret.put(UnsignedLong.fromLongBits(keys[i]), values[i]); + } + } + + @Override + public int hashCode() { + return Arrays.hashCode(keys) ^ Arrays.hashCode(values); + } + + @Override + public boolean equals(final Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Regular)) { + return false; + } + final var other = (Regular) obj; + return Arrays.equals(keys, other.keys) && Arrays.equals(values, other.values); + } + } + + private static final class Singleton extends UnsignedLongBitmap { + private final long key; + private final boolean value; + + Singleton(final long key, final boolean value) { + this.key = key; + this.value = value; + } + + @Override + public boolean isEmpty() { + return false; + } + + @Override + public int size() { + return 1; + } + + @Override + void writeEntriesTo(final DataOutput out) throws IOException { + writeEntry(out, key, value); + } + + @Override + StringBuilder appendEntries(final StringBuilder sb) { + return sb.append(Long.toUnsignedString(key)).append('=').append(value); + } + + @Override + void putEntries(final HashMap ret) { + ret.put(UnsignedLong.fromLongBits(key), value); + } + + @Override + public int hashCode() { + return Long.hashCode(key) ^ Boolean.hashCode(value); + } + + @Override + public boolean equals(final Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Singleton)) { + return false; + } + final var other = (Singleton) obj; + return key == other.key && value == other.value; + } + } + + private static final @NonNull UnsignedLongBitmap EMPTY = new Regular(new long[0], new boolean[0]); + + private UnsignedLongBitmap() { + // Hidden on purpose + } + + public static @NonNull UnsignedLongBitmap of() { + return EMPTY; + } + + public static @NonNull UnsignedLongBitmap of(final long keyBits, final boolean value) { + return new Singleton(keyBits, value); + } + + public static @NonNull UnsignedLongBitmap copyOf(final Map map) { + final int size = map.size(); + switch (size) { + case 0: + return of(); + case 1: + final var entry = map.entrySet().iterator().next(); + return of(entry.getKey().longValue(), entry.getValue()); + default: + final var entries = new ArrayList<>(map.entrySet()); + entries.sort(Comparator.comparing(Entry::getKey)); + + final var keys = new long[size]; + final var values = new boolean[size]; + + int idx = 0; + for (var e : entries) { + keys[idx] = e.getKey().longValue(); + values[idx] = e.getValue(); + ++idx; + } + + return new Regular(keys, values); + } + } + + public abstract boolean isEmpty(); + + public abstract int size(); + + public final @NonNull HashMap mutableCopy() { + final int size = size(); + switch (size) { + case 0: + return new HashMap<>(); + default: + final var ret = Maps.newHashMapWithExpectedSize(size); + putEntries(ret); + return ret; + } + } + + public static @NonNull UnsignedLongBitmap readFrom(final @NonNull DataInput in, final int size) throws IOException { + switch (size) { + case 0: + return of(); + case 1: + return new Singleton(WritableObjects.readLong(in), in.readBoolean()); + default: + final var keys = new long[size]; + final var values = new boolean[size]; + for (int i = 0; i < size; ++i) { + keys[i] = WritableObjects.readLong(in); + values[i] = in.readBoolean(); + } + + // There should be no duplicates and the IDs need to be increasing + long prevKey = keys[0]; + for (int i = 1; i < size; ++i) { + final long key = keys[i]; + if (Long.compareUnsigned(prevKey, key) >= 0) { + throw new IOException("Key " + Long.toUnsignedString(key) + " may not be used after key " + + Long.toUnsignedString(prevKey)); + } + prevKey = key; + } + + return new Regular(keys, values); + } + } + + public void writeEntriesTo(final @NonNull DataOutput out, final int size) throws IOException { + if (size != size()) { + throw new IOException("Mismatched size: expected " + size() + ", got " + size); + } + writeEntriesTo(out); + } + + abstract void writeEntriesTo(@NonNull DataOutput out) throws IOException; + + abstract StringBuilder appendEntries(StringBuilder sb); + + abstract void putEntries(HashMap ret); + + /** + * {@inheritDoc} + * + *

+ * Implementations of this method return a deterministic value. + */ + @Override + public abstract int hashCode(); + + @Override + public abstract boolean equals(Object obj); + + @Override + public final String toString() { + return isEmpty() ? "{}" : appendEntries(new StringBuilder().append('{')).append('}').toString(); + } + + @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD", + justification = "https://github.com/spotbugs/spotbugs/issues/811") + private static StringBuilder appendEntry(final StringBuilder sb, final long key, final boolean value) { + return sb.append(Long.toUnsignedString(key)).append('=').append(value); + } + + @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD", + justification = "https://github.com/spotbugs/spotbugs/issues/811") + private static void writeEntry(final @NonNull DataOutput out, final long key, final boolean value) + throws IOException { + // FIXME: This serialization format is what we inherited. We could do better by storing the boolean in + // writeLong()'s flags. On the other had, we could also be writing longs by twos, which might be + // benefitial. + WritableObjects.writeLong(out, key); + out.writeBoolean(value); + } +} diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java index c02cea95b8..7daafcd786 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java @@ -13,7 +13,6 @@ import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertThrows; import static org.junit.Assert.assertTrue; -import com.google.common.collect.ImmutableMap; import com.google.common.primitives.UnsignedLong; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; @@ -31,6 +30,7 @@ import org.opendaylight.controller.cluster.access.concepts.FrontendType; import org.opendaylight.controller.cluster.access.concepts.MemberName; import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet; import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap; public class FrontendShardDataTreeSnapshotMetadataTest { @@ -108,8 +108,8 @@ public class FrontendShardDataTreeSnapshotMetadataTest { final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy(); return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), List.of( - new FrontendHistoryMetadata(num, num, true, ImmutableMap.of(UnsignedLong.ZERO, Boolean.TRUE), - purgedHistories))); + new FrontendHistoryMetadata(num, num, true, + UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, Boolean.TRUE)), purgedHistories))); } private static void testObject(final T object, final T equalObject) { diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java new file mode 100644 index 0000000000..fc0b4907b8 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java @@ -0,0 +1,150 @@ +/* + * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.cluster.datastore.utils; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotEquals; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertThrows; +import static org.junit.Assert.assertTrue; +import static org.mockito.Mockito.mock; + +import com.google.common.base.VerifyException; +import com.google.common.io.ByteStreams; +import com.google.common.primitives.UnsignedLong; +import java.io.DataOutput; +import java.io.IOException; +import java.util.Map; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.mockito.junit.MockitoJUnitRunner; +import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap.Regular; +import org.opendaylight.yangtools.concepts.WritableObjects; + +@RunWith(MockitoJUnitRunner.StrictStubs.class) +public class UnsignedLongBitmapTest { + @Test + public void testEmpty() throws IOException { + final var empty = UnsignedLongBitmap.of(); + assertTrue(empty.isEmpty()); + assertEquals(empty, empty); + assertSame(empty, UnsignedLongBitmap.copyOf(Map.of())); + assertEquals(Map.of(), empty.mutableCopy()); + assertEquals("{}", empty.toString()); + assertEquals(0, empty.hashCode()); + + final var ex = assertThrows(IOException.class, () -> empty.writeEntriesTo(mock(DataOutput.class), 1)); + assertEquals("Mismatched size: expected 0, got 1", ex.getMessage()); + + // Should not do anything + empty.writeEntriesTo(mock(DataOutput.class), 0); + + assertSame(empty, assertWriteToReadFrom(empty)); + } + + @Test + public void testSingleton() { + final var one = UnsignedLongBitmap.of(0, false); + assertFalse(one.isEmpty()); + assertEquals(1, one.size()); + assertEquals(one, one); + assertEquals(one, UnsignedLongBitmap.of(0, false)); + assertEquals(one, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false))); + assertEquals(Map.of(UnsignedLong.ZERO, false), one.mutableCopy()); + assertEquals("{0=false}", one.toString()); + assertEquals(1237, one.hashCode()); + + final var ex = assertThrows(IOException.class, () -> one.writeEntriesTo(mock(DataOutput.class), 0)); + assertEquals("Mismatched size: expected 1, got 0", ex.getMessage()); + + assertEquals(one, UnsignedLongBitmap.of(0, false)); + assertNotEquals(one, UnsignedLongBitmap.of(0, true)); + assertNotEquals(one, UnsignedLongBitmap.of(1, false)); + assertNotEquals(UnsignedLongBitmap.of(), one); + assertNotEquals(one, UnsignedLongBitmap.of()); + + assertWriteToReadFrom(one); + } + + @Test + public void testRegular() { + final var one = UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false, UnsignedLong.ONE, true)); + assertFalse(one.isEmpty()); + assertEquals(2, one.size()); + assertEquals(one, one); + assertEquals(one, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ONE, true, UnsignedLong.ZERO, false))); + assertEquals(Map.of(UnsignedLong.ZERO, false, UnsignedLong.ONE, true), one.mutableCopy()); + + assertNotEquals(one, + UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false, UnsignedLong.valueOf(2), true))); + assertEquals("{0=false, 1=true}", one.toString()); + assertEquals(40345, one.hashCode()); + + final var ex = assertThrows(IOException.class, () -> one.writeEntriesTo(mock(DataOutput.class), 1)); + assertEquals("Mismatched size: expected 2, got 1", ex.getMessage()); + + final var two = UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, true, UnsignedLong.ONE, false)); + assertFalse(two.isEmpty()); + assertEquals(2, two.size()); + assertEquals(two, two); + assertEquals(two, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, true, UnsignedLong.ONE, false))); + assertEquals("{0=true, 1=false}", two.toString()); + assertEquals(40549, two.hashCode()); + + assertNotEquals(one, two); + assertNotEquals(two, one); + + assertWriteToReadFrom(one); + assertWriteToReadFrom(two); + } + + private static UnsignedLongBitmap assertWriteToReadFrom(final UnsignedLongBitmap orig) { + final var dos = ByteStreams.newDataOutput(); + try { + orig.writeEntriesTo(dos); + } catch (IOException e) { + throw new AssertionError(e); + } + + final UnsignedLongBitmap copy; + try { + final var dis = ByteStreams.newDataInput(dos.toByteArray()); + copy = UnsignedLongBitmap.readFrom(dis, orig.size()); + assertThrows(IllegalStateException.class, () -> dis.readByte()); + } catch (IOException e) { + throw new AssertionError(e); + } + + assertEquals(orig, copy); + return copy; + } + + @Test + public void testKeyOrder() throws IOException { + assertInvalidKey(0); + assertInvalidKey(1); + } + + private static void assertInvalidKey(final long second) throws IOException { + final var out = ByteStreams.newDataOutput(); + WritableObjects.writeLong(out, 1); + out.writeBoolean(false); + WritableObjects.writeLong(out, second); + out.writeBoolean(true); + + final var ex = assertThrows(IOException.class, + () -> UnsignedLongBitmap.readFrom(ByteStreams.newDataInput(out.toByteArray()), 2)); + assertEquals("Key " + second + " may not be used after key 1", ex.getMessage()); + } + + @Test + public void testInvalidArrays() { + assertThrows(VerifyException.class, () -> new Regular(new long[0], new boolean[] { false, false })); + } +}