Revert "Adjust how we assign vtable indexes during class loading."

This reverts commit 868e576d4f67026bb7109286f922cb26e0e84145.

Bug: 211854716
Bug: 233545487

Reason for revert: Some inaccuracies in the comments.

Change-Id: Iddfe66c7748ef2f617d06d5dbcb8787a18e22125
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index a598d27..c8dbc75 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -37,7 +37,6 @@
 #include "art_method-inl.h"
 #include "barrier.h"
 #include "base/arena_allocator.h"
-#include "base/arena_bit_vector.h"
 #include "base/casts.h"
 #include "base/file_utils.h"
 #include "base/hash_map.h"
@@ -7977,7 +7976,40 @@
       super_vtable_buffer_ptr,
       super_vtable_buffer_size,
       allocator_.Adapter());
+  ArrayRef<uint32_t> same_signature_vtable_lists;
+  // Insert the first `mirror::Object::kVTableLength` indexes with pre-calculated hashes.
+  DCHECK_GE(super_vtable_length, mirror::Object::kVTableLength);
+  for (uint32_t i = 0; i != mirror::Object::kVTableLength; ++i) {
+    size_t hash = class_linker_->object_virtual_method_hashes_[i];
+    // There are no duplicate signatures in `java.lang.Object`, so use `HashSet<>::PutWithHash()`.
+    // This avoids equality comparison for the three `java.lang.Object.wait()` overloads.
+    super_vtable_signatures.PutWithHash(i, hash);
+  }
+  // Insert the remaining indexes, check for duplicate signatures.
+  if (super_vtable_length > mirror::Object::kVTableLength) {
+    for (size_t i = mirror::Object::kVTableLength; i < super_vtable_length; ++i) {
+      // Use `super_vtable_accessor` for getting the method for hash calculation.
+      // Letting `HashSet<>::insert()` use the internal accessor copy in the hash
+      // function prevents the compiler from optimizing this properly because the
+      // compiler cannot prove that the accessor copy is immutable.
+      size_t hash = ComputeMethodHash(super_vtable_accessor.GetVTableEntry(i));
+      auto [it, inserted] = super_vtable_signatures.InsertWithHash(i, hash);
+      if (UNLIKELY(!inserted)) {
+        if (same_signature_vtable_lists.empty()) {
+          same_signature_vtable_lists = ArrayRef<uint32_t>(
+              allocator_.AllocArray<uint32_t>(super_vtable_length), super_vtable_length);
+          std::fill_n(same_signature_vtable_lists.data(), super_vtable_length, dex::kDexNoIndex);
+          same_signature_vtable_lists_ = same_signature_vtable_lists;
+        }
+        DCHECK_LT(*it, i);
+        same_signature_vtable_lists[i] = *it;
+        *it = i;
+      }
+    }
+  }
 
+  // For each declared virtual method, look for a superclass virtual method
+  // to override and assign a new vtable index if no method was overridden.
   DeclaredVirtualSignatureSet declared_virtual_signatures(
       kMinLoadFactor,
       kMaxLoadFactor,
@@ -7986,22 +8018,8 @@
       declared_virtuals_buffer_ptr,
       declared_virtuals_buffer_size,
       allocator_.Adapter());
-
-  ArrayRef<uint32_t> same_signature_vtable_lists;
   const bool is_proxy_class = klass->IsProxyClass();
   size_t vtable_length = super_vtable_length;
