| /* |
| * 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_INFO_H_ |
| #define ART_RUNTIME_SUBTYPE_CHECK_INFO_H_ |
| |
| #include "base/bit_string.h" |
| #include "subtype_check_bits.h" |
| |
| // Forward-declare for testing purposes. |
| struct SubtypeCheckInfoTest; |
| |
| namespace art { |
| |
| /** |
| * SubtypeCheckInfo is a logical label for the class SubtypeCheck data, which is necessary to |
| * perform efficient O(1) subtype comparison checks. See also subtype_check.h |
| * for the more general explanation of how the labels are used overall. |
| * |
| * For convenience, we also store the class depth within an SubtypeCheckInfo, since nearly all |
| * calculations are dependent on knowing the depth of the class. |
| * |
| * A SubtypeCheckInfo logically has: |
| * * Depth - How many levels up to the root (j.l.Object)? |
| * * PathToRoot - Possibly truncated BitString that encodes path to root |
| * * Next - The value a newly inserted Child would get appended to its path. |
| * * Overflow - If this path can never become a full path. |
| * |
| * Depending on the values of the above, it can be in one of these logical states, |
| * which are introduced in subtype_check.h: |
| * |
| * Transient States Terminal States |
| * |
| * +-----------------+ +--------------------+ +-------------------+ |
| * | | | | | | |
| * | Uninitialized | +---> Initialized | +---> Assigned | |
| * | | | | | | |
| * +--------+--------+ +---------+----------+ +-------------------+ |
| * | | |
| * | | |
| * | | +-------------------+ |
| * | +----------------> | |
| * | | Overflowed | |
| * +-----------------------------------------> | |
| * +-------------------+ |
| * |
| * Invariants: |
| * |
| * Initialized => Parent >= Initialized |
| * |
| * Assigned => Parent == Assigned |
| * |
| * Overflowed => Parent == Overflowed || Parent.Next == Overflowed |
| * |
| * Thread-safety invariants: |
| * |
| * Initialized => Parent == Assigned |
| * // For a class that has an Initialized bitstring, its superclass needs to have an |
| * // Assigned bitstring since if its super class's bitstring is not Assigned yet, |
| * // once it becomes Assigned, we cannot update its children's bitstrings to maintain |
| * // all the tree invariants (below) atomically. |
| * |
| * -------------------------------------------------------------------------------------------- |
| * Knowing these transitions above, we can more closely define the various terms and operations: |
| * |
| * Definitions: |
| * (see also base/bit_string.h definitions). |
| * |
| * Depth := Distance(Root, Class) |
| * Safe(Depth) := Min(Depth, MaxBitstringLen) |
| * PathToRoot := Bitstring[0..Safe(Depth)) |
| * Next := Bitstring[Depth] |
| * OF ∈ {False, True} |
| * TruncPath(D) := PathToRoot[0..D) |
| * |
| * Local Invariants: |
| * |
| * Uninitialized <=> StrLen(PathToRoot) == 0 |
| * Next == 0 |
| * Initialized <=> StrLen(PathToRoot) < Depth |
| * Next == 0 |
| * Assigned <=> StrLen(PathToRoot) == Depth |
| * Next > 1 |
| * Overflowed <=> OF == True |
| * |
| * Tree Invariants: |
| * |
| * Uninitialized => |
| * forall child ∈ Children(Class): |
| * child.State == Uninitialized |
| * |
| * Assigned => |
| * forall child ∈ Children(Class): |
| * Next > Child.PathToRoot[Child.Depth-1] |
| * |
| * ! Uninitialized => |
| * forall ancestor ∈ Ancestors(Class): |
| * TruncPath(ancestor.Depth) == ancestor.PathToRoot |
| * forall unrelated ∈ (Classes - Ancestors(Class)) |
| * s.t. unrelated.State == Assigned: |
| * TruncPath(unrelated.Depth) != unrelated.PathToRoot |
| * |
| * Thread-safety invariants: |
| * |
| * Initialized <=> StrLen(PathToRoot) == Safe(Depth - 1) |
| * // Initialized State corresponds to exactly 1 bitstring. |
| * // Cannot transition from Initialized to Initialized. |
| */ |
| struct SubtypeCheckInfo { |
| // See above documentation for possible state transitions. |
| enum State { |
| kUninitialized, |
| kInitialized, |
| kAssigned, |
| kOverflowed |
| }; |
| |
| // The result of a "src IsSubType target" check: |
| enum Result { |
| kUnknownSubtypeOf, // Not enough data. Operand states weren't high enough. |
| kNotSubtypeOf, // Enough data. src is not a subchild of the target. |
| kSubtypeOf // Enough data. src is a subchild of the target. |
| }; |
| |
| // Chop off the depth, returning only the bitstring+of state. |
| // (Used to store into memory, since storing the depth would be redundant.) |
| SubtypeCheckBits GetSubtypeCheckBits() const { |
| return bitstring_and_of_; |
| } |
| |
| // Create from the depth and the bitstring+of state. |
| // This is done for convenience to avoid passing in "depth" everywhere, |
| // since our current state is almost always a function of depth. |
| static SubtypeCheckInfo Create(SubtypeCheckBits compressed_value, size_t depth) { |
| SubtypeCheckInfo io; |
| io.depth_ = depth; |
| io.bitstring_and_of_ = compressed_value; |
| io.DcheckInvariants(); |
| return io; |
| } |
| |
| // Is this a subtype of the target? |
| // |
| // The current state must be at least Initialized, and the target state |
| // must be Assigned, otherwise the result will return kUnknownSubtypeOf. |
| // |
| // Normally, return kSubtypeOf or kNotSubtypeOf. |
| Result IsSubtypeOf(const SubtypeCheckInfo& target) { |
| if (target.GetState() != SubtypeCheckInfo::kAssigned) { |
| return Result::kUnknownSubtypeOf; |
| } else if (GetState() == SubtypeCheckInfo::kUninitialized) { |
| return Result::kUnknownSubtypeOf; |
| } |
| |
| BitString::StorageType source_value = GetEncodedPathToRoot(); |
| BitString::StorageType target_value = target.GetEncodedPathToRoot(); |
| BitString::StorageType target_mask = target.GetEncodedPathToRootMask(); |
| |
| bool result = (source_value & target_mask) == (target_value); |
| if (result) { |
| DCHECK_EQ(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot()) |
| << "Source: " << *this << ", Target: " << target; |
| } else { |
| DCHECK_NE(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot()) |
| << "Source: " << *this << ", Target: " << target; |
| } |
| |
| // Note: We could've also used shifts here, as described in subtype_check_bits.h, |
| // but it doesn't make much of a difference in the Runtime since we aren't trying to optimize |
| // for code size. |
| |
| return result ? Result::kSubtypeOf : Result::kNotSubtypeOf; |
| } |
| |
| // Returns a new root SubtypeCheckInfo with a blank PathToRoot. |
| // Post-condition: The return valued has an Assigned state. |
| static SubtypeCheckInfo CreateRoot() { |
| SubtypeCheckInfo io{}; // NOLINT |
| io.depth_ = 0u; |
| io.SetNext(io.GetNext() + 1u); |
| |
| // The root is always considered assigned once it is no longer Initialized. |
| DCHECK_EQ(SubtypeCheckInfo::kAssigned, io.GetState()); |
| return io; |
| } |
| |
| // Copies the current PathToRoot into the child. |
| // |
| // If assign_next is true, then also assign a new SubtypeCheckInfo for a child by |
| // assigning the current Next value to its PathToRoot[Depth] component. |
| // Updates the current Next value as a side effect. |
| // |
| // Preconditions: State is either Assigned or Overflowed. |
| // Returns: A new child >= Initialized state. |
| SubtypeCheckInfo CreateChild(bool assign_next) { |
| SubtypeCheckInfo child = *this; // Copy everything (path, next, of). |
| child.depth_ = depth_ + 1u; |
| |
| // Must be Assigned or Overflowed in order to create a subchild. |
| DCHECK(GetState() == kAssigned || GetState() == kOverflowed) |
| << "Unexpected bitstring state: " << GetState(); |
| |
| // Begin transition to >= Initialized. |
| |
| // Always attempt to re-initialize Child's Next value. |
| // Next must be non-0 to disambiguate it from Uninitialized. |
| child.MaybeInitNext(); |
| |
| // Always clear the inherited Parent's next Value on the child. |
| OverwriteNextValueFromParent(/*inout*/&child, BitStringChar{}); // NOLINT |
| |
| // The state is now Initialized | Overflowed. |
| DCHECK_NE(kAssigned, child.GetState()) << child.GetBitString(); |
| DCHECK_NE(kUninitialized, child.GetState()) << child.GetBitString(); |
| |
| if (assign_next == false) { |
| child.DcheckInvariants(); |
| return child; |
| } |
| |
| // Begin transition to >= Assigned. |
| |
| // Assign attempt. |
| if (HasNext() && !bitstring_and_of_.overflow_) { |
| // Do not bother assigning if parent had overflowed. |
| BitStringChar next = GetNext(); |
| if (next != next.MaximumValue()) { |
| // The parent's "next" value is now the child's latest path element. |
| OverwriteNextValueFromParent(/*inout*/&child, next); |
| // Update self next value, so that future CreateChild calls |
| // do not get the same path value. |
| SetNext(next + 1u); |
| } else { |
| child.MarkOverflowed(); // Too wide. |
| } |
| } else { |
| child.MarkOverflowed(); // Too deep, or parent was already overflowed. |
| } |
| |
| // The state is now Assigned | Overflowed. |
| DCHECK(child.GetState() == kAssigned || child.GetState() == kOverflowed); |
| |
| child.DcheckInvariants(); |
| return child; |
| } |
| |
| // 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 |
| // Empty bitstring (all 0s) -> uninitialized. |
| DCHECK(!bitstring_and_of_.overflow_); |
| return kUninitialized; |
| } |
| |
| if (bitstring_and_of_.overflow_) { |
| // Overflowed if and only if the OF bit was set. |
| return kOverflowed; |
| } |
| |
| // Either Assigned or Initialized. |
| BitString path_to_root = GetPathToRoot(); |
| |
| DCHECK(!HasNext() || GetNext() != BitStringChar{}) // NOLINT |
| << "Expected (Assigned|Initialized) state to have >0 Next value: " |
| << GetNext() << " path: " << path_to_root; |
| |
| if (path_to_root.Length() == depth_) { |
| return kAssigned; |
| } |
| |
| return kInitialized; |
| } |
| |
| // 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". |
| BitString::StorageType GetEncodedPathToRoot() const { |
| BitString::StorageType data = static_cast<BitString::StorageType>(GetPathToRoot()); |
| // Bit strings are logically in the least-significant memory. |
| // Shift it so the bits are all most-significant. |
| return data << (BitSizeOf(data) - BitStructSizeOf<BitString>()); |
| } |
| |
| // Retrieve the path to root bitstring mask as a plain uintN_t that is amenable to |
| // be used by a fast check "encoded_src & mask_target == encoded_target". |
| BitString::StorageType GetEncodedPathToRootMask() const { |
| size_t num_bitchars = GetSafeDepth(); |
| size_t bitlength = BitString::GetBitLengthTotalAtPosition(num_bitchars); |
| |
| BitString::StorageType mask_all = |
| std::numeric_limits<BitString::StorageType>::max(); |
| BitString::StorageType mask_lsb = |
| MaskLeastSignificant<BitString::StorageType>( |
| BitSizeOf<BitString::StorageType>() - bitlength); |
| |
| BitString::StorageType result = mask_all & ~mask_lsb; |
| |
| // TODO: refactor above code into MaskMostSignificant? |
| return result; |
| } |
| |
| // Get the "Next" bitchar, assuming that there is one to get. |
| BitStringChar GetNext() const { |
| DCHECK(HasNext()); |
| return GetBitString()[depth_]; |
| } |
| |
| // Try to get the Next value, if there is one. |
| // Returns: Whether or not there was a Next value. |
| bool MaybeGetNext(/*out*/BitStringChar* next) const { |
| DCHECK(next != nullptr); |
| |
| if (HasNext()) { |
| *next = GetBitString()[depth_]; |
| return true; |
| } |
| return false; |
| } |
| |
| private: |
| // Constructor intended for testing. Runs all invariant checks. |
| SubtypeCheckInfo(BitString path_to_root, BitStringChar next, bool overflow, size_t depth) { |
| SubtypeCheckBits iod; |
| iod.bitstring_ = path_to_root; |
| iod.overflow_ = overflow; |
| |
| bitstring_and_of_ = iod; |
| depth_ = depth; |
| |
| // Len(Path-to-root) <= Depth. |
| DCHECK_GE(depth_, path_to_root.Length()) |
| << "Path was too long for the depth, path: " << path_to_root; |
| |
| bool did_overlap = false; |
| if (HasNext()) { |
| if (kIsDebugBuild) { |
| did_overlap = (GetNext() != BitStringChar{}); // NOLINT |
| } |
| |
| SetNext(next); |
| |
| DCHECK_EQ(next, GetNext()); |
| } |
| // "Next" must be set before we can check the invariants. |
| DcheckInvariants(); |
| DCHECK(!did_overlap) |
| << "Path to root overlapped with Next value, path: " << path_to_root; |
| DCHECK_EQ(path_to_root, GetPathToRoot()); |
| } |
| |
| // Factory intended for testing. Skips DcheckInvariants. |
| static SubtypeCheckInfo MakeUnchecked(BitString bitstring, bool overflow, size_t depth) { |
| SubtypeCheckBits iod; |
| iod.bitstring_ = bitstring; |
| iod.overflow_ = overflow; |
| |
| SubtypeCheckInfo io; |
| io.depth_ = depth; |
| io.bitstring_and_of_ = iod; |
| |
| return io; |
| } |
| |
| void SetNext(BitStringChar next) { |
| DCHECK(HasNext()); |
| BitString bs = GetBitString(); |
| bs.SetAt(depth_, next); |
| SetBitString(bs); |
| } |
| |
| void SetNextUnchecked(BitStringChar next) { |
| BitString bs = GetBitString(); |
| bs.SetAt(depth_, next); |
| SetBitStringUnchecked(bs); |
| } |
| |
| void MaybeInitNext() { |
| if (HasNext()) { |
| // Clearing out the "Next" value like this |
| // is often an intermediate operation which temporarily |
| // violates the invariants. Do not do the extra dchecks. |
| SetNextUnchecked(BitStringChar{}); // NOLINT |
| SetNextUnchecked(GetNext()+1u); |
| } |
| } |
| |
| BitString GetPathToRoot() const { |
| size_t end = GetSafeDepth(); |
| return GetBitString().Truncate(end); |
| } |
| |
| bool HasNext() const { |
| return depth_ < BitString::kCapacity; |
| } |
| |
| void MarkOverflowed() { |
| bitstring_and_of_.overflow_ = true; |
| } |
| |
| static constexpr bool HasBitStringCharStorage(size_t idx) { |
| return idx < BitString::kCapacity; |
| } |
| |
| size_t GetSafeDepth() const { |
| return GetSafeDepth(depth_); |
| } |
| |
| // Get a "safe" depth, one that is truncated to the bitstring max capacity. |
| // Using a value larger than this will cause undefined behavior. |
| static size_t GetSafeDepth(size_t depth) { |
| return std::min(depth, BitString::kCapacity); |
| } |
| |
| BitString GetBitString() const { |
| return bitstring_and_of_.bitstring_; |
| } |
| |
| void SetBitString(const BitString& val) { |
| SetBitStringUnchecked(val); |
| DcheckInvariants(); |
| } |
| |
| void SetBitStringUnchecked(const BitString& val) { |
| bitstring_and_of_.bitstring_ = val; |
| } |
| |
| void OverwriteNextValueFromParent(/*inout*/SubtypeCheckInfo* child, BitStringChar value) const { |
| // Helper function for CreateChild. |
| if (HasNext()) { |
| // When we copied the "Next" value, it is now our |
| // last path component in the child. |
| // Always overwrite it with either a cleared value or the parent's Next value. |
| BitString bs = child->GetBitString(); |
| |
| // Safe write. This.Next always occupies same slot as Child[Depth_]. |
| DCHECK(child->HasBitStringCharStorage(depth_)); |
| |
| bs.SetAt(depth_, value); |
| |
| // The child is temporarily in a bad state until it is fixed up further. |
| // Do not do the normal dchecks which do not allow transient badness. |
| child->SetBitStringUnchecked(bs); |
| } |
| } |
| |
| void DcheckInvariants() const { |
| if (kIsDebugBuild) { |
| CHECK_GE(GetSafeDepth(depth_ + 1u), GetBitString().Length()) |
| << "Bitstring too long for depth, bitstring: " << GetBitString() << ", depth: " << depth_; |
| |
| BitString path_to_root = GetPathToRoot(); |
| |
| // A 'null' (\0) character in path-to-root must be followed only |
| // by other null characters. |
| size_t i; |
| for (i = 0; i < BitString::kCapacity; ++i) { |
| BitStringChar bc = path_to_root[i]; |
| if (bc == 0u) { |
| break; |
| } |
| } |
| |
| // All characters following a 0 must also be 0. |
| for (; i < BitString::kCapacity; ++i) { |
| BitStringChar bc = path_to_root[i]; |
| if (bc != 0u) { |
| LOG(FATAL) << "Path to root had non-0s following 0s: " << path_to_root; |
| } |
| } |
| |
| // Trigger any dchecks in GetState. |
| (void)GetState(); |
| } |
| } |
| |
| SubtypeCheckInfo() = default; |
| size_t depth_; |
| SubtypeCheckBits bitstring_and_of_; |
| |
| friend struct ::SubtypeCheckInfoTest; |
| friend std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io); |
| }; |
| |
| // Prints the SubtypeCheckInfo::State, e.g. "kUnitialized". |
| inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo::State& state) { |
| switch (state) { |
| case SubtypeCheckInfo::kUninitialized: |
| os << "kUninitialized"; |
| break; |
| case SubtypeCheckInfo::kInitialized: |
| os << "kInitialized"; |
| break; |
| case SubtypeCheckInfo::kAssigned: |
| os << "kAssigned"; |
| break; |
| case SubtypeCheckInfo::kOverflowed: |
| os << "kOverflowed"; |
| break; |
| default: |
| os << "(Invalid SubtypeCheckInfo::State " << static_cast<int>(state) << ")"; |
| } |
| return os; |
| } |
| |
| // Prints e.g. "SubtypeCheckInfo{BitString[1,2,3], depth: 3, of:1}" |
| inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io) { |
| os << "SubtypeCheckInfo{" << io.GetBitString() << ", " |
| << "depth: " << io.depth_ << ", of:" << io.bitstring_and_of_.overflow_ << "}"; |
| return os; |
| } |
| |
| } // namespace art |
| |
| #endif // ART_RUNTIME_SUBTYPE_CHECK_INFO_H_ |