X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=folly%2FAtomicHashArray-inl.h;h=5b81837953e6ecebca5feddcb187211eb3ec6b9b;hb=02fe20e3434fd6400ecf2ad92c7e1231b8f17108;hp=bfc1637dad377bbb6f99e08aa5062e9d1c7e2ef7;hpb=b4746252b468b726482d491994d9be8905de13a4;p=folly.git diff --git a/folly/AtomicHashArray-inl.h b/folly/AtomicHashArray-inl.h index bfc1637d..5b818379 100644 --- a/folly/AtomicHashArray-inl.h +++ b/folly/AtomicHashArray-inl.h @@ -1,5 +1,5 @@ /* - * Copyright 2014 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,18 +18,28 @@ #error "This should only be included by AtomicHashArray.h" #endif +#include + #include #include namespace folly { // AtomicHashArray private constructor -- -template -AtomicHashArray:: +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +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) { @@ -42,26 +52,36 @@ 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 < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +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 @@ -80,20 +100,30 @@ 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 < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +template < + typename LookupKeyT, + typename LookupHashFcn, + typename LookupEqualFcn, + typename LookupKeyToKeyFcn, + typename... ArgTs> +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_); @@ -113,10 +143,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_) { @@ -128,16 +159,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. @@ -145,9 +184,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_) { @@ -160,13 +201,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); @@ -177,17 +218,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 -- * @@ -198,16 +241,24 @@ 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 < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +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); @@ -234,6 +285,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 @@ -242,17 +296,18 @@ erase(KeyT key_in) { } } -template -const typename AtomicHashArray::Config -AtomicHashArray::defaultConfig; - -template -typename AtomicHashArray::SmartPtr -AtomicHashArray:: +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +typename AtomicHashArray::SmartPtr +AtomicHashArray:: create(size_t maxSize, const Config& c) { CHECK_LE(c.maxLoadFactor, 1.0); CHECK_GT(c.maxLoadFactor, 0.0); @@ -290,9 +345,16 @@ create(size_t maxSize, const Config& c) { return map; } -template -void AtomicHashArray:: +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +void AtomicHashArray:: destroy(AtomicHashArray* p) { assert(p); @@ -309,9 +371,16 @@ destroy(AtomicHashArray* p) { } // clear -- clears all keys and values in the map and resets all counters -template -void AtomicHashArray:: +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> +void AtomicHashArray:: clear() { FOR_EACH_RANGE(i, 0, capacity_) { if (cells_[i].first != kEmptyKey_) { @@ -329,10 +398,18 @@ clear() { // Iterator implementation -template +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> template -struct AtomicHashArray::aha_iterator +struct AtomicHashArray:: + aha_iterator : boost::iterator_facade, IterVal, boost::forward_traversal_tag> @@ -342,7 +419,7 @@ struct AtomicHashArray::aha_iterator // Conversion ctor for interoperability between const_iterator and // iterator. The enable_if<> magic keeps us well-behaved for // is_convertible<> (v. the iterator_facade documentation). - template + template aha_iterator(const aha_iterator& o, typename std::enable_if< std::is_convertible::value >::type* = 0) @@ -396,5 +473,3 @@ struct AtomicHashArray::aha_iterator }; // aha_iterator } // namespace folly - -#undef FOLLY_SPIN_WAIT