--- a/hotspot/src/share/vm/code/nmethod.cpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/code/nmethod.cpp	Tue Oct 13 10:06:46 2015 +0200
@@ -1628,7 +1628,11 @@
         // During GC the is_alive closure is non-NULL, and is used to
         // determine liveness of dependees that need to be updated.
         if (is_alive == NULL || klass->is_loader_alive(is_alive)) {
-          InstanceKlass::cast(klass)->remove_dependent_nmethod(this);
+          // The GC defers deletion of this entry, since there might be multiple threads
+          // iterating over the _dependencies graph. Other call paths are single-threaded
+          // and may delete it immediately.
+          bool delete_immediately = is_alive == NULL;
+          InstanceKlass::cast(klass)->remove_dependent_nmethod(this, delete_immediately);
         }
       }
     }

--- a/hotspot/src/share/vm/gc/g1/g1CollectedHeap.cpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/gc/g1/g1CollectedHeap.cpp	Tue Oct 13 10:06:46 2015 +0200
@@ -4592,12 +4592,7 @@
 public:
 
   void clean_klass(InstanceKlass* ik) {
-    ik->clean_implementors_list(_is_alive);
-    ik->clean_method_data(_is_alive);
-
-    // G1 specific cleanup work that has
-    // been moved here to be done in parallel.
-    ik->clean_dependent_nmethods();
+    ik->clean_weak_instanceklass_links(_is_alive);
   }
 
   void work() {

--- a/hotspot/src/share/vm/oops/instanceKlass.cpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/oops/instanceKlass.cpp	Tue Oct 13 10:06:46 2015 +0200
@@ -1907,18 +1907,33 @@
 // Decrement count of the nmethod in the dependency list and remove
 // the bucket completely when the count goes to 0.  This method must
 // find a corresponding bucket otherwise there's a bug in the
-// recording of dependencies. Returns true if the bucket is ready for reclamation.
-//
-bool nmethodBucket::remove_dependent_nmethod(nmethodBucket* deps, nmethod* nm) {
+// recording of dependencies. Returns true if the bucket was deleted,
+// or marked ready for reclaimation.
+bool nmethodBucket::remove_dependent_nmethod(nmethodBucket** deps, nmethod* nm, bool delete_immediately) {
   assert_locked_or_safepoint(CodeCache_lock);
 
-  for (nmethodBucket* b = deps; b != NULL; b = b->next()) {
+  nmethodBucket* first = *deps;
+  nmethodBucket* last = NULL;
+
+  for (nmethodBucket* b = first; b != NULL; b = b->next()) {
     if (nm == b->get_nmethod()) {
       int val = b->decrement();
       guarantee(val >= 0, "Underflow: %d", val);
-      return (val == 0);
+      if (val == 0) {
+        if (delete_immediately) {
+          if (last == NULL) {
+            *deps = b->next();
+          } else {
+            last->set_next(b->next());
+          }
+          delete b;
+        }
+      }
+      return true;
     }
+    last = b;
   }
+
 #ifdef ASSERT
   tty->print_raw_cr("### can't find dependent nmethod");
   nm->print();
@@ -1927,6 +1942,12 @@
   return false;
 }
 
+// Convenience overload, for callers that don't want to delete the nmethodBucket entry.
+bool nmethodBucket::remove_dependent_nmethod(nmethodBucket* deps, nmethod* nm) {
+  nmethodBucket** deps_addr = &deps;
+  return remove_dependent_nmethod(deps_addr, nm, false /* Don't delete */);
+}
+
 //
 // Reclaim all unused buckets. Returns new head of the list.
 //
@@ -2013,10 +2034,10 @@
   _dependencies = nmethodBucket::add_dependent_nmethod(_dependencies, nm);
 }
 
-void InstanceKlass::remove_dependent_nmethod(nmethod* nm) {
+void InstanceKlass::remove_dependent_nmethod(nmethod* nm, bool delete_immediately) {
   assert_locked_or_safepoint(CodeCache_lock);
 
-  if (nmethodBucket::remove_dependent_nmethod(_dependencies, nm)) {
+  if (nmethodBucket::remove_dependent_nmethod(&_dependencies, nm, delete_immediately)) {
     set_has_unloaded_dependent(true);
   }
 }
@@ -2031,6 +2052,13 @@
 }
 #endif //PRODUCT
 
+void InstanceKlass::clean_weak_instanceklass_links(BoolObjectClosure* is_alive) {
+  clean_implementors_list(is_alive);
+  clean_method_data(is_alive);
+
+  clean_dependent_nmethods();
+}
+
 void InstanceKlass::clean_implementors_list(BoolObjectClosure* is_alive) {
   assert(class_loader_data()->is_alive(is_alive), "this klass should be live");
   if (is_interface()) {
@@ -3546,3 +3574,199 @@
 unsigned char * InstanceKlass::get_cached_class_file_bytes() {
   return VM_RedefineClasses::get_cached_class_file_bytes(_cached_class_file);
 }
+
+
+/////////////// Unit tests ///////////////
+
+#ifndef PRODUCT
+
+class TestNmethodBucketContext {
+ public:
+  nmethod* _nmethodLast;
+  nmethod* _nmethodMiddle;
+  nmethod* _nmethodFirst;
+
+  nmethodBucket* _bucketLast;
+  nmethodBucket* _bucketMiddle;
+  nmethodBucket* _bucketFirst;
+
+  nmethodBucket* _bucketList;
+
+  TestNmethodBucketContext() {
+    CodeCache_lock->lock_without_safepoint_check();
+
+    _nmethodLast   = reinterpret_cast<nmethod*>(0x8 * 0);
+    _nmethodMiddle = reinterpret_cast<nmethod*>(0x8 * 1);
+    _nmethodFirst  = reinterpret_cast<nmethod*>(0x8 * 2);
+
+    _bucketLast   = new nmethodBucket(_nmethodLast,   NULL);
+    _bucketMiddle = new nmethodBucket(_nmethodMiddle, _bucketLast);
+    _bucketFirst  = new nmethodBucket(_nmethodFirst,   _bucketMiddle);
+
+    _bucketList = _bucketFirst;
+  }
+
+  ~TestNmethodBucketContext() {
+    delete _bucketLast;
+    delete _bucketMiddle;
+    delete _bucketFirst;
+
+    CodeCache_lock->unlock();
+  }
+};
+
+class TestNmethodBucket {
+ public:
+  static void testRemoveDependentNmethodFirstDeleteImmediately() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodFirst, true /* delete */);
+
+    assert(c._bucketList == c._bucketMiddle, "check");
+    assert(c._bucketList->next() == c._bucketLast, "check");
+    assert(c._bucketList->next()->next() == NULL, "check");
+
+    // Cleanup before context is deleted.
+    c._bucketFirst = NULL;
+  }
+
+  static void testRemoveDependentNmethodMiddleDeleteImmediately() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodMiddle, true /* delete */);
+
+    assert(c._bucketList == c._bucketFirst, "check");
+    assert(c._bucketList->next() == c._bucketLast, "check");
+    assert(c._bucketList->next()->next() == NULL, "check");
+
+    // Cleanup before context is deleted.
+    c._bucketMiddle = NULL;
+  }
+
+  static void testRemoveDependentNmethodLastDeleteImmediately() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodLast, true /* delete */);
+
+    assert(c._bucketList == c._bucketFirst, "check");
+    assert(c._bucketList->next() == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next() == NULL, "check");
+
+    // Cleanup before context is deleted.
+    c._bucketLast = NULL;
+  }
+
+  static void testRemoveDependentNmethodFirstDeleteDeferred() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodFirst, false /* delete */);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 0, "check");
+    assert(c._bucketMiddle->count() == 1, "check");
+    assert(c._bucketLast->count()   == 1, "check");
+  }
+
+  static void testRemoveDependentNmethodMiddleDeleteDeferred() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodMiddle, false /* delete */);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 1, "check");
+    assert(c._bucketMiddle->count() == 0, "check");
+    assert(c._bucketLast->count()   == 1, "check");
+  }
+
+  static void testRemoveDependentNmethodLastDeleteDeferred() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(&c._bucketList, c._nmethodLast, false /* delete */);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 1, "check");
+    assert(c._bucketMiddle->count() == 1, "check");
+    assert(c._bucketLast->count()   == 0, "check");
+  }
+
+  static void testRemoveDependentNmethodConvenienceFirst() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(c._bucketList, c._nmethodFirst);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 0, "check");
+    assert(c._bucketMiddle->count() == 1, "check");
+    assert(c._bucketLast->count()   == 1, "check");
+  }
+
+  static void testRemoveDependentNmethodConvenienceMiddle() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(c._bucketList, c._nmethodMiddle);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 1, "check");
+    assert(c._bucketMiddle->count() == 0, "check");
+    assert(c._bucketLast->count()   == 1, "check");
+  }
+
+  static void testRemoveDependentNmethodConvenienceLast() {
+    TestNmethodBucketContext c;
+
+    nmethodBucket::remove_dependent_nmethod(c._bucketList, c._nmethodLast);
+
+    assert(c._bucketList                         == c._bucketFirst,  "check");
+    assert(c._bucketList->next()                 == c._bucketMiddle, "check");
+    assert(c._bucketList->next()->next()         == c._bucketLast,   "check");
+    assert(c._bucketList->next()->next()->next() == NULL,            "check");
+
+    assert(c._bucketFirst->count()  == 1, "check");
+    assert(c._bucketMiddle->count() == 1, "check");
+    assert(c._bucketLast->count()   == 0, "check");
+  }
+
+  static void testRemoveDependentNmethod() {
+    testRemoveDependentNmethodFirstDeleteImmediately();
+    testRemoveDependentNmethodMiddleDeleteImmediately();
+    testRemoveDependentNmethodLastDeleteImmediately();
+
+    testRemoveDependentNmethodFirstDeleteDeferred();
+    testRemoveDependentNmethodMiddleDeleteDeferred();
+    testRemoveDependentNmethodLastDeleteDeferred();
+
+    testRemoveDependentNmethodConvenienceFirst();
+    testRemoveDependentNmethodConvenienceMiddle();
+    testRemoveDependentNmethodConvenienceLast();
+  }
+
+  static void test() {
+    testRemoveDependentNmethod();
+  }
+};
+
+void TestNmethodBucket_test() {
+  TestNmethodBucket::test();
+}
+
+#endif

