--- a/src/share/vm/code/nmethod.cpp	Wed Dec 02 17:48:20 2015 -0800
+++ b/src/share/vm/code/nmethod.cpp	Thu Nov 12 09:53:17 2015 +0100
@@ -1619,7 +1619,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/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Wed Dec 02 17:48:20 2015 -0800
+++ b/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Thu Nov 12 09:53:17 2015 +0100
@@ -5045,12 +5045,8 @@
 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);
+
     if (JvmtiExport::has_redefined_a_class()) {
       InstanceKlass::purge_previous_versions(ik);
     }

--- a/src/share/vm/oops/instanceKlass.cpp	Wed Dec 02 17:48:20 2015 -0800
+++ b/src/share/vm/oops/instanceKlass.cpp	Thu Nov 12 09:53:17 2015 +0100
@@ -1969,7 +1969,7 @@
 // find a corresponding bucket otherwise there's a bug in the
 // recording of dependecies.
 //
-void InstanceKlass::remove_dependent_nmethod(nmethod* nm) {
+void InstanceKlass::remove_dependent_nmethod(nmethod* nm, bool delete_immediately) {
   assert_locked_or_safepoint(CodeCache_lock);
   nmethodBucket* b = _dependencies;
   nmethodBucket* last = NULL;
@@ -1978,7 +1978,17 @@
       int val = b->decrement();
       guarantee(val >= 0, err_msg("Underflow: %d", val));
       if (val == 0) {
-        set_has_unloaded_dependent(true);
+        if (delete_immediately) {
+          if (last == NULL) {
+            _dependencies = b->next();
+          } else {
+            last->set_next(b->next());
+          }
+          delete b;
+        } else {
+          // The deletion of this entry is deferred until a later, potentially parallel GC phase.
+          set_has_unloaded_dependent(true);
+        }
       }
       return;
     }
@@ -2318,6 +2328,13 @@
 
 #endif // INCLUDE_ALL_GCS
 
+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()) {

--- a/src/share/vm/oops/instanceKlass.hpp	Wed Dec 02 17:48:20 2015 -0800
+++ b/src/share/vm/oops/instanceKlass.hpp	Thu Nov 12 09:53:17 2015 +0100
@@ -785,7 +785,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; };
@@ -974,6 +974,7 @@
   void oop_follow_contents(oop obj);
   int  oop_adjust_pointers(oop obj);
 
+  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();

--- a/src/share/vm/oops/klass.cpp	Wed Dec 02 17:48:20 2015 -0800
+++ b/src/share/vm/oops/klass.cpp	Thu Nov 12 09:53:17 2015 +0100
@@ -454,8 +454,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);
     }
   }
 }