You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by sl...@apache.org on 2013/10/23 16:17:11 UTC
[1/4] git commit: 6233
Updated Branches:
refs/heads/cassandra-2.0 1240c9bd2 -> 322f9a983
6233
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/86b26b67
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/86b26b67
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/86b26b67
Branch: refs/heads/cassandra-2.0
Commit: 86b26b67fe9dd804b84a56c2535726b966d28d13
Parents: 1240c9b
Author: Sylvain Lebresne <sy...@datastax.com>
Authored: Wed Oct 23 15:57:19 2013 +0200
Committer: Sylvain Lebresne <sy...@datastax.com>
Committed: Wed Oct 23 15:57:19 2013 +0200
----------------------------------------------------------------------
src/java/org/apache/cassandra/transport/CBUtil.java | 2 +-
.../cassandra/transport/messages/StartupMessage.java | 11 ++++++++++-
2 files changed, 11 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/86b26b67/src/java/org/apache/cassandra/transport/CBUtil.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/transport/CBUtil.java b/src/java/org/apache/cassandra/transport/CBUtil.java
index f183af3..dfd0439 100644
--- a/src/java/org/apache/cassandra/transport/CBUtil.java
+++ b/src/java/org/apache/cassandra/transport/CBUtil.java
@@ -227,7 +227,7 @@ public abstract class CBUtil
Map<String, String> m = new HashMap<String, String>(length);
for (int i = 0; i < length; i++)
{
- String k = readString(cb).toUpperCase();
+ String k = readString(cb);
String v = readString(cb);
m.put(k, v);
}
http://git-wip-us.apache.org/repos/asf/cassandra/blob/86b26b67/src/java/org/apache/cassandra/transport/messages/StartupMessage.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/transport/messages/StartupMessage.java b/src/java/org/apache/cassandra/transport/messages/StartupMessage.java
index 51fece1..d56a037 100644
--- a/src/java/org/apache/cassandra/transport/messages/StartupMessage.java
+++ b/src/java/org/apache/cassandra/transport/messages/StartupMessage.java
@@ -17,6 +17,7 @@
*/
package org.apache.cassandra.transport.messages;
+import java.util.HashMap;
import java.util.Map;
import org.jboss.netty.buffer.ChannelBuffer;
@@ -42,7 +43,7 @@ public class StartupMessage extends Message.Request
{
public StartupMessage decode(ChannelBuffer body, int version)
{
- return new StartupMessage(CBUtil.readStringMap(body));
+ return new StartupMessage(upperCaseKeys(CBUtil.readStringMap(body)));
}
public void encode(StartupMessage msg, ChannelBuffer dest, int version)
@@ -108,6 +109,14 @@ public class StartupMessage extends Message.Request
return new ReadyMessage();
}
+ private static Map<String, String> upperCaseKeys(Map<String, String> options)
+ {
+ Map<String, String> newMap = new HashMap<String, String>(options.size());
+ for (Map.Entry<String, String> entry : options.entrySet())
+ newMap.put(entry.getKey().toUpperCase(), entry.getValue());
+ return newMap;
+ }
+
@Override
public String toString()
{
[3/4] git commit: Update changelog
Posted by sl...@apache.org.
Update changelog
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/62e8804d
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/62e8804d
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/62e8804d
Branch: refs/heads/cassandra-2.0
Commit: 62e8804d5b14a870b173eee9b019bced38d84faa
Parents: 4768daa
Author: Sylvain Lebresne <sy...@datastax.com>
Authored: Wed Oct 23 16:15:12 2013 +0200
Committer: Sylvain Lebresne <sy...@datastax.com>
Committed: Wed Oct 23 16:15:12 2013 +0200
----------------------------------------------------------------------
CHANGES.txt | 1 +
1 file changed, 1 insertion(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/62e8804d/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index bb40dff..44eb25d 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -3,6 +3,7 @@
* Fix altering column types (CASSANDRA-6185)
* cqlsh: fix CREATE/ALTER WITH completion (CASSANDRA-6196)
* add windows bat files for shell commands (CASSANDRA-6145)
+ * Fix potential stack overflow during range tombstones insertion (CASSANDRA-6181)
1.2.11
[2/4] git commit: Avoid stack overflow on RangeTombstoneList insertion
Posted by sl...@apache.org.
Avoid stack overflow on RangeTombstoneList insertion
patch by slebresne; reviewed by frousseau for CASSANDRA-6181
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/4768daa9
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/4768daa9
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/4768daa9
Branch: refs/heads/cassandra-2.0
Commit: 4768daa9d0ad55f026615d1aef330c38203d80d1
Parents: f388a2e
Author: Sylvain Lebresne <sy...@datastax.com>
Authored: Tue Oct 22 09:55:40 2013 +0200
Committer: Sylvain Lebresne <sy...@datastax.com>
Committed: Wed Oct 23 16:13:28 2013 +0200
----------------------------------------------------------------------
.../apache/cassandra/db/RangeTombstoneList.java | 226 ++++++++-----------
.../cassandra/db/RangeTombstoneListTest.java | 31 ++-
2 files changed, 122 insertions(+), 135 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/4768daa9/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 e7ec119..fad07b1 100644
--- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java
+++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
@@ -129,22 +129,18 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
return;
}
- int c = comparator.compare(starts[size-1], start);
+ int c = comparator.compare(ends[size-1], start);
// Fast path if we add in sorted order
if (c <= 0)
{
- // Note that we may still overlap the last range
- insertFrom(size-1, start, end, markedAt, delTime);
+ addInternal(size, start, end, markedAt, delTime);
}
else
{
- int pos = Arrays.binarySearch(starts, 0, size, start, comparator);
- if (pos >= 0)
- insertFrom(pos, start, end, markedAt, delTime);
- else
- // Insertion point (-pos-1) is such start < start[-pos-1], so we should insert from the previous
- insertFrom(-pos-2, start, end, markedAt, delTime);
+ // 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);
}
}
@@ -164,11 +160,11 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
/*
* We basically have 2 techniques we can use here: either we repeatedly call add() on tombstones values,
- * or we do a merge of both (sorted) lists. If this lists is bigger enough than the one we add, the
+ * or we do a merge of both (sorted) lists. If this lists is bigger enough than the one we add, then
* calling add() will be faster, otherwise it's merging that will be faster.
*
* Let's note that during memtables updates, it might not be uncommon that a new update has only a few range
- * tombstones, while the CF we're adding it to (the on in the memtable) has many. In that case, using add() is
+ * tombstones, while the CF we're adding it to (the one in the memtable) has many. In that case, using add() is
* likely going to be faster.
*
* In other cases however, like when diffing responses from multiple nodes, the tombstone lists we "merge" will
@@ -191,9 +187,9 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
int j = 0;
while (i < size && j < tombstones.size)
{
- if (comparator.compare(tombstones.starts[j], starts[i]) < 0)
+ if (comparator.compare(tombstones.starts[j], ends[i]) < 0)
{
- insertFrom(i-1, tombstones.starts[j], tombstones.ends[j], tombstones.markedAts[j], tombstones.delTimes[j]);
+ insertFrom(i, tombstones.starts[j], tombstones.ends[j], tombstones.markedAts[j], tombstones.delTimes[j]);
j++;
}
else
@@ -201,9 +197,9 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
i++;
}
}
- // Addds the remaining ones from tombstones if any (not that insertFrom will increment size if relevant).
+ // Addds the remaining ones from tombstones if any (note that addInternal will increment size if relevant).
for (; j < tombstones.size; j++)
- insertFrom(size - 1, tombstones.starts[j], tombstones.ends[j], tombstones.markedAts[j], tombstones.delTimes[j]);
+ addInternal(size, tombstones.starts[j], tombstones.ends[j], tombstones.markedAts[j], tombstones.delTimes[j]);
}
}
@@ -373,136 +369,106 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>
}
/*
- * Inserts a new element whose start should be inserted at index i. This method
- * assumes that:
- * - starts[i] <= start
- * - start < starts[i+1] or there is no i+1 element.
+ * 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]
*/
private void insertFrom(int i, ByteBuffer start, ByteBuffer end, long markedAt, int delTime)
{
- if (i < 0)
+ while (i < size)
{
- insertAfter(i, start, end, markedAt, delTime);
- return;
- }
+ assert i == 0 || comparator.compare(start, ends[i-1]) >= 0;
+ assert i >= size || comparator.compare(start, ends[i]) < 0;
- /*
- * We have elt(i) = [s_i, e_i]@t_i and want to insert X = [s, e]@t, knowing that s_i < s < s_i+1.
- * We can have 3 cases:
- * - s < e_i && e <= e_i: we're fully contained in i.
- * - s < e_i && e > e_i: we rewrite X to X1=[s, e_i]@t + X2=[e_i, e]@t. X1 is fully contained
- * in i and X2 is the insertAfter() case for i.
- * - s >= e_i: we're in the insertAfter() case for i.
- */
- if (comparator.compare(start, ends[i]) < 0)
- {
- if (comparator.compare(end, ends[i]) <= 0)
- {
- update(i, start, end, markedAt, delTime);
- }
- else
+ // Do we overwrite the current element?
+ if (markedAt > markedAts[i])
{
- insertAfter(i, ends[i], end, markedAt, delTime);
- update(i, start, ends[i], markedAt, delTime);
- }
- }
- else
- {
- insertAfter(i, start, end, markedAt, delTime);
- }
- }
+ // We do overwrite.
- /*
- * Inserts a new element knowing that the new element start strictly after
- * the one at index i, i.e that:
- * - ends[i] <= start (or i == -1)
- */
- private void insertAfter(int i, ByteBuffer start, ByteBuffer end, long markedAt, int delTime)
- {
- if (i == size - 1)
- {
- addInternal(i+1, start, end, markedAt, delTime);
- return;
- }
-
- /*
- * We have the following intervals:
- * i i+1
- * ..., [s1, e1]@t1, [s2, e2]@t2, ...
- *
- * And we want to insert X = [s, e]@t, knowing that e1 <= s.
- * We can have 2 cases:
- * - s < s2: we rewrite X to X1=[s, s2]@t + X2=[s2, e]@t. X2 meet the weakInsertFrom() condition
- * for i+1, and X1 is a new element between i and i+1.
- * - s2 <= s: we're in the weakInsertFrom() case for i+1.
- */
- if (comparator.compare(start, starts[i+1]) < 0)
- {
- /*
- * If it happens the new element is fully before the current one, we insert it and
- * we're done
- */
- if (comparator.compare(end, starts[i+1]) <= 0)
- {
- addInternal(i+1, start, end, markedAt, delTime);
- return;
- }
-
- weakInsertFrom(i+1, starts[i+1], end, markedAt, delTime);
- addInternal(i+1, start, starts[i+1], markedAt, delTime);
- }
- else
- {
- weakInsertFrom(i+1, start, end, markedAt, delTime);
- }
- }
+ // First deal with what might come before the newly added one.
+ if (comparator.compare(starts[i], start) < 0)
+ {
+ addInternal(i, starts[i], start, markedAts[i], delTimes[i]);
+ i++;
+ // We don't need to do the following line, but in spirit that's what we want to do
+ // setInternal(i, start, ends[i], markedAts, delTime])
+ }
- /*
- * Weak version of insertFrom that only assumes the new element starts after index i,
- * but without knowing about the 2nd condition, i.e. this only assume that:
- * - starts[i] <= start
- */
- private void weakInsertFrom(int i, ByteBuffer start, ByteBuffer end, long markedAt, int delTime)
- {
- /*
- * Either start is before the next element start, and we're in fact in the insertFrom()
- * case, or it's not and it's an weakInsertFrom for the next index.
- */
- if (i == size - 1 || comparator.compare(start, starts[i+1]) < 0)
- insertFrom(i, start, end, markedAt, delTime);
- else
- weakInsertFrom(i+1, start, end, markedAt, delTime);
- }
+ // now, start <= starts[i]
- /*
- * Update index i with new element, assuming that new element is contained in the element i,
- * i.e that:
- * - starts[i] <= s
- * - e <= end[i]
- */
- private void update(int i, ByteBuffer start, ByteBuffer end, long markedAt, int delTime)
- {
- /*
- * If the new markedAt is lower than the one of i, we can ignore the
- * new element, otherwise we split the current element.
- */
- if (markedAts[i] < markedAt)
- {
- if (comparator.compare(ends[i], end) != 0)
- addInternal(i+1, end, ends[i], markedAts[i], delTimes[i]);
+ // If the new element stops before the current one, insert it and
+ // we're done
+ if (comparator.compare(end, starts[i]) <= 0)
+ {
+ addInternal(i, start, end, markedAt, delTime);
+ return;
+ }
- if (comparator.compare(starts[i], start) == 0)
- {
- markedAts[i] = markedAt;
- delTimes[i] = delTime;
- ends[i] = end;
+ // Do we overwrite the current element fully?
+ int cmp = comparator.compare(ends[i], end);
+ if (cmp <= 0)
+ {
+ // We do overwrite fully:
+ // update the current element until it's end and continue
+ // on with the next element (with the new inserted start == current end).
+
+ // If we're on the last element, we can optimize
+ if (i == size-1)
+ {
+ setInternal(i, start, end, markedAt, delTime);
+ return;
+ }
+
+ setInternal(i, start, ends[i], markedAt, delTime);
+ if (cmp == 0)
+ return;
+
+ start = ends[i];
+ i++;
+ }
+ else
+ {
+ // We don't ovewrite fully. Insert the new interval, and then update the now next
+ // one to reflect the not overwritten parts. We're then done.
+ addInternal(i, start, end, markedAt, delTime);
+ i++;
+ setInternal(i, end, ends[i], markedAts[i], delTimes[i]);
+ return;
+ }
}
else
{
- addInternal(i+1, start, end, markedAt, delTime);
- ends[i] = start;
+ // we don't overwrite the current element
+
+ // If the new interval starts before the current one, insert that new interval
+ if (comparator.compare(start, starts[i]) < 0)
+ {
+ // If we stop before the start of the current element, just insert the new
+ // interval and we're done; otherwise insert until the beginning of the
+ // current element
+ if (comparator.compare(end, starts[i]) <= 0)
+ {
+ addInternal(i, start, end, markedAt, delTime);
+ return;
+ }
+ addInternal(i, start, starts[i], markedAt, delTime);
+ i++;
+ }
+
+ // After that, we're overwritten on the current element but might have
+ // some residual parts after ...
+
+ // ... unless we don't extend beyond it.
+ if (comparator.compare(end, ends[i]) <= 0)
+ return;
+
+ start = ends[i];
+ i++;
}
}
+
+ // If we got there, then just insert the remainder at the end
+ addInternal(i, start, end, markedAt, delTime);
}
private int capacity()
http://git-wip-us.apache.org/repos/asf/cassandra/blob/4768daa9/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 8166ffd..dc9f9c4 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
@@ -103,8 +103,7 @@ public class RangeTombstoneListTest
assertRT(rt(0, 1, 1), iter.next());
assertRT(rt(1, 4, 2), iter.next());
assertRT(rt(4, 8, 3), iter.next());
- assertRT(rt(8, 10, 4), iter.next());
- assertRT(rt(10, 13, 4), iter.next());
+ assertRT(rt(8, 13, 4), iter.next());
assertRT(rt(13, 15, 1), iter.next());
assert !iter.hasNext();
@@ -116,8 +115,16 @@ public class RangeTombstoneListTest
}
@Test
- public void overlappingSearchTest()
+ public void largeAdditionTest()
{
+ int N = 3000;
+ // Test that the StackOverflow from #6181 is fixed
+ RangeTombstoneList l = new RangeTombstoneList(cmp, N);
+ for (int i = 0; i < N; i++)
+ l.add(rt(2*i+1, 2*i+2, 1));
+ assertEquals(l.size(), N);
+
+ l.add(rt(0, 2*N+3, 2));
}
@Test
@@ -143,6 +150,21 @@ public class RangeTombstoneListTest
}
@Test
+ public void overlappingPreviousEndEqualsStartTest()
+ {
+ RangeTombstoneList l = new RangeTombstoneList(cmp, 0);
+ // add a RangeTombstone, so, last insert is not in insertion order
+ l.add(rt(11, 12, 2));
+ l.add(rt(1, 4, 2));
+ l.add(rt(4, 10, 5));
+
+ assertEquals(2, l.search(b(3)).markedForDeleteAt);
+ assertEquals(5, l.search(b(4)).markedForDeleteAt);
+ assertEquals(5, l.search(b(8)).markedForDeleteAt);
+ assertEquals(3, l.size());
+ }
+
+ @Test
public void searchTest()
{
RangeTombstoneList l = new RangeTombstoneList(cmp, 0);
@@ -198,8 +220,7 @@ public class RangeTombstoneListTest
assertRT(rt(7, 8, 3), iter.next());
assertRT(rt(8, 10, 2), iter.next());
assertRT(rt(10, 12, 1), iter.next());
- assertRT(rt(14, 15, 4), iter.next());
- assertRT(rt(15, 17, 4), iter.next());
+ assertRT(rt(14, 17, 4), iter.next());
assert !iter.hasNext();
}
[4/4] git commit: Merge branch 'cassandra-1.2' into cassandra-2.0
Posted by sl...@apache.org.
Merge branch 'cassandra-1.2' into cassandra-2.0
Conflicts:
CHANGES.txt
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/322f9a98
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/322f9a98
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/322f9a98
Branch: refs/heads/cassandra-2.0
Commit: 322f9a98315aabd8a57b6fe42d5763f9ff6de3a7
Parents: 86b26b6 62e8804
Author: Sylvain Lebresne <sy...@datastax.com>
Authored: Wed Oct 23 16:17:02 2013 +0200
Committer: Sylvain Lebresne <sy...@datastax.com>
Committed: Wed Oct 23 16:17:02 2013 +0200
----------------------------------------------------------------------
CHANGES.txt | 4 +-
.../apache/cassandra/db/RangeTombstoneList.java | 226 ++++++++-----------
.../cassandra/db/RangeTombstoneListTest.java | 31 ++-
3 files changed, 125 insertions(+), 136 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/322f9a98/CHANGES.txt
----------------------------------------------------------------------
diff --cc CHANGES.txt
index 1df6ade,44eb25d..47e52f1
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@@ -5,38 -3,10 +5,40 @@@ Merged from 1.2
* Fix altering column types (CASSANDRA-6185)
* cqlsh: fix CREATE/ALTER WITH completion (CASSANDRA-6196)
* add windows bat files for shell commands (CASSANDRA-6145)
-
+ * Fix potential stack overflow during range tombstones insertion (CASSANDRA-6181)
+
+
-1.2.11
+2.0.2
+ * Update FailureDetector to use nanontime (CASSANDRA-4925)
+ * Fix FileCacheService regressions (CASSANDRA-6149)
+ * Never return WriteTimeout for CL.ANY (CASSANDRA-6032)
+ * Fix race conditions in bulk loader (CASSANDRA-6129)
+ * Add configurable metrics reporting (CASSANDRA-4430)
+ * drop queries exceeding a configurable number of tombstones (CASSANDRA-6117)
+ * Track and persist sstable read activity (CASSANDRA-5515)
+ * Fixes for speculative retry (CASSANDRA-5932)
+ * Improve memory usage of metadata min/max column names (CASSANDRA-6077)
+ * Fix thrift validation refusing row markers on CQL3 tables (CASSANDRA-6081)
+ * Fix insertion of collections with CAS (CASSANDRA-6069)
+ * Correctly send metadata on SELECT COUNT (CASSANDRA-6080)
+ * Track clients' remote addresses in ClientState (CASSANDRA-6070)
+ * Create snapshot dir if it does not exist when migrating
+ leveled manifest (CASSANDRA-6093)
+ * make sequential nodetool repair the default (CASSANDRA-5950)
+ * Add more hooks for compaction strategy implementations (CASSANDRA-6111)
+ * Fix potential NPE on composite 2ndary indexes (CASSANDRA-6098)
+ * Delete can potentially be skipped in batch (CASSANDRA-6115)
+ * Allow alter keyspace on system_traces (CASSANDRA-6016)
+ * Disallow empty column names in cql (CASSANDRA-6136)
+ * Use Java7 file-handling APIs and fix file moving on Windows (CASSANDRA-5383)
+ * Save compaction history to system keyspace (CASSANDRA-5078)
+ * Fix NPE if StorageService.getOperationMode() is executed before full startup (CASSANDRA-6166)
+ * CQL3: support pre-epoch longs for TimestampType (CASSANDRA-6212)
+ * Add reloadtriggers command to nodetool (CASSANDRA-4949)
+ * cqlsh: ignore empty 'value alias' in DESCRIBE (CASSANDRA-6139)
+ * Fix sstable loader (CASSANDRA-6205)
+Merged from 1.2:
+ * (Hadoop) Require CFRR batchSize to be at least 2 (CASSANDRA-6114)
* Add a warning for small LCS sstable size (CASSANDRA-6191)
* Add ability to list specific KS/CF combinations in nodetool cfstats (CASSANDRA-4191)
* Mark CF clean if a mutation raced the drop and got it marked dirty (CASSANDRA-5946)
http://git-wip-us.apache.org/repos/asf/cassandra/blob/322f9a98/src/java/org/apache/cassandra/db/RangeTombstoneList.java
----------------------------------------------------------------------