2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_ATOMICHASHARRAY_H_
18 #error "This should only be included by AtomicHashArray.h"
21 #include <type_traits>
23 #include <folly/Bits.h>
24 #include <folly/detail/AtomicHashUtils.h>
28 // AtomicHashArray private constructor --
29 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
30 class Allocator, class ProbeFcn, class KeyConvertFcn>
31 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
32 Allocator, ProbeFcn, KeyConvertFcn>::
33 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
34 KeyT erasedKey, double _maxLoadFactor, uint32_t cacheSize)
35 : capacity_(capacity),
36 maxEntries_(size_t(_maxLoadFactor * capacity_ + 0.5)),
37 kEmptyKey_(emptyKey), kLockedKey_(lockedKey), kErasedKey_(erasedKey),
38 kAnchorMask_(nextPowTwo(capacity_) - 1), numEntries_(0, cacheSize),
39 numPendingEntries_(0, cacheSize), isFull_(0), numErases_(0) {
45 * Sets ret.second to value found and ret.index to index
46 * of key and returns true, or if key does not exist returns false and
47 * ret.index is set to capacity_.
49 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
50 class Allocator, class ProbeFcn, class KeyConvertFcn>
51 template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
52 typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
53 Allocator, ProbeFcn, KeyConvertFcn>::SimpleRetT
54 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
55 Allocator, ProbeFcn, KeyConvertFcn>::
56 findInternal(const LookupKeyT key_in) {
57 checkLegalKeyIfKey<LookupKeyT>(key_in);
59 for (size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in),
62 idx = ProbeFcn()(idx, numProbes, capacity_)) {
63 const KeyT key = acquireLoadKey(cells_[idx]);
64 if (LIKELY(LookupEqualFcn()(key, key_in))) {
65 return SimpleRetT(idx, true);
67 if (UNLIKELY(key == kEmptyKey_)) {
68 // if we hit an empty element, this key does not exist
69 return SimpleRetT(capacity_, false);
71 // NOTE: the way we count numProbes must be same in find(), insert(),
72 // and erase(). Otherwise it may break probing.
74 if (UNLIKELY(numProbes >= capacity_)) {
75 // probed every cell...fail
76 return SimpleRetT(capacity_, false);
84 * Returns false on failure due to key collision or full.
85 * Also sets ret.index to the index of the key. If the map is full, sets
86 * ret.index = capacity_. Also sets ret.second to cell value, thus if insert
87 * successful this will be what we just inserted, if there is a key collision
88 * this will be the previously inserted value, and if the map is full it is
91 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
92 class Allocator, class ProbeFcn, class KeyConvertFcn>
93 template <typename LookupKeyT,
94 typename LookupHashFcn,
95 typename LookupEqualFcn,
96 typename LookupKeyToKeyFcn,
98 typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
99 Allocator, ProbeFcn, KeyConvertFcn>::SimpleRetT
100 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
101 Allocator, ProbeFcn, KeyConvertFcn>::
102 insertInternal(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
103 const short NO_NEW_INSERTS = 1;
104 const short NO_PENDING_INSERTS = 2;
105 checkLegalKeyIfKey<LookupKeyT>(key_in);
107 size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in);
108 size_t numProbes = 0;
110 DCHECK_LT(idx, capacity_);
111 value_type* cell = &cells_[idx];
112 if (relaxedLoadKey(*cell) == kEmptyKey_) {
113 // NOTE: isFull_ is set based on numEntries_.readFast(), so it's
114 // possible to insert more than maxEntries_ entries. However, it's not
115 // possible to insert past capacity_.
116 ++numPendingEntries_;
117 if (isFull_.load(std::memory_order_acquire)) {
118 --numPendingEntries_;
120 // Before deciding whether this insert succeeded, this thread needs to
121 // wait until no other thread can add a new entry.
123 // Correctness assumes isFull_ is true at this point. If
124 // another thread now does ++numPendingEntries_, we expect it
125 // to pass the isFull_.load() test above. (It shouldn't insert
127 detail::atomic_hash_spin_wait([&] {
129 (isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS) &&
130 (numPendingEntries_.readFull() != 0);
132 isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
134 if (relaxedLoadKey(*cell) == kEmptyKey_) {
135 // Don't insert past max load factor
136 return SimpleRetT(capacity_, false);
139 // An unallocated cell. Try once to lock it. If we succeed, insert here.
140 // If we fail, fall through to comparison below; maybe the insert that
141 // just beat us was for this very key....
142 if (tryLockCell(cell)) {
144 // Write the value - done before unlocking
146 key_new = LookupKeyToKeyFcn()(key_in);
147 typedef typename std::remove_const<LookupKeyT>::type
149 constexpr bool kAlreadyChecked =
150 std::is_same<KeyT, LookupKeyTNoConst>::value;
151 if (!kAlreadyChecked) {
152 checkLegalKeyIfKey(key_new);
154 DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
155 // A const mapped_type is only constant once constructed, so cast
156 // away any const for the placement new here.
157 using mapped = typename std::remove_const<mapped_type>::type;
158 new (const_cast<mapped*>(&cell->second))
159 ValueT(std::forward<ArgTs>(vCtorArgs)...);
160 unlockCell(cell, key_new); // Sets the new key
162 // Transition back to empty key---requires handling
163 // locked->empty below.
164 unlockCell(cell, kEmptyKey_);
165 --numPendingEntries_;
168 // An erase() can race here and delete right after our insertion
169 // Direct comparison rather than EqualFcn ok here
170 // (we just inserted it)
171 DCHECK(relaxedLoadKey(*cell) == key_new ||
172 relaxedLoadKey(*cell) == kErasedKey_);
173 --numPendingEntries_;
174 ++numEntries_; // This is a thread cached atomic increment :)
175 if (numEntries_.readFast() >= maxEntries_) {
176 isFull_.store(NO_NEW_INSERTS, std::memory_order_relaxed);
178 return SimpleRetT(idx, true);
180 --numPendingEntries_;
183 DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
184 if (kLockedKey_ == acquireLoadKey(*cell)) {
185 detail::atomic_hash_spin_wait([&] {
186 return kLockedKey_ == acquireLoadKey(*cell);
190 const KeyT thisKey = acquireLoadKey(*cell);
191 if (LookupEqualFcn()(thisKey, key_in)) {
192 // Found an existing entry for our key, but we don't overwrite the
194 return SimpleRetT(idx, false);
195 } else if (thisKey == kEmptyKey_ || thisKey == kLockedKey_) {
196 // We need to try again (i.e., don't increment numProbes or
197 // advance idx): this case can happen if the constructor for
198 // ValueT threw for this very cell (the rethrow block above).
203 // NOTE: the way we count numProbes must be same in find(),
204 // insert(), and erase(). Otherwise it may break probing.
206 if (UNLIKELY(numProbes >= capacity_)) {
207 // probed every cell...fail
208 return SimpleRetT(capacity_, false);
211 idx = ProbeFcn()(idx, numProbes, capacity_);
218 * This will attempt to erase the given key key_in if the key is found. It
219 * returns 1 iff the key was located and marked as erased, and 0 otherwise.
221 * Memory is not freed or reclaimed by erase, i.e. the cell containing the
222 * erased key will never be reused. If there's an associated value, we won't
225 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
226 class Allocator, class ProbeFcn, class KeyConvertFcn>
227 size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
228 Allocator, ProbeFcn, KeyConvertFcn>::
230 CHECK_NE(key_in, kEmptyKey_);
231 CHECK_NE(key_in, kLockedKey_);
232 CHECK_NE(key_in, kErasedKey_);
234 for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
236 idx = ProbeFcn()(idx, numProbes, capacity_)) {
237 DCHECK_LT(idx, capacity_);
238 value_type* cell = &cells_[idx];
239 KeyT currentKey = acquireLoadKey(*cell);
240 if (currentKey == kEmptyKey_ || currentKey == kLockedKey_) {
241 // If we hit an empty (or locked) element, this key does not exist. This
242 // is similar to how it's handled in find().
245 if (EqualFcn()(currentKey, key_in)) {
246 // Found an existing entry for our key, attempt to mark it erased.
247 // Some other thread may have erased our key, but this is ok.
248 KeyT expect = currentKey;
249 if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
250 numErases_.fetch_add(1, std::memory_order_relaxed);
252 // Even if there's a value in the cell, we won't delete (or even
253 // default construct) it because some other thread may be accessing it.
254 // Locking it meanwhile won't work either since another thread may be
255 // holding a pointer to it.
257 // We found the key and successfully erased it.
260 // If another thread succeeds in erasing our key, we'll stop our search.
264 // NOTE: the way we count numProbes must be same in find(), insert(),
265 // and erase(). Otherwise it may break probing.
267 if (UNLIKELY(numProbes >= capacity_)) {
268 // probed every cell...fail
274 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
275 class Allocator, class ProbeFcn, class KeyConvertFcn>
276 typename AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
277 Allocator, ProbeFcn, KeyConvertFcn>::SmartPtr
278 AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
279 Allocator, ProbeFcn, KeyConvertFcn>::
280 create(size_t maxSize, const Config& c) {
281 CHECK_LE(c.maxLoadFactor, 1.0);
282 CHECK_GT(c.maxLoadFactor, 0.0);
283 CHECK_NE(c.emptyKey, c.lockedKey);
284 size_t capacity = size_t(maxSize / c.maxLoadFactor);
285 size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
287 auto const mem = Allocator().allocate(sz);
289 new (mem) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
290 c.maxLoadFactor, c.entryCountThreadCacheSize);
292 Allocator().deallocate(mem, sz);
296 SmartPtr map(static_cast<AtomicHashArray*>((void *)mem));
299 * Mark all cells as empty.
301 * Note: we're bending the rules a little here accessing the key
302 * element in our cells even though the cell object has not been
303 * constructed, and casting them to atomic objects (see cellKeyPtr).
304 * (Also, in fact we never actually invoke the value_type
305 * constructor.) This is in order to avoid needing to default
306 * construct a bunch of value_type when we first start up: if you
307 * have an expensive default constructor for the value type this can
308 * noticeably speed construction time for an AHA.
310 FOR_EACH_RANGE(i, 0, map->capacity_) {
311 cellKeyPtr(map->cells_[i])->store(map->kEmptyKey_,
312 std::memory_order_relaxed);
317 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
318 class Allocator, class ProbeFcn, class KeyConvertFcn>
319 void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
320 Allocator, ProbeFcn, KeyConvertFcn>::
321 destroy(AtomicHashArray* p) {
324 size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;
326 FOR_EACH_RANGE(i, 0, p->capacity_) {
327 if (p->cells_[i].first != p->kEmptyKey_) {
328 p->cells_[i].~value_type();
331 p->~AtomicHashArray();
333 Allocator().deallocate((char *)p, sz);
336 // clear -- clears all keys and values in the map and resets all counters
337 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
338 class Allocator, class ProbeFcn, class KeyConvertFcn>
339 void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
340 Allocator, ProbeFcn, KeyConvertFcn>::
342 FOR_EACH_RANGE(i, 0, capacity_) {
343 if (cells_[i].first != kEmptyKey_) {
344 cells_[i].~value_type();
345 *const_cast<KeyT*>(&cells_[i].first) = kEmptyKey_;
347 CHECK(cells_[i].first == kEmptyKey_);
350 numPendingEntries_.set(0);
351 isFull_.store(0, std::memory_order_relaxed);
352 numErases_.store(0, std::memory_order_relaxed);
356 // Iterator implementation
358 template <class KeyT, class ValueT, class HashFcn, class EqualFcn,
359 class Allocator, class ProbeFcn, class KeyConvertFcn>
360 template <class ContT, class IterVal>
361 struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn,
362 Allocator, ProbeFcn, KeyConvertFcn>::
364 : boost::iterator_facade<aha_iterator<ContT,IterVal>,
366 boost::forward_traversal_tag>
368 explicit aha_iterator() : aha_(0) {}
370 // Conversion ctor for interoperability between const_iterator and
371 // iterator. The enable_if<> magic keeps us well-behaved for
372 // is_convertible<> (v. the iterator_facade documentation).
373 template<class OtherContT, class OtherVal>
374 aha_iterator(const aha_iterator<OtherContT,OtherVal>& o,
375 typename std::enable_if<
376 std::is_convertible<OtherVal*,IterVal*>::value >::type* = 0)
381 explicit aha_iterator(ContT* array, size_t offset)
386 // Returns unique index that can be used with findAt().
387 // WARNING: The following function will fail silently for hashtable
388 // with capacity > 2^32
389 uint32_t getIndex() const { return offset_; }
391 void advancePastEmpty() {
392 while (offset_ < aha_->capacity_ && !isValid()) {
398 friend class AtomicHashArray;
399 friend class boost::iterator_core_access;
406 bool equal(const aha_iterator& o) const {
407 return aha_ == o.aha_ && offset_ == o.offset_;
410 IterVal& dereference() const {
411 return aha_->cells_[offset_];
414 bool isValid() const {
415 KeyT key = acquireLoadKey(aha_->cells_[offset_]);
416 return key != aha_->kEmptyKey_ &&
417 key != aha_->kLockedKey_ &&
418 key != aha_->kErasedKey_;