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