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_BITS_H_
18 #define ART_RUNTIME_SUBTYPE_CHECK_BITS_H_
19 
20 #include "base/bit_string.h"
21 #include "base/bit_struct.h"
22 #include "base/bit_utils.h"
23 
24 namespace art {
25 
26 /**
27  * The SubtypeCheckBits memory layout (in bits):
28  *
29  *   1 bit       Variable
30  *     |             |
31  *     v             v     <---- up to 23 bits ---->
32  *
33  *  +----+-----------+--------+-------------------------+
34  *  |    |                  Bitstring                   |
35  *  +    +-----------+--------+-------------------------+
36  *  | OF | (unused)  |  Next  |      Path To Root       |
37  *  +    |           |--------+----+----------+----+----+
38  *  |    | (0....0)  |        |    |   ...    |    |    |
39  *  +----+-----------+--------+----+----------+----+----+
40  * MSB (most significant bit)                          LSB
41  *
42  * The bitstring takes up to 23 bits; anything exceeding that is truncated:
43  * - Path To Root is a list of chars, encoded as a BitString:
44  *     starting at the root (in LSB), each character is a sibling index unique to the parent,
45  *   Paths longer than BitString::kCapacity are truncated to fit within the BitString.
46  * - Next is a single BitStringChar (immediatelly following Path To Root)
47  *     When new children are assigned paths, they get allocated the parent's Next value.
48  *     The next value is subsequently incremented.
49  *
50  * The exact bit position of (unused) is variable-length:
51  * In the cases that the "Path To Root" + "Next" does not fill up the entire
52  * BitString capacity, the remaining bits are (unused) and left as 0s.
53  *
54  * There is also an additional "OF" (overflow) field to indicate that the
55  * PathToRoot has been truncated.
56  *
57  * See subtype_check.h and subtype_check_info.h for more details.
58  */
59 BITSTRUCT_DEFINE_START(SubtypeCheckBits, /*size=*/ BitString::BitStructSizeOf() + 1u)
60   BitStructField<BitString, /*lsb=*/ 0> bitstring_;
61   BitStructUint</*lsb=*/ BitString::BitStructSizeOf(), /*width=*/ 1> overflow_;
62 BITSTRUCT_DEFINE_END(SubtypeCheckBits);
63 
64 }  // namespace art
65 
66 #endif  // ART_RUNTIME_SUBTYPE_CHECK_BITS_H_
67