Reland "Walk up the super chain to find an IMT to share."

This reverts commit ef0b1544519f91fc5663b06d433da474115feb5a.

Bug: 266937358

Reason for revert: Fix wrong assumption: an IMT being shared can be
updated for subclasses, but we need to use the right allocator.

Change-Id: I0055a81d30199e5cba53f21a5b759fe530a0dfa2

7 files changed, 280 insertions, 16 deletions

diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index c772a9c29a..08457852a4 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -5988,17 +5988,6 @@ ClassTable* ClassLinker::ClassTableForClassLoader(ObjPtr<mirror::ClassLoader> cl
   return class_loader == nullptr ? boot_class_table_.get() : class_loader->GetClassTable();
 }
 
-static ImTable* FindSuperImt(ObjPtr<mirror::Class> klass, PointerSize pointer_size)
-    REQUIRES_SHARED(Locks::mutator_lock_) {
-  while (klass->HasSuperClass()) {
-    klass = klass->GetSuperClass();
-    if (klass->ShouldHaveImt()) {
-      return klass->GetImt(pointer_size);
-    }
-  }
-  return nullptr;
-}
-
 bool ClassLinker::LinkClass(Thread* self,
                             const char* descriptor,
                             Handle<mirror::Class> klass,
@@ -6034,7 +6023,7 @@ bool ClassLinker::LinkClass(Thread* self,
     // will possibly create a table that is incorrect for either of the classes.
     // Same IMT with new_conflict does not happen very often.
     if (!new_conflict) {
-      ImTable* super_imt = FindSuperImt(klass.Get(), image_pointer_size_);
+      ImTable* super_imt = klass->FindSuperImt(image_pointer_size_);
       if (super_imt != nullptr) {
         bool imt_equals = true;
         for (size_t i = 0; i < ImTable::kSize && imt_equals; ++i) {
@@ -6317,13 +6306,36 @@ class MethodNameAndSignatureComparator final : public ValueObject {
   std::string_view name_view_;
 };
 
+static ObjPtr<mirror::Class> GetImtOwner(ObjPtr<mirror::Class> klass)
+    REQUIRES_SHARED(Locks::mutator_lock_) {
+  ImTable* imt = klass->GetImt(kRuntimePointerSize);
+  DCHECK(imt != nullptr);
+  while (klass->HasSuperClass()) {
+    ObjPtr<mirror::Class> super_class = klass->GetSuperClass();
+    if (super_class->ShouldHaveImt() && imt != super_class->GetImt(kRuntimePointerSize)) {
+      // IMT not shared with the super class, return the current class.
+      return klass;
+    }
+    klass = super_class;
+  }
+  return nullptr;
+}
+
 ArtMethod* ClassLinker::AddMethodToConflictTable(ObjPtr<mirror::Class> klass,
                                                  ArtMethod* conflict_method,
                                                  ArtMethod* interface_method,
                                                  ArtMethod* method) {
   ImtConflictTable* current_table = conflict_method->GetImtConflictTable(kRuntimePointerSize);
   Runtime* const runtime = Runtime::Current();
-  LinearAlloc* linear_alloc = GetAllocatorForClassLoader(klass->GetClassLoader());
+
+  // The IMT may be shared with a super class, in which case we need to use that
+  // super class's `LinearAlloc`. The conflict itself should be limited to
+  // methods at or higher up the chain of the IMT owner, otherwise class
+  // linker would have created a different IMT.
+  ObjPtr<mirror::Class> imt_owner = GetImtOwner(klass);
+  DCHECK(imt_owner != nullptr);
+
+  LinearAlloc* linear_alloc = GetAllocatorForClassLoader(imt_owner->GetClassLoader());
 
   // Create a new entry if the existing one is the shared conflict method.
   ArtMethod* new_conflict_method = (conflict_method == runtime->GetImtConflictMethod())
@@ -6408,9 +6420,8 @@ void ClassLinker::FillIMTAndConflictTables(ObjPtr<mirror::Class> klass) {
   // Compare the IMT with the super class including the conflict methods. If they are equivalent,
   // we can just use the same pointer.
   ImTable* imt = nullptr;
-  ObjPtr<mirror::Class> super_class = klass->GetSuperClass();
-  if (super_class != nullptr && super_class->ShouldHaveImt()) {
-    ImTable* super_imt = super_class->GetImt(image_pointer_size_);
+  ImTable* super_imt = klass->FindSuperImt(image_pointer_size_);
+  if (super_imt != nullptr) {
     bool same = true;
     for (size_t i = 0; same && i < ImTable::kSize; ++i) {
       ArtMethod* method = imt_data[i];
@@ -6439,6 +6450,7 @@ void ClassLinker::FillIMTAndConflictTables(ObjPtr<mirror::Class> klass) {
   if (imt == nullptr) {
     imt = klass->GetImt(image_pointer_size_);
     DCHECK(imt != nullptr);
+    DCHECK_NE(imt, super_imt);
     imt->Populate(imt_data, image_pointer_size_);
   } else {
     klass->SetImt(imt, image_pointer_size_);
diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h
index b6b1415b09..e2fd82f83a 100644
--- a/runtime/mirror/class-inl.h
+++ b/runtime/mirror/class-inl.h
@@ -1195,6 +1195,17 @@ inline void Class::SetHasDefaultMethods() {
   SetAccessFlagsDuringLinking(flags | kAccHasDefaultMethod);
 }
 
+inline ImTable* Class::FindSuperImt(PointerSize pointer_size) {
+  ObjPtr<mirror::Class> klass = this;
+  while (klass->HasSuperClass()) {
+    klass = klass->GetSuperClass();
+    if (klass->ShouldHaveImt()) {
+      return klass->GetImt(pointer_size);
+    }
+  }
+  return nullptr;
+}
+
 }  // namespace mirror
 }  // namespace art
 
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index b9eb9d05b4..a515188bc3 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -867,6 +867,8 @@ class MANAGED Class final : public Object {
 
   void SetImt(ImTable* imt, PointerSize pointer_size) REQUIRES_SHARED(Locks::mutator_lock_);
 
+  ImTable* FindSuperImt(PointerSize pointer_size) REQUIRES_SHARED(Locks::mutator_lock_);
+
   ArtMethod* GetEmbeddedVTableEntry(uint32_t i, PointerSize pointer_size)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
diff --git a/test/141-class-unload/src-ex/ConflictImpl.java b/test/141-class-unload/src-ex/ConflictImpl.java
new file mode 100644
index 0000000000..8144c7ebf9
--- /dev/null
+++ b/test/141-class-unload/src-ex/ConflictImpl.java
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class ConflictImpl extends ConflictSuper {
+}
diff --git a/test/141-class-unload/src/ConflictIface.java b/test/141-class-unload/src/ConflictIface.java
new file mode 100644
index 0000000000..033349f7d9
--- /dev/null
+++ b/test/141-class-unload/src/ConflictIface.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public interface ConflictIface {
+  public default Class<?> method1() { return ConflictIface.class; }
+  public default Class<?> method2() { return ConflictIface.class; }
+  public default Class<?> method3() { return ConflictIface.class; }
+  public default Class<?> method4() { return ConflictIface.class; }
+  public default Class<?> method5() { return ConflictIface.class; }
+  public default Class<?> method6() { return ConflictIface.class; }
+  public default Class<?> method7() { return ConflictIface.class; }
+  public default Class<?> method8() { return ConflictIface.class; }
+  public default Class<?> method9() { return ConflictIface.class; }
+  public default Class<?> method10() { return ConflictIface.class; }
+  public default Class<?> method11() { return ConflictIface.class; }
+  public default Class<?> method12() { return ConflictIface.class; }
+  public default Class<?> method13() { return ConflictIface.class; }
+  public default Class<?> method14() { return ConflictIface.class; }
+  public default Class<?> method15() { return ConflictIface.class; }
+  public default Class<?> method16() { return ConflictIface.class; }
+  public default Class<?> method17() { return ConflictIface.class; }
+  public default Class<?> method18() { return ConflictIface.class; }
+  public default Class<?> method19() { return ConflictIface.class; }
+  public default Class<?> method20() { return ConflictIface.class; }
+  public default Class<?> method21() { return ConflictIface.class; }
+  public default Class<?> method22() { return ConflictIface.class; }
+  public default Class<?> method23() { return ConflictIface.class; }
+  public default Class<?> method24() { return ConflictIface.class; }
+  public default Class<?> method25() { return ConflictIface.class; }
+  public default Class<?> method26() { return ConflictIface.class; }
+  public default Class<?> method27() { return ConflictIface.class; }
+  public default Class<?> method28() { return ConflictIface.class; }
+  public default Class<?> method29() { return ConflictIface.class; }
+  public default Class<?> method30() { return ConflictIface.class; }
+  public default Class<?> method31() { return ConflictIface.class; }
+  public default Class<?> method32() { return ConflictIface.class; }
+  public default Class<?> method33() { return ConflictIface.class; }
+  public default Class<?> method34() { return ConflictIface.class; }
+  public default Class<?> method35() { return ConflictIface.class; }
+  public default Class<?> method36() { return ConflictIface.class; }
+  public default Class<?> method37() { return ConflictIface.class; }
+  public default Class<?> method38() { return ConflictIface.class; }
+  public default Class<?> method39() { return ConflictIface.class; }
+  public default Class<?> method40() { return ConflictIface.class; }
+  public default Class<?> method41() { return ConflictIface.class; }
+  public default Class<?> method42() { return ConflictIface.class; }
+  public default Class<?> method43() { return ConflictIface.class; }
+  public default Class<?> method44() { return ConflictIface.class; }
+  public default Class<?> method45() { return ConflictIface.class; }
+  public default Class<?> method46() { return ConflictIface.class; }
+  public default Class<?> method47() { return ConflictIface.class; }
+  public default Class<?> method48() { return ConflictIface.class; }
+  public default Class<?> method49() { return ConflictIface.class; }
+  public default Class<?> method50() { return ConflictIface.class; }
+  public default Class<?> method51() { return ConflictIface.class; }
+  public default Class<?> method52() { return ConflictIface.class; }
+  public default Class<?> method53() { return ConflictIface.class; }
+  public default Class<?> method54() { return ConflictIface.class; }
+  public default Class<?> method55() { return ConflictIface.class; }
+  public default Class<?> method56() { return ConflictIface.class; }
+  public default Class<?> method57() { return ConflictIface.class; }
+  public default Class<?> method58() { return ConflictIface.class; }
+  public default Class<?> method59() { return ConflictIface.class; }
+  public default Class<?> method60() { return ConflictIface.class; }
+  public default Class<?> method61() { return ConflictIface.class; }
+  public default Class<?> method62() { return ConflictIface.class; }
+  public default Class<?> method63() { return ConflictIface.class; }
+  public default Class<?> method64() { return ConflictIface.class; }
+  public default Class<?> method65() { return ConflictIface.class; }
+  public default Class<?> method66() { return ConflictIface.class; }
+  public default Class<?> method67() { return ConflictIface.class; }
+  public default Class<?> method68() { return ConflictIface.class; }
+  public default Class<?> method69() { return ConflictIface.class; }
+  public default Class<?> method70() { return ConflictIface.class; }
+  public default Class<?> method71() { return ConflictIface.class; }
+  public default Class<?> method72() { return ConflictIface.class; }
+  public default Class<?> method73() { return ConflictIface.class; }
+  public default Class<?> method74() { return ConflictIface.class; }
+  public default Class<?> method75() { return ConflictIface.class; }
+  public default Class<?> method76() { return ConflictIface.class; }
+  public default Class<?> method77() { return ConflictIface.class; }
+  public default Class<?> method78() { return ConflictIface.class; }
+  public default Class<?> method79() { return ConflictIface.class; }
+}
diff --git a/test/141-class-unload/src/ConflictSuper.java b/test/141-class-unload/src/ConflictSuper.java
new file mode 100644
index 0000000000..5ca587b2a8
--- /dev/null
+++ b/test/141-class-unload/src/ConflictSuper.java
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class ConflictSuper implements ConflictIface {
+}
diff --git a/test/141-class-unload/src/Main.java b/test/141-class-unload/src/Main.java
index 716f05543c..7b7ffa2ea7 100644
--- a/test/141-class-unload/src/Main.java
+++ b/test/141-class-unload/src/Main.java
@@ -59,6 +59,8 @@ public class Main {
             // Test that code preventing unloading holder classes of copied methods recorded in
             // a stack trace does not crash when processing a copied method in an app image.
             testCopiedAppImageMethodInStackTrace();
+            // Test that the runtime uses the right allocator when creating conflict methods.
+            testConflictMethod(constructor);
         } catch (Exception e) {
             e.printStackTrace(System.out);
         }
@@ -224,6 +226,110 @@ public class Main {
         }
     }
 
+    private static void $noinline$callAllMethods(ConflictIface iface) {
+        // Call all methods in the interface to make sure we hit conflicts in the IMT.
+        iface.method1();
+        iface.method2();
+        iface.method3();
+        iface.method4();
+        iface.method5();
+        iface.method6();
+        iface.method7();
+        iface.method8();
+        iface.method9();
+        iface.method10();
+        iface.method11();
+        iface.method12();
+        iface.method13();
+        iface.method14();
+        iface.method15();
+        iface.method16();
+        iface.method17();
+        iface.method18();
+        iface.method19();
+        iface.method20();
+        iface.method21();
+        iface.method22();
+        iface.method23();
+        iface.method24();
+        iface.method25();
+        iface.method26();
+        iface.method27();
+        iface.method28();
+        iface.method29();
+        iface.method30();
+        iface.method31();
+        iface.method32();
+        iface.method33();
+        iface.method34();
+        iface.method35();
+        iface.method36();
+        iface.method37();
+        iface.method38();
+        iface.method39();
+        iface.method40();
+        iface.method41();
+        iface.method42();
+        iface.method43();
+        iface.method44();
+        iface.method45();
+        iface.method46();
+        iface.method47();
+        iface.method48();
+        iface.method49();
+        iface.method50();
+        iface.method51();
+        iface.method52();
+        iface.method53();
+        iface.method54();
+        iface.method55();
+        iface.method56();
+        iface.method57();
+        iface.method58();
+        iface.method59();
+        iface.method60();
+        iface.method61();
+        iface.method62();
+        iface.method63();
+        iface.method64();
+        iface.method65();
+        iface.method66();
+        iface.method67();
+        iface.method68();
+        iface.method69();
+        iface.method70();
+        iface.method71();
+        iface.method72();
+        iface.method73();
+        iface.method74();
+        iface.method75();
+        iface.method76();
+        iface.method77();
+        iface.method78();
+        iface.method79();
+    }
+
+    private static void $noinline$invokeConflictMethod(Constructor<?> constructor)
+            throws Exception {
+        ClassLoader loader = (ClassLoader) constructor.newInstance(
+                DEX_FILE, LIBRARY_SEARCH_PATH, ClassLoader.getSystemClassLoader());
+        Class<?> impl = loader.loadClass("ConflictImpl");
+        ConflictIface iface = (ConflictIface) impl.newInstance();
+        $noinline$callAllMethods(iface);
+    }
+
+    private static void testConflictMethod(Constructor<?> constructor) throws Exception {
+        // Load and unload a few class loaders to force re-use of the native memory where we
+        // used to allocate the conflict table.
+        for (int i = 0; i < 2; i++) {
+            $noinline$invokeConflictMethod(constructor);
+            doUnloading();
+        }
+        Class<?> impl = Class.forName("ConflictSuper");
+        ConflictIface iface = (ConflictIface) impl.newInstance();
+        $noinline$callAllMethods(iface);
+    }
+
     private static void testCopiedMethodInStackTrace(Constructor<?> constructor) throws Exception {
         Throwable t = $noinline$createStackTraceWithCopiedMethod(constructor);
         doUnloading();