--- a/src/hotspot/share/classfile/classLoaderDataGraph.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/classfile/classLoaderDataGraph.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -29,6 +29,7 @@
 #include "classfile/metadataOnStackMark.hpp"
 #include "classfile/moduleEntry.hpp"
 #include "classfile/packageEntry.hpp"
+#include "code/dependencyContext.hpp"
 #include "logging/log.hpp"
 #include "logging/logStream.hpp"
 #include "memory/allocation.inline.hpp"
@@ -597,6 +598,7 @@
     Metaspace::purge();
     set_metaspace_oom(false);
   }
+  DependencyContext::purge_dependency_contexts();
 }
 
 int ClassLoaderDataGraph::resize_if_needed() {

--- a/src/hotspot/share/classfile/javaClasses.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/classfile/javaClasses.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -3741,6 +3741,7 @@
 // Support for java_lang_invoke_MethodHandleNatives_CallSiteContext
 
 int java_lang_invoke_MethodHandleNatives_CallSiteContext::_vmdependencies_offset;
+int java_lang_invoke_MethodHandleNatives_CallSiteContext::_last_cleanup_offset;
 
 void java_lang_invoke_MethodHandleNatives_CallSiteContext::compute_offsets() {
   InstanceKlass* k = SystemDictionary::Context_klass();
@@ -3755,8 +3756,9 @@
 
 DependencyContext java_lang_invoke_MethodHandleNatives_CallSiteContext::vmdependencies(oop call_site) {
   assert(java_lang_invoke_MethodHandleNatives_CallSiteContext::is_instance(call_site), "");
-  intptr_t* vmdeps_addr = (intptr_t*)call_site->field_addr(_vmdependencies_offset);
-  DependencyContext dep_ctx(vmdeps_addr);
+  nmethodBucket* volatile* vmdeps_addr = (nmethodBucket* volatile*)call_site->field_addr(_vmdependencies_offset);
+  volatile uint64_t* last_cleanup_addr = (volatile uint64_t*)call_site->field_addr(_last_cleanup_offset);
+  DependencyContext dep_ctx(vmdeps_addr, last_cleanup_addr);
   return dep_ctx;
 }
 

--- a/src/hotspot/share/classfile/javaClasses.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/classfile/javaClasses.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -1201,7 +1201,8 @@
 // Interface to java.lang.invoke.MethodHandleNatives$CallSiteContext objects
 
 #define CALLSITECONTEXT_INJECTED_FIELDS(macro) \
-  macro(java_lang_invoke_MethodHandleNatives_CallSiteContext, vmdependencies, intptr_signature, false)
+  macro(java_lang_invoke_MethodHandleNatives_CallSiteContext, vmdependencies, intptr_signature, false) \
+  macro(java_lang_invoke_MethodHandleNatives_CallSiteContext, last_cleanup, long_signature, false)
 
 class DependencyContext;
 
@@ -1210,6 +1211,7 @@
 
 private:
   static int _vmdependencies_offset;
+  static int _last_cleanup_offset;
 
   static void compute_offsets();
 

--- a/src/hotspot/share/classfile/vmSymbols.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/classfile/vmSymbols.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -426,6 +426,7 @@
   template(signers_name,                              "signers_name")                             \
   template(loader_data_name,                          "loader_data")                              \
   template(vmdependencies_name,                       "vmdependencies")                           \
+  template(last_cleanup_name,                         "last_cleanup")                             \
   template(loader_name,                               "loader")                                   \
   template(getModule_name,                            "getModule")                                \
   template(input_stream_void_signature,               "(Ljava/io/InputStream;)V")                 \

--- a/src/hotspot/share/code/codeBlob.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/codeBlob.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -116,7 +116,12 @@
 
   CodeBlob(const char* name, CompilerType type, const CodeBlobLayout& layout, int frame_complete_offset, int frame_size, ImmutableOopMapSet* oop_maps, bool caller_must_gc_arguments);
   CodeBlob(const char* name, CompilerType type, const CodeBlobLayout& layout, CodeBuffer* cb, int frame_complete_offset, int frame_size, OopMapSet* oop_maps, bool caller_must_gc_arguments);
+
 public:
+  // Only used by unit test.
+  CodeBlob()
+    : _type(compiler_none) {}
+
   // Returns the space needed for CodeBlob
   static unsigned int allocation_size(CodeBuffer* cb, int header_size);
   static unsigned int align_code_offset(int offset);

--- a/src/hotspot/share/code/codeCache.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/codeCache.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -29,6 +29,7 @@
 #include "code/codeHeapState.hpp"
 #include "code/compiledIC.hpp"
 #include "code/dependencies.hpp"
+#include "code/dependencyContext.hpp"
 #include "code/icBuffer.hpp"
 #include "code/nmethod.hpp"
 #include "code/pcDesc.hpp"
@@ -940,6 +941,19 @@
   }
 }
 
