# HG changeset patch
# User rehn
# Date 1526545946 -7200
# Node ID 8e4fcfb4cfe48e6b481c6aa1751d916014a826af
# Parent  bd198a98f3c50a91879bfa1a2821fcd2cda23ecf
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

diff -r bd198a98f3c5 -r 8e4fcfb4cfe4 src/hotspot/share/utilities/concurrentHashTable.hpp
--- /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
diff -r bd198a98f3c5 -r 8e4fcfb4cfe4 src/hotspot/share/utilities/concurrentHashTable.inline.hpp
--- /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
diff -r bd198a98f3c5 -r 8e4fcfb4cfe4 src/hotspot/share/utilities/concurrentHashTableTasks.inline.hpp
--- /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
diff -r bd198a98f3c5 -r 8e4fcfb4cfe4 test/hotspot/gtest/utilities/test_concurrentHashtable.cpp
--- /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>();
+}