-
-  // Record which declared methods are overriding a super method.
-  ArenaBitVector initialized_methods(&allocator_, num_virtual_methods, /* expandable= */ false);
-
-  // Note: our sets hash on the method name, and therefore we pay a high
-  // performance price when a class has many overloads.
-  //
-  // We populate the declared_virtual_signatures instead of the
-  // super_vtable_signatures (which is only lazy populated in case of interface
-  // overriding, see below). This makes sure that we pay the performance price
-  // only on that class, and not on its subclasses (except in the case of
-  // interface overriding, see below).
   for (size_t i = 0; i != num_virtual_methods; ++i) {
     ArtMethod* virtual_method = klass->GetVirtualMethodDuringLinking(i, kPointerSize);
     DCHECK(!virtual_method->IsStatic()) << virtual_method->PrettyMethod();
@@ -8010,65 +8028,57 @@
         : virtual_method;
     size_t hash = ComputeMethodHash(signature_method);
     declared_virtual_signatures.PutWithHash(i, hash);
-  }
-
-  // Loop through each super vtable method and see if they are overridden by a method we added to
-  // the hash table.
-  for (size_t j = 0; j < super_vtable_length; ++j) {
-    // Search the hash table to see if we are overridden by any method.
-    ArtMethod* super_method = super_vtable_accessor.GetVTableEntry(j);
-    if (!klass->CanAccessMember(super_method->GetDeclaringClass(),
-                                super_method->GetAccessFlags())) {
-      // Continue on to the next method since this one is package private and cannot be overridden.
-      // Before Android 4.1, the package-private method super_method might have been incorrectly
-      // overridden.
-      continue;
-    }
-    size_t hash = (j < mirror::Object::kVTableLength)
-        ? class_linker_->object_virtual_method_hashes_[j]
-        : ComputeMethodHash(super_method);
-    auto it = declared_virtual_signatures.FindWithHash(super_method, hash);
-    if (it == declared_virtual_signatures.end()) {
-      continue;
-    }
-    ArtMethod* virtual_method = klass->GetVirtualMethodDuringLinking(*it, kPointerSize);
-    if (super_method->IsFinal()) {
-      sants.reset();
-      ThrowLinkageError(klass, "Method %s overrides final method in class %s",
-                        virtual_method->PrettyMethod().c_str(),
-                        super_method->GetDeclaringClassDescriptor());
-      return 0u;
-    }
-    if (initialized_methods.IsBitSet(*it)) {
-      // The method is overriding two methods: one public, and one package private.
-      // We record that information to later set the method in the vtable
-      // location that isn't the method index.
-      if (same_signature_vtable_lists.empty()) {
-        same_signature_vtable_lists = ArrayRef<uint32_t>(
-            allocator_.AllocArray<uint32_t>(super_vtable_length), super_vtable_length);
-        std::fill_n(same_signature_vtable_lists.data(), super_vtable_length, dex::kDexNoIndex);
-        same_signature_vtable_lists_ = same_signature_vtable_lists;
+    auto it = super_vtable_signatures.FindWithHash(signature_method, hash);
+    if (it != super_vtable_signatures.end()) {
+      size_t super_index = *it;
+      DCHECK_LT(super_index, super_vtable_length);
+      ArtMethod* super_method = super_vtable_accessor.GetVTableEntry(super_index);
+      // Historical note: Before Android 4.1, an inaccessible package-private
+      // superclass method would have been incorrectly overridden.
+      bool overrides = klass->CanAccessMember(super_method->GetDeclaringClass(),
+                                              super_method->GetAccessFlags());
+      if (overrides && super_method->IsFinal()) {
+        sants.reset();
+        ThrowLinkageError(klass, "Method %s overrides final method in class %s",
+                          virtual_method->PrettyMethod().c_str(),
+                          super_method->GetDeclaringClassDescriptor());
+        return 0u;
       }
-      same_signature_vtable_lists[j] = virtual_method->GetMethodIndexDuringLinking();
-    } else {
-      initialized_methods.SetBit(*it);
+      if (UNLIKELY(!same_signature_vtable_lists.empty())) {
+        // We may override more than one method according to JLS, see b/211854716 .
+        // We record the highest overridden vtable index here so that we can walk
+        // the list to find other overridden methods when constructing the vtable.
+        // However, we walk all the methods to check for final method overriding.
+        size_t current_index = super_index;
+        while (same_signature_vtable_lists[current_index] != dex::kDexNoIndex) {
+          DCHECK_LT(same_signature_vtable_lists[current_index], current_index);
+          current_index = same_signature_vtable_lists[current_index];
+          ArtMethod* current_method = super_vtable_accessor.GetVTableEntry(current_index);
+          if (klass->CanAccessMember(current_method->GetDeclaringClass(),
+                                     current_method->GetAccessFlags())) {
+            if (current_method->IsFinal()) {
+              sants.reset();
+              ThrowLinkageError(klass, "Method %s overrides final method in class %s",
+                                virtual_method->PrettyMethod().c_str(),
+                                current_method->GetDeclaringClassDescriptor());
+              return 0u;
+            }
+            if (!overrides) {
+              overrides = true;
+              super_index = current_index;
+              super_method = current_method;
+            }
+          }
+        }
+      }
+      if (overrides) {
+        virtual_method->SetMethodIndex(super_index);
+        continue;
+      }
     }
-    // Make sure the vtable index of the method is the vtable index of the overridden
-    // method that is public. We know that index is the largest one, a we can
-    // only start with a package private in the superclass hierarchy, and then have a new
-    // index in a closer superclass.
-    // This makes sure we find the public version when looking for interface
-    // (see code below).
-    virtual_method->SetMethodIndex(j);
-  }
-
-  // Add the non-overridden methods at the end.
-  for (size_t i = 0; i < num_virtual_methods; ++i) {
-    if (!initialized_methods.IsBitSet(i)) {
-      ArtMethod* local_method = klass->GetVirtualMethodDuringLinking(i, kPointerSize);
-      local_method->SetMethodIndex(vtable_length);
-      vtable_length++;
-    }
+    // The method does not override any method from superclass, so it needs a new vtable index.
+    virtual_method->SetMethodIndex(vtable_length);
+    ++vtable_length;
   }
 
   // Assign vtable indexes for interface methods in new interfaces and store them
@@ -8095,34 +8105,24 @@
         vtable_method = klass->GetVirtualMethodDuringLinking(*it1, kPointerSize);
         found = true;
       } else {
-        // This situation should be rare (a superclass implements a method
-        // declared in an interface this class is inheriting). Only in this case
-        // do we lazily populate the super_vtable_signatures.
-        if (super_vtable_signatures.empty()) {
-          for (size_t k = 0; k < super_vtable_length; ++k) {
-            ArtMethod* super_method = super_vtable_accessor.GetVTableEntry(k);
-            if (!klass->CanAccessMember(super_method->GetDeclaringClass(),
-                                        super_method->GetAccessFlags())) {
-                continue;
-            }
-            size_t super_hash = (k < mirror::Object::kVTableLength)
-                ? class_linker_->object_virtual_method_hashes_[k]
-                : ComputeMethodHash(super_method);
-            auto [it, inserted] = super_vtable_signatures.InsertWithHash(k, super_hash);
-            if (UNLIKELY(!inserted)) {
-              // If there is an existing method with the same name and
-              // signature, this means we have a package-private version and a
-              // public version. When setting up vtable indexes, we make sure
-              // the public version has the highest index, and therefore we only
-              // record the public version here. This makes sure we don't get
-              // the package-private version in the lookup below.
-              *it = k;
-            }
-          }
-        }
         auto it2 = super_vtable_signatures.FindWithHash(interface_method, hash);
         if (it2 != super_vtable_signatures.end()) {
+          // If there are multiple vtable methods with the same signature, the one with
+          // the highest vtable index is not nessarily the one in most-derived class.
+          // Find the most-derived method. See b/211854716 .
           vtable_method = super_vtable_accessor.GetVTableEntry(*it2);
+          if (UNLIKELY(!same_signature_vtable_lists.empty())) {
+            size_t current_index = *it2;
+            while (same_signature_vtable_lists[current_index] != dex::kDexNoIndex) {
+              DCHECK_LT(same_signature_vtable_lists[current_index], current_index);
+              current_index = same_signature_vtable_lists[current_index];
+              ArtMethod* current_method = super_vtable_accessor.GetVTableEntry(current_index);
+              ObjPtr<mirror::Class> current_class = current_method->GetDeclaringClass();
+              if (current_class->IsSubClass(vtable_method->GetDeclaringClass())) {
+                vtable_method = current_method;
+              }
+            }
+          }
           found = true;
         }
       }
@@ -8484,15 +8484,8 @@
       uint32_t vtable_index = virtual_method.GetMethodIndexDuringLinking();
       vtable->SetElementPtrSize(vtable_index, &virtual_method, kPointerSize);
       if (UNLIKELY(vtable_index < same_signature_vtable_lists.size())) {
-        // We may override more than one method according to JLS, see b/211854716.
-        // We really only expect one or two methods overridden, not more: one for
-        // package-private visibility, and one for public visibility.
-        // In AssignVTableIndexes, we make sure the vtable index of a method that
-        // overrides two methods is the same vtable index as the public one.
-        // This makes sure we find the public version when looking for interface
-        // method overriding.
-        // FIXME: Change this while loop into code that only expects two
-        // entries.
+        // We may override more than one method according to JLS, see b/211854716 .
+        // If we do, arbitrarily update the method index to the lowest overridden vtable index.
         while (same_signature_vtable_lists[vtable_index] != dex::kDexNoIndex) {
           DCHECK_LT(same_signature_vtable_lists[vtable_index], vtable_index);
           vtable_index = same_signature_vtable_lists[vtable_index];
@@ -8501,6 +8494,7 @@
                                      current_method->GetAccessFlags())) {
             DCHECK(!current_method->IsFinal());
             vtable->SetElementPtrSize(vtable_index, &virtual_method, kPointerSize);
+            virtual_method.SetMethodIndex(vtable_index);
           }
         }
       }
diff --git a/runtime/mirror/array-inl.h b/runtime/mirror/array-inl.h
index b7a8a8c..b0e77b4 100644
--- a/runtime/mirror/array-inl.h
+++ b/runtime/mirror/array-inl.h
@@ -98,7 +98,7 @@
   if (kTransactionActive) {
     Runtime::Current()->RecordWriteArray(this, i, GetWithoutChecks(i));
   }
-  DCHECK(CheckIsValidIndex<kVerifyFlags>(i)) << i << " " << GetLength<kVerifyFlags>();
+  DCHECK(CheckIsValidIndex<kVerifyFlags>(i));
   GetData()[i] = value;
 }
 // Backward copy where elements are of aligned appropriately for T. Count is in T sized units.