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