folly/AtomicHashArray-inl.h

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