1 /*
   2  * Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP
  26 #define SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "utilities/globalCounter.hpp"
  30 #include "utilities/globalDefinitions.hpp"
  31 #include "utilities/tableStatistics.hpp"
  32 
  33 // A mostly concurrent-hash-table where the read-side is wait-free, inserts are
  34 // CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
  35 // type kept inside each Node and CONFIG contains hash and allocation methods.
  36 // A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
  37 
  38 class Thread;
  39 class Mutex;
  40 
  41 template <typename VALUE, typename CONFIG, MEMFLAGS F>
  42 class ConcurrentHashTable : public CHeapObj<F> {
  43  private:
  44   // This is the internal node structure.
  45   // Only constructed with placement new from memory allocated with MEMFLAGS of
  46   // the InternalTable or user-defined memory.
  47   class Node {
  48    private:
  49     Node * volatile _next;
  50     VALUE _value;
  51    public:
  52     Node(const VALUE& value, Node* next = NULL)
  53       : _next(next), _value(value) {
  54       assert((((uintptr_t)this) & ((uintptr_t)0x3)) == 0,
  55              "Must 16 bit aligned.");
  56     }
  57 
  58     Node* next() const;
  59     void set_next(Node* node)         { _next = node; }
  60     Node* const volatile * next_ptr() { return &_next; }
  61 
  62     VALUE* value()                    { return &_value; }
  63 
  64     // Creates a node.
  65     static Node* create_node(const VALUE& value, Node* next = NULL) {
  66       return new (CONFIG::allocate_node(sizeof(Node), value)) Node(value, next);
  67     }
  68     // Destroys a node.
  69     static void destroy_node(Node* node) {
  70       CONFIG::free_node((void*)node, node->_value);
  71     }
  72 
  73     void print_on(outputStream* st) const {};
  74     void print_value_on(outputStream* st) const {};
  75   };
  76 
  77   // Only constructed with placement new from an array allocated with MEMFLAGS
  78   // of InternalTable.
  79   class Bucket {
  80    private:
  81 
  82     // Embedded state in two low bits in first pointer is a spinlock with 3
  83     // states, unlocked, locked, redirect. You must never busy-spin on trylock()
  84     // or call lock() without _resize_lock, that would deadlock. Redirect can
  85     // only be installed by owner and is the final state of a bucket.
  86     // The only two valid flows are:
  87     // unlocked -> locked -> unlocked
  88     // unlocked -> locked -> redirect
  89     // Locked state only applies to an updater.
  90     // Reader only check for redirect.
  91     Node * volatile _first;
  92 
  93     static const uintptr_t STATE_LOCK_BIT     = 0x1;
  94     static const uintptr_t STATE_REDIRECT_BIT = 0x2;
  95     static const uintptr_t STATE_MASK         = 0x3;
  96 
  97     // Get the first pointer unmasked.
  98     Node* first_raw() const;
  99 
 100     // Methods to manipulate the embedded.
 101     static bool is_state(Node* node, uintptr_t bits) {
 102       return (bits & (uintptr_t)node) == bits;
 103     }
 104 
 105     static Node* set_state(Node* n, uintptr_t bits) {
 106       return (Node*)(bits | (uintptr_t)n);
 107     }
 108 
 109     static uintptr_t get_state(Node* node) {
 110       return (((uintptr_t)node) & STATE_MASK);
 111     }
 112 
 113     static Node* clear_state(Node* node) {
 114       return (Node*)(((uintptr_t)node) & (~(STATE_MASK)));
 115     }
 116 
 117     static Node* clear_set_state(Node* node, Node* state) {
 118       return (Node*)(((uintptr_t)clear_state(node)) ^ get_state(state));
 119     }
 120 
 121    public:
 122     // A bucket is only one pointer with the embedded state.
 123     Bucket() : _first(NULL) {};
 124 
 125     // Get the first pointer unmasked.
 126     Node* first() const;
 127 
 128     // Get a pointer to the const first pointer. Do not deference this
 129     // pointer, the pointer pointed to _may_ contain an embedded state. Such
 130     // pointer should only be used as input to release_assign_node_ptr.
 131     Node* const volatile * first_ptr() { return &_first; }
 132 
 133     // This is the only place where a pointer to a Node pointer that potentially
 134     // is _first should be changed. Otherwise we destroy the embedded state. We
 135     // only give out pointer to const Node pointer to avoid accidental
 136     // assignment, thus here we must cast const part away. Method is not static
 137     // due to an assert.
 138     void release_assign_node_ptr(Node* const volatile * dst, Node* node) const;
 139 
 140     // This method assigns this buckets last Node next ptr to input Node.
 141     void release_assign_last_node_next(Node* node);
 142 
 143     // Setting the first pointer must be done with CAS.
 144     bool cas_first(Node *node, Node* expect);
 145 
 146     // Returns true if this bucket is redirecting to a new table.
 147     // Redirect is a terminal state and will never change.
 148     bool have_redirect() const;
 149 
 150     // Return true if this bucket is locked for updates.
 151     bool is_locked() const;
 152 
 153     // Return true if this bucket was locked.
 154     bool trylock();
 155 
 156     // The bucket might be invalid, due to a concurrent resize. The lock()
 157     // method do no respect that and can deadlock if caller do not hold
 158     // _resize_lock.
 159     void lock();
 160 
 161     // Unlocks this bucket.
 162     void unlock();
 163 
 164     // Installs redirect in this bucket.
 165     // Prior to doing so you must have successfully locked this bucket.
 166     void redirect();
 167   };
 168 
 169   // The backing storage table holding the buckets and it's size and mask-bits.
 170   // Table is always a power of two for two reasons:
 171   // - Re-size can only change the size into half or double
 172   //   (any pow 2 would also be possible).
 173   // - Use masking of hash for bucket index.
 174   class InternalTable : public CHeapObj<F> {
 175    private:
 176     Bucket* _buckets;        // Bucket array.
 177    public:
 178     const size_t _log2_size; // Size in log2.
 179     const size_t _size;      // Size in log10.
 180 
 181     // The mask used on hash for selecting bucket.
 182     // The masked value is guaranteed be to inside the buckets array.
 183     const size_t _hash_mask;
 184 
 185     // Create a backing table
 186     InternalTable(size_t log2_size);
 187     ~InternalTable();
 188 
 189     Bucket* get_buckets() { return _buckets; }
 190     Bucket* get_bucket(size_t idx) { return &_buckets[idx]; }
 191   };
 192 
 193   // Used as default functor when no functor supplied for some methods.
 194   struct NoOp {
 195     void operator()(VALUE*) {}
 196     const VALUE& operator()() {}
 197     void operator()(bool, VALUE*) {}
 198   } noOp;
 199 
 200   // For materializing a supplied value.
 201   class LazyValueRetrieve {
 202    private:
 203     const VALUE& _val;
 204    public:
 205     LazyValueRetrieve(const VALUE& val) : _val(val) {}
 206     const VALUE& operator()() { return _val; }
 207   };
 208 
 209   InternalTable* _table;      // Active table.
 210   InternalTable* _new_table;  // Table we are resizing to.
 211 
 212   // Default sizes
 213   static const size_t DEFAULT_MAX_SIZE_LOG2 = 21;
 214   static const size_t DEFAULT_START_SIZE_LOG2 = 13;
 215   static const size_t DEFAULT_GROW_HINT = 4; // Chain length
 216 
 217   const size_t _log2_size_limit;  // The biggest size.
 218   const size_t _log2_start_size;  // Start size.
 219   const size_t _grow_hint;        // Number of linked items
 220 
 221   volatile bool _size_limit_reached;
 222 
 223   // We serialize resizers and other bulk operations which do not support
 224   // concurrent resize with this lock.
 225   Mutex* _resize_lock;
 226   // Since we need to drop mutex for safepoints, but stop other threads from
 227   // taking the mutex after a safepoint this bool is the actual state. After
 228   // acquiring the mutex you must check if this is already locked. If so you
 229   // must drop the mutex until the real lock holder grabs the mutex.
 230   volatile Thread* _resize_lock_owner;
 231 
 232   // Return true if lock mutex/state succeeded.
 233   bool try_resize_lock(Thread* locker);
 234   // Returns when both mutex and state are proper locked.
 235   void lock_resize_lock(Thread* locker);
 236   // Unlocks mutex and state.
 237   void unlock_resize_lock(Thread* locker);
 238 
 239   // This method sets the _invisible_epoch and do a write_synchronize.
 240   // Subsequent calls check the state of _invisible_epoch and determine if the
 241   // write_synchronize can be avoided. If not, it sets the _invisible_epoch
 242   // again and do a write_synchronize.
 243   void write_synchonize_on_visible_epoch(Thread* thread);
 244   // To be-able to avoid write_synchronize in resize and other bulk operation,
 245   // this field keep tracks if a version of the hash-table was ever been seen.
 246   // We the working thread pointer as tag for debugging. The _invisible_epoch
 247   // can only be used by the owner of _resize_lock.
 248   volatile Thread* _invisible_epoch;
 249 
 250   // Scoped critical section, which also handles the invisible epochs.
 251   // An invisible epoch/version do not need a write_synchronize().
 252   class ScopedCS: public StackObj {
 253    protected:
 254     Thread* _thread;
 255     ConcurrentHashTable<VALUE, CONFIG, F>* _cht;
 256     GlobalCounter::CSContext _cs_context;
 257    public:
 258     ScopedCS(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht);
 259     ~ScopedCS();
 260   };
 261 
 262 
 263   // Max number of deletes in one bucket chain during bulk delete.
 264   static const size_t BULK_DELETE_LIMIT = 256;
 265 
 266   // Simple getters and setters for the internal table.
 267   InternalTable* get_table() const;
 268   InternalTable* get_new_table() const;
 269   InternalTable* set_table_from_new();
 270 
 271   // Destroys all nodes.
 272   void free_nodes();
 273 
 274   // Mask away high bits of hash.
 275   static size_t bucket_idx_hash(InternalTable* table, const uintx hash) {
 276     return ((size_t)hash) & table->_hash_mask;
 277   }
 278 
 279   // Returns bucket for hash for that internal table.
 280   Bucket* get_bucket_in(InternalTable* table, const uintx hash) const {
 281     size_t bucket_index = bucket_idx_hash(table, hash);
 282     return table->get_bucket(bucket_index);
 283   }
 284 
 285   // Return correct bucket for reading and handles resizing.
 286   Bucket* get_bucket(const uintx hash) const;
 287 
 288   // Return correct bucket for updates and handles resizing.
 289   Bucket* get_bucket_locked(Thread* thread, const uintx hash);
 290 
 291   // Finds a node.
 292   template <typename LOOKUP_FUNC>
 293   Node* get_node(const Bucket* const bucket, LOOKUP_FUNC& lookup_f,
 294                  bool* have_dead, size_t* loops = NULL) const;
 295 
 296   // Method for shrinking.
 297   bool internal_shrink_prolog(Thread* thread, size_t log2_size);
 298   void internal_shrink_epilog(Thread* thread);
 299   void internal_shrink_range(Thread* thread, size_t start, size_t stop);
 300   bool internal_shrink(Thread* thread, size_t size_limit_log2);
 301 
 302   // Methods for growing.
 303   bool unzip_bucket(Thread* thread, InternalTable* old_table,
 304                     InternalTable* new_table, size_t even_index,
 305                     size_t odd_index);
 306   bool internal_grow_prolog(Thread* thread, size_t log2_size);
 307   void internal_grow_epilog(Thread* thread);
 308   void internal_grow_range(Thread* thread, size_t start, size_t stop);
 309   bool internal_grow(Thread* thread, size_t log2_size);
 310 
 311   // Get a value.
 312   template <typename LOOKUP_FUNC>
 313   VALUE* internal_get(Thread* thread, LOOKUP_FUNC& lookup_f,
 314                       bool* grow_hint = NULL);
 315 
 316   // Plain insert.
 317   template <typename LOOKUP_FUNC>
 318   bool internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
 319                        bool* grow_hint, bool* clean_hint);
 320 
 321   // Returns true if an item matching LOOKUP_FUNC is removed.
 322   // Calls DELETE_FUNC before destroying the node.
 323   template <typename LOOKUP_FUNC, typename DELETE_FUNC>
 324   bool internal_remove(Thread* thread, LOOKUP_FUNC& lookup_f,
 325                        DELETE_FUNC& delete_f);
 326 
 327   // Visits nodes with FUNC.
 328   template <typename FUNC>
 329   static bool visit_nodes(Bucket* bucket, FUNC& visitor_f);
 330 
 331   // During shrink/grow we cannot guarantee that we only visit nodes once, with
 332   // current algorithm. To keep it simple caller will have locked
 333   // _resize_lock.
 334   template <typename FUNC>
 335   void do_scan_locked(Thread* thread, FUNC& scan_f);
 336 
 337   // Check for dead items in a bucket.
 338   template <typename EVALUATE_FUNC>
 339   size_t delete_check_nodes(Bucket* bucket, EVALUATE_FUNC& eval_f,
 340                             size_t num_del, Node** ndel);
 341 
 342   // Check for dead items in this table. During shrink/grow we cannot guarantee
 343   // that we only visit nodes once. To keep it simple caller will have locked
 344   // _resize_lock.
 345   template <typename EVALUATE_FUNC, typename DELETE_FUNC>
 346   void do_bulk_delete_locked(Thread* thread, EVALUATE_FUNC& eval_f
 347                              , DELETE_FUNC& del_f) {
 348     do_bulk_delete_locked_for(thread, 0, _table->_size, eval_f, del_f);
 349   }
 350 
 351   // To have prefetching for a VALUE that is pointer during
 352   // do_bulk_delete_locked, we have this helper classes. One for non-pointer
 353   // case without prefect and one for pointer with prefect.
 354   template <bool b, typename EVALUATE_FUNC>
 355   struct HaveDeletables {
 356     static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
 357                                Bucket* prefetch_bucket);
 358   };
 359   template<typename EVALUATE_FUNC>
 360   struct HaveDeletables<true, EVALUATE_FUNC> {
 361     static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
 362                                Bucket* prefetch_bucket);
 363   };
 364 
 365   // Check for dead items in this table with range. During shrink/grow we cannot
 366   // guarantee that we only visit nodes once. To keep it simple caller will
 367   // have locked _resize_lock.
 368   template <typename EVALUATE_FUNC, typename DELETE_FUNC>
 369   void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
 370                                  size_t stop_idx, EVALUATE_FUNC& eval_f,
 371                                  DELETE_FUNC& del_f, bool is_mt = false);
 372 
 373   // Method to delete one items.
 374   template <typename LOOKUP_FUNC>
 375   void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
 376 
 377  public:
 378   ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
 379                       size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
 380                       size_t grow_hint = DEFAULT_GROW_HINT);
 381 
 382   ~ConcurrentHashTable();
 383 
 384   TableRateStatistics _stats_rate;
 385 
 386   size_t get_size_log2(Thread* thread);
 387   size_t get_node_size() const { return sizeof(Node); }
 388   bool is_max_size_reached() { return _size_limit_reached; }
 389 
 390   // This means no paused bucket resize operation is going to resume
 391   // on this table.
 392   bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
 393 
 394   // Re-size operations.
 395   bool shrink(Thread* thread, size_t size_limit_log2 = 0);
 396   bool grow(Thread* thread, size_t size_limit_log2 = 0);
 397 
 398   // All callbacks for get are under critical sections. Other callbacks may be
 399   // under critical section or may have locked parts of table. Calling any
 400   // methods on the table during a callback is not supported.Only MultiGetHandle
 401   // supports multiple gets.
 402 
 403   // Get methods return true on found item with LOOKUP_FUNC and FOUND_FUNC is
 404   // called.
 405   template <typename LOOKUP_FUNC, typename FOUND_FUNC>
 406   bool get(Thread* thread, LOOKUP_FUNC& lookup_f, FOUND_FUNC& foundf,
 407            bool* grow_hint = NULL);
 408 
 409   // Returns true true if the item was inserted, duplicates are found with
 410   // LOOKUP_FUNC.
 411   template <typename LOOKUP_FUNC>
 412   bool insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
 413               bool* grow_hint = NULL, bool* clean_hint = NULL) {
 414     return internal_insert(thread, lookup_f, value, grow_hint, clean_hint);
 415   }
 416 
 417   // This does a fast unsafe insert and can thus only be used when there is no
 418   // risk for a duplicates and no other threads uses this table.
 419   bool unsafe_insert(const VALUE& value);
 420 
 421   // Returns true if items was deleted matching LOOKUP_FUNC and
 422   // prior to destruction DELETE_FUNC is called.
 423   template <typename LOOKUP_FUNC, typename DELETE_FUNC>
 424   bool remove(Thread* thread, LOOKUP_FUNC& lookup_f, DELETE_FUNC& del_f) {
 425     return internal_remove(thread, lookup_f, del_f);
 426   }
 427 
 428   // Same without DELETE_FUNC.
 429   template <typename LOOKUP_FUNC>
 430   bool remove(Thread* thread, LOOKUP_FUNC& lookup_f) {
 431     return internal_remove(thread, lookup_f, noOp);
 432   }
 433 
 434   // Visit all items with SCAN_FUNC if no concurrent resize. Takes the resize
 435   // lock to avoid concurrent resizes. Else returns false.
 436   template <typename SCAN_FUNC>
 437   bool try_scan(Thread* thread, SCAN_FUNC& scan_f);
 438 
 439   // Visit all items with SCAN_FUNC when the resize lock is obtained.
 440   template <typename SCAN_FUNC>
 441   void do_scan(Thread* thread, SCAN_FUNC& scan_f);
 442 
 443   // Visit all items with SCAN_FUNC without any protection.
 444   // It will assume there is no other thread accessing this
 445   // table during the safepoint. Must be called with VM thread.
 446   template <typename SCAN_FUNC>
 447   void do_safepoint_scan(SCAN_FUNC& scan_f);
 448 
 449   // Destroying items matching EVALUATE_FUNC, before destroying items
 450   // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
 451   template <typename EVALUATE_FUNC, typename DELETE_FUNC>
 452   bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
 453                        DELETE_FUNC& del_f);
 454 
 455   // Destroying items matching EVALUATE_FUNC, before destroying items
 456   // DELETE_FUNC is called, when the resize lock is successfully obtained.
 457   template <typename EVALUATE_FUNC, typename DELETE_FUNC>
 458   void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
 459 
 460   // Calcuate statistics. Item sizes are calculated with VALUE_SIZE_FUNC.
 461   template <typename VALUE_SIZE_FUNC>
 462   TableStatistics statistics_calculate(Thread* thread, VALUE_SIZE_FUNC& vs_f);
 463 
 464   // Gets statistics if available, if not return old one. Item sizes are calculated with
 465   // VALUE_SIZE_FUNC.
 466   template <typename VALUE_SIZE_FUNC>
 467   TableStatistics statistics_get(Thread* thread, VALUE_SIZE_FUNC& vs_f, TableStatistics old);
 468 
 469   // Writes statistics to the outputStream. Item sizes are calculated with
 470   // VALUE_SIZE_FUNC.
 471   template <typename VALUE_SIZE_FUNC>
 472   void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
 473                      const char* table_name);
 474 
 475   // Moves all nodes from this table to to_cht
 476   bool try_move_nodes_to(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* to_cht);
 477 
 478   // This is a Curiously Recurring Template Pattern (CRPT) interface for the
 479   // specialization.
 480   struct BaseConfig {
 481    public:
 482     // Called when the hash table needs the hash for a VALUE.
 483     static uintx get_hash(const VALUE& value, bool* dead) {
 484       return CONFIG::get_hash(value, dead);
 485     }
 486     // Default node allocation.
 487     static void* allocate_node(size_t size, const VALUE& value);
 488     // Default node reclamation.
 489     static void free_node(void* memory, const VALUE& value);
 490   };
 491 
 492   // Scoped multi getter.
 493   class MultiGetHandle : private ScopedCS {
 494    public:
 495     MultiGetHandle(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht)
 496       : ScopedCS(thread, cht) {}
 497     // In the MultiGetHandle scope you can lookup items matching LOOKUP_FUNC.
 498     // The VALUEs are safe as long as you never save the VALUEs outside the
 499     // scope, e.g. after ~MultiGetHandle().
 500     template <typename LOOKUP_FUNC>
 501     VALUE* get(LOOKUP_FUNC& lookup_f, bool* grow_hint = NULL);
 502   };
 503 
 504  private:
 505   class BucketsOperation;
 506 
 507  public:
 508   class BulkDeleteTask;
 509   class GrowTask;
 510 };
 511 
 512 #endif // SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP