1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef LIBPANDABASE_MEM_GC_BARRIER_H
17 #define LIBPANDABASE_MEM_GC_BARRIER_H
18
19 #include "utils/bit_field.h"
20
21 #include <atomic>
22 #include <cstdint>
23 #include <functional>
24 #include <variant>
25
26 namespace panda::mem {
27
28 /**
29 * Represents Pre and Post barrier
30 */
31 enum BarrierPosition : uint8_t {
32 BARRIER_POSITION_PRE = 0x1, // Should be inserted before each store/load when reference stored/loaded
33 BARRIER_POSITION_POST = 0x0, // Should be inserted after each store/load when reference stored/loaded
34 };
35
36 /**
37 * Indicates if barrier for store or load
38 */
39 enum BarrierActionType : uint8_t {
40 WRITE_BARRIER = 0x1, // Should be used around store
41 READ_BARRIER = 0x0, // Should be used around load
42 };
43
44 namespace internal {
45 constexpr uint8_t BARRIER_POS_OFFSET = 0U; // offset in bits for encoding position of barrier(pre or post)
46 constexpr uint8_t BARRIER_WRB_FLAG_OFFSET = 1U; // offset in bits for WRB flag
47 } // namespace internal
48
EncodeBarrierType(uint8_t value,BarrierPosition position,BarrierActionType action_type)49 constexpr uint8_t EncodeBarrierType(uint8_t value, BarrierPosition position, BarrierActionType action_type)
50 {
51 // NOLINTNEXTLINE(hicpp-signed-bitwise)
52 return (value << 2U) | (position << internal::BARRIER_POS_OFFSET) |
53 (action_type << internal::BARRIER_WRB_FLAG_OFFSET);
54 }
55
56 /**
57 * Should help to encode barrier for the compiler.
58 * PreWrite barrier can be used for avoiding lost object problem.
59 * PostWrite barrier used for tracking intergenerational or interregion references
60 */
61 enum BarrierType : uint8_t {
62 PRE_WRB_NONE = EncodeBarrierType(1U, BarrierPosition::BARRIER_POSITION_PRE, BarrierActionType::WRITE_BARRIER),
63 PRE_RB_NONE = EncodeBarrierType(1U, BarrierPosition::BARRIER_POSITION_PRE, BarrierActionType::READ_BARRIER),
64 POST_WRB_NONE = EncodeBarrierType(1U, BarrierPosition::BARRIER_POSITION_POST, BarrierActionType::WRITE_BARRIER),
65 POST_RB_NONE = EncodeBarrierType(1U, BarrierPosition::BARRIER_POSITION_POST, BarrierActionType::READ_BARRIER),
66 /**
67 * Pre barrier for SATB.
68 * Pseudocode:
69 * load CONCURRENT_MARKING_ADDR -> concurrent_marking
70 * if (UNLIKELY(concurrent_marking)) {
71 * load obj.field -> pre_val // note: if store volatile - we need to have volatile load here
72 * if (pre_val != nullptr) {
73 * call STORE_IN_BUFF_TO_MARK_FUNC(pre_val);
74 * }
75 * }
76 * store obj.field <- new_val // STORE for which barrier generated
77 *
78 * Runtime should provide these parameters:
79 * CONCURRENT_MARKING_ADDR - address of bool flag which indicates that we have concurrent marking on
80 * STORE_IN_BUFF_TO_MARK_FUNC - address of function to store replaced reference
81 */
82 PRE_SATB_BARRIER = EncodeBarrierType(2U, BarrierPosition::BARRIER_POSITION_PRE, BarrierActionType::WRITE_BARRIER),
83 /**
84 * Post barrier. Intergenerational barrier for GCs with explicit continuous young gen space. Unconditional.
85 * Can be fully encoded by compiler
86 * Pseudocode:
87 * store obj.field <- new_val // STORE for which barrier generated
88 * load AddressOf(MIN_ADDR) -> min_addr
89 * load AddressOf(CARD_TABLE_ADDR) -> card_table_addr
90 * card_index = (AddressOf(obj) - min_addr) >> CARD_BITS // shift right
91 * card_addr = card_table_addr + card_index
92 * store card_addr <- DIRTY_VAL
93 *
94 * Runtime should provide these parameters:
95 * MIN_ADDR - minimal address used by runtime (it is required only to support 64-bit addresses)
96 * CARD_TABLE_ADDR - address of the start of card table raw data array
97 * CARD_BITS - how many bits covered by one card (probably it will be a literal)
98 * DIRTY_VAL - some literal representing dirty card
99 *
100 * Note if store if to expensive on the architecture(for example in multithreading environment) -
101 * consider to create conditional barrier, ie check that card is not dirty before store
102 */
103 POST_INTERGENERATIONAL_BARRIER =
104 EncodeBarrierType(3U, BarrierPosition::BARRIER_POSITION_POST, BarrierActionType::WRITE_BARRIER),
105 /**
106 * Inter-region barrier. For GCs without explicit continuous young gen space.
107 * Pseudocode:
108 * store obj.field <- new_val // STORE for which barrier generated
109 * // Check if new_val is nullptr first - then we don't need a barrier
110 * if (new_val == null) {
111 * return
112 * }
113 * // Check if new_val and address of field is in different regions
114 * // (each region contain 2^REGION_SIZE_BITS and aligned with 2^REGION_SIZE_BITS bytes)
115 * if ((AddressOf(obj) XOR AddressOf(new_val)) >> REGION_SIZE_BITS) != 0) {
116 * call UPDATE_CARD_FUNC(obj, new_val);
117 * }
118 *
119 * Runtime should provide these parameters:
120 * REGION_SIZE_BITS - log2 of the size of region
121 * UPDATE_CARD_FUNC - function which updates card corresponding to the obj.field
122 */
123 POST_INTERREGION_BARRIER =
124 EncodeBarrierType(4U, BarrierPosition::BARRIER_POSITION_POST, BarrierActionType::WRITE_BARRIER),
125 /* Note: cosider two-level card table for pre-barrier */
126 };
127
IsPreBarrier(BarrierType barrier_type)128 constexpr bool IsPreBarrier(BarrierType barrier_type)
129 {
130 return BitField<uint8_t, internal::BARRIER_POS_OFFSET, 1>::Get(barrier_type) ==
131 BarrierPosition::BARRIER_POSITION_PRE;
132 }
133
IsPostBarrier(BarrierType barrier_type)134 constexpr bool IsPostBarrier(BarrierType barrier_type)
135 {
136 return BitField<uint8_t, internal::BARRIER_POS_OFFSET, 1>::Get(barrier_type) ==
137 BarrierPosition::BARRIER_POSITION_POST;
138 }
139
IsWriteBarrier(BarrierType barrier_type)140 constexpr bool IsWriteBarrier(BarrierType barrier_type)
141 {
142 return BitField<uint8_t, internal::BARRIER_WRB_FLAG_OFFSET, 1>::Get(barrier_type) ==
143 BarrierActionType::WRITE_BARRIER;
144 }
145
IsReadBarrier(BarrierType barrier_type)146 constexpr bool IsReadBarrier(BarrierType barrier_type)
147 {
148 return BitField<uint8_t, internal::BARRIER_WRB_FLAG_OFFSET, 1>::Get(barrier_type) ==
149 BarrierActionType::READ_BARRIER;
150 }
151
152 static_assert(IsPreBarrier(BarrierType::PRE_SATB_BARRIER));
153 static_assert(IsWriteBarrier(BarrierType::PRE_SATB_BARRIER));
154 static_assert(IsPostBarrier(BarrierType::POST_INTERGENERATIONAL_BARRIER));
155 static_assert(IsWriteBarrier(BarrierType::POST_INTERGENERATIONAL_BARRIER));
156 static_assert(IsPostBarrier(BarrierType::POST_INTERREGION_BARRIER));
157 static_assert(IsWriteBarrier(BarrierType::POST_INTERREGION_BARRIER));
158
IsEmptyBarrier(BarrierType barrier_type)159 constexpr bool IsEmptyBarrier(BarrierType barrier_type)
160 {
161 return (barrier_type == BarrierType::PRE_WRB_NONE) || (barrier_type == BarrierType::POST_WRB_NONE) ||
162 (barrier_type == BarrierType::PRE_RB_NONE) || (barrier_type == BarrierType::POST_RB_NONE);
163 }
164
165 using objRefProcessFunc = void (*)(void *);
166 using objTwoRefProcessFunc = void (*)(const void *, const void *);
167
168 enum class BarrierOperandType {
169 ADDRESS = 0, // just an address (void*)
170 BOOL_ADDRESS, // contains address of bool value (bool*)
171 UINT8_ADDRESS, // contains address of uint8_t value
172 FUNC_WITH_OBJ_REF_ADDRESS, // contains address of function with this sig: void foo(void* );
173 UINT8_LITERAL, // contains uint8_t value
174 FUNC_WITH_TWO_OBJ_REF_ADDRESSES, // contains address of function with this sig: void foo(void* , void* );
175 };
176
177 using BarrierOperandValue =
178 std::variant<void *, bool *, std::atomic<bool> *, uint8_t *, objRefProcessFunc, uint8_t, objTwoRefProcessFunc>;
179
180 class BarrierOperand {
181 public:
182 // NOLINTNEXTLINE(modernize-pass-by-value)
BarrierOperand(BarrierOperandType barrier_operand_type,BarrierOperandValue barrier_operand_value)183 BarrierOperand(BarrierOperandType barrier_operand_type, BarrierOperandValue barrier_operand_value)
184 : barrier_operand_type_(barrier_operand_type), barrier_operand_value_(barrier_operand_value)
185 {
186 }
187
GetType()188 inline BarrierOperandType GetType() const
189 {
190 return barrier_operand_type_;
191 }
192
GetValue()193 inline BarrierOperandValue GetValue() const
194 {
195 return barrier_operand_value_;
196 }
197
198 virtual ~BarrierOperand() = default;
199
200 DEFAULT_COPY_SEMANTIC(BarrierOperand);
201 DEFAULT_MOVE_SEMANTIC(BarrierOperand);
202
203 private:
204 BarrierOperandType barrier_operand_type_;
205 BarrierOperandValue barrier_operand_value_;
206 };
207
208 } // namespace panda::mem
209
210 #endif // LIBPANDABASE_MEM_GC_BARRIER_H
211