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