• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_RUNTIME_SUBTYPE_CHECK_INFO_H_
18 #define ART_RUNTIME_SUBTYPE_CHECK_INFO_H_
19 
20 #include "base/bit_string.h"
21 #include "base/logging.h"
22 #include "subtype_check_bits.h"
23 
24 // Forward-declare for testing purposes.
25 struct SubtypeCheckInfoTest;
26 
27 namespace art {
28 
29 /**
30  * SubtypeCheckInfo is a logical label for the class SubtypeCheck data, which is necessary to
31  * perform efficient O(1) subtype comparison checks. See also subtype_check.h
32  * for the more general explanation of how the labels are used overall.
33  *
34  * For convenience, we also store the class depth within an SubtypeCheckInfo, since nearly all
35  * calculations are dependent on knowing the depth of the class.
36  *
37  * A SubtypeCheckInfo logically has:
38  *          * Depth - How many levels up to the root (j.l.Object)?
39  *          * PathToRoot - Possibly truncated BitString that encodes path to root
40  *          * Next - The value a newly inserted Child would get appended to its path.
41  *          * Overflow - If this path can never become a full path.
42  *
43  * Depending on the values of the above, it can be in one of these logical states,
44  * which are introduced in subtype_check.h:
45  *
46  *               Transient States                         Terminal States
47  *
48  *  +-----------------+     +--------------------+     +-------------------+
49  *  |                 |     |                    |     |                   |
50  *  |  Uninitialized  | +--->    Initialized     | +--->     Assigned      |
51  *  |                 |     |                    |     |                   |
52  *  +--------+--------+     +---------+----------+     +-------------------+
53  *           |                        |
54  *           |                        |
55  *           |                        |                +-------------------+
56  *           |                        +---------------->                   |
57  *           |                                         |     Overflowed    |
58  *           +----------------------------------------->                   |
59  *                                                     +-------------------+
60  *
61  * Invariants:
62  *
63  *   Initialized      => Parent >= Initialized
64  *
65  *   Assigned         => Parent == Assigned
66  *
67  *   Overflowed       => Parent == Overflowed || Parent.Next == Overflowed
68  *
69  * Thread-safety invariants:
70  *
71  *   Initialized      => Parent == Assigned
72  *   // For a class that has an Initialized bitstring, its superclass needs to have an
73  *   // Assigned bitstring since if its super class's bitstring is not Assigned yet,
74  *   // once it becomes Assigned, we cannot update its children's bitstrings to maintain
75  *   // all the tree invariants (below) atomically.
76  *
77  * --------------------------------------------------------------------------------------------
78  * Knowing these transitions above, we can more closely define the various terms and operations:
79  *
80  * Definitions:
81  *   (see also base/bit_string.h definitions).
82  *
83  *           Depth :=  Distance(Root, Class)
84  *     Safe(Depth) :=  Min(Depth, MaxBitstringLen)
85  *      PathToRoot :=  Bitstring[0..Safe(Depth))
86  *           Next  :=  Bitstring[Depth]
87  *           OF    ∈   {False, True}
88  *    TruncPath(D) :=  PathToRoot[0..D)
89  *
90  * Local Invariants:
91  *
92  *   Uninitialized <=> StrLen(PathToRoot) == 0
93  *                     Next == 0
94  *                     OF == False
95  *   Initialized   <=> StrLen(PathToRoot) < Depth
96  *                     Next == 1
97  *                     OF == False
98  *   Assigned      <=> StrLen(PathToRoot) == Depth
99  *                     Next >= 1
100  *                     OF == False
101  *   Overflowed    <=> OF == True
102  *
103  * Tree Invariants:
104  *
105  *   Uninitialized =>
106  *     forall child ∈ Children(Class):
107  *       child.State == Uninitialized
108  *
109  *   Assigned       =>
110  *     forall child ∈ Children(Class):
111  *       Next > Child.PathToRoot[Child.Depth-1]
112  *
113  *   ! Uninitialized =>
114  *     forall ancestor ∈ Ancestors(Class):
115  *       TruncPath(ancestor.Depth) == ancestor.PathToRoot
116  *     forall unrelated ∈ (Classes - Ancestors(Class))
117  *         s.t. unrelated.State == Assigned:
118  *       TruncPath(unrelated.Depth) != unrelated.PathToRoot
119  *
120  * Thread-safety invariants:
121  *
122  *   Initialized   <=> StrLen(PathToRoot) == Safe(Depth - 1)
123  *   // Initialized State corresponds to exactly 1 bitstring.
124  *   // Cannot transition from Initialized to Initialized.
125  */
126 struct SubtypeCheckInfo {
127   // See above documentation for possible state transitions.
128   enum State {
129     kUninitialized,
130     kInitialized,
131     kAssigned,
132     kOverflowed
133   };
134 
135   // The result of a "src IsSubType target" check:
136   enum Result {
137     kUnknownSubtypeOf,  // Not enough data. Operand states weren't high enough.
138     kNotSubtypeOf,      // Enough data. src is not a subchild of the target.
139     kSubtypeOf          // Enough data. src is a subchild of the target.
140   };
141 
142   // Get the raw depth.
GetDepthSubtypeCheckInfo143   size_t GetDepth() const {
144     return depth_;
145   }
146 
147   // Chop off the depth, returning only the bitstring+of state.
148   // (Used to store into memory, since storing the depth would be redundant.)
GetSubtypeCheckBitsSubtypeCheckInfo149   SubtypeCheckBits GetSubtypeCheckBits() const {
150     return bitstring_and_of_;
151   }
152 
153   // Create from the depth and the bitstring+of state.
154   // This is done for convenience to avoid passing in "depth" everywhere,
155   // since our current state is almost always a function of depth.
CreateSubtypeCheckInfo156   static SubtypeCheckInfo Create(const SubtypeCheckBits& compressed_value, size_t depth) {
157     SubtypeCheckInfo io;
158     io.depth_ = depth;
159     io.bitstring_and_of_ = compressed_value;
160     io.DcheckInvariants();
161     return io;
162   }
163 
164   // Is this a subtype of the target?
165   //
166   // The current state must be at least Initialized, and the target state
167   // must be Assigned, otherwise the result will return kUnknownSubtypeOf.
168   //
169   // Normally, return kSubtypeOf or kNotSubtypeOf.
IsSubtypeOfSubtypeCheckInfo170   Result IsSubtypeOf(const SubtypeCheckInfo& target) {
171     if (target.GetState() != SubtypeCheckInfo::kAssigned ||
172         GetState() == SubtypeCheckInfo::kUninitialized) {
173       return Result::kUnknownSubtypeOf;
174     }
175 
176     BitString::StorageType source_value = GetEncodedPathToRoot();
177     BitString::StorageType target_value = target.GetEncodedPathToRoot();
178     BitString::StorageType target_mask = target.GetEncodedPathToRootMask();
179 
180     bool result = (source_value & target_mask) == (target_value);
181     if (result) {
182       DCHECK_EQ(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot())
183           << "Source: " << *this << ", Target: " << target;
184     } else {
185       DCHECK_NE(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot())
186           << "Source: " << *this << ", Target: " << target;
187     }
188 
189     // Note: We could've also used shifts here, as described in subtype_check_bits.h,
190     // but it doesn't make much of a difference in the Runtime since we aren't trying to optimize
191     // for code size.
192 
193     return result ? Result::kSubtypeOf : Result::kNotSubtypeOf;
194   }
195 
196   // Returns a new root SubtypeCheckInfo with a blank PathToRoot.
197   // Post-condition: The return valued has an Assigned state.
CreateRootSubtypeCheckInfo198   static SubtypeCheckInfo CreateRoot() {
199     SubtypeCheckInfo io{};
200     io.depth_ = 0u;
201     io.SetNext(io.GetNext() + 1u);
202 
203     // The root is always considered assigned once it is no longer Initialized.
204     DCHECK_EQ(SubtypeCheckInfo::kAssigned, io.GetState());
205     return io;
206   }
207 
208   // Copies the current PathToRoot into the child.
209   //
210   // If assign_next is true, then also assign a new SubtypeCheckInfo for a child by
211   // assigning the current Next value to its PathToRoot[Depth] component.
212   // Updates the current Next value as a side effect.
213   //
214   // Preconditions: State is either Assigned or Overflowed.
215   // Returns: A new child >= Initialized state.
CreateChildSubtypeCheckInfo216   SubtypeCheckInfo CreateChild(bool assign_next) {
217     SubtypeCheckInfo child = *this;  // Copy everything (path, next, of).
218     child.depth_ = depth_ + 1u;
219 
220     // Must be Assigned or Overflowed in order to create a subchild.
221     DCHECK(GetState() == kAssigned || GetState() == kOverflowed)
222         << "Unexpected bitstring state: " << GetState();
223 
224     // Begin transition to >= Initialized.
225 
226     // Always attempt to re-initialize Child's Next value.
227     // Next must be non-0 to disambiguate it from Uninitialized.
228     child.MaybeInitNext();
229 
230     // Always clear the inherited Parent's next Value, i.e. the child's last path entry.
231     OverwriteNextValueFromParent(/*inout*/&child, BitStringChar{});
232 
233     // The state is now Initialized | Overflowed.
234     DCHECK_NE(kAssigned, child.GetState()) << child.GetBitString();
235     DCHECK_NE(kUninitialized, child.GetState()) << child.GetBitString();
236 
237     if (assign_next == false) {
238       child.DcheckInvariants();
239       return child;
240     }
241 
242     // Begin transition to >= Assigned.
243 
244     // Assign attempt.
245     if (HasNext() && !bitstring_and_of_.overflow_) {
246       BitStringChar next = GetNext();
247       if (next != next.MaximumValue()) {
248         // The parent's "next" value is now the child's latest path element.
249         OverwriteNextValueFromParent(/*inout*/&child, next);
250         // Update self next value, so that future CreateChild calls
251         // do not get the same path value.
252         SetNext(next + 1u);
253       } else {
254         child.MarkOverflowed();  // Too wide.
255       }
256     } else {
257       child.MarkOverflowed();  // Too deep, or parent was already overflowed.
258     }
259 
260     // The state is now Assigned | Overflowed.
261     DCHECK(child.GetState() == kAssigned || child.GetState() == kOverflowed);
262 
263     child.DcheckInvariants();
264     return child;
265   }
266 
267   // Get the current state (Uninitialized, Initialized, Assigned, or Overflowed).
268   // See the "SubtypeCheckInfo" documentation above which explains how a state is determined.
GetStateSubtypeCheckInfo269   State GetState() const {
270     if (bitstring_and_of_.overflow_) {
271       // Overflowed if and only if the OF bit was set.
272       return kOverflowed;
273     }
274 
275     if (GetBitString().IsEmpty()) {
276       // Empty bitstring (all 0s) -> uninitialized.
277       return kUninitialized;
278     }
279 
280     // Either Assigned or Initialized.
281     BitString path_to_root = GetPathToRoot();
282 
283     DCHECK_IMPLIES(HasNext(), GetNext() != 0u)
284         << "Expected (Assigned|Initialized) state to have >0 Next value: " << GetNext()
285         << " path: " << path_to_root;
286 
287     if (path_to_root.Length() == depth_) {
288       return kAssigned;
289     }
290 
291     return kInitialized;
292   }
293 
294   // Retrieve the path to root bitstring as a plain uintN_t value that is amenable to
295   // be used by a fast check "encoded_src & mask_target == encoded_target".
GetEncodedPathToRootSubtypeCheckInfo296   BitString::StorageType GetEncodedPathToRoot() const {
297     BitString::StorageType data = static_cast<BitString::StorageType>(GetPathToRoot());
298     // Bit strings are logically in the least-significant memory.
299     return data;
300   }
301 
302   // Retrieve the path to root bitstring mask as a plain uintN_t that is amenable to
303   // be used by a fast check "encoded_src & mask_target == encoded_target".
GetEncodedPathToRootMaskSubtypeCheckInfo304   BitString::StorageType GetEncodedPathToRootMask() const {
305     size_t num_bitchars = GetSafeDepth();
306     size_t bitlength = BitString::GetBitLengthTotalAtPosition(num_bitchars);
307     return MaskLeastSignificant<BitString::StorageType>(bitlength);
308   }
309 
310   // Get the "Next" bitchar, assuming that there is one to get.
GetNextSubtypeCheckInfo311   BitStringChar GetNext() const {
312     DCHECK(HasNext());
313     return GetBitString()[depth_];
314   }
315 
316   // Try to get the Next value, if there is one.
317   // Returns: Whether or not there was a Next value.
MaybeGetNextSubtypeCheckInfo318   bool MaybeGetNext(/*out*/BitStringChar* next) const {
319     DCHECK(next != nullptr);
320 
321     if (HasNext()) {
322       *next = GetBitString()[depth_];
323       return true;
324     }
325     return false;
326   }
327 
328  private:
329   // Constructor intended for testing. Runs all invariant checks.
SubtypeCheckInfoSubtypeCheckInfo330   SubtypeCheckInfo(BitString path_to_root, BitStringChar next, bool overflow, size_t depth) {
331     SubtypeCheckBits iod;
332     iod.bitstring_ = path_to_root;
333     iod.overflow_ = overflow;
334 
335     bitstring_and_of_ = iod;
336     depth_ = depth;
337 
338     // Len(Path-to-root) <= Depth.
339     DCHECK_GE(depth_, path_to_root.Length())
340         << "Path was too long for the depth, path: " << path_to_root;
341 
342     bool did_overlap = false;
343     if (HasNext()) {
344       if (kIsDebugBuild) {
345         did_overlap = (GetNext() != 0u);
346       }
347 
348       SetNext(next);
349 
350       DCHECK_EQ(next, GetNext());
351     }
352     // "Next" must be set before we can check the invariants.
353     DcheckInvariants();
354     DCHECK(!did_overlap)
355           << "Path to root overlapped with Next value, path: " << path_to_root;
356     DCHECK_EQ(path_to_root, GetPathToRoot());
357   }
358 
359   // Factory intended for testing. Skips DcheckInvariants.
MakeUncheckedSubtypeCheckInfo360   static SubtypeCheckInfo MakeUnchecked(BitString bitstring, bool overflow, size_t depth) {
361     SubtypeCheckBits iod;
362     iod.bitstring_ = bitstring;
363     iod.overflow_ = overflow;
364 
365     SubtypeCheckInfo io;
366     io.depth_ = depth;
367     io.bitstring_and_of_ = iod;
368 
369     return io;
370   }
371 
SetNextSubtypeCheckInfo372   void SetNext(BitStringChar next) {
373     DCHECK(HasNext());
374     BitString bs = GetBitString();
375     bs.SetAt(depth_, next);
376     SetBitString(bs);
377   }
378 
SetNextUncheckedSubtypeCheckInfo379   void SetNextUnchecked(BitStringChar next) {
380     BitString bs = GetBitString();
381     bs.SetAt(depth_, next);
382     SetBitStringUnchecked(bs);
383   }
384 
385   // If there is a next field, set it to 1.
MaybeInitNextSubtypeCheckInfo386   void MaybeInitNext() {
387     if (HasNext()) {
388       // Clearing out the "Next" value like this
389       // is often an intermediate operation which temporarily
390       // violates the invariants. Do not do the extra dchecks.
391       SetNextUnchecked(BitStringChar{});
392       SetNextUnchecked(GetNext()+1u);
393     }
394   }
395 
GetPathToRootSubtypeCheckInfo396   BitString GetPathToRoot() const {
397     size_t end = GetSafeDepth();
398     return GetBitString().Truncate(end);
399   }
400 
HasNextSubtypeCheckInfo401   bool HasNext() const {
402     return depth_ < BitString::kCapacity;
403   }
404 
MarkOverflowedSubtypeCheckInfo405   void MarkOverflowed() {
406     bitstring_and_of_.overflow_ = true;
407   }
408 
HasBitStringCharStorageSubtypeCheckInfo409   static constexpr bool HasBitStringCharStorage(size_t idx) {
410     return idx < BitString::kCapacity;
411   }
412 
GetSafeDepthSubtypeCheckInfo413   size_t GetSafeDepth() const {
414     return GetSafeDepth(depth_);
415   }
416 
417   // Get a "safe" depth, one that is truncated to the bitstring max capacity.
418   // Using a value larger than this will cause undefined behavior.
GetSafeDepthSubtypeCheckInfo419   static size_t GetSafeDepth(size_t depth) {
420     return std::min(depth, BitString::kCapacity);
421   }
422 
GetBitStringSubtypeCheckInfo423   BitString GetBitString() const {
424     return bitstring_and_of_.bitstring_;
425   }
426 
SetBitStringSubtypeCheckInfo427   void SetBitString(const BitString& val) {
428     SetBitStringUnchecked(val);
429     DcheckInvariants();
430   }
431 
SetBitStringUncheckedSubtypeCheckInfo432   void SetBitStringUnchecked(const BitString& val) {
433     bitstring_and_of_.bitstring_ = val;
434   }
435 
OverwriteNextValueFromParentSubtypeCheckInfo436   void OverwriteNextValueFromParent(/*inout*/SubtypeCheckInfo* child, BitStringChar value) const {
437     // Helper function for CreateChild.
438     if (HasNext()) {
439       // When we copied the "Next" value, it is now our
440       // last path component in the child.
441       // Always overwrite it with either a cleared value or the parent's Next value.
442       BitString bs = child->GetBitString();
443 
444       // Safe write. This.Next always occupies same slot as Child[Depth_].
445       DCHECK(child->HasBitStringCharStorage(depth_));
446 
447       bs.SetAt(depth_, value);
448 
449       // The child is temporarily in a bad state until it is fixed up further.
450       // Do not do the normal dchecks which do not allow transient badness.
451       child->SetBitStringUnchecked(bs);
452     }
453   }
454 
DcheckInvariantsSubtypeCheckInfo455   void DcheckInvariants() const {
456     if (kIsDebugBuild) {
457       CHECK_GE(GetSafeDepth(depth_ + 1u), GetBitString().Length())
458           << "Bitstring too long for depth, bitstring: " << GetBitString() << ", depth: " << depth_;
459 
460       BitString path_to_root = GetPathToRoot();
461 
462       // A 'null' (\0) character in path-to-root must be followed only
463       // by other null characters.
464       size_t i;
465       for (i = 0; i < BitString::kCapacity; ++i) {
466         BitStringChar bc = path_to_root[i];
467         if (bc == 0u) {
468           break;
469         }
470       }
471 
472       // All characters following a 0 must also be 0.
473       for (; i < BitString::kCapacity; ++i) {
474         BitStringChar bc = path_to_root[i];
475         if (bc != 0u) {
476           LOG(FATAL) << "Path to root had non-0s following 0s: " << path_to_root;
477         }
478       }
479 
480        // Trigger any dchecks in GetState.
481       (void)GetState();
482     }
483   }
484 
485   SubtypeCheckInfo() = default;
486   size_t depth_;
487   SubtypeCheckBits bitstring_and_of_;
488 
489   friend struct ::SubtypeCheckInfoTest;
490   friend std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io);
491 };
492 
493 // Prints the SubtypeCheckInfo::State, e.g. "kUnitialized".
494 inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo::State& state) {
495   switch (state) {
496     case SubtypeCheckInfo::kUninitialized:
497       os << "kUninitialized";
498       break;
499     case SubtypeCheckInfo::kInitialized:
500       os << "kInitialized";
501       break;
502     case SubtypeCheckInfo::kAssigned:
503       os << "kAssigned";
504       break;
505     case SubtypeCheckInfo::kOverflowed:
506       os << "kOverflowed";
507       break;
508     default:
509       os << "(Invalid SubtypeCheckInfo::State " << static_cast<int>(state) << ")";
510   }
511   return os;
512 }
513 
514 // Prints e.g. "SubtypeCheckInfo{BitString[1,2,3], depth: 3, of:1}"
515 inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io) {
516   os << "SubtypeCheckInfo{" << io.GetBitString() << ", "
517      << "depth: " << io.depth_ << ", of:" << io.bitstring_and_of_.overflow_ << "}";
518   return os;
519 }
520 
521 }  // namespace art
522 
523 #endif  // ART_RUNTIME_SUBTYPE_CHECK_INFO_H_
524