ART: Account for OOME during array merging

When joining class types, in the case of arrays it is possible that
a join type cannot be created (e.g., there's no Java heap to actually
create the class). In that case report an unresolved reference. For
AoT this will lead to re-verification at runtime. At runtime, this
will most likely fail the class.

However, have a special cutout that aborts for AoT on the host, to
protect determinism of preopting.

The decision for an unresolved reference type was made as we do not
want to propagate the underlying exception out of verification. This
would require significant work along all call edges, violating the
current design and invariants of the verifier.

Extend reg_type_test.

Bug: 63822536
Test: m test-art-host-gtest-reg_type_test
Change-Id: I823201e3c401b2c2a46a46fad3327a28e049c181
diff --git a/runtime/verifier/reg_type.cc b/runtime/verifier/reg_type.cc
index 740b7dd..883de38 100644
--- a/runtime/verifier/reg_type.cc
+++ b/runtime/verifier/reg_type.cc
@@ -711,6 +711,29 @@
       DCHECK(c1 != nullptr && !c1->IsPrimitive());
       DCHECK(c2 != nullptr && !c2->IsPrimitive());
       mirror::Class* join_class = ClassJoin(c1, c2);
+      if (UNLIKELY(join_class == nullptr)) {
+        // Internal error joining the classes (e.g., OOME). Report an unresolved reference type.
+        // We cannot report an unresolved merge type, as that will attempt to merge the resolved
+        // components, leaving us in an infinite loop.
+        // We do not want to report the originating exception, as that would require a fast path
+        // out all the way to VerifyClass. Instead attempt to continue on without a detailed type.
+        Thread* self = Thread::Current();
+        self->AssertPendingException();
+        self->ClearException();
+
+        // When compiling on the host, we rather want to abort to ensure determinism for preopting.
+        // (In that case, it is likely a misconfiguration of dex2oat.)
+        if (!kIsTargetBuild && Runtime::Current()->IsAotCompiler()) {
+          LOG(FATAL) << "Could not create class join of "
+                     << c1->PrettyClass()
+                     << " & "
+                     << c2->PrettyClass();
+          UNREACHABLE();
+        }
+
+        return reg_types->MakeUnresolvedReference();
+      }
+
       // Record the dependency that both `c1` and `c2` are assignable to `join_class`.
       // The `verifier` is null during unit tests.
       if (verifier != nullptr) {
@@ -753,10 +776,18 @@
       DCHECK(result->IsObjectClass());
       return result;
     }
+    Thread* self = Thread::Current();
     ObjPtr<mirror::Class> common_elem = ClassJoin(s_ct, t_ct);
+    if (UNLIKELY(common_elem == nullptr)) {
+      self->AssertPendingException();
+      return nullptr;
+    }
     ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-    mirror::Class* array_class = class_linker->FindArrayClass(Thread::Current(), &common_elem);
-    DCHECK(array_class != nullptr);
+    mirror::Class* array_class = class_linker->FindArrayClass(self, &common_elem);
+    if (UNLIKELY(array_class == nullptr)) {
+      self->AssertPendingException();
+      return nullptr;
+    }
     return array_class;
   } else {
     size_t s_depth = s->Depth();
diff --git a/runtime/verifier/reg_type.h b/runtime/verifier/reg_type.h
index 6c01a79..c5d8ff5 100644
--- a/runtime/verifier/reg_type.h
+++ b/runtime/verifier/reg_type.h
@@ -355,6 +355,10 @@
    * the perversion of Object being assignable to an interface type (note, however, that we don't
    * allow assignment of Object or Interface to any concrete class and are therefore type safe).
    *
+   * Note: This may return null in case of internal errors, e.g., OOME when a new class would have
+   *       to be created but there is no heap space. The exception will stay pending, and it is
+   *       the job of the caller to handle it.
+   *
    * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
    */
   static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t)
diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc
index 93286ea..0c00868 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -222,6 +222,11 @@
   }
 }
 
