/*
* 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"
// Build flag for the bitstring subtype check runtime hooks.
constexpr bool kBitstringSubtypeCheckEnabled = false;
/**
* 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.
*/
namespace art {
struct MockSubtypeCheck; // Forward declaration for testing.
// This class is using a template parameter to enable testability without losing performance.
// ClassPtr is almost always `mirror::Class*` or `ObjPtr<mirror::Class>`.
template <typename ClassPtr /* 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(ClassPtr 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(ClassPtr 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(ClassPtr 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{};
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(ClassPtr 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(ClassPtr 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(ClassPtr 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(ClassPtr source, ClassPtr 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(ClassPtr klass, std::ostream& os)
REQUIRES_SHARED(Locks::mutator_lock_) {
return os << GetSubtypeCheckInfo(klass);
}
static void WriteStatus(ClassPtr klass, ClassStatus status)
REQUIRES_SHARED(Locks::mutator_lock_) {
WriteStatusImpl(klass, status);
}
private:
static ClassPtr GetParentClass(ClassPtr klass)
REQUIRES_SHARED(Locks::mutator_lock_) {
DCHECK(klass->HasSuperClass());
return ClassPtr(klass->GetSuperClass());
}
static SubtypeCheckInfo InitializeOrAssign(ClassPtr 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.
ClassPtr parent_klass = GetParentClass(klass);
size_t parent_depth = InitializeOrAssign(parent_klass, /*assign*/true).GetDepth();
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, parent_depth + 1u);
SubtypeCheckInfo parent_sci = GetSubtypeCheckInfo(parent_klass, parent_depth);
// 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(ClassPtr 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(ClassPtr 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(ClassPtr 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(ClassPtr 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(ClassPtr klass)
REQUIRES_SHARED(Locks::mutator_lock_) {
return GetSubtypeCheckInfo(klass, klass->Depth());
}
// Get the SubtypeCheckInfo for a klass with known depth.
static SubtypeCheckInfo GetSubtypeCheckInfo(ClassPtr klass, size_t depth)
REQUIRES_SHARED(Locks::mutator_lock_) {
DCHECK_EQ(depth, klass->Depth());
SubtypeCheckBitsAndStatus current_bits_and_status = ReadField(klass);
const SubtypeCheckInfo current =
SubtypeCheckInfo::Create(current_bits_and_status.subtype_check_info_, depth);
return current;
}
static void SetSubtypeCheckInfo(ClassPtr 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_