cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From alek...@apache.org
Subject [02/17] git commit: Fix potential AssertionError in RangeTombstoneList
Date Sun, 10 Aug 2014 22:07:47 GMT
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/5bd37b92
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/5bd37b92
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/5bd37b92

Branch: refs/heads/cassandra-2.1
Commit: 5bd37b92d2a8c75163ca51a0cfde908a299b7ca1
Parents: 4f475d1
Author: Sylvain Lebresne <sylvain@datastax.com>
Authored: Fri Aug 8 10:21:34 2014 +0200
Committer: Sylvain Lebresne <sylvain@datastax.com>
Committed: Fri Aug 8 10:21:34 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/5bd37b92/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index b03e250..9c78d07 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 2.0.10
+ * 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/5bd37b92/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 dad9004..dadcc20 100644
--- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java
+++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
@@ -138,7 +138,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
         {
             // 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);
         }
     }
 
@@ -185,7 +185,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
             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++;
@@ -380,16 +380,52 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
     }
 
     /*
-     * 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, ByteBuffer start, ByteBuffer 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])
@@ -407,11 +443,18 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
 
                 // 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;
                 }
 
@@ -503,6 +546,20 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
         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/5bd37b92/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 dc9f9c4..b0065e0 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
@@ -30,6 +30,7 @@ import org.apache.cassandra.utils.ByteBufferUtil;
 public class RangeTombstoneListTest
 {
     private static final Comparator<ByteBuffer> cmp = IntegerType.instance;
+    private static final Random rand = new Random();
 
     @Test
     public void sortedAdditionTest()
@@ -295,16 +296,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 ByteBuffer b(int i)
     {
         return ByteBufferUtil.bytes(i);


Mime
View raw message