1/*
2 * Copyright 2012-present 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 <type_traits>
22
23#include <folly/detail/AtomicHashUtils.h>
24#include <folly/lang/Bits.h>
25
26namespace folly {
27
28// AtomicHashArray private constructor --
29template <
30 class KeyT,
31 class ValueT,
32 class HashFcn,
33 class EqualFcn,
34 class Allocator,
35 class ProbeFcn,
36 class KeyConvertFcn>
37AtomicHashArray<
38 KeyT,
39 ValueT,
40 HashFcn,
41 EqualFcn,
42 Allocator,
43 ProbeFcn,
44 KeyConvertFcn>::
45 AtomicHashArray(
46 size_t capacity,
47 KeyT emptyKey,
48 KeyT lockedKey,
49 KeyT erasedKey,
50 double _maxLoadFactor,
51 uint32_t cacheSize)
52 : capacity_(capacity),
53 maxEntries_(size_t(_maxLoadFactor * capacity_ + 0.5)),
54 kEmptyKey_(emptyKey),
55 kLockedKey_(lockedKey),
56 kErasedKey_(erasedKey),
57 kAnchorMask_(nextPowTwo(capacity_) - 1),
58 numEntries_(0, cacheSize),
59 numPendingEntries_(0, cacheSize),
60 isFull_(0),
61 numErases_(0) {}
62
63/*
64 * findInternal --
65 *
66 * Sets ret.second to value found and ret.index to index
67 * of key and returns true, or if key does not exist returns false and
68 * ret.index is set to capacity_.
69 */
70template <
71 class KeyT,
72 class ValueT,
73 class HashFcn,
74 class EqualFcn,
75 class Allocator,
76 class ProbeFcn,
77 class KeyConvertFcn>
78template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn>
79typename AtomicHashArray<
80 KeyT,
81 ValueT,
82 HashFcn,
83 EqualFcn,
84 Allocator,
85 ProbeFcn,
86 KeyConvertFcn>::SimpleRetT
87AtomicHashArray<
88 KeyT,
89 ValueT,
90 HashFcn,
91 EqualFcn,
92 Allocator,
93 ProbeFcn,
94 KeyConvertFcn>::findInternal(const LookupKeyT key_in) {
95 checkLegalKeyIfKey<LookupKeyT>(key_in);
96
97 for (size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in),
98 numProbes = 0;
99 ;
100 idx = ProbeFcn()(idx, numProbes, capacity_)) {
101 const KeyT key = acquireLoadKey(cells_[idx]);
102 if (LIKELY(LookupEqualFcn()(key, key_in))) {
103 return SimpleRetT(idx, true);
104 }
105 if (UNLIKELY(key == kEmptyKey_)) {
106 // if we hit an empty element, this key does not exist
107 return SimpleRetT(capacity_, false);
108 }
109 // NOTE: the way we count numProbes must be same in find(), insert(),
110 // and erase(). Otherwise it may break probing.
111 ++numProbes;
112 if (UNLIKELY(numProbes >= capacity_)) {
113 // probed every cell...fail
114 return SimpleRetT(capacity_, false);
115 }
116 }
117}
118
119/*
120 * insertInternal --
121 *
122 * Returns false on failure due to key collision or full.
123 * Also sets ret.index to the index of the key. If the map is full, sets
124 * ret.index = capacity_. Also sets ret.second to cell value, thus if insert
125 * successful this will be what we just inserted, if there is a key collision
126 * this will be the previously inserted value, and if the map is full it is
127 * default.
128 */
129template <
130 class KeyT,
131 class ValueT,
132 class HashFcn,
133 class EqualFcn,
134 class Allocator,
135 class ProbeFcn,
136 class KeyConvertFcn>
137template <
138 typename LookupKeyT,
139 typename LookupHashFcn,
140 typename LookupEqualFcn,
141 typename LookupKeyToKeyFcn,
142 typename... ArgTs>
143typename AtomicHashArray<
144 KeyT,
145 ValueT,
146 HashFcn,
147 EqualFcn,
148 Allocator,
149 ProbeFcn,
150 KeyConvertFcn>::SimpleRetT
151AtomicHashArray<
152 KeyT,
153 ValueT,
154 HashFcn,
155 EqualFcn,
156 Allocator,
157 ProbeFcn,
158 KeyConvertFcn>::insertInternal(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
159 const short NO_NEW_INSERTS = 1;
160 const short NO_PENDING_INSERTS = 2;
161 checkLegalKeyIfKey<LookupKeyT>(key_in);
162
163 size_t idx = keyToAnchorIdx<LookupKeyT, LookupHashFcn>(key_in);
164 size_t numProbes = 0;
165 for (;;) {
166 DCHECK_LT(idx, capacity_);
167 value_type* cell = &cells_[idx];
168 if (relaxedLoadKey(*cell) == kEmptyKey_) {
169 // NOTE: isFull_ is set based on numEntries_.readFast(), so it's
170 // possible to insert more than maxEntries_ entries. However, it's not
171 // possible to insert past capacity_.
172 ++numPendingEntries_;
173 if (isFull_.load(std::memory_order_acquire)) {
174 --numPendingEntries_;
175
176 // Before deciding whether this insert succeeded, this thread needs to
177 // wait until no other thread can add a new entry.
178
179 // Correctness assumes isFull_ is true at this point. If
180 // another thread now does ++numPendingEntries_, we expect it
181 // to pass the isFull_.load() test above. (It shouldn't insert
182 // a new entry.)
183 detail::atomic_hash_spin_wait([&] {
184 return (isFull_.load(std::memory_order_acquire) !=
185 NO_PENDING_INSERTS) &&
186 (numPendingEntries_.readFull() != 0);
187 });
188 isFull_.store(NO_PENDING_INSERTS, std::memory_order_release);
189
190 if (relaxedLoadKey(*cell) == kEmptyKey_) {
191 // Don't insert past max load factor
192 return SimpleRetT(capacity_, false);
193 }
194 } else {
195 // An unallocated cell. Try once to lock it. If we succeed, insert here.
196 // If we fail, fall through to comparison below; maybe the insert that
197 // just beat us was for this very key....
198 if (tryLockCell(cell)) {
199 KeyT key_new;
200 // Write the value - done before unlocking
201 try {
202 key_new = LookupKeyToKeyFcn()(key_in);
203 typedef
204 typename std::remove_const<LookupKeyT>::type LookupKeyTNoConst;
205 constexpr bool kAlreadyChecked =
206 std::is_same<KeyT, LookupKeyTNoConst>::value;
207 if (!kAlreadyChecked) {
208 checkLegalKeyIfKey(key_new);
209 }
210 DCHECK(relaxedLoadKey(*cell) == kLockedKey_);
211 // A const mapped_type is only constant once constructed, so cast
212 // away any const for the placement new here.
213 using mapped = typename std::remove_const<mapped_type>::type;
214 new (const_cast<mapped*>(&cell->second))
215 ValueT(std::forward<ArgTs>(vCtorArgs)...);
216 unlockCell(cell, key_new); // Sets the new key
217 } catch (...) {
218 // Transition back to empty key---requires handling
219 // locked->empty below.
220 unlockCell(cell, kEmptyKey_);
221 --numPendingEntries_;
222 throw;
223 }
224 // An erase() can race here and delete right after our insertion
225 // Direct comparison rather than EqualFcn ok here
226 // (we just inserted it)
227 DCHECK(
228 relaxedLoadKey(*cell) == key_new ||
229 relaxedLoadKey(*cell) == kErasedKey_);
230 --numPendingEntries_;
231 ++numEntries_; // This is a thread cached atomic increment :)
232 if (numEntries_.readFast() >= maxEntries_) {
233 isFull_.store(NO_NEW_INSERTS, std::memory_order_relaxed);
234 }
235 return SimpleRetT(idx, true);
236 }
237 --numPendingEntries_;
238 }
239 }
240 DCHECK(relaxedLoadKey(*cell) != kEmptyKey_);
241 if (kLockedKey_ == acquireLoadKey(*cell)) {
242 detail::atomic_hash_spin_wait(
243 [&] { return kLockedKey_ == acquireLoadKey(*cell); });
244 }
245
246 const KeyT thisKey = acquireLoadKey(*cell);
247 if (LookupEqualFcn()(thisKey, key_in)) {
248 // Found an existing entry for our key, but we don't overwrite the
249 // previous value.
250 return SimpleRetT(idx, false);
251 } else if (thisKey == kEmptyKey_ || thisKey == kLockedKey_) {
252 // We need to try again (i.e., don't increment numProbes or
253 // advance idx): this case can happen if the constructor for
254 // ValueT threw for this very cell (the rethrow block above).
255 continue;
256 }
257
258 // NOTE: the way we count numProbes must be same in find(),
259 // insert(), and erase(). Otherwise it may break probing.
260 ++numProbes;
261 if (UNLIKELY(numProbes >= capacity_)) {
262 // probed every cell...fail
263 return SimpleRetT(capacity_, false);
264 }
265
266 idx = ProbeFcn()(idx, numProbes, capacity_);
267 }
268}
269
270/*
271 * erase --
272 *
273 * This will attempt to erase the given key key_in if the key is found. It
274 * returns 1 iff the key was located and marked as erased, and 0 otherwise.
275 *
276 * Memory is not freed or reclaimed by erase, i.e. the cell containing the
277 * erased key will never be reused. If there's an associated value, we won't
278 * touch it either.
279 */
280template <
281 class KeyT,
282 class ValueT,
283 class HashFcn,
284 class EqualFcn,
285 class Allocator,
286 class ProbeFcn,
287 class KeyConvertFcn>
288size_t AtomicHashArray<
289 KeyT,
290 ValueT,
291 HashFcn,
292 EqualFcn,
293 Allocator,
294 ProbeFcn,
295 KeyConvertFcn>::erase(KeyT key_in) {
296 CHECK_NE(key_in, kEmptyKey_);
297 CHECK_NE(key_in, kLockedKey_);
298 CHECK_NE(key_in, kErasedKey_);
299
300 for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;;
301 idx = ProbeFcn()(idx, numProbes, capacity_)) {
302 DCHECK_LT(idx, capacity_);
303 value_type* cell = &cells_[idx];
304 KeyT currentKey = acquireLoadKey(*cell);
305 if (currentKey == kEmptyKey_ || currentKey == kLockedKey_) {
306 // If we hit an empty (or locked) element, this key does not exist. This
307 // is similar to how it's handled in find().
308 return 0;
309 }
310 if (EqualFcn()(currentKey, key_in)) {
311 // Found an existing entry for our key, attempt to mark it erased.
312 // Some other thread may have erased our key, but this is ok.
313 KeyT expect = currentKey;
314 if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
315 numErases_.fetch_add(1, std::memory_order_relaxed);
316
317 // Even if there's a value in the cell, we won't delete (or even
318 // default construct) it because some other thread may be accessing it.
319 // Locking it meanwhile won't work either since another thread may be
320 // holding a pointer to it.
321
322 // We found the key and successfully erased it.
323 return 1;
324 }
325 // If another thread succeeds in erasing our key, we'll stop our search.
326 return 0;
327 }
328
329 // NOTE: the way we count numProbes must be same in find(), insert(),
330 // and erase(). Otherwise it may break probing.
331 ++numProbes;
332 if (UNLIKELY(numProbes >= capacity_)) {
333 // probed every cell...fail
334 return 0;
335 }
336 }
337}
338
339template <
340 class KeyT,
341 class ValueT,
342 class HashFcn,
343 class EqualFcn,
344 class Allocator,
345 class ProbeFcn,
346 class KeyConvertFcn>
347typename AtomicHashArray<
348 KeyT,
349 ValueT,
350 HashFcn,
351 EqualFcn,
352 Allocator,
353 ProbeFcn,
354 KeyConvertFcn>::SmartPtr
355AtomicHashArray<
356 KeyT,
357 ValueT,
358 HashFcn,
359 EqualFcn,
360 Allocator,
361 ProbeFcn,
362 KeyConvertFcn>::create(size_t maxSize, const Config& c) {
363 CHECK_LE(c.maxLoadFactor, 1.0);
364 CHECK_GT(c.maxLoadFactor, 0.0);
365 CHECK_NE(c.emptyKey, c.lockedKey);
366 size_t capacity = size_t(maxSize / c.maxLoadFactor);
367 size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
368
369 auto const mem = Allocator().allocate(sz);
370 try {
371 new (mem) AtomicHashArray(
372 capacity,
373 c.emptyKey,
374 c.lockedKey,
375 c.erasedKey,
376 c.maxLoadFactor,
377 c.entryCountThreadCacheSize);
378 } catch (...) {
379 Allocator().deallocate(mem, sz);
380 throw;
381 }
382
383 SmartPtr map(static_cast<AtomicHashArray*>((void*)mem));
384
385 /*
386 * Mark all cells as empty.
387 *
388 * Note: we're bending the rules a little here accessing the key
389 * element in our cells even though the cell object has not been
390 * constructed, and casting them to atomic objects (see cellKeyPtr).
391 * (Also, in fact we never actually invoke the value_type
392 * constructor.) This is in order to avoid needing to default
393 * construct a bunch of value_type when we first start up: if you
394 * have an expensive default constructor for the value type this can
395 * noticeably speed construction time for an AHA.
396 */
397 FOR_EACH_RANGE (i, 0, map->capacity_) {
398 cellKeyPtr(map->cells_[i])
399 ->store(map->kEmptyKey_, std::memory_order_relaxed);
400 }
401 return map;
402}
403
404template <
405 class KeyT,
406 class ValueT,
407 class HashFcn,
408 class EqualFcn,
409 class Allocator,
410 class ProbeFcn,
411 class KeyConvertFcn>
412void AtomicHashArray<
413 KeyT,
414 ValueT,
415 HashFcn,
416 EqualFcn,
417 Allocator,
418 ProbeFcn,
419 KeyConvertFcn>::destroy(AtomicHashArray* p) {
420 assert(p);
421
422 size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;
423
424 FOR_EACH_RANGE (i, 0, p->capacity_) {
425 if (p->cells_[i].first != p->kEmptyKey_) {
426 p->cells_[i].~value_type();
427 }
428 }
429 p->~AtomicHashArray();
430
431 Allocator().deallocate((char*)p, sz);
432}
433
434// clear -- clears all keys and values in the map and resets all counters
435template <
436 class KeyT,
437 class ValueT,
438 class HashFcn,
439 class EqualFcn,
440 class Allocator,
441 class ProbeFcn,
442 class KeyConvertFcn>
443void AtomicHashArray<
444 KeyT,
445 ValueT,
446 HashFcn,
447 EqualFcn,
448 Allocator,
449 ProbeFcn,
450 KeyConvertFcn>::clear() {
451 FOR_EACH_RANGE (i, 0, capacity_) {
452 if (cells_[i].first != kEmptyKey_) {
453 cells_[i].~value_type();
454 *const_cast<KeyT*>(&cells_[i].first) = kEmptyKey_;
455 }
456 CHECK(cells_[i].first == kEmptyKey_);
457 }
458 numEntries_.set(0);
459 numPendingEntries_.set(0);
460 isFull_.store(0, std::memory_order_relaxed);
461 numErases_.store(0, std::memory_order_relaxed);
462}
463
464// Iterator implementation
465
466template <
467 class KeyT,
468 class ValueT,
469 class HashFcn,
470 class EqualFcn,
471 class Allocator,
472 class ProbeFcn,
473 class KeyConvertFcn>
474template <class ContT, class IterVal>
475struct AtomicHashArray<
476 KeyT,
477 ValueT,
478 HashFcn,
479 EqualFcn,
480 Allocator,
481 ProbeFcn,
482 KeyConvertFcn>::aha_iterator
483 : boost::iterator_facade<
484 aha_iterator<ContT, IterVal>,
485 IterVal,
486 boost::forward_traversal_tag> {
487 explicit aha_iterator() : aha_(nullptr) {}
488
489 // Conversion ctor for interoperability between const_iterator and
490 // iterator. The enable_if<> magic keeps us well-behaved for
491 // is_convertible<> (v. the iterator_facade documentation).
492 template <class OtherContT, class OtherVal>
493 aha_iterator(
494 const aha_iterator<OtherContT, OtherVal>& o,
495 typename std::enable_if<
496 std::is_convertible<OtherVal*, IterVal*>::value>::type* = nullptr)
497 : aha_(o.aha_), offset_(o.offset_) {}
498
499 explicit aha_iterator(ContT* array, size_t offset)
500 : aha_(array), offset_(offset) {}
501
502 // Returns unique index that can be used with findAt().
503 // WARNING: The following function will fail silently for hashtable
504 // with capacity > 2^32
505 uint32_t getIndex() const {
506 return offset_;
507 }
508
509 void advancePastEmpty() {
510 while (offset_ < aha_->capacity_ && !isValid()) {
511 ++offset_;
512 }
513 }
514
515 private:
516 friend class AtomicHashArray;
517 friend class boost::iterator_core_access;
518
519 void increment() {
520 ++offset_;
521 advancePastEmpty();
522 }
523
524 bool equal(const aha_iterator& o) const {
525 return aha_ == o.aha_ && offset_ == o.offset_;
526 }
527
528 IterVal& dereference() const {
529 return aha_->cells_[offset_];
530 }
531
532 bool isValid() const {
533 KeyT key = acquireLoadKey(aha_->cells_[offset_]);
534 return key != aha_->kEmptyKey_ && key != aha_->kLockedKey_ &&
535 key != aha_->kErasedKey_;
536 }
537
538 private:
539 ContT* aha_;
540 size_t offset_;
541}; // aha_iterator
542
543} // namespace folly
544