--- a/src/hotspot/share/aot/aotCodeHeap.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotCodeHeap.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -690,6 +690,28 @@
   return false;
 }
 
+void AOTCodeHeap::mark_evol_dependent_methods(InstanceKlass* dependee) {
+  AOTKlassData* klass_data = find_klass(dependee);
+  if (klass_data == NULL) {
+    return; // no AOT records for this class - no dependencies
+  }
+  if (!dependee->has_passed_fingerprint_check()) {
+    return; // different class
+  }
+
+  int methods_offset = klass_data->_dependent_methods_offset;
+  if (methods_offset >= 0) {
+    address methods_cnt_adr = _dependencies + methods_offset;
+    int methods_cnt = *(int*)methods_cnt_adr;
+    int* indexes = (int*)(methods_cnt_adr + 4);
+    for (int i = 0; i < methods_cnt; ++i) {
+      int code_id = indexes[i];
+      AOTCompiledMethod* aot = _code_to_aot[code_id]._aot;
+      aot->mark_for_deoptimization(false);
+    }
+  }
+}
+
 void AOTCodeHeap::sweep_dependent_methods(int* indexes, int methods_cnt) {
   int marked = 0;
   for (int i = 0; i < methods_cnt; ++i) {

--- a/src/hotspot/share/aot/aotCodeHeap.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotCodeHeap.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -244,6 +244,7 @@
   Klass* get_klass_from_got(const char* klass_name, int klass_len, const Method* method);
 
   bool is_dependent_method(Klass* dependee, AOTCompiledMethod* aot);
+  void mark_evol_dependent_methods(InstanceKlass* dependee);
 
   const char* get_name_at(int offset) {
     return _metaspace_names + offset;

--- a/src/hotspot/share/aot/aotCompiledMethod.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotCompiledMethod.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -428,10 +428,6 @@
   return pltcall->instruction_address();
 }
 
-bool AOTCompiledMethod::is_evol_dependent_on(Klass* dependee) {
-  return !is_aot_runtime_stub() && _heap->is_dependent_method(dependee, this);
-}
-
 void AOTCompiledMethod::clear_inline_caches() {
   assert(SafepointSynchronize::is_at_safepoint(), "cleaning of IC's only allowed at safepoint");
   if (is_zombie()) {

--- a/src/hotspot/share/aot/aotCompiledMethod.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotCompiledMethod.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -206,7 +206,8 @@
   // AOT compiled methods do not get into zombie state
   virtual bool can_convert_to_zombie() { return false; }
 
-  virtual bool is_evol_dependent_on(Klass* dependee);
+  // Evol dependent methods already marked.
+  virtual bool is_evol_dependent() { return false; }
   virtual bool is_dependent_on_method(Method* dependee) { return true; }
 
   virtual void clear_inline_caches();

--- a/src/hotspot/share/aot/aotLoader.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotLoader.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -86,6 +86,14 @@
   }
 }
 
+void AOTLoader::mark_evol_dependent_methods(InstanceKlass* dependee) {
+  if (UseAOT) {
+    FOR_ALL_AOT_HEAPS(heap) {
+      (*heap)->mark_evol_dependent_methods(dependee);
+    }
+  }
+}
+
 /**
  * List of core modules for which we search for shared libraries.
  */

--- a/src/hotspot/share/aot/aotLoader.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/aot/aotLoader.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -63,6 +63,7 @@
   static uint64_t get_saved_fingerprint(InstanceKlass* ik) NOT_AOT({ return 0; });
   static void oops_do(OopClosure* f) NOT_AOT_RETURN;
   static void metadata_do(void f(Metadata*)) NOT_AOT_RETURN;
+  static void mark_evol_dependent_methods(InstanceKlass* dependee) NOT_AOT_RETURN;
 
   NOT_PRODUCT( static void print_statistics() NOT_AOT_RETURN; )
 

--- a/src/hotspot/share/code/codeCache.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/code/codeCache.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -1200,9 +1200,9 @@
 #endif
 }
 
-int CodeCache::mark_for_evol_deoptimization(InstanceKlass* dependee) {
+// Just marks the methods in this class as needing deoptimization
+void CodeCache::mark_for_evol_deoptimization(InstanceKlass* dependee) {
   MutexLockerEx mu(CodeCache_lock, Mutex::_no_safepoint_check_flag);
-  int number_of_marked_CodeBlobs = 0;
 
   // Deoptimize all methods of the evolving class itself
   Array<Method*>* old_methods = dependee->methods();
@@ -1212,16 +1212,24 @@
     CompiledMethod* nm = old_method->code();
     if (nm != NULL) {
       nm->mark_for_deoptimization();
-      number_of_marked_CodeBlobs++;
     }
   }
 
+  // Mark dependent AOT nmethods, which are only found via the class redefined.
+  AOTLoader::mark_evol_dependent_methods(dependee);
+}
+
+// Walk compiled methods and mark dependent methods for deoptimization.
+int CodeCache::mark_dependents_for_evol_deoptimization() {
+  int number_of_marked_CodeBlobs = 0;
   CompiledMethodIterator iter(CompiledMethodIterator::only_alive_and_not_unloading);
   while(iter.next()) {
     CompiledMethod* nm = iter.method();
     if (nm->is_marked_for_deoptimization()) {
-      // ...Already marked in the previous pass; don't count it again.
-    } else if (nm->is_evol_dependent_on(dependee)) {
+      // ...Already marked in the previous pass; count it here.
+      // Also counts AOT compiled methods, already marked.
+      number_of_marked_CodeBlobs++;
+    } else if (nm->is_evol_dependent()) {
       ResourceMark rm;
       nm->mark_for_deoptimization();
       number_of_marked_CodeBlobs++;
@@ -1231,6 +1239,8 @@
     }
   }
 
+  // return total count of nmethods marked for deoptimization, if zero the caller
+  // can skip deoptimization
   return number_of_marked_CodeBlobs;
 }
 
@@ -1294,34 +1304,30 @@
   }
 }
 
