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