folly/AtomicHashArray-inl.h

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