--- a/src/hotspot/share/gc/g1/dirtyCardQueue.cpp	Thu Jan 24 14:22:50 2019 -0800
+++ b/src/hotspot/share/gc/g1/dirtyCardQueue.cpp	Fri Jan 25 00:27:51 2019 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2001, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2001, 2019, 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
@@ -25,6 +25,7 @@
 #include "precompiled.hpp"
 #include "gc/g1/dirtyCardQueue.hpp"
 #include "gc/g1/g1CollectedHeap.inline.hpp"
+#include "gc/g1/g1FreeIdSet.hpp"
 #include "gc/g1/g1RemSet.hpp"
 #include "gc/g1/g1ThreadLocalData.hpp"
 #include "gc/g1/heapRegionRemSet.hpp"
@@ -55,72 +56,6 @@
   }
 };
 
-// Represents a set of free small integer ids.
-class FreeIdSet : public CHeapObj<mtGC> {
-  enum {
-    end_of_list = UINT_MAX,
-    claimed = UINT_MAX - 1
-  };
-
-  uint _size;
-  Monitor* _mon;
-
-  uint* _ids;
-  uint _hd;
-  uint _waiters;
-  uint _claimed;
-
-public:
-  FreeIdSet(uint size, Monitor* mon);
-  ~FreeIdSet();
-
-  // Returns an unclaimed parallel id (waiting for one to be released if
-  // necessary).
-  uint claim_par_id();
-
-  void release_par_id(uint id);
-};
-
-FreeIdSet::FreeIdSet(uint size, Monitor* mon) :
-  _size(size), _mon(mon), _hd(0), _waiters(0), _claimed(0)
-{
-  guarantee(size != 0, "must be");
-  _ids = NEW_C_HEAP_ARRAY(uint, size, mtGC);
-  for (uint i = 0; i < size - 1; i++) {
-    _ids[i] = i+1;
-  }
-  _ids[size-1] = end_of_list; // end of list.
-}
-
-FreeIdSet::~FreeIdSet() {
-  FREE_C_HEAP_ARRAY(uint, _ids);
-}
-
-uint FreeIdSet::claim_par_id() {
-  MutexLockerEx x(_mon, Mutex::_no_safepoint_check_flag);
-  while (_hd == end_of_list) {
-    _waiters++;
-    _mon->wait(Mutex::_no_safepoint_check_flag);
-    _waiters--;
-  }
-  uint res = _hd;
-  _hd = _ids[res];
-  _ids[res] = claimed;  // For debugging.
-  _claimed++;
-  return res;
-}
-
-void FreeIdSet::release_par_id(uint id) {
-  MutexLockerEx x(_mon, Mutex::_no_safepoint_check_flag);
-  assert(_ids[id] == claimed, "Precondition.");
-  _ids[id] = _hd;
-  _hd = id;
-  _claimed--;
-  if (_waiters > 0) {
-    _mon->notify_all();
-  }
-}
-
 DirtyCardQueue::DirtyCardQueue(DirtyCardQueueSet* qset, bool permanent) :
   // Dirty card queues are always active, so we create them with their
   // active field set to true.
@@ -144,6 +79,10 @@
   _all_active = true;
 }
 
+DirtyCardQueueSet::~DirtyCardQueueSet() {
+  delete _free_ids;
+}
+
 // Determines how many mutator threads can process the buffers in parallel.
 uint DirtyCardQueueSet::num_par_ids() {
   return (uint)os::initial_active_processor_count();
@@ -156,7 +95,7 @@
   PtrQueueSet::initialize(cbl_mon, allocator);
   _shared_dirty_card_queue.set_lock(lock);
   if (init_free_ids) {
-    _free_ids = new FreeIdSet(num_par_ids(), cbl_mon);
+    _free_ids = new G1FreeIdSet(0, num_par_ids());
   }
 }
 

