folly/AtomicHashMap-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_ATOMICHASHMAP_H_
  18 #error "This should only be included by AtomicHashMap.h"
  19 #endif
  20
  21 #include <folly/detail/AtomicHashUtils.h>
  22
  23 namespace folly {
  24
  25 // AtomicHashMap constructor -- Atomic wrapper that allows growth
  26 // This class has a lot of overhead (184 Bytes) so only use for big maps
  27 template <typename KeyT, typename ValueT,
  28           typename HashFcn, typename EqualFcn, typename Allocator>
  29 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
  30 AtomicHashMap(size_t finalSizeEst, const Config& config)
  31   : kGrowthFrac_(config.growthFactor < 0 ?
  32                  1.0 - config.maxLoadFactor : config.growthFactor) {
  33   CHECK(config.maxLoadFactor > 0.0 && config.maxLoadFactor < 1.0);
  34   subMaps_[0].store(SubMap::create(finalSizeEst, config).release(),
  35     std::memory_order_relaxed);
  36   auto subMapCount = kNumSubMaps_;
  37   FOR_EACH_RANGE(i, 1, subMapCount) {
  38     subMaps_[i].store(nullptr, std::memory_order_relaxed);
  39   }
  40   numMapsAllocated_.store(1, std::memory_order_relaxed);
  41 }
  42
  43 // emplace --
  44 template <typename KeyT, typename ValueT,
  45           typename HashFcn, typename EqualFcn, typename Allocator>
  46 template <typename... ArgTs>
  47 std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
  48                                  EqualFcn, Allocator>::iterator, bool>
  49 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
  50 emplace(key_type k, ArgTs&&... vCtorArgs) {
  51   SimpleRetT ret = insertInternal(k, std::forward<ArgTs>(vCtorArgs)...);
  52   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
  53   return std::make_pair(iterator(this, ret.i, subMap->makeIter(ret.j)),
  54                         ret.success);
  55 }
  56
  57 // insertInternal -- Allocates new sub maps as existing ones fill up.
  58 template <typename KeyT, typename ValueT,
  59           typename HashFcn, typename EqualFcn, typename Allocator>
  60 template <typename... ArgTs>
  61 typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
  62 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
  63 insertInternal(key_type key, ArgTs&&... vCtorArgs) {
  64  beginInsertInternal:
  65   auto nextMapIdx = // this maintains our state
  66     numMapsAllocated_.load(std::memory_order_acquire);
  67   typename SubMap::SimpleRetT ret;
  68   FOR_EACH_RANGE(i, 0, nextMapIdx) {
  69     // insert in each map successively.  If one succeeds, we're done!
  70     SubMap* subMap = subMaps_[i].load(std::memory_order_relaxed);
  71     ret = subMap->insertInternal(key, std::forward<ArgTs>(vCtorArgs)...);
  72     if (ret.idx == subMap->capacity_) {
  73       continue;  //map is full, so try the next one
  74     }
  75     // Either collision or success - insert in either case
  76     return SimpleRetT(i, ret.idx, ret.success);
  77   }
  78
  79   // If we made it this far, all maps are full and we need to try to allocate
  80   // the next one.
  81
  82   SubMap* primarySubMap = subMaps_[0].load(std::memory_order_relaxed);
  83   if (nextMapIdx >= kNumSubMaps_ ||
  84       primarySubMap->capacity_ * kGrowthFrac_ < 1.0) {
  85     // Can't allocate any more sub maps.
  86     throw AtomicHashMapFullError();
  87   }
  88
  89   if (tryLockMap(nextMapIdx)) {
  90     // Alloc a new map and shove it in.  We can change whatever
  91     // we want because other threads are waiting on us...
  92     size_t numCellsAllocated = (size_t)
  93       (primarySubMap->capacity_ *
  94        std::pow(1.0 + kGrowthFrac_, nextMapIdx - 1));
  95     size_t newSize = (int) (numCellsAllocated * kGrowthFrac_);
  96     DCHECK(subMaps_[nextMapIdx].load(std::memory_order_relaxed) ==
  97       (SubMap*)kLockedPtr_);
  98     // create a new map using the settings stored in the first map
  99
 100     Config config;
 101     config.emptyKey = primarySubMap->kEmptyKey_;
 102     config.lockedKey = primarySubMap->kLockedKey_;
 103     config.erasedKey = primarySubMap->kErasedKey_;
 104     config.maxLoadFactor = primarySubMap->maxLoadFactor();
 105     config.entryCountThreadCacheSize =
 106       primarySubMap->getEntryCountThreadCacheSize();
 107     subMaps_[nextMapIdx].store(SubMap::create(newSize, config).release(),
 108       std::memory_order_relaxed);
 109
 110     // Publish the map to other threads.
 111     numMapsAllocated_.fetch_add(1, std::memory_order_release);
 112     DCHECK_EQ(nextMapIdx + 1,
 113       numMapsAllocated_.load(std::memory_order_relaxed));
 114   } else {
 115     // If we lost the race, we'll have to wait for the next map to get
 116     // allocated before doing any insertion here.
 117     detail::atomic_hash_spin_wait([&] {
 118       return nextMapIdx >= numMapsAllocated_.load(std::memory_order_acquire);
 119     });
 120   }
 121
 122   // Relaxed is ok here because either we just created this map, or we
 123   // just did a spin wait with an acquire load on numMapsAllocated_.
 124   SubMap* loadedMap = subMaps_[nextMapIdx].load(std::memory_order_relaxed);
 125   DCHECK(loadedMap && loadedMap != (SubMap*)kLockedPtr_);
 126   ret = loadedMap->insertInternal(key, std::forward<ArgTs>(vCtorArgs)...);
 127   if (ret.idx != loadedMap->capacity_) {
 128     return SimpleRetT(nextMapIdx, ret.idx, ret.success);
 129   }
 130   // We took way too long and the new map is already full...try again from
 131   // the top (this should pretty much never happen).
 132   goto beginInsertInternal;
 133 }
 134
 135 // find --
 136 template <typename KeyT, typename ValueT,
 137           typename HashFcn, typename EqualFcn, typename Allocator>
 138 typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::iterator
 139 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 140 find(KeyT k) {
 141   SimpleRetT ret = findInternal(k);
 142   if (!ret.success) {
 143     return end();
 144   }
 145   SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
 146   return iterator(this, ret.i, subMap->makeIter(ret.j));
 147 }
 148
 149 template <typename KeyT, typename ValueT,
 150           typename HashFcn, typename EqualFcn, typename Allocator>
 151 typename AtomicHashMap<KeyT, ValueT,
 152          HashFcn, EqualFcn, Allocator>::const_iterator
 153 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 154 find(KeyT k) const {
 155   return const_cast<AtomicHashMap*>(this)->find(k);
 156 }
 157
 158 // findInternal --
 159 template <typename KeyT, typename ValueT,
 160           typename HashFcn, typename EqualFcn, typename Allocator>
 161 typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
 162 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 163 findInternal(const KeyT k) const {
 164   SubMap* const primaryMap = subMaps_[0].load(std::memory_order_relaxed);
 165   typename SubMap::SimpleRetT ret = primaryMap->findInternal(k);
 166   if (LIKELY(ret.idx != primaryMap->capacity_)) {
 167     return SimpleRetT(0, ret.idx, ret.success);
 168   }
 169   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
 170   FOR_EACH_RANGE(i, 1, numMaps) {
 171     // Check each map successively.  If one succeeds, we're done!
 172     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
 173     ret = thisMap->findInternal(k);
 174     if (LIKELY(ret.idx != thisMap->capacity_)) {
 175       return SimpleRetT(i, ret.idx, ret.success);
 176     }
 177   }
 178   // Didn't find our key...
 179   return SimpleRetT(numMaps, 0, false);
 180 }
 181
 182 // findAtInternal -- see encodeIndex() for details.
 183 template <typename KeyT, typename ValueT,
 184           typename HashFcn, typename EqualFcn, typename Allocator>
 185 typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
 186 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 187 findAtInternal(uint32_t idx) const {
 188   uint32_t subMapIdx, subMapOffset;
 189   if (idx & kSecondaryMapBit_) {
 190     // idx falls in a secondary map
 191     idx &= ~kSecondaryMapBit_;  // unset secondary bit
 192     subMapIdx = idx >> kSubMapIndexShift_;
 193     DCHECK_LT(subMapIdx, numMapsAllocated_.load(std::memory_order_relaxed));
 194     subMapOffset = idx & kSubMapIndexMask_;
 195   } else {
 196     // idx falls in primary map
 197     subMapIdx = 0;
 198     subMapOffset = idx;
 199   }
 200   return SimpleRetT(subMapIdx, subMapOffset, true);
 201 }
 202
 203 // erase --
 204 template <typename KeyT, typename ValueT,
 205           typename HashFcn, typename EqualFcn, typename Allocator>
 206 typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::size_type
 207 AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 208 erase(const KeyT k) {
 209   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
 210   FOR_EACH_RANGE(i, 0, numMaps) {
 211     // Check each map successively.  If one succeeds, we're done!
 212     if (subMaps_[i].load(std::memory_order_relaxed)->erase(k)) {
 213       return 1;
 214     }
 215   }
 216   // Didn't find our key...
 217   return 0;
 218 }
 219
 220 // capacity -- summation of capacities of all submaps
 221 template <typename KeyT, typename ValueT,
 222           typename HashFcn, typename EqualFcn, typename Allocator>
 223 size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 224 capacity() const {
 225   size_t totalCap(0);
 226   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
 227   FOR_EACH_RANGE(i, 0, numMaps) {
 228     totalCap += subMaps_[i].load(std::memory_order_relaxed)->capacity_;
 229   }
 230   return totalCap;
 231 }
 232
 233 // spaceRemaining --
 234 // number of new insertions until current submaps are all at max load
 235 template <typename KeyT, typename ValueT,
 236           typename HashFcn, typename EqualFcn, typename Allocator>
 237 size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 238 spaceRemaining() const {
 239   size_t spaceRem(0);
 240   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
 241   FOR_EACH_RANGE(i, 0, numMaps) {
 242     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
 243     spaceRem += std::max(
 244       0,
 245       thisMap->maxEntries_ - &thisMap->numEntries_.readFull()
 246     );
 247   }
 248   return spaceRem;
 249 }
 250
 251 // clear -- Wipes all keys and values from primary map and destroys
 252 // all secondary maps.  Not thread safe.
 253 template <typename KeyT, typename ValueT,
 254           typename HashFcn, typename EqualFcn, typename Allocator>
 255 void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 256 clear() {
 257   subMaps_[0].load(std::memory_order_relaxed)->clear();
 258   int const numMaps = numMapsAllocated_
 259     .load(std::memory_order_relaxed);
 260   FOR_EACH_RANGE(i, 1, numMaps) {
 261     SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed);
 262     DCHECK(thisMap);
 263     SubMap::destroy(thisMap);
 264     subMaps_[i].store(nullptr, std::memory_order_relaxed);
 265   }
 266   numMapsAllocated_.store(1, std::memory_order_relaxed);
 267 }
 268
 269 // size --
 270 template <typename KeyT, typename ValueT,
 271           typename HashFcn, typename EqualFcn, typename Allocator>
 272 size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 273 size() const {
 274   size_t totalSize(0);
 275   int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
 276   FOR_EACH_RANGE(i, 0, numMaps) {
 277     totalSize += subMaps_[i].load(std::memory_order_relaxed)->size();
 278   }
 279   return totalSize;
 280 }
 281
 282 // encodeIndex -- Encode the submap index and offset into return.
 283 // index_ret must be pre-populated with the submap offset.
 284 //
 285 // We leave index_ret untouched when referring to the primary map
 286 // so it can be as large as possible (31 data bits).  Max size of
 287 // secondary maps is limited by what can fit in the low 27 bits.
 288 //
 289 // Returns the following bit-encoded data in index_ret:
 290 //   if subMap == 0 (primary map) =>
 291 //     bit(s)          value
 292 //         31              0
 293 //       0-30  submap offset (index_ret input)
 294 //
 295 //   if subMap > 0 (secondary maps) =>
 296 //     bit(s)          value
 297 //         31              1
 298 //      27-30   which subMap
 299 //       0-26  subMap offset (index_ret input)
 300 template <typename KeyT, typename ValueT,
 301           typename HashFcn, typename EqualFcn, typename Allocator>
 302 inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 303 encodeIndex(uint32_t subMap, uint32_t offset) {
 304   DCHECK_EQ(offset & kSecondaryMapBit_, 0);  // offset can't be too big
 305   if (subMap == 0) return offset;
 306   // Make sure subMap isn't too big
 307   DCHECK_EQ(subMap >> kNumSubMapBits_, 0);
 308   // Make sure subMap bits of offset are clear
 309   DCHECK_EQ(offset & (~kSubMapIndexMask_ | kSecondaryMapBit_), 0);
 310
 311   // Set high-order bits to encode which submap this index belongs to
 312   return offset | (subMap << kSubMapIndexShift_) | kSecondaryMapBit_;
 313 }
 314
 315
 316 // Iterator implementation
 317
 318 template <typename KeyT, typename ValueT,
 319           typename HashFcn, typename EqualFcn, typename Allocator>
 320 template<class ContT, class IterVal, class SubIt>
 321 struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::ahm_iterator
 322     : boost::iterator_facade<ahm_iterator<ContT,IterVal,SubIt>,
 323                              IterVal,
 324                              boost::forward_traversal_tag>
 325 {
 326   explicit ahm_iterator() : ahm_(0) {}
 327
 328   // Conversion ctor for interoperability between const_iterator and
 329   // iterator.  The enable_if<> magic keeps us well-behaved for
 330   // is_convertible<> (v. the iterator_facade documentation).
 331   template<class OtherContT, class OtherVal, class OtherSubIt>
 332   ahm_iterator(const ahm_iterator<OtherContT,OtherVal,OtherSubIt>& o,
 333                typename std::enable_if<
 334                std::is_convertible<OtherSubIt,SubIt>::value >::type* = 0)
 335       : ahm_(o.ahm_)
 336       , subMap_(o.subMap_)
 337       , subIt_(o.subIt_)
 338   {}
 339
 340   /*
 341    * Returns the unique index that can be used for access directly
 342    * into the data storage.
 343    */
 344   uint32_t getIndex() const {
 345     CHECK(!isEnd());
 346     return ahm_->encodeIndex(subMap_, subIt_.getIndex());
 347   }
 348
 349  private:
 350   friend class AtomicHashMap;
 351   explicit ahm_iterator(ContT* ahm,
 352                         uint32_t subMap,
 353                         const SubIt& subIt)
 354       : ahm_(ahm)
 355       , subMap_(subMap)
 356       , subIt_(subIt)
 357   {}
 358
 359   friend class boost::iterator_core_access;
 360
 361   void increment() {
 362     CHECK(!isEnd());
 363     ++subIt_;
 364     checkAdvanceToNextSubmap();
 365   }
 366
 367   bool equal(const ahm_iterator& other) const {
 368     if (ahm_ != other.ahm_) {
 369       return false;
 370     }
 371
 372     if (isEnd() || other.isEnd()) {
 373       return isEnd() == other.isEnd();
 374     }
 375
 376     return subMap_ == other.subMap_ &&
 377       subIt_ == other.subIt_;
 378   }
 379
 380   IterVal& dereference() const {
 381     return *subIt_;
 382   }
 383
 384   bool isEnd() const { return ahm_ == nullptr; }
 385
 386   void checkAdvanceToNextSubmap() {
 387     if (isEnd()) {
 388       return;
 389     }
 390
 391     SubMap* thisMap = ahm_->subMaps_[subMap_].
 392       load(std::memory_order_relaxed);
 393     while (subIt_ == thisMap->end()) {
 394       // This sub iterator is done, advance to next one
 395       if (subMap_ + 1 <
 396           ahm_->numMapsAllocated_.load(std::memory_order_acquire)) {
 397         ++subMap_;
 398         thisMap = ahm_->subMaps_[subMap_].load(std::memory_order_relaxed);
 399         subIt_ = thisMap->begin();
 400       } else {
 401         ahm_ = nullptr;
 402         return;
 403       }
 404     }
 405   }
 406
 407  private:
 408   ContT* ahm_;
 409   uint32_t subMap_;
 410   SubIt subIt_;
 411 }; // ahm_iterator
 412
 413 } // namespace folly