--- a/hotspot/src/share/vm/oops/instanceKlass.hpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/oops/instanceKlass.hpp	Tue Oct 13 10:06:46 2015 +0200
@@ -837,7 +837,7 @@
   // maintenance of deoptimization dependencies
   int mark_dependent_nmethods(DepChange& changes);
   void add_dependent_nmethod(nmethod* nm);
-  void remove_dependent_nmethod(nmethod* nm);
+  void remove_dependent_nmethod(nmethod* nm, bool delete_immediately);
 
   // On-stack replacement support
   nmethod* osr_nmethods_head() const         { return _osr_nmethods_head; };
@@ -1021,6 +1021,7 @@
   void adjust_default_methods(InstanceKlass* holder, bool* trace_name_printed);
 #endif // INCLUDE_JVMTI
 
+  void clean_weak_instanceklass_links(BoolObjectClosure* is_alive);
   void clean_implementors_list(BoolObjectClosure* is_alive);
   void clean_method_data(BoolObjectClosure* is_alive);
   void clean_dependent_nmethods();
@@ -1349,6 +1350,7 @@
 
   static int mark_dependent_nmethods(nmethodBucket* deps, DepChange& changes);
   static nmethodBucket* add_dependent_nmethod(nmethodBucket* deps, nmethod* nm);
