runtime: Bitstring implementation for subtype checking (3/4).
Implement the subtype check manipulation of the class hierarchy.
This walks the class hierarchy tree and allocates bitstring values
to each class by encoding the path from the class to the root as a
bitstring.
Used to implement O(1) subtype checking in the subsequent CL.
Test: art/test.py -b -j32 --host --target
Bug: 64692057
Change-Id: I484940bbb3901b56236245cdd4f8f4a8d859f919
diff --git a/runtime/subtype_check.h b/runtime/subtype_check.h
new file mode 100644
index 0000000..24f0763
--- /dev/null
+++ b/runtime/subtype_check.h
@@ -0,0 +1,573 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#ifndef ART_RUNTIME_SUBTYPE_CHECK_H_
+#define ART_RUNTIME_SUBTYPE_CHECK_H_
+
+#include "subtype_check_bits_and_status.h"
+#include "subtype_check_info.h"
+
+#include "base/mutex.h"
+#include "mirror/class.h"
+#include "runtime.h"
+
+/**
+ * Any node in a tree can have its path (from the root to the node) represented as a string by
+ * concatenating the path of the parent to that of the current node.
+ *
+ * We can annotate each node with a `sibling-label` which is some value unique amongst all of the
+ * node's siblings. As a special case, the root is empty.
+ *
+ * (none)
+ * / | \
+ * A B C
+ * / \
+ * A’ B’
+ * |
+ * A’’
+ * |
+ * A’’’
+ * |
+ * A’’’’
+ *
+ * Given these sibling-labels, we can now encode the path from any node to the root by starting at
+ * the node and going up to the root, marking each node with this `path-label`. The special
+ * character $ means "end of path".
+ *
+ * $
+ * / | \
+ * A$ B$ C$
+ * / \
+ * A’A$ B’A$
+ * |
+ * A’’B’A$
+ * |
+ * A’’’A’’B’A$
+ * |
+ * A’’’’A’’B’A$
+ *
+ * Given the above `path-label` we can express if any two nodes are an offspring of the other
+ * through a O(1) expression:
+ *
+ * x <: y :=
+ * suffix(x, y) == y
+ *
+ * In the above example suffix(x,y) means the suffix of x that is as long as y (right-padded with
+ * $s if x is shorter than y) :
+ *
+ * suffix(x,y) := x(x.length - y.length .. 0]
+ * + repeat($, max(y.length - x.length, 0))
+ *
+ * A few generalities here to elaborate:
+ *
+ * - There can be at most D levels in the tree.
+ * - Each level L has an alphabet A, and the maximum number of
+ * nodes is determined by |A|
+ * - The alphabet A can be a subset, superset, equal, or unique with respect to the other alphabets
+ * without loss of generality. (In practice it would almost always be a subset of the previous
+ * level’s alphabet as we assume most classes have less children the deeper they are.)
+ * - The `sibling-label` doesn’t need to be stored as an explicit value. It can a temporary when
+ * visiting every immediate child of a node. Only the `path-label` needs to be actually stored for
+ * every node.
+ *
+ * The path can also be reversed, and use a prefix instead of a suffix to define the subchild
+ * relation.
+ *
+ * $
+ * / | \ \
+ * A$ B$ C$ D$
+ * / \
+ * AA’$ AB’$
+ * |
+ * AB’A’’$
+ * |
+ * AB’A’’A’’’$
+ * |
+ * AB’A’’A’’’A’’’’$
+ *
+ * x <: y :=
+ * prefix(x, y) == y
+ *
+ * prefix(x,y) := x[0 .. y.length)
+ * + repeat($, max(y.length - x.length, 0))
+ *
+ * In a dynamic tree, new nodes can be inserted at any time. This means if a minimal alphabet is
+ * selected to contain the initial tree hierarchy, later node insertions will be illegal because
+ * there is no more room to encode the path.
+ *
+ * In this simple example with an alphabet A,B,C and max level 1:
+ *
+ * Level
+ * 0: $
+ * / | \ \
+ * 1: A$ B$ C$ D$ (illegal)
+ * |
+ * 2: AA$ (illegal)
+ *
+ * Attempting to insert the sibling “D” at Level 1 would be illegal because the Alphabet(1) is
+ * {A,B,C} and inserting an extra node would mean the `sibling-label` is no longer unique.
+ * Attempting to insert “AA$” is illegal because the level 2 is more than the max level 1.
+ *
+ * One solution to this would be to revisit the entire graph, select a larger alphabet to that
+ * every `sibling-label` is unique, pick a larger max level count, and then store the updated
+ * `path-label` accordingly.
+ *
+ * The more common approach would instead be to select a set of alphabets and max levels statically,
+ * with large enough sizes, for example:
+ *
+ * Alphabets = {{A,B,C,D}, {A,B,C}, {A,B}, {A}}
+ * Max Levels = |Alphabets|
+ *
+ * Which would allow up to 4 levels with each successive level having 1 less max siblings.
+ *
+ * Attempting to insert a new node into the graph which does not fit into that level’s alphabet
+ * would be represented by re-using the `path-label` of the parent. Such a `path_label` would be
+ * considered truncated (because it would only have a prefix of the full path from the root to the
+ * node).
+ *
+ * Level
+ * 0: $
+ * / | \ \
+ * 1: A$ B$ C$ $ (same as parent)
+ * |
+ * 2: A$ (same as parent)
+ *
+ * The updated relation for offspring is then:
+ *
+ * x <: y :=
+ * if !truncated_path(y):
+ * return prefix(x, y) == y // O(1)
+ * else:
+ * return slow_check_is_offspring(x, y) // worse than O(1)
+ *
+ * (Example definition of truncated_path -- any semantically equivalent way to check that the
+ * sibling's `sibling-label` is not unique will do)
+ *
+ * truncated_path(y) :=
+ * return y == parent(y)
+ *
+ * (Example definition. Any slower-than-O(1) definition will do here. This is the traversing
+ * superclass hierarchy solution)
+ *
+ * slow_check_is_offspring(x, y) :=
+ * if not x: return false
+ * else: return x == y || recursive_is_offspring(parent(x), y)
+ *
+ * In which case slow_check_is_offspring is some non-O(1) way to check if x and is an offspring of y.
+ *
+ * In addition, note that it doesn’t matter if the "x" from above is a unique sibling or not; the
+ * relation will still be correct.
+ *
+ * ------------------------------------------------------------------------------------------------
+ *
+ * Leveraging truncated paths to minimize path lengths.
+ *
+ * As observed above, for any x <: y, it is sufficient to have a full path only for y,
+ * and x can be truncated (to its nearest ancestor's full path).
+ *
+ * We call a node that stores a full path "Assigned", and a node that stores a truncated path
+ * either "Initialized" or "Overflowed."
+ *
+ * "Initialized" means it is still possible to assign a full path to the node, and "Overflowed"
+ * means there is insufficient characters in the alphabet left.
+ *
+ * In this example, assume that we attempt to "Assign" all non-leafs if possible. Leafs
+ * always get truncated (as either Initialized or Overflowed).
+ *
+ * Alphabets = {{A,B,C,D}, {A,B}}
+ * Max Levels = |Alphabets|
+ *
+ * Level
+ * 0: $
+ * / | \ \ \
+ * 1: A$ B$ C$ D$ $ (Overflowed: Too wide)
+ * | |
+ * 2: AA$ C$ (Initialized)
+ * |
+ * 3: AA$ (Overflowed: Too deep)
+ *
+ * (All un-annotated nodes are "Assigned").
+ * Above, the node at level 3 becomes overflowed because it exceeds the max levels. The
+ * right-most node at level 1 becomes overflowed because there's no characters in the alphabet
+ * left in that level.
+ *
+ * The "C$" node is Initialized at level 2, but it can still be promoted to "Assigned" later on
+ * if we wanted to.
+ *
+ * In particular, this is the strategy we use in our implementation
+ * (SubtypeCheck::EnsureInitialized, SubtypeCheck::EnsureAssigned).
+ *
+ * Since the # of characters in our alphabet (BitString) is very limited, we want to avoid
+ * allocating a character to a node until its absolutely necessary.
+ *
+ * All node targets (in `src <: target`) get Assigned, and any parent of an Initialized
+ * node also gets Assigned.
+ */
+struct MockSubtypeCheck; // Forward declaration for testing.
+namespace art {
+
+// This is class is using a template parameter to enable testability without losing performance.
+// KlassT is almost always `mirror::Class*` or `ObjPtr<mirror::Class>`.
+template <typename KlassT /* Pointer-like type to Class */>
+struct SubtypeCheck {
+ // Force this class's SubtypeCheckInfo state into at least Initialized.
+ // As a side-effect, all parent classes also become Assigned|Overflowed.
+ //
+ // Cost: O(Depth(Class))
+ //
+ // Post-condition: State is >= Initialized.
+ // Returns: The precise SubtypeCheckInfo::State.
+ static SubtypeCheckInfo::State EnsureInitialized(KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ return InitializeOrAssign(klass, /*assign*/false).GetState();
+ }
+
+ // Force this class's SubtypeCheckInfo state into Assigned|Overflowed.
+ // As a side-effect, all parent classes also become Assigned|Overflowed.
+ //
+ // Cost: O(Depth(Class))
+ //
+ // Post-condition: State is Assigned|Overflowed.
+ // Returns: The precise SubtypeCheckInfo::State.
+ static SubtypeCheckInfo::State EnsureAssigned(KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ return InitializeOrAssign(klass, /*assign*/true).GetState();
+ }
+
+ // Resets the SubtypeCheckInfo into the Uninitialized state.
+ //
+ // Intended only for the AOT image writer.
+ // This is a static function to avoid calling klass.Depth(), which is unsupported
+ // in some portions of the image writer.
+ //
+ // Cost: O(1).
+ //
+ // Returns: A state that is always Uninitialized.
+ static SubtypeCheckInfo::State ForceUninitialize(KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ // Trying to do this in a real runtime will break thread safety invariants
+ // of existing live objects in the class hierarchy.
+ // This is only safe as the last step when the classes are about to be
+ // written out as an image and IsSubClass is never used again.
+ DCHECK(Runtime::Current() == nullptr || Runtime::Current()->IsAotCompiler())
+ << "This only makes sense when compiling an app image.";
+
+ // Directly read/write the class field here.
+ // As this method is used by image_writer on a copy,
+ // the Class* there is not a real class and using it for anything
+ // more complicated (e.g. ObjPtr or Depth call) will fail dchecks.
+
+ // OK. zero-initializing subtype_check_info_ puts us into the kUninitialized state.
+ SubtypeCheckBits scb_uninitialized = SubtypeCheckBits{}; // NOLINT
+ WriteSubtypeCheckBits(klass, scb_uninitialized);
+
+ // Do not use "SubtypeCheckInfo" API here since that requires Depth()
+ // which would cause a dcheck failure.
+ return SubtypeCheckInfo::kUninitialized;
+ }
+
+ // Retrieve the path to root bitstring as a plain uintN_t value that is amenable to
+ // be used by a fast check "encoded_src & mask_target == encoded_target".
+ //
+ // Cost: O(Depth(Class)).
+ //
+ // Returns the encoded_src value. Must be >= Initialized (EnsureInitialized).
+ static BitString::StorageType GetEncodedPathToRootForSource(const KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK_NE(SubtypeCheckInfo::kUninitialized, GetSubtypeCheckInfo(klass).GetState());
+ return GetSubtypeCheckInfo(klass).GetEncodedPathToRoot();
+ }
+
+ // Retrieve the path to root bitstring as a plain uintN_t value that is amenable to
+ // be used by a fast check "encoded_src & mask_target == encoded_target".
+ //
+ // Cost: O(Depth(Class)).
+ //
+ // Returns the encoded_target value. Must be Assigned (EnsureAssigned).
+ static BitString::StorageType GetEncodedPathToRootForTarget(const KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK_EQ(SubtypeCheckInfo::kAssigned, GetSubtypeCheckInfo(klass).GetState());
+ return GetSubtypeCheckInfo(klass).GetEncodedPathToRoot();
+ }
+
+ // Retrieve the path to root bitstring mask as a plain uintN_t value that is amenable to
+ // be used by a fast check "encoded_src & mask_target == encoded_target".
+ //
+ // Cost: O(Depth(Class)).
+ //
+ // Returns the mask_target value. Must be Assigned (EnsureAssigned).
+ static BitString::StorageType GetEncodedPathToRootMask(const KlassT& klass)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK_EQ(SubtypeCheckInfo::kAssigned, GetSubtypeCheckInfo(klass).GetState());
+ return GetSubtypeCheckInfo(klass).GetEncodedPathToRootMask();
+ }
+
+ // Is the source class a subclass of the target?
+ //
+ // The source state must be at least Initialized, and the target state
+ // must be Assigned, otherwise the result will return kUnknownSubtypeOf.
+ //
+ // See EnsureInitialized and EnsureAssigned. Ideally,
+ // EnsureInitialized will be called previously on all possible sources,
+ // and EnsureAssigned will be called previously on all possible targets.
+ //
+ // Runtime cost: O(Depth(Class)), but would be O(1) if depth was known.
+ //
+ // If the result is known, return kSubtypeOf or kNotSubtypeOf.
+ static SubtypeCheckInfo::Result IsSubtypeOf(const KlassT& source, const KlassT& target)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ SubtypeCheckInfo sci = GetSubtypeCheckInfo(source);
+ SubtypeCheckInfo target_sci = GetSubtypeCheckInfo(target);
+
+ return sci.IsSubtypeOf(target_sci);
+ }
+
+ // Print SubtypeCheck bitstring and overflow to a stream (e.g. for oatdump).
+ static std::ostream& Dump(const KlassT& klass, std::ostream& os)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ return os << GetSubtypeCheckInfo(klass);
+ }
+
+ static void WriteStatus(const KlassT& klass, ClassStatus status)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ WriteStatusImpl(klass, status);
+ }
+
+ private:
+ static KlassT GetParentClass(const KlassT& klass)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK(klass->HasSuperClass());
+ return KlassT(klass->GetSuperClass());
+ }
+
+ static SubtypeCheckInfo InitializeOrAssign(KlassT& klass, bool assign)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ if (UNLIKELY(!klass->HasSuperClass())) {
+ // Object root always goes directly from Uninitialized -> Assigned.
+
+ const SubtypeCheckInfo root_sci = GetSubtypeCheckInfo(klass);
+ if (root_sci.GetState() != SubtypeCheckInfo::kUninitialized) {
+ return root_sci; // No change needed.
+ }
+
+ const SubtypeCheckInfo new_root_sci = root_sci.CreateRoot();
+ SetSubtypeCheckInfo(klass, new_root_sci);
+
+ // The object root is always in the Uninitialized|Assigned state.
+ DCHECK_EQ(SubtypeCheckInfo::kAssigned, GetSubtypeCheckInfo(klass).GetState())
+ << "Invalid object root state, must be Assigned";
+ return new_root_sci;
+ }
+
+ // Force all ancestors to Assigned | Overflowed.
+ KlassT parent_klass = GetParentClass(klass);
+ EnsureAssigned(parent_klass);
+ if (kIsDebugBuild) {
+ SubtypeCheckInfo::State parent_state = GetSubtypeCheckInfo(parent_klass).GetState();
+ DCHECK(parent_state == SubtypeCheckInfo::kAssigned ||
+ parent_state == SubtypeCheckInfo::kOverflowed)
+ << "Expected parent Assigned|Overflowed, but was: " << parent_state;
+ }
+
+ // Read.
+ SubtypeCheckInfo sci = GetSubtypeCheckInfo(klass);
+ SubtypeCheckInfo parent_sci = GetSubtypeCheckInfo(parent_klass);
+
+ // Modify.
+ const SubtypeCheckInfo::State sci_state = sci.GetState();
+ // Skip doing any work if the state is already up-to-date.
+ // - assign == false -> Initialized or higher.
+ // - assign == true -> Assigned or higher.
+ if (sci_state == SubtypeCheckInfo::kUninitialized ||
+ (sci_state == SubtypeCheckInfo::kInitialized && assign)) {
+ // Copy parent path into the child.
+ //
+ // If assign==true, this also appends Parent.Next value to the end.
+ // Then the Parent.Next value is incremented to avoid allocating
+ // the same value again to another node.
+ sci = parent_sci.CreateChild(assign); // Note: Parent could be mutated.
+ } else {
+ // Nothing to do, already >= Initialized.
+ return sci;
+ }
+
+ // Post-condition: EnsureAssigned -> Assigned|Overflowed.
+ // Post-condition: EnsureInitialized -> Not Uninitialized.
+ DCHECK_NE(sci.GetState(), SubtypeCheckInfo::kUninitialized);
+
+ if (assign) {
+ DCHECK_NE(sci.GetState(), SubtypeCheckInfo::kInitialized);
+ }
+
+ // Write.
+ SetSubtypeCheckInfo(klass, sci); // self
+ SetSubtypeCheckInfo(parent_klass, parent_sci); // parent
+
+ return sci;
+ }
+
+ static SubtypeCheckBitsAndStatus ReadField(const KlassT& klass)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ SubtypeCheckBitsAndStatus current_bits_and_status;
+
+ int32_t int32_data = klass->GetField32Volatile(klass->StatusOffset());
+ current_bits_and_status.int32_alias_ = int32_data;
+
+ if (kIsDebugBuild) {
+ SubtypeCheckBitsAndStatus tmp;
+ memcpy(&tmp, &int32_data, sizeof(tmp));
+ DCHECK_EQ(0, memcmp(&tmp, ¤t_bits_and_status, sizeof(tmp))) << int32_data;
+ }
+ return current_bits_and_status;
+ }
+
+ static void WriteSubtypeCheckBits(const KlassT& klass, const SubtypeCheckBits& new_bits)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ // Use a "CAS" to write the SubtypeCheckBits in the class.
+ // Although we have exclusive access to the bitstrings, because
+ // ClassStatus and SubtypeCheckBits share the same word, another thread could
+ // potentially overwrite that word still.
+
+ SubtypeCheckBitsAndStatus new_value;
+ ClassStatus old_status;
+ SubtypeCheckBitsAndStatus full_old;
+ while (true) {
+ // TODO: Atomic compare-and-swap does not update the 'expected' parameter,
+ // so we have to read it as a separate step instead.
+ SubtypeCheckBitsAndStatus old_value = ReadField(klass);
+
+ {
+ SubtypeCheckBits old_bits = old_value.subtype_check_info_;
+ if (memcmp(&old_bits, &new_bits, sizeof(old_bits)) == 0) {
+ // Avoid dirtying memory when the data hasn't changed.
+ return;
+ }
+ }
+
+ full_old = old_value;
+ old_status = old_value.status_;
+
+ new_value = old_value;
+ new_value.subtype_check_info_ = new_bits;
+
+ if (kIsDebugBuild) {
+ int32_t int32_data = 0;
+ memcpy(&int32_data, &new_value, sizeof(int32_t));
+ DCHECK_EQ(int32_data, new_value.int32_alias_) << int32_data;
+
+ DCHECK_EQ(old_status, new_value.status_)
+ << "full new: " << bit_cast<uint32_t>(new_value)
+ << ", full old: " << bit_cast<uint32_t>(full_old);
+ }
+
+ if (CasFieldWeakSequentiallyConsistent32(klass,
+ klass->StatusOffset(),
+ old_value.int32_alias_,
+ new_value.int32_alias_)) {
+ break;
+ }
+ }
+ }
+
+ static void WriteStatusImpl(const KlassT& klass, ClassStatus status)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ // Despite not having a lock annotation, this is done with mutual exclusion.
+ // See Class::SetStatus for more details.
+ SubtypeCheckBitsAndStatus new_value;
+ ClassStatus old_status;
+ while (true) {
+ // TODO: Atomic compare-and-swap does not update the 'expected' parameter,
+ // so we have to read it as a separate step instead.
+ SubtypeCheckBitsAndStatus old_value = ReadField(klass);
+ old_status = old_value.status_;
+
+ if (memcmp(&old_status, &status, sizeof(status)) == 0) {
+ // Avoid dirtying memory when the data hasn't changed.
+ return;
+ }
+
+ new_value = old_value;
+ new_value.status_ = status;
+
+ if (CasFieldWeakSequentiallyConsistent32(klass,
+ klass->StatusOffset(),
+ old_value.int32_alias_,
+ new_value.int32_alias_)) {
+ break;
+ }
+ }
+ }
+
+ static bool CasFieldWeakSequentiallyConsistent32(const KlassT& klass,
+ MemberOffset offset,
+ int32_t old_value,
+ int32_t new_value)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ if (Runtime::Current() != nullptr && Runtime::Current()->IsActiveTransaction()) {
+ return klass->template
+ CasFieldWeakSequentiallyConsistent32</*kTransactionActive*/true>(offset,
+ old_value,
+ new_value);
+ } else {
+ return klass->template
+ CasFieldWeakSequentiallyConsistent32</*kTransactionActive*/false>(offset,
+ old_value,
+ new_value);
+ }
+ }
+
+ // Get the SubtypeCheckInfo for a klass. O(Depth(Class)) since
+ // it also requires calling klass->Depth.
+ //
+ // Anything calling this function will also be O(Depth(Class)).
+ static SubtypeCheckInfo GetSubtypeCheckInfo(const KlassT& klass)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ SubtypeCheckBitsAndStatus current_bits_and_status = ReadField(klass);
+
+ size_t depth = klass->Depth();
+ const SubtypeCheckInfo current =
+ SubtypeCheckInfo::Create(current_bits_and_status.subtype_check_info_, depth);
+ return current;
+ }
+
+ static void SetSubtypeCheckInfo(KlassT& klass,
+ const SubtypeCheckInfo& new_sci)
+ REQUIRES(Locks::subtype_check_lock_)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ SubtypeCheckBits new_bits = new_sci.GetSubtypeCheckBits();
+ WriteSubtypeCheckBits(klass, new_bits);
+ }
+
+ // Tests can inherit this class. Normal code should use static methods.
+ SubtypeCheck() = default;
+ SubtypeCheck(const SubtypeCheck& other) = default;
+ SubtypeCheck(SubtypeCheck&& other) = default;
+ ~SubtypeCheck() = default;
+
+ friend struct ::MockSubtypeCheck;
+};
+
+} // namespace art
+
+#endif // ART_RUNTIME_SUBTYPE_CHECK_H_