1 | //==- llvm/Support/Recycler.h - Recycling Allocator --------------*- C++ -*-==// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines the Recycler class template. See the doxygen comment for |
10 | // Recycler for more details. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_SUPPORT_RECYCLER_H |
15 | #define LLVM_SUPPORT_RECYCLER_H |
16 | |
17 | #include "llvm/ADT/ilist.h" |
18 | #include "llvm/Support/Allocator.h" |
19 | #include "llvm/Support/ErrorHandling.h" |
20 | #include <cassert> |
21 | |
22 | namespace llvm { |
23 | |
24 | /// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for |
25 | /// printing statistics. |
26 | /// |
27 | void PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize); |
28 | |
29 | /// Recycler - This class manages a linked-list of deallocated nodes |
30 | /// and facilitates reusing deallocated memory in place of allocating |
31 | /// new memory. |
32 | /// |
33 | template <class T, size_t Size = sizeof(T), size_t Align = alignof(T)> |
34 | class Recycler { |
35 | struct FreeNode { |
36 | FreeNode *Next; |
37 | }; |
38 | |
39 | /// List of nodes that have deleted contents and are not in active use. |
40 | FreeNode *FreeList = nullptr; |
41 | |
42 | FreeNode *pop_val() { |
43 | auto *Val = FreeList; |
44 | __asan_unpoison_memory_region(Val, Size); |
45 | FreeList = FreeList->Next; |
46 | __msan_allocated_memory(Val, Size); |
47 | return Val; |
48 | } |
49 | |
50 | void push(FreeNode *N) { |
51 | N->Next = FreeList; |
52 | FreeList = N; |
53 | __asan_poison_memory_region(N, Size); |
54 | } |
55 | |
56 | public: |
57 | ~Recycler() { |
58 | // If this fails, either the callee has lost track of some allocation, |
59 | // or the callee isn't tracking allocations and should just call |
60 | // clear() before deleting the Recycler. |
61 | assert(!FreeList && "Non-empty recycler deleted!" ); |
62 | } |
63 | |
64 | /// clear - Release all the tracked allocations to the allocator. The |
65 | /// recycler must be free of any tracked allocations before being |
66 | /// deleted; calling clear is one way to ensure this. |
67 | template<class AllocatorType> |
68 | void clear(AllocatorType &Allocator) { |
69 | while (FreeList) { |
70 | T *t = reinterpret_cast<T *>(pop_val()); |
71 | Allocator.Deallocate(t); |
72 | } |
73 | } |
74 | |
75 | /// Special case for BumpPtrAllocator which has an empty Deallocate() |
76 | /// function. |
77 | /// |
78 | /// There is no need to traverse the free list, pulling all the objects into |
79 | /// cache. |
80 | void clear(BumpPtrAllocator &) { FreeList = nullptr; } |
81 | |
82 | template<class SubClass, class AllocatorType> |
83 | SubClass *Allocate(AllocatorType &Allocator) { |
84 | static_assert(alignof(SubClass) <= Align, |
85 | "Recycler allocation alignment is less than object align!" ); |
86 | static_assert(sizeof(SubClass) <= Size, |
87 | "Recycler allocation size is less than object size!" ); |
88 | return FreeList ? reinterpret_cast<SubClass *>(pop_val()) |
89 | : static_cast<SubClass *>(Allocator.Allocate(Size, Align)); |
90 | } |
91 | |
92 | template<class AllocatorType> |
93 | T *Allocate(AllocatorType &Allocator) { |
94 | return Allocate<T>(Allocator); |
95 | } |
96 | |
97 | template<class SubClass, class AllocatorType> |
98 | void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) { |
99 | push(N: reinterpret_cast<FreeNode *>(Element)); |
100 | } |
101 | |
102 | void PrintStats(); |
103 | }; |
104 | |
105 | template <class T, size_t Size, size_t Align> |
106 | void Recycler<T, Size, Align>::PrintStats() { |
107 | size_t S = 0; |
108 | for (auto *I = FreeList; I; I = I->Next) |
109 | ++S; |
110 | PrintRecyclerStats(Size, Align, FreeListSize: S); |
111 | } |
112 | |
113 | } |
114 | |
115 | #endif |
116 | |