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 #include "runtime/mem/gc/heap-space-misc/crossing_map.h"
17
18 #include <cstring>
19
20 namespace panda::mem {
21
22 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
23 #define LOG_CROSSING_MAP(level) LOG(level, GC) << "CrossingMap: "
24
CrossingMap(InternalAllocatorPtr internal_allocator,uintptr_t start_addr,size_t size)25 CrossingMap::CrossingMap(InternalAllocatorPtr internal_allocator, uintptr_t start_addr, size_t size)
26 : start_addr_(start_addr), internal_allocator_(internal_allocator)
27 {
28 ASSERT(size % CROSSING_MAP_GRANULARITY == 0);
29 map_elements_count_ = size / CROSSING_MAP_GRANULARITY;
30 static_array_elements_count_ =
31 AlignUp(size, CROSSING_MAP_STATIC_ARRAY_GRANULARITY) / CROSSING_MAP_STATIC_ARRAY_GRANULARITY;
32 ASSERT((start_addr & (PAGE_SIZE - 1)) == 0U);
33 LOG_CROSSING_MAP(DEBUG) << "Create CrossingMap with start_addr 0x" << std::hex << start_addr_;
34 }
35
~CrossingMap()36 CrossingMap::~CrossingMap()
37 {
38 ASSERT(static_array_ == nullptr);
39 }
40
Initialize()41 void CrossingMap::Initialize()
42 {
43 if (static_array_ != nullptr) {
44 LOG_CROSSING_MAP(FATAL) << "Try to initialize already initialized CrossingMap";
45 }
46 size_t static_array_size_in_bytes = static_array_elements_count_ * sizeof(StaticArrayPtr);
47 static_array_ = static_cast<StaticArrayPtr>(internal_allocator_->Alloc(static_array_size_in_bytes));
48 ASSERT(static_array_ != nullptr);
49 for (size_t i = 0; i < static_array_elements_count_; i++) {
50 SetStaticArrayElement(i, nullptr);
51 }
52 }
53
Destroy()54 void CrossingMap::Destroy()
55 {
56 for (size_t i = 0; i < static_array_elements_count_; i++) {
57 void *element = GetStaticArrayElement(i);
58 if (element != nullptr) {
59 internal_allocator_->Free(element);
60 }
61 }
62 ASSERT(static_array_ != nullptr);
63 internal_allocator_->Free(static_array_);
64 static_array_ = nullptr;
65 }
66
AddObject(const void * obj_addr,size_t obj_size)67 void CrossingMap::AddObject(const void *obj_addr, size_t obj_size)
68 {
69 LOG_CROSSING_MAP(DEBUG) << "Try to AddObject with addr " << std::hex << obj_addr << " and size " << std::dec
70 << obj_size;
71 size_t first_map_num = GetMapNumFromAddr(obj_addr);
72 size_t obj_offset = GetOffsetFromAddr(obj_addr);
73 CrossingMapElement::STATE state = GetMapElement(first_map_num)->GetState();
74 switch (state) {
75 case CrossingMapElement::STATE::STATE_UNINITIALIZED:
76 LOG_CROSSING_MAP(DEBUG) << "AddObject - state of the map num " << first_map_num
77 << " wasn't INITIALIZED. Initialize it with offset " << obj_offset;
78 GetMapElement(first_map_num)->SetInitialized(obj_offset);
79 break;
80 case CrossingMapElement::STATE::STATE_CROSSED_BORDER:
81 LOG_CROSSING_MAP(DEBUG) << "AddObject - state of the map num " << first_map_num
82 << " was CROSSED BORDER. Initialize it with offset " << obj_offset;
83 GetMapElement(first_map_num)->SetInitializedAndCrossedBorder(obj_offset);
84 break;
85 case CrossingMapElement::STATE::STATE_INITIALIZED_AND_CROSSED_BORDERS:
86 if (GetMapElement(first_map_num)->GetOffset() > obj_offset) {
87 LOG_CROSSING_MAP(DEBUG) << "AddObject - state of the map num " << first_map_num
88 << " is INITIALIZED and CROSSED BORDERS, but this object is the first in it."
89 << " Initialize it with new offset " << obj_offset;
90 GetMapElement(first_map_num)->SetInitializedAndCrossedBorder(obj_offset);
91 }
92 break;
93 case CrossingMapElement::STATE::STATE_INITIALIZED:
94 if (GetMapElement(first_map_num)->GetOffset() > obj_offset) {
95 LOG_CROSSING_MAP(DEBUG) << "AddObject - state of the map num " << first_map_num
96 << " is INITIALIZED, but this object is the first in it."
97 << " Initialize it with new offset " << obj_offset;
98 GetMapElement(first_map_num)->SetInitialized(obj_offset);
99 }
100 break;
101 default:
102 LOG_CROSSING_MAP(FATAL) << "Unknown state!";
103 }
104 if constexpr (CROSSING_MAP_MANAGE_CROSSED_BORDER) {
105 void *last_obj_byte = ToVoidPtr(ToUintPtr(obj_addr) + obj_size - 1U);
106 size_t final_map_num = GetMapNumFromAddr(last_obj_byte);
107 if (final_map_num != first_map_num) {
108 UpdateCrossedBorderOnAdding(first_map_num + 1U, final_map_num);
109 }
110 }
111 }
112
UpdateCrossedBorderOnAdding(const size_t first_crossed_border_map,const size_t last_crossed_border_map)113 void CrossingMap::UpdateCrossedBorderOnAdding(const size_t first_crossed_border_map,
114 const size_t last_crossed_border_map)
115 {
116 ASSERT(last_crossed_border_map >= first_crossed_border_map);
117 // Iterate over maps which are fully covered by this object
118 // i.e. from second to last minus one map
119 size_t map_offset = 1U;
120 for (size_t i = first_crossed_border_map; i + 1U <= last_crossed_border_map; i++) {
121 LOG_CROSSING_MAP(DEBUG) << "AddObject - set CROSSED_BORDER to map num " << i << " with offset " << map_offset;
122 GetMapElement(i)->SetCrossedBorder(map_offset);
123 // If map_offset exceeds the limit, we will set max value to each map after that.
124 // When we want to find the element, which crosses the borders of a map,
125 // we will iterate before we meet a map with non-CROSSED_BORDER state.
126 if (map_offset < CrossingMapElement::GetMaxOffsetValue()) {
127 map_offset++;
128 }
129 }
130 // Set up last map:
131 switch (GetMapElement(last_crossed_border_map)->GetState()) {
132 case CrossingMapElement::STATE::STATE_UNINITIALIZED:
133 GetMapElement(last_crossed_border_map)->SetCrossedBorder(map_offset);
134 break;
135 case CrossingMapElement::STATE::STATE_INITIALIZED:
136 GetMapElement(last_crossed_border_map)
137 ->SetInitializedAndCrossedBorder(GetMapElement(last_crossed_border_map)->GetOffset());
138 break;
139 default:
140 LOG_CROSSING_MAP(FATAL) << "Unknown state!";
141 }
142 LOG_CROSSING_MAP(DEBUG) << "AddObject - set CROSSED_BORDER or INITIALIZED_AND_CROSSED_BORDERS to final map num "
143 << last_crossed_border_map << " with offset " << map_offset;
144 }
145
RemoveObject(const void * obj_addr,size_t obj_size,const void * next_obj_addr,const void * prev_obj_addr,size_t prev_obj_size)146 void CrossingMap::RemoveObject(const void *obj_addr, size_t obj_size, const void *next_obj_addr,
147 const void *prev_obj_addr, size_t prev_obj_size)
148 {
149 LOG_CROSSING_MAP(DEBUG) << "Try to RemoveObject with addr " << std::hex << obj_addr << " and size " << std::dec
150 << obj_size;
151 ASSERT(obj_addr != nullptr);
152 // Let's set all maps, which are related to this object, as uninitialized
153 size_t first_map_num = GetMapNumFromAddr(obj_addr);
154 size_t obj_offset = GetOffsetFromAddr(obj_addr);
155 ASSERT(GetMapElement(first_map_num)->GetState() == CrossingMapElement::STATE::STATE_INITIALIZED ||
156 GetMapElement(first_map_num)->GetState() ==
157 CrossingMapElement::STATE::STATE_INITIALIZED_AND_CROSSED_BORDERS);
158 // We need to check that first object in this map is a pointer to this object
159 size_t map_offset = GetMapElement(first_map_num)->GetOffset();
160 ASSERT(map_offset <= obj_offset);
161 if (map_offset == obj_offset) {
162 LOG_CROSSING_MAP(DEBUG) << "RemoveObject - it is the first object in map num " << first_map_num
163 << ". So, just uninitialize it.";
164 GetMapElement(first_map_num)->SetUninitialized();
165 }
166
167 if constexpr (CROSSING_MAP_MANAGE_CROSSED_BORDER) {
168 void *last_obj_byte = ToVoidPtr(ToUintPtr(obj_addr) + obj_size - 1U);
169 size_t final_map_num = GetMapNumFromAddr(last_obj_byte);
170 ASSERT(final_map_num >= first_map_num);
171 // Set all pages, which fully covered by this object, as Uninitialized;
172 // and for last map (we will set it up correctly later)
173 for (size_t i = first_map_num + 1U; i <= final_map_num; i++) {
174 LOG_CROSSING_MAP(DEBUG) << "RemoveObject - Set uninitialized to map num " << i;
175 GetMapElement(i)->SetUninitialized();
176 }
177 }
178
179 // Set up map for next element (because we could set it as uninitialized)
180 if (next_obj_addr != nullptr) {
181 size_t next_obj_map_num = GetMapNumFromAddr(next_obj_addr);
182 if (GetMapElement(next_obj_map_num)->GetState() == CrossingMapElement::STATE::STATE_UNINITIALIZED) {
183 LOG_CROSSING_MAP(DEBUG) << "RemoveObject - Set up map " << next_obj_map_num << " for next object with addr "
184 << std::hex << next_obj_addr << " as INITIALIZED with offset " << std::dec
185 << GetOffsetFromAddr(next_obj_addr);
186 GetMapElement(next_obj_map_num)->SetInitialized(GetOffsetFromAddr(next_obj_addr));
187 }
188 }
189 // Set up map for last byte of prev element (because it can cross the page borders)
190 if constexpr (CROSSING_MAP_MANAGE_CROSSED_BORDER) {
191 if (prev_obj_addr != nullptr) {
192 void *prev_obj_last_byte = ToVoidPtr(ToUintPtr(prev_obj_addr) + prev_obj_size - 1U);
193 size_t prev_obj_last_map = GetMapNumFromAddr(prev_obj_last_byte);
194 size_t prev_obj_first_map = GetMapNumFromAddr(prev_obj_addr);
195 if ((prev_obj_last_map == first_map_num) && (prev_obj_first_map != first_map_num)) {
196 UpdateCrossedBorderOnRemoving(prev_obj_last_map);
197 }
198 }
199 }
200 }
201
UpdateCrossedBorderOnRemoving(const size_t crossed_border_map)202 void CrossingMap::UpdateCrossedBorderOnRemoving(const size_t crossed_border_map)
203 {
204 switch (GetMapElement(crossed_border_map)->GetState()) {
205 case CrossingMapElement::STATE::STATE_UNINITIALIZED: {
206 // This situation can only happen when removed object was the first object in a corresponding page map
207 // and next_obj_addr is not located in the same page map.
208 ASSERT(crossed_border_map > 0);
209 // Calculate offset for crossed border map
210 size_t offset = GetMapElement(crossed_border_map - 1U)->GetOffset();
211 CrossingMapElement::STATE prev_map_state = GetMapElement(crossed_border_map - 1U)->GetState();
212 switch (prev_map_state) {
213 case CrossingMapElement::STATE::STATE_INITIALIZED:
214 case CrossingMapElement::STATE::STATE_INITIALIZED_AND_CROSSED_BORDERS:
215 offset = 1U;
216 break;
217 case CrossingMapElement::STATE::STATE_CROSSED_BORDER:
218 if (offset < CrossingMapElement::GetMaxOffsetValue()) {
219 offset++;
220 }
221 break;
222 default:
223 LOG_CROSSING_MAP(FATAL) << "Incorrect state!";
224 }
225 GetMapElement(crossed_border_map)->SetCrossedBorder(offset);
226 break;
227 }
228 case CrossingMapElement::STATE::STATE_INITIALIZED: {
229 GetMapElement(crossed_border_map)
230 ->SetInitializedAndCrossedBorder(GetMapElement(crossed_border_map)->GetOffset());
231 break;
232 }
233 default:
234 LOG_CROSSING_MAP(FATAL) << "Incorrect state!";
235 }
236 }
237
FindFirstObject(const void * start_addr,const void * end_addr)238 void *CrossingMap::FindFirstObject(const void *start_addr, const void *end_addr)
239 {
240 LOG_CROSSING_MAP(DEBUG) << "FindFirstObject for interval [" << std::hex << start_addr << ", " << end_addr << "]";
241 size_t first_map = GetMapNumFromAddr(start_addr);
242 size_t last_map = GetMapNumFromAddr(end_addr);
243 LOG_CROSSING_MAP(DEBUG) << "FindFirstObject for maps [" << std::dec << first_map << ", " << last_map << "]";
244 for (size_t i = first_map; i <= last_map; i++) {
245 void *obj_offset = FindObjInMap(i);
246 if (obj_offset != nullptr) {
247 LOG_CROSSING_MAP(DEBUG) << "Found first object in this interval with addr " << std::hex << obj_offset;
248 return obj_offset;
249 }
250 }
251 LOG_CROSSING_MAP(DEBUG) << "There is no object in this interval, return nullptr";
252 return nullptr;
253 }
254
InitializeCrossingMapForMemory(const void * start_addr,size_t size)255 void CrossingMap::InitializeCrossingMapForMemory(const void *start_addr, size_t size)
256 {
257 LOG_CROSSING_MAP(DEBUG) << "InitializeCrossingMapForMemory for addr " << std::hex << start_addr << " with size "
258 << size;
259 size_t start_map = GetStaticArrayNumFromAddr(start_addr);
260 size_t end_map = GetStaticArrayNumFromAddr(ToVoidPtr(ToUintPtr(start_addr) + size - 1));
261 ASSERT(start_map <= end_map);
262 size_t static_map_size_in_bytes = CROSSING_MAP_COUNT_IN_STATIC_ARRAY_ELEMENT * sizeof(CROSSING_MAP_TYPE);
263 for (size_t i = start_map; i <= end_map; i++) {
264 ASSERT(GetStaticArrayElement(i) == nullptr);
265 void *mem = internal_allocator_->Alloc(static_map_size_in_bytes);
266 memset_s(mem, static_map_size_in_bytes, 0x0, static_map_size_in_bytes);
267 SetStaticArrayElement(i, static_cast<CrossingMapElement *>(mem));
268 ASSERT(GetStaticArrayElement(i) != nullptr);
269 }
270 }
271
RemoveCrossingMapForMemory(const void * start_addr,size_t size)272 void CrossingMap::RemoveCrossingMapForMemory(const void *start_addr, size_t size)
273 {
274 LOG_CROSSING_MAP(DEBUG) << "RemoveCrossingMapForMemory for addr " << std::hex << start_addr << " with size "
275 << size;
276 size_t start_map = GetStaticArrayNumFromAddr(start_addr);
277 size_t end_map = GetStaticArrayNumFromAddr(ToVoidPtr(ToUintPtr(start_addr) + size - 1));
278 ASSERT(start_map <= end_map);
279 for (size_t i = start_map; i <= end_map; i++) {
280 ASSERT(GetStaticArrayElement(i) != nullptr);
281 internal_allocator_->Free(GetStaticArrayElement(i));
282 SetStaticArrayElement(i, nullptr);
283 }
284 }
285
FindObjInMap(size_t map_num)286 void *CrossingMap::FindObjInMap(size_t map_num)
287 {
288 LOG_CROSSING_MAP(DEBUG) << "Try to find object for map_num - " << map_num;
289 CrossingMapElement::STATE state = GetMapElement(map_num)->GetState();
290 switch (state) {
291 case CrossingMapElement::STATE::STATE_UNINITIALIZED:
292 LOG_CROSSING_MAP(DEBUG) << "STATE_UNINITIALIZED, return nullptr";
293 return nullptr;
294 case CrossingMapElement::STATE::STATE_INITIALIZED:
295 LOG_CROSSING_MAP(DEBUG) << "STATE_INITIALIZED, obj addr = " << std::hex
296 << GetAddrFromOffset(map_num, GetMapElement(map_num)->GetOffset());
297 return GetAddrFromOffset(map_num, GetMapElement(map_num)->GetOffset());
298 case CrossingMapElement::STATE::STATE_INITIALIZED_AND_CROSSED_BORDERS: {
299 LOG_CROSSING_MAP(DEBUG)
300 << "STATE_INITIALIZED_AND_CROSSED_BORDERS, try to find object which crosses the borders";
301 ASSERT(map_num > 0);
302 size_t current_map = map_num - 1;
303 while (GetMapElement(current_map)->GetState() == CrossingMapElement::STATE::STATE_CROSSED_BORDER) {
304 ASSERT(current_map >= GetMapElement(current_map)->GetOffset());
305 current_map = current_map - GetMapElement(current_map)->GetOffset();
306 }
307 ASSERT(GetMapElement(current_map)->GetState() != CrossingMapElement::STATE::STATE_UNINITIALIZED);
308 LOG_CROSSING_MAP(DEBUG) << "Found object in map " << current_map << " with object addr = " << std::hex
309 << GetAddrFromOffset(current_map, GetMapElement(current_map)->GetOffset());
310 return GetAddrFromOffset(current_map, GetMapElement(current_map)->GetOffset());
311 }
312 case CrossingMapElement::STATE::STATE_CROSSED_BORDER: {
313 LOG_CROSSING_MAP(DEBUG) << "STATE_CROSSED_BORDER, try to find object which crosses the borders";
314 ASSERT(map_num >= GetMapElement(map_num)->GetOffset());
315 size_t current_map = map_num - GetMapElement(map_num)->GetOffset();
316 while (GetMapElement(current_map)->GetState() == CrossingMapElement::STATE::STATE_CROSSED_BORDER) {
317 ASSERT(current_map >= GetMapElement(current_map)->GetOffset());
318 current_map = current_map - GetMapElement(current_map)->GetOffset();
319 }
320 ASSERT(GetMapElement(current_map)->GetState() != CrossingMapElement::STATE::STATE_UNINITIALIZED);
321 LOG_CROSSING_MAP(DEBUG) << "Found object in map " << current_map << " with object addr = " << std::hex
322 << GetAddrFromOffset(current_map, GetMapElement(current_map)->GetOffset());
323 return GetAddrFromOffset(current_map, GetMapElement(current_map)->GetOffset());
324 }
325 default:
326 LOG_CROSSING_MAP(ERROR) << "Undefined map state";
327 return nullptr;
328 }
329 }
330
331 } // namespace panda::mem
332