folly/ReadMostlySharedPtr.h

   1 /*
   2  * Copyright 2015 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 /* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */
  17 #pragma once
  18
  19 #include <atomic>
  20 #include <memory>
  21 #include <folly/Optional.h>
  22 #include <folly/ThreadLocal.h>
  23 #include <folly/SpinLock.h>
  24
  25 namespace folly {
  26
  27 /**
  28  * @file ReadMostlySharedPtr is a smart pointer that allows for high
  29  * performance shared ownership of an object. In order to provide
  30  * this, ReadMostlySharedPtr may potentially delay the destruction of
  31  * a shared object for longer than a std::shared_ptr would, and
  32  * depending on the implementation, may have slower updates.
  33  *
  34  * The load() method allows a reader to acquire a ReadPtr that
  35  * maintains a reference to a single version of the object. Even if a
  36  * writer calls store(), the ReadPtr will point to the version of the
  37  * object that was in use at the time of the read. The old version of
  38  * the object will only be destroyed after all outstanding ReadPtrs to
  39  * that version have been destroyed.
  40  */
  41
  42 template<typename T,
  43          typename Tag = void>
  44 class ReadMostlySharedPtr {
  45  public:
  46   constexpr explicit ReadMostlySharedPtr(std::unique_ptr<T>&& ptr = nullptr)
  47       : masterPtr_(std::move(ptr)) {}
  48
  49   /**
  50    * Replaces the managed object.
  51    */
  52   void store(std::unique_ptr<T>&& uptr) {
  53     {
  54       std::shared_ptr<T> ptr(std::move(uptr));
  55       std::lock_guard<std::mutex> lock(mutex_);
  56       // Swap to avoid calling ~T() under the lock
  57       std::swap(masterPtr_, ptr);
  58     }
  59
  60     {
  61       // This also holds a lock that prevents destruction of thread cache
  62       // entries, but not creation. If creating a thread cache entry for a new
  63       // thread happens duting iteration, the entry is not guaranteed to
  64       // be seen. It's fine for us: if load() created a new cache entry after
  65       // we got accessor, it will see the updated pointer, so we don't need to
  66       // clear the cache.
  67       auto accessor = threadLocalCache_.accessAllThreads();
  68
  69       for (CachedPointer& local: accessor) {
  70         std::lock_guard<folly::SpinLock> local_lock(local.lock);
  71         // We could instead just assign masterPtr_ to local.ptr, but it's better
  72         // if the thread allocates the Ptr for itself - the allocator is more
  73         // likely to place its reference counter in a region optimal for access
  74         // from that thread.
  75         local.ptr.clear();
  76       }
  77     }
  78   }
  79
  80   class ReadPtr {
  81     friend class ReadMostlySharedPtr;
  82    public:
  83     ReadPtr() {}
  84     void reset() {
  85       ref_ = nullptr;
  86       ptr_.reset();
  87     }
  88     explicit operator bool() const {
  89       return (ref_ != nullptr);
  90     }
  91     bool operator ==(T* ptr) const {
  92       return ref_ == ptr;
  93     }
  94     bool operator ==(std::nullptr_t) const {
  95       return ref_ == nullptr;
  96     }
  97     T* operator->() const { return ref_; }
  98     T& operator*() const { return *ref_; }
  99     T* get() const { return ref_; }
 100    private:
 101     explicit ReadPtr(std::shared_ptr<T>& ptr)
 102         : ptr_(ptr)
 103         , ref_(ptr.get()) {}
 104     std::shared_ptr<T> ptr_;
 105     T* ref_{nullptr};
 106   };
 107
 108   /**
 109    * Returns a shared_ptr to the managed object.
 110    */
 111   ReadPtr load() const {
 112     auto& local = *threadLocalCache_;
 113
 114     std::lock_guard<folly::SpinLock> local_lock(local.lock);
 115
 116     if (!local.ptr.hasValue()) {
 117       std::lock_guard<std::mutex> lock(mutex_);
 118       if (!masterPtr_) {
 119         local.ptr.emplace(nullptr);
 120       } else {
 121         // The following expression is tricky.
 122         //
 123         // It creates a shared_ptr<shared_ptr<T>> that points to a copy of
 124         // masterPtr_. The reference counter of this shared_ptr<shared_ptr<T>>
 125         // will normally only be modified from this thread, which avoids
 126         // cache line bouncing. (Though the caller is free to pass the pointer
 127         // to other threads and bump reference counter from there)
 128         //
 129         // Then this shared_ptr<shared_ptr<T>> is turned into shared_ptr<T>.
 130         // This means that the returned shared_ptr<T> will internally point to
 131         // control block of the shared_ptr<shared_ptr<T>>, but will dereference
 132         // to T, not shared_ptr<T>.
 133         local.ptr = makeCachedCopy(masterPtr_);
 134       }
 135     }
 136
 137     // The return statement makes the copy before destroying local variables,
 138     // so local.ptr is only accessed under local.lock here.
 139     return ReadPtr(local.ptr.value());
 140   }
 141
 142  private:
 143
 144   // non copyable
 145   ReadMostlySharedPtr(const ReadMostlySharedPtr&) = delete;
 146   ReadMostlySharedPtr& operator=(const ReadMostlySharedPtr&) = delete;
 147
 148   struct CachedPointer {
 149     folly::Optional<std::shared_ptr<T>> ptr;
 150     folly::SpinLock lock;
 151   };
 152
 153   std::shared_ptr<T> masterPtr_;
 154
 155   // Instead of using Tag as tag for ThreadLocal, effectively use pair (T, Tag),
 156   // which is more granular.
 157   struct ThreadLocalTag {};
 158
 159   mutable folly::ThreadLocal<CachedPointer, ThreadLocalTag> threadLocalCache_;
 160
 161   // Ensures safety between concurrent store() and load() calls
 162   mutable std::mutex mutex_;
 163
 164   std::shared_ptr<T>
 165   makeCachedCopy(const std::shared_ptr<T> &ptr) const {
 166     // For std::shared_ptr wrap a copy in another std::shared_ptr to
 167     // avoid cache line bouncing.
 168     //
 169     // The following expression is tricky.
 170     //
 171     // It creates a shared_ptr<shared_ptr<T>> that points to a copy of
 172     // masterPtr_. The reference counter of this shared_ptr<shared_ptr<T>>
 173     // will normally only be modified from this thread, which avoids
 174     // cache line bouncing. (Though the caller is free to pass the pointer
 175     // to other threads and bump reference counter from there)
 176     //
 177     // Then this shared_ptr<shared_ptr<T>> is turned into shared_ptr<T>.
 178     // This means that the returned shared_ptr<T> will internally point to
 179     // control block of the shared_ptr<shared_ptr<T>>, but will dereference
 180     // to T, not shared_ptr<T>.
 181     return std::shared_ptr<T>(
 182       std::make_shared<std::shared_ptr<T>>(ptr), ptr.get());
 183   }
 184
 185 };
 186
 187 }