+const RegType& RegTypeCache::MakeUnresolvedReference() {
+  // The descriptor is intentionally invalid so nothing else will match this type.
+  return AddEntry(new (&arena_) UnresolvedReferenceType(AddString("a"), entries_.size()));
+}
+
 const RegType* RegTypeCache::FindClass(mirror::Class* klass, bool precise) const {
   DCHECK(klass != nullptr);
   if (klass->IsPrimitive()) {
diff --git a/runtime/verifier/reg_type_cache.h b/runtime/verifier/reg_type_cache.h
index 37f8a1f..c9bf6a9 100644
--- a/runtime/verifier/reg_type_cache.h
+++ b/runtime/verifier/reg_type_cache.h
@@ -97,6 +97,10 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
   const RegType& FromUnresolvedSuperClass(const RegType& child)
       REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Note: this should not be used outside of RegType::ClassJoin!
+  const RegType& MakeUnresolvedReference() REQUIRES_SHARED(Locks::mutator_lock_);
+
   const ConstantType& Zero() REQUIRES_SHARED(Locks::mutator_lock_) {
     return FromCat1Const(0, true);
   }
diff --git a/runtime/verifier/reg_type_test.cc b/runtime/verifier/reg_type_test.cc
index b0ea6c8..64d906e 100644
--- a/runtime/verifier/reg_type_test.cc
+++ b/runtime/verifier/reg_type_test.cc
@@ -22,6 +22,7 @@
 #include "base/casts.h"
 #include "base/scoped_arena_allocator.h"
 #include "common_runtime_test.h"
+#include "compiler_callbacks.h"
 #include "reg_type_cache-inl.h"
 #include "reg_type-inl.h"
 #include "scoped_thread_state_change-inl.h"
@@ -677,5 +678,109 @@
   EXPECT_FALSE(imprecise_const.Equals(precise_const));
 }
 
+class RegTypeOOMTest : public RegTypeTest {
+ protected:
+  void SetUpRuntimeOptions(RuntimeOptions *options) OVERRIDE {
+    // Use a smaller heap
+    for (std::pair<std::string, const void*>& pair : *options) {
+      if (pair.first.find("-Xmx") == 0) {
+        pair.first = "-Xmx4M";  // Smallest we can go.
+      }
+    }
+    options->push_back(std::make_pair("-Xint", nullptr));
+
+    // We must not appear to be a compiler, or we'll abort on the host.
+    callbacks_.reset();
+  }
+
+  static const size_t kMaxHandles = 1000000;  // Use arbitrary large amount for now.
+  static void FillHeap(Thread* self,
+                       ClassLinker* class_linker,
+                       std::unique_ptr<StackHandleScope<kMaxHandles>>* hsp,
+                       std::vector<MutableHandle<mirror::Object>>* handles)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    Runtime::Current()->GetHeap()->SetIdealFootprint(1 * GB);
+
+    hsp->reset(new StackHandleScope<kMaxHandles>(self));
+    // Class java.lang.Object.
+    Handle<mirror::Class> c((*hsp)->NewHandle(
+        class_linker->FindSystemClass(self, "Ljava/lang/Object;")));
+    // Array helps to fill memory faster.
+    Handle<mirror::Class> ca((*hsp)->NewHandle(
+        class_linker->FindSystemClass(self, "[Ljava/lang/Object;")));
+
+    // Start allocating with 128K
+    size_t length = 128 * KB / 4;
+    while (length > 10) {
+      MutableHandle<mirror::Object> h((*hsp)->NewHandle<mirror::Object>(
+          mirror::ObjectArray<mirror::Object>::Alloc(self, ca.Get(), length / 4)));
+      if (self->IsExceptionPending() || h == nullptr) {
+        self->ClearException();
+
+        // Try a smaller length
+        length = length / 8;
+        // Use at most half the reported free space.
+        size_t mem = Runtime::Current()->GetHeap()->GetFreeMemory();
+        if (length * 8 > mem) {
+          length = mem / 8;
+        }
+      } else {
+        handles->push_back(h);
+      }
+    }
+
+    // Allocate simple objects till it fails.
+    while (!self->IsExceptionPending()) {
+      MutableHandle<mirror::Object> h = (*hsp)->NewHandle<mirror::Object>(c->AllocObject(self));
+      if (!self->IsExceptionPending() && h != nullptr) {
+        handles->push_back(h);
+      }
+    }
+    self->ClearException();
+  }
+};
+
+TEST_F(RegTypeOOMTest, ClassJoinOOM) {
+  // Tests that we don't abort with OOMs.
+
+  ArenaStack stack(Runtime::Current()->GetArenaPool());
+  ScopedArenaAllocator allocator(&stack);
+  ScopedObjectAccess soa(Thread::Current());
+
+  // We cannot allow moving GC. Otherwise we'd have to ensure the reg types are updated (reference
+  // reg types store a class pointer in a GCRoot, which is normally updated through active verifiers
+  // being registered with their thread), which is unnecessarily complex.
+  Runtime::Current()->GetHeap()->IncrementDisableMovingGC(soa.Self());
+
+  // We merge nested array of primitive wrappers. These have a join type of an array of Number of
+  // the same depth. We start with depth five, as we want at least two newly created classes to
+  // test recursion (it's just more likely that nobody uses such deep arrays in runtime bringup).
+  constexpr const char* kIntArrayFive = "[[[[[Ljava/lang/Integer;";
+  constexpr const char* kFloatArrayFive = "[[[[[Ljava/lang/Float;";
+  constexpr const char* kNumberArrayFour = "[[[[Ljava/lang/Number;";
+  constexpr const char* kNumberArrayFive = "[[[[[Ljava/lang/Number;";
+
+  RegTypeCache cache(true, allocator);
+  const RegType& int_array_array = cache.From(nullptr, kIntArrayFive, false);
+  ASSERT_TRUE(int_array_array.HasClass());
+  const RegType& float_array_array = cache.From(nullptr, kFloatArrayFive, false);
+  ASSERT_TRUE(float_array_array.HasClass());
+
+  // Check assumptions: the joined classes don't exist, yet.
+  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
+  ASSERT_TRUE(class_linker->LookupClass(soa.Self(), kNumberArrayFour, nullptr) == nullptr);
+  ASSERT_TRUE(class_linker->LookupClass(soa.Self(), kNumberArrayFive, nullptr) == nullptr);
+
+  // Fill the heap.
+  std::unique_ptr<StackHandleScope<kMaxHandles>> hsp;
+  std::vector<MutableHandle<mirror::Object>> handles;
+  FillHeap(soa.Self(), class_linker, &hsp, &handles);
+
+  const RegType& join_type = int_array_array.Merge(float_array_array, &cache, nullptr);
+  ASSERT_TRUE(join_type.IsUnresolvedReference());
+
+  Runtime::Current()->GetHeap()->DecrementDisableMovingGC(soa.Self());
+}
+
 }  // namespace verifier
 }  // namespace art