folly/AtomicUnorderedMap.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 #ifndef FOLLY_ATOMICUNORDEREDMAP_H
  17 #define FOLLY_ATOMICUNORDEREDMAP_H
  18
  19 #include <atomic>
  20 #include <functional>
  21 #include <stdexcept>
  22 #include <system_error>
  23 #include <type_traits>
  24 #include <stdint.h>
  25 #include <unistd.h>
  26 #include <sys/mman.h>
  27 #include <folly/Likely.h>
  28 #include <folly/Bits.h>
  29 #include <folly/Conv.h>
  30 #include <folly/Random.h>
  31 #include <folly/detail/AtomicUnorderedMapUtils.h>
  32 #include <boost/type_traits/has_trivial_destructor.hpp>
  33 #include <limits>
  34
  35 namespace folly {
  36
  37 /// You're probably reading this because you are looking for an
  38 /// AtomicUnorderedMap<K,V> that is fully general, highly concurrent (for
  39 /// reads, writes, and iteration), and makes no performance compromises.
  40 /// We haven't figured that one out yet.  What you will find here is a
  41 /// hash table implementation that sacrifices generality so that it can
  42 /// give you all of the other things.
  43 ///
  44 /// LIMITATIONS:
  45 ///
  46 /// * Insert only (*) - the only write operation supported directly by
  47 ///   AtomicUnorderedInsertMap is findOrConstruct.  There is a (*) because
  48 ///   values aren't moved, so you can roll your own concurrency control for
  49 ///   in-place updates of values (see MutableData and MutableAtom below),
  50 ///   but the hash table itself doesn't help you.
  51 ///
  52 /// * No resizing - you must specify the capacity up front, and once
  53 ///   the hash map gets full you won't be able to insert.  Insert
  54 ///   performance will degrade once the load factor is high.  Insert is
  55 ///   O(1/(1-actual_load_factor)).  Note that this is a pretty strong
  56 ///   limitation, because you can't remove existing keys.
  57 ///
  58 /// * 2^30 maximum capacity - you'll need to use something else if you
  59 ///   have more than a billion entries.  If this limit bothers you let it
  60 ///   wouldn't be too hard to parameterize the internal indexes between
  61 ///   uint32_t and uint64_t.
  62 ///
  63 /// WHAT YOU GET IN EXCHANGE:
  64 ///
  65 /// * Arbitrary key and value types - any K and V that can be used in a
  66 ///   std::unordered_map can be used here.  In fact, the key and value
  67 ///   types don't even have to be copyable or moveable!
  68 ///
  69 /// * Keys and values in the map won't be moved - it is safe to keep
  70 ///   pointers or references to the keys and values in the map, because
  71 ///   they are never moved or destroyed (until the map itself is destroyed).
  72 ///
  73 /// * Iterators are never invalidated - writes don't invalidate iterators,
  74 ///   so you can scan and insert in parallel.
  75 ///
  76 /// * Fast wait-free reads - reads are usually only a single cache miss,
  77 ///   even when the hash table is very large.  Wait-freedom means that
  78 ///   you won't see latency outliers even in the face of concurrent writes.
  79 ///
  80 /// * Lock-free insert - writes proceed in parallel.  If a thread in the
  81 ///   middle of a write is unlucky and gets suspended, it doesn't block
  82 ///   anybody else.
  83 ///
  84 /// COMMENTS ON INSERT-ONLY
  85 ///
  86 /// This map provides wait-free linearizable reads and lock-free
  87 /// linearizable inserts.  Inserted values won't be moved, but no
  88 /// concurrency control is provided for safely updating them.  To remind
  89 /// you of that fact they are only provided in const form.  This is the
  90 /// only simple safe thing to do while preserving something like the normal
  91 /// std::map iteration form, which requires that iteration be exposed
  92 /// via std::pair (and prevents encapsulation of access to the value).
  93 ///
  94 /// There are a couple of reasonable policies for doing in-place
  95 /// concurrency control on the values.  I am hoping that the policy can
  96 /// be injected via the value type or an extra template param, to keep
  97 /// the core AtomicUnorderedInsertMap insert-only:
  98 ///
  99 ///   CONST: this is the currently implemented strategy, which is simple,
 100 ///   performant, and not that expressive.  You can always put in a value
 101 ///   with a mutable field (see MutableAtom below), but that doesn't look
 102 ///   as pretty as it should.
 103 ///
 104 ///   ATOMIC: for integers and integer-size trivially copyable structs
 105 ///   (via an adapter like tao/queues/AtomicStruct) the value can be a
 106 ///   std::atomic and read and written atomically.
 107 ///
 108 ///   SEQ-LOCK: attach a counter incremented before and after write.
 109 ///   Writers serialize by using CAS to make an even->odd transition,
 110 ///   then odd->even after the write.  Readers grab the value with memcpy,
 111 ///   checking sequence value before and after.  Readers retry until they
 112 ///   see an even sequence number that doesn't change.  This works for
 113 ///   larger structs, but still requires memcpy to be equivalent to copy
 114 ///   assignment, and it is no longer lock-free.  It scales very well,
 115 ///   because the readers are still invisible (no cache line writes).
 116 ///
 117 ///   LOCK: folly's SharedMutex would be a good choice here.
 118 ///
 119 /// MEMORY ALLOCATION
 120 ///
 121 /// Underlying memory is allocated as a big anonymous mmap chunk, which
 122 /// might be cheaper than calloc() and is certainly not more expensive
 123 /// for large maps.  If the SkipKeyValueDeletion template param is true
 124 /// then deletion of the map consists of unmapping the backing memory,
 125 /// which is much faster than destructing all of the keys and values.
 126 /// Feel free to override if std::is_trivial_destructor isn't recognizing
 127 /// the triviality of your destructors.
 128 template <typename Key,
 129           typename Value,
 130           typename Hash = std::hash<Key>,
 131           typename KeyEqual = std::equal_to<Key>,
 132           bool SkipKeyValueDeletion =
 133               (boost::has_trivial_destructor<Key>::value &&
 134                boost::has_trivial_destructor<Value>::value),
 135           template<typename> class Atom = std::atomic,
 136           typename Allocator = folly::detail::MMapAlloc>
 137
 138 struct AtomicUnorderedInsertMap {
 139
 140   typedef Key key_type;
 141   typedef Value mapped_type;
 142   typedef std::pair<Key,Value> value_type;
 143   typedef std::size_t size_type;
 144   typedef std::ptrdiff_t difference_type;
 145   typedef Hash hasher;
 146   typedef KeyEqual key_equal;
 147   typedef const value_type& const_reference;
 148
 149   typedef struct ConstIterator {
 150     ConstIterator(const AtomicUnorderedInsertMap& owner, uint32_t slot)
 151       : owner_(owner)
 152       , slot_(slot)
 153     {}
 154
 155     ConstIterator(const ConstIterator&) = default;
 156     ConstIterator& operator= (const ConstIterator&) = default;
 157
 158     const value_type& operator* () const {
 159       return owner_.slots_[slot_].keyValue();
 160     }
 161
 162     const value_type* operator-> () const {
 163       return &owner_.slots_[slot_].keyValue();
 164     }
 165
 166     // pre-increment
 167     const ConstIterator& operator++ () {
 168       while (slot_ > 0) {
 169         --slot_;
 170         if (owner_.slots_[slot_].state() == LINKED) {
 171           break;
 172         }
 173       }
 174       return *this;
 175     }
 176
 177     // post-increment
 178     ConstIterator operator++ (int dummy) {
 179       auto prev = *this;
 180       ++*this;
 181       return prev;
 182     }
 183
 184     bool operator== (const ConstIterator& rhs) const {
 185       return slot_ == rhs.slot_;
 186     }
 187     bool operator!= (const ConstIterator& rhs) const {
 188       return !(*this == rhs);
 189     }
 190
 191    private:
 192     const AtomicUnorderedInsertMap& owner_;
 193     uint32_t slot_;
 194   } const_iterator;
 195
 196   friend ConstIterator;
 197
 198   /// Constructs a map that will support the insertion of maxSize
 199   /// key-value pairs without exceeding the max load factor.  Load
 200   /// factors of greater than 1 are not supported, and once the actual load
 201   /// factor of the map approaches 1 the insert performance will suffer.
 202   /// The capacity is limited to 2^30 (about a billion), beyond which
 203   /// we will throw invalid_argument.
 204   explicit AtomicUnorderedInsertMap(
 205       size_t maxSize,
 206       float maxLoadFactor = 0.8f,
 207       const Allocator& alloc = Allocator())
 208     : allocator_(alloc)
 209   {
 210     size_t capacity = maxSize / std::max(1.0f, maxLoadFactor) + 128;
 211     if (capacity > (1 << 30) && maxSize < (1 << 30)) {
 212       // we'll do our best
 213       capacity = (1 << 30);
 214     }
 215     if (capacity < maxSize || capacity > (1 << 30)) {
 216       throw std::invalid_argument(
 217           "AtomicUnorderedInsertMap capacity must fit in 30 bits");
 218     }
 219
 220     numSlots_ = capacity;
 221     slotMask_ = folly::nextPowTwo(capacity * 4) - 1;
 222     mmapRequested_ = sizeof(Slot) * capacity;
 223     slots_ = reinterpret_cast<Slot*>(allocator_.allocate(mmapRequested_));
 224     zeroFillSlots();
 225     // mark the zero-th slot as in-use but not valid, since that happens
 226     // to be our nil value
 227     slots_[0].stateUpdate(EMPTY, CONSTRUCTING);
 228   }
 229
 230   ~AtomicUnorderedInsertMap() {
 231     if (!SkipKeyValueDeletion) {
 232       for (size_t i = 1; i < numSlots_; ++i) {
 233         slots_[i].~Slot();
 234       }
 235     }
 236     allocator_.deallocate(reinterpret_cast<char*>(slots_), mmapRequested_);
 237   }
 238
 239   /// Searches for the key, returning (iter,false) if it is found.
 240   /// If it is not found calls the functor Func with a void* argument
 241   /// that is raw storage suitable for placement construction of a Value
 242   /// (see raw_value_type), then returns (iter,true).  May call Func and
 243   /// then return (iter,false) if there are other concurrent writes, in
 244   /// which case the newly constructed value will be immediately destroyed.
 245   ///
 246   /// This function does not block other readers or writers.  If there
 247   /// are other concurrent writes, many parallel calls to func may happen
 248   /// and only the first one to complete will win.  The values constructed
 249   /// by the other calls to func will be destroyed.
 250   ///
 251   /// Usage:
 252   ///
 253   ///  AtomicUnorderedInsertMap<std::string,std::string> memo;
 254   ///
 255   ///  auto value = memo.findOrConstruct(key, [=](void* raw) {
 256   ///    new (raw) std::string(computation(key));
 257   ///  })->first;
 258   template<typename Func>
 259   std::pair<const_iterator,bool> findOrConstruct(const Key& key, Func&& func) {
 260     auto const slot = keyToSlotIdx(key);
 261     auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire);
 262
 263     auto existing = find(key, slot);
 264     if (existing != 0) {
 265       return std::make_pair(ConstIterator(*this, existing), false);
 266     }
 267
 268     auto idx = allocateNear(slot);
 269     new (&slots_[idx].keyValue().first) Key(key);
 270     func(static_cast<void*>(&slots_[idx].keyValue().second));
 271
 272     while (true) {
 273       slots_[idx].next_ = prev >> 2;
 274
 275       // we can merge the head update and the CONSTRUCTING -> LINKED update
 276       // into a single CAS if slot == idx (which should happen often)
 277       auto after = idx << 2;
 278       if (slot == idx) {
 279         after += LINKED;
 280       } else {
 281         after += (prev & 3);
 282       }
 283
 284       if (slots_[slot].headAndState_.compare_exchange_strong(prev, after)) {
 285         // success
 286         if (idx != slot) {
 287           slots_[idx].stateUpdate(CONSTRUCTING, LINKED);
 288         }
 289         return std::make_pair(ConstIterator(*this, idx), true);
 290       }
 291       // compare_exchange_strong updates its first arg on failure, so
 292       // there is no need to reread prev
 293
 294       existing = find(key, slot);
 295       if (existing != 0) {
 296         // our allocated key and value are no longer needed
 297         slots_[idx].keyValue().first.~Key();
 298         slots_[idx].keyValue().second.~Value();
 299         slots_[idx].stateUpdate(CONSTRUCTING, EMPTY);
 300
 301         return std::make_pair(ConstIterator(*this, existing), false);
 302       }
 303     }
 304   }
 305
 306   /// This isn't really emplace, but it is what we need to test.
 307   /// Eventually we can duplicate all of the std::pair constructor
 308   /// forms, including a recursive tuple forwarding template
 309   /// http://functionalcpp.wordpress.com/2013/08/28/tuple-forwarding/).
 310   template<class K, class V>
 311   std::pair<const_iterator,bool> emplace(const K& key, V&& value) {
 312     return findOrConstruct(key, [&](void* raw) {
 313       new (raw) Value(std::forward<V>(value));
 314     });
 315   }
 316
 317   const_iterator find(const Key& key) const {
 318     return ConstIterator(*this, find(key, keyToSlotIdx(key)));
 319   }
 320
 321   const_iterator cbegin() const {
 322     uint32_t slot = numSlots_ - 1;
 323     while (slot > 0 && slots_[slot].state() != LINKED) {
 324       --slot;
 325     }
 326     return ConstIterator(*this, slot);
 327   }
 328
 329   const_iterator cend() const {
 330     return ConstIterator(*this, 0);
 331   }
 332
 333  private:
 334
 335   enum {
 336     kMaxAllocationTries = 1000, // after this we throw
 337   };
 338
 339   enum BucketState : uint32_t {
 340     EMPTY = 0,
 341     CONSTRUCTING = 1,
 342     LINKED = 2,
 343   };
 344
 345   /// Lock-free insertion is easiest by prepending to collision chains.
 346   /// A large chaining hash table takes two cache misses instead of
 347   /// one, however.  Our solution is to colocate the bucket storage and
 348   /// the head storage, so that even though we are traversing chains we
 349   /// are likely to stay within the same cache line.  Just make sure to
 350   /// traverse head before looking at any keys.  This strategy gives us
 351   /// 32 bit pointers and fast iteration.
 352   struct Slot {
 353     /// The bottom two bits are the BucketState, the rest is the index
 354     /// of the first bucket for the chain whose keys map to this slot.
 355     /// When things are going well the head usually links to this slot,
 356     /// but that doesn't always have to happen.
 357     Atom<uint32_t> headAndState_;
 358
 359     /// The next bucket in the chain
 360     uint32_t next_;
 361
 362     /// Key and Value
 363     typename std::aligned_storage<sizeof(value_type),
 364                                   alignof(value_type)>::type raw_;
 365
 366
 367     ~Slot() {
 368       auto s = state();
 369       assert(s == EMPTY || s == LINKED);
 370       if (s == LINKED) {
 371         keyValue().first.~Key();
 372         keyValue().second.~Value();
 373       }
 374     }
 375
 376     BucketState state() const {
 377       return BucketState(headAndState_.load(std::memory_order_acquire) & 3);
 378     }
 379
 380     void stateUpdate(BucketState before, BucketState after) {
 381       assert(state() == before);
 382       headAndState_ += (after - before);
 383     }
 384
 385     value_type& keyValue() {
 386       assert(state() != EMPTY);
 387       return *static_cast<value_type*>(static_cast<void*>(&raw_));
 388     }
 389
 390     const value_type& keyValue() const {
 391       assert(state() != EMPTY);
 392       return *static_cast<const value_type*>(static_cast<const void*>(&raw_));
 393     }
 394
 395   };
 396
 397   // We manually manage the slot memory so we can bypass initialization
 398   // (by getting a zero-filled mmap chunk) and optionally destruction of
 399   // the slots
 400
 401   size_t mmapRequested_;
 402   size_t numSlots_;
 403
 404   /// tricky, see keyToSlodIdx
 405   size_t slotMask_;
 406
 407   Allocator allocator_;
 408   Slot* slots_;
 409
 410   uint32_t keyToSlotIdx(const Key& key) const {
 411     size_t h = hasher()(key);
 412     h &= slotMask_;
 413     while (h >= numSlots_) {
 414       h -= numSlots_;
 415     }
 416     return h;
 417   }
 418
 419   uint32_t find(const Key& key, uint32_t slot) const {
 420     KeyEqual ke = {};
 421     auto hs = slots_[slot].headAndState_.load(std::memory_order_acquire);
 422     for (slot = hs >> 2; slot != 0; slot = slots_[slot].next_) {
 423       if (ke(key, slots_[slot].keyValue().first)) {
 424         return slot;
 425       }
 426     }
 427     return 0;
 428   }
 429
 430   /// Allocates a slot and returns its index.  Tries to put it near
 431   /// slots_[start].
 432   uint32_t allocateNear(uint32_t start) {
 433     for (auto tries = 0; tries < kMaxAllocationTries; ++tries) {
 434       auto slot = allocationAttempt(start, tries);
 435       auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire);
 436       if ((prev & 3) == EMPTY &&
 437           slots_[slot].headAndState_.compare_exchange_strong(
 438               prev, prev + CONSTRUCTING - EMPTY)) {
 439         return slot;
 440       }
 441     }
 442     throw std::bad_alloc();
 443   }
 444
 445   /// Returns the slot we should attempt to allocate after tries failed
 446   /// tries, starting from the specified slot.  This is pulled out so we
 447   /// can specialize it differently during deterministic testing
 448   uint32_t allocationAttempt(uint32_t start, uint32_t tries) const {
 449     if (LIKELY(tries < 8 && start + tries < numSlots_)) {
 450       return start + tries;
 451     } else {
 452       uint32_t rv = folly::Random::rand32(numSlots_);
 453       assert(rv < numSlots_);
 454       return rv;
 455     }
 456   }
 457
 458   void zeroFillSlots() {
 459     using folly::detail::GivesZeroFilledMemory;
 460     if (!GivesZeroFilledMemory<Allocator>::value) {
 461       memset(slots_, 0, mmapRequested_);
 462     }
 463   }
 464 };
 465
 466
 467 /// MutableAtom is a tiny wrapper than gives you the option of atomically
 468 /// updating values inserted into an AtomicUnorderedInsertMap<K,
 469 /// MutableAtom<V>>.  This relies on AtomicUnorderedInsertMap's guarantee
 470 /// that it doesn't move values.
 471 template <typename T,
 472           template<typename> class Atom = std::atomic>
 473 struct MutableAtom {
 474   mutable Atom<T> data;
 475
 476   explicit MutableAtom(const T& init) : data(init) {}
 477 };
 478
 479 /// MutableData is a tiny wrapper than gives you the option of using an
 480 /// external concurrency control mechanism to updating values inserted
 481 /// into an AtomicUnorderedInsertMap.
 482 template <typename T>
 483 struct MutableData {
 484   mutable T data;
 485   explicit MutableData(const T& init) : data(init) {}
 486 };
 487
 488
 489 }
 490 #endif