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 22namespace llvm { 23 24/// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for 25/// printing statistics. 26/// 27void 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/// 33template <class T, size_t Size = sizeof(T), size_t Align = alignof(T)> 34class 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 56public: 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(reinterpret_cast<FreeNode *>(Element)); 100 } 101 102 void PrintStats(); 103}; 104 105template <class T, size_t Size, size_t Align> 106void 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, S); 111} 112 113} 114 115#endif 116