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/AlignOf.h"
26 : #include "llvm/Support/DataTypes.h"
27 : #include "llvm/Support/MathExtras.h"
28 : #include "llvm/Support/Memory.h"
29 : #include <algorithm>
30 : #include <cassert>
31 : #include <cstddef>
32 : #include <cstdlib>
33 :
34 : namespace llvm {
35 :
36 : /// \brief CRTP base class providing obvious overloads for the core \c
37 : /// Allocate() methods of LLVM-style allocators.
38 : ///
39 : /// This base class both documents the full public interface exposed by all
40 : /// LLVM-style allocators, and redirects all of the overloads to a single core
41 : /// set of methods which the derived class must define.
42 : template <typename DerivedT> class AllocatorBase {
43 : public:
44 : /// \brief Allocate \a Size bytes of \a Alignment aligned memory. This method
45 : /// must be implemented by \c DerivedT.
46 : void *Allocate(size_t Size, size_t Alignment) {
47 : #ifdef __clang__
48 : static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
49 : &AllocatorBase::Allocate) !=
50 : static_cast<void *(DerivedT::*)(size_t, size_t)>(
51 : &DerivedT::Allocate),
52 : "Class derives from AllocatorBase without implementing the "
53 : "core Allocate(size_t, size_t) overload!");
54 : #endif
55 : return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
56 : }
57 :
58 : /// \brief Deallocate \a Ptr to \a Size bytes of memory allocated by this
59 : /// allocator.
60 : void Deallocate(const void *Ptr, size_t Size) {
61 : #ifdef __clang__
62 : static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>(
63 : &AllocatorBase::Deallocate) !=
64 : static_cast<void (DerivedT::*)(const void *, size_t)>(
65 : &DerivedT::Deallocate),
66 : "Class derives from AllocatorBase without implementing the "
67 : "core Deallocate(void *) overload!");
68 : #endif
69 : return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size);
70 : }
71 :
72 : // The rest of these methods are helpers that redirect to one of the above
73 : // core methods.
74 :
75 : /// \brief Allocate space for a sequence of objects without constructing them.
76 : template <typename T> T *Allocate(size_t Num = 1) {
77 : return static_cast<T *>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
78 : }
79 :
80 : /// \brief Deallocate space for a sequence of objects without constructing them.
81 : template <typename T>
82 : typename std::enable_if<
83 : !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type
84 : Deallocate(T *Ptr, size_t Num = 1) {
85 : Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T));
86 : }
87 : };
88 :
89 : class MallocAllocator : public AllocatorBase<MallocAllocator> {
90 : public:
91 : void Reset() {}
92 :
93 : LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size,
94 : size_t /*Alignment*/) {
95 0 : return malloc(Size);
96 : }
97 :
98 : // Pull in base class overloads.
99 : using AllocatorBase<MallocAllocator>::Allocate;
100 :
101 : void Deallocate(const void *Ptr, size_t /*Size*/) {
102 24 : free(const_cast<void *>(Ptr));
103 24 : }
104 :
105 : // Pull in base class overloads.
106 : using AllocatorBase<MallocAllocator>::Deallocate;
107 :
108 : void PrintStats() const {}
109 : };
110 :
111 : namespace detail {
112 :
113 : // We call out to an external function to actually print the message as the
114 : // printing code uses Allocator.h in its implementation.
115 : void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
116 : size_t TotalMemory);
117 : } // End namespace detail.
118 :
119 : /// \brief Allocate memory in an ever growing pool, as if by bump-pointer.
120 : ///
121 : /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
122 : /// memory rather than relying on a boundless contiguous heap. However, it has
123 : /// bump-pointer semantics in that it is a monotonically growing pool of memory
124 : /// where every allocation is found by merely allocating the next N bytes in
125 : /// the slab, or the next N bytes in the next slab.
126 : ///
127 : /// Note that this also has a threshold for forcing allocations above a certain
128 : /// size into their own slab.
129 : ///
130 : /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator
131 : /// object, which wraps malloc, to allocate memory, but it can be changed to
132 : /// use a custom allocator.
133 : template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
134 : size_t SizeThreshold = SlabSize>
135 : class BumpPtrAllocatorImpl
136 : : public AllocatorBase<
137 : BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
138 : public:
139 : static_assert(SizeThreshold <= SlabSize,
140 : "The SizeThreshold must be at most the SlabSize to ensure "
141 : "that objects larger than a slab go into their own memory "
142 : "allocation.");
143 :
144 : BumpPtrAllocatorImpl()
145 : : CurPtr(nullptr), End(nullptr), BytesAllocated(0), Allocator() {}
146 : template <typename T>
147 : BumpPtrAllocatorImpl(T &&Allocator)
148 : : CurPtr(nullptr), End(nullptr), BytesAllocated(0),
149 : Allocator(std::forward<T &&>(Allocator)) {}
150 :
151 : // Manually implement a move constructor as we must clear the old allocator's
152 : // slabs as a matter of correctness.
153 : BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
154 : : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
155 : CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
156 : BytesAllocated(Old.BytesAllocated),
157 : Allocator(std::move(Old.Allocator)) {
158 : Old.CurPtr = Old.End = nullptr;
159 : Old.BytesAllocated = 0;
160 : Old.Slabs.clear();
161 : Old.CustomSizedSlabs.clear();
162 : }
163 :
164 : ~BumpPtrAllocatorImpl() {
165 : DeallocateSlabs(Slabs.begin(), Slabs.end());
166 : DeallocateCustomSizedSlabs();
167 : }
168 :
169 : BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) {
170 : DeallocateSlabs(Slabs.begin(), Slabs.end());
171 : DeallocateCustomSizedSlabs();
172 :
173 : CurPtr = RHS.CurPtr;
174 : End = RHS.End;
175 : BytesAllocated = RHS.BytesAllocated;
176 : Slabs = std::move(RHS.Slabs);
177 : CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
178 : Allocator = std::move(RHS.Allocator);
179 :
180 : RHS.CurPtr = RHS.End = nullptr;
181 : RHS.BytesAllocated = 0;
182 : RHS.Slabs.clear();
183 : RHS.CustomSizedSlabs.clear();
184 : return *this;
185 : }
186 :
187 : /// \brief Deallocate all but the current slab and reset the current pointer
188 : /// to the beginning of it, freeing all memory allocated so far.
189 : void Reset() {
190 : DeallocateCustomSizedSlabs();
191 : CustomSizedSlabs.clear();
192 :
193 : if (Slabs.empty())
194 : return;
195 :
196 : // Reset the state.
197 : BytesAllocated = 0;
198 : CurPtr = (char *)Slabs.front();
199 : End = CurPtr + SlabSize;
200 :
201 : // Deallocate all but the first slab, and deallocate all custom-sized slabs.
202 : DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
203 : Slabs.erase(std::next(Slabs.begin()), Slabs.end());
204 : }
205 :
206 : /// \brief Allocate space at the specified alignment.
207 : LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void *
208 : Allocate(size_t Size, size_t Alignment) {
209 0 : assert(Alignment > 0 && "0-byte alignnment is not allowed. Use 1 instead.");
210 :
211 : // Keep track of how many bytes we've allocated.
212 0 : BytesAllocated += Size;
213 :
214 0 : size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
215 0 : assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
216 :
217 : // Check if we have enough space.
218 0 : if (Adjustment + Size <= size_t(End - CurPtr)) {
219 0 : char *AlignedPtr = CurPtr + Adjustment;
220 0 : CurPtr = AlignedPtr + Size;
221 : // Update the allocation point of this memory block in MemorySanitizer.
222 : // Without this, MemorySanitizer messages for values originated from here
223 : // will point to the allocation of the entire slab.
224 : __msan_allocated_memory(AlignedPtr, Size);
225 0 : return AlignedPtr;
226 : }
227 :
228 : // If Size is really big, allocate a separate slab for it.
229 0 : size_t PaddedSize = Size + Alignment - 1;
230 0 : if (PaddedSize > SizeThreshold) {
231 0 : void *NewSlab = Allocator.Allocate(PaddedSize, 0);
232 0 : CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
233 :
234 0 : uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
235 0 : assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
236 0 : char *AlignedPtr = (char*)AlignedAddr;
237 : __msan_allocated_memory(AlignedPtr, Size);
238 0 : return AlignedPtr;
239 : }
240 :
241 : // Otherwise, start a new slab and try again.
242 0 : StartNewSlab();
243 0 : uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
244 0 : assert(AlignedAddr + Size <= (uintptr_t)End &&
245 : "Unable to allocate memory!");
246 0 : char *AlignedPtr = (char*)AlignedAddr;
247 0 : CurPtr = AlignedPtr + Size;
248 : __msan_allocated_memory(AlignedPtr, Size);
249 0 : return AlignedPtr;
250 0 : }
251 :
252 : // Pull in base class overloads.
253 : using AllocatorBase<BumpPtrAllocatorImpl>::Allocate;
254 :
255 : void Deallocate(const void * /*Ptr*/, size_t /*Size*/) {}
256 :
257 : // Pull in base class overloads.
258 : using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
259 :
260 : size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
261 :
262 : size_t getTotalMemory() const {
263 : size_t TotalMemory = 0;
264 : for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
265 : TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
266 : for (auto &PtrAndSize : CustomSizedSlabs)
267 : TotalMemory += PtrAndSize.second;
268 : return TotalMemory;
269 : }
270 :
271 : void PrintStats() const {
272 : detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
273 : getTotalMemory());
274 : }
275 :
276 : private:
277 : /// \brief The current pointer into the current slab.
278 : ///
279 : /// This points to the next free byte in the slab.
280 : char *CurPtr;
281 :
282 : /// \brief The end of the current slab.
283 : char *End;
284 :
285 : /// \brief The slabs allocated so far.
286 : SmallVector<void *, 4> Slabs;
287 :
288 : /// \brief Custom-sized slabs allocated for too-large allocation requests.
289 : SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
290 :
291 : /// \brief How many bytes we've allocated.
292 : ///
293 : /// Used so that we can compute how much space was wasted.
294 : size_t BytesAllocated;
295 :
296 : /// \brief The allocator instance we use to get slabs of memory.
297 : AllocatorT Allocator;
298 :
299 : static size_t computeSlabSize(unsigned SlabIdx) {
300 : // Scale the actual allocated slab size based on the number of slabs
301 : // allocated. Every 128 slabs allocated, we double the allocated size to
302 : // reduce allocation frequency, but saturate at multiplying the slab size by
303 : // 2^30.
304 0 : return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
305 : }
306 :
307 : /// \brief Allocate a new slab and move the bump pointers over into the new
308 : /// slab, modifying CurPtr and End.
309 : void StartNewSlab() {
310 0 : size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
311 :
312 0 : void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
313 0 : Slabs.push_back(NewSlab);
314 0 : CurPtr = (char *)(NewSlab);
315 0 : End = ((char *)NewSlab) + AllocatedSlabSize;
316 0 : }
317 :
318 : /// \brief Deallocate a sequence of slabs.
319 : void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
320 : SmallVectorImpl<void *>::iterator E) {
321 : for (; I != E; ++I) {
322 : size_t AllocatedSlabSize =
323 : computeSlabSize(std::distance(Slabs.begin(), I));
324 : Allocator.Deallocate(*I, AllocatedSlabSize);
325 : }
326 : }
327 :
328 : /// \brief Deallocate all memory for custom sized slabs.
329 : void DeallocateCustomSizedSlabs() {
330 : for (auto &PtrAndSize : CustomSizedSlabs) {
331 : void *Ptr = PtrAndSize.first;
332 : size_t Size = PtrAndSize.second;
333 : Allocator.Deallocate(Ptr, Size);
334 : }
335 : }
336 :
337 : template <typename T> friend class SpecificBumpPtrAllocator;
338 : };
339 :
340 : /// \brief The standard BumpPtrAllocator which just uses the default template
341 : /// paramaters.
342 : typedef BumpPtrAllocatorImpl<> BumpPtrAllocator;
343 :
344 : /// \brief A BumpPtrAllocator that allows only elements of a specific type to be
345 : /// allocated.
346 : ///
347 : /// This allows calling the destructor in DestroyAll() and when the allocator is
348 : /// destroyed.
349 : template <typename T> class SpecificBumpPtrAllocator {
350 : BumpPtrAllocator Allocator;
351 :
352 : public:
353 : SpecificBumpPtrAllocator() : Allocator() {}
354 : SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old)
355 : : Allocator(std::move(Old.Allocator)) {}
356 : ~SpecificBumpPtrAllocator() { DestroyAll(); }
357 :
358 : SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) {
359 : Allocator = std::move(RHS.Allocator);
360 : return *this;
361 : }
362 :
363 : /// Call the destructor of each allocated object and deallocate all but the
364 : /// current slab and reset the current pointer to the beginning of it, freeing
365 : /// all memory allocated so far.
366 : void DestroyAll() {
367 : auto DestroyElements = [](char *Begin, char *End) {
368 : assert(Begin == (char*)alignAddr(Begin, alignOf<T>()));
369 : for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
370 : reinterpret_cast<T *>(Ptr)->~T();
371 : };
372 :
373 : for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
374 : ++I) {
375 : size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
376 : std::distance(Allocator.Slabs.begin(), I));
377 : char *Begin = (char*)alignAddr(*I, alignOf<T>());
378 : char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
379 : : (char *)*I + AllocatedSlabSize;
380 :
381 : DestroyElements(Begin, End);
382 : }
383 :
384 : for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
385 : void *Ptr = PtrAndSize.first;
386 : size_t Size = PtrAndSize.second;
387 : DestroyElements((char*)alignAddr(Ptr, alignOf<T>()), (char *)Ptr + Size);
388 : }
389 :
390 : Allocator.Reset();
391 : }
392 :
393 : /// \brief Allocate space for an array of objects without constructing them.
394 : T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
395 : };
396 :
397 : } // end namespace llvm
398 :
399 : template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
400 : void *operator new(size_t Size,
401 : llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
402 : SizeThreshold> &Allocator) {
403 : struct S {
404 : char c;
405 : union {
406 : double D;
407 : long double LD;
408 : long long L;
409 : void *P;
410 : } x;
411 : };
412 : return Allocator.Allocate(
413 : Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
414 : }
415 :
416 : template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
417 : void operator delete(
418 : void *, llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold> &) {
419 : }
420 :
421 : #endif // LLVM_SUPPORT_ALLOCATOR_H
|
