1 /* 2 * Copyright 2024, Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 */ 5 #ifndef _BUMP_ALLOCATOR_H 6 #define _BUMP_ALLOCATOR_H 7 8 9 #include <stdlib.h> 10 11 #include <OS.h> 12 #include <SupportDefs.h> 13 14 15 template<size_t InlineDataSize = (16 * sizeof(void*)), size_t SlabSize = 4096> 16 class BumpAllocator { 17 public: 18 BumpAllocator() 19 : 20 fCurrentSlab((Slab*)fInlineData) 21 { 22 fCurrentSlab->previous = NULL; 23 fCurrentSlab->total = sizeof(fInlineData) - sizeof(Slab); 24 fCurrentSlab->remaining = fCurrentSlab->total; 25 } 26 27 ~BumpAllocator() 28 { 29 if (fCurrentSlab != (Slab*)fInlineData) 30 Free(NULL); 31 32 if (!IsEmpty()) 33 debugger("BumpAllocator: deleted with allocations still active!"); 34 } 35 36 bool IsEmpty() const 37 { 38 return fCurrentSlab == (Slab*)fInlineData 39 && fCurrentSlab->remaining == fCurrentSlab->total; 40 } 41 42 void* Allocate(size_t _size) 43 { 44 const size_t size = _size + sizeof(Allocation); 45 if (size > SlabSize) 46 debugger("BumpAllocator: can't allocate larger than the slab size"); 47 if (fCurrentSlab->remaining < size) { 48 // We need a new slab. 49 Slab* newSlab = (Slab*)malloc(SlabSize); 50 if (newSlab == NULL) 51 return NULL; 52 53 newSlab->previous = fCurrentSlab; 54 newSlab->total = SlabSize - sizeof(Slab); 55 newSlab->remaining = newSlab->total; 56 fCurrentSlab = newSlab; 57 } 58 59 fCurrentSlab->remaining -= size; 60 uint8* pointer = fCurrentSlab->data + fCurrentSlab->remaining; 61 62 Allocation* allocation = (Allocation*)pointer; 63 allocation->size = size; 64 return allocation->data; 65 } 66 67 void Free(void* _pointer) 68 { 69 if (fCurrentSlab->remaining == fCurrentSlab->total) { 70 // Free the current slab. 71 Slab* previous = fCurrentSlab->previous; 72 free(fCurrentSlab); 73 fCurrentSlab = previous; 74 } 75 if (_pointer == NULL) 76 return; 77 78 Allocation* allocation = (((Allocation*)_pointer) - 1); 79 80 // This needs to be the last thing allocated. 81 uint8* last = fCurrentSlab->data + fCurrentSlab->remaining; 82 if ((uint8*)allocation != last) { 83 debugger("BumpAllocator: out-of-order free"); 84 return; 85 } 86 87 fCurrentSlab->remaining += allocation->size; 88 } 89 90 private: 91 #if __cplusplus >= 201103L 92 # define FLA_SIZE 93 #else 94 # define FLA_SIZE 0 95 #endif 96 struct Slab { 97 Slab* previous; 98 uint32 total; 99 uint32 remaining; 100 uint8 data[FLA_SIZE]; 101 }; 102 struct Allocation { 103 uint32 size; /*!< includes sizeof(Allocation) */ 104 uint32 _pad; 105 uint8 data[FLA_SIZE]; 106 #undef FLA_SIZE 107 }; 108 Slab* fCurrentSlab; 109 uint8 fInlineData[InlineDataSize - sizeof(Slab*)]; 110 }; 111 112 #endif /* _BUMP_ALLOCATOR_H */ 113