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