• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #ifndef PANDA_MEM_FREELIST_H
16 #define PANDA_MEM_FREELIST_H
17 
18 #include <cstddef>
19 #include <cstdint>
20 #include <limits>
21 
22 #include "libpandabase/mem/mem.h"
23 #include "libpandabase/utils/asan_interface.h"
24 
25 namespace panda::mem::freelist {
26 
27 class MemoryBlockHeader {
28 public:
29     ATTRIBUTE_NO_SANITIZE_ADDRESS
Initialize(size_t size,MemoryBlockHeader * prev_header)30     void Initialize(size_t size, MemoryBlockHeader *prev_header)
31     {
32         ASSERT((std::numeric_limits<size_t>::max() >> STATUS_BITS_SIZE) >= size);
33         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
34         prev_header_ = prev_header;
35         size_ = size << STATUS_BITS_SIZE;
36         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
37     }
38 
39     // Is this memory block used somewhere or not (i.e. it is free)
40     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsUsed()41     bool IsUsed()
42     {
43         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
44         bool used = !((size_ & USED_BIT_MASK_IN_PLACE) == 0x0);
45         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
46         return used;
47     }
48 
49     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetUsed()50     void SetUsed()
51     {
52         ASSERT(!IsUsed());
53         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
54         size_ = size_ | USED_BIT_MASK_IN_PLACE;
55         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
56     }
57 
58     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetUnused()59     void SetUnused()
60     {
61         ASSERT(IsUsed());
62         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
63         size_ = size_ & (~USED_BIT_MASK_IN_PLACE);
64         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
65     }
66 
67     // Is this memory block the last in the memory pool
68     // (i.e. we can't compute next memory block via size)
69     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsLastBlockInPool()70     bool IsLastBlockInPool()
71     {
72         ASSERT(!IsPaddingHeader());
73         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
74         bool is_last_block_in_pool = !((size_ & LAST_BLOCK_IN_POOL_BIT_MASK_IN_PLACE) == 0x0);
75         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
76         return is_last_block_in_pool;
77     }
78 
79     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetLastBlockInPool()80     void SetLastBlockInPool()
81     {
82         ASSERT(!IsLastBlockInPool());
83         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
84         size_ = size_ | LAST_BLOCK_IN_POOL_BIT_MASK_IN_PLACE;
85         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
86     }
87 
88     // Is this memory block has some padding for alignment.
89     // If yes, it is some hidden header and we have some extra header where all correct information has been stored.
90     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsPaddingHeader()91     bool IsPaddingHeader()
92     {
93         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
94         bool is_padding_header = GetPaddingStatus(size_) == PADDING_STATUS_PADDING_HEADER;
95         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
96         return is_padding_header;
97     }
98 
99     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetAsPaddingHeader()100     void SetAsPaddingHeader()
101     {
102         ASSERT(!IsPaddingSizeStoredAfterHeader());
103         ASSERT(!IsPaddingHeaderStoredAfterHeader());
104         ASSERT(!IsPaddingHeader());
105         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
106         size_ = SetPaddingStatus(size_, PADDING_STATUS_PADDING_HEADER);
107         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
108     }
109 
110     // Is this memory block has some padding for alignment and we can get correct object memory address by using
111     // padding size, which is stored after this header.
112     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsPaddingSizeStoredAfterHeader()113     bool IsPaddingSizeStoredAfterHeader()
114     {
115         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
116         bool result = GetPaddingStatus(size_) == PADDING_STATUS_COMMON_HEADER_WITH_PADDING_SIZE;
117         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
118         return result;
119     }
120 
121     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPaddingSizeStoredAfterHeader()122     void SetPaddingSizeStoredAfterHeader()
123     {
124         ASSERT(!IsPaddingSizeStoredAfterHeader());
125         ASSERT(!IsPaddingHeaderStoredAfterHeader());
126         ASSERT(!IsPaddingHeader());
127         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
128         size_ = SetPaddingStatus(size_, PADDING_STATUS_COMMON_HEADER_WITH_PADDING_SIZE);
129         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
130     }
131 
132     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPaddingSize(size_t size)133     void SetPaddingSize(size_t size)
134     {
135         ASSERT(IsPaddingSizeStoredAfterHeader());
136         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
137         ASAN_UNPOISON_MEMORY_REGION(GetRawMemory(), sizeof(size_t));
138         *static_cast<size_t *>(GetRawMemory()) = size;
139         ASAN_UNPOISON_MEMORY_REGION(GetRawMemory(), sizeof(size_t));
140         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
141     }
142 
143     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetPaddingSize()144     size_t GetPaddingSize()
145     {
146         ASSERT(IsPaddingSizeStoredAfterHeader());
147         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
148         ASAN_UNPOISON_MEMORY_REGION(GetRawMemory(), sizeof(size_t));
149         auto size_pointer = static_cast<size_t *>(GetRawMemory());
150         size_t size = *size_pointer;
151         ASAN_UNPOISON_MEMORY_REGION(GetRawMemory(), sizeof(size_t));
152         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
153         return size;
154     }
155 
156     // Is this memory block has some padding for alignment and we have padding header just after this header,
157     // So, to compute object memory address we need to add padding header size.
158     ATTRIBUTE_NO_SANITIZE_ADDRESS
IsPaddingHeaderStoredAfterHeader()159     bool IsPaddingHeaderStoredAfterHeader()
160     {
161         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
162         bool result = GetPaddingStatus(size_) == PADDING_STATUS_COMMON_HEADER_WITH_PADDING_HEADER;
163         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
164         return result;
165     }
166 
167     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPaddingHeaderStoredAfterHeader()168     void SetPaddingHeaderStoredAfterHeader()
169     {
170         ASSERT(!IsPaddingSizeStoredAfterHeader());
171         ASSERT(!IsPaddingHeaderStoredAfterHeader());
172         ASSERT(!IsPaddingHeader());
173         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
174         size_ = SetPaddingStatus(size_, PADDING_STATUS_COMMON_HEADER_WITH_PADDING_HEADER);
175         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
176     }
177 
178     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetCommonHeader()179     void SetCommonHeader()
180     {
181         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
182         size_ = SetPaddingStatus(size_, PADDING_STATUS_COMMON_HEADER);
183         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
184     }
185 
186     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetSize()187     size_t GetSize()
188     {
189         ASSERT(!IsPaddingHeader());
190         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
191         size_t size = size_ >> STATUS_BITS_SIZE;
192         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
193         return size;
194     }
195 
196     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetPrevHeader()197     MemoryBlockHeader *GetPrevHeader()
198     {
199         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
200         MemoryBlockHeader *prev = prev_header_;
201         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
202         return prev;
203     }
204 
205     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetNextHeader()206     MemoryBlockHeader *GetNextHeader()
207     {
208         if (IsLastBlockInPool()) {
209             return nullptr;
210         }
211         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
212         auto next = static_cast<MemoryBlockHeader *>(ToVoidPtr(ToUintPtr(GetRawMemory()) + GetSize()));
213         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
214         return next;
215     }
216 
GetPrevUsedHeader()217     MemoryBlockHeader *GetPrevUsedHeader()
218     {
219         MemoryBlockHeader *prev = GetPrevHeader();
220         if (prev != nullptr) {
221             if (!prev->IsUsed()) {
222                 prev = prev->GetPrevHeader();
223                 if (prev != nullptr) {
224                     // We can't have 2 free consistent memory blocks
225                     ASSERT(prev->IsUsed());
226                 }
227             }
228         }
229         return prev;
230     }
231 
GetNextUsedHeader()232     MemoryBlockHeader *GetNextUsedHeader()
233     {
234         MemoryBlockHeader *next = GetNextHeader();
235         if (next != nullptr) {
236             if (!next->IsUsed()) {
237                 next = next->GetNextHeader();
238                 if (next != nullptr) {
239                     // We can't have 2 free consistent memory blocks
240                     ASSERT(next->IsUsed());
241                 }
242             }
243         }
244         return next;
245     }
246 
247     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPrevHeader(MemoryBlockHeader * header)248     void SetPrevHeader(MemoryBlockHeader *header)
249     {
250         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
251         prev_header_ = header;
252         ASAN_POISON_MEMORY_REGION(this, sizeof(MemoryBlockHeader));
253     }
254 
CanBeCoalescedWithNext()255     bool CanBeCoalescedWithNext()
256     {
257         if (IsLastBlockInPool()) {
258             return false;
259         }
260         ASSERT(GetNextHeader() != nullptr);
261         return !GetNextHeader()->IsUsed();
262     }
263 
CanBeCoalescedWithPrev()264     bool CanBeCoalescedWithPrev()
265     {
266         if (GetPrevHeader() == nullptr) {
267             return false;
268         }
269         return !GetPrevHeader()->IsUsed();
270     }
271 
GetMemory()272     void *GetMemory()
273     {
274         void *mem_pointer = GetRawMemory();
275         if (IsPaddingHeaderStoredAfterHeader()) {
276             return ToVoidPtr(ToUintPtr(mem_pointer) + sizeof(MemoryBlockHeader));
277         }
278         if (IsPaddingSizeStoredAfterHeader()) {
279             return ToVoidPtr(ToUintPtr(mem_pointer) + GetPaddingSize());
280         }
281         return mem_pointer;
282     }
283 
284 private:
285     enum STATUS_BITS : size_t {
286         USED_BIT_SIZE = 1U,
287         LAST_BLOCK_IN_POOL_BIT_SIZE = 1U,
288         PADDIND_STATUS_SIZE = 2U,
289         STATUS_BITS_SIZE = PADDIND_STATUS_SIZE + LAST_BLOCK_IN_POOL_BIT_SIZE + USED_BIT_SIZE,
290 
291         USED_BIT_POS = 0U,
292         LAST_BLOCK_IN_POOL_BIT_POS = USED_BIT_POS + USED_BIT_SIZE,
293         PADDIND_STATUS_POS = LAST_BLOCK_IN_POOL_BIT_POS + LAST_BLOCK_IN_POOL_BIT_SIZE,
294 
295         USED_BIT_MASK = (1U << USED_BIT_SIZE) - 1U,
296         USED_BIT_MASK_IN_PLACE = USED_BIT_MASK << USED_BIT_POS,
297 
298         LAST_BLOCK_IN_POOL_BIT_MASK = (1U << LAST_BLOCK_IN_POOL_BIT_SIZE) - 1U,
299         LAST_BLOCK_IN_POOL_BIT_MASK_IN_PLACE = LAST_BLOCK_IN_POOL_BIT_MASK << LAST_BLOCK_IN_POOL_BIT_POS,
300 
301         PADDIND_STATUS_MASK = (1U << PADDIND_STATUS_SIZE) - 1U,
302         PADDIND_STATUS_MASK_IN_PLACE = PADDIND_STATUS_MASK << PADDIND_STATUS_POS,
303 
304         // A common header with object stored just after the header
305         PADDING_STATUS_COMMON_HEADER = 0U,
306         // A special padding header, which is used to find the common header of this memory.
307         // This object required special alignment, that's why we created some padding between
308         // the common header of this memory and place where the object is stored.
309         PADDING_STATUS_PADDING_HEADER = PADDING_STATUS_COMMON_HEADER + 1U,
310         // A common header for aligned object which required some padding.
311         // The padding size is stored in size_t variable just after the common header
312         PADDING_STATUS_COMMON_HEADER_WITH_PADDING_SIZE = PADDING_STATUS_PADDING_HEADER + 1U,
313         // A common header for aligned object which required some padding.
314         // The padding header is stored just after the common header
315         PADDING_STATUS_COMMON_HEADER_WITH_PADDING_HEADER = PADDING_STATUS_COMMON_HEADER_WITH_PADDING_SIZE + 1U,
316     };
317 
GetPaddingStatus(size_t size)318     static size_t GetPaddingStatus(size_t size)
319     {
320         return (size & PADDIND_STATUS_MASK_IN_PLACE) >> PADDIND_STATUS_POS;
321     }
322 
SetPaddingStatus(size_t size,STATUS_BITS status)323     static size_t SetPaddingStatus(size_t size, STATUS_BITS status)
324     {
325         size = size & (~PADDIND_STATUS_MASK_IN_PLACE);
326         return size | (static_cast<size_t>(status) << PADDIND_STATUS_POS);
327     }
328 
GetRawMemory()329     void *GetRawMemory()
330     {
331         return ToVoidPtr(ToUintPtr(this) + sizeof(MemoryBlockHeader));
332     }
333 
334     size_t size_ {0};
335     MemoryBlockHeader *prev_header_ {nullptr};
336 };
337 
338 class FreeListHeader : public MemoryBlockHeader {
339 public:
340     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetNextFree()341     FreeListHeader *GetNextFree()
342     {
343         ASSERT(!IsUsed());
344         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
345         FreeListHeader *next_free = next_free_;
346         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
347         return next_free;
348     }
349 
350     ATTRIBUTE_NO_SANITIZE_ADDRESS
GetPrevFree()351     FreeListHeader *GetPrevFree()
352     {
353         ASSERT(!IsUsed());
354         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
355         FreeListHeader *prev_free = prev_free_;
356         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
357         return prev_free;
358     }
359 
360     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetNextFree(FreeListHeader * link)361     void SetNextFree(FreeListHeader *link)
362     {
363         ASSERT(!IsUsed());
364         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
365         // Potentially, TSAN finds false data race (due to full memory barrier in Array::Create)
366         TSAN_ANNOTATE_IGNORE_WRITES_BEGIN();
367         next_free_ = link;
368         TSAN_ANNOTATE_IGNORE_WRITES_END();
369         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
370     }
371 
372     ATTRIBUTE_NO_SANITIZE_ADDRESS
SetPrevFree(FreeListHeader * link)373     void SetPrevFree(FreeListHeader *link)
374     {
375         ASSERT(!IsUsed());
376         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
377         // TSAN finds false data race (due to full memory barrier in Array::Create
378         TSAN_ANNOTATE_IGNORE_WRITES_BEGIN();
379         prev_free_ = link;
380         TSAN_ANNOTATE_IGNORE_WRITES_END();
381         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
382     }
383 
384     ATTRIBUTE_NO_SANITIZE_ADDRESS
InsertPrev(FreeListHeader * link)385     void InsertPrev(FreeListHeader *link)
386     {
387         ASSERT(!IsUsed());
388         ASSERT(link != nullptr);
389         ASSERT(!link->IsUsed());
390         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
391         if (prev_free_ != nullptr) {
392             prev_free_->SetNextFree(link);
393         }
394         link->SetNextFree(this);
395         link->SetPrevFree(prev_free_);
396         prev_free_ = link;
397         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
398     }
399 
400     ATTRIBUTE_NO_SANITIZE_ADDRESS
InsertNext(FreeListHeader * link)401     void InsertNext(FreeListHeader *link)
402     {
403         ASSERT(!IsUsed());
404         ASSERT(link != nullptr);
405         ASSERT(!link->IsUsed());
406         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
407         if (next_free_ != nullptr) {
408             next_free_->SetPrevFree(link);
409         }
410         link->SetNextFree(next_free_);
411         link->SetPrevFree(this);
412         next_free_ = link;
413         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
414     }
415 
416     ATTRIBUTE_NO_SANITIZE_ADDRESS
PopFromFreeList()417     void PopFromFreeList()
418     {
419         ASSERT(!IsUsed());
420         ASAN_UNPOISON_MEMORY_REGION(this, sizeof(FreeListHeader));
421         if (next_free_ != nullptr) {
422             next_free_->SetPrevFree(prev_free_);
423         }
424         if (prev_free_ != nullptr) {
425             prev_free_->SetNextFree(next_free_);
426         }
427         ASAN_POISON_MEMORY_REGION(this, sizeof(FreeListHeader));
428     }
429 
430 private:
431     FreeListHeader *next_free_ {nullptr};
432     FreeListHeader *prev_free_ {nullptr};
433 };
434 
435 }  // namespace panda::mem::freelist
436 
437 #endif  // PANDA_MEM_FREELIST_H
438