2 * Copyright 2017-present 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.
18 #include <folly/experimental/hazptr/hazptr.h>
26 namespace concurrenthashmap {
28 // hazptr retire() that can use an allocator.
29 template <typename Allocator>
32 template <typename Node>
33 void operator()(Node* node) {
35 Allocator().deallocate((uint8_t*)node, sizeof(Node));
43 typename Enabled = void>
46 typedef std::pair<const KeyType, ValueType> value_type;
48 explicit ValueHolder(const ValueHolder& other) : item_(other.item_) {}
50 template <typename... Args>
51 ValueHolder(const KeyType& k, Args&&... args)
53 std::piecewise_construct,
54 std::forward_as_tuple(k),
55 std::forward_as_tuple(std::forward<Args>(args)...)) {}
56 value_type& getItem() {
64 // If the ValueType is not copy constructible, we can instead add
65 // an extra indirection. Adds more allocations / deallocations and
66 // pulls in an extra cacheline.
67 template <typename KeyType, typename ValueType, typename Allocator>
72 std::enable_if_t<!std::is_nothrow_copy_constructible<ValueType>::value>> {
74 typedef std::pair<const KeyType, ValueType> value_type;
76 explicit ValueHolder(const ValueHolder& other) {
81 template <typename... Args>
82 ValueHolder(const KeyType& k, Args&&... args) {
83 item_ = (value_type*)Allocator().allocate(sizeof(value_type));
84 new (item_) value_type(
85 std::piecewise_construct,
86 std::forward_as_tuple(k),
87 std::forward_as_tuple(std::forward<Args>(args)...));
93 Allocator().deallocate((uint8_t*)item_, sizeof(value_type));
97 value_type& getItem() {
103 mutable bool owned_{true};
110 template <typename> class Atom = std::atomic>
111 class NodeT : public folly::hazptr::hazptr_obj_base<
112 NodeT<KeyType, ValueType, Allocator, Atom>,
113 concurrenthashmap::HazptrDeleter<Allocator>> {
115 typedef std::pair<const KeyType, ValueType> value_type;
117 explicit NodeT(NodeT* other) : item_(other->item_) {}
119 template <typename... Args>
120 NodeT(const KeyType& k, Args&&... args)
121 : item_(k, std::forward<Args>(args)...) {}
123 /* Nodes are refcounted: If a node is retired() while a writer is
124 traversing the chain, the rest of the chain must remain valid
125 until all readers are finished. This includes the shared tail
126 portion of the chain, as well as both old/new hash buckets that
127 may point to the same portion, and erased nodes may increase the
130 DCHECK(refcount_.load() != 0);
131 refcount_.fetch_add(1);
134 if (refcount_.fetch_sub(1) == 1 /* was previously 1 */) {
136 folly::hazptr::default_hazptr_domain(),
137 concurrenthashmap::HazptrDeleter<Allocator>());
141 auto next = next_.load(std::memory_order_acquire);
147 value_type& getItem() {
148 return item_.getItem();
150 Atom<NodeT*> next_{nullptr};
153 ValueHolder<KeyType, ValueType, Allocator> item_;
154 Atom<uint8_t> refcount_{1};
157 } // namespace concurrenthashmap
159 /* A Segment is a single shard of the ConcurrentHashMap.
160 * All writes take the lock, while readers are all wait-free.
161 * Readers always proceed in parallel with the single writer.
164 * Possible additional optimizations:
166 * * insert / erase could be lock / wait free. Would need to be
167 * careful that assign and rehash don't conflict (possibly with
168 * reader/writer lock, or microlock per node or per bucket, etc).
169 * Java 8 goes halfway, and and does lock per bucket, except for the
170 * first item, that is inserted with a CAS (which is somewhat
171 * specific to java having a lock per object)
173 * * I tried using trylock() and find() to warm the cache for insert()
174 * and erase() similar to Java 7, but didn't have much luck.
176 * * We could order elements using split ordering, for faster rehash,
177 * and no need to ever copy nodes. Note that a full split ordering
178 * including dummy nodes increases the memory usage by 2x, but we
179 * could split the difference and still require a lock to set bucket
182 * * hazptr acquire/release could be optimized more, in
183 * single-threaded case, hazptr overhead is ~30% for a hot find()
189 uint8_t ShardBits = 0,
190 typename HashFn = std::hash<KeyType>,
191 typename KeyEqual = std::equal_to<KeyType>,
192 typename Allocator = std::allocator<uint8_t>,
193 template <typename> class Atom = std::atomic,
194 class Mutex = std::mutex>
195 class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
196 enum class InsertType {
197 DOES_NOT_EXIST, // insert/emplace operations. If key exists, return false.
198 MUST_EXIST, // assign operations. If key does not exist, return false.
199 ANY, // insert_or_assign.
200 MATCH, // assign_if_equal (not in std). For concurrent maps, a
201 // way to atomically change a value if equal to some other
206 typedef KeyType key_type;
207 typedef ValueType mapped_type;
208 typedef std::pair<const KeyType, ValueType> value_type;
209 typedef std::size_t size_type;
211 using Node = concurrenthashmap::NodeT<KeyType, ValueType, Allocator, Atom>;
214 ConcurrentHashMapSegment(
215 size_t initial_buckets,
218 : load_factor_(load_factor), max_size_(max_size) {
219 auto buckets = (Buckets*)Allocator().allocate(sizeof(Buckets));
220 initial_buckets = folly::nextPowTwo(initial_buckets);
223 (isPowTwo(max_size_) &&
224 (folly::popcount(max_size_ - 1) + ShardBits <= 32)));
225 new (buckets) Buckets(initial_buckets);
226 buckets_.store(buckets, std::memory_order_release);
227 load_factor_nodes_ = initial_buckets * load_factor_;
230 ~ConcurrentHashMapSegment() {
231 auto buckets = buckets_.load(std::memory_order_relaxed);
232 // We can delete and not retire() here, since users must have
233 // their own synchronization around destruction.
235 Allocator().deallocate((uint8_t*)buckets, sizeof(Buckets));
246 bool insert(Iterator& it, std::pair<key_type, mapped_type>&& foo) {
247 return insert(it, foo.first, foo.second);
250 bool insert(Iterator& it, const KeyType& k, const ValueType& v) {
251 auto node = (Node*)Allocator().allocate(sizeof(Node));
252 new (node) Node(k, v);
253 auto res = insert_internal(
256 InsertType::DOES_NOT_EXIST,
257 [](const ValueType&) { return false; },
262 Allocator().deallocate((uint8_t*)node, sizeof(Node));
267 template <typename... Args>
268 bool try_emplace(Iterator& it, const KeyType& k, Args&&... args) {
269 return insert_internal(
272 InsertType::DOES_NOT_EXIST,
273 [](const ValueType&) { return false; },
275 std::forward<Args>(args)...);
278 template <typename... Args>
279 bool emplace(Iterator& it, const KeyType& k, Node* node) {
280 return insert_internal(
283 InsertType::DOES_NOT_EXIST,
284 [](const ValueType&) { return false; },
288 bool insert_or_assign(Iterator& it, const KeyType& k, const ValueType& v) {
289 return insert_internal(
293 [](const ValueType&) { return false; },
298 bool assign(Iterator& it, const KeyType& k, const ValueType& v) {
299 auto node = (Node*)Allocator().allocate(sizeof(Node));
300 new (node) Node(k, v);
301 auto res = insert_internal(
304 InsertType::MUST_EXIST,
305 [](const ValueType&) { return false; },
310 Allocator().deallocate((uint8_t*)node, sizeof(Node));
315 bool assign_if_equal(
318 const ValueType& expected,
319 const ValueType& desired) {
320 return insert_internal(
324 [expected](const ValueType& v) { return v == expected; },
329 template <typename MatchFunc, typename... Args>
330 bool insert_internal(
337 auto h = HashFn()(k);
338 std::unique_lock<Mutex> g(m_);
340 auto buckets = buckets_.load(std::memory_order_relaxed);
341 // Check for rehash needed for DOES_NOT_EXIST
342 if (size_ >= load_factor_nodes_ && type == InsertType::DOES_NOT_EXIST) {
343 if (max_size_ && size_ << 1 > max_size_) {
344 // Would exceed max size.
345 throw std::bad_alloc();
347 rehash(buckets->bucket_count_ << 1);
348 buckets = buckets_.load(std::memory_order_relaxed);
351 auto idx = getIdx(buckets, h);
352 auto head = &buckets->buckets_[idx];
353 auto node = head->load(std::memory_order_relaxed);
354 auto headnode = node;
356 it.buckets_hazptr_.reset(buckets);
359 if (KeyEqual()(k, node->getItem().first)) {
360 it.setNode(node, buckets, idx);
361 it.node_hazptr_.reset(node);
362 if (type == InsertType::MATCH) {
363 if (!match(node->getItem().second)) {
367 if (type == InsertType::DOES_NOT_EXIST) {
371 cur = (Node*)Allocator().allocate(sizeof(Node));
372 new (cur) Node(k, std::forward<Args>(args)...);
374 auto next = node->next_.load(std::memory_order_relaxed);
375 cur->next_.store(next, std::memory_order_relaxed);
379 prev->store(cur, std::memory_order_release);
381 // Release not under lock.
388 node = node->next_.load(std::memory_order_relaxed);
390 if (type != InsertType::DOES_NOT_EXIST && type != InsertType::ANY) {
391 it.node_hazptr_.reset();
392 it.buckets_hazptr_.reset();
395 // Node not found, check for rehash on ANY
396 if (size_ >= load_factor_nodes_ && type == InsertType::ANY) {
397 if (max_size_ && size_ << 1 > max_size_) {
398 // Would exceed max size.
399 throw std::bad_alloc();
401 rehash(buckets->bucket_count_ << 1);
403 // Reload correct bucket.
404 buckets = buckets_.load(std::memory_order_relaxed);
405 it.buckets_hazptr_.reset(buckets);
406 idx = getIdx(buckets, h);
407 head = &buckets->buckets_[idx];
408 headnode = head->load(std::memory_order_relaxed);
411 // We found a slot to put the node.
415 // OR DOES_NOT_EXIST, but only in the try_emplace case
416 DCHECK(type == InsertType::ANY || type == InsertType::DOES_NOT_EXIST);
417 cur = (Node*)Allocator().allocate(sizeof(Node));
418 new (cur) Node(k, std::forward<Args>(args)...);
420 cur->next_.store(headnode, std::memory_order_relaxed);
421 head->store(cur, std::memory_order_release);
422 it.setNode(cur, buckets, idx);
427 void rehash(size_t bucket_count) {
428 auto buckets = buckets_.load(std::memory_order_relaxed);
429 auto newbuckets = (Buckets*)Allocator().allocate(sizeof(Buckets));
430 new (newbuckets) Buckets(bucket_count);
432 load_factor_nodes_ = bucket_count * load_factor_;
434 for (size_t i = 0; i < buckets->bucket_count_; i++) {
435 auto bucket = &buckets->buckets_[i];
436 auto node = bucket->load(std::memory_order_relaxed);
440 auto h = HashFn()(node->getItem().first);
441 auto idx = getIdx(newbuckets, h);
442 // Reuse as long a chain as possible from the end. Since the
443 // nodes don't have previous pointers, the longest last chain
444 // will be the same for both the previous hashmap and the new one,
445 // assuming all the nodes hash to the same bucket.
449 auto last = node->next_.load(std::memory_order_relaxed);
450 for (; last != nullptr;
451 last = last->next_.load(std::memory_order_relaxed)) {
452 auto k = getIdx(newbuckets, HashFn()(last->getItem().first));
460 // Set longest last run in new bucket, incrementing the refcount.
462 newbuckets->buckets_[lastidx].store(lastrun, std::memory_order_relaxed);
463 // Clone remaining nodes
464 for (; node != lastrun;
465 node = node->next_.load(std::memory_order_relaxed)) {
466 auto newnode = (Node*)Allocator().allocate(sizeof(Node));
467 new (newnode) Node(node);
468 auto k = getIdx(newbuckets, HashFn()(node->getItem().first));
469 auto prevhead = &newbuckets->buckets_[k];
470 newnode->next_.store(prevhead->load(std::memory_order_relaxed));
471 prevhead->store(newnode, std::memory_order_relaxed);
475 auto oldbuckets = buckets_.load(std::memory_order_relaxed);
476 buckets_.store(newbuckets, std::memory_order_release);
478 folly::hazptr::default_hazptr_domain(),
479 concurrenthashmap::HazptrDeleter<Allocator>());
482 bool find(Iterator& res, const KeyType& k) {
483 folly::hazptr::hazptr_holder haznext;
484 auto h = HashFn()(k);
485 auto buckets = res.buckets_hazptr_.get_protected(buckets_);
486 auto idx = getIdx(buckets, h);
487 auto prev = &buckets->buckets_[idx];
488 auto node = res.node_hazptr_.get_protected(*prev);
490 if (KeyEqual()(k, node->getItem().first)) {
491 res.setNode(node, buckets, idx);
494 node = haznext.get_protected(node->next_);
495 haznext.swap(res.node_hazptr_);
500 // Listed separately because we need a prev pointer.
501 size_type erase(const key_type& key) {
502 return erase_internal(key, nullptr);
505 size_type erase_internal(const key_type& key, Iterator* iter) {
507 auto h = HashFn()(key);
509 std::lock_guard<Mutex> g(m_);
511 auto buckets = buckets_.load(std::memory_order_relaxed);
512 auto idx = getIdx(buckets, h);
513 auto head = &buckets->buckets_[idx];
514 node = head->load(std::memory_order_relaxed);
515 Node* prev = nullptr;
517 if (KeyEqual()(key, node->getItem().first)) {
518 auto next = node->next_.load(std::memory_order_relaxed);
523 prev->next_.store(next, std::memory_order_release);
525 // Must be head of list.
526 head->store(next, std::memory_order_release);
530 iter->buckets_hazptr_.reset(buckets);
532 node->next_.load(std::memory_order_acquire), buckets, idx);
538 node = node->next_.load(std::memory_order_relaxed);
541 // Delete the node while not under the lock.
551 // Unfortunately because we are reusing nodes on rehash, we can't
552 // have prev pointers in the bucket chain. We have to start the
553 // search from the bucket.
555 // This is a small departure from standard stl containers: erase may
556 // throw if hash or key_eq functions throw.
557 void erase(Iterator& res, Iterator& pos) {
558 auto cnt = erase_internal(pos->first, &res);
563 auto buckets = buckets_.load(std::memory_order_relaxed);
564 auto newbuckets = (Buckets*)Allocator().allocate(sizeof(Buckets));
565 new (newbuckets) Buckets(buckets->bucket_count_);
567 std::lock_guard<Mutex> g(m_);
568 buckets_.store(newbuckets, std::memory_order_release);
572 folly::hazptr::default_hazptr_domain(),
573 concurrenthashmap::HazptrDeleter<Allocator>());
576 void max_load_factor(float factor) {
577 std::lock_guard<Mutex> g(m_);
578 load_factor_ = factor;
579 auto buckets = buckets_.load(std::memory_order_relaxed);
580 load_factor_nodes_ = buckets->bucket_count_ * load_factor_;
585 auto buckets = res.buckets_hazptr_.get_protected(buckets_);
586 res.setNode(nullptr, buckets, 0);
592 return Iterator(nullptr);
595 // Could be optimized to avoid an extra pointer dereference by
596 // allocating buckets_ at the same time.
597 class Buckets : public folly::hazptr::hazptr_obj_base<
599 concurrenthashmap::HazptrDeleter<Allocator>> {
601 explicit Buckets(size_t count) : bucket_count_(count) {
603 (Atom<Node*>*)Allocator().allocate(sizeof(Atom<Node*>) * count);
604 new (buckets_) Atom<Node*>[ count ];
605 for (size_t i = 0; i < count; i++) {
606 buckets_[i].store(nullptr, std::memory_order_relaxed);
610 for (size_t i = 0; i < bucket_count_; i++) {
611 auto elem = buckets_[i].load(std::memory_order_relaxed);
616 Allocator().deallocate(
617 (uint8_t*)buckets_, sizeof(Atom<Node*>) * bucket_count_);
620 size_t bucket_count_;
621 Atom<Node*>* buckets_{nullptr};
627 FOLLY_ALWAYS_INLINE Iterator() {}
628 FOLLY_ALWAYS_INLINE explicit Iterator(std::nullptr_t)
629 : buckets_hazptr_(nullptr), node_hazptr_(nullptr) {}
630 FOLLY_ALWAYS_INLINE ~Iterator() {}
632 void setNode(Node* node, Buckets* buckets, uint64_t idx) {
638 const value_type& operator*() const {
640 return node_->getItem();
643 const value_type* operator->() const {
645 return &(node_->getItem());
648 const Iterator& operator++() {
650 node_ = node_hazptr_.get_protected(node_->next_);
660 if (idx_ >= buckets_->bucket_count_) {
664 DCHECK(buckets_->buckets_);
665 node_ = node_hazptr_.get_protected(buckets_->buckets_[idx_]);
673 Iterator operator++(int) {
679 bool operator==(const Iterator& o) const {
680 return node_ == o.node_;
683 bool operator!=(const Iterator& o) const {
684 return !(*this == o);
687 Iterator& operator=(const Iterator& o) {
689 node_hazptr_.reset(node_);
691 buckets_ = o.buckets_;
692 buckets_hazptr_.reset(buckets_);
696 /* implicit */ Iterator(const Iterator& o) {
698 node_hazptr_.reset(node_);
700 buckets_ = o.buckets_;
701 buckets_hazptr_.reset(buckets_);
704 /* implicit */ Iterator(Iterator&& o) noexcept
705 : buckets_hazptr_(std::move(o.buckets_hazptr_)),
706 node_hazptr_(std::move(o.node_hazptr_)) {
708 buckets_ = o.buckets_;
712 // These are accessed directly from the functions above
713 folly::hazptr::hazptr_holder buckets_hazptr_;
714 folly::hazptr::hazptr_holder node_hazptr_;
717 Node* node_{nullptr};
718 Buckets* buckets_{nullptr};
723 // Shards have already used low ShardBits of the hash.
724 // Shift it over to use fresh bits.
725 uint64_t getIdx(Buckets* buckets, size_t hash) {
726 return (hash >> ShardBits) & (buckets->bucket_count_ - 1);
730 size_t load_factor_nodes_;
732 size_t const max_size_;
733 Atom<Buckets*> buckets_{nullptr};
736 } // namespace detail