--- a/src/hotspot/share/gc/g1/dirtyCardQueue.hpp	Thu Jan 24 14:22:50 2019 -0800
+++ b/src/hotspot/share/gc/g1/dirtyCardQueue.hpp	Fri Jan 25 00:27:51 2019 -0500
@@ -28,8 +28,8 @@
 #include "gc/shared/ptrQueue.hpp"
 #include "memory/allocation.hpp"
 
-class FreeIdSet;
 class DirtyCardQueueSet;
+class G1FreeIdSet;
 class JavaThread;
 class Monitor;
 
@@ -103,8 +103,7 @@
 
   bool mut_process_buffer(BufferNode* node);
 
-  // Protected by the _cbl_mon.
-  FreeIdSet* _free_ids;
+  G1FreeIdSet* _free_ids;
 
   // The number of completed buffers processed by mutator and rs thread,
   // respectively.
@@ -118,6 +117,7 @@
 
 public:
   DirtyCardQueueSet(bool notify_when_complete = true);
+  ~DirtyCardQueueSet();
 
   void initialize(Monitor* cbl_mon,
                   BufferNode::Allocator* allocator,

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/gc/g1/g1FreeIdSet.cpp	Fri Jan 25 00:27:51 2019 -0500
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2019, 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 "gc/g1/g1FreeIdSet.hpp"
+#include "memory/allocation.inline.hpp"
+#include "runtime/atomic.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/globalDefinitions.hpp"
+#include "utilities/macros.hpp"
+
+G1FreeIdSet::G1FreeIdSet(uint start, uint size) :
+  _sem(size),          // counting semaphore for available ids
+  _next(NULL),         // array of "next" indices
+  _start(start),       // first id value
+  _size(size),         // number of available ids
+  _head_index_mask(0), // mask for extracting index from a _head value.
+  _head(0)             // low part: index; high part: update counter
+{
+  assert(size != 0, "precondition");
+  assert(start <= (UINT_MAX - size),
+         "start (%u) + size (%u) overflow: ", start, size);
+  // 2^shift must be greater than size. Equal is not permitted, because
+  // size is the "end of list" value, and can be the index part of _head.
+  uint shift = log2_intptr((uintptr_t)size) + 1;
+  assert(shift <= (BitsPerWord / 2), "excessive size %u", size);
+  _head_index_mask = (uintx(1) << shift) - 1;
+  assert(size <= _head_index_mask, "invariant");
+  _next = NEW_C_HEAP_ARRAY(uint, size, mtGC);
+  for (uint i = 0; i < size; ++i) {
+    _next[i] = i + 1;
+  }
+}
+
+G1FreeIdSet::~G1FreeIdSet() {
+  FREE_C_HEAP_ARRAY(uint, _next);
+}
+
+uint G1FreeIdSet::head_index(uintx head) const {
+  return head & _head_index_mask;
+}
+
+uintx G1FreeIdSet::make_head(uint index, uintx old_head) const {
+  // Include incremented old update counter to avoid ABA problem.
+  return index | ((old_head & ~_head_index_mask) + 1 + _head_index_mask);
+}
+
+const uint Claimed = UINT_MAX;
+
+uint G1FreeIdSet::claim_par_id() {
+  _sem.wait();
+  // Semaphore gate permits passage by no more than the number of
+  // available ids, so there must be one that we can claim.  But there
+  // may be multiple threads trying to claim ids at the same time.
+  uintx old_head = Atomic::load(&_head);
+  uint index;
+  while (true) {
+    index = head_index(old_head);
+    assert(index < _size, "invariant");
+    uintx new_head = make_head(_next[index], old_head);
+    new_head = Atomic::cmpxchg(new_head, &_head, old_head);
+    if (new_head == old_head) break;
+    old_head = new_head;
+  }
+  DEBUG_ONLY(_next[index] = Claimed;)
+  return _start + index;
+}
+
+void G1FreeIdSet::release_par_id(uint id) {
+  uint index = id - _start;
+  assert(index < _size, "invalid id %u", id);
+  assert(_next[index] == Claimed, "precondition");
+  uintx old_head = Atomic::load(&_head);
+  while (true) {
+    _next[index] = head_index(old_head);
+    uintx new_head = make_head(index, old_head);
+    new_head = Atomic::cmpxchg(new_head, &_head, old_head);
+    if (new_head == old_head) break;
+    old_head = new_head;
+  }
+  // Now that id has been released, permit another thread through the gate.
+  _sem.signal();
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/gc/g1/g1FreeIdSet.hpp	Fri Jan 25 00:27:51 2019 -0500
@@ -0,0 +1,65 @@
+/*
+ * Copyright (c) 2019, 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_GC_G1_G1FREEIDSET_HPP
+#define SHARE_GC_G1_G1FREEIDSET_HPP
+
+#include "memory/allocation.hpp"
+#include "runtime/semaphore.hpp"
+#include "utilities/globalDefinitions.hpp"
+
+// Represents a set of small integer ids, from which elements can be
+// temporarily allocated for exclusive use.  The ids are in a
+// contiguous range from 'start' to 'start + size'.  Used to obtain a
+// distinct worker_id value for a mutator thread that doesn't normally
+// have such an id.
+class G1FreeIdSet : public CHeapObj<mtGC> {
+  Semaphore _sem;
+  uint* _next;
+  uint _start;
+  uint _size;
+  uintx _head_index_mask;
+  volatile uintx _head;
+
+  uint head_index(uintx head) const;
+  uintx make_head(uint index, uintx old_head) const;
+
+  // Noncopyable.
+  G1FreeIdSet(const G1FreeIdSet&);
+  G1FreeIdSet& operator=(const G1FreeIdSet&);
+
+public:
+  G1FreeIdSet(uint start, uint size);
+  ~G1FreeIdSet();
+
+  // Returns an unclaimed parallel id (waiting for one to be released if
+  // necessary).  Must not safepoint while holding a claimed id.
+  uint claim_par_id();
+
+  void release_par_id(uint id);
+
+  struct TestSupport;           // For unit test access.
+};
+
+#endif // SHARE_GC_G1_G1FREEIDSET_HPP

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/gtest/gc/g1/test_g1FreeIdSet.cpp	Fri Jan 25 00:27:51 2019 -0500
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2019, 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 "gc/g1/g1FreeIdSet.hpp"
+#include "memory/allocation.hpp"
+#include "runtime/atomic.hpp"
+#include "runtime/interfaceSupport.inline.hpp"
+#include "runtime/orderAccess.hpp"
+#include "runtime/semaphore.inline.hpp"
+#include "runtime/thread.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/globalDefinitions.hpp"
+#include "utilities/ostream.hpp"
+#include "threadHelper.inline.hpp"
+#include "unittest.hpp"
+
+struct G1FreeIdSet::TestSupport : AllStatic {
+  static uint next(const G1FreeIdSet& set, uint index) {
+    assert(index < set._size, "precondition");
+    return set._next[index];
+  }
+
+  static uint start(const G1FreeIdSet& set) { return set._start; }
+  static uint size(const G1FreeIdSet& set) { return set._size; }
+  static uintx mask(const G1FreeIdSet& set) { return set._head_index_mask; }
+  static uintx head(const G1FreeIdSet& set) { return Atomic::load(&set._head); }
+
+  static uint head_index(const G1FreeIdSet& set, uintx head) {
+    return set.head_index(head);
+  }
+};
+
+typedef G1FreeIdSet::TestSupport TestSupport;
+
+TEST_VM(G1FreeIdSetTest, initial_state) {
+  const uint start = 5;
+  const uint size = 4;
+  G1FreeIdSet set(start, size);
+
+  ASSERT_EQ(start, TestSupport::start(set));
+  ASSERT_EQ(size, TestSupport::size(set));
+  ASSERT_EQ(7u, TestSupport::mask(set));
+  ASSERT_EQ(0u, TestSupport::head(set));
+  for (uint i = 0; i < size; ++i) {
+    ASSERT_EQ(i + 1, TestSupport::next(set, i));
+  }
+}
+
+TEST_VM(G1FreeIdSetTest, non_blocking_ops) {
+  const uint start = 5;
+  const uint size = 3;
+  G1FreeIdSet set(start, size);
+
+  ASSERT_EQ(5u, set.claim_par_id());
+  ASSERT_EQ(1u, TestSupport::head_index(set, TestSupport::head(set)));
+  ASSERT_EQ(6u, set.claim_par_id());
+  ASSERT_EQ(2u, TestSupport::head_index(set, TestSupport::head(set)));
+  ASSERT_EQ(7u, set.claim_par_id());
+  ASSERT_EQ(3u, TestSupport::head_index(set, TestSupport::head(set)));
+
+  set.release_par_id(5u);
+  set.release_par_id(6u);
+  ASSERT_EQ(6u, set.claim_par_id());
+  ASSERT_EQ(5u, set.claim_par_id());
+}
+
+class TestG1FreeIdSetThread : public JavaTestThread {
+  G1FreeIdSet* _set;
+  volatile size_t* _total_allocations;
+  volatile bool* _continue_running;
+  size_t _allocations;
+  uint _thread_number;
+
+public:
+  TestG1FreeIdSetThread(uint thread_number,
+                        Semaphore* post,
+                        G1FreeIdSet* set,
+                        volatile size_t* total_allocations,
+                        volatile bool* continue_running) :
+    JavaTestThread(post),
+    _set(set),
+    _total_allocations(total_allocations),
+    _continue_running(continue_running),
+    _allocations(0),
+    _thread_number(thread_number)
+  {}
+
+  virtual void main_run() {
+    while (OrderAccess::load_acquire(_continue_running)) {
+      uint id = _set->claim_par_id();
+      _set->release_par_id(id);
+      ++_allocations;
+      ThreadBlockInVM tbiv(this); // Safepoint check.
+    }
+    tty->print_cr("%u allocations: " SIZE_FORMAT, _thread_number, _allocations);
+    Atomic::add(_allocations, _total_allocations);
+  }
+};
+
+TEST_VM(G1FreeIdSetTest, stress) {
+  const uint start = 5;
+  const uint size = 3;
+  const uint nthreads = size + 1;
+  const uint milliseconds_to_run = 1000;
+
+  Semaphore post;
+  volatile size_t total_allocations = 0;
+  volatile bool continue_running = true;
+
+  G1FreeIdSet set(start, size);
+
+  TestG1FreeIdSetThread* threads[nthreads] = {};
+  for (uint i = 0; i < nthreads; ++i) {
+    threads[i] = new TestG1FreeIdSetThread(i,
+                                           &post,
+                                           &set,
+                                           &total_allocations,
+                                           &continue_running);
+    threads[i]->doit();
+  }
+
+  JavaThread* this_thread = JavaThread::current();
+  tty->print_cr("Stressing G1FreeIdSet for %u ms", milliseconds_to_run);
+  {
+    ThreadInVMfromNative invm(this_thread);
+    os::sleep(this_thread, milliseconds_to_run, true);
+  }
+  OrderAccess::release_store(&continue_running, false);
+  for (uint i = 0; i < nthreads; ++i) {
+    ThreadInVMfromNative invm(this_thread);
+    post.wait_with_safepoint_check(this_thread);
+  }
+  tty->print_cr("total allocations: " SIZE_FORMAT, total_allocations);
+  tty->print_cr("final free list: ");
+  uint ids[size] = {};
+  for (uint i = 0; i < size; ++i) {
+    uint id = set.claim_par_id();
+    uint index = id - TestSupport::start(set);
+    ASSERT_LT(index, TestSupport::size(set));
+    tty->print_cr("  %u: %u", i, index);
+  }
+  ASSERT_EQ(size, TestSupport::head_index(set, TestSupport::head(set)));
+}