cds/intrusive/details/feldman_hashset_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
   4 #define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
   5
   6 #include <memory.h> // memcmp, memcpy
   7 #include <type_traits>
   8
   9 #include <cds/intrusive/details/base.h>
  10 #include <cds/opt/compare.h>
  11 #include <cds/algo/atomic.h>
  12 #include <cds/algo/split_bitstring.h>
  13 #include <cds/details/marked_ptr.h>
  14 #include <cds/urcu/options.h>
  15
  16 namespace cds { namespace intrusive {
  17
  18     /// FeldmanHashSet related definitions
  19     /** @ingroup cds_intrusive_helper
  20     */
  21     namespace feldman_hashset {
  22         /// Hash accessor option
  23         /**
  24             @copydetails traits::hash_accessor
  25         */
  26         template <typename Accessor>
  27         struct hash_accessor {
  28             //@cond
  29             template <typename Base> struct pack: public Base
  30             {
  31                 typedef Accessor hash_accessor;
  32             };
  33             //@endcond
  34         };
  35
  36         /// \p FeldmanHashSet internal statistics
  37         template <typename EventCounter = cds::atomicity::event_counter>
  38         struct stat {
  39             typedef EventCounter event_counter ; ///< Event counter type
  40
  41             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
  42             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
  43             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
  44             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  45             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  46             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  47             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  48             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  49             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  50             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  51             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  52             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  53
  54             event_counter   m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
  55             event_counter   m_nExpandNodeFailed;  ///< Number of failed attempts converting data node to array node
  56             event_counter   m_nSlotChanged;     ///< Number of array node slot changing by other thread during an operation
  57             event_counter   m_nSlotConverting;  ///< Number of events when we encounter a slot while it is converting to array node
  58
  59             event_counter   m_nArrayNodeCount;  ///< Number of array nodes
  60             event_counter   m_nHeight;          ///< Current height of the tree
  61
  62             //@cond
  63             void onInsertSuccess()              { ++m_nInsertSuccess;       }
  64             void onInsertFailed()               { ++m_nInsertFailed;        }
  65             void onInsertRetry()                { ++m_nInsertRetry;         }
  66             void onUpdateNew()                  { ++m_nUpdateNew;           }
  67             void onUpdateExisting()             { ++m_nUpdateExisting;      }
  68             void onUpdateFailed()               { ++m_nUpdateFailed;        }
  69             void onUpdateRetry()                { ++m_nUpdateRetry;         }
  70             void onEraseSuccess()               { ++m_nEraseSuccess;        }
  71             void onEraseFailed()                { ++m_nEraseFailed;         }
  72             void onEraseRetry()                 { ++m_nEraseRetry;          }
  73             void onFindSuccess()                { ++m_nFindSuccess;         }
  74             void onFindFailed()                 { ++m_nFindFailed;          }
  75
  76             void onExpandNodeSuccess()          { ++m_nExpandNodeSuccess;   }
  77             void onExpandNodeFailed()           { ++m_nExpandNodeFailed;    }
  78             void onSlotChanged()                { ++m_nSlotChanged;         }
  79             void onSlotConverting()             { ++m_nSlotConverting;      }
  80             void onArrayNodeCreated()           { ++m_nArrayNodeCount;      }
  81             void height( size_t h )             { if (m_nHeight < h ) m_nHeight = h; }
  82             //@endcond
  83         };
  84
  85         /// \p FeldmanHashSet empty internal statistics
  86         struct empty_stat {
  87             //@cond
  88             void onInsertSuccess()              const {}
  89             void onInsertFailed()               const {}
  90             void onInsertRetry()                const {}
  91             void onUpdateNew()                  const {}
  92             void onUpdateExisting()             const {}
  93             void onUpdateFailed()               const {}
  94             void onUpdateRetry()                const {}
  95             void onEraseSuccess()               const {}
  96             void onEraseFailed()                const {}
  97             void onEraseRetry()                 const {}
  98             void onFindSuccess()                const {}
  99             void onFindFailed()                 const {}
 100
 101             void onExpandNodeSuccess()          const {}
 102             void onExpandNodeFailed()           const {}
 103             void onSlotChanged()                const {}
 104             void onSlotConverting()             const {}
 105             void onArrayNodeCreated()           const {}
 106             void height(size_t)                 const {}
 107             //@endcond
 108         };
 109
 110         /// \p FeldmanHashSet traits
 111         struct traits
 112         {
 113             /// Mandatory functor to get hash value from data node
 114             /**
 115                 It is most-important feature of \p FeldmanHashSet.
 116                 That functor must return a reference to fixed-sized hash value of data node.
 117                 The return value of that functor specifies the type of hash value.
 118
 119                 Example:
 120                 \code
 121                 typedef uint8_t hash_type[32]; // 256-bit hash type
 122                 struct foo {
 123                     hash_type  hash; // 256-bit hash value
 124                     // ... other fields
 125                 };
 126
 127                 // Hash accessor
 128                 struct foo_hash_accessor {
 129                     hash_type const& operator()( foo const& d ) const
 130                     {
 131                         return d.hash;
 132                     }
 133                 };
 134                 \endcode
 135             */
 136             typedef cds::opt::none hash_accessor;
 137
 138             /// Disposer for removing data nodes
 139             typedef cds::intrusive::opt::v::empty_disposer disposer;
 140
 141             /// Hash comparing functor
 142             /**
 143                 No default functor is provided.
 144                 If the option is not specified, the \p less option is used.
 145             */
 146             typedef cds::opt::none compare;
 147
 148             /// Specifies binary predicate used for hash compare.
 149             /**
 150                 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
 151                 because the hash value is treated as fixed-sized bit-string.
 152             */
 153             typedef cds::opt::none less;
 154
 155             /// Item counter
 156             /**
 157                 The item counting is an important part of \p FeldmanHashSet algorithm:
 158                 the \p empty() member function depends on correct item counting.
 159                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 160
 161                 Default is \p atomicity::item_counter.
 162             */
 163             typedef cds::atomicity::item_counter item_counter;
 164
 165             /// Array node allocator
 166             /**
 167                 Allocator for array nodes. That allocator is used for creating \p headNode and \p arrayNode when the set grows.
 168                 Default is \ref CDS_DEFAULT_ALLOCATOR
 169             */
 170             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 171
 172             /// C++ memory ordering model
 173             /**
 174                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 175                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 176             */
 177             typedef cds::opt::v::relaxed_ordering memory_model;
 178
 179             /// Back-off strategy
 180             typedef cds::backoff::Default back_off;
 181
 182             /// Internal statistics
 183             /**
 184                 By default, internal statistics is disabled (\p feldman_hashset::empty_stat).
 185                 Use \p feldman_hashset::stat to enable it.
 186             */
 187             typedef empty_stat stat;
 188
 189             /// RCU deadlock checking policy (only for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
 190             /**
 191                 List of available policy see \p opt::rcu_check_deadlock
 192             */
 193             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 194         };
 195
 196         /// Metafunction converting option list to \p feldman_hashset::traits
 197         /**
 198             Supported \p Options are:
 199             - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
 200                 @copydetails traits::hash_accessor
 201             - \p opt::node_allocator - array node allocator.
 202                 @copydetails traits::node_allocator
 203             - \p opt::compare - hash comparison functor. No default functor is provided.
 204                 If the option is not specified, the \p opt::less is used.
 205             - \p opt::less - specifies binary predicate used for hash comparison.
 206                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 207                 because the hash value is treated as fixed-sized bit-string.
 208             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 209             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 210                 of GC schema the disposer may be called asynchronously.
 211             - \p opt::item_counter - the type of item counting feature.
 212                  The item counting is an important part of \p FeldmanHashSet algorithm:
 213                  the \p empty() member function depends on correct item counting.
 214                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 215                  Default is \p atomicity::item_counter.
 216             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 217                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 218             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
 219                 To enable it use \p feldman_hashset::stat
 220             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 221                 Default is \p opt::v::rcu_throw_deadlock
 222         */
 223         template <typename... Options>
 224         struct make_traits
 225         {
 226 #   ifdef CDS_DOXYGEN_INVOKED
 227             typedef implementation_defined type ;   ///< Metafunction result
 228 #   else
 229             typedef typename cds::opt::make_options<
 230                 typename cds::opt::find_type_traits< traits, Options... >::type
 231                 ,Options...
 232             >::type   type;
 233 #   endif
 234         };
 235
 236         /// Bit-wise memcmp-based comparator for hash value \p T
 237         template <typename T>
 238         struct bitwise_compare
 239         {
 240             /// Compares \p lhs and \p rhs
 241             /**
 242                 Returns:
 243                 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
 244                 - <tt>0</tt> if <tt>lhs == rhs</tt>
 245                 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
 246             */
 247             int operator()( T const& lhs, T const& rhs ) const
 248             {
 249                 return memcmp( &lhs, &rhs, sizeof(T));
 250             }
 251         };
 252
 253         /// One-level statistics, see \p FeldmanHashSet::get_level_statistics
 254         struct level_statistics
 255         {
 256             size_t array_node_count;    ///< Count of array node at the level
 257             size_t node_capacity;       ///< Array capacity
 258
 259             size_t data_cell_count;     ///< The number of data cells in all array node at this level
 260             size_t array_cell_count;    ///< The number of array cells in all array node at this level
 261             size_t empty_cell_count;    ///< The number of empty cells in all array node at this level
 262
 263             //@cond
 264             level_statistics()
 265                 : array_node_count(0)
 266                 , data_cell_count(0)
 267                 , array_cell_count(0)
 268                 , empty_cell_count(0)
 269             {}
 270             //@endcond
 271         };
 272
 273         //@cond
 274         namespace details {
 275             template <typename HashType, typename UInt = size_t >
 276             using hash_splitter = cds::algo::split_bitstring< HashType, UInt >;
 277
 278             struct metrics {
 279                 size_t  head_node_size;     // power-of-two
 280                 size_t  head_node_size_log; // log2( head_node_size )
 281                 size_t  array_node_size;    // power-of-two
 282                 size_t  array_node_size_log;// log2( array_node_size )
 283
 284                 static metrics make(size_t head_bits, size_t array_bits, size_t hash_size )
 285                 {
 286                     size_t const hash_bits = hash_size * 8;
 287
 288                     if (array_bits < 2)
 289                         array_bits = 2;
 290                     if (head_bits < 4)
 291                         head_bits = 4;
 292                     if (head_bits > hash_bits)
 293                         head_bits = hash_bits;
 294                     if ((hash_bits - head_bits) % array_bits != 0)
 295                         head_bits += (hash_bits - head_bits) % array_bits;
 296
 297                     assert((hash_bits - head_bits) % array_bits == 0);
 298
 299                     metrics m;
 300                     m.head_node_size_log = head_bits;
 301                     m.head_node_size = size_t(1) << head_bits;
 302                     m.array_node_size_log = array_bits;
 303                     m.array_node_size = size_t(1) << array_bits;
 304                     return m;
 305                 }
 306             };
 307
 308         } // namespace details
 309         //@endcond
 310
 311         //@cond
 312         template <typename T, typename Traits>
 313         class multilevel_array
 314         {
 315         public:
 316             typedef T value_type;
 317             typedef Traits traits;
 318             typedef typename Traits::node_allocator node_allocator;
 319             typedef typename traits::memory_model   memory_model;
 320             typedef typename traits::back_off       back_off;       ///< Backoff strategy
 321             typedef typename traits::stat           stat;           ///< Internal statistics type
 322
 323             typedef typename traits::hash_accessor hash_accessor;
 324             static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified");
 325
 326             /// Hash type deduced from \p hash_accessor return type
 327             typedef typename std::decay<
 328                 typename std::remove_reference<
 329                 decltype(hash_accessor()(std::declval<value_type>()))
 330                 >::type
 331             >::type hash_type;
 332             //typedef typename std::result_of< hash_accessor( std::declval<value_type>()) >::type hash_type;
 333             static_assert(!std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value");
 334
 335             typedef typename cds::opt::details::make_comparator_from<
 336                 hash_type,
 337                 traits,
 338                 feldman_hashset::bitwise_compare< hash_type >
 339             >::type hash_comparator;
 340
 341             typedef feldman_hashset::details::hash_splitter< hash_type > hash_splitter;
 342
 343             enum node_flags {
 344                 flag_array_converting = 1,   ///< the cell is converting from data node to an array node
 345                 flag_array_node = 2          ///< the cell is a pointer to an array node
 346             };
 347
 348         protected:
 349
 350             typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
 351             typedef atomics::atomic< node_ptr > atomic_node_ptr;
 352
 353             struct array_node {
 354                 array_node * const  pParent;    ///< parent array node
 355                 size_t const        idxParent;  ///< index in parent array node
 356                 atomic_node_ptr     nodes[1];   ///< node array
 357
 358                 array_node(array_node * parent, size_t idx)
 359                     : pParent(parent)
 360                     , idxParent(idx)
 361                 {}
 362
 363                 array_node() = delete;
 364                 array_node(array_node const&) = delete;
 365                 array_node(array_node&&) = delete;
 366             };
 367
 368             typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
 369
 370             struct traverse_data {
 371                 hash_splitter splitter;
 372                 array_node * pArr;
 373                 size_t nOffset;
 374                 size_t nSlot;
 375                 size_t nHeight;
 376
 377                 traverse_data( hash_type const& hash, multilevel_array& arr )
 378                     : splitter( hash )
 379                     , pArr( arr.head() )
 380                     , nOffset( arr.metrics().head_node_size_log )
 381                     , nSlot(splitter.cut(arr.metrics().head_node_size_log))
 382                     , nHeight( 1 )
 383                 {}
 384             };
 385
 386         protected:
 387             feldman_hashset::details::metrics const m_Metrics;
 388             array_node *      m_Head;
 389             mutable stat      m_Stat;
 390
 391         public:
 392             multilevel_array(size_t head_bits, size_t array_bits )
 393                 : m_Metrics(feldman_hashset::details::metrics::make(head_bits, array_bits, sizeof(hash_type)))
 394                 , m_Head( alloc_head_node())
 395             {}
 396
 397             ~multilevel_array()
 398             {
 399                 destroy_tree();
 400                 free_array_node(m_Head);
 401             }
 402
 403             node_ptr traverse(traverse_data& pos)
 404             {
 405                 back_off bkoff;
 406                 while (true) {
 407                     node_ptr slot = pos.pArr->nodes[pos.nSlot].load(memory_model::memory_order_acquire);
 408                     if (slot.bits() == flag_array_node) {
 409                         // array node, go down the tree
 410                         assert(slot.ptr() != nullptr);
 411                         pos.nSlot = pos.splitter.cut( metrics().array_node_size_log );
 412                         assert( pos.nSlot < metrics().array_node_size );
 413                         pos.pArr = to_array(slot.ptr());
 414                         pos.nOffset += metrics().array_node_size_log;
 415                         ++pos.nHeight;
 416                     }
 417                     else if (slot.bits() == flag_array_converting) {
 418                         // the slot is converting to array node right now
 419                         bkoff();
 420                         stats().onSlotConverting();
 421                     }
 422                     else {
 423                         // data node
 424                         assert(slot.bits() == 0);
 425                         return slot;
 426                     }
 427                 } // while
 428             }
 429
 430             size_t head_size() const
 431             {
 432                 return m_Metrics.head_node_size;
 433             }
 434
 435             size_t array_node_size() const
 436             {
 437                 return m_Metrics.array_node_size;
 438             }
 439
 440             void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 441             {
 442                 stat.clear();
 443                 gather_level_statistics(stat, 0, m_Head, head_size());
 444             }
 445
 446         protected:
 447             array_node * head() const
 448             {
 449                 return m_Head;
 450             }
 451
 452             stat& stats() const
 453             {
 454                 return m_Stat;
 455             }
 456
 457             feldman_hashset::details::metrics const& metrics() const
 458             {
 459                 return m_Metrics;
 460             }
 461
 462             void destroy_tree()
 463             {
 464                 // The function is not thread-safe. For use in dtor only
 465                 // Destroy all array nodes
 466                 destroy_array_nodes(m_Head, head_size());
 467             }
 468
 469             void destroy_array_nodes(array_node * pArr, size_t nSize)
 470             {
 471                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 472                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 473                     if (slot.bits() == flag_array_node) {
 474                         destroy_array_nodes(to_array(slot.ptr()), array_node_size());
 475                         free_array_node(to_array(slot.ptr()));
 476                         p->store(node_ptr(), memory_model::memory_order_relaxed);
 477                     }
 478                 }
 479             }
 480
 481             static array_node * alloc_array_node(size_t nSize, array_node * pParent, size_t idxParent)
 482             {
 483                 array_node * pNode = cxx_array_node_allocator().NewBlock(sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent);
 484                 new (pNode->nodes) atomic_node_ptr[nSize];
 485                 return pNode;
 486             }
 487
 488             array_node * alloc_head_node() const
 489             {
 490                 return alloc_array_node(head_size(), nullptr, 0);
 491             }
 492
 493             array_node * alloc_array_node(array_node * pParent, size_t idxParent) const
 494             {
 495                 return alloc_array_node(array_node_size(), pParent, idxParent);
 496             }
 497
 498             static void free_array_node(array_node * parr)
 499             {
 500                 cxx_array_node_allocator().Delete(parr);
 501             }
 502
 503             union converter {
 504                 value_type * pData;
 505                 array_node * pArr;
 506
 507                 converter(value_type * p)
 508                     : pData(p)
 509                 {}
 510
 511                 converter(array_node * p)
 512                     : pArr(p)
 513                 {}
 514             };
 515
 516             static array_node * to_array(value_type * p)
 517             {
 518                 return converter(p).pArr;
 519             }
 520             static value_type * to_node(array_node * p)
 521             {
 522                 return converter(p).pData;
 523             }
 524
 525             void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
 526             {
 527                 if (stat.size() <= nLevel) {
 528                     stat.resize(nLevel + 1);
 529                     stat[nLevel].node_capacity = nSize;
 530                 }
 531
 532                 ++stat[nLevel].array_node_count;
 533                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 534                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 535                     if (slot.bits()) {
 536                         ++stat[nLevel].array_cell_count;
 537                         if (slot.bits() == flag_array_node)
 538                             gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
 539                     }
 540                     else if (slot.ptr())
 541                         ++stat[nLevel].data_cell_count;
 542                     else
 543                         ++stat[nLevel].empty_cell_count;
 544                 }
 545             }
 546
 547             bool expand_slot( traverse_data& pos, node_ptr current)
 548             {
 549                 return expand_slot( pos.pArr, pos.nSlot, current, pos.nOffset );
 550             }
 551
 552             bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset)
 553             {
 554                 assert(current.bits() == 0);
 555                 assert(current.ptr());
 556
 557                 size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut(m_Metrics.array_node_size_log);
 558                 array_node * pArr = alloc_array_node(pParent, idxParent);
 559
 560                 node_ptr cur(current.ptr());
 561                 atomic_node_ptr& slot = pParent->nodes[idxParent];
 562                 if (!slot.compare_exchange_strong(cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed))
 563                 {
 564                     stats().onExpandNodeFailed();
 565                     free_array_node(pArr);
 566                     return false;
 567                 }
 568
 569                 pArr->nodes[idx].store(current, memory_model::memory_order_release);
 570
 571                 cur = cur | flag_array_converting;
 572                 CDS_VERIFY(
 573                     slot.compare_exchange_strong(cur, node_ptr(to_node(pArr), flag_array_node), memory_model::memory_order_release, atomics::memory_order_relaxed)
 574                     );
 575
 576                 stats().onExpandNodeSuccess();
 577                 stats().onArrayNodeCreated();
 578                 return true;
 579             }
 580
 581         };
 582         //@endcond
 583     } // namespace feldman_hashset
 584
 585     //@cond
 586     // Forward declaration
 587     template < class GC, typename T, class Traits = feldman_hashset::traits >
 588     class FeldmanHashSet;
 589     //@endcond
 590
 591 }} // namespace cds::intrusive
 592
 593 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H