8195098: Low latency hashtable for read-mostly scenarios
Summary: This implement a concurrent hashtable using chaining and the GlobalCounter for ABA problems.
Reviewed-by: acorn, coleenp, dcubed, eosterlund, gziemski, mlarsson
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/utilities/concurrentHashTable.hpp Thu May 17 10:32:26 2018 +0200
@@ -0,0 +1,525 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#ifndef SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
+#define SHARE_UTILITIES_CONCURRENT_HASH_TABLE_HPP
+
+// A mostly concurrent-hash-table where the read-side is wait-free, inserts are
+// CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
+// type kept inside each Node and CONFIG contains hash and allocation methods.
+// A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
+
+class Thread;
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+class ConcurrentHashTable : public CHeapObj<F> {
+ private:
+ // This is the internal node structure.
+ // Only constructed with placement new from memory allocated with MEMFLAGS of
+ // the InternalTable or user-defined memory.
+ class Node {
+ private:
+ Node * volatile _next;
+ VALUE _value;
+ public:
+ Node(const VALUE& value, Node* next = NULL)
+ : _next(next), _value(value) {
+ assert((((uintptr_t)this) & ((uintptr_t)0x3)) == 0,
+ "Must 16 bit aligned.");
+ }
+
+ Node* next() const;
+ void set_next(Node* node) { _next = node; }
+ Node* const volatile * next_ptr() { return &_next; }
+
+ VALUE* value() { return &_value; }
+
+ // Creates a node.
+ static Node* create_node(const VALUE& value, Node* next = NULL) {
+ return new (CONFIG::allocate_node(sizeof(Node), value)) Node(value, next);
+ }
+ // Destroys a node.
+ static void destroy_node(Node* node) {
+ CONFIG::free_node((void*)node, node->_value);
+ }
+
+ void print_on(outputStream* st) const {};
+ void print_value_on(outputStream* st) const {};
+ };
+
+ // Only constructed with placement new[] from an array allocated with MEMFLAGS
+ // of InternalTable.
+ class Bucket {
+ private:
+
+ // Embedded state in two low bits in first pointer is a spinlock with 3
+ // states, unlocked, locked, redirect. You must never busy-spin on trylock()
+ // or call lock() without _resize_lock, that would deadlock. Redirect can
+ // only be installed by owner and is the final state of a bucket.
+ // The only two valid flows are:
+ // unlocked -> locked -> unlocked
+ // unlocked -> locked -> redirect
+ // Locked state only applies to an updater.
+ // Reader only check for redirect.
+ Node * volatile _first;
+
+ static const uintptr_t STATE_LOCK_BIT = 0x1;
+ static const uintptr_t STATE_REDIRECT_BIT = 0x2;
+ static const uintptr_t STATE_MASK = 0x3;
+
+ // Get the first pointer unmasked.
+ Node* first_raw() const;
+
+ // Methods to manipulate the embedded.
+ static bool is_state(Node* node, uintptr_t bits) {
+ return (bits & (uintptr_t)node) == bits;
+ }
+
+ static Node* set_state(Node* n, uintptr_t bits) {
+ return (Node*)(bits | (uintptr_t)n);
+ }
+
+ static uintptr_t get_state(Node* node) {
+ return (((uintptr_t)node) & STATE_MASK);
+ }
+
+ static Node* clear_state(Node* node) {
+ return (Node*)(((uintptr_t)node) & (~(STATE_MASK)));
+ }
+
+ static Node* clear_set_state(Node* node, Node* state) {
+ return (Node*)(((uintptr_t)clear_state(node)) ^ get_state(state));
+ }
+
+ public:
+ // A bucket is only one pointer with the embedded state.
+ Bucket() : _first(NULL) {};
+
+ // Get the first pointer unmasked.
+ Node* first() const;
+
+ // Get a pointer to the const first pointer. Do not deference this
+ // pointer, the pointer pointed to _may_ contain an embedded state. Such
+ // pointer should only be used as input to release_assign_node_ptr.
+ Node* const volatile * first_ptr() { return &_first; }
+
+ // This is the only place where a pointer to a Node pointer that potentially
+ // is _first should be changed. Otherwise we destroy the embedded state. We
+ // only give out pointer to const Node pointer to avoid accidental
+ // assignment, thus here we must cast const part away. Method is not static
+ // due to an assert.
+ void release_assign_node_ptr(Node* const volatile * dst, Node* node) const;
+
+ // This method assigns this buckets last Node next ptr to input Node.
+ void release_assign_last_node_next(Node* node);
+
+ // Setting the first pointer must be done with CAS.
+ bool cas_first(Node *node, Node* expect);
+
+ // Returns true if this bucket is redirecting to a new table.
+ // Redirect is a terminal state and will never change.
+ bool have_redirect() const;
+
+ // Return true if this bucket is locked for updates.
+ bool is_locked() const;
+
+ // Return true if this bucket was locked.
+ bool trylock();
+
+ // The bucket might be invalid, due to a concurrent resize. The lock()
+ // method do no respect that and can deadlock if caller do not hold
+ // _resize_lock.
+ void lock();
+
+ // Unlocks this bucket.
+ void unlock();
+
+ // Installs redirect in this bucket.
+ // Prior to doing so you must have successfully locked this bucket.
+ void redirect();
+ };
+
+ // The backing storage table holding the buckets and it's size and mask-bits.
+ // Table is always a power of two for two reasons:
+ // - Re-size can only change the size into half or double
+ // (any pow 2 would also be possible).
+ // - Use masking of hash for bucket index.
+ class InternalTable : public CHeapObj<F> {
+ private:
+ Bucket* _buckets; // Bucket array.
+ public:
+ const size_t _log2_size; // Size in log2.
+ const size_t _size; // Size in log10.
+
+ // The mask used on hash for selecting bucket.
+ // The masked value is guaranteed be to inside the buckets array.
+ const size_t _hash_mask;
+
+ // Create a backing table
+ InternalTable(size_t log2_size);
+ ~InternalTable();
+
+ Bucket* get_buckets() { return _buckets; }
+ Bucket* get_bucket(size_t idx) { return &_buckets[idx]; }
+ };
+
+ // Used as default functor when no functor supplied for some methods.
+ struct NoOp {
+ void operator()(VALUE*) {}
+ const VALUE& operator()() {}
+ void operator()(bool, VALUE*) {}
+ } noOp;
+
+ // For materializing a supplied value.
+ class LazyValueRetrieve {
+ private:
+ const VALUE& _val;
+ public:
+ LazyValueRetrieve(const VALUE& val) : _val(val) {}
+ const VALUE& operator()() { return _val; }
+ };
+
+ InternalTable* _table; // Active table.
+ InternalTable* _new_table; // Table we are resizing to.
+
+ // Default sizes
+ static const size_t DEFAULT_MAX_SIZE_LOG2 = 21;
+ static const size_t DEFAULT_START_SIZE_LOG2 = 13;
+ static const size_t DEFAULT_GROW_HINT = 4; // Chain length
+
+ const size_t _log2_size_limit; // The biggest size.
+ const size_t _log2_start_size; // Start size.
+ const size_t _grow_hint; // Number of linked items
+
+ volatile bool _size_limit_reached;
+
+ // We serialize resizers and other bulk operations which do not support
+ // concurrent resize with this lock.
+ Mutex* _resize_lock;
+ // Since we need to drop mutex for safepoints, but stop other threads from
+ // taking the mutex after a safepoint this bool is the actual state. After
+ // acquiring the mutex you must check if this is already locked. If so you
+ // must drop the mutex until the real lock holder grabs the mutex.
+ volatile Thread* _resize_lock_owner;
+
+ // Return true if lock mutex/state succeeded.
+ bool try_resize_lock(Thread* locker);
+ // Returns when both mutex and state are proper locked.
+ void lock_resize_lock(Thread* locker);
+ // Unlocks mutex and state.
+ void unlock_resize_lock(Thread* locker);
+
+ // This method sets the _invisible_epoch and do a write_synchronize.
+ // Subsequent calls check the state of _invisible_epoch and determine if the
+ // write_synchronize can be avoided. If not, it sets the _invisible_epoch
+ // again and do a write_synchronize.
+ void write_synchonize_on_visible_epoch(Thread* thread);
+ // To be-able to avoid write_synchronize in resize and other bulk operation,
+ // this field keep tracks if a version of the hash-table was ever been seen.
+ // We the working thread pointer as tag for debugging. The _invisible_epoch
+ // can only be used by the owner of _resize_lock.
+ volatile Thread* _invisible_epoch;
+
+ // Scoped critical section, which also handles the invisible epochs.
+ // An invisible epoch/version do not need a write_synchronize().
+ class ScopedCS: public StackObj {
+ protected:
+ Thread* _thread;
+ ConcurrentHashTable<VALUE, CONFIG, F>* _cht;
+ public:
+ ScopedCS(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht);
+ ~ScopedCS();
+ };
+
+
+ // Max number of deletes in one bucket chain during bulk delete.
+ static const size_t BULK_DELETE_LIMIT = 256;
+
+ // Simple getters and setters for the internal table.
+ InternalTable* get_table() const;
+ InternalTable* get_new_table() const;
+ InternalTable* set_table_from_new();
+
+ // Destroys all nodes.
+ void free_nodes();
+
+ // Mask away high bits of hash.
+ static size_t bucket_idx_hash(InternalTable* table, const uintx hash) {
+ return ((size_t)hash) & table->_hash_mask;
+ }
+
+ // Returns bucket for hash for that internal table.
+ Bucket* get_bucket_in(InternalTable* table, const uintx hash) const {
+ size_t bucket_index = bucket_idx_hash(table, hash);
+ return table->get_bucket(bucket_index);
+ }
+
+ // Return correct bucket for reading and handles resizing.
+ Bucket* get_bucket(const uintx hash) const;
+
+ // Return correct bucket for updates and handles resizing.
+ Bucket* get_bucket_locked(Thread* thread, const uintx hash);
+
+ // Finds a node.
+ template <typename LOOKUP_FUNC>
+ Node* get_node(const Bucket* const bucket, LOOKUP_FUNC& lookup_f,
+ bool* have_dead, size_t* loops = NULL) const;
+
+ // Method for shrinking.
+ bool internal_shrink_prolog(Thread* thread, size_t log2_size);
+ void internal_shrink_epilog(Thread* thread);
+ void internal_shrink_range(Thread* thread, size_t start, size_t stop);
+ bool internal_shrink(Thread* thread, size_t size_limit_log2);
+
+ // Methods for growing.
+ bool unzip_bucket(Thread* thread, InternalTable* old_table,
+ InternalTable* new_table, size_t even_index,
+ size_t odd_index);
+ bool internal_grow_prolog(Thread* thread, size_t log2_size);
+ void internal_grow_epilog(Thread* thread);
+ void internal_grow_range(Thread* thread, size_t start, size_t stop);
+ bool internal_grow(Thread* thread, size_t log2_size);
+
+ // Get a value.
+ template <typename LOOKUP_FUNC>
+ VALUE* internal_get(Thread* thread, LOOKUP_FUNC& lookup_f,
+ bool* grow_hint = NULL);
+
+ // Insert which handles a number of cases.
+ template <typename LOOKUP_FUNC, typename VALUE_FUNC, typename CALLBACK_FUNC>
+ bool internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& value_f,
+ CALLBACK_FUNC& callback, bool* grow_hint = NULL);
+
+ // Returns true if an item matching LOOKUP_FUNC is removed.
+ // Calls DELETE_FUNC before destroying the node.
+ template <typename LOOKUP_FUNC, typename DELETE_FUNC>
+ bool internal_remove(Thread* thread, LOOKUP_FUNC& lookup_f,
+ DELETE_FUNC& delete_f);
+
+ // Visits nodes with FUNC.
+ template <typename FUNC>
+ static bool visit_nodes(Bucket* bucket, FUNC& visitor_f);
+
+ // During shrink/grow we cannot guarantee that we only visit nodes once, with
+ // current algorithm. To keep it simple caller will have locked
+ // _resize_lock.
+ template <typename FUNC>
+ void do_scan_locked(Thread* thread, FUNC& scan_f);
+
+ // Check for dead items in a bucket.
+ template <typename EVALUATE_FUNC>
+ size_t delete_check_nodes(Bucket* bucket, EVALUATE_FUNC& eval_f,
+ size_t num_del, Node** ndel);
+
+ // Check for dead items in this table. During shrink/grow we cannot guarantee
+ // that we only visit nodes once. To keep it simple caller will have locked
+ // _resize_lock.
+ template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+ void do_bulk_delete_locked(Thread* thread, EVALUATE_FUNC& eval_f
+ , DELETE_FUNC& del_f) {
+ do_bulk_delete_locked_for(thread, 0, _table->_size, eval_f, del_f);
+ }
+
+ // To have prefetching for a VALUE that is pointer during
+ // do_bulk_delete_locked, we have this helper classes. One for non-pointer
+ // case without prefect and one for pointer with prefect.
+ template <bool b, typename EVALUATE_FUNC>
+ struct HaveDeletables {
+ static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
+ Bucket* prefetch_bucket);
+ };
+ template<typename EVALUATE_FUNC>
+ struct HaveDeletables<true, EVALUATE_FUNC> {
+ static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
+ Bucket* prefetch_bucket);
+ };
+
+ // Check for dead items in this table with range. During shrink/grow we cannot
+ // guarantee that we only visit nodes once. To keep it simple caller will
+ // have locked _resize_lock.
+ template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+ void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
+ size_t stop_idx, EVALUATE_FUNC& eval_f,
+ DELETE_FUNC& del_f);
+
+ // Method to delete one items.
+ template <typename LOOKUP_FUNC>
+ void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
+
+ public:
+ ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
+ size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
+ size_t grow_hint = DEFAULT_GROW_HINT);
+
+ ~ConcurrentHashTable();
+
+ size_t get_size_log2(Thread* thread);
+ size_t get_node_size() const { return sizeof(Node); }
+ bool is_max_size_reached() { return _size_limit_reached; }
+
+ // This means no paused bucket resize operation is going to resume
+ // on this table.
+ bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
+
+ // Re-size operations.
+ bool shrink(Thread* thread, size_t size_limit_log2 = 0);
+ bool grow(Thread* thread, size_t size_limit_log2 = 0);
+
+ // All callbacks for get are under critical sections. Other callbacks may be
+ // under critical section or may have locked parts of table. Calling any
+ // methods on the table during a callback is not supported.Only MultiGetHandle
+ // supports multiple gets.
+
+ // LOOKUP_FUNC is matching methods, VALUE_FUNC creates value to be inserted
+ // and CALLBACK_FUNC is called with new or old value. Returns true if the
+ // value already exists.
+ template <typename LOOKUP_FUNC, typename VALUE_FUNC, typename CALLBACK_FUNC>
+ bool get_insert_lazy(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& val_f,
+ CALLBACK_FUNC& callback_f, bool* grow_hint = NULL) {
+ return !internal_insert(thread, lookup_f, val_f, callback_f, grow_hint);
+ }
+
+ // Same without CALLBACK_FUNC.
+ template <typename LOOKUP_FUNC, typename VALUE_FUNC>
+ bool get_insert_lazy(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& val_f,
+ bool* grow_hint = NULL) {
+ return get_insert_lazy(thread, lookup_f, val_f, noOp, grow_hint);
+ }
+
+ // Same without VALUE_FUNC.
+ template <typename LOOKUP_FUNC, typename CALLBACK_FUNC>
+ bool get_insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
+ CALLBACK_FUNC& callback_f, bool* grow_hint = NULL) {
+ LazyValueRetrieve vp(value);
+ return get_insert_lazy(thread, lookup_f, vp, callback_f, grow_hint);
+ }
+
+ // Same without CALLBACK_FUNC and VALUE_FUNC.
+ template <typename LOOKUP_FUNC>
+ bool get_insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
+ bool* grow_hint = NULL) {
+ return get_insert(thread, lookup_f, value, noOp, grow_hint);
+ }
+
+ // Get methods return true on found item with LOOKUP_FUNC and FOUND_FUNC is
+ // called.
+ template <typename LOOKUP_FUNC, typename FOUND_FUNC>
+ bool get(Thread* thread, LOOKUP_FUNC& lookup_f, FOUND_FUNC& foundf,
+ bool* grow_hint = NULL);
+
+ // Return a copy of an item found with LOOKUP_FUNC.
+ template <typename LOOKUP_FUNC>
+ VALUE get_copy(Thread* thread, LOOKUP_FUNC& lookup_f, bool* grow_hint = NULL);
+
+ // Returns true true if the item was inserted, duplicates are found with
+ // LOOKUP_FUNC.
+ template <typename LOOKUP_FUNC>
+ bool insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
+ bool* grow_hint = NULL) {
+ LazyValueRetrieve vp(value);
+ return internal_insert(thread, lookup_f, vp, noOp, grow_hint);
+ }
+
+ // This does a fast unsafe insert and can thus only be used when there is no
+ // risk for a duplicates and no other threads uses this table.
+ bool unsafe_insert(const VALUE& value);
+
+ // Returns true if items was deleted matching LOOKUP_FUNC and
+ // prior to destruction DELETE_FUNC is called.
+ template <typename LOOKUP_FUNC, typename DELETE_FUNC>
+ bool remove(Thread* thread, LOOKUP_FUNC& lookup_f, DELETE_FUNC& del_f) {
+ return internal_remove(thread, lookup_f, del_f);
+ }
+
+ // Same without DELETE_FUNC.
+ template <typename LOOKUP_FUNC>
+ bool remove(Thread* thread, LOOKUP_FUNC& lookup_f) {
+ return internal_remove(thread, lookup_f, noOp);
+ }
+
+ // Visit all items with SCAN_FUNC if no concurrent resize. Takes the resize
+ // lock to avoid concurrent resizes. Else returns false.
+ template <typename SCAN_FUNC>
+ bool try_scan(Thread* thread, SCAN_FUNC& scan_f);
+
+ // Visit all items with SCAN_FUNC when the resize lock is obtained.
+ template <typename SCAN_FUNC>
+ void do_scan(Thread* thread, SCAN_FUNC& scan_f);
+
+ // Destroying items matching EVALUATE_FUNC, before destroying items
+ // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
+ template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+ bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
+ DELETE_FUNC& del_f);
+
+ // Destroying items matching EVALUATE_FUNC, before destroying items
+ // DELETE_FUNC is called, when the resize lock is successfully obtained.
+ template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+ void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
+
+ // Writes statistics to the outputStream. Item sizes are calculated with
+ // VALUE_SIZE_FUNC.
+ template <typename VALUE_SIZE_FUNC>
+ void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
+ const char* table_name);
+
+ // This is a Curiously Recurring Template Pattern (CRPT) interface for the
+ // specialization.
+ struct BaseConfig {
+ public:
+ // Called when the hash table needs the hash for a VALUE.
+ static uintx get_hash(const VALUE& value, bool* dead) {
+ return CONFIG::get_hash(value, dead);
+ }
+ // On get_copy if no value is found then this value is returned.
+ static const VALUE& notfound() {
+ return CONFIG::notfound();
+ }
+ // Default node allocation.
+ static void* allocate_node(size_t size, const VALUE& value);
+ // Default node reclamation.
+ static void free_node(void* memory, const VALUE& value);
+ };
+
+ // Scoped multi getter.
+ class MultiGetHandle : private ScopedCS {
+ public:
+ MultiGetHandle(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht)
+ : ScopedCS(thread, cht) {}
+ // In the MultiGetHandle scope you can lookup items matching LOOKUP_FUNC.
+ // The VALUEs are safe as long as you never save the VALUEs outside the
+ // scope, e.g. after ~MultiGetHandle().
+ template <typename LOOKUP_FUNC>
+ VALUE* get(LOOKUP_FUNC& lookup_f, bool* grow_hint = NULL);
+ };
+
+ private:
+ class BucketsOperation;
+
+ public:
+ class BulkDeleteTask;
+ class GrowTask;
+};
+
+#endif // include guard
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/utilities/concurrentHashTable.inline.hpp Thu May 17 10:32:26 2018 +0200
@@ -0,0 +1,1216 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#ifndef SHARE_UTILITIES_CONCURRENT_HASH_TABLE_INLINE_HPP
+#define SHARE_UTILITIES_CONCURRENT_HASH_TABLE_INLINE_HPP
+
+#include "memory/allocation.inline.hpp"
+#include "runtime/atomic.hpp"
+#include "runtime/orderAccess.inline.hpp"
+#include "runtime/prefetch.inline.hpp"
+#include "utilities/concurrentHashTable.hpp"
+#include "utilities/globalCounter.inline.hpp"
+#include "utilities/numberSeq.hpp"
+#include "utilities/spinYield.hpp"
+
+// 2^30 = 1G buckets
+#define SIZE_BIG_LOG2 30
+// 2^5 = 32 buckets
+#define SIZE_SMALL_LOG2 5
+
+// Number from spinYield.hpp. In some loops SpinYield would be unfair.
+#define SPINPAUSES_PER_YIELD 8192
+
+#ifdef ASSERT
+#ifdef _LP64
+// Two low bits are not usable.
+static const void* POISON_PTR = (void*)UCONST64(0xfbadbadbadbadbac);
+#else
+// Two low bits are not usable.
+static const void* POISON_PTR = (void*)0xffbadbac;
+#endif
+#endif
+
+// Node
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::Node*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ Node::next() const
+{
+ return OrderAccess::load_acquire(&_next);
+}
+
+// Bucket
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::Node*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::first_raw() const
+{
+ return OrderAccess::load_acquire(&_first);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::release_assign_node_ptr(
+ typename ConcurrentHashTable<VALUE, CONFIG, F>::Node* const volatile * dst,
+ typename ConcurrentHashTable<VALUE, CONFIG, F>::Node* node) const
+{
+ // Due to this assert this methods is not static.
+ assert(is_locked(), "Must be locked.");
+ Node** tmp = (Node**)dst;
+ OrderAccess::release_store(tmp, clear_set_state(node, *dst));
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::Node*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::first() const
+{
+ // We strip the states bit before returning the ptr.
+ return clear_state(OrderAccess::load_acquire(&_first));
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::have_redirect() const
+{
+ return is_state(first_raw(), STATE_REDIRECT_BIT);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::is_locked() const
+{
+ return is_state(first_raw(), STATE_LOCK_BIT);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::lock()
+{
+ int i = 0;
+ // SpinYield would be unfair here
+ while (!this->trylock()) {
+ if ((++i) == SPINPAUSES_PER_YIELD) {
+ // On contemporary OS yielding will give CPU to another runnable thread if
+ // there is no CPU available.
+ os::naked_yield();
+ i = 0;
+ } else {
+ SpinPause();
+ }
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::release_assign_last_node_next(
+ typename ConcurrentHashTable<VALUE, CONFIG, F>::Node* node)
+{
+ assert(is_locked(), "Must be locked.");
+ Node* const volatile * ret = first_ptr();
+ while (clear_state(*ret) != NULL) {
+ ret = clear_state(*ret)->next_ptr();
+ }
+ release_assign_node_ptr(ret, node);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::cas_first(typename ConcurrentHashTable<VALUE, CONFIG, F>::Node* node,
+ typename ConcurrentHashTable<VALUE, CONFIG, F>::Node* expect
+ )
+{
+ if (is_locked()) {
+ return false;
+ }
+ if (Atomic::cmpxchg(node, &_first, expect) == expect) {
+ return true;
+ }
+ return false;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::trylock()
+{
+ if (is_locked()) {
+ return false;
+ }
+ // We will expect a clean first pointer.
+ Node* tmp = first();
+ if (Atomic::cmpxchg(set_state(tmp, STATE_LOCK_BIT), &_first, tmp) == tmp) {
+ return true;
+ }
+ return false;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::unlock()
+{
+ assert(is_locked(), "Must be locked.");
+ assert(!have_redirect(),
+ "Unlocking a bucket after it has reached terminal state.");
+ OrderAccess::release_store(&_first, clear_state(first()));
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ Bucket::redirect()
+{
+ assert(is_locked(), "Must be locked.");
+ OrderAccess::release_store(&_first, set_state(_first, STATE_REDIRECT_BIT));
+}
+
+// InternalTable
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ InternalTable::InternalTable(size_t log2_size)
+ : _log2_size(log2_size), _size(((size_t)1ul) << _log2_size),
+ _hash_mask(~(~((size_t)0) << _log2_size))
+{
+ assert(_log2_size >= SIZE_SMALL_LOG2 && _log2_size <= SIZE_BIG_LOG2,
+ "Bad size");
+ void* memory = NEW_C_HEAP_ARRAY(Bucket, _size, F);
+ _buckets = new (memory) Bucket[_size];
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ InternalTable::~InternalTable()
+{
+ FREE_C_HEAP_ARRAY(Bucket, _buckets);
+}
+
+// ScopedCS
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ ScopedCS::ScopedCS(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht)
+ : _thread(thread), _cht(cht)
+{
+ GlobalCounter::critical_section_begin(_thread);
+ // This version is published now.
+ if (OrderAccess::load_acquire(&_cht->_invisible_epoch) != NULL) {
+ OrderAccess::release_store_fence(&_cht->_invisible_epoch, (Thread*)NULL);
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ ScopedCS::~ScopedCS()
+{
+ GlobalCounter::critical_section_end(_thread);
+}
+
+// BaseConfig
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void* ConcurrentHashTable<VALUE, CONFIG, F>::
+ BaseConfig::allocate_node(size_t size, const VALUE& value)
+{
+ return AllocateHeap(size, F);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ BaseConfig::free_node(void* memory, const VALUE& value)
+{
+ FreeHeap(memory);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC>
+inline VALUE* ConcurrentHashTable<VALUE, CONFIG, F>::
+ MultiGetHandle::get(LOOKUP_FUNC& lookup_f, bool* grow_hint)
+{
+ return ScopedCS::_cht->internal_get(ScopedCS::_thread, lookup_f, grow_hint);
+}
+
+// HaveDeletables
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename EVALUATE_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ HaveDeletables<true, EVALUATE_FUNC>::have_deletable(Bucket* bucket,
+ EVALUATE_FUNC& eval_f,
+ Bucket* prefetch_bucket)
+{
+ // Instantiated for pointer type (true), so we can use prefetch.
+ // When visiting all Nodes doing this prefetch give around 30%.
+ Node* pref = prefetch_bucket != NULL ? prefetch_bucket->first() : NULL;
+ for (Node* next = bucket->first(); next != NULL ; next = next->next()) {
+ if (pref != NULL) {
+ Prefetch::read(*pref->value(), 0);
+ pref = pref->next();
+ }
+ if (next->next() != NULL) {
+ Prefetch::read(*next->next()->value(), 0);
+ }
+ if (eval_f(next->value())) {
+ return true;
+ }
+ }
+ return false;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <bool b, typename EVALUATE_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ HaveDeletables<b, EVALUATE_FUNC>::have_deletable(Bucket* bucket,
+ EVALUATE_FUNC& eval_f,
+ Bucket* preb)
+{
+ for (Node* next = bucket->first(); next != NULL ; next = next->next()) {
+ if (eval_f(next->value())) {
+ return true;
+ }
+ }
+ return false;
+}
+
+// ConcurrentHashTable
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ write_synchonize_on_visible_epoch(Thread* thread)
+{
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ OrderAccess::fence(); // Prevent below load from floating up.
+ // If no reader saw this version we can skip write_synchronize.
+ if (OrderAccess::load_acquire(&_invisible_epoch) == thread) {
+ return;
+ }
+ assert(_invisible_epoch == NULL, "Two thread doing bulk operations");
+ // We set this/next version that we are synchronizing for to not published.
+ // A reader will zero this flag if it reads this/next version.
+ OrderAccess::release_store(&_invisible_epoch, thread);
+ GlobalCounter::write_synchronize();
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ try_resize_lock(Thread* locker)
+{
+ if (_resize_lock->try_lock()) {
+ if (_resize_lock_owner != NULL) {
+ assert(locker != _resize_lock_owner, "Already own lock");
+ // We got mutex but internal state is locked.
+ _resize_lock->unlock();
+ return false;
+ }
+ } else {
+ return false;
+ }
+ _invisible_epoch = 0;
+ _resize_lock_owner = locker;
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ lock_resize_lock(Thread* locker)
+{
+ size_t i = 0;
+ // If lock is hold by some other thread, the chances that it is return quick
+ // is low. So we will prefer yielding.
+ SpinYield yield(1, 512);
+ do {
+ _resize_lock->lock_without_safepoint_check();
+ // If holder of lock dropped mutex for safepoint mutex might be unlocked,
+ // and _resize_lock_owner will contain the owner.
+ if (_resize_lock_owner != NULL) {
+ assert(locker != _resize_lock_owner, "Already own lock");
+ // We got mutex but internal state is locked.
+ _resize_lock->unlock();
+ yield.wait();
+ } else {
+ break;
+ }
+ } while(true);
+ _resize_lock_owner = locker;
+ _invisible_epoch = 0;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ unlock_resize_lock(Thread* locker)
+{
+ _invisible_epoch = 0;
+ assert(locker == _resize_lock_owner, "Not unlocked by locker.");
+ _resize_lock_owner = NULL;
+ _resize_lock->unlock();
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ free_nodes()
+{
+ // We assume we are not MT during freeing.
+ for (size_t node_it = 0; node_it < _table->_size; node_it++) {
+ Bucket* bucket = _table->get_buckets() + node_it;
+ Node* node = bucket->first();
+ while (node != NULL) {
+ Node* free_node = node;
+ node = node->next();
+ Node::destroy_node(free_node);
+ }
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::InternalTable*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_table() const
+{
+ return OrderAccess::load_acquire(&_table);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::InternalTable*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_new_table() const
+{
+ return OrderAccess::load_acquire(&_new_table);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::InternalTable*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ set_table_from_new()
+{
+ InternalTable* old_table = _table;
+ // Publish the new table.
+ OrderAccess::release_store(&_table, _new_table);
+ // All must see this.
+ GlobalCounter::write_synchronize();
+ // _new_table not read any more.
+ _new_table = NULL;
+ DEBUG_ONLY(_new_table = (InternalTable*)POISON_PTR;)
+ return old_table;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_grow_range(Thread* thread, size_t start, size_t stop)
+{
+ assert(stop <= _table->_size, "Outside backing array");
+ assert(_new_table != NULL, "Grow not proper setup before start");
+ // The state is also copied here. Hence all buckets in new table will be
+ // locked. I call the siblings odd/even, where even have high bit 0 and odd
+ // have high bit 1.
+ for (size_t even_index = start; even_index < stop; even_index++) {
+ Bucket* bucket = _table->get_bucket(even_index);
+
+ bucket->lock();
+
+ size_t odd_index = even_index + _table->_size;
+ _new_table->get_buckets()[even_index] = *bucket;
+ _new_table->get_buckets()[odd_index] = *bucket;
+
+ // Moves lockers go to new table, where they will wait until unlock() below.
+ bucket->redirect(); /* Must release stores above */
+
+ // When this is done we have separated the nodes into corresponding buckets
+ // in new table.
+ if (!unzip_bucket(thread, _table, _new_table, even_index, odd_index)) {
+ // If bucket is empty, unzip does nothing.
+ // We must make sure readers go to new table before we poison the bucket.
+ DEBUG_ONLY(GlobalCounter::write_synchronize();)
+ }
+
+ // Unlock for writes into the new table buckets.
+ _new_table->get_bucket(even_index)->unlock();
+ _new_table->get_bucket(odd_index)->unlock();
+
+ DEBUG_ONLY(
+ bucket->release_assign_node_ptr(
+ _table->get_bucket(even_index)->first_ptr(), (Node*)POISON_PTR);
+ )
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC, typename DELETE_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_remove(Thread* thread, LOOKUP_FUNC& lookup_f, DELETE_FUNC& delete_f)
+{
+ Bucket* bucket = get_bucket_locked(thread, lookup_f.get_hash());
+ assert(bucket->is_locked(), "Must be locked.");
+ Node* const volatile * rem_n_prev = bucket->first_ptr();
+ Node* rem_n = bucket->first();
+ bool have_dead = false;
+ while (rem_n != NULL) {
+ if (lookup_f.equals(rem_n->value(), &have_dead)) {
+ bucket->release_assign_node_ptr(rem_n_prev, rem_n->next());
+ break;
+ } else {
+ rem_n_prev = rem_n->next_ptr();
+ rem_n = rem_n->next();
+ }
+ }
+
+ bucket->unlock();
+
+ if (rem_n == NULL) {
+ return false;
+ }
+ // Publish the deletion.
+ GlobalCounter::write_synchronize();
+ delete_f(rem_n->value());
+ Node::destroy_node(rem_n);
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ do_bulk_delete_locked_for(Thread* thread, size_t start_idx, size_t stop_idx,
+ EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f)
+{
+ // Here we have resize lock so table is SMR safe, and there is no new
+ // table. Can do this in parallel if we want.
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ Node* ndel[BULK_DELETE_LIMIT];
+ InternalTable* table = get_table();
+ assert(start_idx < stop_idx, "Must be");
+ assert(stop_idx <= _table->_size, "Must be");
+ // Here manual do critical section since we don't want to take the cost of
+ // locking the bucket if there is nothing to delete. But we can have
+ // concurrent single deletes. The _invisible_epoch can only be used by the
+ // owner of _resize_lock, us here. There we should not changed it in our
+ // own read-side.
+ GlobalCounter::critical_section_begin(thread);
+ for (size_t bucket_it = start_idx; bucket_it < stop_idx; bucket_it++) {
+ Bucket* bucket = _table->get_bucket(bucket_it);
+ Bucket* prefetch_bucket = (bucket_it+1) < stop_idx ?
+ _table->get_bucket(bucket_it+1) : NULL;
+
+ if (!HaveDeletables<IsPointer<VALUE>::value, EVALUATE_FUNC>::
+ have_deletable(bucket, eval_f, prefetch_bucket)) {
+ // Nothing to remove in this bucket.
+ continue;
+ }
+
+ GlobalCounter::critical_section_end(thread);
+ // We left critical section but the bucket cannot be removed while we hold
+ // the _resize_lock.
+ bucket->lock();
+ size_t nd = delete_check_nodes(bucket, eval_f, BULK_DELETE_LIMIT, ndel);
+ bucket->unlock();
+ write_synchonize_on_visible_epoch(thread);
+ for (size_t node_it = 0; node_it < nd; node_it++) {
+ del_f(ndel[node_it]->value());
+ Node::destroy_node(ndel[node_it]);
+ DEBUG_ONLY(ndel[node_it] = (Node*)POISON_PTR;)
+ }
+ GlobalCounter::critical_section_begin(thread);
+ }
+ GlobalCounter::critical_section_end(thread);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f)
+{
+ size_t dels = 0;
+ Node* ndel[BULK_DELETE_LIMIT];
+ Node* const volatile * rem_n_prev = bucket->first_ptr();
+ Node* rem_n = bucket->first();
+ while (rem_n != NULL) {
+ bool is_dead = false;
+ lookup_f.equals(rem_n->value(), &is_dead);
+ if (is_dead) {
+ ndel[dels++] = rem_n;
+ bucket->release_assign_node_ptr(rem_n_prev, rem_n->next());
+ rem_n = rem_n->next();
+ if (dels == BULK_DELETE_LIMIT) {
+ break;
+ }
+ } else {
+ rem_n_prev = rem_n->next_ptr();
+ rem_n = rem_n->next();
+ }
+ }
+ if (dels > 0) {
+ GlobalCounter::write_synchronize();
+ for (size_t node_it = 0; node_it < dels; node_it++) {
+ Node::destroy_node(ndel[node_it]);
+ DEBUG_ONLY(ndel[node_it] = (Node*)POISON_PTR;)
+ }
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::Bucket*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_bucket(uintx hash) const
+{
+ InternalTable* table = get_table();
+ Bucket* bucket = get_bucket_in(table, hash);
+ if (bucket->have_redirect()) {
+ table = get_new_table();
+ bucket = get_bucket_in(table, hash);
+ }
+ return bucket;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline typename ConcurrentHashTable<VALUE, CONFIG, F>::Bucket*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_bucket_locked(Thread* thread, const uintx hash)
+{
+ Bucket* bucket;
+ int i = 0;
+ // SpinYield would be unfair here
+ while(true) {
+ {
+ // We need a critical section to protect the table itself. But if we fail
+ // we must leave critical section otherwise we would deadlock.
+ ScopedCS cs(thread, this);
+ bucket = get_bucket(hash);
+ if (bucket->trylock()) {
+ break; /* ends critical section */
+ }
+ } /* ends critical section */
+ if ((++i) == SPINPAUSES_PER_YIELD) {
+ // On contemporary OS yielding will give CPU to another runnable thread if
+ // there is no CPU available.
+ os::naked_yield();
+ i = 0;
+ } else {
+ SpinPause();
+ }
+ }
+ return bucket;
+}
+
+// Always called within critical section
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC>
+typename ConcurrentHashTable<VALUE, CONFIG, F>::Node*
+ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_node(const Bucket* const bucket, LOOKUP_FUNC& lookup_f,
+ bool* have_dead, size_t* loops) const
+{
+ size_t loop_count = 0;
+ Node* node = bucket->first();
+ while (node != NULL) {
+ bool is_dead = false;
+ ++loop_count;
+ if (lookup_f.equals(node->value(), &is_dead)) {
+ break;
+ }
+ if (is_dead && !(*have_dead)) {
+ *have_dead = true;
+ }
+ node = node->next();
+ }
+ if (loops != NULL) {
+ *loops = loop_count;
+ }
+ return node;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ unzip_bucket(Thread* thread, InternalTable* old_table,
+ InternalTable* new_table, size_t even_index, size_t odd_index)
+{
+ Node* aux = old_table->get_bucket(even_index)->first();
+ if (aux == NULL) {
+ // This is an empty bucket and in debug we poison first ptr in bucket.
+ // Therefore we must make sure no readers are looking at this bucket.
+ // If we don't do a write_synch here, caller must do it.
+ return false;
+ }
+ Node* delete_me = NULL;
+ Node* const volatile * even = new_table->get_bucket(even_index)->first_ptr();
+ Node* const volatile * odd = new_table->get_bucket(odd_index)->first_ptr();
+ while (aux != NULL) {
+ bool dead_hash = false;
+ size_t aux_hash = CONFIG::get_hash(*aux->value(), &dead_hash);
+ if (dead_hash) {
+ delete_me = aux;
+ // This item is dead, move both list to next
+ new_table->get_bucket(odd_index)->release_assign_node_ptr(odd,
+ aux->next());
+ new_table->get_bucket(even_index)->release_assign_node_ptr(even,
+ aux->next());
+ } else {
+ size_t aux_index = bucket_idx_hash(new_table, aux_hash);
+ if (aux_index == even_index) {
+ // This is a even, so move odd to aux/even next
+ new_table->get_bucket(odd_index)->release_assign_node_ptr(odd,
+ aux->next());
+ // Keep in even list
+ even = aux->next_ptr();
+ } else if (aux_index == odd_index) {
+ // This is a odd, so move odd to aux/odd next
+ new_table->get_bucket(even_index)->release_assign_node_ptr(even,
+ aux->next());
+ // Keep in odd list
+ odd = aux->next_ptr();
+ } else {
+ fatal("aux_index does not match even or odd indices");
+ }
+ }
+ aux = aux->next();
+
+ // We can only move 1 pointer otherwise a reader might be moved to the wrong
+ // chain. E.g. looking for even hash value but got moved to the odd bucket
+ // chain.
+ write_synchonize_on_visible_epoch(thread);
+ if (delete_me != NULL) {
+ Node::destroy_node(delete_me);
+ delete_me = NULL;
+ }
+ }
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_shrink_prolog(Thread* thread, size_t log2_size)
+{
+ if (!try_resize_lock(thread)) {
+ return false;
+ }
+
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+
+ if (_table->_log2_size == _log2_start_size ||
+ _table->_log2_size <= log2_size) {
+ unlock_resize_lock(thread);
+ return false;
+ }
+
+ _new_table = new InternalTable(_table->_log2_size - 1);
+
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_shrink_epilog(Thread* thread)
+{
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ assert(_resize_lock_owner, "Should be locked");
+
+ InternalTable* old_table = set_table_from_new();
+ _size_limit_reached = false;
+ unlock_resize_lock(thread);
+#ifdef ASSERT
+ for (size_t i = 0; i < old_table->_size; i++) {
+ assert(old_table->get_bucket(i++)->first() == POISON_PTR,
+ "No poison found");
+ }
+#endif
+ // ABA safe, old_table not visible to any other threads.
+ delete old_table;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_shrink_range(Thread* thread, size_t start, size_t stop)
+{
+ // The state is also copied here.
+ // Hence all buckets in new table will be locked.
+ for (size_t bucket_it = start; bucket_it < stop; bucket_it++) {
+ size_t even_hash_index = bucket_it; // High bit 0
+ size_t odd_hash_index = bucket_it + _new_table->_size; // High bit 1
+
+ Bucket* b_old_even = _table->get_bucket(even_hash_index);
+ Bucket* b_old_odd = _table->get_bucket(odd_hash_index);
+
+ b_old_even->lock();
+ b_old_odd->lock();
+
+ _new_table->get_buckets()[bucket_it] = *b_old_even;
+
+ // Put chains together.
+ _new_table->get_bucket(bucket_it)->
+ release_assign_last_node_next(*(b_old_odd->first_ptr()));
+
+ b_old_even->redirect();
+ b_old_odd->redirect();
+
+ write_synchonize_on_visible_epoch(thread);
+
+ // Unlock for writes into new smaller table.
+ _new_table->get_bucket(bucket_it)->unlock();
+
+ DEBUG_ONLY(b_old_even->release_assign_node_ptr(b_old_even->first_ptr(),
+ (Node*)POISON_PTR);)
+ DEBUG_ONLY(b_old_odd->release_assign_node_ptr(b_old_odd->first_ptr(),
+ (Node*)POISON_PTR);)
+ }
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_shrink(Thread* thread, size_t log2_size)
+{
+ if (!internal_shrink_prolog(thread, log2_size)) {
+ assert(!_resize_lock->owned_by_self(), "Re-size lock held");
+ return false;
+ }
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ assert(_resize_lock_owner == thread, "Should be locked by me");
+ internal_shrink_range(thread, 0, _new_table->_size);
+ internal_shrink_epilog(thread);
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_grow_prolog(Thread* thread, size_t log2_size)
+{
+ // This double checking of _size_limit_reached/is_max_size_reached()
+ // we only do in grow path, since grow means high load on table
+ // while shrink means low load.
+ if (is_max_size_reached()) {
+ return false;
+ }
+ if (!try_resize_lock(thread)) {
+ // Either we have an ongoing resize or an operation which doesn't want us
+ // to resize now.
+ return false;
+ }
+ if (is_max_size_reached() || _table->_log2_size >= log2_size) {
+ unlock_resize_lock(thread);
+ return false;
+ }
+
+ _new_table = new InternalTable(_table->_log2_size + 1);
+
+ if (_new_table->_log2_size == _log2_size_limit) {
+ _size_limit_reached = true;
+ }
+
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_grow_epilog(Thread* thread)
+{
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ assert(_resize_lock_owner, "Should be locked");
+
+ InternalTable* old_table = set_table_from_new();
+ unlock_resize_lock(thread);
+#ifdef ASSERT
+ for (size_t i = 0; i < old_table->_size; i++) {
+ assert(old_table->get_bucket(i++)->first() == POISON_PTR,
+ "No poison found");
+ }
+#endif
+ // ABA safe, old_table not visible to any other threads.
+ delete old_table;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_grow(Thread* thread, size_t log2_size)
+{
+ if (!internal_grow_prolog(thread, log2_size)) {
+ assert(!_resize_lock->owned_by_self(), "Re-size lock held");
+ return false;
+ }
+ assert(_resize_lock->owned_by_self(), "Re-size lock not held");
+ assert(_resize_lock_owner == thread, "Should be locked by me");
+ internal_grow_range(thread, 0, _table->_size);
+ internal_grow_epilog(thread);
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ return true;
+}
+
+// Always called within critical section
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC>
+inline VALUE* ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_get(Thread* thread, LOOKUP_FUNC& lookup_f, bool* grow_hint)
+{
+ bool clean = false;
+ size_t loops = 0;
+ VALUE* ret = NULL;
+
+ const Bucket* bucket = get_bucket(lookup_f.get_hash());
+ Node* node = get_node(bucket, lookup_f, &clean, &loops);
+ if (node != NULL) {
+ ret = node->value();
+ }
+ if (grow_hint != NULL) {
+ *grow_hint = loops > _grow_hint;
+ }
+
+ return ret;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC, typename VALUE_FUNC, typename CALLBACK_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& value_f,
+ CALLBACK_FUNC& callback, bool* grow_hint)
+{
+ bool ret = false;
+ bool clean = false;
+ bool locked;
+ size_t loops = 0;
+ size_t i = 0;
+ Node* new_node = NULL;
+ uintx hash = lookup_f.get_hash();
+ while (true) {
+ {
+ ScopedCS cs(thread, this); /* protected the table/bucket */
+ Bucket* bucket = get_bucket(hash);
+
+ Node* first_at_start = bucket->first();
+ Node* old = get_node(bucket, lookup_f, &clean, &loops);
+ if (old == NULL) {
+ // No duplicate found.
+ if (new_node == NULL) {
+ new_node = Node::create_node(value_f(), first_at_start);
+ } else {
+ new_node->set_next(first_at_start);
+ }
+ if (bucket->cas_first(new_node, first_at_start)) {
+ callback(true, new_node->value());
+ new_node = NULL;
+ ret = true;
+ break; /* leave critical section */
+ }
+ // CAS failed we must leave critical section and retry.
+ locked = bucket->is_locked();
+ } else {
+ // There is a duplicate.
+ callback(false, old->value());
+ break; /* leave critical section */
+ }
+ } /* leave critical section */
+ i++;
+ if (locked) {
+ os::naked_yield();
+ } else {
+ SpinPause();
+ }
+ }
+
+ if (new_node != NULL) {
+ // CAS failed and a duplicate was inserted, we must free this node.
+ Node::destroy_node(new_node);
+ } else if (i == 0 && clean) {
+ // We only do cleaning on fast inserts.
+ Bucket* bucket = get_bucket_locked(thread, lookup_f.get_hash());
+ assert(bucket->is_locked(), "Must be locked.");
+ delete_in_bucket(thread, bucket, lookup_f);
+ bucket->unlock();
+ }
+
+ if (grow_hint != NULL) {
+ *grow_hint = loops > _grow_hint;
+ }
+
+ return ret;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ visit_nodes(Bucket* bucket, FUNC& visitor_f)
+{
+ Node* current_node = bucket->first();
+ while (current_node != NULL) {
+ if (!visitor_f(current_node->value())) {
+ return false;
+ }
+ current_node = current_node->next();
+ }
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ do_scan_locked(Thread* thread, FUNC& scan_f)
+{
+ assert(_resize_lock->owned_by_self() ||
+ (thread->is_VM_thread() && SafepointSynchronize::is_at_safepoint()),
+ "Re-size lock not held or not VMThread at safepoint");
+ // We can do a critical section over the entire loop but that would block
+ // updates for a long time. Instead we choose to block resizes.
+ InternalTable* table = get_table();
+ for (size_t bucket_it = 0; bucket_it < _table->_size; bucket_it++) {
+ ScopedCS cs(thread, this);
+ if (!visit_nodes(_table->get_bucket(bucket_it), scan_f)) {
+ break; /* ends critical section */
+ }
+ } /* ends critical section */
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename EVALUATE_FUNC>
+inline size_t ConcurrentHashTable<VALUE, CONFIG, F>::
+ delete_check_nodes(Bucket* bucket, EVALUATE_FUNC& eval_f,
+ size_t num_del, Node** ndel)
+{
+ size_t dels = 0;
+ Node* const volatile * rem_n_prev = bucket->first_ptr();
+ Node* rem_n = bucket->first();
+ while (rem_n != NULL) {
+ if (eval_f(rem_n->value())) {
+ ndel[dels++] = rem_n;
+ bucket->release_assign_node_ptr(rem_n_prev, rem_n->next());
+ rem_n = rem_n->next();
+ if (dels == num_del) {
+ break;
+ }
+ } else {
+ rem_n_prev = rem_n->next_ptr();
+ rem_n = rem_n->next();
+ }
+ }
+ return dels;
+}
+
+// Constructor
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ ConcurrentHashTable(size_t log2size, size_t log2size_limit, size_t grow_hint)
+ : _new_table(NULL), _log2_start_size(log2size),
+ _log2_size_limit(log2size_limit), _grow_hint(grow_hint),
+ _size_limit_reached(false), _resize_lock_owner(NULL),
+ _invisible_epoch(0)
+{
+ _resize_lock =
+ new Mutex(Mutex::leaf, "ConcurrentHashTable", false,
+ Monitor::_safepoint_check_never);
+ _table = new InternalTable(log2size);
+ assert(log2size_limit >= log2size, "bad ergo");
+ _size_limit_reached = _table->_log2_size == _log2_size_limit;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline ConcurrentHashTable<VALUE, CONFIG, F>::
+ ~ConcurrentHashTable()
+{
+ delete _resize_lock;
+ free_nodes();
+ delete _table;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline size_t ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_size_log2(Thread* thread)
+{
+ ScopedCS cs(thread, this);
+ return _table->_log2_size;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ shrink(Thread* thread, size_t size_limit_log2)
+{
+ size_t tmp = size_limit_log2 == 0 ? _log2_start_size : size_limit_log2;
+ bool ret = internal_shrink(thread, tmp);
+ return ret;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ grow(Thread* thread, size_t size_limit_log2)
+{
+ size_t tmp = size_limit_log2 == 0 ? _log2_size_limit : size_limit_log2;
+ return internal_grow(thread, tmp);
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC, typename FOUND_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ get(Thread* thread, LOOKUP_FUNC& lookup_f, FOUND_FUNC& found_f, bool* grow_hint)
+{
+ bool ret = false;
+ ScopedCS cs(thread, this);
+ VALUE* val = internal_get(thread, lookup_f, grow_hint);
+ if (val != NULL) {
+ found_f(val);
+ ret = true;
+ }
+ return ret;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename LOOKUP_FUNC>
+inline VALUE ConcurrentHashTable<VALUE, CONFIG, F>::
+ get_copy(Thread* thread, LOOKUP_FUNC& lookup_f, bool* grow_hint)
+{
+ ScopedCS cs(thread, this);
+ VALUE* val = internal_get(thread, lookup_f, grow_hint);
+ return val != NULL ? *val : CONFIG::notfound();
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ unsafe_insert(const VALUE& value) {
+ bool dead_hash = false;
+ size_t hash = CONFIG::get_hash(value, &dead_hash);
+ if (dead_hash) {
+ return false;
+ }
+ // This is an unsafe operation.
+ InternalTable* table = get_table();
+ Bucket* bucket = get_bucket_in(table, hash);
+ assert(!bucket->have_redirect() && !bucket->is_locked(), "bad");
+ Node* new_node = Node::create_node(value, bucket->first());
+ if (!bucket->cas_first(new_node, bucket->first())) {
+ assert(false, "bad");
+ }
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename SCAN_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ try_scan(Thread* thread, SCAN_FUNC& scan_f)
+{
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ bool vm_and_safepoint = thread->is_VM_thread() &&
+ SafepointSynchronize::is_at_safepoint();
+ if (!vm_and_safepoint && !try_resize_lock(thread)) {
+ return false;
+ }
+ do_scan_locked(thread, scan_f);
+ if (!vm_and_safepoint) {
+ unlock_resize_lock(thread);
+ }
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename SCAN_FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ do_scan(Thread* thread, SCAN_FUNC& scan_f)
+{
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ lock_resize_lock(thread);
+ do_scan_locked(thread, scan_f);
+ unlock_resize_lock(thread);
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+inline bool ConcurrentHashTable<VALUE, CONFIG, F>::
+ try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f)
+{
+ if (!try_resize_lock(thread)) {
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ return false;
+ }
+ do_bulk_delete_locked(thread, eval_f, del_f);
+ unlock_resize_lock(thread);
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ return true;
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f)
+{
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+ lock_resize_lock(thread);
+ do_bulk_delete_locked(thread, eval_f, del_f);
+ unlock_resize_lock(thread);
+ assert(!_resize_lock->owned_by_self(), "Re-size lock not held");
+}
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+template <typename VALUE_SIZE_FUNC>
+inline void ConcurrentHashTable<VALUE, CONFIG, F>::
+ statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f,
+ outputStream* st, const char* table_name)
+{
+ NumberSeq summary;
+ size_t literal_bytes = 0;
+ if ((thread->is_VM_thread() && !SafepointSynchronize::is_at_safepoint()) ||
+ (!thread->is_VM_thread() && !try_resize_lock(thread))) {
+ st->print_cr("statistics unavailable at this moment");
+ return;
+ }
+
+ InternalTable* table = get_table();
+ for (size_t bucket_it = 0; bucket_it < _table->_size; bucket_it++) {
+ ScopedCS cs(thread, this);
+ size_t count = 0;
+ Bucket* bucket = _table->get_bucket(bucket_it);
+ if (bucket->have_redirect() || bucket->is_locked()) {
+ continue;
+ }
+ Node* current_node = bucket->first();
+ while (current_node != NULL) {
+ ++count;
+ literal_bytes += vs_f(current_node->value());
+ current_node = current_node->next();
+ }
+ summary.add((double)count);
+ }
+
+ double num_buckets = summary.num();
+ double num_entries = summary.sum();
+
+ size_t bucket_bytes = num_buckets * sizeof(Bucket);
+ size_t entry_bytes = num_entries * sizeof(Node);
+ size_t total_bytes = literal_bytes + bucket_bytes + entry_bytes;
+
+ size_t bucket_size = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
+ size_t entry_size = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
+
+ st->print_cr("%s statistics:", table_name);
+ st->print_cr("Number of buckets : %9" PRIuPTR " = %9" PRIuPTR
+ " bytes, each " SIZE_FORMAT,
+ (size_t)num_buckets, bucket_bytes, bucket_size);
+ st->print_cr("Number of entries : %9" PRIuPTR " = %9" PRIuPTR
+ " bytes, each " SIZE_FORMAT,
+ (size_t)num_entries, entry_bytes, entry_size);
+ if (literal_bytes != 0) {
+ double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
+ st->print_cr("Number of literals : %9" PRIuPTR " = %9" PRIuPTR
+ " bytes, avg %7.3f",
+ (size_t)num_entries, literal_bytes, literal_avg);
+ }
+ st->print_cr("Total footprsize_t : %9s = %9" PRIuPTR " bytes", ""
+ , total_bytes);
+ st->print_cr("Average bucket size : %9.3f", summary.avg());
+ st->print_cr("Variance of bucket size : %9.3f", summary.variance());
+ st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
+ st->print_cr("Maximum bucket size : %9" PRIuPTR,
+ (size_t)summary.maximum());
+ if (!thread->is_VM_thread()) {
+ unlock_resize_lock(thread);
+ }
+}
+
+#endif // include guard
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/utilities/concurrentHashTableTasks.inline.hpp Thu May 17 10:32:26 2018 +0200
@@ -0,0 +1,226 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#ifndef SHARE_UTILITIES_CONCURRENT_HASH_TABLE_TASKS_INLINE_HPP
+#define SHARE_UTILITIES_CONCURRENT_HASH_TABLE_TASKS_INLINE_HPP
+
+#include "utilities/concurrentHashTable.inline.hpp"
+
+// This inline file contains BulkDeleteTask and GrowTasks which are both bucket
+// operations, which they are serialized with each other.
+
+// Base class for pause and/or parallel bulk operations.
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+class ConcurrentHashTable<VALUE, CONFIG, F>::BucketsOperation {
+ protected:
+ ConcurrentHashTable<VALUE, CONFIG, F>* _cht;
+
+ // Default size of _task_size_log2
+ static const size_t DEFAULT_TASK_SIZE_LOG2 = 12;
+
+ // The table is split into ranges, every increment is one range.
+ volatile size_t _next_to_claim;
+ size_t _task_size_log2; // Number of buckets.
+ size_t _stop_task; // Last task
+ size_t _size_log2; // Table size.
+
+ BucketsOperation(ConcurrentHashTable<VALUE, CONFIG, F>* cht)
+ : _cht(cht), _next_to_claim(0), _task_size_log2(DEFAULT_TASK_SIZE_LOG2),
+ _stop_task(0), _size_log2(0) {}
+
+ // Returns true if you succeeded to claim the range start -> (stop-1).
+ bool claim(size_t* start, size_t* stop) {
+ size_t claimed = Atomic::add((size_t)1, &_next_to_claim) - 1;
+ if (claimed >= _stop_task) {
+ return false;
+ }
+ *start = claimed * (((size_t)1) << _task_size_log2);
+ *stop = ((*start) + (((size_t)1) << _task_size_log2));
+ return true;
+ }
+
+ // Calculate starting values.
+ void setup() {
+ _size_log2 = _cht->_table->_log2_size;
+ size_t tmp = _size_log2 > _task_size_log2 ?
+ _size_log2 - _task_size_log2 : 0;
+ _stop_task = (((size_t)1) << tmp);
+ }
+
+ // Returns false if all ranges are claimed.
+ bool have_more_work() {
+ return OrderAccess::load_acquire(&_next_to_claim) >= _stop_task;
+ }
+
+ // If we have changed size.
+ bool is_same_table() {
+ // Not entirely true.
+ return _size_log2 != _cht->_table->_log2_size;
+ }
+
+ void thread_owns_resize_lock(Thread* thread) {
+ assert(BucketsOperation::_cht->_resize_lock_owner == thread,
+ "Should be locked by me");
+ assert(BucketsOperation::_cht->_resize_lock->owned_by_self(),
+ "Operations lock not held");
+ }
+ void thread_owns_only_state_lock(Thread* thread) {
+ assert(BucketsOperation::_cht->_resize_lock_owner == thread,
+ "Should be locked by me");
+ assert(!BucketsOperation::_cht->_resize_lock->owned_by_self(),
+ "Operations lock held");
+ }
+ void thread_do_not_own_resize_lock(Thread* thread) {
+ assert(!BucketsOperation::_cht->_resize_lock->owned_by_self(),
+ "Operations lock held");
+ assert(BucketsOperation::_cht->_resize_lock_owner != thread,
+ "Should not be locked by me");
+ }
+};
+
+// For doing pausable/parallel bulk delete.
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+class ConcurrentHashTable<VALUE, CONFIG, F>::BulkDeleteTask :
+ public BucketsOperation
+{
+ public:
+ BulkDeleteTask(ConcurrentHashTable<VALUE, CONFIG, F>* cht)
+ : BucketsOperation(cht) {
+ }
+ // Before start prepare must be called.
+ bool prepare(Thread* thread) {
+ bool lock = BucketsOperation::_cht->try_resize_lock(thread);
+ if (!lock) {
+ return false;
+ }
+ this->setup();
+ this->thread_owns_resize_lock(thread);
+ return true;
+ }
+
+ // Does one range destroying all matching EVALUATE_FUNC and
+ // DELETE_FUNC is called be destruction. Returns true if there is more work.
+ template <typename EVALUATE_FUNC, typename DELETE_FUNC>
+ bool doTask(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f) {
+ size_t start, stop;
+ assert(BucketsOperation::_cht->_resize_lock_owner != NULL,
+ "Should be locked");
+ if (!this->claim(&start, &stop)) {
+ return false;
+ }
+ BucketsOperation::_cht->do_bulk_delete_locked_for(thread, start, stop,
+ eval_f, del_f);
+ return true;
+ }
+
+ // Pauses this operations for a safepoint.
+ void pause(Thread* thread) {
+ this->thread_owns_resize_lock(thread);
+ // This leaves internal state locked.
+ BucketsOperation::_cht->unlock_resize_lock(thread);
+ this->thread_do_not_own_resize_lock(thread);
+ }
+
+ // Continues this operations after a safepoint.
+ bool cont(Thread* thread) {
+ this->thread_do_not_own_resize_lock(thread);
+ if (!BucketsOperation::_cht->try_resize_lock(thread)) {
+ this->thread_do_not_own_resize_lock(thread);
+ return false;
+ }
+ if (BucketsOperation::is_same_table()) {
+ BucketsOperation::_cht->unlock_resize_lock(thread);
+ this->thread_do_not_own_resize_lock(thread);
+ return false;
+ }
+ this->thread_owns_resize_lock(thread);
+ return true;
+ }
+
+ // Must be called after ranges are done.
+ void done(Thread* thread) {
+ this->thread_owns_resize_lock(thread);
+ BucketsOperation::_cht->unlock_resize_lock(thread);
+ this->thread_do_not_own_resize_lock(thread);
+ }
+};
+
+template <typename VALUE, typename CONFIG, MEMFLAGS F>
+class ConcurrentHashTable<VALUE, CONFIG, F>::GrowTask :
+ public BucketsOperation
+{
+ public:
+ GrowTask(ConcurrentHashTable<VALUE, CONFIG, F>* cht) : BucketsOperation(cht) {
+ }
+ // Before start prepare must be called.
+ bool prepare(Thread* thread) {
+ if (!BucketsOperation::_cht->internal_grow_prolog(
+ thread, BucketsOperation::_cht->_log2_size_limit)) {
+ return false;
+ }
+ this->thread_owns_resize_lock(thread);
+ BucketsOperation::setup();
+ return true;
+ }
+
+ // Re-sizes a portion of the table. Returns true if there is more work.
+ bool doTask(Thread* thread) {
+ size_t start, stop;
+ assert(BucketsOperation::_cht->_resize_lock_owner != NULL,
+ "Should be locked");
+ if (!this->claim(&start, &stop)) {
+ return false;
+ }
+ BucketsOperation::_cht->internal_grow_range(thread, start, stop);
+ assert(BucketsOperation::_cht->_resize_lock_owner != NULL,
+ "Should be locked");
+ return true;
+ }
+
+ // Pauses growing for safepoint
+ void pause(Thread* thread) {
+ // This leaves internal state locked.
+ this->thread_owns_resize_lock(thread);
+ BucketsOperation::_cht->_resize_lock->unlock();
+ this->thread_owns_only_state_lock(thread);
+ }
+
+ // Continues growing after safepoint.
+ void cont(Thread* thread) {
+ this->thread_owns_only_state_lock(thread);
+ // If someone slips in here directly after safepoint.
+ while (!BucketsOperation::_cht->_resize_lock->try_lock())
+ { /* for ever */ };
+ this->thread_owns_resize_lock(thread);
+ }
+
+ // Must be called after doTask returns false.
+ void done(Thread* thread) {
+ this->thread_owns_resize_lock(thread);
+ BucketsOperation::_cht->internal_grow_epilog(thread);
+ this->thread_do_not_own_resize_lock(thread);
+ }
+};
+
+#endif // include guard
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/gtest/utilities/test_concurrentHashtable.cpp Thu May 17 10:32:26 2018 +0200
@@ -0,0 +1,917 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+#include "precompiled.hpp"
+#include "runtime/mutex.hpp"
+#include "runtime/semaphore.hpp"
+#include "runtime/thread.hpp"
+#include "runtime/vmThread.hpp"
+#include "runtime/vm_operations.hpp"
+#include "utilities/concurrentHashTable.inline.hpp"
+#include "utilities/concurrentHashTableTasks.inline.hpp"
+#include "utilitiesHelper.inline.hpp"
+#include "unittest.hpp"
+
+// NOTE: On win32 gtest asserts are not mt-safe.
+// Amusingly as long as they do not assert they are mt-safe.
+#define SIZE_32 5
+
+struct Pointer;
+
+typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal> SimpleTestTable;
+typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal>::MultiGetHandle SimpleTestGetHandle;
+
+// Simplest working CRPT implementation for the hash-table.
+struct Pointer : public SimpleTestTable::BaseConfig {
+ static uintx get_hash(const uintptr_t& value, bool* dead_hash) {
+ return (uintx)value;
+ }
+ static const uintptr_t& notfound() {
+ static uintptr_t notfound = 0;
+ return notfound;
+ }
+ static void* allocate_node(size_t size, const uintptr_t& value) {
+ return ::malloc(size);
+ }
+ static void free_node(void* memory, const uintptr_t& value) {
+ ::free(memory);
+ }
+};
+
+struct SimpleTestLookup {
+ uintptr_t _val;
+ SimpleTestLookup(uintptr_t val) : _val(val) {}
+ uintx get_hash() {
+ return Pointer::get_hash(_val, NULL);
+ }
+ bool equals(const uintptr_t* value, bool* is_dead) {
+ return _val == *value;
+ }
+};
+
+static void cht_insert(Thread* thr) {
+ uintptr_t val = 0x2;
+ SimpleTestLookup stl(val);
+ SimpleTestTable* cht = new SimpleTestTable();
+ EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
+ EXPECT_EQ(cht->get_copy(thr, stl), val) << "Getting an existing value failed.";
+ EXPECT_TRUE(cht->remove(thr, stl)) << "Removing an existing value failed.";
+ EXPECT_FALSE(cht->remove(thr, stl)) << "Removing an already removed item succeeded.";
+ EXPECT_NE(cht->get_copy(thr, stl), val) << "Getting a removed value succeeded.";
+ delete cht;
+}
+
+struct ValVerify {
+ uintptr_t _val;
+ bool called_get;
+ bool called_insert;
+ ValVerify(uintptr_t val) : called_get(false), called_insert(false), _val(val) {}
+ void operator()(bool inserted, uintptr_t* val) {
+ EXPECT_EQ(_val, *val) << "The value inserted is not correct.";
+ if (inserted) {
+ called_insert = true;
+ } else {
+ called_get = true;
+ }
+ }
+ void verify(bool get, bool insert) {
+ EXPECT_EQ(called_get, get) << "Get unexpected";
+ EXPECT_EQ(called_insert, insert) << "Insert unexpected";
+ }
+};
+
+static void cht_get_insert_helper(Thread* thr, SimpleTestTable* cht, uintptr_t val) {
+ {
+ SimpleTestLookup stl(val);
+ ValVerify vv(val);
+ EXPECT_EQ(cht->get_insert(thr, stl, val, vv), false) << "Inserting an unique value failed.";
+ vv.verify(false, true);
+ }
+
+ {
+ SimpleTestLookup stl(val);
+ ValVerify vv(val);
+ EXPECT_EQ(cht->get_insert(thr, stl, val, vv), true) << "Getting an old value failed.";
+ vv.verify(true, false);
+ }
+}
+
+static void cht_get_insert(Thread* thr) {
+ uintptr_t val = 0x2;
+ SimpleTestLookup stl(val);
+ SimpleTestTable* cht = new SimpleTestTable();
+
+ {
+ SCOPED_TRACE("First");
+ cht_get_insert_helper(thr, cht, val);
+ }
+ EXPECT_EQ(cht->get_copy(thr, stl), val) << "Get an old value failed";
+ EXPECT_TRUE(cht->remove(thr, stl)) << "Removing existing value failed.";
+ EXPECT_NE(cht->get_copy(thr, stl), val) << "Got an already removed item.";
+
+ {
+ SCOPED_TRACE("Second");
+ cht_get_insert_helper(thr, cht, val);
+ }
+
+ delete cht;
+}
+
+static bool getinsert_bulkdelete_eval(uintptr_t* val) {
+ EXPECT_TRUE(*val > 0 && *val < 4) << "Val wrong for this test.";
+ return (*val & 0x1); // Delete all values ending with first bit set.
+}
+
+static void getinsert_bulkdelete_del(uintptr_t* val) {
+ EXPECT_EQ(*val & 0x1, (uintptr_t)1) << "Deleting wrong value.";
+}
+
+static void cht_getinsert_bulkdelete_insert_verified(Thread* thr, SimpleTestTable* cht, uintptr_t val,
+ bool verify_expect_get, bool verify_expect_inserted) {
+ ValVerify vv(val);
+ SimpleTestLookup stl(val);
+ EXPECT_EQ(cht->get_insert(thr, stl, val, vv), verify_expect_get) << "Inserting an unique value failed.";
+ vv.verify(verify_expect_get, verify_expect_inserted);
+}
+
+static void cht_getinsert_bulkdelete(Thread* thr) {
+ uintptr_t val1 = 1;
+ uintptr_t val2 = 2;
+ uintptr_t val3 = 3;
+ SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);
+
+ SimpleTestTable* cht = new SimpleTestTable();
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);
+
+ EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";
+
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present
+
+ EXPECT_EQ(cht->get_copy(thr, stl1), val1) << "Get did not find value.";
+ EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Get did not find value.";
+ EXPECT_EQ(cht->get_copy(thr, stl3), val3) << "Get did not find value.";
+
+ // Removes all odd values.
+ cht->bulk_delete(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del);
+
+ EXPECT_EQ(cht->get_copy(thr, stl1), (uintptr_t)0) << "Odd value should not exist.";
+ EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";
+ EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Even value should not have been removed.";
+ EXPECT_EQ(cht->get_copy(thr, stl3), (uintptr_t)0) << "Add value should not exists.";
+ EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";
+
+ delete cht;
+}
+
+static void cht_getinsert_bulkdelete_task(Thread* thr) {
+ uintptr_t val1 = 1;
+ uintptr_t val2 = 2;
+ uintptr_t val3 = 3;
+ SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);
+
+ SimpleTestTable* cht = new SimpleTestTable();
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);
+
+ EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";
+
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted
+ cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present
+
+ EXPECT_EQ(cht->get_copy(thr, stl1), val1) << "Get did not find value.";
+ EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Get did not find value.";
+ EXPECT_EQ(cht->get_copy(thr, stl3), val3) << "Get did not find value.";
+
+ // Removes all odd values.
+ SimpleTestTable::BulkDeleteTask bdt(cht);
+ if (bdt.prepare(thr)) {
+ while(bdt.doTask(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del)) {
+ bdt.pause(thr);
+ EXPECT_TRUE(bdt.cont(thr)) << "Uncontended continue should work.";
+ }
+ bdt.done(thr);
+ }
+
+ EXPECT_EQ(cht->get_copy(thr, stl1), (uintptr_t)0) << "Odd value should not exist.";
+ EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";
+ EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Even value should not have been removed.";
+ EXPECT_EQ(cht->get_copy(thr, stl3), (uintptr_t)0) << "Add value should not exists.";
+ EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";
+
+ delete cht;
+}
+
+static void cht_scope(Thread* thr) {
+ uintptr_t val = 0x2;
+ SimpleTestLookup stl(val);
+ SimpleTestTable* cht = new SimpleTestTable();
+ EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
+ {
+ SimpleTestGetHandle get_handle(thr, cht);
+ EXPECT_EQ(*get_handle.get(stl), val) << "Getting a pre-existing value failed.";
+ }
+ // We do remove here to make sure the value-handle 'unlocked' the table when leaving the scope.
+ EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl) == val) << "Got a removed value.";
+ delete cht;
+}
+
+struct ChtScan {
+ size_t _count;
+ ChtScan() : _count(0) {}
+ bool operator()(uintptr_t* val) {
+ EXPECT_EQ(*val, (uintptr_t)0x2) << "Got an unknown value.";
+ EXPECT_EQ(_count, 0u) << "Only one value should be in table.";
+ _count++;
+ return true; /* continue scan */
+ }
+};
+
+static void cht_scan(Thread* thr) {
+ uintptr_t val = 0x2;
+ SimpleTestLookup stl(val);
+ ChtScan scan;
+ SimpleTestTable* cht = new SimpleTestTable();
+ EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
+ EXPECT_EQ(cht->try_scan(thr, scan), true) << "Scanning an non-growing/shrinking table should work.";
+ EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl) == val) << "Got a removed value.";
+ delete cht;
+}
+
+static void cht_grow(Thread* thr) {
+ uintptr_t val = 0x2;
+ uintptr_t val2 = 0x22;
+ uintptr_t val3 = 0x222;
+ SimpleTestLookup stl(val), stl2(val2), stl3(val3);
+ SimpleTestTable* cht = new SimpleTestTable();
+
+ EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
+ EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
+ EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
+
+ EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
+ EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
+
+
+ EXPECT_TRUE(cht->grow(thr)) << "Growing uncontended should not fail.";
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed.";
+
+ EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
+
+ EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
+
+ delete cht;
+}
+
+static void cht_task_grow(Thread* thr) {
+ uintptr_t val = 0x2;
+ uintptr_t val2 = 0x22;
+ uintptr_t val3 = 0x222;
+ SimpleTestLookup stl(val), stl2(val2), stl3(val3);
+ SimpleTestTable* cht = new SimpleTestTable();
+
+ EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
+ EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
+ EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
+
+ EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
+ EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
+
+ SimpleTestTable::GrowTask gt(cht);
+ EXPECT_TRUE(gt.prepare(thr)) << "Growing uncontended should not fail.";
+ while(gt.doTask(thr)) { /* grow */ }
+ gt.done(thr);
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed.";
+
+ EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
+ EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
+
+ EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
+
+ EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed.";
+ EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed.";
+ EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
+
+ delete cht;
+}
+
+TEST_VM(ConcurrentHashTable, basic_insert) {
+ nomt_test_doer(cht_insert);
+}
+
+TEST_VM(ConcurrentHashTable, basic_get_insert) {
+ nomt_test_doer(cht_get_insert);
+}
+
+TEST_VM(ConcurrentHashTable, basic_scope) {
+ nomt_test_doer(cht_scope);
+}
+
+TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete) {
+ nomt_test_doer(cht_getinsert_bulkdelete);
+}
+
+TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete_task) {
+ nomt_test_doer(cht_getinsert_bulkdelete_task);
+}
+
+TEST_VM(ConcurrentHashTable, basic_scan) {
+ nomt_test_doer(cht_scan);
+}
+
+TEST_VM(ConcurrentHashTable, basic_grow) {
+ nomt_test_doer(cht_grow);
+}
+
+TEST_VM(ConcurrentHashTable, task_grow) {
+ nomt_test_doer(cht_task_grow);
+}
+
+//#############################################################################################
+
+class TestInterface;
+
+typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal> TestTable;
+typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal>::MultiGetHandle TestGetHandle;
+
+class TestInterface : public TestTable::BaseConfig {
+public:
+ static uintx get_hash(const uintptr_t& value, bool* dead_hash) {
+ return (uintx)(value + 18446744073709551557ul) * 18446744073709551557ul;
+ }
+ static const uintptr_t& notfound() {
+ static uintptr_t notfound = 0;
+ return notfound;
+ }
+};
+
+struct TestLookup {
+ uintptr_t _val;
+ TestLookup(uintptr_t val) : _val(val) {}
+ uintx get_hash() {
+ return TestInterface::get_hash(_val, NULL);
+ }
+ bool equals(const uintptr_t* value, bool* is_dead) {
+ return _val == *value;
+ }
+};
+
+class CHTTestThread : public JavaTestThread {
+ public:
+ uintptr_t _start;
+ uintptr_t _stop;
+ TestTable *_cht;
+ jlong _stop_ms;
+ CHTTestThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
+ : JavaTestThread(post), _start(start), _stop(stop), _cht(cht) {}
+ virtual void premain() {}
+ void main_run() {
+ premain();
+ _stop_ms = os::javaTimeMillis() + 2000; // 2 seconds max test time
+ while (keep_looping() && test_loop()) { /* */ }
+ postmain();
+ }
+ virtual void postmain() {}
+ virtual bool keep_looping() {
+ return _stop_ms > os::javaTimeMillis();
+ };
+ virtual bool test_loop() = 0;
+ virtual ~CHTTestThread() {}
+};
+
+class ValueSaver {
+ uintptr_t* _vals;
+ size_t _it;
+ size_t _size;
+ public:
+ ValueSaver() : _it(0), _size(1024) {
+ _vals = NEW_C_HEAP_ARRAY(uintptr_t, _size, mtInternal);
+ }
+
+ bool operator()(uintptr_t* val) {
+ _vals[_it++] = *val;
+ if (_it == _size) {
+ _size *= 2;
+ _vals = REALLOC_RESOURCE_ARRAY(uintptr_t, _vals, _size/2, _size);
+ }
+ return true;
+ }
+
+ void check() {
+ for (size_t i = 0; i < _it; i++) {
+ size_t count = 0;
+ for (size_t j = (i + 1u); j < _it; j++) {
+ if (_vals[i] == _vals[j]) {
+ count++;
+ }
+ }
+ EXPECT_EQ(count, 0u);
+ }
+ }
+};
+
+static void integrity_check(Thread* thr, TestTable* cht)
+{
+ ValueSaver vs;
+ cht->do_scan(thr, vs);
+ vs.check();
+}
+
+//#############################################################################################
+// All threads are working on different items
+// This item should only be delete by this thread
+// Thus get_unsafe is safe for this test.
+
+class SimpleInserterThread : public CHTTestThread {
+public:
+ static volatile bool _exit;
+
+ SimpleInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
+ : CHTTestThread(start, stop, cht, post) {};
+ virtual ~SimpleInserterThread(){}
+
+ bool keep_looping() {
+ return !_exit;
+ }
+
+ bool test_loop() {
+ bool grow;
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work.";
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->get_copy(this, tl) == TestInterface::notfound()) << "Got a removed value.";
+ }
+ return true;
+ }
+};
+
+volatile bool SimpleInserterThread::_exit = false;
+
+class RunnerSimpleInserterThread : public CHTTestThread {
+public:
+ Semaphore _done;
+
+ RunnerSimpleInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
+ _cht = new TestTable(SIZE_32, SIZE_32);
+ };
+ virtual ~RunnerSimpleInserterThread(){}
+
+ void premain() {
+
+ SimpleInserterThread* ins1 = new SimpleInserterThread((uintptr_t)0x100, (uintptr_t) 0x1FF, _cht, &_done);
+ SimpleInserterThread* ins2 = new SimpleInserterThread((uintptr_t)0x200, (uintptr_t) 0x2FF, _cht, &_done);
+ SimpleInserterThread* ins3 = new SimpleInserterThread((uintptr_t)0x300, (uintptr_t) 0x3FF, _cht, &_done);
+ SimpleInserterThread* ins4 = new SimpleInserterThread((uintptr_t)0x400, (uintptr_t) 0x4FF, _cht, &_done);
+
+ for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
+ }
+
+ ins1->doit();
+ ins2->doit();
+ ins3->doit();
+ ins4->doit();
+
+ }
+
+ bool test_loop() {
+ for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";;
+ }
+ return true;
+ }
+
+ void postmain() {
+ SimpleInserterThread::_exit = true;
+ for (int i = 0; i < 4; i++) {
+ _done.wait();
+ }
+ for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
+ }
+ integrity_check(this, _cht);
+ delete _cht;
+ }
+};
+
+
+TEST_VM(ConcurrentHashTable, concurrent_simple) {
+ SimpleInserterThread::_exit = false;
+ mt_test_doer<RunnerSimpleInserterThread>();
+}
+
+//#############################################################################################
+// In this test we try to get a 'bad' value
+class DeleteInserterThread : public CHTTestThread {
+public:
+ static volatile bool _exit;
+
+ DeleteInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
+ virtual ~DeleteInserterThread(){}
+
+ bool keep_looping() {
+ return !_exit;
+ }
+
+ bool test_loop() {
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ _cht->insert(this, tl, v);
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ _cht->remove(this, tl);
+ }
+ return true;
+ }
+};
+
+volatile bool DeleteInserterThread::_exit = true;
+
+class RunnerDeleteInserterThread : public CHTTestThread {
+public:
+ Semaphore _done;
+
+ RunnerDeleteInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
+ _cht = new TestTable(SIZE_32, SIZE_32);
+ };
+ virtual ~RunnerDeleteInserterThread(){}
+
+ void premain() {
+ DeleteInserterThread* ins1 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
+ DeleteInserterThread* ins2 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
+ DeleteInserterThread* ins3 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
+ DeleteInserterThread* ins4 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
+
+ ins1->doit();
+ ins2->doit();
+ ins3->doit();
+ ins4->doit();
+ }
+
+ bool test_loop() {
+ for (uintptr_t v = 0x1; v < 0xFFF; v++ ) {
+ uintptr_t tv;
+ if (v & 0x1) {
+ TestLookup tl(v);
+ tv = _cht->get_copy(this, tl);
+ } else {
+ TestLookup tl(v);
+ TestGetHandle value_handle(this, _cht);
+ uintptr_t* tmp = value_handle.get(tl);
+ tv = tmp != NULL ? *tmp : 0;
+ }
+ EXPECT_TRUE(tv == 0 || tv == v) << "Got unknown value.";
+ }
+ return true;
+ }
+
+ void postmain() {
+ DeleteInserterThread::_exit = true;
+ for (int i = 0; i < 4; i++) {
+ _done.wait();
+ }
+ integrity_check(this, _cht);
+ delete _cht;
+ }
+};
+
+TEST_VM(ConcurrentHashTable, concurrent_deletes) {
+ DeleteInserterThread::_exit = false;
+ mt_test_doer<RunnerDeleteInserterThread>();
+}
+
+//#############################################################################################
+
+#define START_SIZE 13
+#define END_SIZE 17
+#define START (uintptr_t)0x10000
+#define RANGE (uintptr_t)0xFFFF
+
+#define GSTEST_THREAD_COUNT 5
+
+
+class GSInserterThread: public CHTTestThread {
+public:
+ static volatile bool _shrink;
+ GSInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
+ virtual ~GSInserterThread(){}
+ bool keep_looping() {
+ return !(_shrink && _cht->get_size_log2(this) == START_SIZE);
+ }
+ bool test_loop() {
+ bool grow;
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work.";
+ if (grow && !_shrink) {
+ _cht->grow(this);
+ }
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
+ }
+ if (_shrink) {
+ _cht->shrink(this);
+ }
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ TestLookup tl(v);
+ EXPECT_FALSE(_cht->get_copy(this, tl) == v) << "Getting a removed value should have failed.";
+ }
+ if (!_shrink && _cht->get_size_log2(this) == END_SIZE) {
+ _shrink = true;
+ }
+ return true;
+ }
+};
+
+volatile bool GSInserterThread::_shrink = false;
+
+class GSScannerThread : public CHTTestThread {
+public:
+ GSScannerThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
+ virtual ~GSScannerThread(){}
+
+ bool operator()(uintptr_t* val) {
+ if (*val >= this->_start && *val <= this->_stop) {
+ return false;
+ }
+ // continue scan
+ return true;
+ }
+
+ bool test_loop() {
+ _cht->try_scan(this, *this);
+ os::naked_short_sleep(5);
+ return true;
+ }
+};
+
+class RunnerGSInserterThread : public CHTTestThread {
+public:
+ uintptr_t _start;
+ uintptr_t _range;
+ Semaphore _done;
+
+ RunnerGSInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
+ _cht = new TestTable(START_SIZE, END_SIZE, 2);
+ };
+ virtual ~RunnerGSInserterThread(){}
+
+ void premain() {
+ volatile bool timeout = false;
+ _start = START;
+ _range = RANGE;
+ CHTTestThread* tt[GSTEST_THREAD_COUNT];
+ tt[0] = new GSInserterThread(_start, _start + _range, _cht, &_done);
+ _start += _range + 1;
+ tt[1] = new GSInserterThread(_start, _start + _range, _cht, &_done);
+ _start += _range + 1;
+ tt[2] = new GSInserterThread(_start, _start + _range, _cht, &_done);
+ _start += _range + 1;
+ tt[3] = new GSInserterThread(_start, _start + _range, _cht, &_done);
+ tt[4] = new GSScannerThread(_start, _start + _range, _cht, &_done);
+ _start += _range + 1;
+
+
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
+ }
+
+ for (int i = 0; i < GSTEST_THREAD_COUNT; i++) {
+ tt[i]->doit();
+ }
+ }
+
+ bool test_loop() {
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
+ }
+ return true;
+ }
+
+ void postmain() {
+ GSInserterThread::_shrink = true;
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
+ }
+ for (int i = 0; i < GSTEST_THREAD_COUNT; i++) {
+ _done.wait();
+ }
+ EXPECT_TRUE(_cht->get_size_log2(this) == START_SIZE) << "Not at start size.";
+ Count cnt;
+ _cht->do_scan(this, cnt);
+ EXPECT_TRUE(cnt._cnt == 0) << "Items still in table";
+ delete _cht;
+ }
+
+ struct Count {
+ Count() : _cnt(0) {}
+ size_t _cnt;
+ bool operator()(uintptr_t*) { _cnt++; return true; };
+ };
+};
+
+TEST_VM(ConcurrentHashTable, concurrent_scan_grow_shrink) {
+ GSInserterThread::_shrink = false;
+ mt_test_doer<RunnerGSInserterThread>();
+}
+
+
+//#############################################################################################
+
+#define GI_BD_GI_BD_START_SIZE 13
+#define GI_BD_END_SIZE 17
+#define GI_BD_START (uintptr_t)0x1
+#define GI_BD_RANGE (uintptr_t)0x3FFFF
+
+#define GI_BD_TEST_THREAD_COUNT 4
+
+
+class GI_BD_InserterThread: public CHTTestThread {
+public:
+ static volatile bool _shrink;
+ uintptr_t _br;
+ GI_BD_InserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post, uintptr_t br)
+ : CHTTestThread(start, stop, cht, post), _br(br) {};
+ virtual ~GI_BD_InserterThread(){}
+
+ bool keep_looping() {
+ return !(_shrink && _cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE);
+ }
+
+ bool test_loop() {
+ bool grow;
+ MyDel del(_br);
+ for (uintptr_t v = _start; v <= _stop; v++) {
+ ValVerify vv(v);
+ TestLookup tl(v);
+ _cht->get_insert(this, tl, v, vv, &grow);
+ EXPECT_NE(vv.called_get, vv.called_insert) << "Non or both callbacks was called.";
+ if (grow && !_shrink) {
+ _cht->grow(this);
+ }
+ }
+ if (_shrink) {
+ _cht->shrink(this);
+ }
+ _cht->try_bulk_delete(this, *this, del);
+ if (!_shrink && _cht->is_max_size_reached()) {
+ _shrink = true;
+ }
+ _cht->bulk_delete(this, *this, del);
+ return true;
+ }
+
+ bool operator()(uintptr_t* val) {
+ return (*val & _br) == 1;
+ }
+
+ struct MyDel {
+ MyDel(uintptr_t &br) : _br(br) {};
+ uintptr_t &_br;
+ void operator()(uintptr_t* val) {
+ EXPECT_EQ((*val & _br), _br) << "Removing an item that should not have been removed.";
+ }
+ };
+};
+
+volatile bool GI_BD_InserterThread::_shrink = false;
+
+class RunnerGI_BD_InserterThread : public CHTTestThread {
+public:
+ Semaphore _done;
+ uintptr_t _start;
+ uintptr_t _range;
+ RunnerGI_BD_InserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
+ _cht = new TestTable(GI_BD_GI_BD_START_SIZE, GI_BD_END_SIZE, 2);
+ };
+ virtual ~RunnerGI_BD_InserterThread(){}
+
+ void premain() {
+ _start = GI_BD_START;
+ _range = GI_BD_RANGE;
+ CHTTestThread* tt[GI_BD_TEST_THREAD_COUNT];
+ tt[0] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x1);
+ tt[1] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x2);
+ tt[2] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x4);
+ tt[3] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x8);
+
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
+ }
+
+ for (int i =0; i < GI_BD_TEST_THREAD_COUNT; i++) {
+ tt[i]->doit();
+ }
+ }
+
+ bool test_loop() {
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ if (v & 0xF) {
+ _cht->get_copy(this, tl);
+ } else {
+ EXPECT_EQ(_cht->get_copy(this, tl), v) << "Item ending with 0xX0 should never be removed.";
+ }
+ }
+ return true;
+ }
+
+ void postmain() {
+ GI_BD_InserterThread::_shrink = true;
+ for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
+ TestLookup tl(v);
+ if (v & 0xF) {
+ _cht->remove(this, tl);
+ } else {
+ EXPECT_TRUE(_cht->remove(this, tl)) << "Removing item ending with 0xX0 should always work.";
+ }
+ }
+ for (int i = 0; i < GI_BD_TEST_THREAD_COUNT; i++) {
+ _done.wait();
+ }
+ EXPECT_TRUE(_cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE) << "We have not shrunk back to start size.";
+ delete _cht;
+ }
+};
+
+TEST_VM(ConcurrentHashTable, concurrent_get_insert_bulk_delete) {
+ GI_BD_InserterThread::_shrink = false;
+ mt_test_doer<RunnerGI_BD_InserterThread>();
+}