You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by al...@apache.org on 2014/08/11 03:11:39 UTC
[06/18] git commit: Fix potential AssertionError in RangeTombstoneList
Fix potential AssertionError in RangeTombstoneList
patch by slebresne; reviewed by thobbs for CASSANDRA-7700
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/78952731
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/78952731
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/78952731
Branch: refs/heads/trunk
Commit: 78952731f320ed792783deea988164389794bb30
Parents: b70eaf3
Author: Sylvain Lebresne <sy...@datastax.com>
Authored: Fri Aug 8 10:21:34 2014 +0200
Committer: Sylvain Lebresne <sy...@datastax.com>
Committed: Fri Aug 8 17:46:17 2014 +0200
----------------------------------------------------------------------
CHANGES.txt | 1 +
.../apache/cassandra/db/RangeTombstoneList.java | 79 +++++++++++++++---
.../cassandra/db/RangeTombstoneListTest.java | 88 ++++++++++++++++++++
3 files changed, 157 insertions(+), 11 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/78952731/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 2c2ab71..fff06ae 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -6,6 +6,7 @@
* Fix UDT field selection with empty fields (CASSANDRA-7670)
* Bogus deserialization of static cells from sstable (CASSANDRA-7684)
Merged from 2.0:
+ * Fix potential AssertionError in RangeTombstoneList (CASSANDRA-7700)
* Validate arguments of blobAs* functions (CASSANDRA-7707)
* Fix potential AssertionError with 2ndary indexes (CASSANDRA-6612)
* Avoid logging CompactionInterrupted at ERROR (CASSANDRA-7694)
http://git-wip-us.apache.org/repos/asf/cassandra/blob/78952731/src/java/org/apache/cassandra/db/RangeTombstoneList.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/RangeTombstoneList.java b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
index 393ff3c..cbb4abe 100644
--- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java
+++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
@@ -168,7 +168,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable
{
// Note: insertFrom expect i to be the insertion point in term of interval ends
int pos = Arrays.binarySearch(ends, 0, size, start, comparator);
- insertFrom((pos >= 0 ? pos+1 : -pos-1), start, end, markedAt, delTime);
+ insertFrom((pos >= 0 ? pos : -pos-1), start, end, markedAt, delTime);
}
boundaryHeapSize += start.unsharedHeapSize() + end.unsharedHeapSize();
}
@@ -216,7 +216,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable
int j = 0;
while (i < size && j < tombstones.size)
{
- if (comparator.compare(tombstones.starts[j], ends[i]) < 0)
+ if (comparator.compare(tombstones.starts[j], ends[i]) <= 0)
{
insertFrom(i, tombstones.starts[j], tombstones.ends[j], tombstones.markedAts[j], tombstones.delTimes[j]);
j++;
@@ -517,16 +517,52 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable
}
/*
- * Inserts a new element starting at index i. This method assumes that i is the insertion point
- * in term of intervals for start:
- * ends[i-1] <= start < ends[i]
+ * Inserts a new element starting at index i. This method assumes that:
+ * ends[i-1] <= start <= ends[i]
+ *
+ * A RangeTombstoneList is a list of range [s_0, e_0]...[s_n, e_n] such that:
+ * - s_i <= e_i
+ * - e_i <= s_i+1
+ * - if s_i == e_i and e_i == s_i+1 then s_i+1 < e_i+1
+ * Basically, range are non overlapping except for their bound and in order. And while
+ * we allow ranges with the same value for the start and end, we don't allow repeating
+ * such range (so we can't have [0, 0][0, 0] even though it would respect the first 2
+ * conditions).
+ *
*/
private void insertFrom(int i, Composite start, Composite end, long markedAt, int delTime)
{
while (i < size)
{
- assert i == 0 || comparator.compare(start, ends[i-1]) >= 0;
- assert i >= size || comparator.compare(start, ends[i]) < 0;
+ assert i == 0 || comparator.compare(ends[i-1], start) <= 0;
+
+ int c = comparator.compare(start, ends[i]);
+ assert c <= 0;
+ if (c == 0)
+ {
+ // If start == ends[i], then we can insert from the next one (basically the new element
+ // really start at the next element), except for the case where starts[i] == ends[i].
+ // In this latter case, if we were to move to next element, we could end up with ...[x, x][x, x]...
+ if (comparator.compare(starts[i], ends[i]) == 0)
+ {
+ // The current element cover a single value which is equal to the start of the inserted
+ // element. If the inserted element overwrites the current one, just remove the current
+ // (it's included in what we insert) and proceed with the insert.
+ if (markedAt > markedAts[i])
+ {
+ removeInternal(i);
+ continue;
+ }
+
+ // Otherwise (the current singleton interval override the new one), we want to leave the
+ // current element and move to the next, unless start == end since that means the new element
+ // is in fact fully covered by the current one (so we're done)
+ if (comparator.compare(start, end) == 0)
+ return;
+ }
+ i++;
+ continue;
+ }
// Do we overwrite the current element?
if (markedAt > markedAts[i])
@@ -544,11 +580,18 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable
// now, start <= starts[i]
- // If the new element stops before the current one, insert it and
- // we're done
- if (comparator.compare(end, starts[i]) <= 0)
+ // Does the new element stops before/at the current one,
+ int endCmp = comparator.compare(end, starts[i]);
+ if (endCmp <= 0)
{
- addInternal(i, start, end, markedAt, delTime);
+ // Here start <= starts[i] and end <= starts[i]
+ // This means the current element is before the current one. However, one special
+ // case is if end == starts[i] and starts[i] == ends[i]. In that case,
+ // the new element entirely overwrite the current one and we can just overwrite
+ if (endCmp == 0 && comparator.compare(starts[i], ends[i]) == 0)
+ setInternal(i, start, end, markedAt, delTime);
+ else
+ addInternal(i, start, end, markedAt, delTime);
return;
}
@@ -640,6 +683,20 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable
size++;
}
+ private void removeInternal(int i)
+ {
+ assert i >= 0;
+
+ System.arraycopy(starts, i+1, starts, i, size - i - 1);
+ System.arraycopy(ends, i+1, ends, i, size - i - 1);
+ System.arraycopy(markedAts, i+1, markedAts, i, size - i - 1);
+ System.arraycopy(delTimes, i+1, delTimes, i, size - i - 1);
+
+ --size;
+ starts[size] = null;
+ ends[size] = null;
+ }
+
/*
* Grow the arrays, leaving index i "free" in the process.
*/
http://git-wip-us.apache.org/repos/asf/cassandra/blob/78952731/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
index faa15f0..798ce91 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
@@ -31,6 +31,7 @@ import org.apache.cassandra.utils.ByteBufferUtil;
public class RangeTombstoneListTest
{
private static final Comparator<Composite> cmp = new SimpleDenseCellNameType(IntegerType.instance);
+ private static final Random rand = new Random();
@Test
public void sortedAdditionTest()
@@ -290,16 +291,103 @@ public class RangeTombstoneListTest
assertEquals(6, l.maxMarkedAt());
}
+ private RangeTombstoneList makeRandom(int size, int maxItSize, int maxItDistance, int maxMarkedAt)
+ {
+ RangeTombstoneList l = new RangeTombstoneList(cmp, size);
+
+ int prevStart = -1;
+ int prevEnd = 0;
+ for (int i = 0; i < size; i++)
+ {
+ int nextStart = prevEnd + rand.nextInt(maxItDistance);
+ int nextEnd = nextStart + rand.nextInt(maxItSize);
+
+ // We can have an interval [x, x], but not 2 consecutives ones for the same x
+ if (nextEnd == nextStart && prevEnd == prevStart && prevEnd == nextStart)
+ nextEnd += 1 + rand.nextInt(maxItDistance);
+
+ l.add(rt(nextStart, nextEnd, rand.nextInt(maxMarkedAt)));
+
+ prevStart = nextStart;
+ prevEnd = nextEnd;
+ }
+ return l;
+ }
+
+ @Test
+ public void addAllRandomTest() throws Throwable
+ {
+ int TEST_COUNT = 1000;
+ int MAX_LIST_SIZE = 50;
+
+ int MAX_IT_SIZE = 20;
+ int MAX_IT_DISTANCE = 10;
+ int MAX_MARKEDAT = 10;
+
+ for (int i = 0; i < TEST_COUNT; i++)
+ {
+ RangeTombstoneList l1 = makeRandom(rand.nextInt(MAX_LIST_SIZE) + 1, rand.nextInt(MAX_IT_SIZE) + 1, rand.nextInt(MAX_IT_DISTANCE) + 1, rand.nextInt(MAX_MARKEDAT) + 1);
+ RangeTombstoneList l2 = makeRandom(rand.nextInt(MAX_LIST_SIZE) + 1, rand.nextInt(MAX_IT_SIZE) + 1, rand.nextInt(MAX_IT_DISTANCE) + 1, rand.nextInt(MAX_MARKEDAT) + 1);
+
+ RangeTombstoneList l1Initial = l1.copy();
+
+ try
+ {
+ // We generate the list randomly, so "all" we check is that the resulting range tombstone list looks valid.
+ l1.addAll(l2);
+ assertValid(l1);
+ }
+ catch (Throwable e)
+ {
+ System.out.println("Error merging:");
+ System.out.println(" l1: " + toString(l1Initial));
+ System.out.println(" l2: " + toString(l2));
+ throw e;
+ }
+ }
+ }
+
private static void assertRT(RangeTombstone expected, RangeTombstone actual)
{
assertEquals(String.format("Expected %s but got %s", toString(expected), toString(actual)), expected, actual);
}
+ private static void assertValid(RangeTombstoneList l)
+ {
+ // We check that ranges are in the right order and that we never have something
+ // like ...[x, x][x, x] ...
+ int prevStart = -2;
+ int prevEnd = -1;
+ for (RangeTombstone rt : l)
+ {
+ int curStart = i(rt.min);
+ int curEnd = i(rt.max);
+
+ assertTrue("Invalid " + toString(l), prevEnd <= curStart);
+ assertTrue("Invalid " + toString(l), curStart <= curEnd);
+
+ if (curStart == curEnd && prevEnd == curStart)
+ assertTrue("Invalid " + toString(l), prevStart != prevEnd);
+
+ prevStart = curStart;
+ prevEnd = curEnd;
+ }
+ }
+
private static String toString(RangeTombstone rt)
{
return String.format("[%d, %d]@%d", i(rt.min), i(rt.max), rt.data.markedForDeleteAt);
}
+ private static String toString(RangeTombstoneList l)
+ {
+ StringBuilder sb = new StringBuilder();
+ sb.append("{");
+ for (RangeTombstone rt : l)
+ sb.append(" ").append(toString(rt));
+ return sb.append(" }").toString();
+ }
+
private static Composite b(int i)
{
return Util.cellname(i);