+  static bool remove_dependent_nmethod(nmethodBucket** deps, nmethod* nm, bool delete_immediately);
   static bool remove_dependent_nmethod(nmethodBucket* deps, nmethod* nm);
   static nmethodBucket* clean_dependent_nmethods(nmethodBucket* deps);
 #ifndef PRODUCT

--- a/hotspot/src/share/vm/oops/klass.cpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/oops/klass.cpp	Tue Oct 13 10:06:46 2015 +0200
@@ -442,8 +442,7 @@
     // Clean the implementors list and method data.
     if (clean_alive_klasses && current->oop_is_instance()) {
       InstanceKlass* ik = InstanceKlass::cast(current);
-      ik->clean_implementors_list(is_alive);
-      ik->clean_method_data(is_alive);
+      ik->clean_weak_instanceklass_links(is_alive);
     }
   }
 }

--- a/hotspot/src/share/vm/prims/jni.cpp	Tue Oct 20 11:17:19 2015 -0400
+++ b/hotspot/src/share/vm/prims/jni.cpp	Tue Oct 13 10:06:46 2015 +0200
@@ -3852,6 +3852,7 @@
   unit_test_function_call
 
 // Forward declaration
+void TestNmethodBucket_test();
 void test_semaphore();
 void TestOS_test();
 void TestReservedSpace_test();
@@ -3880,6 +3881,7 @@
 void execute_internal_vm_tests() {
   if (ExecuteInternalVMTests) {
     tty->print_cr("Running internal VM tests");
+    run_unit_test(TestNmethodBucket_test());
     run_unit_test(test_semaphore());
     run_unit_test(TestOS_test());
     run_unit_test(TestReservedSpace_test());