2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #ifndef FOLLY_ATOMICUNORDEREDMAP_H
17 #define FOLLY_ATOMICUNORDEREDMAP_H
22 #include <system_error>
23 #include <type_traits>
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>
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.
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.
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.
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.
63 /// WHAT YOU GET IN EXCHANGE:
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!
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).
73 /// * Iterators are never invalidated - writes don't invalidate iterators,
74 /// so you can scan and insert in parallel.
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.
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
84 /// COMMENTS ON INSERT-ONLY
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).
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:
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.
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.
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).
117 /// LOCK: folly's SharedMutex would be a good choice here.
119 /// MEMORY ALLOCATION
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,
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>
138 struct AtomicUnorderedInsertMap {
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;
146 typedef KeyEqual key_equal;
147 typedef const value_type& const_reference;
149 typedef struct ConstIterator {
150 ConstIterator(const AtomicUnorderedInsertMap& owner, uint32_t slot)
155 ConstIterator(const ConstIterator&) = default;
156 ConstIterator& operator= (const ConstIterator&) = default;
158 const value_type& operator* () const {
159 return owner_.slots_[slot_].keyValue();
162 const value_type* operator-> () const {
163 return &owner_.slots_[slot_].keyValue();
167 const ConstIterator& operator++ () {
170 if (owner_.slots_[slot_].state() == LINKED) {
178 ConstIterator operator++ (int dummy) {
184 bool operator== (const ConstIterator& rhs) const {
185 return slot_ == rhs.slot_;
187 bool operator!= (const ConstIterator& rhs) const {
188 return !(*this == rhs);
192 const AtomicUnorderedInsertMap& owner_;
196 friend ConstIterator;
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(
206 float maxLoadFactor = 0.8f,
207 const Allocator& alloc = Allocator())
210 size_t capacity = maxSize / std::max(1.0f, maxLoadFactor) + 128;
211 if (capacity > (1 << 30) && maxSize < (1 << 30)) {
213 capacity = (1 << 30);
215 if (capacity < maxSize || capacity > (1 << 30)) {
216 throw std::invalid_argument(
217 "AtomicUnorderedInsertMap capacity must fit in 30 bits");
220 numSlots_ = capacity;
221 slotMask_ = folly::nextPowTwo(capacity * 4) - 1;
222 mmapRequested_ = sizeof(Slot) * capacity;
223 slots_ = reinterpret_cast<Slot*>(allocator_.allocate(mmapRequested_));
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);
230 ~AtomicUnorderedInsertMap() {
231 if (!SkipKeyValueDeletion) {
232 for (size_t i = 1; i < numSlots_; ++i) {
236 allocator_.deallocate(reinterpret_cast<char*>(slots_), mmapRequested_);
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.
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.
253 /// AtomicUnorderedInsertMap<std::string,std::string> memo;
255 /// auto value = memo.findOrConstruct(key, [=](void* raw) {
256 /// new (raw) std::string(computation(key));
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);
263 auto existing = find(key, slot);
265 return std::make_pair(ConstIterator(*this, existing), false);
268 auto idx = allocateNear(slot);
269 new (&slots_[idx].keyValue().first) Key(key);
270 func(static_cast<void*>(&slots_[idx].keyValue().second));
273 slots_[idx].next_ = prev >> 2;
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;
284 if (slots_[slot].headAndState_.compare_exchange_strong(prev, after)) {
287 slots_[idx].stateUpdate(CONSTRUCTING, LINKED);
289 return std::make_pair(ConstIterator(*this, idx), true);
291 // compare_exchange_strong updates its first arg on failure, so
292 // there is no need to reread prev
294 existing = find(key, slot);
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);
301 return std::make_pair(ConstIterator(*this, existing), false);
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));
317 const_iterator find(const Key& key) const {
318 return ConstIterator(*this, find(key, keyToSlotIdx(key)));
321 const_iterator cbegin() const {
322 uint32_t slot = numSlots_ - 1;
323 while (slot > 0 && slots_[slot].state() != LINKED) {
326 return ConstIterator(*this, slot);
329 const_iterator cend() const {
330 return ConstIterator(*this, 0);
336 kMaxAllocationTries = 1000, // after this we throw
339 enum BucketState : uint32_t {
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.
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_;
359 /// The next bucket in the chain
363 typename std::aligned_storage<sizeof(value_type),
364 alignof(value_type)>::type raw_;
369 assert(s == EMPTY || s == LINKED);
371 keyValue().first.~Key();
372 keyValue().second.~Value();
376 BucketState state() const {
377 return BucketState(headAndState_.load(std::memory_order_acquire) & 3);
380 void stateUpdate(BucketState before, BucketState after) {
381 assert(state() == before);
382 headAndState_ += (after - before);
385 value_type& keyValue() {
386 assert(state() != EMPTY);
387 return *static_cast<value_type*>(static_cast<void*>(&raw_));
390 const value_type& keyValue() const {
391 assert(state() != EMPTY);
392 return *static_cast<const value_type*>(static_cast<const void*>(&raw_));
397 // We manually manage the slot memory so we can bypass initialization
398 // (by getting a zero-filled mmap chunk) and optionally destruction of
401 size_t mmapRequested_;
404 /// tricky, see keyToSlodIdx
407 Allocator allocator_;
410 uint32_t keyToSlotIdx(const Key& key) const {
411 size_t h = hasher()(key);
413 while (h >= numSlots_) {
419 uint32_t find(const Key& key, uint32_t slot) const {
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)) {
430 /// Allocates a slot and returns its index. Tries to put it near
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)) {
442 throw std::bad_alloc();
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;
452 uint32_t rv = folly::Random::rand32(numSlots_);
453 assert(rv < numSlots_);
458 void zeroFillSlots() {
459 using folly::detail::GivesZeroFilledMemory;
460 if (!GivesZeroFilledMemory<Allocator>::value) {
461 memset(slots_, 0, mmapRequested_);
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>
474 mutable Atom<T> data;
476 explicit MutableAtom(const T& init) : data(init) {}
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>
485 explicit MutableData(const T& init) : data(init) {}