LCOV - code coverage report
Current view: top level - include/llvm/Support - Allocator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 90 95 94.7 %
Date: 2018-07-13 00:08:38 Functions: 204 218 93.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- Allocator.h - Simple memory allocation abstraction -------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : /// \file
      10             : ///
      11             : /// This file defines the MallocAllocator and BumpPtrAllocator interfaces. Both
      12             : /// of these conform to an LLVM "Allocator" concept which consists of an
      13             : /// Allocate method accepting a size and alignment, and a Deallocate accepting
      14             : /// a pointer and size. Further, the LLVM "Allocator" concept has overloads of
      15             : /// Allocate and Deallocate for setting size and alignment based on the final
      16             : /// type. These overloads are typically provided by a base class template \c
      17             : /// AllocatorBase.
      18             : ///
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #ifndef LLVM_SUPPORT_ALLOCATOR_H
      22             : #define LLVM_SUPPORT_ALLOCATOR_H
      23             : 
      24             : #include "llvm/ADT/SmallVector.h"
      25             : #include "llvm/Support/Compiler.h"
      26             : #include "llvm/Support/ErrorHandling.h"
      27             : #include "llvm/Support/MathExtras.h"
      28             : #include "llvm/Support/MemAlloc.h"
      29             : #include <algorithm>
      30             : #include <cassert>
      31             : #include <cstddef>
      32             : #include <cstdint>
      33             : #include <cstdlib>
      34             : #include <iterator>
      35             : #include <type_traits>
      36             : #include <utility>
      37             : 
      38             : namespace llvm {
      39             : 
      40             : /// CRTP base class providing obvious overloads for the core \c
      41             : /// Allocate() methods of LLVM-style allocators.
      42             : ///
      43             : /// This base class both documents the full public interface exposed by all
      44             : /// LLVM-style allocators, and redirects all of the overloads to a single core
      45             : /// set of methods which the derived class must define.
      46             : template <typename DerivedT> class AllocatorBase {
      47             : public:
      48             :   /// Allocate \a Size bytes of \a Alignment aligned memory. This method
      49             :   /// must be implemented by \c DerivedT.
      50             :   void *Allocate(size_t Size, size_t Alignment) {
      51             : #ifdef __clang__
      52             :     static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
      53             :                       &AllocatorBase::Allocate) !=
      54             :                       static_cast<void *(DerivedT::*)(size_t, size_t)>(
      55             :                           &DerivedT::Allocate),
      56             :                   "Class derives from AllocatorBase without implementing the "
      57             :                   "core Allocate(size_t, size_t) overload!");
      58             : #endif
      59   160695581 :     return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
      60             :   }
      61             : 
      62             :   /// Deallocate \a Ptr to \a Size bytes of memory allocated by this
      63             :   /// allocator.
      64             :   void Deallocate(const void *Ptr, size_t Size) {
      65             : #ifdef __clang__
      66             :     static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>(
      67             :                       &AllocatorBase::Deallocate) !=
      68             :                       static_cast<void (DerivedT::*)(const void *, size_t)>(
      69             :                           &DerivedT::Deallocate),
      70             :                   "Class derives from AllocatorBase without implementing the "
      71             :                   "core Deallocate(void *) overload!");
      72             : #endif
      73             :     return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size);
      74             :   }
      75             : 
      76             :   // The rest of these methods are helpers that redirect to one of the above
      77             :   // core methods.
      78             : 
      79             :   /// Allocate space for a sequence of objects without constructing them.
      80             :   template <typename T> T *Allocate(size_t Num = 1) {
      81    18675018 :     return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T)));
      82             :   }
      83             : 
      84             :   /// Deallocate space for a sequence of objects without constructing them.
      85             :   template <typename T>
      86             :   typename std::enable_if<
      87             :       !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type
      88             :   Deallocate(T *Ptr, size_t Num = 1) {
      89             :     Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T));
      90             :   }
      91             : };
      92             : 
      93             : class MallocAllocator : public AllocatorBase<MallocAllocator> {
      94             : public:
      95             :   void Reset() {}
      96             : 
      97             :   LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size,
      98             :                                                 size_t /*Alignment*/) {
      99   241416002 :     return safe_malloc(Size);
     100             :   }
     101             : 
     102             :   // Pull in base class overloads.
     103             :   using AllocatorBase<MallocAllocator>::Allocate;
     104             : 
     105             :   void Deallocate(const void *Ptr, size_t /*Size*/) {
     106   224209373 :     free(const_cast<void *>(Ptr));
     107             :   }
     108             : 
     109             :   // Pull in base class overloads.
     110             :   using AllocatorBase<MallocAllocator>::Deallocate;
     111             : 
     112             :   void PrintStats() const {}
     113             : };
     114             : 
     115             : namespace detail {
     116             : 
     117             : // We call out to an external function to actually print the message as the
     118             : // printing code uses Allocator.h in its implementation.
     119             : void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
     120             :                                 size_t TotalMemory);
     121             : 
     122             : } // end namespace detail
     123             : 
     124             : /// Allocate memory in an ever growing pool, as if by bump-pointer.
     125             : ///
     126             : /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
     127             : /// memory rather than relying on a boundless contiguous heap. However, it has
     128             : /// bump-pointer semantics in that it is a monotonically growing pool of memory
     129             : /// where every allocation is found by merely allocating the next N bytes in
     130             : /// the slab, or the next N bytes in the next slab.
     131             : ///
     132             : /// Note that this also has a threshold for forcing allocations above a certain
     133             : /// size into their own slab.
     134             : ///
     135             : /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator
     136             : /// object, which wraps malloc, to allocate memory, but it can be changed to
     137             : /// use a custom allocator.
     138             : template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
     139             :           size_t SizeThreshold = SlabSize>
     140             : class BumpPtrAllocatorImpl
     141             :     : public AllocatorBase<
     142             :           BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
     143             : public:
     144             :   static_assert(SizeThreshold <= SlabSize,
     145             :                 "The SizeThreshold must be at most the SlabSize to ensure "
     146             :                 "that objects larger than a slab go into their own memory "
     147             :                 "allocation.");
     148             : 
     149    32408983 :   BumpPtrAllocatorImpl() = default;
     150             : 
     151             :   template <typename T>
     152             :   BumpPtrAllocatorImpl(T &&Allocator)
     153             :       : Allocator(std::forward<T &&>(Allocator)) {}
     154             : 
     155             :   // Manually implement a move constructor as we must clear the old allocator's
     156             :   // slabs as a matter of correctness.
     157        7219 :   BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
     158       14438 :       : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
     159             :         CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
     160       14438 :         BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize),
     161       28876 :         Allocator(std::move(Old.Allocator)) {
     162        7219 :     Old.CurPtr = Old.End = nullptr;
     163        7219 :     Old.BytesAllocated = 0;
     164             :     Old.Slabs.clear();
     165             :     Old.CustomSizedSlabs.clear();
     166        7219 :   }
     167             : 
     168    15891870 :   ~BumpPtrAllocatorImpl() {
     169    15891870 :     DeallocateSlabs(Slabs.begin(), Slabs.end());
     170             :     DeallocateCustomSizedSlabs();
     171    15891870 :   }
     172             : 
     173         197 :   BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) {
     174         197 :     DeallocateSlabs(Slabs.begin(), Slabs.end());
     175             :     DeallocateCustomSizedSlabs();
     176             : 
     177         197 :     CurPtr = RHS.CurPtr;
     178         197 :     End = RHS.End;
     179         197 :     BytesAllocated = RHS.BytesAllocated;
     180         197 :     RedZoneSize = RHS.RedZoneSize;
     181             :     Slabs = std::move(RHS.Slabs);
     182             :     CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
     183             :     Allocator = std::move(RHS.Allocator);
     184             : 
     185         197 :     RHS.CurPtr = RHS.End = nullptr;
     186         197 :     RHS.BytesAllocated = 0;
     187             :     RHS.Slabs.clear();
     188             :     RHS.CustomSizedSlabs.clear();
     189         197 :     return *this;
     190             :   }
     191             : 
     192             :   /// Deallocate all but the current slab and reset the current pointer
     193             :   /// to the beginning of it, freeing all memory allocated so far.
     194     9850132 :   void Reset() {
     195             :     // Deallocate all but the first slab, and deallocate all custom-sized slabs.
     196             :     DeallocateCustomSizedSlabs();
     197             :     CustomSizedSlabs.clear();
     198             : 
     199     9850132 :     if (Slabs.empty())
     200             :       return;
     201             : 
     202             :     // Reset the state.
     203     2954774 :     BytesAllocated = 0;
     204     2954774 :     CurPtr = (char *)Slabs.front();
     205     2954774 :     End = CurPtr + SlabSize;
     206             : 
     207             :     __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0));
     208     2954774 :     DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
     209             :     Slabs.erase(std::next(Slabs.begin()), Slabs.end());
     210             :   }
     211             : 
     212             :   /// Allocate space at the specified alignment.
     213             :   LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
     214   588628508 :   Allocate(size_t Size, size_t Alignment) {
     215             :     assert(Alignment > 0 && "0-byte alignnment is not allowed. Use 1 instead.");
     216             : 
     217             :     // Keep track of how many bytes we've allocated.
     218   588628508 :     BytesAllocated += Size;
     219             : 
     220   588628508 :     size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
     221             :     assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
     222             : 
     223             :     size_t SizeToAllocate = Size;
     224             : #if LLVM_ADDRESS_SANITIZER_BUILD
     225             :     // Add trailing bytes as a "red zone" under ASan.
     226             :     SizeToAllocate += RedZoneSize;
     227             : #endif
     228             : 
     229             :     // Check if we have enough space.
     230   588628508 :     if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) {
     231   580699184 :       char *AlignedPtr = CurPtr + Adjustment;
     232   580699184 :       CurPtr = AlignedPtr + SizeToAllocate;
     233             :       // Update the allocation point of this memory block in MemorySanitizer.
     234             :       // Without this, MemorySanitizer messages for values originated from here
     235             :       // will point to the allocation of the entire slab.
     236             :       __msan_allocated_memory(AlignedPtr, Size);
     237             :       // Similarly, tell ASan about this space.
     238             :       __asan_unpoison_memory_region(AlignedPtr, Size);
     239   580699184 :       return AlignedPtr;
     240             :     }
     241             : 
     242             :     // If Size is really big, allocate a separate slab for it.
     243     7929324 :     size_t PaddedSize = SizeToAllocate + Alignment - 1;
     244     7929324 :     if (PaddedSize > SizeThreshold) {
     245             :       void *NewSlab = Allocator.Allocate(PaddedSize, 0);
     246             :       // We own the new slab and don't want anyone reading anyting other than
     247             :       // pieces returned from this method.  So poison the whole slab.
     248             :       __asan_poison_memory_region(NewSlab, PaddedSize);
     249       16350 :       CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
     250             : 
     251             :       uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
     252             :       assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
     253       16350 :       char *AlignedPtr = (char*)AlignedAddr;
     254             :       __msan_allocated_memory(AlignedPtr, Size);
     255             :       __asan_unpoison_memory_region(AlignedPtr, Size);
     256             :       return AlignedPtr;
     257             :     }
     258             : 
     259             :     // Otherwise, start a new slab and try again.
     260     7912974 :     StartNewSlab();
     261     7912975 :     uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
     262             :     assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&
     263             :            "Unable to allocate memory!");
     264     7912975 :     char *AlignedPtr = (char*)AlignedAddr;
     265     7912975 :     CurPtr = AlignedPtr + SizeToAllocate;
     266             :     __msan_allocated_memory(AlignedPtr, Size);
     267             :     __asan_unpoison_memory_region(AlignedPtr, Size);
     268     7912975 :     return AlignedPtr;
     269             :   }
     270             : 
     271             :   // Pull in base class overloads.
     272             :   using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
     273             : 
     274             :   // Bump pointer allocators are expected to never free their storage; and
     275             :   // clients expect pointers to remain valid for non-dereferencing uses even
     276             :   // after deallocation.
     277             :   void Deallocate(const void *Ptr, size_t Size) {
     278             :     __asan_poison_memory_region(Ptr, Size);
     279             :   }
     280             : 
     281             :   // Pull in base class overloads.
     282             :   using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
     283             : 
     284          18 :   size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
     285             : 
     286          24 :   size_t getTotalMemory() const {
     287             :     size_t TotalMemory = 0;
     288         464 :     for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
     289         440 :       TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
     290          24 :     for (auto &PtrAndSize : CustomSizedSlabs)
     291           0 :       TotalMemory += PtrAndSize.second;
     292          24 :     return TotalMemory;
     293             :   }
     294             : 
     295             :   size_t getBytesAllocated() const { return BytesAllocated; }
     296             : 
     297             :   void setRedZoneSize(size_t NewSize) {
     298      503655 :     RedZoneSize = NewSize;
     299             :   }
     300             : 
     301           9 :   void PrintStats() const {
     302          18 :     detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
     303             :                                        getTotalMemory());
     304           9 :   }
     305             : 
     306             : private:
     307             :   /// The current pointer into the current slab.
     308             :   ///
     309             :   /// This points to the next free byte in the slab.
     310             :   char *CurPtr = nullptr;
     311             : 
     312             :   /// The end of the current slab.
     313             :   char *End = nullptr;
     314             : 
     315             :   /// The slabs allocated so far.
     316             :   SmallVector<void *, 4> Slabs;
     317             : 
     318             :   /// Custom-sized slabs allocated for too-large allocation requests.
     319             :   SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
     320             : 
     321             :   /// How many bytes we've allocated.
     322             :   ///
     323             :   /// Used so that we can compute how much space was wasted.
     324             :   size_t BytesAllocated = 0;
     325             : 
     326             :   /// The number of bytes to put between allocations when running under
     327             :   /// a sanitizer.
     328             :   size_t RedZoneSize = 1;
     329             : 
     330             :   /// The allocator instance we use to get slabs of memory.
     331             :   AllocatorT Allocator;
     332             : 
     333             :   static size_t computeSlabSize(unsigned SlabIdx) {
     334             :     // Scale the actual allocated slab size based on the number of slabs
     335             :     // allocated. Every 128 slabs allocated, we double the allocated size to
     336             :     // reduce allocation frequency, but saturate at multiplying the slab size by
     337             :     // 2^30.
     338    23903226 :     return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
     339             :   }
     340             : 
     341             :   /// Allocate a new slab and move the bump pointers over into the new
     342             :   /// slab, modifying CurPtr and End.
     343     7912973 :   void StartNewSlab() {
     344     7912973 :     size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
     345             : 
     346     7912975 :     void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
     347             :     // We own the new slab and don't want anyone reading anything other than
     348             :     // pieces returned from this method.  So poison the whole slab.
     349             :     __asan_poison_memory_region(NewSlab, AllocatedSlabSize);
     350             : 
     351     7912975 :     Slabs.push_back(NewSlab);
     352     7912975 :     CurPtr = (char *)(NewSlab);
     353     7912975 :     End = ((char *)NewSlab) + AllocatedSlabSize;
     354     7912975 :   }
     355             : 
     356             :   /// Deallocate a sequence of slabs.
     357    18846840 :   void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
     358             :                        SmallVectorImpl<void *>::iterator E) {
     359    31899812 :     for (; I != E; ++I) {
     360             :       size_t AllocatedSlabSize =
     361     6526486 :           computeSlabSize(std::distance(Slabs.begin(), I));
     362     6526486 :       Allocator.Deallocate(*I, AllocatedSlabSize);
     363             :     }
     364    18846840 :   }
     365             : 
     366             :   /// Deallocate all memory for custom sized slabs.
     367             :   void DeallocateCustomSizedSlabs() {
     368    25763069 :     for (auto &PtrAndSize : CustomSizedSlabs) {
     369       10435 :       void *Ptr = PtrAndSize.first;
     370             :       size_t Size = PtrAndSize.second;
     371             :       Allocator.Deallocate(Ptr, Size);
     372             :     }
     373             :   }
     374             : 
     375             :   template <typename T> friend class SpecificBumpPtrAllocator;
     376             : };
     377             : 
     378             : /// The standard BumpPtrAllocator which just uses the default template
     379             : /// parameters.
     380             : typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
     381             : 
     382             : /// A BumpPtrAllocator that allows only elements of a specific type to be
     383             : /// allocated.
     384             : ///
     385             : /// This allows calling the destructor in DestroyAll() and when the allocator is
     386             : /// destroyed.
     387             : template <typename T> class SpecificBumpPtrAllocator {
     388             :   BumpPtrAllocator Allocator;
     389             : 
     390             : public:
     391      503655 :   SpecificBumpPtrAllocator() {
     392             :     // Because SpecificBumpPtrAllocator walks the memory to call destructors,
     393             :     // it can't have red zones between allocations.
     394             :     Allocator.setRedZoneSize(0);
     395             :   }
     396        1088 :   SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old)
     397        1088 :       : Allocator(std::move(Old.Allocator)) {}
     398      503330 :   ~SpecificBumpPtrAllocator() { DestroyAll(); }
     399             : 
     400             :   SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) {
     401           0 :     Allocator = std::move(RHS.Allocator);
     402             :     return *this;
     403             :   }
     404             : 
     405             :   /// Call the destructor of each allocated object and deallocate all but the
     406             :   /// current slab and reset the current pointer to the beginning of it, freeing
     407             :   /// all memory allocated so far.
     408      843014 :   void DestroyAll() {
     409        4718 :     auto DestroyElements = [](char *Begin, char *End) {
     410             :       assert(Begin == (char *)alignAddr(Begin, alignof(T)));
     411     9074161 :       for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
     412     4537033 :         reinterpret_cast<T *>(Ptr)->~T();
     413        4718 :     };
     414             : 
     415     2475200 :     for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
     416             :          ++I) {
     417      816093 :       size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
     418             :           std::distance(Allocator.Slabs.begin(), I));
     419     1468522 :       char *Begin = (char *)alignAddr(*I, alignof(T));
     420      734261 :       char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
     421             :                                                : (char *)*I + AllocatedSlabSize;
     422             : 
     423        4718 :       DestroyElements(Begin, End);
     424             :     }
     425             : 
     426      799015 :     for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
     427           0 :       void *Ptr = PtrAndSize.first;
     428           0 :       size_t Size = PtrAndSize.second;
     429           0 :       DestroyElements((char *)alignAddr(Ptr, alignof(T)), (char *)Ptr + Size);
     430             :     }
     431             : 
     432      843014 :     Allocator.Reset();
     433      843014 :   }
     434             : 
     435             :   /// Allocate space for an array of objects without constructing them.
     436    12965657 :   T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
     437             : };
     438             : 
     439             : } // end namespace llvm
     440             : 
     441             : template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
     442             : void *operator new(size_t Size,
     443             :                    llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
     444             :                                               SizeThreshold> &Allocator) {
     445             :   struct S {
     446             :     char c;
     447             :     union {
     448             :       double D;
     449             :       long double LD;
     450             :       long long L;
     451             :       void *P;
     452             :     } x;
     453             :   };
     454             :   return Allocator.Allocate(
     455    65327888 :       Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
     456             : }
     457             : 
     458             : template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
     459             : void operator delete(
     460             :     void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) {
     461             : }
     462             : 
     463             : #endif // LLVM_SUPPORT_ALLOCATOR_H

Generated by: LCOV version 1.13