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
32 // A mostly concurrent-hash-table where the read-side is wait-free, inserts are
33 // CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
34 // type kept inside each Node and CONFIG contains hash and allocation methods.
35 // A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
36
37 class Thread;
38 class Mutex;
39
40 template <typename VALUE, typename CONFIG, MEMFLAGS F>
41 class ConcurrentHashTable : public CHeapObj<F> {
42 private:
43 // This is the internal node structure.
44 // Only constructed with placement new from memory allocated with MEMFLAGS of
45 // the InternalTable or user-defined memory.
46 class Node {
47 private:
48 Node * volatile _next;
49 VALUE _value;
50 public:
363
364 // Check for dead items in this table with range. During shrink/grow we cannot
365 // guarantee that we only visit nodes once. To keep it simple caller will
366 // have locked _resize_lock.
367 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
368 void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
369 size_t stop_idx, EVALUATE_FUNC& eval_f,
370 DELETE_FUNC& del_f, bool is_mt = false);
371
372 // Method to delete one items.
373 template <typename LOOKUP_FUNC>
374 void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
375
376 public:
377 ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
378 size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
379 size_t grow_hint = DEFAULT_GROW_HINT);
380
381 ~ConcurrentHashTable();
382
383 size_t get_size_log2(Thread* thread);
384 size_t get_node_size() const { return sizeof(Node); }
385 bool is_max_size_reached() { return _size_limit_reached; }
386
387 // This means no paused bucket resize operation is going to resume
388 // on this table.
389 bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
390
391 // Re-size operations.
392 bool shrink(Thread* thread, size_t size_limit_log2 = 0);
393 bool grow(Thread* thread, size_t size_limit_log2 = 0);
394
395 // All callbacks for get are under critical sections. Other callbacks may be
396 // under critical section or may have locked parts of table. Calling any
397 // methods on the table during a callback is not supported.Only MultiGetHandle
398 // supports multiple gets.
399
400 // Get methods return true on found item with LOOKUP_FUNC and FOUND_FUNC is
401 // called.
402 template <typename LOOKUP_FUNC, typename FOUND_FUNC>
437 template <typename SCAN_FUNC>
438 void do_scan(Thread* thread, SCAN_FUNC& scan_f);
439
440 // Visit all items with SCAN_FUNC without any protection.
441 // It will assume there is no other thread accessing this
442 // table during the safepoint. Must be called with VM thread.
443 template <typename SCAN_FUNC>
444 void do_safepoint_scan(SCAN_FUNC& scan_f);
445
446 // Destroying items matching EVALUATE_FUNC, before destroying items
447 // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
448 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
449 bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
450 DELETE_FUNC& del_f);
451
452 // Destroying items matching EVALUATE_FUNC, before destroying items
453 // DELETE_FUNC is called, when the resize lock is successfully obtained.
454 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
455 void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
456
457 // Writes statistics to the outputStream. Item sizes are calculated with
458 // VALUE_SIZE_FUNC.
459 template <typename VALUE_SIZE_FUNC>
460 void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
461 const char* table_name);
462
463 // Moves all nodes from this table to to_cht
464 bool try_move_nodes_to(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* to_cht);
465
466 // This is a Curiously Recurring Template Pattern (CRPT) interface for the
467 // specialization.
468 struct BaseConfig {
469 public:
470 // Called when the hash table needs the hash for a VALUE.
471 static uintx get_hash(const VALUE& value, bool* dead) {
472 return CONFIG::get_hash(value, dead);
473 }
474 // Default node allocation.
475 static void* allocate_node(size_t size, const VALUE& value);
476 // Default node reclamation.
|
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:
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>
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.
|