LLVM  8.0.0svn
Allocator.h
Go to the documentation of this file.
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/Optional.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/Support/Compiler.h"
29 #include "llvm/Support/MemAlloc.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <cstddef>
33 #include <cstdint>
34 #include <cstdlib>
35 #include <iterator>
36 #include <type_traits>
37 #include <utility>
38 
39 namespace llvm {
40 
41 /// CRTP base class providing obvious overloads for the core \c
42 /// Allocate() methods of LLVM-style allocators.
43 ///
44 /// This base class both documents the full public interface exposed by all
45 /// LLVM-style allocators, and redirects all of the overloads to a single core
46 /// set of methods which the derived class must define.
47 template <typename DerivedT> class AllocatorBase {
48 public:
49  /// Allocate \a Size bytes of \a Alignment aligned memory. This method
50  /// must be implemented by \c DerivedT.
51  void *Allocate(size_t Size, size_t Alignment) {
52 #ifdef __clang__
53  static_assert(static_cast<void *(AllocatorBase::*)(size_t, size_t)>(
55  static_cast<void *(DerivedT::*)(size_t, size_t)>(
56  &DerivedT::Allocate),
57  "Class derives from AllocatorBase without implementing the "
58  "core Allocate(size_t, size_t) overload!");
59 #endif
60  return static_cast<DerivedT *>(this)->Allocate(Size, Alignment);
61  }
62 
63  /// Deallocate \a Ptr to \a Size bytes of memory allocated by this
64  /// allocator.
65  void Deallocate(const void *Ptr, size_t Size) {
66 #ifdef __clang__
67  static_assert(static_cast<void (AllocatorBase::*)(const void *, size_t)>(
69  static_cast<void (DerivedT::*)(const void *, size_t)>(
70  &DerivedT::Deallocate),
71  "Class derives from AllocatorBase without implementing the "
72  "core Deallocate(void *) overload!");
73 #endif
74  return static_cast<DerivedT *>(this)->Deallocate(Ptr, Size);
75  }
76 
77  // The rest of these methods are helpers that redirect to one of the above
78  // core methods.
79 
80  /// Allocate space for a sequence of objects without constructing them.
81  template <typename T> T *Allocate(size_t Num = 1) {
82  return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T)));
83  }
84 
85  /// Deallocate space for a sequence of objects without constructing them.
86  template <typename T>
87  typename std::enable_if<
88  !std::is_same<typename std::remove_cv<T>::type, void>::value, void>::type
89  Deallocate(T *Ptr, size_t Num = 1) {
90  Deallocate(static_cast<const void *>(Ptr), Num * sizeof(T));
91  }
92 };
93 
94 class MallocAllocator : public AllocatorBase<MallocAllocator> {
95 public:
96  void Reset() {}
97 
99  size_t /*Alignment*/) {
100  return safe_malloc(Size);
101  }
102 
103  // Pull in base class overloads.
105 
106  void Deallocate(const void *Ptr, size_t /*Size*/) {
107  free(const_cast<void *>(Ptr));
108  }
109 
110  // Pull in base class overloads.
112 
113  void PrintStats() const {}
114 };
115 
116 namespace detail {
117 
118 // We call out to an external function to actually print the message as the
119 // printing code uses Allocator.h in its implementation.
120 void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated,
121  size_t TotalMemory);
122 
123 } // end namespace detail
124 
125 /// Allocate memory in an ever growing pool, as if by bump-pointer.
126 ///
127 /// This isn't strictly a bump-pointer allocator as it uses backing slabs of
128 /// memory rather than relying on a boundless contiguous heap. However, it has
129 /// bump-pointer semantics in that it is a monotonically growing pool of memory
130 /// where every allocation is found by merely allocating the next N bytes in
131 /// the slab, or the next N bytes in the next slab.
132 ///
133 /// Note that this also has a threshold for forcing allocations above a certain
134 /// size into their own slab.
135 ///
136 /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator
137 /// object, which wraps malloc, to allocate memory, but it can be changed to
138 /// use a custom allocator.
139 template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
140  size_t SizeThreshold = SlabSize>
142  : public AllocatorBase<
143  BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold>> {
144 public:
145  static_assert(SizeThreshold <= SlabSize,
146  "The SizeThreshold must be at most the SlabSize to ensure "
147  "that objects larger than a slab go into their own memory "
148  "allocation.");
149 
150  BumpPtrAllocatorImpl() = default;
151 
152  template <typename T>
154  : Allocator(std::forward<T &&>(Allocator)) {}
155 
156  // Manually implement a move constructor as we must clear the old allocator's
157  // slabs as a matter of correctness.
159  : CurPtr(Old.CurPtr), End(Old.End), Slabs(std::move(Old.Slabs)),
160  CustomSizedSlabs(std::move(Old.CustomSizedSlabs)),
161  BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize),
162  Allocator(std::move(Old.Allocator)) {
163  Old.CurPtr = Old.End = nullptr;
164  Old.BytesAllocated = 0;
165  Old.Slabs.clear();
166  Old.CustomSizedSlabs.clear();
167  }
168 
170  DeallocateSlabs(Slabs.begin(), Slabs.end());
171  DeallocateCustomSizedSlabs();
172  }
173 
175  DeallocateSlabs(Slabs.begin(), Slabs.end());
176  DeallocateCustomSizedSlabs();
177 
178  CurPtr = RHS.CurPtr;
179  End = RHS.End;
180  BytesAllocated = RHS.BytesAllocated;
181  RedZoneSize = RHS.RedZoneSize;
182  Slabs = std::move(RHS.Slabs);
183  CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
184  Allocator = std::move(RHS.Allocator);
185 
186  RHS.CurPtr = RHS.End = nullptr;
187  RHS.BytesAllocated = 0;
188  RHS.Slabs.clear();
189  RHS.CustomSizedSlabs.clear();
190  return *this;
191  }
192 
193  /// Deallocate all but the current slab and reset the current pointer
194  /// to the beginning of it, freeing all memory allocated so far.
195  void Reset() {
196  // Deallocate all but the first slab, and deallocate all custom-sized slabs.
197  DeallocateCustomSizedSlabs();
198  CustomSizedSlabs.clear();
199 
200  if (Slabs.empty())
201  return;
202 
203  // Reset the state.
204  BytesAllocated = 0;
205  CurPtr = (char *)Slabs.front();
206  End = CurPtr + SlabSize;
207 
208  __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0));
209  DeallocateSlabs(std::next(Slabs.begin()), Slabs.end());
210  Slabs.erase(std::next(Slabs.begin()), Slabs.end());
211  }
212 
213  /// Allocate space at the specified alignment.
215  Allocate(size_t Size, size_t Alignment) {
216  assert(Alignment > 0 && "0-byte alignnment is not allowed. Use 1 instead.");
217 
218  // Keep track of how many bytes we've allocated.
219  BytesAllocated += Size;
220 
221  size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
222  assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
223 
224  size_t SizeToAllocate = Size;
225 #if LLVM_ADDRESS_SANITIZER_BUILD
226  // Add trailing bytes as a "red zone" under ASan.
227  SizeToAllocate += RedZoneSize;
228 #endif
229 
230  // Check if we have enough space.
231  if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) {
232  char *AlignedPtr = CurPtr + Adjustment;
233  CurPtr = AlignedPtr + SizeToAllocate;
234  // Update the allocation point of this memory block in MemorySanitizer.
235  // Without this, MemorySanitizer messages for values originated from here
236  // will point to the allocation of the entire slab.
237  __msan_allocated_memory(AlignedPtr, Size);
238  // Similarly, tell ASan about this space.
239  __asan_unpoison_memory_region(AlignedPtr, Size);
240  return AlignedPtr;
241  }
242 
243  // If Size is really big, allocate a separate slab for it.
244  size_t PaddedSize = SizeToAllocate + Alignment - 1;
245  if (PaddedSize > SizeThreshold) {
246  void *NewSlab = Allocator.Allocate(PaddedSize, 0);
247  // We own the new slab and don't want anyone reading anyting other than
248  // pieces returned from this method. So poison the whole slab.
249  __asan_poison_memory_region(NewSlab, PaddedSize);
250  CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
251 
252  uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment);
253  assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
254  char *AlignedPtr = (char*)AlignedAddr;
255  __msan_allocated_memory(AlignedPtr, Size);
256  __asan_unpoison_memory_region(AlignedPtr, Size);
257  return AlignedPtr;
258  }
259 
260  // Otherwise, start a new slab and try again.
261  StartNewSlab();
262  uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
263  assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&
264  "Unable to allocate memory!");
265  char *AlignedPtr = (char*)AlignedAddr;
266  CurPtr = AlignedPtr + SizeToAllocate;
267  __msan_allocated_memory(AlignedPtr, Size);
268  __asan_unpoison_memory_region(AlignedPtr, Size);
269  return AlignedPtr;
270  }
271 
272  // Pull in base class overloads.
274 
275  // Bump pointer allocators are expected to never free their storage; and
276  // clients expect pointers to remain valid for non-dereferencing uses even
277  // after deallocation.
278  void Deallocate(const void *Ptr, size_t Size) {
279  __asan_poison_memory_region(Ptr, Size);
280  }
281 
282  // Pull in base class overloads.
284 
285  size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
286 
287  /// \return An index uniquely and reproducibly identifying
288  /// an input pointer \p Ptr in the given allocator.
289  /// The returned value is negative iff the object is inside a custom-size
290  /// slab.
291  /// Returns an empty optional if the pointer is not found in the allocator.
293  const char *P = static_cast<const char *>(Ptr);
294  int64_t InSlabIdx = 0;
295  for (size_t Idx = 0, E = Slabs.size(); Idx < E; Idx++) {
296  const char *S = static_cast<const char *>(Slabs[Idx]);
297  if (P >= S && P < S + computeSlabSize(Idx))
298  return InSlabIdx + static_cast<int64_t>(P - S);
299  InSlabIdx += static_cast<int64_t>(computeSlabSize(Idx));
300  }
301 
302  // Use negative index to denote custom sized slabs.
303  int64_t InCustomSizedSlabIdx = -1;
304  for (size_t Idx = 0, E = CustomSizedSlabs.size(); Idx < E; Idx++) {
305  const char *S = static_cast<const char *>(CustomSizedSlabs[Idx].first);
306  size_t Size = CustomSizedSlabs[Idx].second;
307  if (P >= S && P < S + Size)
308  return InCustomSizedSlabIdx - static_cast<int64_t>(P - S);
309  InCustomSizedSlabIdx -= static_cast<int64_t>(Size);
310  }
311  return None;
312  }
313 
314  size_t getTotalMemory() const {
315  size_t TotalMemory = 0;
316  for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
317  TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
318  for (auto &PtrAndSize : CustomSizedSlabs)
319  TotalMemory += PtrAndSize.second;
320  return TotalMemory;
321  }
322 
323  size_t getBytesAllocated() const { return BytesAllocated; }
324 
325  void setRedZoneSize(size_t NewSize) {
326  RedZoneSize = NewSize;
327  }
328 
329  void PrintStats() const {
330  detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated,
331  getTotalMemory());
332  }
333 
334 private:
335  /// The current pointer into the current slab.
336  ///
337  /// This points to the next free byte in the slab.
338  char *CurPtr = nullptr;
339 
340  /// The end of the current slab.
341  char *End = nullptr;
342 
343  /// The slabs allocated so far.
345 
346  /// Custom-sized slabs allocated for too-large allocation requests.
347  SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs;
348 
349  /// How many bytes we've allocated.
350  ///
351  /// Used so that we can compute how much space was wasted.
352  size_t BytesAllocated = 0;
353 
354  /// The number of bytes to put between allocations when running under
355  /// a sanitizer.
356  size_t RedZoneSize = 1;
357 
358  /// The allocator instance we use to get slabs of memory.
359  AllocatorT Allocator;
360 
361  static size_t computeSlabSize(unsigned SlabIdx) {
362  // Scale the actual allocated slab size based on the number of slabs
363  // allocated. Every 128 slabs allocated, we double the allocated size to
364  // reduce allocation frequency, but saturate at multiplying the slab size by
365  // 2^30.
366  return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
367  }
368 
369  /// Allocate a new slab and move the bump pointers over into the new
370  /// slab, modifying CurPtr and End.
371  void StartNewSlab() {
372  size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
373 
374  void *NewSlab = Allocator.Allocate(AllocatedSlabSize, 0);
375  // We own the new slab and don't want anyone reading anything other than
376  // pieces returned from this method. So poison the whole slab.
377  __asan_poison_memory_region(NewSlab, AllocatedSlabSize);
378 
379  Slabs.push_back(NewSlab);
380  CurPtr = (char *)(NewSlab);
381  End = ((char *)NewSlab) + AllocatedSlabSize;
382  }
383 
384  /// Deallocate a sequence of slabs.
385  void DeallocateSlabs(SmallVectorImpl<void *>::iterator I,
387  for (; I != E; ++I) {
388  size_t AllocatedSlabSize =
389  computeSlabSize(std::distance(Slabs.begin(), I));
390  Allocator.Deallocate(*I, AllocatedSlabSize);
391  }
392  }
393 
394  /// Deallocate all memory for custom sized slabs.
395  void DeallocateCustomSizedSlabs() {
396  for (auto &PtrAndSize : CustomSizedSlabs) {
397  void *Ptr = PtrAndSize.first;
398  size_t Size = PtrAndSize.second;
399  Allocator.Deallocate(Ptr, Size);
400  }
401  }
402 
403  template <typename T> friend class SpecificBumpPtrAllocator;
404 };
405 
406 /// The standard BumpPtrAllocator which just uses the default template
407 /// parameters.
409 
410 /// A BumpPtrAllocator that allows only elements of a specific type to be
411 /// allocated.
412 ///
413 /// This allows calling the destructor in DestroyAll() and when the allocator is
414 /// destroyed.
415 template <typename T> class SpecificBumpPtrAllocator {
416  BumpPtrAllocator Allocator;
417 
418 public:
420  // Because SpecificBumpPtrAllocator walks the memory to call destructors,
421  // it can't have red zones between allocations.
422  Allocator.setRedZoneSize(0);
423  }
425  : Allocator(std::move(Old.Allocator)) {}
426  ~SpecificBumpPtrAllocator() { DestroyAll(); }
427 
429  Allocator = std::move(RHS.Allocator);
430  return *this;
431  }
432 
433  /// Call the destructor of each allocated object and deallocate all but the
434  /// current slab and reset the current pointer to the beginning of it, freeing
435  /// all memory allocated so far.
436  void DestroyAll() {
437  auto DestroyElements = [](char *Begin, char *End) {
438  assert(Begin == (char *)alignAddr(Begin, alignof(T)));
439  for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T))
440  reinterpret_cast<T *>(Ptr)->~T();
441  };
442 
443  for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
444  ++I) {
445  size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
446  std::distance(Allocator.Slabs.begin(), I));
447  char *Begin = (char *)alignAddr(*I, alignof(T));
448  char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
449  : (char *)*I + AllocatedSlabSize;
450 
451  DestroyElements(Begin, End);
452  }
453 
454  for (auto &PtrAndSize : Allocator.CustomSizedSlabs) {
455  void *Ptr = PtrAndSize.first;
456  size_t Size = PtrAndSize.second;
457  DestroyElements((char *)alignAddr(Ptr, alignof(T)), (char *)Ptr + Size);
458  }
459 
460  Allocator.Reset();
461  }
462 
463  /// Allocate space for an array of objects without constructing them.
464  T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); }
465 };
466 
467 } // end namespace llvm
468 
469 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
470 void *operator new(size_t Size,
471  llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
472  SizeThreshold> &Allocator) {
473  struct S {
474  char c;
475  union {
476  double D;
477  long double LD;
478  long long L;
479  void *P;
480  } x;
481  };
482  return Allocator.Allocate(
483  Size, std::min((size_t)llvm::NextPowerOf2(Size), offsetof(S, x)));
484 }
485 
486 template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold>
487 void operator delete(
489 }
490 
491 #endif // LLVM_SUPPORT_ALLOCATOR_H
#define __asan_poison_memory_region(p, size)
Definition: Compiler.h:390
void push_back(const T &Elt)
Definition: SmallVector.h:218
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void Deallocate(const void *Ptr, size_t Size)
Deallocate Ptr to Size bytes of memory allocated by this allocator.
Definition: Allocator.h:65
#define __asan_unpoison_memory_region(p, size)
Definition: Compiler.h:391
void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated, size_t TotalMemory)
Definition: Allocator.cpp:21
void * Allocate(size_t Size, size_t Alignment)
Allocate Size bytes of Alignment aligned memory.
Definition: Allocator.h:51
void PrintStats() const
Definition: Allocator.h:113
Definition: BitVector.h:938
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it...
Definition: Allocator.h:195
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
BumpPtrAllocatorImpl & operator=(BumpPtrAllocatorImpl &&RHS)
Definition: Allocator.h:174
This file defines counterparts of C library allocation functions defined in the namespace &#39;std&#39;...
void Deallocate(const void *Ptr, size_t Size)
Definition: Allocator.h:278
#define __msan_allocated_memory(p, size)
Definition: Compiler.h:379
#define T
void DestroyAll()
Call the destructor of each allocated object and deallocate all but the current slab and reset the cu...
Definition: Allocator.h:436
size_t getBytesAllocated() const
Definition: Allocator.h:323
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:408
#define P(N)
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
llvm::Optional< int64_t > identifyObject(const void *Ptr)
Definition: Allocator.h:292
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
size_t alignmentAdjustment(const void *Ptr, size_t Alignment)
Returns the necessary adjustment for aligning Ptr to Alignment bytes, rounding up.
Definition: MathExtras.h:634
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:215
#define offsetof(TYPE, MEMBER)
void Deallocate(const void *Ptr, size_t)
Definition: Allocator.h:106
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:464
void setRedZoneSize(size_t NewSize)
Definition: Allocator.h:325
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:640
size_t size() const
Definition: SmallVector.h:53
SpecificBumpPtrAllocator & operator=(SpecificBumpPtrAllocator &&RHS)
Definition: Allocator.h:428
Basic Register Allocator
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:26
SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old)
Definition: Allocator.h:424
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:415
size_t GetNumSlabs() const
Definition: Allocator.h:285
uintptr_t alignAddr(const void *Addr, size_t Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: MathExtras.h:623
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, size_t)
Definition: Allocator.h:98
T * Allocate(size_t Num=1)
Allocate space for a sequence of objects without constructing them.
Definition: Allocator.h:81
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
#define LLVM_ATTRIBUTE_RETURNS_NOALIAS
LLVM_ATTRIBUTE_RETURNS_NOALIAS Used to mark a function as returning a pointer that does not alias any...
Definition: Compiler.h:227
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:47
#define LLVM_ATTRIBUTE_RETURNS_NONNULL
Definition: Compiler.h:217
std::enable_if< !std::is_same< typename std::remove_cv< T >::type, void >::value, void >::type Deallocate(T *Ptr, size_t Num=1)
Deallocate space for a sequence of objects without constructing them.
Definition: Allocator.h:89
size_t getTotalMemory() const
Definition: Allocator.h:314
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
BumpPtrAllocatorImpl(T &&Allocator)
Definition: Allocator.h:153
BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old)
Definition: Allocator.h:158
CRTP base class providing obvious overloads for the core Allocate() methods of LLVM-style allocators...
Definition: Allocator.h:47