folly/experimental/hazptr/example/MWMRSet.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #pragma once
  17
  18 #include <folly/experimental/hazptr/debug.h>
  19 #include <folly/experimental/hazptr/hazptr.h>
  20
  21 namespace folly {
  22 namespace hazptr {
  23
  24 /** Set implemented as an ordered singly-linked list.
  25  *
  26  *  Multiple writers may add or remove elements. Multiple reader
  27  *  threads may search the set concurrently with each other and with
  28  *  the writers' operations.
  29  */
  30 template <typename T>
  31 class MWMRListSet {
  32   class Node : public hazptr_obj_base<Node> {
  33     friend MWMRListSet;
  34     T elem_;
  35     std::atomic<uint64_t> refcount_{1};
  36     std::atomic<Node*> next_{nullptr};
  37
  38     // Node must be refcounted for wait-free access: A deleted node
  39     // may have hazptrs pointing at it, so the rest of the list (or at
  40     // least, what existed at the time of the hazptr load) must still
  41     // be accessible.
  42     void release() {
  43       if (refcount_.fetch_sub(1) == 1) {
  44         this->retire();
  45       }
  46     }
  47
  48     // Optimization in the case that we know there are no hazptrs pointing
  49     // at the list.
  50     void releaseFast() {
  51       if (refcount_.load(std::memory_order_relaxed) == 1) {
  52         auto next = getPtr(next_.load(std::memory_order_relaxed));
  53         if (next) {
  54           next->releaseFast();
  55           next_.store(nullptr, std::memory_order_relaxed);
  56         }
  57         delete this;
  58       }
  59     }
  60
  61     void acquire() {
  62       DCHECK(refcount_.load() != 0);
  63       refcount_.fetch_add(1);
  64     }
  65
  66    public:
  67     explicit Node(T e) : elem_(e) {
  68       DEBUG_PRINT(this << " " << e);
  69     }
  70
  71     ~Node() {
  72       DEBUG_PRINT(this);
  73       auto next = getPtr(next_.load(std::memory_order_relaxed));
  74       if (next) {
  75         next->release();
  76       }
  77     }
  78   };
  79
  80   static bool getDeleted(Node* ptr) {
  81     return uintptr_t(ptr) & 1;
  82   }
  83
  84   static Node* getPtr(Node* ptr) {
  85     return (Node*)(uintptr_t(ptr) & ~1UL);
  86   }
  87
  88   mutable std::atomic<Node*> head_ = {nullptr};
  89
  90   // Remove a single deleted item.
  91   // Although it doesn't have to be our item.
  92   //
  93   // Note that standard lock-free Michael linked lists put this in the
  94   // contains() path, while this implementation leaves it only in
  95   // remove(), such that contains() is wait-free.
  96   void fixlist(
  97       hazptr_holder& hptr_prev,
  98       hazptr_holder& hptr_curr,
  99       std::atomic<Node*>*& prev,
 100       Node*& curr) const {
 101     while (true) {
 102       prev = &head_;
 103       curr = hptr_curr.get_protected(*prev, getPtr);
 104       while (getPtr(curr)) {
 105         auto next = getPtr(curr)->next_.load(std::memory_order_acquire);
 106         if (getDeleted(next)) {
 107           auto nextp = getPtr(next);
 108           if (nextp) {
 109             nextp->acquire();
 110           }
 111           // Try to fix
 112           auto curr_no_mark = getPtr(curr);
 113           if (prev->compare_exchange_weak(curr_no_mark, nextp)) {
 114             // Physically delete
 115             curr_no_mark->release();
 116             return;
 117           } else {
 118             if (nextp) {
 119               nextp->release();
 120             }
 121             break;
 122           }
 123         }
 124         prev = &(getPtr(curr)->next_);
 125         curr = hptr_prev.get_protected(getPtr(curr)->next_, getPtr);
 126
 127         swap(hptr_curr, hptr_prev);
 128       }
 129       DCHECK(getPtr(curr));
 130     }
 131   }
 132
 133   /* wait-free set search */
 134   bool find(
 135       const T& val,
 136       hazptr_holder& hptr_prev,
 137       hazptr_holder& hptr_curr,
 138       std::atomic<Node*>*& prev,
 139       Node*& curr) const {
 140     prev = &head_;
 141     curr = hptr_curr.get_protected(*prev, getPtr);
 142     while (getPtr(curr)) {
 143       auto next = getPtr(curr)->next_.load(std::memory_order_acquire);
 144       if (!getDeleted(next)) {
 145         if (getPtr(curr)->elem_ == val) {
 146           return true;
 147         } else if (!(getPtr(curr)->elem_ < val)) {
 148           break; // Because the list is sorted.
 149         }
 150       }
 151       prev = &(getPtr(curr)->next_);
 152       curr = hptr_prev.get_protected(getPtr(curr)->next_, getPtr);
 153       /* Swap does not change the values of the owned hazard
 154        * pointers themselves. After the swap, The hazard pointer
 155        * owned by hptr_prev continues to protect the node that
 156        * contains the pointer *prev. The hazard pointer owned by
 157        * hptr_curr will continue to protect the node that contains
 158        * the old *prev (unless the old prev was &head), which no
 159        * longer needs protection, so hptr_curr's hazard pointer is
 160        * now free to protect *curr in the next iteration (if curr !=
 161        * null).
 162        */
 163       swap(hptr_curr, hptr_prev);
 164     }
 165
 166     return false;
 167   }
 168
 169  public:
 170   explicit MWMRListSet() {}
 171
 172   ~MWMRListSet() {
 173     Node* next = head_.load();
 174     if (next) {
 175       next->releaseFast();
 176     }
 177   }
 178
 179   bool add(T v) {
 180     hazptr_holder hptr_prev;
 181     hazptr_holder hptr_curr;
 182     std::atomic<Node*>* prev;
 183     Node* cur;
 184
 185     auto newnode = folly::make_unique<Node>(v);
 186
 187     while (true) {
 188       if (find(v, hptr_prev, hptr_curr, prev, cur)) {
 189         return false;
 190       }
 191       newnode->next_.store(cur, std::memory_order_relaxed);
 192       auto cur_no_mark = getPtr(cur);
 193       if (prev->compare_exchange_weak(cur_no_mark, newnode.get())) {
 194         newnode.release();
 195         return true;
 196       }
 197       // Ensure ~Node() destructor doesn't destroy next_
 198       newnode->next_.store(nullptr, std::memory_order_relaxed);
 199     }
 200   }
 201
 202   bool remove(const T& v) {
 203     hazptr_holder hptr_prev;
 204     hazptr_holder hptr_curr;
 205     std::atomic<Node*>* prev;
 206     Node* curr;
 207
 208     while (true) {
 209       if (!find(v, hptr_prev, hptr_curr, prev, curr)) {
 210         return false;
 211       }
 212       auto next = getPtr(curr)->next_.load(std::memory_order_acquire);
 213       auto next_no_mark = getPtr(next); // Ensure only one deleter wins
 214       // Logically delete
 215       if (!getPtr(curr)->next_.compare_exchange_weak(
 216               next_no_mark, (Node*)(uintptr_t(next_no_mark) | 1))) {
 217         continue;
 218       }
 219       if (next) {
 220         next->acquire();
 221       }
 222
 223       // Swing prev around
 224       auto curr_no_mark = getPtr(curr); /* ensure not deleted */
 225       if (prev->compare_exchange_weak(curr_no_mark, next)) {
 226         // Physically delete
 227         curr->release();
 228         return true;
 229       }
 230       if (next) {
 231         next->release();
 232       }
 233
 234       // Someone else modified prev.  Call fixlist
 235       // to unlink deleted element by re-walking list.
 236       fixlist(hptr_prev, hptr_curr, prev, curr);
 237     }
 238   }
 239
 240   bool contains(const T& v) const {
 241     hazptr_holder hptr_prev;
 242     hazptr_holder hptr_curr;
 243     std::atomic<Node*>* prev;
 244     Node* curr;
 245
 246     return find(v, hptr_prev, hptr_curr, prev, curr);
 247   }
 248 };
 249
 250 } // namespace hazptr
 251 } // namespace folly