folly/experimental/AtomicSharedPtr.h

   1 /*
   2  * Copyright 2017-present 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/AtomicStruct.h>
  19 #include <folly/PackedSyncPtr.h>
  20 #include <folly/detail/AtomicUtils.h>
  21 #include <folly/experimental/detail/AtomicSharedPtr-detail.h>
  22 #include <atomic>
  23 #include <thread>
  24
  25 /*
  26  * This is an implementation of the std::atomic_shared_ptr TS
  27  * http://en.cppreference.com/w/cpp/experimental/atomic_shared_ptr
  28  * https://isocpp.org/files/papers/N4162.pdf
  29  *
  30  * AFAIK, the only other implementation is Anthony Williams from
  31  * Just::thread library:
  32  *
  33  * https://bitbucket.org/anthonyw/atomic_shared_ptr
  34  *
  35  * implementation details:
  36  *
  37  * Basically, three things need to be atomically exchanged to make this work:
  38  * * the local count
  39  * * the pointer to the control block
  40  * * the aliased pointer, if any.
  41  *
  42  * The Williams version does it with DWcas: 32 bits for local count, 64
  43  * bits for control block ptr, and he changes the shared_ptr
  44  * implementation to also store the aliased pointers using a linked list
  45  * like structure, and provides 32-bit index accessors to them (like
  46  * IndexedMemPool trick).
  47  *
  48  * This version instead stores the 48 bits of address, plus 16 bits of
  49  * local count in a single 8byte pointer.  This avoids 'lock cmpxchg16b',
  50  * which is much slower than 'lock xchg' in the normal 'store' case.  In
  51  * the less-common aliased pointer scenaro, we just allocate it in a new
  52  * block, and store a pointer to that instead.
  53  *
  54  * Note that even if we only want to use the 3-bits of pointer alignment,
  55  * this trick should still work - Any more than 4 concurrent accesses
  56  * will have to go to an external map count instead (slower, but lots of
  57  * concurrent access will be slow anyway due to bouncing cachelines).
  58  *
  59  * As a perf optimization, we currently batch up local count and only
  60  * move it global every once in a while.  This means load() is usually
  61  * only a single atomic operation, instead of 3.  For this trick to work,
  62  * we probably need at least 8 bits to make batching worth it.
  63  */
  64
  65 // A note on noexcept: If the pointer is an aliased pointer,
  66 // store() will allocate.  Otherwise is noexcept.
  67 namespace folly {
  68
  69 template <
  70     typename T,
  71     template <typename> class Atom = std::atomic,
  72     typename CountedDetail = detail::shared_ptr_internals>
  73 class atomic_shared_ptr {
  74   using SharedPtr = typename CountedDetail::template CountedPtr<T>;
  75   using BasePtr = typename CountedDetail::counted_base;
  76   using PackedPtr = folly::PackedSyncPtr<BasePtr>;
  77
  78  public:
  79   atomic_shared_ptr() noexcept {
  80     init();
  81   }
  82   explicit atomic_shared_ptr(SharedPtr foo) /* noexcept */
  83       : atomic_shared_ptr() {
  84     store(foo);
  85   }
  86   atomic_shared_ptr(const atomic_shared_ptr<T>&) = delete;
  87
  88   ~atomic_shared_ptr() {
  89     store(SharedPtr(nullptr));
  90   }
  91   void operator=(SharedPtr desired) /* noexcept */ {
  92     store(desired);
  93   }
  94   void operator=(const atomic_shared_ptr<T>&) = delete;
  95
  96   bool is_lock_free() const noexcept {
  97     // lock free unless more than EXTERNAL_OFFSET threads are
  98     // contending and they all get unlucky and scheduled out during
  99     // load().
 100     //
 101     // TODO: Could use a lock-free external map to fix this
 102     // corner case.
 103     return true;
 104   }
 105
 106   SharedPtr load(std::memory_order order = std::memory_order_seq_cst) const
 107       noexcept {
 108     auto local = takeOwnedBase(order);
 109
 110     auto res = get_shared_ptr(local, false);
 111
 112     return std::move(res);
 113   }
 114   /* implicit */ operator SharedPtr() const {
 115     return load();
 116   }
 117
 118   void store(
 119       SharedPtr n,
 120       std::memory_order order = std::memory_order_seq_cst) /* noexcept */ {
 121     auto newptr = get_newptr(std::move(n));
 122     auto old = ptr_.exchange(newptr, order);
 123     release_external(old);
 124   }
 125
 126   SharedPtr exchange(
 127       SharedPtr n,
 128       std::memory_order order = std::memory_order_seq_cst) /* noexcept */ {
 129     auto newptr = get_newptr(std::move(n));
 130     auto old = ptr_.exchange(newptr, order);
 131
 132     SharedPtr old_ptr;
 133
 134     if (old.get()) {
 135       old_ptr = get_shared_ptr(old);
 136       release_external(old);
 137     }
 138
 139     return old_ptr;
 140   }
 141
 142   bool compare_exchange_weak(
 143       SharedPtr& expected,
 144       const SharedPtr& n,
 145       std::memory_order mo = std::memory_order_seq_cst) noexcept {
 146     return compare_exchange_weak(
 147         expected, n, mo, detail::default_failure_memory_order(mo));
 148   }
 149   bool compare_exchange_weak(
 150       SharedPtr& expected,
 151       const SharedPtr& n,
 152       std::memory_order success,
 153       std::memory_order failure) /* noexcept */ {
 154     auto newptr = get_newptr(n);
 155     PackedPtr oldptr, expectedptr;
 156
 157     oldptr = takeOwnedBase(success);
 158     if (!owners_eq(oldptr, CountedDetail::get_counted_base(expected))) {
 159       expected = get_shared_ptr(oldptr, false);
 160       release_external(newptr);
 161       return false;
 162     }
 163     expectedptr = oldptr; // Need oldptr to release if failed
 164     if (ptr_.compare_exchange_weak(expectedptr, newptr, success, failure)) {
 165       if (oldptr.get()) {
 166         release_external(oldptr, -1);
 167       }
 168       return true;
 169     } else {
 170       if (oldptr.get()) {
 171         expected = get_shared_ptr(oldptr, false);
 172       } else {
 173         expected = SharedPtr(nullptr);
 174       }
 175       release_external(newptr);
 176       return false;
 177     }
 178   }
 179   bool compare_exchange_weak(
 180       SharedPtr& expected,
 181       SharedPtr&& desired,
 182       std::memory_order mo = std::memory_order_seq_cst) noexcept {
 183     return compare_exchange_weak(
 184         expected, desired, mo, detail::default_failure_memory_order(mo));
 185   }
 186   bool compare_exchange_weak(
 187       SharedPtr& expected,
 188       SharedPtr&& desired,
 189       std::memory_order success,
 190       std::memory_order failure) /* noexcept */ {
 191     return compare_exchange_weak(expected, desired, success, failure);
 192   }
 193   bool compare_exchange_strong(
 194       SharedPtr& expected,
 195       const SharedPtr& n,
 196       std::memory_order mo = std::memory_order_seq_cst) noexcept {
 197     return compare_exchange_strong(
 198         expected, n, mo, detail::default_failure_memory_order(mo));
 199   }
 200   bool compare_exchange_strong(
 201       SharedPtr& expected,
 202       const SharedPtr& n,
 203       std::memory_order success,
 204       std::memory_order failure) /* noexcept */ {
 205     auto local_expected = expected;
 206     do {
 207       if (compare_exchange_weak(expected, n, success, failure)) {
 208         return true;
 209       }
 210     } while (local_expected == expected);
 211
 212     return false;
 213   }
 214   bool compare_exchange_strong(
 215       SharedPtr& expected,
 216       SharedPtr&& desired,
 217       std::memory_order mo = std::memory_order_seq_cst) noexcept {
 218     return compare_exchange_strong(
 219         expected, desired, mo, detail::default_failure_memory_order(mo));
 220   }
 221   bool compare_exchange_strong(
 222       SharedPtr& expected,
 223       SharedPtr&& desired,
 224       std::memory_order success,
 225       std::memory_order failure) /* noexcept */ {
 226     return compare_exchange_strong(expected, desired, success, failure);
 227   }
 228
 229  private:
 230   // Matches packed_sync_pointer.  Must be > max number of local
 231   // counts.  This is the max number of threads that can access this
 232   // atomic_shared_ptr at once before we start blocking.
 233   static constexpr unsigned EXTERNAL_OFFSET{0x2000};
 234   // Bit signifying aliased constructor
 235   static constexpr unsigned ALIASED_PTR{0x4000};
 236
 237   mutable AtomicStruct<PackedPtr, Atom> ptr_;
 238
 239   void add_external(BasePtr* res, int64_t c = 0) const {
 240     assert(res);
 241     CountedDetail::inc_shared_count(res, EXTERNAL_OFFSET + c);
 242   }
 243   void release_external(PackedPtr& res, int64_t c = 0) const {
 244     if (!res.get()) {
 245       return;
 246     }
 247     int64_t count = get_local_count(res) + c;
 248     int64_t diff = EXTERNAL_OFFSET - count;
 249     assert(diff >= 0);
 250     CountedDetail::template release_shared<T>(res.get(), diff);
 251   }
 252   PackedPtr get_newptr(const SharedPtr& n) const {
 253     BasePtr* newval;
 254     unsigned count = 0;
 255     if (!n) {
 256       newval = nullptr;
 257     } else {
 258       newval = CountedDetail::get_counted_base(n);
 259       if (n.get() != CountedDetail::template get_shared_ptr<T>(newval)) {
 260         // This is an aliased sharedptr.  Make an un-aliased one
 261         // by wrapping in *another* shared_ptr.
 262         auto data = CountedDetail::template make_ptr<SharedPtr>(n);
 263         newval = CountedDetail::get_counted_base(data);
 264         count = ALIASED_PTR;
 265         // (add external must happen before data goes out of scope)
 266         add_external(newval);
 267       } else {
 268         add_external(newval);
 269       }
 270     }
 271
 272     PackedPtr newptr;
 273     newptr.init(newval, count);
 274
 275     return newptr;
 276   }
 277   PackedPtr get_newptr(SharedPtr&& n) const {
 278     BasePtr* newval;
 279     unsigned count = 0;
 280     if (!n) {
 281       newval = nullptr;
 282     } else {
 283       newval = CountedDetail::get_counted_base(n);
 284       if (n.get() != CountedDetail::template get_shared_ptr<T>(newval)) {
 285         // This is an aliased sharedptr.  Make an un-aliased one
 286         // by wrapping in *another* shared_ptr.
 287         auto data = CountedDetail::template make_ptr<SharedPtr>(std::move(n));
 288         newval = CountedDetail::get_counted_base(data);
 289         count = ALIASED_PTR;
 290         CountedDetail::release_ptr(data);
 291         add_external(newval, -1);
 292       } else {
 293         CountedDetail::release_ptr(n);
 294         add_external(newval, -1);
 295       }
 296     }
 297
 298     PackedPtr newptr;
 299     newptr.init(newval, count);
 300
 301     return newptr;
 302   }
 303   void init() {
 304     PackedPtr data;
 305     data.init();
 306     ptr_.store(data);
 307   }
 308
 309   unsigned int get_local_count(const PackedPtr& p) const {
 310     return p.extra() & ~ALIASED_PTR;
 311   }
 312
 313   // Check pointer equality considering wrapped aliased pointers.
 314   bool owners_eq(PackedPtr& p1, BasePtr* p2) {
 315     bool aliased1 = p1.extra() & ALIASED_PTR;
 316     if (aliased1) {
 317       auto p1a = CountedDetail::template get_shared_ptr_from_counted_base<T>(
 318           p1.get(), false);
 319       return CountedDetail::get_counted_base(p1a) == p2;
 320     }
 321     return p1.get() == p2;
 322   }
 323
 324   SharedPtr get_shared_ptr(const PackedPtr& p, bool inc = true) const {
 325     bool aliased = p.extra() & ALIASED_PTR;
 326
 327     auto res = CountedDetail::template get_shared_ptr_from_counted_base<T>(
 328         p.get(), inc);
 329     if (aliased) {
 330       auto aliasedp =
 331           CountedDetail::template get_shared_ptr_from_counted_base<SharedPtr>(
 332               p.get());
 333       res = *aliasedp;
 334     }
 335     return std::move(res);
 336   }
 337
 338   /* Get a reference to the pointer, either from the local batch or
 339    * from the global count.
 340    *
 341    * return is the base ptr, and the previous local count, if it is
 342    * needed for compare_and_swap later.
 343    */
 344   PackedPtr takeOwnedBase(std::memory_order order) const noexcept {
 345     PackedPtr local, newlocal;
 346     local = ptr_.load(std::memory_order_acquire);
 347     while (true) {
 348       if (!local.get()) {
 349         return local;
 350       }
 351       newlocal = local;
 352       if (get_local_count(newlocal) + 1 > EXTERNAL_OFFSET) {
 353         // spinlock in the rare case we have more than
 354         // EXTERNAL_OFFSET threads trying to access at once.
 355         std::this_thread::yield();
 356         // Force DeterministicSchedule to choose a different thread
 357         local = ptr_.load(std::memory_order_acquire);
 358       } else {
 359         newlocal.setExtra(newlocal.extra() + 1);
 360         assert(get_local_count(newlocal) > 0);
 361         if (ptr_.compare_exchange_weak(local, newlocal, order)) {
 362           break;
 363         }
 364       }
 365     }
 366
 367     // Check if we need to push a batch from local -> global
 368     auto batchcount = EXTERNAL_OFFSET / 2;
 369     if (get_local_count(newlocal) > batchcount) {
 370       CountedDetail::inc_shared_count(newlocal.get(), batchcount);
 371       putOwnedBase(newlocal.get(), batchcount, order);
 372     }
 373
 374     return newlocal;
 375   }
 376
 377   void putOwnedBase(BasePtr* p, unsigned int count, std::memory_order mo) const
 378       noexcept {
 379     PackedPtr local = ptr_.load(std::memory_order_acquire);
 380     while (true) {
 381       if (local.get() != p) {
 382         break;
 383       }
 384       auto newlocal = local;
 385       if (get_local_count(local) > count) {
 386         newlocal.setExtra(local.extra() - count);
 387       } else {
 388         // Otherwise it may be the same pointer, but someone else won
 389         // the compare_exchange below, local count was already made
 390         // global.  We decrement the global count directly instead of
 391         // the local one.
 392         break;
 393       }
 394       if (ptr_.compare_exchange_weak(local, newlocal, mo)) {
 395         return;
 396       }
 397     }
 398
 399     CountedDetail::template release_shared<T>(p, count);
 400   }
 401 };
 402
 403 } // namespace folly