-// Flushes compiled methods dependent on dependee when the dependee is redefined
-// via RedefineClasses
-void CodeCache::flush_evol_dependents_on(InstanceKlass* ev_k) {
+// Flushes compiled methods dependent on redefined classes, that have already been
+// marked for deoptimization.
+void CodeCache::flush_evol_dependents() {
   // --- Compile_lock is not held. However we are at a safepoint.
   assert_locked_or_safepoint(Compile_lock);
-  if (number_of_nmethods_with_dependencies() == 0 && !UseAOT) return;
 
   // CodeCache can only be updated by a thread_in_VM and they will all be
   // stopped during the safepoint so CodeCache will be safe to update without
   // holding the CodeCache_lock.
 
-  // Compute the dependent nmethods
-  if (mark_for_evol_deoptimization(ev_k) > 0) {
-    // At least one nmethod has been marked for deoptimization
+  // At least one nmethod has been marked for deoptimization
 
-    // All this already happens inside a VM_Operation, so we'll do all the work here.
-    // Stuff copied from VM_Deoptimize and modified slightly.
+  // All this already happens inside a VM_Operation, so we'll do all the work here.
+  // Stuff copied from VM_Deoptimize and modified slightly.
 
-    // We do not want any GCs to happen while we are in the middle of this VM operation
-    ResourceMark rm;
-    DeoptimizationMarker dm;
+  // We do not want any GCs to happen while we are in the middle of this VM operation
+  ResourceMark rm;
+  DeoptimizationMarker dm;
 
-    // Deoptimize all activations depending on marked nmethods
-    Deoptimization::deoptimize_dependents();
+  // Deoptimize all activations depending on marked nmethods
+  Deoptimization::deoptimize_dependents();
 
-    // Make the dependent methods not entrant
-    make_marked_nmethods_not_entrant();
-  }
+  // Make the dependent methods not entrant
+  make_marked_nmethods_not_entrant();
 }
 
 // Flushes compiled methods dependent on dependee

--- a/src/hotspot/share/code/codeCache.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/code/codeCache.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -288,7 +288,6 @@
   // Deoptimization
  private:
   static int  mark_for_deoptimization(KlassDepChange& changes);
-  static int  mark_for_evol_deoptimization(InstanceKlass* dependee);
 
  public:
   static void mark_all_nmethods_for_deoptimization();
@@ -298,7 +297,9 @@
   // Flushing and deoptimization
   static void flush_dependents_on(InstanceKlass* dependee);
   // Flushing and deoptimization in case of evolution
-  static void flush_evol_dependents_on(InstanceKlass* dependee);
+  static void mark_for_evol_deoptimization(InstanceKlass* dependee);
+  static int  mark_dependents_for_evol_deoptimization();
+  static void flush_evol_dependents();
   // Support for fullspeed debugging
   static void flush_dependents_on_method(const methodHandle& dependee);
 

--- a/src/hotspot/share/code/compiledMethod.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/code/compiledMethod.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -367,7 +367,7 @@
   int  verify_icholder_relocations();
   void verify_oop_relocations();
 
-  virtual bool is_evol_dependent_on(Klass* dependee) = 0;
+  virtual bool is_evol_dependent() = 0;
   // Fast breakpoint support. Tells if this compiled method is
   // dependent on the given method. Returns true if this nmethod
   // corresponds to the given method as well.

--- a/src/hotspot/share/code/nmethod.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/code/nmethod.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -2021,30 +2021,26 @@
   return found_check;
 }
 
