runtime: Bitstring implementation for subtype checking (4/4).
Integrate the previous CLs into ART Runtime. Subsequent CLs to add
optimizing compiler support.
Use spare 24-bits from "Class#status_" field to
implement faster subtype checking in the runtime. Does not incur any extra memory overhead,
and (when in compiled code) this is always as fast or faster than the original check.
The new subtype checking is O(1) of the form:
src <: target :=
(*src).status >> #imm_target_mask == #imm_target_shifted
Based on the original prototype CL by Zhengkai Wu:
https://android-review.googlesource.com/#/c/platform/art/+/440996/
Test: art/test.py -b -j32 --host
Bug: 64692057
Change-Id: Iec3c54af529055a7f6147eebe5611d9ecd46942b
diff --git a/runtime/base/bit_string.h b/runtime/base/bit_string.h
index d4197e3..1cda021 100644
--- a/runtime/base/bit_string.h
+++ b/runtime/base/bit_string.h
@@ -246,6 +246,11 @@
return !(*this == other);
}
+ // Does this bitstring contain exactly 0 characters?
+ bool IsEmpty() const {
+ return (*this) == BitString{}; // NOLINT
+ }
+
// Remove all BitStringChars starting at end.
// Returns the BitString[0..end) substring as a copy.
// See also "BitString[I..N)" in the doc header.
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index d3eb29b..ba5fe04 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -453,6 +453,19 @@
java_lang_Object->GetObjectSize(),
VoidFunctor()));
+ // Initialize the SubtypeCheck bitstring for java.lang.Object and java.lang.Class.
+ {
+ // It might seem the lock here is unnecessary, however all the SubtypeCheck
+ // functions are annotated to require locks all the way down.
+ //
+ // We take the lock here to avoid using NO_THREAD_SAFETY_ANALYSIS.
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ mirror::Class* java_lang_Object_ptr = java_lang_Object.Get();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(java_lang_Object_ptr);
+ mirror::Class* java_lang_Class_ptr = java_lang_Class.Get();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(java_lang_Class_ptr);
+ }
+
// Object[] next to hold class roots.
Handle<mirror::Class> object_array_class(hs.NewHandle(
AllocClass(self, java_lang_Class.Get(),
@@ -1806,11 +1819,32 @@
for (const ClassTable::TableSlot& root : temp_set) {
visitor(root.Read());
}
+
+ {
+ // Every class in the app image has initially SubtypeCheckInfo in the
+ // Uninitialized state.
+ //
+ // The SubtypeCheck invariants imply that a SubtypeCheckInfo is at least Initialized
+ // after class initialization is complete. The app image ClassStatus as-is
+ // are almost all ClassStatus::Initialized, and being in the
+ // SubtypeCheckInfo::kUninitialized state is violating that invariant.
+ //
+ // Force every app image class's SubtypeCheck to be at least kIninitialized.
+ //
+ // See also ImageWriter::FixupClass.
+ ScopedTrace trace("Recalculate app image SubtypeCheck bitstrings");
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ for (const ClassTable::TableSlot& root : temp_set) {
+ mirror::Class* root_klass = root.Read();
+ SubtypeCheck<mirror::Class*>::EnsureInitialized(root_klass);
+ }
+ }
}
if (!oat_file->GetBssGcRoots().empty()) {
// Insert oat file to class table for visiting .bss GC roots.
class_table->InsertOatFile(oat_file);
}
+
if (added_class_table) {
WriterMutexLock mu(self, *Locks::classlinker_classes_lock_);
class_table->AddClassSet(std::move(temp_set));
@@ -5122,11 +5156,28 @@
bool can_init_fields,
bool can_init_parents) {
DCHECK(c != nullptr);
+
if (c->IsInitialized()) {
EnsureSkipAccessChecksMethods(c, image_pointer_size_);
self->AssertNoPendingException();
return true;
}
+ // SubtypeCheckInfo::Initialized must happen-before any new-instance for that type.
+ //
+ // Ensure the bitstring is initialized before any of the class initialization
+ // logic occurs. Once a class initializer starts running, objects can
+ // escape into the heap and use the subtype checking code.
+ //
+ // Note: A class whose SubtypeCheckInfo is at least Initialized means it
+ // can be used as a source for the IsSubClass check, and that all ancestors
+ // of the class are Assigned (can be used as a target for IsSubClass check)
+ // or Overflowed (can be used as a source for IsSubClass check).
+ {
+ MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
+ ObjPtr<mirror::Class> c_ptr(c.Get());
+ SubtypeCheck<ObjPtr<mirror::Class>>::EnsureInitialized(c_ptr);
+ // TODO: Avoid taking subtype_check_lock_ if SubtypeCheck is already initialized.
+ }
const bool success = InitializeClass(self, c, can_init_fields, can_init_parents);
if (!success) {
if (can_init_fields && can_init_parents) {
diff --git a/runtime/class_status.h b/runtime/class_status.h
index 0877e68..7f2ef6a 100644
--- a/runtime/class_status.h
+++ b/runtime/class_status.h
@@ -18,6 +18,7 @@
#define ART_RUNTIME_CLASS_STATUS_H_
#include <iosfwd>
+#include <stdint.h>
namespace art {
@@ -70,7 +71,7 @@
// again at runtime.
//
// TODO: Explain the other states
-enum ClassStatus {
+enum ClassStatus : int8_t {
kStatusRetired = -3, // Retired, should not be used. Use the newly cloned one instead.
kStatusErrorResolved = -2,
kStatusErrorUnresolved = -1,
diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h
index 78f6b25..eb54f7f 100644
--- a/runtime/mirror/class-inl.h
+++ b/runtime/mirror/class-inl.h
@@ -31,6 +31,7 @@
#include "gc/heap-inl.h"
#include "iftable.h"
#include "invoke_type.h"
+#include "subtype_check.h"
#include "object-inl.h"
#include "object_array.h"
#include "read_barrier-inl.h"
@@ -56,7 +57,6 @@
return GetField32(ObjectSizeAllocFastPathOffset());
}
-
template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
inline Class* Class::GetSuperClass() {
// Can only get super class for loaded classes (hack for when runtime is
@@ -532,16 +532,46 @@
}
inline bool Class::IsSubClass(ObjPtr<Class> klass) {
+ // Since the SubtypeCheck::IsSubtypeOf needs to lookup the Depth,
+ // it is always O(Depth) in terms of speed to do the check.
+ //
+ // So always do the "slow" linear scan in normal release builds.
+ //
+ // Future note: If we could have the depth in O(1) we could use the 'fast'
+ // method instead as it avoids a loop and a read barrier.
+ bool result = false;
DCHECK(!IsInterface()) << PrettyClass();
DCHECK(!IsArrayClass()) << PrettyClass();
ObjPtr<Class> current = this;
do {
if (current == klass) {
- return true;
+ result = true;
+ break;
}
current = current->GetSuperClass();
} while (current != nullptr);
- return false;
+
+ if (kIsDebugBuild) {
+ ObjPtr<mirror::Class> dis(this);
+
+ SubtypeCheckInfo::Result sc_result = SubtypeCheck<ObjPtr<Class>>::IsSubtypeOf(dis, klass);
+ if (sc_result != SubtypeCheckInfo::kUnknownSubtypeOf) {
+ // Note: The "kUnknownSubTypeOf" can be avoided if and only if:
+ // SubtypeCheck::EnsureInitialized(source)
+ // happens-before source.IsSubClass(target)
+ // SubtypeCheck::EnsureAssigned(target).GetState() == Assigned
+ // happens-before source.IsSubClass(target)
+ //
+ // When code generated by optimizing compiler executes this operation, both
+ // happens-before are guaranteed, so there is no fallback code there.
+ SubtypeCheckInfo::Result expected_result =
+ result ? SubtypeCheckInfo::kSubtypeOf : SubtypeCheckInfo::kNotSubtypeOf;
+ DCHECK_EQ(expected_result, sc_result)
+ << "source: " << PrettyClass() << "target: " << klass->PrettyClass();
+ }
+ }
+
+ return result;
}
inline ArtMethod* Class::FindVirtualMethodForInterface(ArtMethod* method,
diff --git a/runtime/mirror/class.cc b/runtime/mirror/class.cc
index 40157c4..4d810db 100644
--- a/runtime/mirror/class.cc
+++ b/runtime/mirror/class.cc
@@ -29,6 +29,7 @@
#include "dex_file_annotations.h"
#include "gc/accounting/card_table-inl.h"
#include "handle_scope-inl.h"
+#include "subtype_check.h"
#include "method.h"
#include "object-inl.h"
#include "object-refvisitor-inl.h"
@@ -41,6 +42,11 @@
#include "well_known_classes.h"
namespace art {
+
+// TODO: move to own CC file?
+constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
+constexpr size_t BitString::kCapacity;
+
namespace mirror {
using android::base::StringPrintf;
@@ -166,11 +172,9 @@
self->AssertPendingException();
}
- static_assert(sizeof(Status) == sizeof(uint32_t), "Size of status not equal to uint32");
- if (Runtime::Current()->IsActiveTransaction()) {
- h_this->SetField32Volatile<true>(StatusOffset(), new_status);
- } else {
- h_this->SetField32Volatile<false>(StatusOffset(), new_status);
+ {
+ ObjPtr<mirror::Class> h_this_ptr = h_this.Get();
+ SubtypeCheck<ObjPtr<mirror::Class>>::WriteStatus(h_this_ptr, new_status);
}
// Setting the object size alloc fast path needs to be after the status write so that if the
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index 148273b..bf49f51 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -101,9 +101,10 @@
template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags>
Status GetStatus() REQUIRES_SHARED(Locks::mutator_lock_) {
- static_assert(sizeof(Status) == sizeof(uint32_t), "Size of status not equal to uint32");
- return static_cast<Status>(
- GetField32Volatile<kVerifyFlags>(OFFSET_OF_OBJECT_MEMBER(Class, status_)));
+ // Avoid including "subtype_check_bits_and_status.h" to get the field.
+ // The ClassStatus is always in the least-significant bits of status_.
+ return static_cast<Status>(static_cast<uint8_t>(
+ static_cast<uint32_t>(GetField32Volatile<kVerifyFlags>(StatusOffset())) & 0xff));
}
// This is static because 'this' may be moved by GC.
@@ -111,7 +112,7 @@
REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_);
static MemberOffset StatusOffset() {
- return OFFSET_OF_OBJECT_MEMBER(Class, status_);
+ return MemberOffset(OFFSET_OF_OBJECT_MEMBER(Class, status_));
}
// Returns true if the class has been retired.
@@ -1481,8 +1482,9 @@
// Bitmap of offsets of ifields.
uint32_t reference_instance_offsets_;
- // State of class initialization.
- Status status_;
+ // See the real definition in subtype_check_bits_and_status.h
+ // typeof(status_) is actually SubtypeCheckBitsAndStatus.
+ uint32_t status_;
// The offset of the first virtual method that is copied from an interface. This includes miranda,
// default, and default-conflict methods. Having a hard limit of ((2 << 16) - 1) for methods
diff --git a/runtime/subtype_check_info.h b/runtime/subtype_check_info.h
index f60e0ac..d10d472 100644
--- a/runtime/subtype_check_info.h
+++ b/runtime/subtype_check_info.h
@@ -260,7 +260,7 @@
// Get the current state (Uninitialized, Initialized, Assigned, or Overflowed).
// See the "SubtypeCheckInfo" documentation above which explains how a state is determined.
State GetState() const {
- if (GetBitString() == BitString{}) { // NOLINT
+ if (GetBitString().IsEmpty()) {
// Empty bitstring (all 0s) -> uninitialized.
DCHECK(!bitstring_and_of_.overflow_);
return kUninitialized;
@@ -274,7 +274,7 @@
// Either Assigned or Initialized.
BitString path_to_root = GetPathToRoot();
- DCHECK(!HasNext() || GetNext() != BitStringChar{}) // NOLINT
+ DCHECK(!HasNext() || GetNext() != 0u)
<< "Expected (Assigned|Initialized) state to have >0 Next value: "
<< GetNext() << " path: " << path_to_root;
@@ -347,7 +347,7 @@
bool did_overlap = false;
if (HasNext()) {
if (kIsDebugBuild) {
- did_overlap = (GetNext() != BitStringChar{}); // NOLINT
+ did_overlap = (GetNext() != 0u);
}
SetNext(next);