Return-Path: X-Original-To: apmail-cassandra-commits-archive@www.apache.org Delivered-To: apmail-cassandra-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 9050F1166B for ; Mon, 11 Aug 2014 01:11:35 +0000 (UTC) Received: (qmail 65713 invoked by uid 500); 11 Aug 2014 01:11:35 -0000 Delivered-To: apmail-cassandra-commits-archive@cassandra.apache.org Received: (qmail 65646 invoked by uid 500); 11 Aug 2014 01:11:35 -0000 Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@cassandra.apache.org Delivered-To: mailing list commits@cassandra.apache.org Received: (qmail 65546 invoked by uid 99); 11 Aug 2014 01:11:35 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 11 Aug 2014 01:11:35 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 13A819A9F90; Mon, 11 Aug 2014 01:11:35 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: aleksey@apache.org To: commits@cassandra.apache.org Date: Mon, 11 Aug 2014 01:11:35 -0000 Message-Id: In-Reply-To: References: X-Mailer: ASF-Git Admin Mailer Subject: [02/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/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/trunk Commit: 5bd37b92d2a8c75163ca51a0cfde908a299b7ca1 Parents: 4f475d1 Author: Sylvain Lebresne Authored: Fri Aug 8 10:21:34 2014 +0200 Committer: Sylvain Lebresne 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 { // 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 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 } /* - * 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 // 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 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 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);