21 #ifndef GTIRB_ALLOCATOR_H
22 #define GTIRB_ALLOCATOR_H
47 return Value && !(Value & (Value - 1));
54 inline uintptr_t
alignAddr(
const void* Addr,
size_t Alignment) {
56 "Alignment is not a power of two!");
58 assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
60 return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
66 return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
79 template <
size_t SlabSize = 4096,
size_t SizeThreshold = SlabSize>
82 static_assert(SizeThreshold <= SlabSize,
83 "The SizeThreshold must be at most the SlabSize to ensure "
84 "that objects larger than a slab go into their own memory "
92 : CurPtr(Old.CurPtr), End(Old.End), Slabs(
std::move(Old.Slabs)),
93 CustomSizedSlabs(
std::move(Old.CustomSizedSlabs)),
94 BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize) {
95 Old.CurPtr = Old.End =
nullptr;
96 Old.BytesAllocated = 0;
98 Old.CustomSizedSlabs.clear();
102 DeallocateSlabs(Slabs.begin(), Slabs.end());
103 DeallocateCustomSizedSlabs();
107 DeallocateSlabs(Slabs.begin(), Slabs.end());
108 DeallocateCustomSizedSlabs();
112 BytesAllocated = RHS.BytesAllocated;
113 RedZoneSize = RHS.RedZoneSize;
114 Slabs = std::move(RHS.Slabs);
115 CustomSizedSlabs = std::move(RHS.CustomSizedSlabs);
117 RHS.CurPtr = RHS.End =
nullptr;
118 RHS.BytesAllocated = 0;
120 RHS.CustomSizedSlabs.clear();
126 assert(Alignment > 0 &&
"0-byte alignnment is not allowed. Use 1 instead.");
129 BytesAllocated += Size;
132 assert(Adjustment + Size >= Size &&
"Adjustment + Size must not overflow");
134 size_t SizeToAllocate = Size;
141 if (Adjustment + SizeToAllocate <=
size_t(End - CurPtr)) {
142 char* AlignedPtr = CurPtr + Adjustment;
143 CurPtr = AlignedPtr + SizeToAllocate;
154 size_t PaddedSize = SizeToAllocate + Alignment - 1;
155 if (PaddedSize > SizeThreshold) {
156 void* NewSlab = std::malloc(PaddedSize);
160 CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize));
162 uintptr_t AlignedAddr =
alignAddr(NewSlab, Alignment);
163 assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize);
164 char* AlignedPtr = (
char*)AlignedAddr;
172 uintptr_t AlignedAddr =
alignAddr(CurPtr, Alignment);
173 assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&
174 "Unable to allocate memory!");
175 char* AlignedPtr = (
char*)AlignedAddr;
176 CurPtr = AlignedPtr + SizeToAllocate;
183 template <
typename T> T*
Allocate(
size_t Num = 1) {
184 return static_cast<T*
>(
Allocate(Num *
sizeof(T),
alignof(T)));
194 size_t GetNumSlabs()
const {
return Slabs.size() + CustomSizedSlabs.size(); }
197 size_t TotalMemory = 0;
198 for (
auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
199 TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
200 for (
auto& PtrAndSize : CustomSizedSlabs)
201 TotalMemory += PtrAndSize.second;
213 char* CurPtr =
nullptr;
219 std::vector<void*> Slabs;
222 std::vector<std::pair<void*, size_t>> CustomSizedSlabs;
227 size_t BytesAllocated = 0;
231 size_t RedZoneSize = 1;
233 static size_t computeSlabSize(
size_t SlabIdx) {
238 return SlabSize * ((size_t)1 << std::min<size_t>(30, SlabIdx / 128));
243 void StartNewSlab() {
244 size_t AllocatedSlabSize = computeSlabSize(Slabs.size());
246 void* NewSlab = std::malloc(AllocatedSlabSize);
251 Slabs.push_back(NewSlab);
252 CurPtr = (
char*)(NewSlab);
253 End = ((
char*)NewSlab) + AllocatedSlabSize;
257 void DeallocateSlabs(std::vector<void*>::iterator I,
258 std::vector<void*>::iterator E) {
259 for (; I != E; ++I) {
265 void DeallocateCustomSizedSlabs() {
266 for (
auto& PtrAndSize : CustomSizedSlabs) {
267 std::free(PtrAndSize.first);
293 : Allocator(
std::move(Old.Allocator)) {}
297 Allocator = std::move(RHS.Allocator);
309 Allocator.Slabs.clear();
310 Allocator.CustomSizedSlabs.clear();
318 auto DestroyElements = [](
char* Begin,
char* End) {
319 assert(Begin == (
char*)
alignAddr(Begin,
alignof(T)));
320 for (
char* Ptr = Begin; Ptr +
sizeof(T) <= End; Ptr +=
sizeof(T))
321 reinterpret_cast<T*
>(Ptr)->~T();
324 for (
auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E;
326 size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize(
327 std::distance(Allocator.Slabs.begin(), I));
328 char* Begin = (
char*)
alignAddr(*I,
alignof(T));
329 char* End = *I == Allocator.Slabs.back() ? Allocator.CurPtr
330 : (
char*)*I + AllocatedSlabSize;
332 DestroyElements(Begin, End);
335 for (
auto& PtrAndSize : Allocator.CustomSizedSlabs) {
336 void* Ptr = PtrAndSize.first;
337 size_t Size = PtrAndSize.second;
338 DestroyElements((
char*)
alignAddr(Ptr,
alignof(T)), (
char*)Ptr + Size);
343 template <
size_t SlabSize,
size_t SizeThreshold>
344 void*
operator new(
size_t Size,
356 Size, std::min((
size_t)
NextPowerOf2(Size), offsetof(S, x)));
359 template <
size_t SlabSize,
size_t SizeThreshold>
362 #endif // GTIRB_ALLOCATOR_H