PMDK C++ bindings  1.11
This is the C++ bindings documentation for PMDK's libpmemobj.
concurrent_hash_map.hpp
Go to the documentation of this file.
1 // SPDX-License-Identifier: BSD-3-Clause
2 /* Copyright 2019-2020, Intel Corporation */
3 
10 #ifndef PMEMOBJ_CONCURRENT_HASH_MAP_HPP
11 #define PMEMOBJ_CONCURRENT_HASH_MAP_HPP
12 
15 #include <libpmemobj++/detail/pair.hpp>
17 
18 #include <libpmemobj++/defrag.hpp>
20 #include <libpmemobj++/mutex.hpp>
21 #include <libpmemobj++/p.hpp>
24 
25 #include <libpmemobj++/detail/persistent_pool_ptr.hpp>
27 
29 
30 #include <atomic>
31 #include <cassert>
32 #include <functional>
33 #include <initializer_list>
34 #include <iterator> // for std::distance
35 #include <memory>
36 #include <mutex>
37 #include <thread>
38 #include <type_traits>
39 #include <utility>
40 #include <vector>
41 
42 namespace std
43 {
47 template <typename T>
48 struct hash<pmem::obj::p<T>> {
49  size_t
50  operator()(const pmem::obj::p<T> &x) const
51  {
52  return hash<T>()(x.get_ro());
53  }
54 };
55 } /* namespace std */
56 
57 namespace pmem
58 {
59 namespace obj
60 {
61 
62 namespace concurrent_hash_map_internal
63 {
64 template <typename SharedMutexT>
65 class shared_mutex_scoped_lock {
66  using rw_mutex_type = SharedMutexT;
67 
68 public:
69  shared_mutex_scoped_lock(const shared_mutex_scoped_lock &) = delete;
70  shared_mutex_scoped_lock &
71  operator=(const shared_mutex_scoped_lock &) = delete;
72 
74  shared_mutex_scoped_lock() : mutex(nullptr), is_writer(false)
75  {
76  }
77 
79  shared_mutex_scoped_lock(rw_mutex_type &m, bool write = true)
80  : mutex(nullptr)
81  {
82  acquire(m, write);
83  }
84 
86  ~shared_mutex_scoped_lock()
87  {
88  if (mutex)
89  release();
90  }
91 
93  void
94  acquire(rw_mutex_type &m, bool write = true)
95  {
96  is_writer = write;
97  mutex = &m;
98  if (write)
99  mutex->lock();
100  else
101  mutex->lock_shared();
102  }
103 
107  void
108  release()
109  {
110  assert(mutex);
111  rw_mutex_type *m = mutex;
112  mutex = nullptr;
113  if (is_writer) {
114  m->unlock();
115  } else {
116  m->unlock_shared();
117  }
118  }
119 
124  bool
125  try_acquire(rw_mutex_type &m, bool write = true)
126  {
127  assert(!mutex);
128  bool result;
129  is_writer = write;
130  result = write ? m.try_lock() : m.try_lock_shared();
131  if (result)
132  mutex = &m;
133  return result;
134  }
135 
136 protected:
141  rw_mutex_type *mutex;
146  bool is_writer;
147 }; /* class shared_mutex_scoped_lock */
148 
149 template <typename ScopedLockType>
150 using scoped_lock_upgrade_to_writer =
151  decltype(std::declval<ScopedLockType>().upgrade_to_writer());
152 
153 template <typename ScopedLockType>
154 using scoped_lock_has_upgrade_to_writer =
155  detail::supports<ScopedLockType, scoped_lock_upgrade_to_writer>;
156 
157 template <typename ScopedLockType>
158 using scoped_lock_downgrade_to_reader =
159  decltype(std::declval<ScopedLockType>().downgrade_to_reader());
160 
161 template <typename ScopedLockType>
162 using scoped_lock_has_downgrade_to_reader =
163  detail::supports<ScopedLockType, scoped_lock_downgrade_to_reader>;
164 
165 template <typename ScopedLockType,
166  bool = scoped_lock_has_upgrade_to_writer<ScopedLockType>::value
167  &&scoped_lock_has_downgrade_to_reader<ScopedLockType>::value>
168 class scoped_lock_traits {
169 public:
170  using scope_lock_type = ScopedLockType;
171 
172  static bool
173  initial_rw_state(bool write)
174  {
175  /* For upgradeable locks, initial state is always read */
176  return false;
177  }
178 
179  static bool
180  upgrade_to_writer(scope_lock_type &lock)
181  {
182  return lock.upgrade_to_writer();
183  }
184 
185  static bool
186  downgrade_to_reader(scope_lock_type &lock)
187  {
188  return lock.downgrade_to_reader();
189  }
190 };
191 
192 template <typename ScopedLockType>
193 class scoped_lock_traits<ScopedLockType, false> {
194 public:
195  using scope_lock_type = ScopedLockType;
196 
197  static bool
198  initial_rw_state(bool write)
199  {
200  /* For non-upgradeable locks, we take lock in required mode
201  * immediately */
202  return write;
203  }
204 
205  static bool
206  upgrade_to_writer(scope_lock_type &lock)
207  {
208  /* This overload is for locks which do not support upgrade
209  * operation. For those locks, upgrade_to_writer should not be
210  * called when holding a read lock */
211  return true;
212  }
213 
214  static bool
215  downgrade_to_reader(scope_lock_type &lock)
216  {
217  /* This overload is for locks which do not support downgrade
218  * operation. For those locks, downgrade_to_reader should never
219  * be called */
220  assert(false);
221 
222  return false;
223  }
224 };
225 }
226 
227 template <typename Key, typename T, typename Hash = std::hash<Key>,
228  typename KeyEqual = std::equal_to<Key>,
229  typename MutexType = pmem::obj::shared_mutex,
230  typename ScopedLockType = concurrent_hash_map_internal::
231  shared_mutex_scoped_lock<MutexType>>
232 class concurrent_hash_map;
233 
235 namespace concurrent_hash_map_internal
236 {
237 /* Helper method which throws an exception when called in a tx */
238 static inline void
239 check_outside_tx()
240 {
241  if (pmemobj_tx_stage() != TX_STAGE_NONE)
243  "Function called inside transaction scope.");
244 }
245 
246 template <typename Hash>
247 using transparent_key_equal = typename Hash::transparent_key_equal;
248 
249 template <typename Hash>
250 using has_transparent_key_equal = detail::supports<Hash, transparent_key_equal>;
251 
252 template <typename Hash, typename Pred,
253  bool = has_transparent_key_equal<Hash>::value>
254 struct key_equal_type {
255  using type = typename Hash::transparent_key_equal;
256 };
257 
258 template <typename Hash, typename Pred>
259 struct key_equal_type<Hash, Pred, false> {
260  using type = Pred;
261 };
262 
263 template <typename Mutex, typename ScopedLockType>
264 void
265 assert_not_locked(Mutex &mtx)
266 {
267 #ifndef NDEBUG
268  ScopedLockType scoped_lock;
269  assert(scoped_lock.try_acquire(mtx));
270  scoped_lock.release();
271 #else
272  (void)mtx;
273 #endif
274 }
275 
276 template <typename Key, typename T, typename MutexType, typename ScopedLockType>
277 struct hash_map_node {
279  using mutex_t = MutexType;
280 
282  using scoped_t = ScopedLockType;
283 
284  using value_type = detail::pair<const Key, T>;
285 
287  using node_ptr_t = detail::persistent_pool_ptr<
288  hash_map_node<Key, T, mutex_t, scoped_t>>;
289 
291  node_ptr_t next;
292 
294  mutex_t mutex;
295 
297  value_type item;
298 
299  hash_map_node(const node_ptr_t &_next, const Key &key)
300  : next(_next),
301  item(std::piecewise_construct, std::forward_as_tuple(key),
302  std::forward_as_tuple())
303  {
304  }
305 
306  hash_map_node(const node_ptr_t &_next, const Key &key, const T &t)
307  : next(_next), item(key, t)
308  {
309  }
310 
311  hash_map_node(const node_ptr_t &_next, value_type &&i)
312  : next(_next), item(std::move(i))
313  {
314  }
315 
316  template <typename... Args>
317  hash_map_node(const node_ptr_t &_next, Args &&... args)
318  : next(_next), item(std::forward<Args>(args)...)
319  {
320  }
321 
322  hash_map_node(const node_ptr_t &_next, const value_type &i)
323  : next(_next), item(i)
324  {
325  }
326 
328  hash_map_node(const hash_map_node &) = delete;
329 
331  hash_map_node &operator=(const hash_map_node &) = delete;
332 }; /* struct node */
333 
338 template <typename Bucket>
339 class segment_traits {
340 public:
342  using segment_index_t = size_t;
343  using size_type = size_t;
344  using bucket_type = Bucket;
345 
346 protected:
348  constexpr static size_type max_allocation_size = PMEMOBJ_MAX_ALLOC_SIZE;
349 
351  constexpr static segment_index_t first_big_block = 27;
352  /* TODO: avoid hardcoded value; need constexpr similar to:
353  * Log2(max_allocation_size / sizeof(bucket_type)) */
354 
356  constexpr static size_type big_block_size = size_type(1)
357  << first_big_block;
358 
359  /* Block size in bytes cannot exceed max_allocation_size */
360  static_assert((big_block_size * sizeof(bucket_type)) <
361  max_allocation_size,
362  "Block size exceeds max_allocation_size");
363 
365  constexpr static segment_index_t
366  first_block_in_segment(segment_index_t seg)
367  {
368  return seg < first_big_block
369  ? seg
370  : (first_big_block +
371  (segment_index_t(1) << (seg - first_big_block)) - 1);
372  }
373 
375  constexpr static size_type
376  blocks_in_segment(segment_index_t seg)
377  {
378  return seg < first_big_block
379  ? segment_index_t(1)
380  : segment_index_t(1) << (seg - first_big_block);
381  }
382 
384  constexpr static size_type
385  block_size(segment_index_t b)
386  {
387  return b < first_big_block ? segment_size(b ? b : 1)
388  : big_block_size;
389  }
390 
391 public:
393  constexpr static segment_index_t embedded_segments = 1;
394 
396  constexpr static size_type embedded_buckets = 1 << embedded_segments;
397 
399  constexpr static segment_index_t number_of_segments = 32;
400 
402  static const size_type first_block = 8;
403 
405  constexpr static segment_index_t
406  number_of_blocks()
407  {
408  return first_block_in_segment(number_of_segments);
409  }
410 
412  static segment_index_t
413  segment_index_of(size_type index)
414  {
415  return segment_index_t(detail::Log2(index | 1));
416  }
417 
419  constexpr static segment_index_t
420  segment_base(segment_index_t k)
421  {
422  return (segment_index_t(1) << k) & ~segment_index_t(1);
423  }
424 
426  constexpr static size_type
427  segment_size(segment_index_t k)
428  {
429  return size_type(1) << k; // fake value for k == 0
430  }
431  static_assert(
432  embedded_segments < first_big_block,
433  "Number of embedded segments cannot exceed max_allocation_size");
434 }; /* End of class segment_traits */
435 
452 template <typename BlockTable, typename SegmentTraits, bool is_const>
453 class segment_facade_impl : public SegmentTraits {
454 private:
455  using traits_type = SegmentTraits;
456  using traits_type::block_size;
457  using traits_type::blocks_in_segment;
458  using traits_type::embedded_buckets;
459  using traits_type::embedded_segments;
460  using traits_type::first_block;
461  using traits_type::first_block_in_segment;
462  using traits_type::segment_base;
463  using traits_type::segment_size;
464 
465 public:
466  using table_reference =
467  typename std::conditional<is_const, const BlockTable &,
468  BlockTable &>::type;
469 
470  using table_pointer =
471  typename std::conditional<is_const, const BlockTable *,
472  BlockTable *>::type;
473 
474  using bucket_type = typename traits_type::bucket_type;
475  using segment_index_t = typename traits_type::segment_index_t;
476  using size_type = typename traits_type::size_type;
477 
479  segment_facade_impl(table_reference table, segment_index_t s)
480  : my_table(&table), my_seg(s)
481  {
482  assert(my_seg < traits_type::number_of_segments);
483  }
484 
486  segment_facade_impl(const segment_facade_impl &src)
487  : my_table(src.my_table), my_seg(src.my_seg)
488  {
489  }
490 
491  segment_facade_impl(segment_facade_impl &&src) = default;
492 
494  segment_facade_impl &
495  operator=(const segment_facade_impl &src)
496  {
497  my_table = src.my_table;
498  my_seg = src.my_seg;
499  return *this;
500  }
501 
503  segment_facade_impl &
504  operator=(segment_facade_impl &&src)
505  {
506  my_table = src.my_table;
507  my_seg = src.my_seg;
508  return *this;
509  }
510 
517  bucket_type &operator[](size_type i) const
518  {
519  assert(i < size());
520 
521  segment_index_t table_block = first_block_in_segment(my_seg);
522  size_type b_size = block_size(table_block);
523 
524  table_block += i / b_size;
525  i = i % b_size;
526 
527  return (*my_table)[table_block][static_cast<std::ptrdiff_t>(i)];
528  }
529 
533  segment_facade_impl &
534  operator++()
535  {
536  ++my_seg;
537  return *this;
538  }
539 
543  segment_facade_impl
544  operator++(int)
545  {
546  segment_facade_impl tmp = *this;
547  ++(*this);
548  return tmp;
549  }
550 
554  segment_facade_impl &
555  operator--()
556  {
557  --my_seg;
558  return *this;
559  }
560 
564  segment_facade_impl
565  operator--(int)
566  {
567  segment_facade_impl tmp = *this;
568  --(*this);
569  return tmp;
570  }
571 
575  segment_facade_impl &
576  operator+=(segment_index_t off)
577  {
578  my_seg += off;
579  return *this;
580  }
581 
585  segment_facade_impl &
586  operator-=(segment_index_t off)
587  {
588  my_seg -= off;
589  return *this;
590  }
591 
595  segment_facade_impl
596  operator+(segment_index_t off) const
597  {
598  return segment_facade_impl(*(this->my_table),
599  this->my_seg + off);
600  }
601 
605  segment_facade_impl
606  operator-(segment_index_t off) const
607  {
608  return segment_facade_impl(*(this->my_table),
609  this->my_seg - off);
610  }
611 
615  void
616  enable(pool_base &pop)
617  {
618  assert(my_seg >= embedded_segments);
619 
620  if (my_seg < first_block) {
621  enable_first_block(pop);
622  } else {
623  enable_big_segment(pop);
624  }
625  }
626 
630  void
631  disable()
632  {
633  assert(my_seg >= embedded_segments);
634 
635  if (my_seg < first_block) {
636  if (my_seg == embedded_segments) {
637  size_type sz = segment_size(first_block) -
638  embedded_buckets;
639  delete_persistent<bucket_type[]>(
640  (*my_table)[my_seg], sz);
641  }
642  (*my_table)[my_seg] = nullptr;
643  } else {
644  block_range blocks = segment_blocks(my_seg);
645 
646  for (segment_index_t b = blocks.first;
647  b < blocks.second; ++b) {
648  if ((*my_table)[b] != nullptr) {
649  delete_persistent<bucket_type[]>(
650  (*my_table)[b], block_size(b));
651  (*my_table)[b] = nullptr;
652  }
653  }
654  }
655  }
656 
660  constexpr size_type
661  size() const
662  {
663  return segment_size(my_seg ? my_seg : 1);
664  }
665 
671  bool
672  is_valid() const
673  {
674  block_range blocks = segment_blocks(my_seg);
675 
676  for (segment_index_t b = blocks.first; b < blocks.second; ++b) {
677  if ((*my_table)[b] == nullptr)
678  return false;
679  }
680 
681  return true;
682  }
683 
684 private:
685  using block_range = std::pair<segment_index_t, segment_index_t>;
686 
690  static block_range
691  segment_blocks(segment_index_t seg)
692  {
693  segment_index_t begin = first_block_in_segment(seg);
694 
695  return block_range(begin, begin + blocks_in_segment(seg));
696  }
697 
698  void
699  enable_first_block(pool_base &pop)
700  {
701  assert(my_seg == embedded_segments);
702  {
703  transaction::manual tx(pop);
704 
705  size_type sz =
706  segment_size(first_block) - embedded_buckets;
707  (*my_table)[my_seg] =
708  make_persistent<bucket_type[]>(sz);
709 
710  persistent_ptr<bucket_type> base =
711  (*my_table)[embedded_segments].raw();
712 
713  for (segment_index_t s = my_seg + 1; s < first_block;
714  ++s) {
715  std::ptrdiff_t off =
716  static_cast<std::ptrdiff_t>(
717  segment_base(s) -
718  segment_base(my_seg));
719 
720  (*my_table)[s] = (base + off).raw();
721  }
722 
724  }
725  }
726 
727  void
728  enable_big_segment(pool_base &pop)
729  {
730  block_range blocks = segment_blocks(my_seg);
731  {
732  transaction::manual tx(pop);
733 
734  for (segment_index_t b = blocks.first;
735  b < blocks.second; ++b) {
736  assert((*my_table)[b] == nullptr);
737  (*my_table)[b] = make_persistent<bucket_type[]>(
738  block_size(b));
739  }
740 
742  }
743  }
744 
746  table_pointer my_table;
747 
749  segment_index_t my_seg;
750 }; /* End of class segment_facade_impl */
751 
758 template <typename Key, typename T, typename MutexType, typename ScopedLockType>
759 class hash_map_base {
760 public:
761  using mutex_t = MutexType;
762  using scoped_t = ScopedLockType;
763 
765  using size_type = size_t;
766 
768  using hashcode_type = size_t;
769 
771  using node = hash_map_node<Key, T, mutex_t, scoped_t>;
772 
774  using node_ptr_t = detail::persistent_pool_ptr<node>;
775 
777  struct bucket {
778  using mutex_t = MutexType;
779  using scoped_t = ScopedLockType;
780 
782  mutex_t mutex;
783 
785  p<std::atomic<uint64_t>> rehashed;
786 
788  node_ptr_t node_list;
789 
791  bucket() : node_list(nullptr)
792  {
793 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
794  VALGRIND_HG_DISABLE_CHECKING(&rehashed,
795  sizeof(rehashed));
796 #endif
797  rehashed.get_rw() = false;
798  }
799 
805  bool
806  is_rehashed(std::memory_order order)
807  {
808  return rehashed.get_ro().load(order);
809  }
810 
811  void
812  set_rehashed(std::memory_order order)
813  {
814  rehashed.get_rw().store(true, order);
815  }
816 
818  bucket(const bucket &) = delete;
819 
821  bucket &operator=(const bucket &) = delete;
822  }; /* End of struct bucket */
823 
825  using segment_traits_t = segment_traits<bucket>;
826 
828  using segment_index_t = typename segment_traits_t::segment_index_t;
829 
831  static const size_type embedded_buckets =
832  segment_traits_t::embedded_buckets;
833 
835  static const size_type first_block = segment_traits_t::first_block;
836 
838  constexpr static size_type block_table_size =
839  segment_traits_t::number_of_blocks();
840 
842  using segment_ptr_t = persistent_ptr<bucket[]>;
843 
845  using bucket_ptr_t = persistent_ptr<bucket>;
846 
848  using blocks_table_t = segment_ptr_t[block_table_size];
849 
851  using segment_enable_mutex_t = pmem::obj::mutex;
852 
854  struct tls_data_t {
855  p<int64_t> size_diff = 0;
856  std::aligned_storage<56, 8> padding;
857  };
858 
859  using tls_t = detail::enumerable_thread_specific<tls_data_t>;
860 
861  enum feature_flags : uint32_t { FEATURE_CONSISTENT_SIZE = 1 };
862 
864  struct features {
865  p<uint32_t> compat;
866  p<uint32_t> incompat;
867  };
868 
869  /* --------------------------------------------------------- */
870 
872  p<uint64_t> my_pool_uuid;
873 
876  features layout_features;
877 
880  std::aligned_storage<sizeof(size_t), sizeof(size_t)>::type
881  my_mask_reserved;
882 
884  /* my_mask always restored on restart. */
885  std::atomic<hashcode_type> my_mask;
886 
887  /* Size of value (key and value pair) stored in a pool */
888  std::size_t value_size;
889 
891  std::aligned_storage<24, 8>::type padding1;
892 
897  blocks_table_t my_table;
898 
899  /* It must be in separate cache line from my_mask due to performance
900  * effects */
902  std::atomic<size_type> my_size;
903 
905  std::aligned_storage<24, 8>::type padding2;
906 
908  persistent_ptr<tls_t> tls_ptr;
909 
915  p<size_t> on_init_size;
916 
918  std::aligned_storage<40, 8>::type reserved;
919 
921  segment_enable_mutex_t my_segment_enable_mutex;
922 
924  bucket my_embedded_segment[embedded_buckets];
925 
926  /* --------------------------------------------------------- */
927 
929  static constexpr features
930  header_features()
931  {
932  return {FEATURE_CONSISTENT_SIZE, 0};
933  }
934 
935  const std::atomic<hashcode_type> &
936  mask() const noexcept
937  {
938  return my_mask;
939  }
940 
941  std::atomic<hashcode_type> &
942  mask() noexcept
943  {
944  return my_mask;
945  }
946 
947  size_t
948  size() const
949  {
950  return my_size.load(std::memory_order_relaxed);
951  }
952 
953  p<int64_t> &
954  thread_size_diff()
955  {
956  assert(this->tls_ptr != nullptr);
957  return this->tls_ptr->local().size_diff;
958  }
959 
961  void
962  tls_restore()
963  {
964  assert(this->tls_ptr != nullptr);
965 
966  pool_base pop = pool_base{pmemobj_pool_by_ptr(this)};
967 
968  int64_t last_run_size = 0;
969  for (auto &data : *tls_ptr)
970  last_run_size += data.size_diff;
971 
972  /* Make sure that on_init_size + last_run_size >= 0 */
973  assert(last_run_size >= 0 ||
974  static_cast<int64_t>(static_cast<size_t>(last_run_size) +
975  on_init_size) >= 0);
976 
977  transaction::run(pop, [&] {
978  on_init_size += static_cast<size_t>(last_run_size);
979  tls_ptr->clear();
980  });
981 
982  this->my_size = on_init_size;
983  }
984 
986  using const_segment_facade_t =
987  segment_facade_impl<blocks_table_t, segment_traits_t, true>;
988 
990  using segment_facade_t =
991  segment_facade_impl<blocks_table_t, segment_traits_t, false>;
992 
994  hash_map_base()
995  {
996  static_assert(
997  sizeof(size_type) == sizeof(std::atomic<size_type>),
998  "std::atomic should have the same layout as underlying integral type");
999 
1000 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
1001  VALGRIND_HG_DISABLE_CHECKING(&my_mask, sizeof(my_mask));
1002 #endif
1003  layout_features = {0, 0};
1004 
1005  PMEMoid oid = pmemobj_oid(this);
1006 
1007  assert(!OID_IS_NULL(oid));
1008 
1009  my_pool_uuid = oid.pool_uuid_lo;
1010 
1011  pool_base pop = get_pool_base();
1012  /* enable embedded segments */
1013  for (size_type i = 0; i < segment_traits_t::embedded_segments;
1014  ++i) {
1015  my_table[i] =
1016  pmemobj_oid(my_embedded_segment +
1017  segment_traits_t::segment_base(i));
1018  segment_facade_t seg(my_table, i);
1019  mark_rehashed<false>(pop, seg);
1020  }
1021 
1022  on_init_size = 0;
1023 
1024  value_size = 0;
1025 
1026  this->tls_ptr = nullptr;
1027  }
1028 
1029  /*
1030  * Should be called before concurrent_hash_map destructor is called.
1031  * Otherwise, program can terminate if an exception occurs wile freeing
1032  * memory inside dtor.
1033  */
1034  void
1035  free_tls()
1036  {
1037  auto pop = get_pool_base();
1038 
1039  if ((layout_features.compat & FEATURE_CONSISTENT_SIZE) &&
1040  tls_ptr) {
1041  transaction::run(pop, [&] {
1042  delete_persistent<tls_t>(tls_ptr);
1043  tls_ptr = nullptr;
1044  });
1045  }
1046  }
1047 
1051  void
1052  calculate_mask()
1053  {
1054 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
1055  VALGRIND_HG_DISABLE_CHECKING(&my_size, sizeof(my_size));
1056  VALGRIND_HG_DISABLE_CHECKING(&my_mask, sizeof(my_mask));
1057 #endif
1058 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
1059  VALGRIND_PMC_REMOVE_PMEM_MAPPING(&my_size, sizeof(my_size));
1060  VALGRIND_PMC_REMOVE_PMEM_MAPPING(&my_mask, sizeof(my_mask));
1061 #endif
1062 
1063  hashcode_type m = embedded_buckets - 1;
1064 
1065  const_segment_facade_t segment(
1066  my_table, segment_traits_t::embedded_segments);
1067 
1068  while (segment.is_valid()) {
1069  m += segment.size();
1070  ++segment;
1071  }
1072 
1073  mask().store(m, std::memory_order_relaxed);
1074  }
1075 
1079  template <bool Flush = true>
1080  void
1081  mark_rehashed(pool_base &pop, segment_facade_t &segment)
1082  {
1083  for (size_type i = 0; i < segment.size(); ++i) {
1084  bucket *b = &(segment[i]);
1085 
1086  assert_not_locked<mutex_t, scoped_t>(b->mutex);
1087 
1088  b->set_rehashed(std::memory_order_relaxed);
1089  }
1090 
1091  if (Flush) {
1092  /* Flush in separate loop to avoid read-after-flush */
1093  for (size_type i = 0; i < segment.size(); ++i) {
1094  bucket *b = &(segment[i]);
1095  pop.flush(b->rehashed);
1096  }
1097 
1098  pop.drain();
1099  }
1100  }
1101 
1105  void
1106  enable_segment(segment_index_t k, bool is_initial = false)
1107  {
1108  assert(k);
1109 
1110  pool_base pop = get_pool_base();
1111  size_type sz;
1112 
1113  if (k >= first_block) {
1114  segment_facade_t new_segment(my_table, k);
1115 
1116  sz = new_segment.size();
1117  if (!new_segment.is_valid())
1118  new_segment.enable(pop);
1119 
1120  if (is_initial) {
1121  mark_rehashed(pop, new_segment);
1122  }
1123 
1124  /* double it to get entire capacity of the container */
1125  sz <<= 1;
1126  } else {
1127  /* the first block */
1128  assert(k == segment_traits_t::embedded_segments);
1129 
1130  for (segment_index_t i = k; i < first_block; ++i) {
1131  segment_facade_t new_segment(my_table, i);
1132 
1133  if (!new_segment.is_valid())
1134  new_segment.enable(pop);
1135 
1136  if (is_initial) {
1137  mark_rehashed(pop, new_segment);
1138  }
1139  }
1140 
1141  sz = segment_traits_t::segment_size(first_block);
1142  }
1143 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
1144  ANNOTATE_HAPPENS_BEFORE(&my_mask);
1145 #endif
1146  mask().store(sz - 1, std::memory_order_release);
1147  }
1148 
1153  bucket *
1154  get_bucket(hashcode_type h) const
1155  {
1156  segment_index_t s = segment_traits_t::segment_index_of(h);
1157 
1158  h -= segment_traits_t::segment_base(s);
1159 
1160  const_segment_facade_t segment(my_table, s);
1161 
1162  assert(segment.is_valid());
1163 
1164  return &(segment[h]);
1165  }
1166 
1170  inline bool
1171  check_mask_race(hashcode_type h, hashcode_type &m) const
1172  {
1173  hashcode_type m_now, m_old = m;
1174 
1175  m_now = mask().load(std::memory_order_acquire);
1176 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
1177  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
1178 #endif
1179 
1180  if (m_old != m_now)
1181  return check_rehashing_collision(h, m_old, m = m_now);
1182 
1183  return false;
1184  }
1185 
1189  bool
1190  check_rehashing_collision(hashcode_type h, hashcode_type m_old,
1191  hashcode_type m) const
1192  {
1193  assert(m_old != m);
1194 
1195  if ((h & m_old) != (h & m)) {
1196  /* mask changed for this hashcode, rare event condition
1197  * above proves that 'h' has some other bits set beside
1198  * 'm_old', find next applicable mask after m_old */
1199 
1200  for (++m_old; !(h & m_old); m_old <<= 1)
1201  ;
1202 
1203  m_old = (m_old << 1) - 1; /* get full mask from a bit */
1204 
1205  assert((m_old & (m_old + 1)) == 0 && m_old <= m);
1206 
1207  /* check whether it is rehashing/ed */
1208  bucket *b = get_bucket(h & m_old);
1209  return b->is_rehashed(std::memory_order_acquire);
1210  }
1211 
1212  return false;
1213  }
1214 
1219  template <typename Node, typename... Args>
1220  void
1221  insert_new_node_internal(bucket *b,
1222  detail::persistent_pool_ptr<Node> &new_node,
1223  Args &&... args)
1224  {
1225  assert(pmemobj_tx_stage() == TX_STAGE_WORK);
1226 
1227  new_node = pmem::obj::make_persistent<Node>(
1228  b->node_list, std::forward<Args>(args)...);
1229  b->node_list = new_node; /* bucket is locked */
1230  }
1231 
1236  template <typename Node, typename... Args>
1237  size_type
1238  insert_new_node(bucket *b, detail::persistent_pool_ptr<Node> &new_node,
1239  Args &&... args)
1240  {
1241  pool_base pop = get_pool_base();
1242 
1243  /*
1244  * This is only true when called from singlethreaded methods
1245  * like swap() or operator=. In that case it's safe to directly
1246  * modify on_init_size.
1247  */
1248  if (pmemobj_tx_stage() == TX_STAGE_WORK) {
1249  insert_new_node_internal(b, new_node,
1250  std::forward<Args>(args)...);
1251  this->on_init_size++;
1252  } else {
1253  auto &size_diff = thread_size_diff();
1254 
1255  pmem::obj::transaction::run(pop, [&] {
1256  insert_new_node_internal(
1257  b, new_node,
1258  std::forward<Args>(args)...);
1259  ++size_diff;
1260  });
1261  }
1262 
1263  /* Increment volatile size */
1264  return ++(this->my_size);
1265  }
1266 
1271  bool
1272  check_growth(hashcode_type m, size_type sz)
1273  {
1274  if (sz >= m) {
1275  segment_index_t new_seg =
1276  static_cast<segment_index_t>(detail::Log2(
1277  m +
1278  1)); /* optimized segment_index_of */
1279 
1280  assert(segment_facade_t(my_table, new_seg - 1)
1281  .is_valid());
1282 
1283  std::unique_lock<segment_enable_mutex_t> lock(
1284  my_segment_enable_mutex, std::try_to_lock);
1285 
1286  if (lock) {
1287  if (mask().load(std::memory_order_relaxed) ==
1288  m) {
1289  /* Otherwise, other thread enable this
1290  * segment */
1291  enable_segment(new_seg);
1292 
1293  return true;
1294  }
1295  }
1296  }
1297 
1298  return false;
1299  }
1300 
1304  void
1305  reserve(size_type buckets)
1306  {
1307  if (buckets == 0)
1308  return;
1309 
1310  --buckets;
1311 
1312  bool is_initial = this->size() == 0;
1313 
1314  for (size_type m = mask(); buckets > m; m = mask())
1315  enable_segment(
1316  segment_traits_t::segment_index_of(m + 1),
1317  is_initial);
1318  }
1319 
1324  void
1325  internal_swap(hash_map_base<Key, T, mutex_t, scoped_t> &table)
1326  {
1327  pool_base p = get_pool_base();
1328  {
1329  transaction::manual tx(p);
1330 
1331  this->my_pool_uuid.swap(table.my_pool_uuid);
1332 
1333  /*
1334  * As internal_swap can only be called
1335  * from one thread, and there can be an outer
1336  * transaction we must make sure that mask and size
1337  * changes are transactional
1338  */
1339  transaction::snapshot((size_t *)&this->my_mask);
1340  transaction::snapshot((size_t *)&this->my_size);
1341 
1342  this->mask() = table.mask().exchange(
1343  this->mask(), std::memory_order_relaxed);
1344 
1345  this->my_size = table.my_size.exchange(
1346  this->my_size, std::memory_order_relaxed);
1347 
1348  /* Swap consistent size */
1349  std::swap(this->tls_ptr, table.tls_ptr);
1350 
1351  for (size_type i = 0; i < embedded_buckets; ++i)
1352  this->my_embedded_segment[i].node_list.swap(
1353  table.my_embedded_segment[i].node_list);
1354 
1355  for (size_type i = segment_traits_t::embedded_segments;
1356  i < block_table_size; ++i)
1357  this->my_table[i].swap(table.my_table[i]);
1358 
1360  }
1361  }
1362 
1367  pool_base
1368  get_pool_base()
1369  {
1370  PMEMobjpool *pop =
1371  pmemobj_pool_by_oid(PMEMoid{my_pool_uuid, 0});
1372 
1373  return pool_base(pop);
1374  }
1375 }; /* End of class hash_map_base */
1376 
1382 template <typename Container, bool is_const>
1383 class hash_map_iterator {
1384 public:
1385  using iterator_category = std::forward_iterator_tag;
1386  using difference_type = ptrdiff_t;
1387  using map_type = Container;
1388  using value_type = typename map_type::value_type;
1389  using node = typename map_type::node;
1390  using bucket = typename map_type::bucket;
1391  using map_ptr = typename std::conditional<is_const, const map_type *,
1392  map_type *>::type;
1393  using reference =
1394  typename std::conditional<is_const,
1395  typename map_type::const_reference,
1396  typename map_type::reference>::type;
1397  using pointer =
1398  typename std::conditional<is_const,
1399  typename map_type::const_pointer,
1400  typename map_type::pointer>::type;
1401 
1402  template <typename C, bool M, bool U>
1403  friend bool operator==(const hash_map_iterator<C, M> &i,
1404  const hash_map_iterator<C, U> &j);
1405 
1406  template <typename C, bool M, bool U>
1407  friend bool operator!=(const hash_map_iterator<C, M> &i,
1408  const hash_map_iterator<C, U> &j);
1409 
1410  friend class hash_map_iterator<map_type, true>;
1411 
1412 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
1413 private:
1414  template <typename Key, typename T, typename Hash, typename KeyEqual,
1415  typename MutexType, typename ScopedLockType>
1416  friend class ::pmem::obj::concurrent_hash_map;
1417 #else
1418 public: /* workaround */
1419 #endif
1420  hash_map_iterator(map_ptr map, size_t index)
1421  : my_map(map), my_index(index), my_bucket(nullptr), my_node(nullptr)
1422  {
1423  if (my_index <= my_map->mask()) {
1424  bucket_accessor acc(my_map, my_index);
1425  my_bucket = acc.get();
1426  my_node = static_cast<node *>(
1427  my_bucket->node_list.get(my_map->my_pool_uuid));
1428 
1429  if (!my_node) {
1430  advance_to_next_bucket();
1431  }
1432  }
1433  }
1434 
1435 public:
1437  hash_map_iterator() = default;
1438 
1440  hash_map_iterator(const hash_map_iterator &other)
1441  : my_map(other.my_map),
1442  my_index(other.my_index),
1443  my_bucket(other.my_bucket),
1444  my_node(other.my_node)
1445  {
1446  }
1447 
1449  template <typename U = void,
1450  typename = typename std::enable_if<is_const, U>::type>
1451  hash_map_iterator(const hash_map_iterator<map_type, false> &other)
1452  : my_map(other.my_map),
1453  my_index(other.my_index),
1454  my_bucket(other.my_bucket),
1455  my_node(other.my_node)
1456  {
1457  }
1458 
1459  hash_map_iterator &operator=(const hash_map_iterator &it) = default;
1460 
1462  reference operator*() const
1463  {
1464  assert(my_node);
1465  return my_node->item;
1466  }
1467 
1469  pointer operator->() const
1470  {
1471  return &operator*();
1472  }
1473 
1475  hash_map_iterator &
1476  operator++()
1477  {
1478  my_node = static_cast<node *>(
1479  my_node->next.get((my_map->my_pool_uuid)));
1480 
1481  if (!my_node)
1482  advance_to_next_bucket();
1483 
1484  return *this;
1485  }
1486 
1488  hash_map_iterator
1489  operator++(int)
1490  {
1491  hash_map_iterator old(*this);
1492  operator++();
1493  return old;
1494  }
1495 
1496 private:
1498  map_ptr my_map = nullptr;
1499 
1501  size_t my_index = 0;
1502 
1504  bucket *my_bucket = nullptr;
1505 
1507  node *my_node = nullptr;
1508 
1509  class bucket_accessor {
1510  public:
1511  bucket_accessor(map_ptr m, size_t index)
1512  {
1513  my_bucket = m->get_bucket(index);
1514  }
1515 
1516  bucket *
1517  get() const
1518  {
1519  return my_bucket;
1520  }
1521 
1522  private:
1523  bucket *my_bucket;
1524  };
1525 
1526  void
1527  advance_to_next_bucket()
1528  {
1529  size_t k = my_index + 1;
1530 
1531  assert(my_bucket);
1532 
1533  while (k <= my_map->mask()) {
1534  bucket_accessor acc(my_map, k);
1535  my_bucket = acc.get();
1536 
1537  if (my_bucket->node_list) {
1538  my_node = static_cast<node *>(
1539  my_bucket->node_list.get(
1540  my_map->my_pool_uuid));
1541 
1542  my_index = k;
1543 
1544  return;
1545  }
1546 
1547  ++k;
1548  }
1549 
1550  my_bucket = 0;
1551  my_node = 0;
1552  my_index = k;
1553  }
1554 };
1555 
1556 template <typename Container, bool M, bool U>
1557 bool
1558 operator==(const hash_map_iterator<Container, M> &i,
1559  const hash_map_iterator<Container, U> &j)
1560 {
1561  return i.my_node == j.my_node && i.my_map == j.my_map;
1562 }
1563 
1564 template <typename Container, bool M, bool U>
1565 bool
1566 operator!=(const hash_map_iterator<Container, M> &i,
1567  const hash_map_iterator<Container, U> &j)
1568 {
1569  return i.my_node != j.my_node || i.my_map != j.my_map;
1570 }
1571 } /* namespace concurrent_hash_map_internal */
1620 template <typename Key, typename T, typename Hash, typename KeyEqual,
1621  typename MutexType, typename ScopedLockType>
1623  : protected concurrent_hash_map_internal::hash_map_base<Key, T, MutexType,
1624  ScopedLockType> {
1625  template <typename Container, bool is_const>
1626  friend class concurrent_hash_map_internal::hash_map_iterator;
1627 
1628 public:
1629  using size_type = typename concurrent_hash_map_internal::hash_map_base<
1630  Key, T, MutexType, ScopedLockType>::size_type;
1631  using hashcode_type =
1632  typename concurrent_hash_map_internal::hash_map_base<
1633  Key, T, MutexType, ScopedLockType>::hashcode_type;
1634  using key_type = Key;
1635  using mapped_type = T;
1636  using value_type = typename concurrent_hash_map_internal::hash_map_base<
1637  Key, T, MutexType, ScopedLockType>::node::value_type;
1638  using difference_type = ptrdiff_t;
1639  using pointer = value_type *;
1640  using const_pointer = const value_type *;
1641  using reference = value_type &;
1642  using const_reference = const value_type &;
1643  using iterator = concurrent_hash_map_internal::hash_map_iterator<
1644  concurrent_hash_map, false>;
1645  using const_iterator = concurrent_hash_map_internal::hash_map_iterator<
1646  concurrent_hash_map, true>;
1647  using hasher = Hash;
1648  using key_equal = typename concurrent_hash_map_internal::key_equal_type<
1649  Hash, KeyEqual>::type;
1650 
1651 protected:
1652  using mutex_t = MutexType;
1653  using scoped_t = ScopedLockType;
1654  /*
1655  * Explicitly use methods and types from template base class
1656  */
1657  using hash_map_base =
1658  concurrent_hash_map_internal::hash_map_base<Key, T, mutex_t,
1659  scoped_t>;
1660  using hash_map_base::calculate_mask;
1661  using hash_map_base::check_growth;
1662  using hash_map_base::check_mask_race;
1663  using hash_map_base::embedded_buckets;
1664  using hash_map_base::FEATURE_CONSISTENT_SIZE;
1665  using hash_map_base::get_bucket;
1666  using hash_map_base::get_pool_base;
1667  using hash_map_base::header_features;
1668  using hash_map_base::insert_new_node;
1669  using hash_map_base::internal_swap;
1670  using hash_map_base::layout_features;
1671  using hash_map_base::mask;
1672  using hash_map_base::reserve;
1673  using tls_t = typename hash_map_base::tls_t;
1674  using node = typename hash_map_base::node;
1675  using node_mutex_t = typename node::mutex_t;
1676  using node_ptr_t = typename hash_map_base::node_ptr_t;
1677  using bucket = typename hash_map_base::bucket;
1678  using bucket_lock_type = typename bucket::scoped_t;
1679  using segment_index_t = typename hash_map_base::segment_index_t;
1680  using segment_traits_t = typename hash_map_base::segment_traits_t;
1681  using segment_facade_t = typename hash_map_base::segment_facade_t;
1682  using scoped_lock_traits_type =
1683  concurrent_hash_map_internal::scoped_lock_traits<scoped_t>;
1684 
1685  friend class const_accessor;
1686  using persistent_node_ptr_t = detail::persistent_pool_ptr<node>;
1687 
1688  void
1689  delete_node(const node_ptr_t &n)
1690  {
1691  delete_persistent<node>(
1692  detail::static_persistent_pool_pointer_cast<node>(n)
1693  .get_persistent_ptr(this->my_pool_uuid));
1694  }
1695 
1696  template <typename K>
1697  persistent_node_ptr_t
1698  search_bucket(const K &key, bucket *b) const
1699  {
1700  assert(b->is_rehashed(std::memory_order_relaxed));
1701 
1702  persistent_node_ptr_t n =
1703  detail::static_persistent_pool_pointer_cast<node>(
1704  b->node_list);
1705 
1706  while (n &&
1707  !key_equal{}(key,
1708  n.get(this->my_pool_uuid)->item.first)) {
1709  n = detail::static_persistent_pool_pointer_cast<node>(
1710  n.get(this->my_pool_uuid)->next);
1711  }
1712 
1713  return n;
1714  }
1715 
1720  class bucket_accessor : public bucket_lock_type {
1721  bucket *my_b;
1722 
1723  public:
1724  bucket_accessor(bucket_accessor &&b) noexcept : my_b(b.my_b)
1725  {
1726  bucket_lock_type::mutex = b.bucket_lock_type::mutex;
1727  bucket_lock_type::is_writer =
1728  b.bucket_lock_type::is_writer;
1729  b.my_b = nullptr;
1730  b.bucket_lock_type::mutex = nullptr;
1731  b.bucket_lock_type::is_writer = false;
1732  }
1733 
1735  const hashcode_type h, bool writer = false)
1736  {
1737  acquire(base, h, writer);
1738  }
1739 
1740  bucket_accessor(const bucket_accessor &other) = delete;
1741 
1742  bucket_accessor &
1743  operator=(const bucket_accessor &other) = delete;
1744 
1749  inline void
1750  acquire(concurrent_hash_map *base, const hashcode_type h,
1751  bool writer = false)
1752  {
1753  my_b = base->get_bucket(h);
1754 
1755  if (my_b->is_rehashed(std::memory_order_acquire) ==
1756  false &&
1757  bucket_lock_type::try_acquire(this->my_b->mutex,
1758  /*write=*/true)) {
1759  if (my_b->is_rehashed(
1760  std::memory_order_relaxed) ==
1761  false) {
1762  /* recursive rehashing */
1763  base->rehash_bucket<false>(my_b, h);
1764  }
1765  } else {
1766  bucket_lock_type::acquire(my_b->mutex, writer);
1767  }
1768 
1769  assert(my_b->is_rehashed(std::memory_order_relaxed));
1770  }
1771 
1775  bool
1776  is_writer() const
1777  {
1778  return bucket_lock_type::is_writer;
1779  }
1780 
1785  bucket *
1786  get() const
1787  {
1788  return my_b;
1789  }
1790 
1795  bucket *operator->() const
1796  {
1797  return this->get();
1798  }
1799  };
1800 
1805  bucket *my_b;
1806 
1807  public:
1809  const hashcode_type h,
1810  bool writer = false)
1811  {
1812  acquire(base, h, writer);
1813  }
1814 
1815  /*
1816  * Find a bucket by masked hashcode, optionally rehash
1817  */
1818  inline void
1819  acquire(concurrent_hash_map *base, const hashcode_type h,
1820  bool writer = false)
1821  {
1822  my_b = base->get_bucket(h);
1823 
1824  if (my_b->is_rehashed(std::memory_order_relaxed) ==
1825  false) {
1826  /* recursive rehashing */
1827  base->rehash_bucket<true>(my_b, h);
1828  }
1829 
1830  assert(my_b->is_rehashed(std::memory_order_relaxed));
1831  }
1832 
1839  bool
1840  is_writer() const
1841  {
1842  return true;
1843  }
1844 
1849  bucket *
1850  get() const
1851  {
1852  return my_b;
1853  }
1854 
1859  bucket *operator->() const
1860  {
1861  return this->get();
1862  }
1863  };
1864 
1865  hashcode_type
1866  get_hash_code(node_ptr_t &n)
1867  {
1868  return hasher{}(
1869  detail::static_persistent_pool_pointer_cast<node>(n)(
1870  this->my_pool_uuid)
1871  ->item.first);
1872  }
1873 
1874  template <bool serial>
1875  void
1876  rehash_bucket(bucket *b_new, const hashcode_type h)
1877  {
1878  using accessor_type = typename std::conditional<
1879  serial, serial_bucket_accessor, bucket_accessor>::type;
1880 
1881  using scoped_lock_traits_type =
1882  concurrent_hash_map_internal::scoped_lock_traits<
1883  accessor_type>;
1884 
1885  /* First two bucket should be always rehashed */
1886  assert(h > 1);
1887 
1888  pool_base pop = get_pool_base();
1889  node_ptr_t *p_new = &(b_new->node_list);
1890 
1891  /* This condition is only true when there was a failure just
1892  * before setting rehashed flag */
1893  if (*p_new != nullptr) {
1894  assert(!b_new->is_rehashed(std::memory_order_relaxed));
1895 
1896  b_new->set_rehashed(std::memory_order_relaxed);
1897  pop.persist(b_new->rehashed);
1898 
1899  return;
1900  }
1901 
1902  /* get parent mask from the topmost bit */
1903  hashcode_type mask = (1u << detail::Log2(h)) - 1;
1904  assert((h & mask) < h);
1905  accessor_type b_old(
1906  this, h & mask,
1907  scoped_lock_traits_type::initial_rw_state(true));
1908 
1909  pmem::obj::transaction::run(pop, [&] {
1910  /* get full mask for new bucket */
1911  mask = (mask << 1) | 1;
1912  assert((mask & (mask + 1)) == 0 && (h & mask) == h);
1913 
1914  restart:
1915  for (node_ptr_t *p_old = &(b_old->node_list),
1916  n = *p_old;
1917  n; n = *p_old) {
1918  hashcode_type c = get_hash_code(n);
1919 #ifndef NDEBUG
1920  hashcode_type bmask = h & (mask >> 1);
1921 
1922  bmask = bmask == 0
1923  ? 1 /* minimal mask of parent bucket */
1924  : (1u << (detail::Log2(bmask) + 1)) - 1;
1925 
1926  assert((c & bmask) == (h & bmask));
1927 #endif
1928 
1929  if ((c & mask) == h) {
1930  if (!b_old.is_writer() &&
1931  !scoped_lock_traits_type::
1932  upgrade_to_writer(b_old)) {
1933  goto restart;
1934  /* node ptr can be invalid due
1935  * to concurrent erase */
1936  }
1937 
1938  /* Add to new b_new */
1939  *p_new = n;
1940 
1941  /* exclude from b_old */
1942  *p_old = n(this->my_pool_uuid)->next;
1943 
1944  p_new = &(n(this->my_pool_uuid)->next);
1945  } else {
1946  /* iterate to next item */
1947  p_old = &(n(this->my_pool_uuid)->next);
1948  }
1949  }
1950 
1951  *p_new = nullptr;
1952  });
1953 
1954  /* mark rehashed */
1955  b_new->set_rehashed(std::memory_order_release);
1956  pop.persist(b_new->rehashed);
1957  }
1958 
1959  void
1960  check_incompat_features()
1961  {
1962  if (layout_features.incompat != header_features().incompat)
1963  throw pmem::layout_error(
1964  "Incompat flags mismatch, for more details go to: https://pmem.io/pmdk/cpp_obj/ \n");
1965 
1966  if ((layout_features.compat & FEATURE_CONSISTENT_SIZE) &&
1967  this->value_size != sizeof(value_type))
1968  throw pmem::layout_error(
1969  "Size of value_type is different than the one stored in the pool \n");
1970  }
1971 
1972 public:
1973  class accessor;
1978  : protected node::scoped_t /*which derived from no_copy*/ {
1979  friend class concurrent_hash_map<Key, T, Hash, KeyEqual,
1980  mutex_t, scoped_t>;
1981  friend class accessor;
1983  using node::scoped_t::try_acquire;
1984 
1985  public:
1989  using value_type =
1990  const typename concurrent_hash_map::value_type;
1991 
1996  bool
1997  empty() const
1998  {
1999  return !my_node;
2000  }
2001 
2008  void
2010  {
2011  concurrent_hash_map_internal::check_outside_tx();
2012 
2013  if (my_node) {
2014  node::scoped_t::release();
2015  my_node = 0;
2016  }
2017  }
2018 
2022  const_reference operator*() const
2023  {
2024  assert(my_node);
2025 
2026  return my_node->item;
2027  }
2028 
2032  const_pointer operator->() const
2033  {
2034  return &operator*();
2035  }
2036 
2042  const_accessor() : my_node(OID_NULL), my_hash()
2043  {
2044  concurrent_hash_map_internal::check_outside_tx();
2045  }
2046 
2051  {
2052  my_node = OID_NULL; // scoped lock's release() is called
2053  // in its destructor
2054  }
2055 
2056  protected:
2057  node_ptr_t my_node;
2058 
2059  hashcode_type my_hash;
2060  };
2061 
2066  class accessor : public const_accessor {
2067  public:
2069  using value_type = typename concurrent_hash_map::value_type;
2070 
2072  reference operator*() const
2073  {
2074  assert(this->my_node);
2075 
2076  return this->my_node->item;
2077  }
2078 
2080  pointer operator->() const
2081  {
2082  return &operator*();
2083  }
2084  };
2085 
2089  concurrent_hash_map() : hash_map_base()
2090  {
2092  }
2093 
2098  concurrent_hash_map(size_type n) : hash_map_base()
2099  {
2101 
2102  reserve(n);
2103  }
2104 
2108  concurrent_hash_map(const concurrent_hash_map &table) : hash_map_base()
2109  {
2111 
2112  reserve(table.size());
2113 
2114  internal_copy(table);
2115  }
2116 
2120  concurrent_hash_map(concurrent_hash_map &&table) : hash_map_base()
2121  {
2123 
2124  swap(table);
2125  }
2126 
2130  template <typename I>
2131  concurrent_hash_map(I first, I last)
2132  {
2134 
2135  reserve(static_cast<size_type>(std::distance(first, last)));
2136 
2137  internal_copy(first, last);
2138  }
2139 
2143  concurrent_hash_map(std::initializer_list<value_type> il)
2144  {
2146 
2147  reserve(il.size());
2148 
2149  internal_copy(il.begin(), il.end());
2150  }
2151 
2160  void
2162  {
2163  check_incompat_features();
2164 
2165  calculate_mask();
2166 
2167  /*
2168  * Handle case where hash_map was created without
2169  * FEATURE_CONSISTENT_SIZE.
2170  */
2171  if (!(layout_features.compat & FEATURE_CONSISTENT_SIZE)) {
2172  auto actual_size =
2173  std::distance(this->begin(), this->end());
2174  assert(actual_size >= 0);
2175 
2176  this->my_size = static_cast<size_t>(actual_size);
2177 
2178  auto pop = get_pool_base();
2179  transaction::run(pop, [&] {
2180  this->tls_ptr = make_persistent<tls_t>();
2181  this->on_init_size =
2182  static_cast<size_t>(actual_size);
2183  this->value_size = sizeof(value_type);
2184 
2185  layout_features.compat |=
2186  FEATURE_CONSISTENT_SIZE;
2187  });
2188  } else {
2189  assert(this->tls_ptr != nullptr);
2190  this->tls_restore();
2191  }
2192 
2193  assert(this->size() ==
2194  size_type(std::distance(this->begin(), this->end())));
2195  }
2196 
2197  [[deprecated(
2198  "runtime_initialize(bool) is now deprecated, use runtime_initialize(void)")]] void
2199  runtime_initialize(bool graceful_shutdown)
2200  {
2201  check_incompat_features();
2202 
2203  calculate_mask();
2204 
2205  if (!graceful_shutdown) {
2206  auto actual_size =
2207  std::distance(this->begin(), this->end());
2208  assert(actual_size >= 0);
2209  this->my_size = static_cast<size_type>(actual_size);
2210  } else {
2211  assert(this->size() ==
2212  size_type(std::distance(this->begin(),
2213  this->end())));
2214  }
2215  }
2216 
2228  concurrent_hash_map &
2230  {
2231  if (this != &table) {
2232  clear();
2233  internal_copy(table);
2234  }
2235 
2236  return *this;
2237  }
2238 
2251  operator=(std::initializer_list<value_type> il)
2252  {
2253  clear();
2254 
2255  reserve(il.size());
2256 
2257  internal_copy(il.begin(), il.end());
2258 
2259  return *this;
2260  }
2261 
2270  void rehash(size_type n = 0);
2271 
2278  void clear();
2279 
2292  void
2294  {
2295  if (!this->tls_ptr)
2296  return;
2297 
2298  auto pop = get_pool_base();
2299 
2300  transaction::run(pop, [&] {
2301  clear();
2302  this->free_tls();
2303  });
2304  }
2305 
2315  {
2316  try {
2317  free_data();
2318  } catch (...) {
2319  std::terminate();
2320  }
2321  }
2322 
2323  //------------------------------------------------------------------------
2324  // STL support - not thread-safe methods
2325  //------------------------------------------------------------------------
2326 
2333  iterator
2335  {
2336  return iterator(this, 0);
2337  }
2338 
2343  iterator
2345  {
2346  return iterator(this, mask() + 1);
2347  }
2348 
2353  const_iterator
2354  begin() const
2355  {
2356  return const_iterator(this, 0);
2357  }
2358 
2363  const_iterator
2364  end() const
2365  {
2366  return const_iterator(this, mask() + 1);
2367  }
2368 
2372  size_type
2373  size() const
2374  {
2375  return hash_map_base::size();
2376  }
2377 
2381  bool
2382  empty() const
2383  {
2384  return this->size() == 0;
2385  }
2386 
2390  size_type
2391  max_size() const
2392  {
2393  return (~size_type(0)) / sizeof(node);
2394  }
2395 
2399  size_type
2401  {
2402  return mask() + 1;
2403  }
2404 
2408  void swap(concurrent_hash_map &table);
2409 
2410  //------------------------------------------------------------------------
2411  // concurrent map operations
2412  //------------------------------------------------------------------------
2413 
2419  size_type
2420  count(const Key &key) const
2421  {
2422  concurrent_hash_map_internal::check_outside_tx();
2423 
2424  return const_cast<concurrent_hash_map *>(this)->internal_find(
2425  key, nullptr, false);
2426  }
2427 
2439  template <typename K,
2440  typename = typename std::enable_if<
2441  concurrent_hash_map_internal::
2442  has_transparent_key_equal<hasher>::value,
2443  K>::type>
2444  size_type
2445  count(const K &key) const
2446  {
2447  concurrent_hash_map_internal::check_outside_tx();
2448 
2449  return const_cast<concurrent_hash_map *>(this)->internal_find(
2450  key, nullptr, false);
2451  }
2452 
2459  bool
2460  find(const_accessor &result, const Key &key) const
2461  {
2462  concurrent_hash_map_internal::check_outside_tx();
2463 
2464  result.release();
2465 
2466  return const_cast<concurrent_hash_map *>(this)->internal_find(
2467  key, &result, false);
2468  }
2469 
2483  template <typename K,
2484  typename = typename std::enable_if<
2485  concurrent_hash_map_internal::
2486  has_transparent_key_equal<hasher>::value,
2487  K>::type>
2488  bool
2489  find(const_accessor &result, const K &key) const
2490  {
2491  concurrent_hash_map_internal::check_outside_tx();
2492 
2493  result.release();
2494 
2495  return const_cast<concurrent_hash_map *>(this)->internal_find(
2496  key, &result, false);
2497  }
2498 
2505  bool
2506  find(accessor &result, const Key &key)
2507  {
2508  concurrent_hash_map_internal::check_outside_tx();
2509 
2510  result.release();
2511 
2512  return internal_find(key, &result, true);
2513  }
2514 
2528  template <typename K,
2529  typename = typename std::enable_if<
2530  concurrent_hash_map_internal::
2531  has_transparent_key_equal<hasher>::value,
2532  K>::type>
2533  bool
2534  find(accessor &result, const K &key)
2535  {
2536  concurrent_hash_map_internal::check_outside_tx();
2537 
2538  result.release();
2539 
2540  return internal_find(key, &result, true);
2541  }
2549  bool
2550  insert(const_accessor &result, const Key &key)
2551  {
2552  concurrent_hash_map_internal::check_outside_tx();
2553 
2554  result.release();
2555 
2556  return internal_insert(key, &result, false, key);
2557  }
2558 
2566  bool
2567  insert(accessor &result, const Key &key)
2568  {
2569  concurrent_hash_map_internal::check_outside_tx();
2570 
2571  result.release();
2572 
2573  return internal_insert(key, &result, true, key);
2574  }
2575 
2583  bool
2584  insert(const_accessor &result, const value_type &value)
2585  {
2586  concurrent_hash_map_internal::check_outside_tx();
2587 
2588  result.release();
2589 
2590  return internal_insert(value.first, &result, false, value);
2591  }
2592 
2600  bool
2601  insert(accessor &result, const value_type &value)
2602  {
2603  concurrent_hash_map_internal::check_outside_tx();
2604 
2605  result.release();
2606 
2607  return internal_insert(value.first, &result, true, value);
2608  }
2609 
2616  bool
2617  insert(const value_type &value)
2618  {
2619  concurrent_hash_map_internal::check_outside_tx();
2620 
2621  return internal_insert(value.first, nullptr, false, value);
2622  }
2623 
2631  bool
2632  insert(const_accessor &result, value_type &&value)
2633  {
2634  concurrent_hash_map_internal::check_outside_tx();
2635 
2636  result.release();
2637 
2638  return internal_insert(value.first, &result, false,
2639  std::move(value));
2640  }
2641 
2649  bool
2650  insert(accessor &result, value_type &&value)
2651  {
2652  concurrent_hash_map_internal::check_outside_tx();
2653 
2654  result.release();
2655 
2656  return internal_insert(value.first, &result, true,
2657  std::move(value));
2658  }
2659 
2666  bool
2667  insert(value_type &&value)
2668  {
2669  concurrent_hash_map_internal::check_outside_tx();
2670 
2671  return internal_insert(value.first, nullptr, false,
2672  std::move(value));
2673  }
2674 
2680  template <typename I>
2681  void
2682  insert(I first, I last)
2683  {
2684  concurrent_hash_map_internal::check_outside_tx();
2685 
2686  for (; first != last; ++first)
2687  insert(*first);
2688  }
2689 
2695  void
2696  insert(std::initializer_list<value_type> il)
2697  {
2698  concurrent_hash_map_internal::check_outside_tx();
2699 
2700  insert(il.begin(), il.end());
2701  }
2702 
2711  template <typename M>
2712  bool
2713  insert_or_assign(const key_type &key, M &&obj)
2714  {
2715  concurrent_hash_map_internal::check_outside_tx();
2716 
2717  accessor acc;
2718  auto result = internal_insert(key, &acc, true, key,
2719  std::forward<M>(obj));
2720 
2721  if (!result) {
2722  pool_base pop = get_pool_base();
2724  acc->second = std::forward<M>(obj);
2726  }
2727 
2728  return result;
2729  }
2730 
2739  template <typename M>
2740  bool
2741  insert_or_assign(key_type &&key, M &&obj)
2742  {
2743  concurrent_hash_map_internal::check_outside_tx();
2744 
2745  accessor acc;
2746  auto result = internal_insert(key, &acc, true, std::move(key),
2747  std::forward<M>(obj));
2748 
2749  if (!result) {
2750  pool_base pop = get_pool_base();
2752  acc->second = std::forward<M>(obj);
2754  }
2755 
2756  return result;
2757  }
2758 
2767  template <
2768  typename K, typename M,
2769  typename = typename std::enable_if<
2770  concurrent_hash_map_internal::has_transparent_key_equal<
2771  hasher>::value &&
2772  std::is_constructible<key_type, K>::value,
2773  K>::type>
2774  bool
2775  insert_or_assign(K &&key, M &&obj)
2776  {
2777  concurrent_hash_map_internal::check_outside_tx();
2778 
2779  accessor acc;
2780  auto result =
2781  internal_insert(key, &acc, true, std::forward<K>(key),
2782  std::forward<M>(obj));
2783 
2784  if (!result) {
2785  pool_base pop = get_pool_base();
2787  acc->second = std::forward<M>(obj);
2789  }
2790 
2791  return result;
2792  }
2793 
2802  bool
2803  erase(const Key &key)
2804  {
2805  concurrent_hash_map_internal::check_outside_tx();
2806 
2807  return internal_erase(key);
2808  }
2809 
2828  pobj_defrag_result
2829  defragment(double start_percent = 0, double amount_percent = 100)
2830  {
2831  double end_percent = start_percent + amount_percent;
2832  if (start_percent < 0 || start_percent >= 100 ||
2833  end_percent < 0 || end_percent > 100 ||
2834  start_percent >= end_percent) {
2835  throw std::range_error("incorrect range");
2836  }
2837 
2838  size_t max_index = mask().load(std::memory_order_acquire);
2839  size_t start_index =
2840  static_cast<size_t>((start_percent * max_index) / 100);
2841  size_t end_index =
2842  static_cast<size_t>((end_percent * max_index) / 100);
2843 
2844  /* Make sure we do not use too big index, even in case of
2845  * rounding errors. */
2846  end_index = (std::min)(end_index, max_index);
2847 
2848 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
2849  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
2850 #endif
2851 
2852  /* Create defrag object for elements in the current pool */
2853  pmem::obj::defrag my_defrag(this->get_pool_base());
2854  mutex_vector mv;
2855 
2856  /*
2857  * Locks are taken in the backward order to avoid deadlocks
2858  * with the rehashing of buckets.
2859  *
2860  * We do '+ 1' and '- 1' to handle the 'i == 0' case.
2861  */
2862  for (size_t i = end_index + 1; i >= start_index + 1; i--) {
2863  /*
2864  * All locks will be unlocked automatically
2865  * in the destructor of 'mv'.
2866  */
2867  bucket *b = mv.push_and_try_lock(this, i - 1);
2868  if (b == nullptr)
2869  continue;
2870 
2871  defrag_save_nodes(b, my_defrag);
2872  }
2873 
2874  return my_defrag.run();
2875  }
2876 
2891  template <typename K,
2892  typename = typename std::enable_if<
2893  concurrent_hash_map_internal::
2894  has_transparent_key_equal<hasher>::value,
2895  K>::type>
2896  bool
2897  erase(const K &key)
2898  {
2899  concurrent_hash_map_internal::check_outside_tx();
2900 
2901  return internal_erase(key);
2902  }
2903 
2904 protected:
2905  /*
2906  * Try to acquire the mutex for read or write.
2907  *
2908  * If acquiring succeeds returns true, otherwise retries for few times.
2909  * If acquiring fails after all attempts returns false.
2910  */
2911  bool try_acquire_item(const_accessor *result, node_mutex_t &mutex,
2912  bool write);
2913 
2919  public:
2920  using mutex_t = MutexType;
2921 
2923  bucket *
2924  push_and_try_lock(concurrent_hash_map *base, hashcode_type h)
2925  {
2926  vec.emplace_back(base, h, true /*writer*/);
2927  bucket *b = vec.back().get();
2928 
2929  auto node_ptr = static_cast<node *>(
2930  b->node_list.get(base->my_pool_uuid));
2931 
2932  while (node_ptr) {
2933  const_accessor ca;
2934  if (!base->try_acquire_item(&ca,
2935  node_ptr->mutex,
2936  /*write=*/true)) {
2937  vec.pop_back();
2938  return nullptr;
2939  }
2940 
2941  node_ptr =
2942  static_cast<node *>(node_ptr->next.get(
2943  (base->my_pool_uuid)));
2944  }
2945 
2946  return b;
2947  }
2948 
2949  private:
2950  std::vector<bucket_accessor> vec;
2951  };
2952 
2953  template <typename K>
2954  bool internal_find(const K &key, const_accessor *result, bool write);
2955 
2956  template <typename K, typename... Args>
2957  bool internal_insert(const K &key, const_accessor *result, bool write,
2958  Args &&... args);
2959 
2960  /* Obtain pointer to node and lock bucket */
2961  template <bool Bucket_rw_lock, typename K>
2962  persistent_node_ptr_t
2963  get_node(const K &key, bucket_accessor &b)
2964  {
2965  /* find a node */
2966  auto n = search_bucket(key, b.get());
2967 
2968  if (!n) {
2969  if (Bucket_rw_lock && !b.is_writer() &&
2970  !scoped_lock_traits_type::upgrade_to_writer(b)) {
2971  /* Rerun search_list, in case another
2972  * thread inserted the item during the
2973  * upgrade. */
2974  n = search_bucket(key, b.get());
2975  if (n) {
2976  /* unfortunately, it did */
2977  scoped_lock_traits_type::
2978  downgrade_to_reader(b);
2979  return n;
2980  }
2981  }
2982  }
2983 
2984  return n;
2985  }
2986 
2987  template <typename K>
2988  bool internal_erase(const K &key);
2989 
2990  void clear_segment(segment_index_t s);
2991 
2995  void internal_copy(const concurrent_hash_map &source);
2996 
2997  template <typename I>
2998  void internal_copy(I first, I last);
2999 
3004  void
3006  {
3007  auto node_ptr = static_cast<node *>(
3008  b->node_list.get(this->my_pool_uuid));
3009 
3010  while (node_ptr) {
3011  /*
3012  * We do not perform the defragmentation
3013  * on node pointers, because nodes
3014  * always have the same size.
3015  */
3016  defrag.add(node_ptr->item.first);
3017  defrag.add(node_ptr->item.second);
3018 
3019  node_ptr = static_cast<node *>(
3020  node_ptr->next.get((this->my_pool_uuid)));
3021  }
3022  }
3023 }; // class concurrent_hash_map
3024 
3025 template <typename Key, typename T, typename Hash, typename KeyEqual,
3026  typename MutexType, typename ScopedLockType>
3027 bool
3028 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3029  ScopedLockType>::try_acquire_item(const_accessor *result,
3030  node_mutex_t &mutex,
3031  bool write)
3032 {
3033  /* acquire the item */
3034  if (!result->try_acquire(mutex, write)) {
3035  for (detail::atomic_backoff backoff(true);;) {
3036  if (result->try_acquire(mutex, write))
3037  break;
3038 
3039  if (!backoff.bounded_pause())
3040  return false;
3041  }
3042  }
3043 
3044  return true;
3045 }
3046 
3047 template <typename Key, typename T, typename Hash, typename KeyEqual,
3048  typename MutexType, typename ScopedLockType>
3049 template <typename K>
3050 bool
3051 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3052  ScopedLockType>::internal_find(const K &key,
3053  const_accessor *result,
3054  bool write)
3055 {
3056  assert(!result || !result->my_node);
3057 
3058  hashcode_type m = mask().load(std::memory_order_acquire);
3059 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
3060  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
3061 #endif
3062 
3063  assert((m & (m + 1)) == 0);
3064 
3065  hashcode_type const h = hasher{}(key);
3066 
3067  persistent_node_ptr_t node;
3068 
3069  while (true) {
3070  /* get bucket and acquire the lock */
3071  bucket_accessor b(
3072  this, h & m,
3073  scoped_lock_traits_type::initial_rw_state(false));
3074  node = get_node<false>(key, b);
3075 
3076  if (!node) {
3077  /* Element was possibly relocated, try again */
3078  if (check_mask_race(h, m)) {
3079  b.release();
3080  continue;
3081  } else {
3082  return false;
3083  }
3084  }
3085 
3086  /* No need to acquire the item or item acquired */
3087  if (!result ||
3088  try_acquire_item(
3089  result, node.get(this->my_pool_uuid)->mutex, write))
3090  break;
3091 
3092  /* the wait takes really long, restart the
3093  * operation */
3094  b.release();
3095 
3096  std::this_thread::yield();
3097 
3098  m = mask().load(std::memory_order_acquire);
3099 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
3100  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
3101 #endif
3102  }
3103 
3104  if (result) {
3105  result->my_node = node.get_persistent_ptr(this->my_pool_uuid);
3106  result->my_hash = h;
3107  }
3108 
3109  return true;
3110 }
3111 
3112 template <typename Key, typename T, typename Hash, typename KeyEqual,
3113  typename MutexType, typename ScopedLockType>
3114 template <typename K, typename... Args>
3115 bool
3116 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3117  ScopedLockType>::internal_insert(const K &key,
3118  const_accessor *result,
3119  bool write,
3120  Args &&... args)
3121 {
3122  assert(!result || !result->my_node);
3123 
3124  hashcode_type m = mask().load(std::memory_order_acquire);
3125 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
3126  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
3127 #endif
3128 
3129  assert((m & (m + 1)) == 0);
3130 
3131  hashcode_type const h = hasher{}(key);
3132 
3133  persistent_node_ptr_t node;
3134  size_t new_size = 0;
3135  bool inserted = false;
3136 
3137  while (true) {
3138  /* get bucket and acquire the lock */
3139  bucket_accessor b(
3140  this, h & m,
3141  scoped_lock_traits_type::initial_rw_state(true));
3142  node = get_node<true>(key, b);
3143 
3144  if (!node) {
3145  /* Element was possibly relocated, try again */
3146  if (check_mask_race(h, m)) {
3147  b.release();
3148  continue;
3149  }
3150 
3151  /* insert and set flag to grow the container */
3152  new_size = insert_new_node(b.get(), node,
3153  std::forward<Args>(args)...);
3154  inserted = true;
3155  }
3156 
3157  /* No need to acquire the item or item acquired */
3158  if (!result ||
3159  try_acquire_item(
3160  result, node.get(this->my_pool_uuid)->mutex, write))
3161  break;
3162 
3163  /* the wait takes really long, restart the
3164  * operation */
3165  b.release();
3166 
3167  std::this_thread::yield();
3168 
3169  m = mask().load(std::memory_order_acquire);
3170 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
3171  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
3172 #endif
3173  }
3174 
3175  if (result) {
3176  result->my_node = node.get_persistent_ptr(this->my_pool_uuid);
3177  result->my_hash = h;
3178  }
3179 
3180  check_growth(m, new_size);
3181 
3182  return inserted;
3183 }
3184 
3185 template <typename Key, typename T, typename Hash, typename KeyEqual,
3186  typename MutexType, typename ScopedLockType>
3187 template <typename K>
3188 bool
3189 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3190  ScopedLockType>::internal_erase(const K &key)
3191 {
3192  node_ptr_t n;
3193  hashcode_type const h = hasher{}(key);
3194  hashcode_type m = mask().load(std::memory_order_acquire);
3195 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
3196  ANNOTATE_HAPPENS_AFTER(&(this->my_mask));
3197 #endif
3198 
3199  pool_base pop = get_pool_base();
3200 
3201 restart : {
3202  /* lock scope */
3203  /* get bucket */
3204  bucket_accessor b(this, h & m,
3205  scoped_lock_traits_type::initial_rw_state(true));
3206 
3207 search:
3208  node_ptr_t *p = &b->node_list;
3209  n = *p;
3210 
3211  while (n &&
3212  !key_equal{}(key,
3213  detail::static_persistent_pool_pointer_cast<node>(
3214  n)(this->my_pool_uuid)
3215  ->item.first)) {
3216  p = &n(this->my_pool_uuid)->next;
3217  n = *p;
3218  }
3219 
3220  if (!n) {
3221  /* not found, but mask could be changed */
3222  if (check_mask_race(h, m))
3223  goto restart;
3224 
3225  return false;
3226  } else if (!b.is_writer() &&
3227  !scoped_lock_traits_type::upgrade_to_writer(b)) {
3228  if (check_mask_race(h, m)) /* contended upgrade, check mask */
3229  goto restart;
3230 
3231  goto search;
3232  }
3233 
3234  persistent_ptr<node> del = n(this->my_pool_uuid);
3235 
3236  {
3237  /* We cannot remove this element immediately because
3238  * other threads might work with this element via
3239  * accessors. The item_locker required to wait while
3240  * other threads use the node. */
3241  const_accessor acc;
3242  if (!try_acquire_item(&acc, del->mutex, true)) {
3243  /* the wait takes really long, restart the operation */
3244  b.release();
3245 
3246  std::this_thread::yield();
3247 
3248  m = mask().load(std::memory_order_acquire);
3249 
3250  goto restart;
3251  }
3252  }
3253 
3254  assert(pmemobj_tx_stage() == TX_STAGE_NONE);
3255 
3256  auto &size_diff = this->thread_size_diff();
3257 
3258  /* Only one thread can delete it due to write lock on the bucket
3259  */
3260  transaction::run(pop, [&] {
3261  *p = del->next;
3262  delete_node(del);
3263 
3264  --size_diff;
3265  });
3266 
3267  --(this->my_size);
3268 }
3269 
3270  return true;
3271 }
3272 
3273 template <typename Key, typename T, typename Hash, typename KeyEqual,
3274  typename MutexType, typename ScopedLockType>
3275 void
3278 {
3279  internal_swap(table);
3280 }
3281 
3282 template <typename Key, typename T, typename Hash, typename KeyEqual,
3283  typename MutexType, typename ScopedLockType>
3284 void
3286  size_type sz)
3287 {
3288  concurrent_hash_map_internal::check_outside_tx();
3289 
3290  reserve(sz);
3291  hashcode_type m = mask();
3292 
3293  /* only the last segment should be scanned for rehashing size or first
3294  * index of the last segment */
3295  hashcode_type b = (m + 1) >> 1;
3296 
3297  /* zero or power of 2 */
3298  assert((b & (b - 1)) == 0);
3299 
3300  for (; b <= m; ++b) {
3301  bucket *bp = get_bucket(b);
3302 
3303  concurrent_hash_map_internal::assert_not_locked<mutex_t,
3304  scoped_t>(
3305  bp->mutex);
3306  /* XXX Need to investigate if this statement is needed */
3307  if (bp->is_rehashed(std::memory_order_relaxed) == false)
3308  rehash_bucket<true>(bp, b);
3309  }
3310 }
3311 
3312 template <typename Key, typename T, typename Hash, typename KeyEqual,
3313  typename MutexType, typename ScopedLockType>
3314 void
3316 {
3317  hashcode_type m = mask();
3318 
3319  assert((m & (m + 1)) == 0);
3320 
3321 #ifndef NDEBUG
3322  /* check consistency */
3323  for (segment_index_t b = 0; b <= m; ++b) {
3324  bucket *bp = get_bucket(b);
3325  concurrent_hash_map_internal::assert_not_locked<mutex_t,
3326  scoped_t>(
3327  bp->mutex);
3328  }
3329 #endif
3330 
3331  pool_base pop = get_pool_base();
3332  { /* transaction scope */
3333 
3334  transaction::manual tx(pop);
3335 
3336  assert(this->tls_ptr != nullptr);
3337  this->tls_ptr->clear();
3338 
3339  this->on_init_size = 0;
3340 
3341  segment_index_t s = segment_traits_t::segment_index_of(m);
3342 
3343  assert(s + 1 == this->block_table_size ||
3344  !segment_facade_t(this->my_table, s + 1).is_valid());
3345 
3346  do {
3347  clear_segment(s);
3348  } while (s-- > 0);
3349 
3350  /*
3351  * As clear can only be called
3352  * from one thread, and there can be an outer
3353  * transaction we must make sure that mask and size
3354  * changes are transactional
3355  */
3356  transaction::snapshot((size_t *)&this->my_mask);
3357  transaction::snapshot((size_t *)&this->my_size);
3358 
3359  mask().store(embedded_buckets - 1, std::memory_order_relaxed);
3360  this->my_size = 0;
3361 
3363  }
3364 }
3365 
3366 template <typename Key, typename T, typename Hash, typename KeyEqual,
3367  typename MutexType, typename ScopedLockType>
3368 void
3369 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3370  ScopedLockType>::clear_segment(segment_index_t s)
3371 {
3372  segment_facade_t segment(this->my_table, s);
3373 
3374  assert(segment.is_valid());
3375 
3376  size_type sz = segment.size();
3377  for (segment_index_t i = 0; i < sz; ++i) {
3378  for (node_ptr_t n = segment[i].node_list; n;
3379  n = segment[i].node_list) {
3380  segment[i].node_list = n(this->my_pool_uuid)->next;
3381  delete_node(n);
3382  }
3383  }
3384 
3385  if (s >= segment_traits_t::embedded_segments)
3386  segment.disable();
3387 }
3388 
3389 template <typename Key, typename T, typename Hash, typename KeyEqual,
3390  typename MutexType, typename ScopedLockType>
3391 void
3393  internal_copy(const concurrent_hash_map &source)
3394 {
3395  auto pop = get_pool_base();
3396 
3397  reserve(source.size());
3398  internal_copy(source.begin(), source.end());
3399 }
3400 
3401 template <typename Key, typename T, typename Hash, typename KeyEqual,
3402  typename MutexType, typename ScopedLockType>
3403 template <typename I>
3404 void
3405 concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3406  ScopedLockType>::internal_copy(I first, I last)
3407 {
3408  hashcode_type m = mask();
3409 
3410  for (; first != last; ++first) {
3411  hashcode_type h = hasher{}(first->first);
3412  bucket *b = get_bucket(h & m);
3413 
3414  assert(b->is_rehashed(std::memory_order_relaxed));
3415 
3416  detail::persistent_pool_ptr<node> p;
3417  insert_new_node(b, p, *first);
3418  }
3419 }
3420 
3421 template <typename Key, typename T, typename Hash, typename KeyEqual,
3422  typename MutexType, typename ScopedLockType>
3423 inline bool
3424 operator==(const concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3425  ScopedLockType> &a,
3426  const concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3427  ScopedLockType> &b)
3428 {
3429  if (a.size() != b.size())
3430  return false;
3431 
3432  typename concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3433  ScopedLockType>::const_iterator
3434  i(a.begin()),
3435  i_end(a.end());
3436 
3437  typename concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3438  ScopedLockType>::const_iterator j,
3439  j_end(b.end());
3440 
3441  for (; i != i_end; ++i) {
3442  j = b.equal_range(i->first).first;
3443 
3444  if (j == j_end || !(i->second == j->second))
3445  return false;
3446  }
3447 
3448  return true;
3449 }
3450 
3451 template <typename Key, typename T, typename Hash, typename KeyEqual,
3452  typename MutexType, typename ScopedLockType>
3453 inline bool
3454 operator!=(const concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3455  ScopedLockType> &a,
3456  const concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType,
3457  ScopedLockType> &b)
3458 {
3459  return !(a == b);
3460 }
3461 
3462 template <typename Key, typename T, typename Hash, typename KeyEqual,
3463  typename MutexType, typename ScopedLockType>
3464 inline void
3465 swap(concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType, ScopedLockType> &a,
3466  concurrent_hash_map<Key, T, Hash, KeyEqual, MutexType, ScopedLockType> &b)
3467 {
3468  a.swap(b);
3469 }
3470 
3471 } /* namespace obj */
3472 } /* namespace pmem */
3473 
3474 #endif /* PMEMOBJ_CONCURRENT_HASH_MAP_HPP */
pmem::obj::concurrent_hash_map::clear
void clear()
Clear hash map content Not thread safe.
Definition: concurrent_hash_map.hpp:3315
pmem::obj::concurrent_hash_map::insert
bool insert(value_type &&value)
Insert item by copying if there is no such key present already.
Definition: concurrent_hash_map.hpp:2667
pmem::obj::transaction::commit
static void commit()
Manually commit a transaction.
Definition: transaction.hpp:353
pmem::obj::operator+
persistent_ptr< T > operator+(persistent_ptr< T > const &lhs, std::ptrdiff_t s)
Addition operator for persistent pointers.
Definition: persistent_ptr.hpp:805
pmem::obj::mutex
Persistent memory resident mutex implementation.
Definition: mutex.hpp:31
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map(concurrent_hash_map &&table)
Move constructor.
Definition: concurrent_hash_map.hpp:2120
pmem::obj::concurrent_hash_map::erase
bool erase(const Key &key)
Remove element with corresponding key.
Definition: concurrent_hash_map.hpp:2803
pmem::obj::concurrent_hash_map::bucket_accessor
Bucket accessor is to find, rehash, acquire a lock, and access a bucket.
Definition: concurrent_hash_map.hpp:1720
pmem::obj::concurrent_hash_map::const_accessor::release
void release()
Release accessor.
Definition: concurrent_hash_map.hpp:2009
pmem::obj::concurrent_hash_map::bucket_accessor::is_writer
bool is_writer() const
Check whether bucket is locked for write.
Definition: concurrent_hash_map.hpp:1776
pmem::obj::concurrent_hash_map::count
size_type count(const Key &key) const
Definition: concurrent_hash_map.hpp:2420
pmem::obj::concurrent_hash_map::end
iterator end()
Definition: concurrent_hash_map.hpp:2344
pmem::obj::p::get_ro
const T & get_ro() const noexcept
Retrieves read-only const reference of the object.
Definition: p.hpp:128
pmem::obj::concurrent_hash_map::insert
bool insert(accessor &result, value_type &&value)
Insert item by copying if there is no such key present already and acquire a write lock on the item.
Definition: concurrent_hash_map.hpp:2650
pmem
Persistent memory namespace.
Definition: allocation_flag.hpp:15
pmem::obj::concurrent_hash_map::~concurrent_hash_map
~concurrent_hash_map()
free_data should be called before concurrent_hash_map destructor is called.
Definition: concurrent_hash_map.hpp:2314
pmem::obj::concurrent_hash_map::operator=
concurrent_hash_map & operator=(const concurrent_hash_map &table)
Assignment Not thread safe.
Definition: concurrent_hash_map.hpp:2229
pmem::obj::begin
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
pmem::obj::concurrent_hash_map::const_accessor::operator*
const_reference operator*() const
Definition: concurrent_hash_map.hpp:2022
pmem::obj::concurrent_hash_map::accessor
Allows write access to elements and combines data access, locking, and garbage collection.
Definition: concurrent_hash_map.hpp:2066
common.hpp
Commonly used functionality.
pmem::obj::concurrent_hash_map::insert
bool insert(const_accessor &result, const value_type &value)
Insert item by copying if there is no such key present already and acquire a read lock on the item.
Definition: concurrent_hash_map.hpp:2584
template_helpers.hpp
Commonly used SFINAE helpers.
pmem::obj::concurrent_hash_map::insert_or_assign
bool insert_or_assign(key_type &&key, M &&obj)
Inserts item if there is no such key present already, assigns provided value otherwise.
Definition: concurrent_hash_map.hpp:2741
pmem::obj::concurrent_hash_map::runtime_initialize
void runtime_initialize()
Initialize persistent concurrent hash map after process restart.
Definition: concurrent_hash_map.hpp:2161
pmem::obj::transaction::snapshot
static void snapshot(const T *addr, size_t num=1)
Takes a “snapshot” of given elements of type T number (1 by default), located at the given address pt...
Definition: transaction.hpp:496
pmem::obj::concurrent_hash_map::serial_bucket_accessor::operator->
bucket * operator->() const
Overloaded arrow operator.
Definition: concurrent_hash_map.hpp:1859
pmem::obj::concurrent_hash_map::insert
bool insert(const_accessor &result, value_type &&value)
Insert item by copying if there is no such key present already and acquire a read lock on the item.
Definition: concurrent_hash_map.hpp:2632
pmem::obj::operator++
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pmem::obj::concurrent_hash_map::find
bool find(accessor &result, const K &key)
Find item and acquire a write lock on the item.
Definition: concurrent_hash_map.hpp:2534
pmem::obj::operator==
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:420
pmem::obj::concurrent_hash_map::serial_bucket_accessor::get
bucket * get() const
Get bucket pointer.
Definition: concurrent_hash_map.hpp:1850
pmem::obj::p
Resides on pmem class.
Definition: p.hpp:35
pmem::obj::defrag
Defrag class.
Definition: defrag.hpp:83
pmem::obj::concurrent_hash_map::free_data
void free_data()
Should be called before concurrent_hash_map destructor is called.
Definition: concurrent_hash_map.hpp:2293
pmem::obj::concurrent_hash_map::mutex_vector::push_and_try_lock
bucket * push_and_try_lock(concurrent_hash_map *base, hashcode_type h)
Save pointer to the lock in the vector and lock it.
Definition: concurrent_hash_map.hpp:2924
pmem::obj::concurrent_hash_map::const_accessor::~const_accessor
~const_accessor()
Destroy result after releasing the underlying reference.
Definition: concurrent_hash_map.hpp:2050
pmem::obj::concurrent_hash_map::bucket_count
size_type bucket_count() const
Definition: concurrent_hash_map.hpp:2400
defrag.hpp
Defragmentation class.
pmem::obj::concurrent_hash_map::size
size_type size() const
Definition: concurrent_hash_map.hpp:2373
make_persistent.hpp
Persistent_ptr transactional allocation functions for objects.
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map(std::initializer_list< value_type > il)
Construct table with initializer list.
Definition: concurrent_hash_map.hpp:2143
pmem::obj::concurrent_hash_map::mutex_vector
Vector of locks to be unlocked at the destruction time.
Definition: concurrent_hash_map.hpp:2918
pmem::obj::transaction::run
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:406
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map(size_type n)
Construct empty table with n preallocated buckets.
Definition: concurrent_hash_map.hpp:2098
pmem::obj::concurrent_hash_map::count
size_type count(const K &key) const
This overload only participates in overload resolution if the qualified-id Hash::transparent_key_equa...
Definition: concurrent_hash_map.hpp:2445
pmem::obj::concurrent_hash_map::insert
bool insert(accessor &result, const Key &key)
Insert item (if not already present) and acquire a write lock on the item.
Definition: concurrent_hash_map.hpp:2567
pmem::obj::concurrent_hash_map::find
bool find(accessor &result, const Key &key)
Find item and acquire a write lock on the item.
Definition: concurrent_hash_map.hpp:2506
pmem::obj::operator-
persistent_ptr< T > operator-(persistent_ptr< T > const &lhs, std::ptrdiff_t s)
Subtraction operator for persistent pointers.
Definition: persistent_ptr.hpp:819
pmem::obj::swap
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:880
pmem::obj::operator+=
p< T > & operator+=(p< T > &lhs, const p< Y > &rhs)
Addition assignment operator overload.
Definition: pext.hpp:94
pmem::obj::concurrent_hash_map::insert
void insert(std::initializer_list< value_type > il)
Insert initializer list.
Definition: concurrent_hash_map.hpp:2696
pmem::obj::operator!=
bool operator!=(const allocator< T, P, Tr > &lhs, const OtherAllocator &rhs)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:536
pmem::obj::defrag::run
pobj_defrag_result run()
Starts defragmentation with previously stored pointers.
Definition: defrag.hpp:188
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map(const concurrent_hash_map &table)
Copy constructor.
Definition: concurrent_hash_map.hpp:2108
pmem::obj::concurrent_hash_map::max_size
size_type max_size() const
Upper bound on size.
Definition: concurrent_hash_map.hpp:2391
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map()
Construct empty table.
Definition: concurrent_hash_map.hpp:2089
pmem::obj::operator-=
p< T > & operator-=(p< T > &lhs, const p< Y > &rhs)
Subtraction assignment operator overload.
Definition: pext.hpp:116
transaction.hpp
C++ pmemobj transactions.
pmem::obj::concurrent_hash_map::begin
const_iterator begin() const
Definition: concurrent_hash_map.hpp:2354
pmem::obj::concurrent_hash_map::bucket_accessor::acquire
void acquire(concurrent_hash_map *base, const hashcode_type h, bool writer=false)
Find a bucket by masked hashcode, optionally rehash, and acquire the lock.
Definition: concurrent_hash_map.hpp:1750
pmem::obj::concurrent_hash_map::insert_or_assign
bool insert_or_assign(const key_type &key, M &&obj)
Inserts item if there is no such key present already, assigns provided value otherwise.
Definition: concurrent_hash_map.hpp:2713
pmem::obj::concurrent_hash_map::erase
bool erase(const K &key)
Remove element with corresponding key.
Definition: concurrent_hash_map.hpp:2897
pmem::obj::persistent_ptr< node >
shared_mutex.hpp
Pmem-resident shared mutex.
pmem::obj::concurrent_hash_map::insert_or_assign
bool insert_or_assign(K &&key, M &&obj)
Inserts item if there is no such key-comparable type present already, assigns provided value otherwis...
Definition: concurrent_hash_map.hpp:2775
pmem::obj::concurrent_hash_map::insert
bool insert(accessor &result, const value_type &value)
Insert item by copying if there is no such key present already and acquire a write lock on the item.
Definition: concurrent_hash_map.hpp:2601
p.hpp
Resides on pmem property template.
pmem::obj::concurrent_hash_map::const_accessor::operator->
const_pointer operator->() const
Definition: concurrent_hash_map.hpp:2032
pmem::obj::concurrent_hash_map::operator=
concurrent_hash_map & operator=(std::initializer_list< value_type > il)
Assignment Not thread safe.
Definition: concurrent_hash_map.hpp:2251
pmem::obj::concurrent_hash_map::accessor::operator->
pointer operator->() const
Return pointer to associated value in hash table.
Definition: concurrent_hash_map.hpp:2080
pmem::obj::get
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:890
pmem::layout_error
Custom layout error class.
Definition: pexceptions.hpp:178
pmem::obj::concurrent_hash_map::bucket_accessor::get
bucket * get() const
Get bucket pointer.
Definition: concurrent_hash_map.hpp:1786
pmem::obj::concurrent_hash_map::const_accessor::value_type
const typename concurrent_hash_map::value_type value_type
Type of value.
Definition: concurrent_hash_map.hpp:1990
pmem::obj::concurrent_hash_map::serial_bucket_accessor::is_writer
bool is_writer() const
This method is added for consistency with bucket_accessor class.
Definition: concurrent_hash_map.hpp:1840
pmem::transaction_scope_error
Custom transaction error class.
Definition: pexceptions.hpp:158
pmem::obj::concurrent_hash_map::defragment
pobj_defrag_result defragment(double start_percent=0, double amount_percent=100)
Defragment the given (by 'start_percent' and 'amount_percent') part of buckets of the hash map.
Definition: concurrent_hash_map.hpp:2829
pmem::obj::concurrent_hash_map::internal_copy
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
Definition: concurrent_hash_map.hpp:3393
pmem::obj::concurrent_hash_map::empty
bool empty() const
Definition: concurrent_hash_map.hpp:2382
pmem::obj::defrag::add
std::enable_if< is_defragmentable< T >), void >::type add(T &t)
Stores address of the referenced object to the defragmentation queue.
Definition: defrag.hpp:112
pmem::obj::concurrent_hash_map::find
bool find(const_accessor &result, const K &key) const
Find item and acquire a read lock on the item.
Definition: concurrent_hash_map.hpp:2489
pmem::obj::concurrent_hash_map::insert
bool insert(const value_type &value)
Insert item by copying if there is no such key present already.
Definition: concurrent_hash_map.hpp:2617
pmem::obj::concurrent_hash_map::concurrent_hash_map
concurrent_hash_map(I first, I last)
Construction table with copying iteration range.
Definition: concurrent_hash_map.hpp:2131
pmem::obj::pool_base
The non-template pool base class.
Definition: pool.hpp:46
atomic_backoff.hpp
Atomic backoff, for time delay.
pmem::obj::concurrent_hash_map::insert
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.
Definition: concurrent_hash_map.hpp:2550
pmem::obj::concurrent_hash_map::const_accessor
Combines data access, locking, and garbage collection.
Definition: concurrent_hash_map.hpp:1978
pmem::obj::concurrent_hash_map::begin
iterator begin()
Definition: concurrent_hash_map.hpp:2334
persistent_ptr.hpp
Persistent smart pointer.
pmem::obj::concurrent_hash_map::bucket_accessor::operator->
bucket * operator->() const
Overloaded arrow operator.
Definition: concurrent_hash_map.hpp:1795
pmem::obj::concurrent_hash_map::accessor::operator*
reference operator*() const
Return reference to associated value in hash table.
Definition: concurrent_hash_map.hpp:2072
pmem::obj::concurrent_hash_map::swap
void swap(concurrent_hash_map &table)
Swap two instances.
Definition: concurrent_hash_map.hpp:3276
pmem::obj::concurrent_hash_map::insert
void insert(I first, I last)
Insert range [first, last)
Definition: concurrent_hash_map.hpp:2682
pmem::obj::transaction::manual
C++ manual scope transaction class.
Definition: transaction.hpp:84
pmem::obj::operator--
p< T > & operator--(p< T > &pp)
Prefix decrement operator overload.
Definition: pext.hpp:59
pmem::obj::concurrent_hash_map::const_accessor::const_accessor
const_accessor()
Create empty result.
Definition: concurrent_hash_map.hpp:2042
pmem::obj::concurrent_hash_map::find
bool find(const_accessor &result, const Key &key) const
Find item and acquire a read lock on the item.
Definition: concurrent_hash_map.hpp:2460
pmem::obj::concurrent_hash_map
Persistent memory aware implementation of Intel TBB concurrent_hash_map.
Definition: concurrent_hash_map.hpp:1624
enumerable_thread_specific.hpp
A persistent version of thread-local storage.
pmem::obj::concurrent_hash_map::rehash
void rehash(size_type n=0)
Rehashes and optionally resizes the whole table.
Definition: concurrent_hash_map.hpp:3285
mutex.hpp
Pmem-resident mutex.
pmem::obj::concurrent_hash_map::serial_bucket_accessor
Serial bucket accessor used to access bucket in a serial operations.
Definition: concurrent_hash_map.hpp:1804
pmem::obj::concurrent_hash_map::const_accessor::empty
bool empty() const
Definition: concurrent_hash_map.hpp:1997
pmem::obj::concurrent_hash_map::end
const_iterator end() const
Definition: concurrent_hash_map.hpp:2364
pmem::obj::concurrent_hash_map::defrag_save_nodes
void defrag_save_nodes(bucket *b, pmem::obj::defrag &defrag)
Internal method used by defragment().
Definition: concurrent_hash_map.hpp:3005