81fa1c88a57422279306fc4057f6abaecb39f68d
[folly.git] / folly / AtomicHashArray-inl.h
1 /*
2  * Copyright 2013 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 #ifndef FOLLY_ATOMICHASHARRAY_H_
18 #error "This should only be included by AtomicHashArray.h"
19 #endif
20
21 #include "folly/Bits.h"
22 #include "folly/detail/AtomicHashUtils.h"
23
24 namespace folly {
25
26 // AtomicHashArray private constructor --
27 template <class KeyT, class ValueT,
28           class HashFcn, class EqualFcn, class Allocator>
29 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
30 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
31                 KeyT erasedKey, double maxLoadFactor, size_t cacheSize)
32     : capacity_(capacity), maxEntries_(size_t(maxLoadFactor * capacity_ + 0.5)),
33       kEmptyKey_(emptyKey), kLockedKey_(lockedKey), kErasedKey_(erasedKey),
34       kAnchorMask_(nextPowTwo(capacity_) - 1), numEntries_(0, cacheSize),
35       numPendingEntries_(0, cacheSize), isFull_(0), numErases_(0) {
36 }
37
38 /*
39  * findInternal --
40  *
41  *   Sets ret.second to value found and ret.index to index
42  *   of key and returns true, or if key does not exist returns false and
43  *   ret.index is set to capacity_.
44  */
45 template <class KeyT, class ValueT,
46           class HashFcn, class EqualFcn, class Allocator>
47 typename AtomicHashArray<KeyT, ValueT,
48          HashFcn, EqualFcn, Allocator>::SimpleRetT
49 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
50 findInternal(const KeyT key_in) {
51   DCHECK_NE(key_in, kEmptyKey_);
52   DCHECK_NE(key_in, kLockedKey_);
53   DCHECK_NE(key_in, kErasedKey_);
54   for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
55        ;
56        idx = probeNext(idx, numProbes)) {
57     const KeyT key = acquireLoadKey(cells_[idx]);
58     if (LIKELY(EqualFcn()(key, key_in))) {
59       return SimpleRetT(idx, true);
60     }
61     if (UNLIKELY(key == kEmptyKey_)) {
62       // if we hit an empty element, this key does not exist
63       return SimpleRetT(capacity_, false);
64     }
65     ++numProbes;
66     if (UNLIKELY(numProbes >= capacity_)) {
67       // probed every cell...fail
68       return SimpleRetT(capacity_, false);
69     }
70   }
71 }
72
73 /*
74  * insertInternal --
75  *
76  *   Returns false on failure due to key collision or full.
77  *   Also sets ret.index to the index of the key.  If the map is full, sets
78  *   ret.index = capacity_.  Also sets ret.second to cell value, thus if insert
79  *   successful this will be what we just inserted, if there is a key collision
80  *   this will be the previously inserted value, and if the map is full it is
81  *   default.
82  */
83 template <class KeyT, class ValueT,
84           class HashFcn, class EqualFcn, class Allocator>
85 template <class T>
86 typename AtomicHashArray<KeyT, ValueT,
87          HashFcn, EqualFcn, Allocator>::SimpleRetT
88 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
89 insertInternal(KeyT key_in, T&& value) {
90   const short NO_NEW_INSERTS = 1;
91   const short NO_PENDING_INSERTS = 2;
92   CHECK_NE(key_in, kEmptyKey_);
93   CHECK_NE(key_in, kLockedKey_);
94   CHECK_NE(key_in, kErasedKey_);
95
96   size_t idx = keyToAnchorIdx(key_in);
97   size_t numProbes = 0;
98   for (;;) {
99     DCHECK_LT(idx, capacity_);
100     value_type* cell = &cells_[idx];
101     if (relaxedLoadKey(*cell) == kEmptyKey_) {
102       // NOTE: isFull_ is set based on numEntries_.readFast(), so it's
103       // possible to insert more than maxEntries_ entries. However, it's not
104       // possible to insert past capacity_.
105       ++numPendingEntries_;
106       if (isFull_.load(std::memory_order_acquire)) {
107         --numPendingEntries_;
108
109         // Before deciding whether this insert succeeded, this thread needs to
110         // wait until no other thread can add a new entry.
111
112         // Correctness assumes isFull_ is true at this point. If
113         // another thread now does ++numPendingEntries_, we expect it
114         // to pass the isFull_.load() test above. (It shouldn't insert
115         // a new entry.)
116         FOLLY_SPIN_WAIT(
117           isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS
118             && numPendingEntries_.readFull() != 0
119         );
120         isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
121
122         if (relaxedLoadKey(*cell) == kEmptyKey_) {
123           // Don't insert past max load factor
124           return SimpleRetT(capacity_, false);
125         }
126       } else {
127         // An unallocated cell. Try once to lock it. If we succeed, insert here.
128         // If we fail, fall through to comparison below; maybe the insert that
129         // just beat us was for this very key....
130         if (tryLockCell(cell)) {
131           // Write the value - done before unlocking
132           try {
133             DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
134             /*
135              * This happens using the copy constructor because we won't have
136              * constructed a lhs to use an assignment operator on when
137              * values are being set.
138              */
139             new (&cell->second) ValueT(std::forward<T>(value));
140             unlockCell(cell, key_in); // Sets the new key
141           } catch (...) {
142             // Transition back to empty key---requires handling
143             // locked->empty below.
144             unlockCell(cell, kEmptyKey_);
145             --numPendingEntries_;
146             throw;
147           }
148           // Direct comparison rather than EqualFcn ok here
149           // (we just inserted it)
150           DCHECK(relaxedLoadKey(*cell) == key_in);
151           --numPendingEntries_;
152           ++numEntries_;  // This is a thread cached atomic increment :)
153           if (numEntries_.readFast() >= maxEntries_) {
154             isFull_.store(NO_NEW_INSERTS, std::memory_order_relaxed);
155           }
156           return SimpleRetT(idx, true);
157         }
158         --numPendingEntries_;
159       }
160     }
161     DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
162     if (kLockedKey_ == acquireLoadKey(*cell)) {
163       FOLLY_SPIN_WAIT(
164         kLockedKey_ == acquireLoadKey(*cell)
165       );
166     }
167
168     const KeyT thisKey = acquireLoadKey(*cell);
169     if (EqualFcn()(thisKey, key_in)) {
170       // Found an existing entry for our key, but we don't overwrite the
171       // previous value.
172       return SimpleRetT(idx, false);
173     } else if (thisKey == kEmptyKey_ || thisKey == kLockedKey_) {
174       // We need to try again (i.e., don't increment numProbes or
175       // advance idx): this case can happen if the constructor for
176       // ValueT threw for this very cell (the rethrow block above).
177       continue;
178     }
179
180     ++numProbes;
181     if (UNLIKELY(numProbes >= capacity_)) {
182       // probed every cell...fail
183       return SimpleRetT(capacity_, false);
184     }
185
186     idx = probeNext(idx, numProbes);
187   }
188 }
189
190
191 /*
192  * erase --
193  *
194  *   This will attempt to erase the given key key_in if the key is found. It
195  *   returns 1 iff the key was located and marked as erased, and 0 otherwise.
196  *
197  *   Memory is not freed or reclaimed by erase, i.e. the cell containing the
198  *   erased key will never be reused. If there's an associated value, we won't
199  *   touch it either.
200  */
201 template <class KeyT, class ValueT,
202           class HashFcn, class EqualFcn, class Allocator>
203 size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
204 erase(KeyT key_in) {
205   CHECK_NE(key_in, kEmptyKey_);
206   CHECK_NE(key_in, kLockedKey_);
207   CHECK_NE(key_in, kErasedKey_);
208   for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
209        ;
210        idx = probeNext(idx, numProbes)) {
211     DCHECK_LT(idx, capacity_);
212     value_type* cell = &cells_[idx];
213     KeyT currentKey = acquireLoadKey(*cell);
214     if (currentKey == kEmptyKey_ || currentKey == kLockedKey_) {
215       // If we hit an empty (or locked) element, this key does not exist. This
216       // is similar to how it's handled in find().
217       return 0;
218     }
219     if (EqualFcn()(currentKey, key_in)) {
220       // Found an existing entry for our key, attempt to mark it erased.
221       // Some other thread may have erased our key, but this is ok.
222       KeyT expect = currentKey;
223       if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
224         numErases_.fetch_add(1, std::memory_order_relaxed);
225
226         // Even if there's a value in the cell, we won't delete (or even
227         // default construct) it because some other thread may be accessing it.
228         // Locking it meanwhile won't work either since another thread may be
229         // holding a pointer to it.
230
231         // We found the key and successfully erased it.
232         return 1;
233       }
234       // If another thread succeeds in erasing our key, we'll stop our search.
235       return 0;
236     }
237     ++numProbes;
238     if (UNLIKELY(numProbes >= capacity_)) {
239       // probed every cell...fail
240       return 0;
241     }
242   }
243 }
244
245 template <class KeyT, class ValueT,
246           class HashFcn, class EqualFcn, class Allocator>
247 const typename AtomicHashArray<KeyT, ValueT,
248       HashFcn, EqualFcn, Allocator>::Config
249 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
250
251 template <class KeyT, class ValueT,
252          class HashFcn, class EqualFcn, class Allocator>
253 typename AtomicHashArray<KeyT, ValueT,
254          HashFcn, EqualFcn, Allocator>::SmartPtr
255 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
256 create(size_t maxSize, const Config& c) {
257   CHECK_LE(c.maxLoadFactor, 1.0);
258   CHECK_GT(c.maxLoadFactor, 0.0);
259   CHECK_NE(c.emptyKey, c.lockedKey);
260   size_t capacity = size_t(maxSize / c.maxLoadFactor);
261   size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
262
263   auto const mem = Allocator().allocate(sz);
264   try {
265     new (mem) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
266                               c.maxLoadFactor, c.entryCountThreadCacheSize);
267   } catch (...) {
268     Allocator().deallocate(mem, sz);
269     throw;
270   }
271
272   SmartPtr map(static_cast<AtomicHashArray*>((void *)mem));
273
274   /*
275    * Mark all cells as empty.
276    *
277    * Note: we're bending the rules a little here accessing the key
278    * element in our cells even though the cell object has not been
279    * constructed, and casting them to atomic objects (see cellKeyPtr).
280    * (Also, in fact we never actually invoke the value_type
281    * constructor.)  This is in order to avoid needing to default
282    * construct a bunch of value_type when we first start up: if you
283    * have an expensive default constructor for the value type this can
284    * noticeably speed construction time for an AHA.
285    */
286   FOR_EACH_RANGE(i, 0, map->capacity_) {
287     cellKeyPtr(map->cells_[i])->store(map->kEmptyKey_,
288       std::memory_order_relaxed);
289   }
290   return map;
291 }
292
293 template <class KeyT, class ValueT,
294           class HashFcn, class EqualFcn, class Allocator>
295 void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
296 destroy(AtomicHashArray* p) {
297   assert(p);
298
299   size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;
300
301   FOR_EACH_RANGE(i, 0, p->capacity_) {
302     if (p->cells_[i].first != p->kEmptyKey_) {
303       p->cells_[i].~value_type();
304     }
305   }
306   p->~AtomicHashArray();
307
308   Allocator().deallocate((char *)p, sz);
309 }
310
311 // clear -- clears all keys and values in the map and resets all counters
312 template <class KeyT, class ValueT,
313           class HashFcn, class EqualFcn, class Allocator>
314 void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
315 clear() {
316   FOR_EACH_RANGE(i, 0, capacity_) {
317     if (cells_[i].first != kEmptyKey_) {
318       cells_[i].~value_type();
319       *const_cast<KeyT*>(&cells_[i].first) = kEmptyKey_;
320     }
321     CHECK(cells_[i].first == kEmptyKey_);
322   }
323   numEntries_.set(0);
324   numPendingEntries_.set(0);
325   isFull_.store(0, std::memory_order_relaxed);
326   numErases_.store(0, std::memory_order_relaxed);
327 }
328
329
330 // Iterator implementation
331
332 template <class KeyT, class ValueT,
333           class HashFcn, class EqualFcn, class Allocator>
334 template <class ContT, class IterVal>
335 struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
336     : boost::iterator_facade<aha_iterator<ContT,IterVal>,
337                              IterVal,
338                              boost::forward_traversal_tag>
339 {
340   explicit aha_iterator() : aha_(0) {}
341
342   // Conversion ctor for interoperability between const_iterator and
343   // iterator.  The enable_if<> magic keeps us well-behaved for
344   // is_convertible<> (v. the iterator_facade documentation).
345   template<class OtherContT, class OtherVal>
346   aha_iterator(const aha_iterator<OtherContT,OtherVal>& o,
347                typename std::enable_if<
348                std::is_convertible<OtherVal*,IterVal*>::value >::type* = 0)
349       : aha_(o.aha_)
350       , offset_(o.offset_)
351   {}
352
353   explicit aha_iterator(ContT* array, size_t offset)
354       : aha_(array)
355       , offset_(offset)
356   {
357     advancePastEmpty();
358   }
359
360   // Returns unique index that can be used with findAt().
361   // WARNING: The following function will fail silently for hashtable
362   // with capacity > 2^32
363   uint32_t getIndex() const { return offset_; }
364
365  private:
366   friend class AtomicHashArray;
367   friend class boost::iterator_core_access;
368
369   void increment() {
370     ++offset_;
371     advancePastEmpty();
372   }
373
374   bool equal(const aha_iterator& o) const {
375     return aha_ == o.aha_ && offset_ == o.offset_;
376   }
377
378   IterVal& dereference() const {
379     return aha_->cells_[offset_];
380   }
381
382   void advancePastEmpty() {
383     while (offset_ < aha_->capacity_ && !isValid()) {
384       ++offset_;
385     }
386   }
387
388   bool isValid() const {
389     KeyT key = acquireLoadKey(aha_->cells_[offset_]);
390     return key != aha_->kEmptyKey_  &&
391       key != aha_->kLockedKey_ &&
392       key != aha_->kErasedKey_;
393   }
394
395  private:
396   ContT* aha_;
397   size_t offset_;
398 }; // aha_iterator
399
400 } // namespace folly
401
402 #undef FOLLY_SPIN_WAIT