X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FAtomicHashArray-inl.h;h=d2cb08f460718ed651079f4c3bc47c52253d2b53;hp=236c7c223142a2846427bee85bcf08f944d5607b;hb=0fa941367b87fe3e127a5de3ad85535bef321397;hpb=7969353a581b2e0e8e708e97cb55acd2fa45da45 diff --git a/folly/AtomicHashArray-inl.h b/folly/AtomicHashArray-inl.h index 236c7c22..d2cb08f4 100644 --- a/folly/AtomicHashArray-inl.h +++ b/folly/AtomicHashArray-inl.h @@ -1,5 +1,5 @@ /* - * Copyright 2013 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -18,17 +18,22 @@ #error "This should only be included by AtomicHashArray.h" #endif -#include "folly/Bits.h" -#include "folly/detail/AtomicHashUtils.h" +#include + +#include +#include namespace folly { // AtomicHashArray private constructor -- -template -AtomicHashArray:: +template +AtomicHashArray:: AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey, - KeyT erasedKey, double maxLoadFactor, size_t cacheSize) - : capacity_(capacity), maxEntries_(size_t(maxLoadFactor * capacity_ + 0.5)), + KeyT erasedKey, double _maxLoadFactor, uint32_t cacheSize) + : capacity_(capacity), + maxEntries_(size_t(_maxLoadFactor * capacity_ + 0.5)), kEmptyKey_(emptyKey), kLockedKey_(lockedKey), kErasedKey_(erasedKey), kAnchorMask_(nextPowTwo(capacity_) - 1), numEntries_(0, cacheSize), numPendingEntries_(0, cacheSize), isFull_(0), numErases_(0) { @@ -41,24 +46,30 @@ AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey, * of key and returns true, or if key does not exist returns false and * ret.index is set to capacity_. */ -template -typename AtomicHashArray::SimpleRetT -AtomicHashArray:: -findInternal(const KeyT key_in) { - DCHECK_NE(key_in, kEmptyKey_); - DCHECK_NE(key_in, kLockedKey_); - DCHECK_NE(key_in, kErasedKey_); - for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0; +template +template +typename AtomicHashArray::SimpleRetT +AtomicHashArray:: +findInternal(const LookupKeyT key_in) { + checkLegalKeyIfKey(key_in); + + for (size_t idx = keyToAnchorIdx(key_in), + numProbes = 0; ; - idx = probeNext(idx, numProbes)) { + idx = ProbeFcn()(idx, numProbes, capacity_)) { const KeyT key = acquireLoadKey(cells_[idx]); - if (LIKELY(EqualFcn()(key, key_in))) { + if (LIKELY(LookupEqualFcn()(key, key_in))) { return SimpleRetT(idx, true); } if (UNLIKELY(key == kEmptyKey_)) { // if we hit an empty element, this key does not exist return SimpleRetT(capacity_, false); } + // NOTE: the way we count numProbes must be same in find(), insert(), + // and erase(). Otherwise it may break probing. ++numProbes; if (UNLIKELY(numProbes >= capacity_)) { // probed every cell...fail @@ -77,18 +88,23 @@ findInternal(const KeyT key_in) { * this will be the previously inserted value, and if the map is full it is * default. */ -template -template -typename AtomicHashArray::SimpleRetT -AtomicHashArray:: -insertInternal(KeyT key_in, T&& value) { +template +template +typename AtomicHashArray::SimpleRetT +AtomicHashArray:: +insertInternal(LookupKeyT key_in, ArgTs&&... vCtorArgs) { const short NO_NEW_INSERTS = 1; const short NO_PENDING_INSERTS = 2; - CHECK_NE(key_in, kEmptyKey_); - CHECK_NE(key_in, kLockedKey_); - CHECK_NE(key_in, kErasedKey_); + checkLegalKeyIfKey(key_in); - size_t idx = keyToAnchorIdx(key_in); + size_t idx = keyToAnchorIdx(key_in); size_t numProbes = 0; for (;;) { DCHECK_LT(idx, capacity_); @@ -108,10 +124,11 @@ insertInternal(KeyT key_in, T&& value) { // another thread now does ++numPendingEntries_, we expect it // to pass the isFull_.load() test above. (It shouldn't insert // a new entry.) - FOLLY_SPIN_WAIT( - isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS - && numPendingEntries_.readFull() != 0 - ); + detail::atomic_hash_spin_wait([&] { + return + (isFull_.load(std::memory_order_acquire) != NO_PENDING_INSERTS) && + (numPendingEntries_.readFull() != 0); + }); isFull_.store(NO_PENDING_INSERTS, std::memory_order_release); if (relaxedLoadKey(*cell) == kEmptyKey_) { @@ -123,16 +140,24 @@ insertInternal(KeyT key_in, T&& value) { // If we fail, fall through to comparison below; maybe the insert that // just beat us was for this very key.... if (tryLockCell(cell)) { + KeyT key_new; // Write the value - done before unlocking try { + key_new = LookupKeyToKeyFcn()(key_in); + typedef typename std::remove_const::type + LookupKeyTNoConst; + constexpr bool kAlreadyChecked = + std::is_same::value; + if (!kAlreadyChecked) { + checkLegalKeyIfKey(key_new); + } DCHECK(relaxedLoadKey(*cell) == kLockedKey_); - /* - * This happens using the copy constructor because we won't have - * constructed a lhs to use an assignment operator on when - * values are being set. - */ - new (&cell->second) ValueT(std::forward(value)); - unlockCell(cell, key_in); // Sets the new key + // A const mapped_type is only constant once constructed, so cast + // away any const for the placement new here. + using mapped = typename std::remove_const::type; + new (const_cast(&cell->second)) + ValueT(std::forward(vCtorArgs)...); + unlockCell(cell, key_new); // Sets the new key } catch (...) { // Transition back to empty key---requires handling // locked->empty below. @@ -140,9 +165,11 @@ insertInternal(KeyT key_in, T&& value) { --numPendingEntries_; throw; } + // An erase() can race here and delete right after our insertion // Direct comparison rather than EqualFcn ok here // (we just inserted it) - DCHECK(relaxedLoadKey(*cell) == key_in); + DCHECK(relaxedLoadKey(*cell) == key_new || + relaxedLoadKey(*cell) == kErasedKey_); --numPendingEntries_; ++numEntries_; // This is a thread cached atomic increment :) if (numEntries_.readFast() >= maxEntries_) { @@ -155,13 +182,13 @@ insertInternal(KeyT key_in, T&& value) { } DCHECK(relaxedLoadKey(*cell) != kEmptyKey_); if (kLockedKey_ == acquireLoadKey(*cell)) { - FOLLY_SPIN_WAIT( - kLockedKey_ == acquireLoadKey(*cell) - ); + detail::atomic_hash_spin_wait([&] { + return kLockedKey_ == acquireLoadKey(*cell); + }); } const KeyT thisKey = acquireLoadKey(*cell); - if (EqualFcn()(thisKey, key_in)) { + if (LookupEqualFcn()(thisKey, key_in)) { // Found an existing entry for our key, but we don't overwrite the // previous value. return SimpleRetT(idx, false); @@ -172,17 +199,19 @@ insertInternal(KeyT key_in, T&& value) { continue; } + + // NOTE: the way we count numProbes must be same in find(), + // insert(), and erase(). Otherwise it may break probing. ++numProbes; if (UNLIKELY(numProbes >= capacity_)) { // probed every cell...fail return SimpleRetT(capacity_, false); } - idx = probeNext(idx, numProbes); + idx = ProbeFcn()(idx, numProbes, capacity_); } } - /* * erase -- * @@ -193,15 +222,18 @@ insertInternal(KeyT key_in, T&& value) { * erased key will never be reused. If there's an associated value, we won't * touch it either. */ -template -size_t AtomicHashArray:: +template +size_t AtomicHashArray:: erase(KeyT key_in) { CHECK_NE(key_in, kEmptyKey_); CHECK_NE(key_in, kLockedKey_); CHECK_NE(key_in, kErasedKey_); + for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0; ; - idx = probeNext(idx, numProbes)) { + idx = ProbeFcn()(idx, numProbes, capacity_)) { DCHECK_LT(idx, capacity_); value_type* cell = &cells_[idx]; KeyT currentKey = acquireLoadKey(*cell); @@ -228,6 +260,9 @@ erase(KeyT key_in) { // If another thread succeeds in erasing our key, we'll stop our search. return 0; } + + // NOTE: the way we count numProbes must be same in find(), insert(), + // and erase(). Otherwise it may break probing. ++numProbes; if (UNLIKELY(numProbes >= capacity_)) { // probed every cell...fail @@ -236,13 +271,12 @@ erase(KeyT key_in) { } } -template -const typename AtomicHashArray::Config -AtomicHashArray::defaultConfig; - -template -typename AtomicHashArray::SmartPtr -AtomicHashArray:: +template +typename AtomicHashArray::SmartPtr +AtomicHashArray:: create(size_t maxSize, const Config& c) { CHECK_LE(c.maxLoadFactor, 1.0); CHECK_GT(c.maxLoadFactor, 0.0); @@ -250,10 +284,16 @@ create(size_t maxSize, const Config& c) { size_t capacity = size_t(maxSize / c.maxLoadFactor); size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity; - std::unique_ptr mem(malloc(sz), free); - new(mem.get()) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey, - c.maxLoadFactor, c.entryCountThreadCacheSize); - SmartPtr map(static_cast(mem.release())); + auto const mem = Allocator().allocate(sz); + try { + new (mem) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey, + c.maxLoadFactor, c.entryCountThreadCacheSize); + } catch (...) { + Allocator().deallocate(mem, sz); + throw; + } + + SmartPtr map(static_cast((void *)mem)); /* * Mark all cells as empty. @@ -274,22 +314,30 @@ create(size_t maxSize, const Config& c) { return map; } -template -void AtomicHashArray:: +template +void AtomicHashArray:: destroy(AtomicHashArray* p) { assert(p); + + size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_; + FOR_EACH_RANGE(i, 0, p->capacity_) { if (p->cells_[i].first != p->kEmptyKey_) { p->cells_[i].~value_type(); } } p->~AtomicHashArray(); - free(p); + + Allocator().deallocate((char *)p, sz); } // clear -- clears all keys and values in the map and resets all counters -template -void AtomicHashArray:: +template +void AtomicHashArray:: clear() { FOR_EACH_RANGE(i, 0, capacity_) { if (cells_[i].first != kEmptyKey_) { @@ -307,9 +355,12 @@ clear() { // Iterator implementation -template +template template -struct AtomicHashArray::aha_iterator +struct AtomicHashArray:: + aha_iterator : boost::iterator_facade, IterVal, boost::forward_traversal_tag> @@ -330,15 +381,19 @@ struct AtomicHashArray::aha_iterator explicit aha_iterator(ContT* array, size_t offset) : aha_(array) , offset_(offset) - { - advancePastEmpty(); - } + {} // Returns unique index that can be used with findAt(). // WARNING: The following function will fail silently for hashtable // with capacity > 2^32 uint32_t getIndex() const { return offset_; } + void advancePastEmpty() { + while (offset_ < aha_->capacity_ && !isValid()) { + ++offset_; + } + } + private: friend class AtomicHashArray; friend class boost::iterator_core_access; @@ -356,12 +411,6 @@ struct AtomicHashArray::aha_iterator return aha_->cells_[offset_]; } - void advancePastEmpty() { - while (offset_ < aha_->capacity_ && !isValid()) { - ++offset_; - } - } - bool isValid() const { KeyT key = acquireLoadKey(aha_->cells_[offset_]); return key != aha_->kEmptyKey_ && @@ -375,5 +424,3 @@ struct AtomicHashArray::aha_iterator }; // aha_iterator } // namespace folly - -#undef FOLLY_SPIN_WAIT