+CodeCache::UnloadingScope::UnloadingScope(BoolObjectClosure* is_alive)
+  : _is_unloading_behaviour(is_alive)
+{
+  IsUnloadingBehaviour::set_current(&_is_unloading_behaviour);
+  increment_unloading_cycle();
+  DependencyContext::cleaning_start();
+}
+
+CodeCache::UnloadingScope::~UnloadingScope() {
+  IsUnloadingBehaviour::set_current(NULL);
+  DependencyContext::cleaning_end();
+}
+
 void CodeCache::verify_oops() {
   MutexLockerEx mu(CodeCache_lock, Mutex::_no_safepoint_check_flag);
   VerifyOopClosure voc;

--- a/src/hotspot/share/code/codeCache.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/codeCache.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -180,17 +180,10 @@
     ClosureIsUnloadingBehaviour _is_unloading_behaviour;
 
   public:
-    UnloadingScope(BoolObjectClosure* is_alive)
-      : _is_unloading_behaviour(is_alive)
-    {
-      IsUnloadingBehaviour::set_current(&_is_unloading_behaviour);
-      increment_unloading_cycle();
-    }
+    UnloadingScope(BoolObjectClosure* is_alive);
+    ~UnloadingScope();
+  };
 
-    ~UnloadingScope() {
-      IsUnloadingBehaviour::set_current(NULL);
-    }
-  };
   static void do_unloading(BoolObjectClosure* is_alive, bool unloading_occurred);
   static uint8_t unloading_cycle() { return _unloading_cycle; }
   static void increment_unloading_cycle();

--- a/src/hotspot/share/code/compiledMethod.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/compiledMethod.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -177,6 +177,9 @@
   CompiledMethod(Method* method, const char* name, CompilerType type, int size, int header_size, CodeBuffer* cb, int frame_complete_offset, int frame_size, OopMapSet* oop_maps, bool caller_must_gc_arguments);
 
 public:
+  // Only used by unit test.
+  CompiledMethod() {}
+
   virtual bool is_compiled() const                { return true; }
 
   template<typename T>

--- a/src/hotspot/share/code/dependencyContext.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/dependencyContext.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -35,6 +35,8 @@
 PerfCounter* DependencyContext::_perf_total_buckets_deallocated_count = NULL;
 PerfCounter* DependencyContext::_perf_total_buckets_stale_count       = NULL;
 PerfCounter* DependencyContext::_perf_total_buckets_stale_acc_count   = NULL;
