ConcurrentSkipList Bug

Summary:
Bug reported by Yan Lin (not a facebook employee) through @robbert.

@philipp and @jdelong: you are the only two remaining facebookers to have
made non-trivial changes to this code.

Description of bug: layer 0 is 1->4, and we're looking for 3. We pass
over 4, and see that 1 is less than 3 in the for loop. Now a race
condition: another thread inserts 2, so layer 0 is now 1->2->3. Then,
since ht==0, we return pred->skip(0), which is now 2 instead of 4.

Why this is bad: it really breaks the lower_bound function (lower_bound
calls findNode calls findNodeDownRight), since it returns an element
that is lesser.

This patch doesn't change the behavior of the code in the normal case;
it just recycles previously-computed values so that this race condition
doesn't crash and burn.

Patch based off of Yan Lin's in-email suggestion.

Test Plan:
fbconfig -r folly && fbmake runtests

Reviewed By: philipp@fb.com

Subscribers: sdwilsh, folly-diffs@, jdelong, robbert, philipp

FB internal diff: D1732434

Signature: t1:1732434:1418260198:8c707435825cfa2a1093b681e066f320193e98f2

diff --git a/folly/ConcurrentSkipList.h b/folly/ConcurrentSkipList.h
index 620446f94fcce7680679a0d44b3c69033a370424..4aaf19bcd0eb9acf3c89c79a09e5ee5bac5b4523 100644 (file)
--- a/folly/ConcurrentSkipList.h
+++ b/folly/ConcurrentSkipList.h
@@ -430,10 +430,11 @@ class ConcurrentSkipList {
     bool found = false;
     while (!found) {
       // stepping down
-      for (; ht > 0 && less(data, pred->skip(ht - 1)); --ht) {}
-      if (ht == 0) return std::make_pair(pred->skip(0), 0);  // not found
+      for (; ht > 0 && less(data, node = pred->skip(ht - 1)); --ht) {}
+      if (ht == 0) return std::make_pair(node, 0);  // not found
+      // node <= data now, but we need to fix up ht
+      --ht;
 
-      node = pred->skip(--ht);  // node <= data now
       // stepping right
       while (greater(data, node)) {
         pred = node;