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 #ifndef PANDA_RUNTIME_MEM_RUNSLOTS_H
16 #define PANDA_RUNTIME_MEM_RUNSLOTS_H
17 
18 #include <array>
19 #include <cstddef>
20 
21 #include "libpandabase/macros.h"
22 #include "libpandabase/mem/mem.h"
23 #include "libpandabase/utils/asan_interface.h"
24 #include "libpandabase/utils/logger.h"
25 
26 namespace ark::mem {
27 
28 static constexpr size_t PAGES_IN_RUNSLOTS = 1;
29 static constexpr size_t RUNSLOTS_SIZE = PAGES_IN_RUNSLOTS * PAGE_SIZE;
30 static constexpr size_t RUNSLOTS_ALIGNMENT_IN_BYTES = PAGE_SIZE;
31 static constexpr size_t RUNSLOTS_ALIGNMENT = 10 + 2;  // Alignment for shift
32 static constexpr size_t RUNSLOTS_ALIGNMENT_MASK = (1UL << RUNSLOTS_ALIGNMENT) - 1;
33 static_assert((1UL << RUNSLOTS_ALIGNMENT) == RUNSLOTS_ALIGNMENT_IN_BYTES);
34 
35 class RunSlotsLockConfig {
36 public:
37     using CommonLock = os::memory::Mutex;
38     using DummyLock = os::memory::DummyLock;
39 };
40 
41 /**
42  * A class for free slots inside RunSlots object.
43  * Each free slot has a link to the next slot in RunSlots.
44  * If the link is equal to nullptr, then it is the last free slot.
45  */
46 class FreeSlot {
47 public:
GetNext()48     FreeSlot *GetNext()
49     {
50         return nextFree_;
51     }
SetNext(FreeSlot *next)52     void SetNext(FreeSlot *next)
53     {
54         nextFree_ = next;
55     }
56 
57 private:
58     FreeSlot *nextFree_ {nullptr};
59 };
60 /**
61  * The main class for RunSlots.
62  * Each RunSlots consumes RUNSLOTS_SIZE bytes of memory.
63  * RunSlots is divided into equal size slots which will be used for allocation.
64  * The RunSlots header is stored inside the first slot (or slots) of this RunSlots instance.
65  */
66 template <typename LockTypeT = RunSlotsLockConfig::CommonLock>
67 class RunSlots {
68 public:
69     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
70     ATTRIBUTE_NO_SANITIZE_ADDRESS
71     void Initialize(size_t slotSize, uintptr_t poolPointer, bool initializeLock);
72 
MaxSlotSize()73     static constexpr size_t MaxSlotSize()
74     {
75         return SlotToSize(SlotsSizes::SLOT_MAX_SIZE_BYTES);
76     }
77 
MinSlotSize()78     static constexpr size_t MinSlotSize()
79     {
80         return SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES);
81     }
82 
SlotSizesVariants()83     static constexpr size_t SlotSizesVariants()
84     {
85         return SlotToSize(SlotsSizes::SLOT_MAX_SIZE_BYTES_POWER_OF_TWO);
86     }
87 
88     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
89     ATTRIBUTE_NO_SANITIZE_ADDRESS
90     FreeSlot *PopFreeSlot();
91 
92     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
93     ATTRIBUTE_NO_SANITIZE_ADDRESS
94     void PushFreeSlot(FreeSlot *memSlot);
95 
96     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
97     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetPoolPointer()98     uintptr_t GetPoolPointer()
99     {
100         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
101         uintptr_t poolPointer = poolPointer_;
102         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
103         return poolPointer;
104     }
105 
106     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
107     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsEmpty()108     bool IsEmpty()
109     {
110         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
111         bool isEmpty = (usedSlots_ == 0);
112         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
113         return isEmpty;
114     }
115 
116     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
117     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsFull()118     bool IsFull()
119     {
120         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
121         bool isFull = (nextFree_ == nullptr) && (firstUninitializedSlotOffset_ == 0);
122         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
123         return isFull;
124     }
125 
126     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
127     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetNextRunSlots(RunSlots *runslots)128     void SetNextRunSlots(RunSlots *runslots)
129     {
130         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
131         nextRunslot_ = runslots;
132         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
133     }
134 
135     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
136     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetNextRunSlots()137     RunSlots *GetNextRunSlots()
138     {
139         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
140         RunSlots *next = nextRunslot_;
141         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
142         return next;
143     }
144 
145     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
146     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPrevRunSlots(RunSlots *runslots)147     void SetPrevRunSlots(RunSlots *runslots)
148     {
149         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
150         prevRunslot_ = runslots;
151         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
152     }
153 
154     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
155     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetPrevRunSlots()156     RunSlots *GetPrevRunSlots()
157     {
158         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
159         RunSlots *prev = prevRunslot_;
160         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
161         return prev;
162     }
163 
164     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
165     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetSlotsSize()166     size_t GetSlotsSize()
167     {
168         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
169         size_t size = slotSize_;
170         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
171         return size;
172     }
173 
ConvertToPowerOfTwoUnsafe(size_t size)174     static constexpr size_t ConvertToPowerOfTwoUnsafe(size_t size)
175     {
176         size_t i = SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES_POWER_OF_TWO);
177         size_t val = SlotToSize(SlotsSizes::SLOT_MIN_SIZE_BYTES);
178         while (size > val) {
179             i++;
180             val = val << 1UL;
181         }
182         return i;
183     }
184 
185     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
186     template <typename ObjectVisitor>
IterateOverOccupiedSlots(const ObjectVisitor &objectVisitor)187     ATTRIBUTE_NO_SANITIZE_ADDRESS void IterateOverOccupiedSlots(const ObjectVisitor &objectVisitor)
188     {
189         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
190         // NOTE(aemelenko): We can increase execution speed of this loops and do not count BitMapToSlot each time
191         for (size_t arrayIndex = 0; arrayIndex < BITMAP_ARRAY_SIZE; arrayIndex++) {
192             uint8_t byte = bitmap_[arrayIndex];
193             if (byte == 0x0) {
194                 continue;
195             }
196             for (size_t bit = 0; bit < (1U << BITS_IN_BYTE_POWER_OF_TWO); bit++) {
197                 if (byte & 0x1U) {
198                     objectVisitor(static_cast<ObjectHeader *>(static_cast<void *>(BitMapToSlot(arrayIndex, bit))));
199                 }
200                 byte = byte >> 1U;
201             }
202             // We must unpoison again, because we can poison header somewhere inside a visitor
203             ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
204         }
205         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
206     }
207 
208     /// @brief Check integraty of ROS allocator, return failure count.
VerifyRun()209     size_t VerifyRun()
210     {
211         return RunVerifier()(this);
212     }
213 
214     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
215     ATTRIBUTE_NO_SANITIZE_ADDRESS
216     bool IsLive(const ObjectHeader *obj) const;
217 
218     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
219     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetLock()220     LockTypeT *GetLock()
221     {
222         ASAN_UNPOISON_MEMORY_REGION(this, GetHeaderSize());
223         LockTypeT *lock = &lock_;
224         ASAN_POISON_MEMORY_REGION(this, GetHeaderSize());
225         return lock;
226     }
227 
228 private:
229     enum SlotsSizes : size_t {
230         SLOT_8_BYTES_POWER_OF_TWO = 3,
231         SLOT_16_BYTES_POWER_OF_TWO = 4,
232         SLOT_32_BYTES_POWER_OF_TWO = 5,
233         SLOT_64_BYTES_POWER_OF_TWO = 6,
234         SLOT_128_BYTES_POWER_OF_TWO = 7,
235         SLOT_256_BYTES_POWER_OF_TWO = 8,
236         SLOT_MAX_SIZE_BYTES_POWER_OF_TWO = SLOT_256_BYTES_POWER_OF_TWO,
237         SLOT_MIN_SIZE_BYTES_POWER_OF_TWO = SLOT_8_BYTES_POWER_OF_TWO,
238         SLOT_MAX_SIZE_BYTES = 1UL << SLOT_MAX_SIZE_BYTES_POWER_OF_TWO,
239         SLOT_MIN_SIZE_BYTES = 1UL << SLOT_MIN_SIZE_BYTES_POWER_OF_TWO,
240     };
241 
SlotToSize(SlotsSizes val)242     static constexpr size_t SlotToSize(SlotsSizes val)
243     {
244         return static_cast<size_t>(val);
245     }
246 
247     static constexpr size_t BITS_IN_BYTE_POWER_OF_TWO = 3U;
248     static constexpr size_t BITMAP_ARRAY_SIZE =
249         (RUNSLOTS_SIZE >> (SlotsSizes::SLOT_MIN_SIZE_BYTES_POWER_OF_TWO)) >> BITS_IN_BYTE_POWER_OF_TWO;
250 
GetHeaderSize()251     static size_t GetHeaderSize()
252     {
253         return sizeof(RunSlots);
254     }
255 
256     size_t ComputeFirstSlotOffset(size_t slotSize);
257 
258     void SetupSlots();
259 
260     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
261     ATTRIBUTE_NO_SANITIZE_ADDRESS
262     void MarkAsOccupied(const FreeSlot *slotMem);
263 
264     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
265     ATTRIBUTE_NO_SANITIZE_ADDRESS
266     void MarkAsFree(const FreeSlot *slotMem);
267 
268     FreeSlot *BitMapToSlot(size_t arrayIndex, size_t bit);
269 
270     class RunVerifier {
271     public:
272         RunVerifier() = default;
273         ~RunVerifier() = default;
274         NO_COPY_SEMANTIC(RunVerifier);
275         NO_MOVE_SEMANTIC(RunVerifier);
276 
277         size_t operator()(RunSlots *run);
278 
279     private:
280         size_t failCnt_ {0};
281     };
282 
283     // Use ATTRIBUTE_NO_SANITIZE_ADDRESS to prevent MT issues with POISON/UNPOISON
284     ATTRIBUTE_NO_SANITIZE_ADDRESS
285     void *PopUninitializedSlot();
286 
287     static_assert((RUNSLOTS_SIZE / SlotsSizes::SLOT_MIN_SIZE_BYTES) <=
288                   std::numeric_limits<uint16_t>::max());                                     // used_slots_
289     static_assert(SlotsSizes::SLOT_MAX_SIZE_BYTES <= std::numeric_limits<uint16_t>::max());  // slot_size_
290     static_assert(RUNSLOTS_SIZE <= std::numeric_limits<uint16_t>::max());  // first_uninitialized_slot_offset_
291     uint16_t usedSlots_ {0};
292     uint16_t slotSize_ {0};
293     uint16_t firstUninitializedSlotOffset_ {0};  // If equal to zero - we don't have uninitialized slots
294     uintptr_t poolPointer_ {0};
295     FreeSlot *nextFree_ {nullptr};
296     RunSlots *nextRunslot_ {nullptr};
297     RunSlots *prevRunslot_ {nullptr};
298     LockTypeT lock_;
299 
300     // Bitmap for identifying live objects in this RunSlot
301     std::array<uint8_t, BITMAP_ARRAY_SIZE> bitmap_ {};
302 };
303 
304 static_assert(RunSlots<>::MinSlotSize() >= sizeof(uintptr_t));
305 
306 }  // namespace ark::mem
307 
308 #endif  // PANDA_RUNTIME_MEM_RUNSLOTS_H
309