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 Recycler(const Recycler &) = delete; 64 Recycler(Recycler &&Other) 65 : FreeList(std::exchange(Other.FreeList, nullptr)) {} 66 Recycler() = default; 67 68 /// clear - Release all the tracked allocations to the allocator. The 69 /// recycler must be free of any tracked allocations before being 70 /// deleted; calling clear is one way to ensure this. 71 template<class AllocatorType> 72 void clear(AllocatorType &Allocator) { 73 while (FreeList) { 74 T *t = reinterpret_cast<T *>(pop_val()); 75 Allocator.Deallocate(t, Size, Align); 76 } 77 } 78 79 /// Special case for BumpPtrAllocator which has an empty Deallocate() 80 /// function. 81 /// 82 /// There is no need to traverse the free list, pulling all the objects into 83 /// cache. 84 void clear(BumpPtrAllocator &) { FreeList = nullptr; } 85 86 template<class SubClass, class AllocatorType> 87 SubClass *Allocate(AllocatorType &Allocator) { 88 static_assert(alignof(SubClass) <= Align, 89 "Recycler allocation alignment is less than object align!"); 90 static_assert(sizeof(SubClass) <= Size, 91 "Recycler allocation size is less than object size!"); 92 static_assert(Size >= sizeof(FreeNode) && 93 "Recycler allocation size must be at least sizeof(FreeNode)"); 94 return FreeList ? reinterpret_cast<SubClass *>(pop_val()) 95 : static_cast<SubClass *>(Allocator.Allocate(Size, Align)); 96 } 97 98 template<class AllocatorType> 99 T *Allocate(AllocatorType &Allocator) { 100 return Allocate<T>(Allocator); 101 } 102 103 template<class SubClass, class AllocatorType> 104 void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) { 105 push(reinterpret_cast<FreeNode *>(Element)); 106 } 107 108 void PrintStats(); 109 }; 110 111 template <class T, size_t Size, size_t Align> 112 void Recycler<T, Size, Align>::PrintStats() { 113 size_t S = 0; 114 for (auto *I = FreeList; I; I = I->Next) 115 ++S; 116 PrintRecyclerStats(Size, Align, S); 117 } 118 119 } 120 121 #endif 122