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 | |
26 | namespace folly { |
27 | |
28 | // AtomicHashArray private constructor -- |
29 | template < |
30 | class KeyT, |
31 | class ValueT, |
32 | class HashFcn, |
33 | class EqualFcn, |
34 | class Allocator, |
35 | class ProbeFcn, |
36 | class KeyConvertFcn> |
37 | AtomicHashArray< |
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 | */ |
70 | template < |
71 | class KeyT, |
72 | class ValueT, |
73 | class HashFcn, |
74 | class EqualFcn, |
75 | class Allocator, |
76 | class ProbeFcn, |
77 | class KeyConvertFcn> |
78 | template <class LookupKeyT, class LookupHashFcn, class LookupEqualFcn> |
79 | typename AtomicHashArray< |
80 | KeyT, |
81 | ValueT, |
82 | HashFcn, |
83 | EqualFcn, |
84 | Allocator, |
85 | ProbeFcn, |
86 | KeyConvertFcn>::SimpleRetT |
87 | AtomicHashArray< |
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 | */ |
129 | template < |
130 | class KeyT, |
131 | class ValueT, |
132 | class HashFcn, |
133 | class EqualFcn, |
134 | class Allocator, |
135 | class ProbeFcn, |
136 | class KeyConvertFcn> |
137 | template < |
138 | typename LookupKeyT, |
139 | typename LookupHashFcn, |
140 | typename LookupEqualFcn, |
141 | typename LookupKeyToKeyFcn, |
142 | typename... ArgTs> |
143 | typename AtomicHashArray< |
144 | KeyT, |
145 | ValueT, |
146 | HashFcn, |
147 | EqualFcn, |
148 | Allocator, |
149 | ProbeFcn, |
150 | KeyConvertFcn>::SimpleRetT |
151 | AtomicHashArray< |
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 | */ |
280 | template < |
281 | class KeyT, |
282 | class ValueT, |
283 | class HashFcn, |
284 | class EqualFcn, |
285 | class Allocator, |
286 | class ProbeFcn, |
287 | class KeyConvertFcn> |
288 | size_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 | |
339 | template < |
340 | class KeyT, |
341 | class ValueT, |
342 | class HashFcn, |
343 | class EqualFcn, |
344 | class Allocator, |
345 | class ProbeFcn, |
346 | class KeyConvertFcn> |
347 | typename AtomicHashArray< |
348 | KeyT, |
349 | ValueT, |
350 | HashFcn, |
351 | EqualFcn, |
352 | Allocator, |
353 | ProbeFcn, |
354 | KeyConvertFcn>::SmartPtr |
355 | AtomicHashArray< |
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 | |
404 | template < |
405 | class KeyT, |
406 | class ValueT, |
407 | class HashFcn, |
408 | class EqualFcn, |
409 | class Allocator, |
410 | class ProbeFcn, |
411 | class KeyConvertFcn> |
412 | void 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 |
435 | template < |
436 | class KeyT, |
437 | class ValueT, |
438 | class HashFcn, |
439 | class EqualFcn, |
440 | class Allocator, |
441 | class ProbeFcn, |
442 | class KeyConvertFcn> |
443 | void 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 | |
466 | template < |
467 | class KeyT, |
468 | class ValueT, |
469 | class HashFcn, |
470 | class EqualFcn, |
471 | class Allocator, |
472 | class ProbeFcn, |
473 | class KeyConvertFcn> |
474 | template <class ContT, class IterVal> |
475 | struct 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 | |