1 //===- Allocator.h - Simple memory allocation abstraction -------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
10 /// This file defines the MallocAllocator and BumpPtrAllocator interfaces. Both
11 /// of these conform to an LLVM "Allocator" concept which consists of an
12 /// Allocate method accepting a size and alignment, and a Deallocate accepting
13 /// a pointer and size. Further, the LLVM "Allocator" concept has overloads of
14 /// Allocate and Deallocate for setting size and alignment based on the final
15 /// type. These overloads are typically provided by a base class template \c
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_SUPPORT_ALLOCATOR_H
21 #define LLVM_SUPPORT_ALLOCATOR_H
23 #include "llvm/ADT/Optional.h"
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"
35 #include <type_traits>
40 /// CRTP base class providing obvious overloads for the core \c
41 /// Allocate() methods of LLVM-style allocators.
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
{
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
) {
52 static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
53 &AllocatorBase::Allocate
) !=
54 static_cast<void *(DerivedT::*)(size_t, size_t)>(
56 "Class derives from AllocatorBase without implementing the "
57 "core Allocate(size_t, size_t) overload!");
59 return static_cast<DerivedT
*>(this)->Allocate(Size
, Alignment
);
62 /// Deallocate \a Ptr to \a Size bytes of memory allocated by this
64 void Deallocate(const void *Ptr
, size_t Size
) {
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!");
73 return static_cast<DerivedT
*>(this)->Deallocate(Ptr
, Size
);
76 // The rest of these methods are helpers that redirect to one of the above
79 /// Allocate space for a sequence of objects without constructing them.
80 template <typename T
> T
*Allocate(size_t Num
= 1) {
81 return static_cast<T
*>(Allocate(Num
* sizeof(T
), alignof(T
)));
84 /// Deallocate space for a sequence of objects without constructing them.
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
));
93 class MallocAllocator
: public AllocatorBase
<MallocAllocator
> {
97 LLVM_ATTRIBUTE_RETURNS_NONNULL
void *Allocate(size_t Size
,
98 size_t /*Alignment*/) {
99 return safe_malloc(Size
);
102 // Pull in base class overloads.
103 using AllocatorBase
<MallocAllocator
>::Allocate
;
105 void Deallocate(const void *Ptr
, size_t /*Size*/) {
106 free(const_cast<void *>(Ptr
));
109 // Pull in base class overloads.
110 using AllocatorBase
<MallocAllocator
>::Deallocate
;
112 void PrintStats() const {}
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
,
122 } // end namespace detail
124 /// Allocate memory in an ever growing pool, as if by bump-pointer.
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.
132 /// Note that this also has a threshold for forcing allocations above a certain
133 /// size into their own slab.
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
>> {
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 "
149 BumpPtrAllocatorImpl() = default;
151 template <typename T
>
152 BumpPtrAllocatorImpl(T
&&Allocator
)
153 : Allocator(std::forward
<T
&&>(Allocator
)) {}
155 // Manually implement a move constructor as we must clear the old allocator's
156 // slabs as a matter of correctness.
157 BumpPtrAllocatorImpl(BumpPtrAllocatorImpl
&&Old
)
158 : CurPtr(Old
.CurPtr
), End(Old
.End
), Slabs(std::move(Old
.Slabs
)),
159 CustomSizedSlabs(std::move(Old
.CustomSizedSlabs
)),
160 BytesAllocated(Old
.BytesAllocated
), RedZoneSize(Old
.RedZoneSize
),
161 Allocator(std::move(Old
.Allocator
)) {
162 Old
.CurPtr
= Old
.End
= nullptr;
163 Old
.BytesAllocated
= 0;
165 Old
.CustomSizedSlabs
.clear();
168 ~BumpPtrAllocatorImpl() {
169 DeallocateSlabs(Slabs
.begin(), Slabs
.end());
170 DeallocateCustomSizedSlabs();
173 BumpPtrAllocatorImpl
&operator=(BumpPtrAllocatorImpl
&&RHS
) {
174 DeallocateSlabs(Slabs
.begin(), Slabs
.end());
175 DeallocateCustomSizedSlabs();
179 BytesAllocated
= RHS
.BytesAllocated
;
180 RedZoneSize
= RHS
.RedZoneSize
;
181 Slabs
= std::move(RHS
.Slabs
);
182 CustomSizedSlabs
= std::move(RHS
.CustomSizedSlabs
);
183 Allocator
= std::move(RHS
.Allocator
);
185 RHS
.CurPtr
= RHS
.End
= nullptr;
186 RHS
.BytesAllocated
= 0;
188 RHS
.CustomSizedSlabs
.clear();
192 /// Deallocate all but the current slab and reset the current pointer
193 /// to the beginning of it, freeing all memory allocated so far.
195 // Deallocate all but the first slab, and deallocate all custom-sized slabs.
196 DeallocateCustomSizedSlabs();
197 CustomSizedSlabs
.clear();
204 CurPtr
= (char *)Slabs
.front();
205 End
= CurPtr
+ SlabSize
;
207 __asan_poison_memory_region(*Slabs
.begin(), computeSlabSize(0));
208 DeallocateSlabs(std::next(Slabs
.begin()), Slabs
.end());
209 Slabs
.erase(std::next(Slabs
.begin()), Slabs
.end());
212 /// Allocate space at the specified alignment.
213 LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS
void *
214 Allocate(size_t Size
, size_t Alignment
) {
215 assert(Alignment
> 0 && "0-byte alignnment is not allowed. Use 1 instead.");
217 // Keep track of how many bytes we've allocated.
218 BytesAllocated
+= Size
;
220 size_t Adjustment
= alignmentAdjustment(CurPtr
, Alignment
);
221 assert(Adjustment
+ Size
>= Size
&& "Adjustment + Size must not overflow");
223 size_t SizeToAllocate
= Size
;
224 #if LLVM_ADDRESS_SANITIZER_BUILD
225 // Add trailing bytes as a "red zone" under ASan.
226 SizeToAllocate
+= RedZoneSize
;
229 // Check if we have enough space.
230 if (Adjustment
+ SizeToAllocate
<= size_t(End
- CurPtr
)) {
231 char *AlignedPtr
= CurPtr
+ Adjustment
;
232 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
);
242 // If Size is really big, allocate a separate slab for it.
243 size_t PaddedSize
= SizeToAllocate
+ Alignment
- 1;
244 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 CustomSizedSlabs
.push_back(std::make_pair(NewSlab
, PaddedSize
));
251 uintptr_t AlignedAddr
= alignAddr(NewSlab
, Alignment
);
252 assert(AlignedAddr
+ Size
<= (uintptr_t)NewSlab
+ PaddedSize
);
253 char *AlignedPtr
= (char*)AlignedAddr
;
254 __msan_allocated_memory(AlignedPtr
, Size
);
255 __asan_unpoison_memory_region(AlignedPtr
, Size
);
259 // Otherwise, start a new slab and try again.
261 uintptr_t AlignedAddr
= alignAddr(CurPtr
, Alignment
);
262 assert(AlignedAddr
+ SizeToAllocate
<= (uintptr_t)End
&&
263 "Unable to allocate memory!");
264 char *AlignedPtr
= (char*)AlignedAddr
;
265 CurPtr
= AlignedPtr
+ SizeToAllocate
;
266 __msan_allocated_memory(AlignedPtr
, Size
);
267 __asan_unpoison_memory_region(AlignedPtr
, Size
);
271 // Pull in base class overloads.
272 using AllocatorBase
<BumpPtrAllocatorImpl
>::Allocate
;
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
);
281 // Pull in base class overloads.
282 using AllocatorBase
<BumpPtrAllocatorImpl
>::Deallocate
;
284 size_t GetNumSlabs() const { return Slabs
.size() + CustomSizedSlabs
.size(); }
286 /// \return An index uniquely and reproducibly identifying
287 /// an input pointer \p Ptr in the given allocator.
288 /// The returned value is negative iff the object is inside a custom-size
290 /// Returns an empty optional if the pointer is not found in the allocator.
291 llvm::Optional
<int64_t> identifyObject(const void *Ptr
) {
292 const char *P
= static_cast<const char *>(Ptr
);
293 int64_t InSlabIdx
= 0;
294 for (size_t Idx
= 0, E
= Slabs
.size(); Idx
< E
; Idx
++) {
295 const char *S
= static_cast<const char *>(Slabs
[Idx
]);
296 if (P
>= S
&& P
< S
+ computeSlabSize(Idx
))
297 return InSlabIdx
+ static_cast<int64_t>(P
- S
);
298 InSlabIdx
+= static_cast<int64_t>(computeSlabSize(Idx
));
301 // Use negative index to denote custom sized slabs.
302 int64_t InCustomSizedSlabIdx
= -1;
303 for (size_t Idx
= 0, E
= CustomSizedSlabs
.size(); Idx
< E
; Idx
++) {
304 const char *S
= static_cast<const char *>(CustomSizedSlabs
[Idx
].first
);
305 size_t Size
= CustomSizedSlabs
[Idx
].second
;
306 if (P
>= S
&& P
< S
+ Size
)
307 return InCustomSizedSlabIdx
- static_cast<int64_t>(P
- S
);
308 InCustomSizedSlabIdx
-= static_cast<int64_t>(Size
);
313 /// A wrapper around identifyObject that additionally asserts that
314 /// the object is indeed within the allocator.
315 /// \return An index uniquely and reproducibly identifying
316 /// an input pointer \p Ptr in the given allocator.
317 int64_t identifyKnownObject(const void *Ptr
) {
318 Optional
<int64_t> Out
= identifyObject(Ptr
);
319 assert(Out
&& "Wrong allocator used");
323 /// A wrapper around identifyKnownObject. Accepts type information
324 /// about the object and produces a smaller identifier by relying on
325 /// the alignment information. Note that sub-classes may have different
326 /// alignment, so the most base class should be passed as template parameter
327 /// in order to obtain correct results. For that reason automatic template
328 /// parameter deduction is disabled.
329 /// \return An index uniquely and reproducibly identifying
330 /// an input pointer \p Ptr in the given allocator. This identifier is
331 /// different from the ones produced by identifyObject and
332 /// identifyAlignedObject.
333 template <typename T
>
334 int64_t identifyKnownAlignedObject(const void *Ptr
) {
335 int64_t Out
= identifyKnownObject(Ptr
);
336 assert(Out
% alignof(T
) == 0 && "Wrong alignment information");
337 return Out
/ alignof(T
);
340 size_t getTotalMemory() const {
341 size_t TotalMemory
= 0;
342 for (auto I
= Slabs
.begin(), E
= Slabs
.end(); I
!= E
; ++I
)
343 TotalMemory
+= computeSlabSize(std::distance(Slabs
.begin(), I
));
344 for (auto &PtrAndSize
: CustomSizedSlabs
)
345 TotalMemory
+= PtrAndSize
.second
;
349 size_t getBytesAllocated() const { return BytesAllocated
; }
351 void setRedZoneSize(size_t NewSize
) {
352 RedZoneSize
= NewSize
;
355 void PrintStats() const {
356 detail::printBumpPtrAllocatorStats(Slabs
.size(), BytesAllocated
,
361 /// The current pointer into the current slab.
363 /// This points to the next free byte in the slab.
364 char *CurPtr
= nullptr;
366 /// The end of the current slab.
369 /// The slabs allocated so far.
370 SmallVector
<void *, 4> Slabs
;
372 /// Custom-sized slabs allocated for too-large allocation requests.
373 SmallVector
<std::pair
<void *, size_t>, 0> CustomSizedSlabs
;
375 /// How many bytes we've allocated.
377 /// Used so that we can compute how much space was wasted.
378 size_t BytesAllocated
= 0;
380 /// The number of bytes to put between allocations when running under
382 size_t RedZoneSize
= 1;
384 /// The allocator instance we use to get slabs of memory.
385 AllocatorT Allocator
;
387 static size_t computeSlabSize(unsigned SlabIdx
) {
388 // Scale the actual allocated slab size based on the number of slabs
389 // allocated. Every 128 slabs allocated, we double the allocated size to
390 // reduce allocation frequency, but saturate at multiplying the slab size by
392 return SlabSize
* ((size_t)1 << std::min
<size_t>(30, SlabIdx
/ 128));
395 /// Allocate a new slab and move the bump pointers over into the new
396 /// slab, modifying CurPtr and End.
397 void StartNewSlab() {
398 size_t AllocatedSlabSize
= computeSlabSize(Slabs
.size());
400 void *NewSlab
= Allocator
.Allocate(AllocatedSlabSize
, 0);
401 // We own the new slab and don't want anyone reading anything other than
402 // pieces returned from this method. So poison the whole slab.
403 __asan_poison_memory_region(NewSlab
, AllocatedSlabSize
);
405 Slabs
.push_back(NewSlab
);
406 CurPtr
= (char *)(NewSlab
);
407 End
= ((char *)NewSlab
) + AllocatedSlabSize
;
410 /// Deallocate a sequence of slabs.
411 void DeallocateSlabs(SmallVectorImpl
<void *>::iterator I
,
412 SmallVectorImpl
<void *>::iterator E
) {
413 for (; I
!= E
; ++I
) {
414 size_t AllocatedSlabSize
=
415 computeSlabSize(std::distance(Slabs
.begin(), I
));
416 Allocator
.Deallocate(*I
, AllocatedSlabSize
);
420 /// Deallocate all memory for custom sized slabs.
421 void DeallocateCustomSizedSlabs() {
422 for (auto &PtrAndSize
: CustomSizedSlabs
) {
423 void *Ptr
= PtrAndSize
.first
;
424 size_t Size
= PtrAndSize
.second
;
425 Allocator
.Deallocate(Ptr
, Size
);
429 template <typename T
> friend class SpecificBumpPtrAllocator
;
432 /// The standard BumpPtrAllocator which just uses the default template
434 typedef BumpPtrAllocatorImpl
<> BumpPtrAllocator
;
436 /// A BumpPtrAllocator that allows only elements of a specific type to be
439 /// This allows calling the destructor in DestroyAll() and when the allocator is
441 template <typename T
> class SpecificBumpPtrAllocator
{
442 BumpPtrAllocator Allocator
;
445 SpecificBumpPtrAllocator() {
446 // Because SpecificBumpPtrAllocator walks the memory to call destructors,
447 // it can't have red zones between allocations.
448 Allocator
.setRedZoneSize(0);
450 SpecificBumpPtrAllocator(SpecificBumpPtrAllocator
&&Old
)
451 : Allocator(std::move(Old
.Allocator
)) {}
452 ~SpecificBumpPtrAllocator() { DestroyAll(); }
454 SpecificBumpPtrAllocator
&operator=(SpecificBumpPtrAllocator
&&RHS
) {
455 Allocator
= std::move(RHS
.Allocator
);
459 /// Call the destructor of each allocated object and deallocate all but the
460 /// current slab and reset the current pointer to the beginning of it, freeing
461 /// all memory allocated so far.
463 auto DestroyElements
= [](char *Begin
, char *End
) {
464 assert(Begin
== (char *)alignAddr(Begin
, alignof(T
)));
465 for (char *Ptr
= Begin
; Ptr
+ sizeof(T
) <= End
; Ptr
+= sizeof(T
))
466 reinterpret_cast<T
*>(Ptr
)->~T();
469 for (auto I
= Allocator
.Slabs
.begin(), E
= Allocator
.Slabs
.end(); I
!= E
;
471 size_t AllocatedSlabSize
= BumpPtrAllocator::computeSlabSize(
472 std::distance(Allocator
.Slabs
.begin(), I
));
473 char *Begin
= (char *)alignAddr(*I
, alignof(T
));
474 char *End
= *I
== Allocator
.Slabs
.back() ? Allocator
.CurPtr
475 : (char *)*I
+ AllocatedSlabSize
;
477 DestroyElements(Begin
, End
);
480 for (auto &PtrAndSize
: Allocator
.CustomSizedSlabs
) {
481 void *Ptr
= PtrAndSize
.first
;
482 size_t Size
= PtrAndSize
.second
;
483 DestroyElements((char *)alignAddr(Ptr
, alignof(T
)), (char *)Ptr
+ Size
);
489 /// Allocate space for an array of objects without constructing them.
490 T
*Allocate(size_t num
= 1) { return Allocator
.Allocate
<T
>(num
); }
493 } // end namespace llvm
495 template <typename AllocatorT
, size_t SlabSize
, size_t SizeThreshold
>
496 void *operator new(size_t Size
,
497 llvm::BumpPtrAllocatorImpl
<AllocatorT
, SlabSize
,
498 SizeThreshold
> &Allocator
) {
508 return Allocator
.Allocate(
509 Size
, std::min((size_t)llvm::NextPowerOf2(Size
), offsetof(S
, x
)));
512 template <typename AllocatorT
, size_t SlabSize
, size_t SizeThreshold
>
513 void operator delete(
514 void *, llvm::BumpPtrAllocatorImpl
<AllocatorT
, SlabSize
, SizeThreshold
> &) {
517 #endif // LLVM_SUPPORT_ALLOCATOR_H