diff options
Diffstat (limited to 'include/llvm/Support/Allocator.h')
| -rw-r--r-- | include/llvm/Support/Allocator.h | 410 |
1 files changed, 245 insertions, 165 deletions
diff --git a/include/llvm/Support/Allocator.h b/include/llvm/Support/Allocator.h index 0641322..7a7e4c0 100644 --- a/include/llvm/Support/Allocator.h +++ b/include/llvm/Support/Allocator.h @@ -6,14 +6,22 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This file defines the MallocAllocator and BumpPtrAllocator interfaces. -// +/// \file +/// +/// This file defines the MallocAllocator and BumpPtrAllocator interfaces. Both +/// of these conform to an LLVM "Allocator" concept which consists of an +/// Allocate method accepting a size and alignment, and a Deallocate accepting +/// a pointer and size. Further, the LLVM "Allocator" concept has overloads of +/// Allocate and Deallocate for setting size and alignment based on the final +/// type. These overloads are typically provided by a base class template \c +/// AllocatorBase. +/// //===----------------------------------------------------------------------===// #ifndef LLVM_SUPPORT_ALLOCATOR_H #define LLVM_SUPPORT_ALLOCATOR_H +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" @@ -24,90 +32,86 @@ #include <cstdlib> namespace llvm { -template <typename T> struct ReferenceAdder { - typedef T &result; -}; -template <typename T> struct ReferenceAdder<T &> { - typedef T result; -}; -class MallocAllocator { +/// \brief CRTP base class providing obvious overloads for the core \c +/// Allocate() methods of LLVM-style allocators. +/// +/// This base class both documents the full public interface exposed by all +/// LLVM-style allocators, and redirects all of the overloads to a single core +/// set of methods which the derived class must define. +template <typename DerivedT> class AllocatorBase { public: - MallocAllocator() {} - ~MallocAllocator() {} - - void Reset() {} - - void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); } - - template <typename T> T *Allocate() { - return static_cast<T *>(malloc(sizeof(T))); + /// \brief Allocate \a Size bytes of \a Alignment aligned memory. This method + /// must be implemented by \c DerivedT. + void *Allocate(size_t Size, size_t Alignment) { +#ifdef __clang__ + static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>( + &AllocatorBase::Allocate) != + static_cast<void *(DerivedT::*)(size_t, size_t)>( + &DerivedT::Allocate), + "Class derives from AllocatorBase without implementing the " + "core Allocate(size_t, size_t) overload!"); +#endif + return static_cast<DerivedT *>(this)->Allocate(Size, Alignment); } - template <typename T> T *Allocate(size_t Num) { - return static_cast<T *>(malloc(sizeof(T) * Num)); + /// \brief Deallocate \a Ptr to \a Size bytes of memory allocated by this + /// allocator. + void Deallocate(const void *Ptr, size_t Size) { +#ifdef __clang__ + static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>( + &AllocatorBase::Deallocate) != + static_cast<void (DerivedT::*)(const void *, size_t)>( + &DerivedT::Deallocate), + "Class derives from AllocatorBase without implementing the " + "core Deallocate(void *) overload!"); +#endif + return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size); } - void Deallocate(const void *Ptr) { free(const_cast<void *>(Ptr)); } + // The rest of these methods are helpers that redirect to one of the above + // core methods. - void PrintStats() const {} -}; + /// \brief Allocate space for a sequence of objects without constructing them. + template <typename T> T *Allocate(size_t Num = 1) { + return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment)); + } -/// MemSlab - This structure lives at the beginning of every slab allocated by -/// the bump allocator. -class MemSlab { -public: - size_t Size; - MemSlab *NextPtr; + /// \brief Deallocate space for a sequence of objects without constructing them. + template <typename T> + typename std::enable_if< + !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type + Deallocate(T *Ptr, size_t Num = 1) { + Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T)); + } }; -/// SlabAllocator - This class can be used to parameterize the underlying -/// allocation strategy for the bump allocator. In particular, this is used -/// by the JIT to allocate contiguous swathes of executable memory. The -/// interface uses MemSlab's instead of void *'s so that the allocator -/// doesn't have to remember the size of the pointer it allocated. -class SlabAllocator { +class MallocAllocator : public AllocatorBase<MallocAllocator> { public: - virtual ~SlabAllocator(); - virtual MemSlab *Allocate(size_t Size) = 0; - virtual void Deallocate(MemSlab *Slab) = 0; -}; + void Reset() {} -/// MallocSlabAllocator - The default slab allocator for the bump allocator -/// is an adapter class for MallocAllocator that just forwards the method -/// calls and translates the arguments. -class MallocSlabAllocator : public SlabAllocator { - /// Allocator - The underlying allocator that we forward to. - /// - MallocAllocator Allocator; + void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); } -public: - MallocSlabAllocator() : Allocator() {} - virtual ~MallocSlabAllocator(); - MemSlab *Allocate(size_t Size) override; - void Deallocate(MemSlab *Slab) override; -}; + // Pull in base class overloads. + using AllocatorBase<MallocAllocator>::Allocate; -/// \brief Non-templated base class for the \c BumpPtrAllocatorImpl template. -class BumpPtrAllocatorBase { -public: - void Deallocate(const void * /*Ptr*/) {} - void PrintStats() const; + void Deallocate(const void *Ptr, size_t /*Size*/) { + free(const_cast<void *>(Ptr)); + } - /// \brief Returns the total physical memory allocated by this allocator. - size_t getTotalMemory() const; + // Pull in base class overloads. + using AllocatorBase<MallocAllocator>::Deallocate; -protected: - /// \brief The slab that we are currently allocating into. - MemSlab *CurSlab; + void PrintStats() const {} +}; - /// \brief How many bytes we've allocated. - /// - /// Used so that we can compute how much space was wasted. - size_t BytesAllocated; +namespace detail { - BumpPtrAllocatorBase() : CurSlab(0), BytesAllocated(0) {} -}; +// We call out to an external function to actually print the message as the +// printing code uses Allocator.h in its implementation. +void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated, + size_t TotalMemory); +} // End namespace detail. /// \brief Allocate memory in an ever growing pool, as if by bump-pointer. /// @@ -119,11 +123,15 @@ protected: /// /// Note that this also has a threshold for forcing allocations above a certain /// size into their own slab. -template <size_t SlabSize = 4096, size_t SizeThreshold = SlabSize> -class BumpPtrAllocatorImpl : public BumpPtrAllocatorBase { - BumpPtrAllocatorImpl(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION; - void operator=(const BumpPtrAllocatorImpl &) LLVM_DELETED_FUNCTION; - +/// +/// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator +/// object, which wraps malloc, to allocate memory, but it can be changed to +/// use a custom allocator. +template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096, + size_t SizeThreshold = SlabSize> +class BumpPtrAllocatorImpl + : public AllocatorBase< + BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> { public: static_assert(SizeThreshold <= SlabSize, "The SizeThreshold must be at most the SlabSize to ensure " @@ -131,26 +139,69 @@ public: "allocation."); BumpPtrAllocatorImpl() - : Allocator(DefaultSlabAllocator), NumSlabs(0) {} - BumpPtrAllocatorImpl(SlabAllocator &Allocator) - : Allocator(Allocator), NumSlabs(0) {} - ~BumpPtrAllocatorImpl() { DeallocateSlabs(CurSlab); } + : CurPtr(nullptr), End(nullptr), BytesAllocated(0), Allocator() {} + template <typename T> + BumpPtrAllocatorImpl(T &&Allocator) + : CurPtr(nullptr), End(nullptr), BytesAllocated(0), + Allocator(std::forward<T &&>(Allocator)) {} + + // Manually implement a move constructor as we must clear the old allocators + // slabs as a matter of correctness. + BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old) + : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)), + CustomSizedSlabs(std::move(Old.CustomSizedSlabs)), + BytesAllocated(Old.BytesAllocated), + Allocator(std::move(Old.Allocator)) { + Old.CurPtr = Old.End = nullptr; + Old.BytesAllocated = 0; + Old.Slabs.clear(); + Old.CustomSizedSlabs.clear(); + } + + ~BumpPtrAllocatorImpl() { + DeallocateSlabs(Slabs.begin(), Slabs.end()); + DeallocateCustomSizedSlabs(); + } + + BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) { + DeallocateSlabs(Slabs.begin(), Slabs.end()); + DeallocateCustomSizedSlabs(); + + CurPtr = RHS.CurPtr; + End = RHS.End; + BytesAllocated = RHS.BytesAllocated; + Slabs = std::move(RHS.Slabs); + CustomSizedSlabs = std::move(RHS.CustomSizedSlabs); + Allocator = std::move(RHS.Allocator); + + RHS.CurPtr = RHS.End = nullptr; + RHS.BytesAllocated = 0; + RHS.Slabs.clear(); + RHS.CustomSizedSlabs.clear(); + return *this; + } /// \brief Deallocate all but the current slab and reset the current pointer /// to the beginning of it, freeing all memory allocated so far. void Reset() { - if (!CurSlab) + if (Slabs.empty()) return; - DeallocateSlabs(CurSlab->NextPtr); - CurSlab->NextPtr = 0; - CurPtr = (char *)(CurSlab + 1); - End = ((char *)CurSlab) + CurSlab->Size; + + // Reset the state. BytesAllocated = 0; + CurPtr = (char *)Slabs.front(); + End = CurPtr + SlabSize; + + // Deallocate all but the first slab, and all custome sized slabs. + DeallocateSlabs(std::next(Slabs.begin()), Slabs.end()); + Slabs.erase(std::next(Slabs.begin()), Slabs.end()); + DeallocateCustomSizedSlabs(); + CustomSizedSlabs.clear(); } /// \brief Allocate space at the specified alignment. void *Allocate(size_t Size, size_t Alignment) { - if (!CurSlab) // Start a new slab if we haven't allocated one already. + if (!CurPtr) // Start a new slab if we haven't allocated one already. StartNewSlab(); // Keep track of how many bytes we've allocated. @@ -174,18 +225,13 @@ public: } // If Size is really big, allocate a separate slab for it. - size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; + size_t PaddedSize = Size + Alignment - 1; if (PaddedSize > SizeThreshold) { - ++NumSlabs; - MemSlab *NewSlab = Allocator.Allocate(PaddedSize); - - // Put the new slab after the current slab, since we are not allocating - // into it. - NewSlab->NextPtr = CurSlab->NextPtr; - CurSlab->NextPtr = NewSlab; + void *NewSlab = Allocator.Allocate(PaddedSize, 0); + CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize)); - Ptr = alignPtr((char *)(NewSlab + 1), Alignment); - assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); + Ptr = alignPtr((char *)NewSlab, Alignment); + assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + PaddedSize); __msan_allocated_memory(Ptr, Size); return Ptr; } @@ -199,36 +245,31 @@ public: return Ptr; } - /// \brief Allocate space for one object without constructing it. - template <typename T> T *Allocate() { - return static_cast<T *>(Allocate(sizeof(T), AlignOf<T>::Alignment)); - } + // Pull in base class overloads. + using AllocatorBase<BumpPtrAllocatorImpl>::Allocate; - /// \brief Allocate space for an array of objects without constructing them. - template <typename T> T *Allocate(size_t Num) { - return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment)); - } + void Deallocate(const void * /*Ptr*/, size_t /*Size*/) {} - /// \brief Allocate space for an array of objects with the specified alignment - /// and without constructing them. - template <typename T> T *Allocate(size_t Num, size_t Alignment) { - // Round EltSize up to the specified alignment. - size_t EltSize = (sizeof(T) + Alignment - 1) & (-Alignment); - return static_cast<T *>(Allocate(Num * EltSize, Alignment)); - } + // Pull in base class overloads. + using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate; - size_t GetNumSlabs() const { return NumSlabs; } + size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); } -private: - /// \brief The default allocator used if one is not provided. - MallocSlabAllocator DefaultSlabAllocator; + size_t getTotalMemory() const { + size_t TotalMemory = 0; + for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I) + TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I)); + for (auto &PtrAndSize : CustomSizedSlabs) + TotalMemory += PtrAndSize.second; + return TotalMemory; + } - /// \brief The underlying allocator we use to get slabs of memory. - /// - /// This defaults to MallocSlabAllocator, which wraps malloc, but it could be - /// changed to use a custom allocator. - SlabAllocator &Allocator; + void PrintStats() const { + detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated, + getTotalMemory()); + } +private: /// \brief The current pointer into the current slab. /// /// This points to the next free byte in the slab. @@ -237,46 +278,67 @@ private: /// \brief The end of the current slab. char *End; - /// \brief How many slabs we've allocated. + /// \brief The slabs allocated so far. + SmallVector<void *, 4> Slabs; + + /// \brief Custom-sized slabs allocated for too-large allocation requests. + SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs; + + /// \brief How many bytes we've allocated. /// - /// Used to scale the size of each slab and reduce the number of allocations - /// for extremely heavy memory use scenarios. - size_t NumSlabs; + /// Used so that we can compute how much space was wasted. + size_t BytesAllocated; - /// \brief Allocate a new slab and move the bump pointers over into the new - /// slab, modifying CurPtr and End. - void StartNewSlab() { - ++NumSlabs; + /// \brief The allocator instance we use to get slabs of memory. + AllocatorT Allocator; + + static size_t computeSlabSize(unsigned SlabIdx) { // Scale the actual allocated slab size based on the number of slabs // allocated. Every 128 slabs allocated, we double the allocated size to // reduce allocation frequency, but saturate at multiplying the slab size by // 2^30. - // FIXME: Currently, this count includes special slabs for objects above the - // size threshold. That will be fixed in a subsequent commit to make the - // growth even more predictable. - size_t AllocatedSlabSize = - SlabSize * ((size_t)1 << std::min<size_t>(30, NumSlabs / 128)); - - MemSlab *NewSlab = Allocator.Allocate(AllocatedSlabSize); - NewSlab->NextPtr = CurSlab; - CurSlab = NewSlab; - CurPtr = (char *)(CurSlab + 1); - End = ((char *)CurSlab) + CurSlab->Size; + return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128)); } - /// \brief Deallocate all memory slabs after and including this one. - void DeallocateSlabs(MemSlab *Slab) { - while (Slab) { - MemSlab *NextSlab = Slab->NextPtr; + /// \brief Allocate a new slab and move the bump pointers over into the new + /// slab, modifying CurPtr and End. + void StartNewSlab() { + size_t AllocatedSlabSize = computeSlabSize(Slabs.size()); + + void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0); + Slabs.push_back(NewSlab); + CurPtr = (char *)(NewSlab); + End = ((char *)NewSlab) + AllocatedSlabSize; + } + + /// \brief Deallocate a sequence of slabs. + void DeallocateSlabs(SmallVectorImpl<void *>::iterator I, + SmallVectorImpl<void *>::iterator E) { + for (; I != E; ++I) { + size_t AllocatedSlabSize = + computeSlabSize(std::distance(Slabs.begin(), I)); #ifndef NDEBUG // Poison the memory so stale pointers crash sooner. Note we must // preserve the Size and NextPtr fields at the beginning. - sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); - memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); + sys::Memory::setRangeWritable(*I, AllocatedSlabSize); + memset(*I, 0xCD, AllocatedSlabSize); #endif - Allocator.Deallocate(Slab); - Slab = NextSlab; - --NumSlabs; + Allocator.Deallocate(*I, AllocatedSlabSize); + } + } + + /// \brief Deallocate all memory for custom sized slabs. + void DeallocateCustomSizedSlabs() { + for (auto &PtrAndSize : CustomSizedSlabs) { + void *Ptr = PtrAndSize.first; + size_t Size = PtrAndSize.second; +#ifndef NDEBUG + // Poison the memory so stale pointers crash sooner. Note we must + // preserve the Size and NextPtr fields at the beginning. + sys::Memory::setRangeWritable(Ptr, Size); + memset(Ptr, 0xCD, Size); +#endif + Allocator.Deallocate(Ptr, Size); } } @@ -297,25 +359,42 @@ template <typename T> class SpecificBumpPtrAllocator { public: SpecificBumpPtrAllocator() : Allocator() {} - SpecificBumpPtrAllocator(SlabAllocator &allocator) : Allocator(allocator) {} - + SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old) + : Allocator(std::move(Old.Allocator)) {} ~SpecificBumpPtrAllocator() { DestroyAll(); } + SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) { + Allocator = std::move(RHS.Allocator); + return *this; + } + /// Call the destructor of each allocated object and deallocate all but the /// current slab and reset the current pointer to the beginning of it, freeing /// all memory allocated so far. void DestroyAll() { - MemSlab *Slab = Allocator.CurSlab; - while (Slab) { - char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr - : (char *)Slab + Slab->Size; - for (char *Ptr = (char *)(Slab + 1); Ptr < End; Ptr += sizeof(T)) { - Ptr = alignPtr(Ptr, alignOf<T>()); - if (Ptr + sizeof(T) <= End) - reinterpret_cast<T *>(Ptr)->~T(); - } - Slab = Slab->NextPtr; + auto DestroyElements = [](char *Begin, char *End) { + assert(Begin == alignPtr(Begin, alignOf<T>())); + for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T)) + reinterpret_cast<T *>(Ptr)->~T(); + }; + + for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E; + ++I) { + size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize( + std::distance(Allocator.Slabs.begin(), I)); + char *Begin = alignPtr((char *)*I, alignOf<T>()); + char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr + : (char *)*I + AllocatedSlabSize; + + DestroyElements(Begin, End); + } + + for (auto &PtrAndSize : Allocator.CustomSizedSlabs) { + void *Ptr = PtrAndSize.first; + size_t Size = PtrAndSize.second; + DestroyElements(alignPtr((char *)Ptr, alignOf<T>()), (char *)Ptr + Size); } + Allocator.Reset(); } @@ -325,10 +404,10 @@ public: } // end namespace llvm -template <size_t SlabSize, size_t SizeThreshold> -void * -operator new(size_t Size, - llvm::BumpPtrAllocatorImpl<SlabSize, SizeThreshold> &Allocator) { +template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold> +void *operator new(size_t Size, + llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, + SizeThreshold> &Allocator) { struct S { char c; union { @@ -342,8 +421,9 @@ operator new(size_t Size, Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x))); } -template <size_t SlabSize, size_t SizeThreshold> -void operator delete(void *, - llvm::BumpPtrAllocatorImpl<SlabSize, SizeThreshold> &) {} +template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold> +void operator delete( + void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) { +} #endif // LLVM_SUPPORT_ALLOCATOR_H |