-bool nmethod::is_evol_dependent_on(Klass* dependee) {
-  InstanceKlass *dependee_ik = InstanceKlass::cast(dependee);
-  Array<Method*>* dependee_methods = dependee_ik->methods();
+bool nmethod::is_evol_dependent() {
   for (Dependencies::DepStream deps(this); deps.next(); ) {
     if (deps.type() == Dependencies::evol_method) {
       Method* method = deps.method_argument(0);
-      for (int j = 0; j < dependee_methods->length(); j++) {
-        if (dependee_methods->at(j) == method) {
-          if (log_is_enabled(Debug, redefine, class, nmethod)) {
-            ResourceMark rm;
-            log_debug(redefine, class, nmethod)
-              ("Found evol dependency of nmethod %s.%s(%s) compile_id=%d on method %s.%s(%s)",
-               _method->method_holder()->external_name(),
-               _method->name()->as_C_string(),
-               _method->signature()->as_C_string(),
-               compile_id(),
-               method->method_holder()->external_name(),
-               method->name()->as_C_string(),
-               method->signature()->as_C_string());
-          }
-          if (TraceDependencies || LogCompilation)
-            deps.log_dependency(dependee);
-          return true;
+      if (method->is_old()) {
+        if (log_is_enabled(Debug, redefine, class, nmethod)) {
+          ResourceMark rm;
+          log_debug(redefine, class, nmethod)
+            ("Found evol dependency of nmethod %s.%s(%s) compile_id=%d on method %s.%s(%s)",
+             _method->method_holder()->external_name(),
+             _method->name()->as_C_string(),
+             _method->signature()->as_C_string(),
+             compile_id(),
+             method->method_holder()->external_name(),
+             method->name()->as_C_string(),
+             method->signature()->as_C_string());
         }
+        if (TraceDependencies || LogCompilation)
+          deps.log_dependency(method->method_holder());
+        return true;
       }
     }
   }

--- a/src/hotspot/share/code/nmethod.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/code/nmethod.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -588,9 +588,9 @@
   bool check_dependency_on(DepChange& changes);
 
   // Evolution support. Tells if this compiled method is dependent on any of
-  // methods m() of class dependee, such that if m() in dependee is replaced,
+  // redefined methods, such that if m() is replaced,
   // this compiled method will have to be deoptimized.
-  bool is_evol_dependent_on(Klass* dependee);
+  bool is_evol_dependent();
 
   // Fast breakpoint support. Tells if this compiled method is
   // dependent on the given method. Returns true if this nmethod

--- a/src/hotspot/share/prims/jvmtiRedefineClasses.cpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/prims/jvmtiRedefineClasses.cpp	Tue Feb 05 10:40:25 2019 -0500
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 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
@@ -123,6 +123,7 @@
     _res = JVMTI_ERROR_NULL_POINTER;
     return false;
   }
+
   for (int i = 0; i < _class_count; i++) {
     if (_class_defs[i].klass == NULL) {
       _res = JVMTI_ERROR_INVALID_CLASS;
@@ -209,6 +210,9 @@
     redefine_single_class(_class_defs[i].klass, _scratch_classes[i], thread);
   }
 
+  // Flush all compiled code that depends on the classes redefined.
+  flush_dependent_code();
+
   // Clean out MethodData pointing to old Method*
   // Have to do this after all classes are redefined and all methods that
   // are redefined are marked as old.
@@ -3836,28 +3840,41 @@
 // subsequent calls to RedefineClasses need only throw away code
 // that depends on the class.
 //
-void VM_RedefineClasses::flush_dependent_code(InstanceKlass* ik, TRAPS) {
+
+// First step is to walk the code cache for each class redefined and mark
+// dependent methods.  Wait until all classes are processed to deoptimize everything.
+void VM_RedefineClasses::mark_dependent_code(InstanceKlass* ik) {
   assert_locked_or_safepoint(Compile_lock);
 
   // All dependencies have been recorded from startup or this is a second or
   // subsequent use of RedefineClasses
   if (JvmtiExport::all_dependencies_are_recorded()) {
-    CodeCache::flush_evol_dependents_on(ik);
-  } else {
+    CodeCache::mark_for_evol_deoptimization(ik);
+  }
+}
+
+void VM_RedefineClasses::flush_dependent_code() {
+  assert(SafepointSynchronize::is_at_safepoint(), "sanity check");
+
+  bool deopt_needed;
+
+  // This is the first redefinition, mark all the nmethods for deoptimization
+  if (!JvmtiExport::all_dependencies_are_recorded()) {
+    log_debug(redefine, class, nmethod)("Marked all nmethods for deopt");
     CodeCache::mark_all_nmethods_for_deoptimization();
-
-    ResourceMark rm(THREAD);
-    DeoptimizationMarker dm;
-
-    // Deoptimize all activations depending on marked nmethods
-    Deoptimization::deoptimize_dependents();
-
-    // Make the dependent methods not entrant
-    CodeCache::make_marked_nmethods_not_entrant();
-
-    // From now on we know that the dependency information is complete
-    JvmtiExport::set_all_dependencies_are_recorded(true);
+    deopt_needed = true;
+  } else {
+    int deopt = CodeCache::mark_dependents_for_evol_deoptimization();
+    log_debug(redefine, class, nmethod)("Marked %d dependent nmethods for deopt", deopt);
+    deopt_needed = (deopt != 0);
   }
+
+  if (deopt_needed) {
+    CodeCache::flush_evol_dependents();
+  }
+
+  // From now on we know that the dependency information is complete
+  JvmtiExport::set_all_dependencies_are_recorded(true);
 }
 
 void VM_RedefineClasses::compute_added_deleted_matching_methods() {
@@ -3958,8 +3975,8 @@
   JvmtiBreakpoints& jvmti_breakpoints = JvmtiCurrentBreakpoints::get_jvmti_breakpoints();
   jvmti_breakpoints.clearall_in_class_at_safepoint(the_class);
 
-  // Deoptimize all compiled code that depends on this class
-  flush_dependent_code(the_class, THREAD);
+  // Mark all compiled code that depends on this class
+  mark_dependent_code(the_class);
 
   _old_methods = the_class->methods();
   _new_methods = scratch_class->methods();

--- a/src/hotspot/share/prims/jvmtiRedefineClasses.hpp	Thu Jan 31 23:56:37 2019 +0800
+++ b/src/hotspot/share/prims/jvmtiRedefineClasses.hpp	Tue Feb 05 10:40:25 2019 -0500
@@ -493,7 +493,8 @@
          InstanceKlass* scratch_class,
          constantPoolHandle scratch_cp, int scratch_cp_length, TRAPS);
 
-  void flush_dependent_code(InstanceKlass* ik, TRAPS);
+  void flush_dependent_code();
+  void mark_dependent_code(InstanceKlass* ik);
 
   // lock classes to redefine since constant pool merging isn't thread safe.
   void lock_classes();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/runtime/RedefineTests/TestMultipleClasses.java	Tue Feb 05 10:40:25 2019 -0500
@@ -0,0 +1,120 @@
+/*
+ * 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.
+ */
+
+/*
+ * @test
+ * @bug 8139551
+ * @summary Scalability problem with redefinition - multiple code cache walks
+ * @library /test/lib
+ * @modules java.base/jdk.internal.misc
+ * @modules java.compiler
+ *          java.instrument
+ *          jdk.jartool/sun.tools.jar
+ * @run main RedefineClassHelper
+ * @run main/othervm/timeout=180 -javaagent:redefineagent.jar -XX:CompileThreshold=100 -Xlog:redefine+class+nmethod=debug TestMultipleClasses
+ */
+
+import java.lang.instrument.*;
+import java.lang.reflect.*;
+import jdk.test.lib.compiler.InMemoryJavaCompiler;
+
+public class TestMultipleClasses extends ClassLoader {
+
+    public static String B(int count) {
+        return new String("public class B" + count + " {" +
+                "   public static void compiledMethod() { " +
+                "       try{" +
+                "          Thread.sleep(1); " +
+                "       } catch(InterruptedException ie) {" +
+                "       }" +
+                "   }" +
+                "}");
+    }
+
+    static String newB(int count) {
+        return new String("public class B" + count + " {" +
+                "   public static void compiledMethod() { " +
+                "       System.out.println(\"compiledMethod called " + count + "\");" +
+                "   }" +
+                "}");
+    }
+
+    static int index = 0;
+
+    @Override
+    protected Class<?> findClass(String name) throws ClassNotFoundException {
+        if (name.equals("B" + index)) {
+            byte[] b = InMemoryJavaCompiler.compile(name, B(index));
+            return defineClass(name, b, 0, b.length);
+        } else {
+            return super.findClass(name);
+        }
+    }
+
+    static void runCompiledMethodMethods(Class c, int count) throws Exception {
+        // Run for a while so they compile.
+        Object o = c.newInstance();
+        Method m = c.getMethod("compiledMethod");
+        for (int i = 0; i < count; i++) {
+            m.invoke(o);
+        }
+    }
+
+    public static void main(String[] args) throws Exception {
+
+        final int numberOfClasses = 20;
+        Class[] classes = new Class[numberOfClasses];
+        byte[][] newClass = new byte[numberOfClasses][];
+        ClassDefinition[] defs = new ClassDefinition[numberOfClasses];
+
+        TestMultipleClasses loader = new TestMultipleClasses();
+
+        // Load and start all the classes.
+        for (index = 0; index < numberOfClasses; index++) {
+            String name = new String("B" + index);
+            Class c = loader.findClass(name);
+
+            runCompiledMethodMethods(c, 500);
+            // Make class definition for redefinition
+            classes[index] = c;
+            newClass[index] = InMemoryJavaCompiler.compile(c.getName(), newB(index));
+            defs[index] = new ClassDefinition(c, newClass[index]);
+        }
+
+        long startTime = System.currentTimeMillis();
+
+        // Redefine all classes.
+        RedefineClassHelper.instrumentation.redefineClasses(defs);
+
+        long endTime = System.currentTimeMillis();
+
+        System.out.println("Redefinition took " + (endTime - startTime) + " milliseconds");
+
+        System.gc();
+
+        // Run all new classes.
+        for (index = 0; index < numberOfClasses; index++) {
+            runCompiledMethodMethods(classes[index], 1);
+        }
+    }
+}