+nmethodBucket* volatile DependencyContext::_purge_list = NULL;
+volatile uint64_t DependencyContext::_cleaning_epoch = 0;
 
 void dependencyContext_init() {
   DependencyContext::init();
@@ -61,7 +63,7 @@
 //
 int DependencyContext::mark_dependent_nmethods(DepChange& changes) {
   int found = 0;
-  for (nmethodBucket* b = dependencies(); b != NULL; b = b->next()) {
+  for (nmethodBucket* b = dependencies_not_unloading(); b != NULL; b = b->next_not_unloading()) {
     nmethod* nm = b->get_nmethod();
     // since dependencies aren't removed until an nmethod becomes a zombie,
     // the dependency list may contain nmethods which aren't alive.
@@ -86,21 +88,49 @@
 // so a count is kept for each bucket to guarantee that creation and
 // deletion of dependencies is consistent.
 //
-void DependencyContext::add_dependent_nmethod(nmethod* nm, bool expunge) {
+void DependencyContext::add_dependent_nmethod(nmethod* nm) {
   assert_lock_strong(CodeCache_lock);
-  for (nmethodBucket* b = dependencies(); b != NULL; b = b->next()) {
+  for (nmethodBucket* b = dependencies_not_unloading(); b != NULL; b = b->next_not_unloading()) {
     if (nm == b->get_nmethod()) {
       b->increment();
       return;
     }
   }
-  set_dependencies(new nmethodBucket(nm, dependencies()));
+  nmethodBucket* new_head = new nmethodBucket(nm, NULL);
+  for (;;) {
+    nmethodBucket* head = Atomic::load(_dependency_context_addr);
+    new_head->set_next(head);
+    if (Atomic::cmpxchg(new_head, _dependency_context_addr, head) == head) {
+      break;
+    }
+  }
   if (UsePerfData) {
     _perf_total_buckets_allocated_count->inc();
   }
+}
+
+void DependencyContext::release(nmethodBucket* b) {
+  bool expunge = Atomic::load(&_cleaning_epoch) == 0;
   if (expunge) {
-    // Remove stale entries from the list.
-    expunge_stale_entries();
+    assert_locked_or_safepoint(CodeCache_lock);
+    delete b;
+    if (UsePerfData) {
+      _perf_total_buckets_deallocated_count->inc();
+    }
+  } else {
+    // Mark the context as having stale entries, since it is not safe to
+    // expunge the list right now.
+    for (;;) {
+      nmethodBucket* purge_list_head = Atomic::load(&_purge_list);
+      b->set_purge_list_next(purge_list_head);
+      if (Atomic::cmpxchg(b, &_purge_list, purge_list_head) == purge_list_head) {
+        break;
+      }
+    }
+    if (UsePerfData) {
+      _perf_total_buckets_stale_count->inc();
+      _perf_total_buckets_stale_acc_count->inc();
+    }
   }
 }
 
@@ -111,92 +141,71 @@
 // a corresponding bucket otherwise there's a bug in the recording of dependencies.
 // Can be called concurrently by parallel GC threads.
 //
-void DependencyContext::remove_dependent_nmethod(nmethod* nm, bool expunge) {
+void DependencyContext::remove_dependent_nmethod(nmethod* nm) {
   assert_locked_or_safepoint(CodeCache_lock);
-  nmethodBucket* first = dependencies();
+  nmethodBucket* first = dependencies_not_unloading();
   nmethodBucket* last = NULL;
-  for (nmethodBucket* b = first; b != NULL; b = b->next()) {
+  for (nmethodBucket* b = first; b != NULL; b = b->next_not_unloading()) {
     if (nm == b->get_nmethod()) {
       int val = b->decrement();
       guarantee(val >= 0, "Underflow: %d", val);
       if (val == 0) {
-        if (expunge) {
-          if (last == NULL) {
-            set_dependencies(b->next());
-          } else {
-            last->set_next(b->next());
-          }
-          delete b;
-          if (UsePerfData) {
-            _perf_total_buckets_deallocated_count->inc();
-          }
+        if (last == NULL) {
+          // If there was not a head that was not unloading, we can set a new
+          // head without a CAS, because we know there is no contending cleanup.
+          set_dependencies(b->next_not_unloading());
         } else {
-          // Mark the context as having stale entries, since it is not safe to
-          // expunge the list right now.
-          set_has_stale_entries(true);
-          if (UsePerfData) {
-            _perf_total_buckets_stale_count->inc();
-            _perf_total_buckets_stale_acc_count->inc();
-          }
+          // Only supports a single inserting thread (protected by CodeCache_lock)
+          // for now. Therefore, the next pointer only competes with another cleanup
+          // operation. That interaction does not need a CAS.
+          last->set_next(b->next_not_unloading());
         }
-      }
-      if (expunge) {
-        // Remove stale entries from the list.
-        expunge_stale_entries();
+        release(b);
       }
       return;
     }
     last = b;
   }
-#ifdef ASSERT
-  tty->print_raw_cr("### can't find dependent nmethod");
-  nm->print();
-#endif // ASSERT
-  ShouldNotReachHere();
 }
 
 //
 // Reclaim all unused buckets.
 //
-void DependencyContext::expunge_stale_entries() {
-  assert_locked_or_safepoint(CodeCache_lock);
-  if (!has_stale_entries()) {
-    assert(!find_stale_entries(), "inconsistent info");
+void DependencyContext::purge_dependency_contexts() {
+  int removed = 0;
+  for (nmethodBucket* b = _purge_list; b != NULL;) {
+    nmethodBucket* next = b->purge_list_next();
+    removed++;
+    delete b;
+    b = next;
+  }
+  if (UsePerfData && removed > 0) {
+    _perf_total_buckets_deallocated_count->inc(removed);
+  }
+  _purge_list = NULL;
+}
+
+//
+// Cleanup a dependency context by unlinking and placing all dependents corresponding
+// to is_unloading nmethods on a purge list, which will be deleted later when it is safe.
+void DependencyContext::clean_unloading_dependents() {
+  if (!claim_cleanup()) {
+    // Somebody else is cleaning up this dependency context.
     return;
   }
-  nmethodBucket* first = dependencies();
-  nmethodBucket* last = NULL;
-  int removed = 0;
-  for (nmethodBucket* b = first; b != NULL;) {
-    assert(b->count() >= 0, "bucket count: %d", b->count());
-    nmethodBucket* next = b->next();
-    if (b->count() == 0) {
-      if (last == NULL) {
-        first = next;
-      } else {
-        last->set_next(next);
-      }
-      removed++;
-      delete b;
-      // last stays the same.
-    } else {
-      last = b;
-    }
+  // Walk the nmethodBuckets and move dead entries on the purge list, which will
+  // be deleted during ClassLoaderDataGraph::purge().
+  nmethodBucket* b = dependencies_not_unloading();
+  while (b != NULL) {
+    nmethodBucket* next = b->next_not_unloading();
     b = next;
   }
-  set_dependencies(first);
-  set_has_stale_entries(false);
-  if (UsePerfData && removed > 0) {
-    _perf_total_buckets_deallocated_count->inc(removed);
-    _perf_total_buckets_stale_count->dec(removed);
-  }
 }
 
 //
 // Invalidate all dependencies in the context
 int DependencyContext::remove_all_dependents() {
-  assert_locked_or_safepoint(CodeCache_lock);
-  nmethodBucket* b = dependencies();
+  nmethodBucket* b = dependencies_not_unloading();
   set_dependencies(NULL);
   int marked = 0;
   int removed = 0;
@@ -206,12 +215,11 @@
       nm->mark_for_deoptimization();
       marked++;
     }
-    nmethodBucket* next = b->next();
+    nmethodBucket* next = b->next_not_unloading();
     removed++;
-    delete b;
+    release(b);
     b = next;
   }
-  set_has_stale_entries(false);
   if (UsePerfData && removed > 0) {
     _perf_total_buckets_deallocated_count->inc(removed);
   }
@@ -221,7 +229,7 @@
 #ifndef PRODUCT
 void DependencyContext::print_dependent_nmethods(bool verbose) {
   int idx = 0;
-  for (nmethodBucket* b = dependencies(); b != NULL; b = b->next()) {
+  for (nmethodBucket* b = dependencies_not_unloading(); b != NULL; b = b->next_not_unloading()) {
     nmethod* nm = b->get_nmethod();
     tty->print("[%d] count=%d { ", idx++, b->count());
     if (!verbose) {
@@ -236,7 +244,7 @@
 }
 
 bool DependencyContext::is_dependent_nmethod(nmethod* nm) {
-  for (nmethodBucket* b = dependencies(); b != NULL; b = b->next()) {
+  for (nmethodBucket* b = dependencies_not_unloading(); b != NULL; b = b->next_not_unloading()) {
     if (nm == b->get_nmethod()) {
 #ifdef ASSERT
       int count = b->count();
@@ -248,15 +256,112 @@
   return false;
 }
 
-bool DependencyContext::find_stale_entries() {
-  for (nmethodBucket* b = dependencies(); b != NULL; b = b->next()) {
-    if (b->count() == 0)  return true;
-  }
-  return false;
-}
-
 #endif //PRODUCT
 
 int nmethodBucket::decrement() {
   return Atomic::sub(1, &_count);
 }
+
+// We use a safepoint counter to track the safepoint counter the last time a given
+// dependency context was cleaned. GC threads claim cleanup tasks by performing
+// a CAS on this value.
+bool DependencyContext::claim_cleanup() {
+  uint64_t cleaning_epoch = Atomic::load(&_cleaning_epoch);
+  uint64_t last_cleanup = Atomic::load(_last_cleanup_addr);
+  if (last_cleanup >= cleaning_epoch) {
+    return false;
+  }
+  return Atomic::cmpxchg(cleaning_epoch, _last_cleanup_addr, last_cleanup) == last_cleanup;
+}
+
+// Retrieve the first nmethodBucket that has a dependent that does not correspond to
+// an is_unloading nmethod. Any nmethodBucket entries observed from the original head
+// that is_unloading() will be unlinked and placed on the purge list.
+nmethodBucket* DependencyContext::dependencies_not_unloading() {
+  for (;;) {
+    // Need acquire becase the read value could come from a concurrent insert.
+    nmethodBucket* head = OrderAccess::load_acquire(_dependency_context_addr);
+    if (head == NULL || !head->get_nmethod()->is_unloading()) {
+      return head;
+    }
+    nmethodBucket* head_next = head->next();
+    OrderAccess::loadload();
+    if (Atomic::load(_dependency_context_addr) != head) {
+      // Unstable load of head w.r.t. head->next
+      continue;
+    }
+    if (Atomic::cmpxchg(head_next, _dependency_context_addr, head) == head) {
+      // Release is_unloading entries if unlinking was claimed
+      DependencyContext::release(head);
+    }
+  }
+}
+
+// Relaxed accessors
+void DependencyContext::set_dependencies(nmethodBucket* b) {
+  Atomic::store(b, _dependency_context_addr);
+}
+
+nmethodBucket* DependencyContext::dependencies() {
+  return Atomic::load(_dependency_context_addr);
+}
+
+// After the gc_prologue, the dependency contexts may be claimed by the GC
+// and releasing of nmethodBucket entries will be deferred and placed on
+// a purge list to be deleted later.
+void DependencyContext::cleaning_start() {
+  assert(SafepointSynchronize::is_at_safepoint(), "must be");
+  uint64_t epoch = SafepointSynchronize::safepoint_counter();
+  Atomic::store(epoch, &_cleaning_epoch);
+}
+
+// The epilogue marks the end of dependency context cleanup by the GC,
+// and also makes subsequent releases of nmethodBuckets case immediate
+// deletion. It is admitted to end the cleanup in a concurrent phase.
+void DependencyContext::cleaning_end() {
+  uint64_t epoch = 0;
+  Atomic::store(epoch, &_cleaning_epoch);
+}
+
+// This function skips over nmethodBuckets in the list corresponding to
+// nmethods that are is_unloading. This allows exposing a view of the
+// dependents as-if they were already cleaned, despite being cleaned
+// concurrently. Any entry observed that is_unloading() will be unlinked
+// and placed on the purge list.
+nmethodBucket* nmethodBucket::next_not_unloading() {
+  for (;;) {
+    // Do not need acquire because the loaded entry can never be
+    // concurrently inserted.
+    nmethodBucket* next = Atomic::load(&_next);
+    if (next == NULL || !next->get_nmethod()->is_unloading()) {
+      return next;
+    }
+    nmethodBucket* next_next = Atomic::load(&next->_next);
+    OrderAccess::loadload();
+    if (Atomic::load(&_next) != next) {
+      // Unstable load of next w.r.t. next->next
+      continue;
+    }
+    if (Atomic::cmpxchg(next_next, &_next, next) == next) {
+      // Release is_unloading entries if unlinking was claimed
+      DependencyContext::release(next);
+    }
+  }
+}
+
+// Relaxed accessors
+nmethodBucket* nmethodBucket::next() {
+  return Atomic::load(&_next);
+}
+
+void nmethodBucket::set_next(nmethodBucket* b) {
+  Atomic::store(b, &_next);
+}
+
+nmethodBucket* nmethodBucket::purge_list_next() {
+  return Atomic::load(&_purge_list_next);
+}
+
+void nmethodBucket::set_purge_list_next(nmethodBucket* b) {
+  Atomic::store(b, &_purge_list_next);
+}

--- a/src/hotspot/share/code/dependencyContext.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/dependencyContext.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -48,70 +48,50 @@
   friend class VMStructs;
  private:
   nmethod*       _nmethod;
-  int            _count;
-  nmethodBucket* _next;
+  volatile int   _count;
+  nmethodBucket* volatile _next;
+  nmethodBucket* volatile _purge_list_next;
 
  public:
   nmethodBucket(nmethod* nmethod, nmethodBucket* next) :
-   _nmethod(nmethod), _count(1), _next(next) {}
+    _nmethod(nmethod), _count(1), _next(next), _purge_list_next(NULL) {}
 
-  int count()                             { return _count; }
-  int increment()                         { _count += 1; return _count; }
+  int count()                                { return _count; }
+  int increment()                            { _count += 1; return _count; }
   int decrement();
-  nmethodBucket* next()                   { return _next; }
-  void set_next(nmethodBucket* b)         { _next = b; }
-  nmethod* get_nmethod()                  { return _nmethod; }
+  nmethodBucket* next();
+  nmethodBucket* next_not_unloading();
+  void set_next(nmethodBucket* b);
+  nmethodBucket* purge_list_next();
+  void set_purge_list_next(nmethodBucket* b);
+  nmethod* get_nmethod()                     { return _nmethod; }
 };
 
 //
 // Utility class to manipulate nmethod dependency context.
-// The context consists of nmethodBucket* (a head of a linked list)
-// and a boolean flag (does the list contains stale entries). The structure is
-// encoded as an intptr_t: lower bit is used for the flag. It is possible since
-// nmethodBucket* is aligned - the structure is malloc'ed in C heap.
 // Dependency context can be attached either to an InstanceKlass (_dep_context field)
 // or CallSiteContext oop for call_site_target dependencies (see javaClasses.hpp).
-// DependencyContext class operates on some location which holds a intptr_t value.
+// DependencyContext class operates on some location which holds a nmethodBucket* value
+// and uint64_t integer recording the safepoint counter at the last cleanup.
 //
 class DependencyContext : public StackObj {
   friend class VMStructs;
   friend class TestDependencyContext;
  private:
-  enum TagBits { _has_stale_entries_bit = 1, _has_stale_entries_mask = 1 };
-
-  intptr_t* _dependency_context_addr;
-
-  void set_dependencies(nmethodBucket* b) {
-    assert((intptr_t(b) & _has_stale_entries_mask) == 0, "should be aligned");
-    if (has_stale_entries()) {
-      *_dependency_context_addr = intptr_t(b) | _has_stale_entries_mask;
-    } else {
-      *_dependency_context_addr = intptr_t(b);
-    }
-  }
+  nmethodBucket* volatile* _dependency_context_addr;
+  volatile uint64_t*       _last_cleanup_addr;
 
-  void set_has_stale_entries(bool x) {
-    if (x) {
-      *_dependency_context_addr |= _has_stale_entries_mask;
-    } else {
-      *_dependency_context_addr &= ~_has_stale_entries_mask;
-    }
-  }
-
-  nmethodBucket* dependencies() {
-    intptr_t value = *_dependency_context_addr;
-    return (nmethodBucket*) (value & ~_has_stale_entries_mask);
-  }
-
-  bool has_stale_entries() const {
-    intptr_t value = *_dependency_context_addr;
-    return (value & _has_stale_entries_mask) != 0;
-  }
+  bool claim_cleanup();
+  void set_dependencies(nmethodBucket* b);
+  nmethodBucket* dependencies();
+  nmethodBucket* dependencies_not_unloading();
 
   static PerfCounter* _perf_total_buckets_allocated_count;
   static PerfCounter* _perf_total_buckets_deallocated_count;
   static PerfCounter* _perf_total_buckets_stale_count;
   static PerfCounter* _perf_total_buckets_stale_acc_count;
+  static nmethodBucket* volatile _purge_list;
+  static volatile uint64_t       _cleaning_epoch;
 
  public:
 #ifdef ASSERT
@@ -120,31 +100,35 @@
   // (e.g. CallSiteContext Java object).
   uint64_t _safepoint_counter;
 
-  DependencyContext(intptr_t* addr) : _dependency_context_addr(addr),
-    _safepoint_counter(SafepointSynchronize::safepoint_counter()) {}
+  DependencyContext(nmethodBucket* volatile* bucket_addr, volatile uint64_t* last_cleanup_addr)
+    : _dependency_context_addr(bucket_addr),
+      _last_cleanup_addr(last_cleanup_addr),
+      _safepoint_counter(SafepointSynchronize::safepoint_counter()) {}
 
   ~DependencyContext() {
     assert(_safepoint_counter == SafepointSynchronize::safepoint_counter(), "safepoint happened");
   }
 #else
-  DependencyContext(intptr_t* addr) : _dependency_context_addr(addr) {}
+  DependencyContext(nmethodBucket* volatile* bucket_addr, volatile uint64_t* last_cleanup_addr)
+    : _dependency_context_addr(bucket_addr),
+      _last_cleanup_addr(last_cleanup_addr) {}
 #endif // ASSERT
 
-  static const intptr_t EMPTY = 0; // dependencies = NULL, has_stale_entries = false
-
   static void init();
 
   int  mark_dependent_nmethods(DepChange& changes);
-  void add_dependent_nmethod(nmethod* nm, bool expunge_stale_entries = false);
-  void remove_dependent_nmethod(nmethod* nm, bool expunge_stale_entries = false);
+  void add_dependent_nmethod(nmethod* nm);
+  void remove_dependent_nmethod(nmethod* nm);
   int  remove_all_dependents();
-
-  void expunge_stale_entries();
+  void clean_unloading_dependents();
+  static void purge_dependency_contexts();
+  static void release(nmethodBucket* b);
+  static void cleaning_start();
+  static void cleaning_end();
 
 #ifndef PRODUCT
   void print_dependent_nmethods(bool verbose);
   bool is_dependent_nmethod(nmethod* nm);
-  bool find_stale_entries();
 #endif //PRODUCT
 };
 #endif // SHARE_VM_CODE_DEPENDENCYCONTEXT_HPP

--- a/src/hotspot/share/code/nmethod.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/nmethod.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -1372,8 +1372,8 @@
 // notifies instanceKlasses that are reachable
 
 void nmethod::flush_dependencies(bool delete_immediately) {
-  assert_locked_or_safepoint(CodeCache_lock);
-  assert(Universe::heap()->is_gc_active() != delete_immediately,
+  DEBUG_ONLY(bool called_by_gc = Universe::heap()->is_gc_active() || Thread::current()->is_ConcurrentGC_thread();)
+  assert(called_by_gc != delete_immediately,
   "delete_immediately is false if and only if we are called during GC");
   if (!has_flushed_dependencies()) {
     set_has_flushed_dependencies();
@@ -1381,7 +1381,12 @@
       if (deps.type() == Dependencies::call_site_target_value) {
         // CallSite dependencies are managed on per-CallSite instance basis.
         oop call_site = deps.argument_oop(0);
-        MethodHandles::remove_dependent_nmethod(call_site, this);
+        if (delete_immediately) {
+          assert_locked_or_safepoint(CodeCache_lock);
+          MethodHandles::remove_dependent_nmethod(call_site, this);
+        } else {
+          MethodHandles::clean_dependency_context(call_site);
+        }
       } else {
         Klass* klass = deps.context_type();
         if (klass == NULL) {
@@ -1389,11 +1394,12 @@
         }
         // During GC delete_immediately is false, and liveness
         // of dependee determines class that needs to be updated.
-        if (delete_immediately || klass->is_loader_alive()) {
-          // 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.
-          InstanceKlass::cast(klass)->remove_dependent_nmethod(this, delete_immediately);
+        if (delete_immediately) {
+          assert_locked_or_safepoint(CodeCache_lock);
+          InstanceKlass::cast(klass)->remove_dependent_nmethod(this);
+        } else if (klass->is_loader_alive()) {
+          // The GC may clean dependency contexts concurrently and in parallel.
+          InstanceKlass::cast(klass)->clean_dependency_context();
         }
       }
     }

--- a/src/hotspot/share/code/nmethod.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/code/nmethod.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -257,6 +257,14 @@
 #endif
   );
 
+  // Only used for unit tests.
+  nmethod()
+    : CompiledMethod(),
+      _is_unloading_state(0),
+      _native_receiver_sp_offset(in_ByteSize(-1)),
+      _native_basic_lock_sp_offset(in_ByteSize(-1)) {}
+
+
   static nmethod* new_native_nmethod(const methodHandle& method,
                                      int compile_id,
                                      CodeBuffer *code_buffer,

--- a/src/hotspot/share/oops/instanceKlass.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/oops/instanceKlass.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -2117,7 +2117,7 @@
 }
 
 inline DependencyContext InstanceKlass::dependencies() {
-  DependencyContext dep_context(&_dep_context);
+  DependencyContext dep_context(&_dep_context, &_dep_context_last_cleaned);
   return dep_context;
 }
 
@@ -2129,8 +2129,12 @@
   dependencies().add_dependent_nmethod(nm);
 }
 
-void InstanceKlass::remove_dependent_nmethod(nmethod* nm, bool delete_immediately) {
-  dependencies().remove_dependent_nmethod(nm, delete_immediately);
+void InstanceKlass::remove_dependent_nmethod(nmethod* nm) {
+  dependencies().remove_dependent_nmethod(nm);
+}
+
+void InstanceKlass::clean_dependency_context() {
+  dependencies().clean_unloading_dependents();
 }
 
 #ifndef PRODUCT
@@ -2146,10 +2150,6 @@
 void InstanceKlass::clean_weak_instanceklass_links() {
   clean_implementors_list();
   clean_method_data();
-
-  // Since GC iterates InstanceKlasses sequentially, it is safe to remove stale entries here.
-  DependencyContext dep_context(&_dep_context);
-  dep_context.expunge_stale_entries();
 }
 
 void InstanceKlass::clean_implementors_list() {
@@ -2334,7 +2334,7 @@
   // These are not allocated from metaspace, but they should should all be empty
   // during dump time, so we don't need to worry about them in InstanceKlass::iterate().
   guarantee(_source_debug_extension == NULL, "must be");
-  guarantee(_dep_context == DependencyContext::EMPTY, "must be");
+  guarantee(_dep_context == NULL, "must be");
   guarantee(_osr_nmethods_head == NULL, "must be");
 
 #if INCLUDE_JVMTI
@@ -2479,7 +2479,7 @@
     FreeHeap(jmeths);
   }
 
-  assert(_dep_context == DependencyContext::EMPTY,
+  assert(_dep_context == NULL,
          "dependencies should already be cleaned");
 
 #if INCLUDE_JVMTI

--- a/src/hotspot/share/oops/instanceKlass.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/oops/instanceKlass.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -69,6 +69,7 @@
 class jniIdMapBase;
 class JNIid;
 class JvmtiCachedClassFieldMap;
+class nmethodBucket;
 class SuperTypeClosure;
 
 // This is used in iterators below.
@@ -249,7 +250,8 @@
   OopMapCache*    volatile _oop_map_cache;   // OopMapCache for all methods in the klass (allocated lazily)
   JNIid*          _jni_ids;              // First JNI identifier for static fields in this class
   jmethodID*      volatile _methods_jmethod_ids;  // jmethodIDs corresponding to method_idnum, or NULL if none
-  intptr_t        _dep_context;          // packed DependencyContext structure
+  nmethodBucket*  volatile _dep_context;          // packed DependencyContext structure
+  uint64_t        volatile _dep_context_last_cleaned;
   nmethod*        _osr_nmethods_head;    // Head of list of on-stack replacement nmethods for this class
 #if INCLUDE_JVMTI
   BreakpointInfo* _breakpoints;          // bpt lists, managed by Method*
@@ -976,7 +978,8 @@
   inline DependencyContext dependencies();
   int  mark_dependent_nmethods(KlassDepChange& changes);
   void add_dependent_nmethod(nmethod* nm);
-  void remove_dependent_nmethod(nmethod* nm, bool delete_immediately);
+  void remove_dependent_nmethod(nmethod* nm);
+  void clean_dependency_context();
 
   // On-stack replacement support
   nmethod* osr_nmethods_head() const         { return _osr_nmethods_head; };

--- a/src/hotspot/share/prims/methodHandles.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/prims/methodHandles.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -1064,14 +1064,6 @@
   return rfill + overflow;
 }
 
-// Is it safe to remove stale entries from a dependency list?
-static bool safe_to_expunge() {
-  // Since parallel GC threads can concurrently iterate over a dependency
-  // list during safepoint, it is safe to remove entries only when
-  // CodeCache lock is held.
-  return CodeCache_lock->owned_by_self();
-}
-
 void MethodHandles::add_dependent_nmethod(oop call_site, nmethod* nm) {
   assert_locked_or_safepoint(CodeCache_lock);
 
@@ -1082,7 +1074,7 @@
   // in order to avoid memory leak, stale entries are purged whenever a dependency list
   // is changed (both on addition and removal). Though memory reclamation is delayed,
   // it avoids indefinite memory usage growth.
-  deps.add_dependent_nmethod(nm, /*expunge_stale_entries=*/safe_to_expunge());
+  deps.add_dependent_nmethod(nm);
 }
 
 void MethodHandles::remove_dependent_nmethod(oop call_site, nmethod* nm) {
@@ -1090,7 +1082,15 @@
 
   oop context = java_lang_invoke_CallSite::context_no_keepalive(call_site);
   DependencyContext deps = java_lang_invoke_MethodHandleNatives_CallSiteContext::vmdependencies(context);
-  deps.remove_dependent_nmethod(nm, /*expunge_stale_entries=*/safe_to_expunge());
+  deps.remove_dependent_nmethod(nm);
+}
+
+void MethodHandles::clean_dependency_context(oop call_site) {
+  assert_locked_or_safepoint(CodeCache_lock);
+
+  oop context = java_lang_invoke_CallSite::context_no_keepalive(call_site);
+  DependencyContext deps = java_lang_invoke_MethodHandleNatives_CallSiteContext::vmdependencies(context);
+  deps.clean_unloading_dependents();
 }
 
 void MethodHandles::flush_dependent_nmethods(Handle call_site, Handle target) {
@@ -1500,7 +1500,6 @@
     {
       NoSafepointVerifier nsv;
       MutexLockerEx mu2(CodeCache_lock, Mutex::_no_safepoint_check_flag);
-      assert(safe_to_expunge(), "removal is not safe");
       DependencyContext deps = java_lang_invoke_MethodHandleNatives_CallSiteContext::vmdependencies(context());
       marked = deps.remove_all_dependents();
     }

--- a/src/hotspot/share/prims/methodHandles.hpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/hotspot/share/prims/methodHandles.hpp	Fri Nov 30 11:40:48 2018 +0100
@@ -79,6 +79,7 @@
   // CallSite support
   static void add_dependent_nmethod(oop call_site, nmethod* nm);
   static void remove_dependent_nmethod(oop call_site, nmethod* nm);
+  static void clean_dependency_context(oop call_site);
 
   static void flush_dependent_nmethods(Handle call_site, Handle target);
 

--- a/src/java.base/share/classes/java/lang/invoke/MethodHandleNatives.java	Fri Nov 30 20:15:25 2018 +0900
+++ b/src/java.base/share/classes/java/lang/invoke/MethodHandleNatives.java	Fri Nov 30 11:40:48 2018 +0100
@@ -75,6 +75,7 @@
     /** Represents a context to track nmethod dependencies on CallSite instance target. */
     static class CallSiteContext implements Runnable {
         //@Injected JVM_nmethodBucket* vmdependencies;
+        //@Injected jlong last_cleanup;
 
         static CallSiteContext make(CallSite cs) {
             final CallSiteContext newContext = new CallSiteContext();

--- a/test/hotspot/gtest/code/test_dependencyContext.cpp	Fri Nov 30 20:15:25 2018 +0900
+++ b/test/hotspot/gtest/code/test_dependencyContext.cpp	Fri Nov 30 11:40:48 2018 +0100
@@ -24,29 +24,33 @@
 
 #include "precompiled.hpp"
 #include "code/dependencyContext.hpp"
+#include "code/nmethod.hpp"
 #include "unittest.hpp"
 
 class TestDependencyContext {
  public:
-  nmethod* _nmethods[3];
+  nmethod _nmethods[3];
 
-  intptr_t _dependency_context;
+  nmethodBucket* volatile _dependency_context;
+  volatile uint64_t _last_cleanup;
 
   DependencyContext dependencies() {
-    DependencyContext depContext(&_dependency_context);
+    DependencyContext depContext(&_dependency_context, &_last_cleanup);
     return depContext;
   }
 
-  TestDependencyContext() : _dependency_context(DependencyContext::EMPTY) {
+  TestDependencyContext()
+    : _dependency_context(NULL),
+      _last_cleanup(0) {
     CodeCache_lock->lock_without_safepoint_check();
 
-    _nmethods[0] = reinterpret_cast<nmethod*>(0x8 * 0);
-    _nmethods[1] = reinterpret_cast<nmethod*>(0x8 * 1);
-    _nmethods[2] = reinterpret_cast<nmethod*>(0x8 * 2);
+    _nmethods[0].clear_unloading_state();
+    _nmethods[1].clear_unloading_state();
+    _nmethods[2].clear_unloading_state();
 
-    dependencies().add_dependent_nmethod(_nmethods[2]);
-    dependencies().add_dependent_nmethod(_nmethods[1]);
-    dependencies().add_dependent_nmethod(_nmethods[0]);
+    dependencies().add_dependent_nmethod(&_nmethods[2]);
+    dependencies().add_dependent_nmethod(&_nmethods[1]);
+    dependencies().add_dependent_nmethod(&_nmethods[0]);
   }
 
   ~TestDependencyContext() {
@@ -54,21 +58,10 @@
     CodeCache_lock->unlock();
   }
 
-  static bool has_stale_entries(DependencyContext ctx) {
-    return ctx.has_stale_entries();
-  }
-
-#ifndef PRODUCT
-  static bool find_stale_entries(DependencyContext ctx) {
-    return ctx.find_stale_entries();
-  }
-#endif
-
   void wipe() {
-    DependencyContext ctx(&_dependency_context);
+    DependencyContext ctx(&_dependency_context, &_last_cleanup);
     nmethodBucket* b = ctx.dependencies();
     ctx.set_dependencies(NULL);
-    ctx.set_has_stale_entries(false);
     while (b != NULL) {
       nmethodBucket* next = b->next();
       delete b;
@@ -77,33 +70,18 @@
   }
 };
 
-static void test_remove_dependent_nmethod(int id, bool delete_immediately) {
+static void test_remove_dependent_nmethod(int id) {
   TestDependencyContext c;
   DependencyContext depContext = c.dependencies();
-  NOT_PRODUCT(ASSERT_FALSE(TestDependencyContext::find_stale_entries(depContext)));
-  ASSERT_FALSE(TestDependencyContext::has_stale_entries(depContext));
-
-  nmethod* nm = c._nmethods[id];
-  depContext.remove_dependent_nmethod(nm, delete_immediately);
 
-  if (!delete_immediately) {
-    NOT_PRODUCT(ASSERT_TRUE(TestDependencyContext::find_stale_entries(depContext)));
-    ASSERT_TRUE(TestDependencyContext::has_stale_entries(depContext));
-    NOT_PRODUCT(ASSERT_TRUE(depContext.is_dependent_nmethod(nm)));
-    depContext.expunge_stale_entries();
-  }
+  nmethod* nm = &c._nmethods[id];
+  depContext.remove_dependent_nmethod(nm);
 
-  NOT_PRODUCT(ASSERT_FALSE(TestDependencyContext::find_stale_entries(depContext)));
-  ASSERT_FALSE(TestDependencyContext::has_stale_entries(depContext));
   NOT_PRODUCT(ASSERT_FALSE(depContext.is_dependent_nmethod(nm)));
 }
 
 TEST_VM(code, dependency_context) {
-  test_remove_dependent_nmethod(0, false);
-  test_remove_dependent_nmethod(1, false);
-  test_remove_dependent_nmethod(2, false);
-
-  test_remove_dependent_nmethod(0, true);
-  test_remove_dependent_nmethod(1, true);
-  test_remove_dependent_nmethod(2, true);
+  test_remove_dependent_nmethod(0);
+  test_remove_dependent_nmethod(1);
+  test_remove_dependent_nmethod(2);
 }