1 /* 2 * Copyright (c) Facebook, Inc. and its affiliates. 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 17 // @author: Xin Liu <xliux@fb.com> 18 19 #pragma once 20 21 #include <algorithm> 22 #include <atomic> 23 #include <climits> 24 #include <cmath> 25 #include <memory> 26 #include <mutex> 27 #include <type_traits> 28 #include <vector> 29 30 #include <boost/random.hpp> 31 #include <glog/logging.h> 32 33 #include <folly/Memory.h> 34 #include <folly/ThreadLocal.h> 35 #include <folly/synchronization/MicroSpinLock.h> 36 37 namespace folly { 38 namespace detail { 39 40 template <typename ValT, typename NodeT> 41 class csl_iterator; 42 43 template <typename T> 44 class SkipListNode { 45 enum : uint16_t { 46 IS_HEAD_NODE = 1, 47 MARKED_FOR_REMOVAL = (1 << 1), 48 FULLY_LINKED = (1 << 2), 49 }; 50 51 public: 52 typedef T value_type; 53 54 SkipListNode(const SkipListNode&) = delete; 55 SkipListNode& operator=(const SkipListNode&) = delete; 56 57 template < 58 typename NodeAlloc, 59 typename U, 60 typename = 61 typename std::enable_if<std::is_convertible<U, T>::value>::type> 62 static SkipListNode* create( 63 NodeAlloc& alloc, int height, U&& data, bool isHead = false) { 64 DCHECK(height >= 1 && height < 64) << height; 65 66 size_t size = 67 sizeof(SkipListNode) + height * sizeof(std::atomic<SkipListNode*>); 68 auto storage = std::allocator_traits<NodeAlloc>::allocate(alloc, size); 69 // do placement new 70 return new (storage) 71 SkipListNode(uint8_t(height), std::forward<U>(data), isHead); 72 } 73 74 template <typename NodeAlloc> destroy(NodeAlloc & alloc,SkipListNode * node)75 static void destroy(NodeAlloc& alloc, SkipListNode* node) { 76 size_t size = sizeof(SkipListNode) + 77 node->height_ * sizeof(std::atomic<SkipListNode*>); 78 node->~SkipListNode(); 79 std::allocator_traits<NodeAlloc>::deallocate( 80 alloc, typename std::allocator_traits<NodeAlloc>::pointer(node), size); 81 } 82 83 template <typename NodeAlloc> 84 struct DestroyIsNoOp : StrictConjunction< 85 AllocatorHasTrivialDeallocate<NodeAlloc>, 86 std::is_trivially_destructible<SkipListNode>> {}; 87 88 // copy the head node to a new head node assuming lock acquired copyHead(SkipListNode * node)89 SkipListNode* copyHead(SkipListNode* node) { 90 DCHECK(node != nullptr && height_ > node->height_); 91 setFlags(node->getFlags()); 92 for (uint8_t i = 0; i < node->height_; ++i) { 93 setSkip(i, node->skip(i)); 94 } 95 return this; 96 } 97 skip(int layer)98 inline SkipListNode* skip(int layer) const { 99 DCHECK_LT(layer, height_); 100 return skip_[layer].load(std::memory_order_acquire); 101 } 102 103 // next valid node as in the linked list next()104 SkipListNode* next() { 105 SkipListNode* node; 106 for (node = skip(0); (node != nullptr && node->markedForRemoval()); 107 node = node->skip(0)) { 108 } 109 return node; 110 } 111 setSkip(uint8_t h,SkipListNode * next)112 void setSkip(uint8_t h, SkipListNode* next) { 113 DCHECK_LT(h, height_); 114 skip_[h].store(next, std::memory_order_release); 115 } 116 data()117 value_type& data() { return data_; } data()118 const value_type& data() const { return data_; } maxLayer()119 int maxLayer() const { return height_ - 1; } height()120 int height() const { return height_; } 121 acquireGuard()122 std::unique_lock<MicroSpinLock> acquireGuard() { 123 return std::unique_lock<MicroSpinLock>(spinLock_); 124 } 125 fullyLinked()126 bool fullyLinked() const { return getFlags() & FULLY_LINKED; } markedForRemoval()127 bool markedForRemoval() const { return getFlags() & MARKED_FOR_REMOVAL; } isHeadNode()128 bool isHeadNode() const { return getFlags() & IS_HEAD_NODE; } 129 setIsHeadNode()130 void setIsHeadNode() { setFlags(uint16_t(getFlags() | IS_HEAD_NODE)); } setFullyLinked()131 void setFullyLinked() { setFlags(uint16_t(getFlags() | FULLY_LINKED)); } setMarkedForRemoval()132 void setMarkedForRemoval() { 133 setFlags(uint16_t(getFlags() | MARKED_FOR_REMOVAL)); 134 } 135 136 private: 137 // Note! this can only be called from create() as a placement new. 138 template <typename U> SkipListNode(uint8_t height,U && data,bool isHead)139 SkipListNode(uint8_t height, U&& data, bool isHead) 140 : height_(height), data_(std::forward<U>(data)) { 141 spinLock_.init(); 142 setFlags(0); 143 if (isHead) { 144 setIsHeadNode(); 145 } 146 // need to explicitly init the dynamic atomic pointer array 147 for (uint8_t i = 0; i < height_; ++i) { 148 new (&skip_[i]) std::atomic<SkipListNode*>(nullptr); 149 } 150 } 151 ~SkipListNode()152 ~SkipListNode() { 153 for (uint8_t i = 0; i < height_; ++i) { 154 skip_[i].~atomic(); 155 } 156 } 157 getFlags()158 uint16_t getFlags() const { return flags_.load(std::memory_order_acquire); } setFlags(uint16_t flags)159 void setFlags(uint16_t flags) { 160 flags_.store(flags, std::memory_order_release); 161 } 162 163 // TODO(xliu): on x86_64, it's possible to squeeze these into 164 // skip_[0] to maybe save 8 bytes depending on the data alignments. 165 // NOTE: currently this is x86_64 only anyway, due to the 166 // MicroSpinLock. 167 std::atomic<uint16_t> flags_; 168 const uint8_t height_; 169 MicroSpinLock spinLock_; 170 171 value_type data_; 172 173 std::atomic<SkipListNode*> skip_[0]; 174 }; 175 176 class SkipListRandomHeight { 177 enum { kMaxHeight = 64 }; 178 179 public: 180 // make it a singleton. instance()181 static SkipListRandomHeight* instance() { 182 static SkipListRandomHeight instance_; 183 return &instance_; 184 } 185 getHeight(int maxHeight)186 int getHeight(int maxHeight) const { 187 DCHECK_LE(maxHeight, kMaxHeight) << "max height too big!"; 188 double p = randomProb(); 189 for (int i = 0; i < maxHeight; ++i) { 190 if (p < lookupTable_[i]) { 191 return i + 1; 192 } 193 } 194 return maxHeight; 195 } 196 getSizeLimit(int height)197 size_t getSizeLimit(int height) const { 198 DCHECK_LT(height, kMaxHeight); 199 return sizeLimitTable_[height]; 200 } 201 202 private: SkipListRandomHeight()203 SkipListRandomHeight() { initLookupTable(); } 204 initLookupTable()205 void initLookupTable() { 206 // set skip prob = 1/E 207 static const double kProbInv = exp(1); 208 static const double kProb = 1.0 / kProbInv; 209 static const size_t kMaxSizeLimit = std::numeric_limits<size_t>::max(); 210 211 double sizeLimit = 1; 212 double p = lookupTable_[0] = (1 - kProb); 213 sizeLimitTable_[0] = 1; 214 for (int i = 1; i < kMaxHeight - 1; ++i) { 215 p *= kProb; 216 sizeLimit *= kProbInv; 217 lookupTable_[i] = lookupTable_[i - 1] + p; 218 sizeLimitTable_[i] = sizeLimit > kMaxSizeLimit 219 ? kMaxSizeLimit 220 : static_cast<size_t>(sizeLimit); 221 } 222 lookupTable_[kMaxHeight - 1] = 1; 223 sizeLimitTable_[kMaxHeight - 1] = kMaxSizeLimit; 224 } 225 randomProb()226 static double randomProb() { 227 static ThreadLocal<boost::lagged_fibonacci2281> rng_; 228 return (*rng_)(); 229 } 230 231 double lookupTable_[kMaxHeight]; 232 size_t sizeLimitTable_[kMaxHeight]; 233 }; 234 235 template <typename NodeType, typename NodeAlloc, typename = void> 236 class NodeRecycler; 237 238 template <typename NodeType, typename NodeAlloc> 239 class NodeRecycler< 240 NodeType, 241 NodeAlloc, 242 typename std::enable_if< 243 !NodeType::template DestroyIsNoOp<NodeAlloc>::value>::type> { 244 public: NodeRecycler(const NodeAlloc & alloc)245 explicit NodeRecycler(const NodeAlloc& alloc) 246 : refs_(0), dirty_(false), alloc_(alloc) { 247 lock_.init(); 248 } 249 NodeRecycler()250 explicit NodeRecycler() : refs_(0), dirty_(false) { lock_.init(); } 251 ~NodeRecycler()252 ~NodeRecycler() { 253 CHECK_EQ(refs(), 0); 254 if (nodes_) { 255 for (auto& node : *nodes_) { 256 NodeType::destroy(alloc_, node); 257 } 258 } 259 } 260 add(NodeType * node)261 void add(NodeType* node) { 262 std::lock_guard<MicroSpinLock> g(lock_); 263 if (nodes_.get() == nullptr) { 264 nodes_ = std::make_unique<std::vector<NodeType*>>(1, node); 265 } else { 266 nodes_->push_back(node); 267 } 268 DCHECK_GT(refs(), 0); 269 dirty_.store(true, std::memory_order_relaxed); 270 } 271 addRef()272 int addRef() { return refs_.fetch_add(1, std::memory_order_acq_rel); } 273 releaseRef()274 int releaseRef() { 275 // This if statement is purely an optimization. It's possible that this 276 // misses an opportunity to delete, but that's OK, we'll try again at 277 // the next opportunity. It does not harm the thread safety. For this 278 // reason, we can use relaxed loads to make the decision. 279 if (!dirty_.load(std::memory_order_relaxed) || refs() > 1) { 280 return refs_.fetch_add(-1, std::memory_order_acq_rel); 281 } 282 283 std::unique_ptr<std::vector<NodeType*>> newNodes; 284 int ret; 285 { 286 // The order at which we lock, add, swap, is very important for 287 // correctness. 288 std::lock_guard<MicroSpinLock> g(lock_); 289 ret = refs_.fetch_add(-1, std::memory_order_acq_rel); 290 if (ret == 1) { 291 // When releasing the last reference, it is safe to remove all the 292 // current nodes in the recycler, as we already acquired the lock here 293 // so no more new nodes can be added, even though new accessors may be 294 // added after this. 295 newNodes.swap(nodes_); 296 dirty_.store(false, std::memory_order_relaxed); 297 } 298 } 299 // TODO(xliu) should we spawn a thread to do this when there are large 300 // number of nodes in the recycler? 301 if (newNodes) { 302 for (auto& node : *newNodes) { 303 NodeType::destroy(alloc_, node); 304 } 305 } 306 return ret; 307 } 308 alloc()309 NodeAlloc& alloc() { return alloc_; } 310 311 private: refs()312 int refs() const { return refs_.load(std::memory_order_relaxed); } 313 314 std::unique_ptr<std::vector<NodeType*>> nodes_; 315 std::atomic<int32_t> refs_; // current number of visitors to the list 316 std::atomic<bool> dirty_; // whether *nodes_ is non-empty 317 MicroSpinLock lock_; // protects access to *nodes_ 318 NodeAlloc alloc_; 319 }; 320 321 // In case of arena allocator, no recycling is necessary, and it's possible 322 // to save on ConcurrentSkipList size. 323 template <typename NodeType, typename NodeAlloc> 324 class NodeRecycler< 325 NodeType, 326 NodeAlloc, 327 typename std::enable_if< 328 NodeType::template DestroyIsNoOp<NodeAlloc>::value>::type> { 329 public: NodeRecycler(const NodeAlloc & alloc)330 explicit NodeRecycler(const NodeAlloc& alloc) : alloc_(alloc) {} 331 addRef()332 void addRef() {} releaseRef()333 void releaseRef() {} 334 add(NodeType *)335 void add(NodeType* /* node */) {} 336 alloc()337 NodeAlloc& alloc() { return alloc_; } 338 339 private: 340 NodeAlloc alloc_; 341 }; 342 343 } // namespace detail 344 } // namespace folly 345