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