folly/AtomicHashArray-inl.h

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