From: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date: Sat, 25 Mar 2017 20:43:31 +0000 (-0700)
Subject: Several fixes to the "SWMRList" example in experimental/hazptr.
X-Git-Tag: v2017.03.27.00^0
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=4cc8030e3bdc894c3979529e025c3160fd39ecd9

Several fixes to the "SWMRList" example in experimental/hazptr.

Summary:
Fix a correctness bug in "SWMRList.h".

Thanks to Maged for the tip! The old code omitted setting a removed node's
"next" pointer to `nullptr`, which meant that if the writer removed node
A and then node B = A->next while the reader was looking at B, then the reader
might happily keep chasing pointers B->next, B->next->next,... without ever
noticing that it was now on a "dead branch" of the linked list.

(And then there's a bit of a trick: you really do have to remove the node
first and *then* set its "next" pointer to null, because if you do the null
assignment first, you'll truncate the list, which means that some readers
will see a truncated list and return the wrong answer. I've added comments
to try to explain this to future-me.)

Style nit: Avoid doing multiple atomic operations on the same line of code.

----

Modernize the parameter-passing conventions in SWMRList.h.

Pass `T`s by const reference, except in `add` where we're likely to want to
make a copy of the `T` anyway. In that case it would be more "STL-correct"
to supply two different overloads `add(T&&)` and `add(const T&)`, but this
is just an example so it makes sense to keep things simple.

----

Fix an undefined behavior in SWMRList example.

Searching an empty SWMRList<int> always invokes undefined behavior by
comparing an uninitialized `T elem` against `val` on the final line of
the `contains` function. Besides, this patch allows SWMRList to work
with `T`s that aren't default-constructible or even copy-constructible.

----

Closes https://github.com/facebook/folly/pull/566

Reviewed By: djwatson

Differential Revision: D4772359

Pulled By: yfeldblum

fbshipit-source-id: 8f96573530800675cb56006aa91e7a5c5c1fb85d
---

diff --git a/folly/experimental/hazptr/example/SWMRList.h b/folly/experimental/hazptr/example/SWMRList.h
index b54240f2..6697fce8 100644
--- a/folly/experimental/hazptr/example/SWMRList.h
+++ b/folly/experimental/hazptr/example/SWMRList.h
@@ -56,7 +56,7 @@ class SWMRListSet {
   hazptr_domain& domain_;
 
   /* Used by the single writer */
-  void locate_lower_bound(const T v, std::atomic<Node*>*& prev) const {
+  void locate_lower_bound(const T& v, std::atomic<Node*>*& prev) const {
     auto curr = prev->load();
     while (curr) {
       if (curr->elem_ >= v) break;
@@ -78,42 +78,45 @@ class SWMRListSet {
     }
   }
 
-  bool add(const T v) {
+  bool add(T v) {
     auto prev = &head_;
     locate_lower_bound(v, prev);
     auto curr = prev->load();
     if (curr && curr->elem_ == v) return false;
-    prev->store(new Node(v, curr));
+    prev->store(new Node(std::move(v), curr));
     return true;
   }
 
-  bool remove(const T v) {
+  bool remove(const T& v) {
     auto prev = &head_;
     locate_lower_bound(v, prev);
     auto curr = prev->load();
     if (!curr || curr->elem_ != v) return false;
-    prev->store(curr->next_.load());
+    Node *curr_next = curr->next_.load();
+    prev->store(curr_next);  // Patch up the actual list...
+    curr->next_.store(nullptr);  // ...and only then null out the removed node.
     curr->retire(domain_);
     return true;
   }
   /* Used by readers */
-  bool contains(const T val) const {
+  bool contains(const T& val) const {
     /* Acquire two hazard pointers for hand-over-hand traversal. */
     hazptr_owner<Node> hptr_prev(domain_);
     hazptr_owner<Node> hptr_curr(domain_);
-    T elem;
-    bool done = false;
-    while (!done) {
+    while (true) {
       auto prev = &head_;
       auto curr = prev->load();
       while (true) {
-        if (!curr) { done = true; break; }
+        if (!curr) { return false; }
         if (!hptr_curr.try_protect(curr, *prev))
           break;
         auto next = curr->next_.load();
-        elem = curr->elem_;
         if (prev->load() != curr) break;
-        if (elem >= val) { done = true; break; }
+        if (curr->elem_ == val) {
+            return true;
+        } else if (!(curr->elem_ < val)) {
+            return false;  // because the list is sorted
+        }
         prev = &(curr->next_);
         curr = next;
         /* Swap does not change the values of the owned hazard
@@ -129,7 +132,6 @@ class SWMRListSet {
         swap(hptr_curr, hptr_prev);
       }
     }
-    return elem == val;
     /* The hazard pointers are released automatically. */
   }
 };