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