util/block-allocator.spice
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright (c) 2021-2026 ChilliBits. All rights reserved. | ||
| 2 | |||
| 3 | // Std imports | ||
| 4 | import "std/data/vector"; | ||
| 5 | import "std/os/system"; | ||
| 6 | |||
| 7 | // Own imports | ||
| 8 | import "@/util/memory"; | ||
| 9 | |||
| 10 | type Base dyn; | ||
| 11 | type T dyn; | ||
| 12 | |||
| 13 | ✗ | public type BlockAllocator<Base> struct { | |
| 14 | IMemoryManager& memoryManager | ||
| 15 | // The heap qualifier is re-applied via a cast wherever a block is allocated, used or freed. | ||
| 16 | Vector<byte*> memoryBlocks | ||
| 17 | Vector<Base*> allocatedObjects | ||
| 18 | unsigned long blockSize | ||
| 19 | 4223 | unsigned long offsetInBlock = 0l | |
| 20 | } | ||
| 21 | |||
| 22 | 4223 | public p BlockAllocator.ctor(IMemoryManager& memoryManager, unsigned long blockSize = 0l) { | |
| 23 | 4223 | this.memoryManager = memoryManager; | |
| 24 | 4223 | this.blockSize = blockSize == 0l ? cast<unsigned long>(getPageSize()) : blockSize; | |
| 25 | // We do not allow allocating objects that exceed the block size | ||
| 26 | 4223 | assert sizeof<Base>() <= this.blockSize; | |
| 27 | // Allocate the first block | ||
| 28 | 4223 | this.allocateNewBlock(); | |
| 29 | 4223 | } | |
| 30 | |||
| 31 | 3067 | public p BlockAllocator.dtor() { | |
| 32 | // Destruct all objects. We dereference here so that the destructor of the pointed-to object (the | ||
| 33 | // 'Base' value, e.g. ASTNode) runs. Passing the pointer itself would instantiate sDestruct for a | ||
| 34 | // pointer type, which is trivially destructible and would therefore be a no-op. | ||
| 35 | 435083 | foreach Base* ptr : this.allocatedObjects { | |
| 36 | 432016 | sDestruct(*ptr); | |
| 37 | 432016 | } | |
| 38 | 3067 | this.allocatedObjects.clear(); | |
| 39 | |||
| 40 | // Free all memory blocks | ||
| 41 | 154935 | foreach byte* block : this.memoryBlocks { | |
| 42 | unsafe { | ||
| 43 | 151868 | this.memoryManager.deallocate(cast<heap byte*>(block)); | |
| 44 | } | ||
| 45 | 151868 | } | |
| 46 | 3067 | this.memoryBlocks.clear(); | |
| 47 | 3067 | } | |
| 48 | |||
| 49 | /** | ||
| 50 | * Reserve uninitialized, correctly sized storage for an object of type T within the current block | ||
| 51 | * (allocating a new block if required) and return a typed pointer to it. The caller is responsible | ||
| 52 | * for constructing the object in place (e.g. via __placement_new). Returning raw storage instead of | ||
| 53 | * copying a prebuilt object means T does not need to be copyable. | ||
| 54 | */ | ||
| 55 | 2677136 | public f<T*> BlockAllocator.reserve<T>() { | |
| 56 | // We do not allow allocating objects that exceed the block size | ||
| 57 | 2677136 | const unsigned long objSize = sizeof<T>(); | |
| 58 | 2677136 | assert objSize <= this.blockSize; | |
| 59 | |||
| 60 | // Check if we need a new block | ||
| 61 | 2677136 | if this.offsetInBlock + objSize > this.blockSize { | |
| 62 | 153756 | this.allocateNewBlock(); | |
| 63 | 153756 | } | |
| 64 | |||
| 65 | // Compute the destination address inside the current block. We deliberately operate on a plain | ||
| 66 | // (non-heap) byte* here: a named 'heap byte*' local would be treated as an owning pointer and freed | ||
| 67 | // again at scope exit, double-freeing the block that is owned by 'memoryBlocks'. | ||
| 68 | 2677136 | T* ptr; | |
| 69 | unsafe { | ||
| 70 | 2677136 | byte* destAddr = this.memoryBlocks.back(); | |
| 71 | 2677136 | destAddr += this.offsetInBlock; | |
| 72 | 2677136 | ptr = cast<T*>(destAddr); | |
| 73 | } | ||
| 74 | |||
| 75 | // Track the object so it can be destructed in the allocator's dtor and update the offset to be ready | ||
| 76 | // to store the next object. The object is not constructed yet, but its address is already stable. | ||
| 77 | 2677136 | Base* basePtr = cast<Base*>(ptr); | |
| 78 | 2677136 | this.allocatedObjects.pushBack(basePtr); | |
| 79 | 2677136 | this.offsetInBlock += objSize; | |
| 80 | 2677136 | return ptr; | |
| 81 | } | ||
| 82 | |||
| 83 | /** | ||
| 84 | * Hand the reserved objects over to the caller, which is then responsible for destructing them. The memory blocks stay owned by | ||
| 85 | * the allocator. Pools of objects, whose concrete types compose Base (e.g. the AST nodes), need this, because the dtor of the | ||
| 86 | * allocator can only destruct them as Base, which would leak the members of the concrete types. | ||
| 87 | * | ||
| 88 | * @return Pointers to all objects, which were reserved via this allocator | ||
| 89 | */ | ||
| 90 | 767 | public f<Vector<Base*>> BlockAllocator.releaseObjects() { | |
| 91 | 767 | Vector<Base*> objects = this.allocatedObjects; | |
| 92 | 767 | this.allocatedObjects.clear(); | |
| 93 | 1534 | return objects; | |
| 94 | 767 | } | |
| 95 | |||
| 96 | /** | ||
| 97 | * Get the total number of bytes, which were allocated for memory blocks | ||
| 98 | * | ||
| 99 | * @return Total allocated size in bytes | ||
| 100 | */ | ||
| 101 | 2 | public f<unsigned long> BlockAllocator.getTotalAllocatedSize() { | |
| 102 | 2 | return this.memoryBlocks.getSize() * this.blockSize; | |
| 103 | } | ||
| 104 | |||
| 105 | /** | ||
| 106 | * Get the number of objects, which were reserved via this allocator | ||
| 107 | * | ||
| 108 | * @return Number of allocations | ||
| 109 | */ | ||
| 110 | 3 | public f<unsigned long> BlockAllocator.getAllocationCount() { | |
| 111 | 3 | return this.allocatedObjects.getSize(); | |
| 112 | } | ||
| 113 | |||
| 114 | 157979 | public p BlockAllocator.allocateNewBlock() { | |
| 115 | // Allocate a new block and immediately reinterpret it as a plain byte*. The 'memoryManager.allocate' | ||
| 116 | // result is a 'heap byte*'; binding it to a named local would make it an owning pointer that is freed | ||
| 117 | // again at scope exit. By casting the temporary inline we transfer the raw address into 'memoryBlocks' | ||
| 118 | // without the compiler inserting an auto-free. The block is freed manually in the dtor. | ||
| 119 | 157979 | byte* rawPtr; | |
| 120 | unsafe { | ||
| 121 | 157979 | rawPtr = cast<byte*>(this.memoryManager.allocate(this.blockSize)); | |
| 122 | } | ||
| 123 | 157979 | if rawPtr == nil<byte*> { | |
| 124 | ✗ | panic(Error("Could not allocate memory block for BlockAllocator.")); | |
| 125 | } | ||
| 126 | |||
| 127 | // Store pointer and reset offset | ||
| 128 | 157979 | this.memoryBlocks.pushBack(rawPtr); | |
| 129 | 157979 | this.offsetInBlock = 0l; | |
| 130 | 157979 | } | |
| 131 | // ─── tests ──────────────────────────────────────────────────────────────────── | ||
| 132 | |||
| 133 | // Number of destructed dummy nodes. Spice only supports globals of primitive type, so the counter lives here | ||
| 134 | unsigned long DESTRUCTED_DUMMY_NODES = 0l; | ||
| 135 | |||
| 136 | type DummyNode struct { | ||
| 137 | unsigned long line | ||
| 138 | unsigned long col | ||
| 139 | } | ||
| 140 | |||
| 141 | 101005 | public p DummyNode.ctor(unsigned long line, unsigned long col) { | |
| 142 | 101005 | this.line = line; | |
| 143 | 101005 | this.col = col; | |
| 144 | 101005 | } | |
| 145 | |||
| 146 | 101005 | public p DummyNode.dtor() { | |
| 147 | unsafe { | ||
| 148 | 101005 | DESTRUCTED_DUMMY_NODES++; | |
| 149 | } | ||
| 150 | 101005 | } | |
| 151 | |||
| 152 | // Memory manager, that counts the allocated and deallocated blocks | ||
| 153 | 2 | type CountingMemoryManager struct : IMemoryManager { | |
| 154 | DefaultMemoryManager defaultMemoryManager | ||
| 155 | 2 | unsigned long allocations = 0l | |
| 156 | 2 | unsigned long deallocations = 0l | |
| 157 | } | ||
| 158 | |||
| 159 | 20250 | public f<heap byte*> CountingMemoryManager.allocate(unsigned long size) { | |
| 160 | 20250 | this.allocations++; | |
| 161 | 20250 | return this.defaultMemoryManager.allocate(size); | |
| 162 | } | ||
| 163 | |||
| 164 | 20250 | public p CountingMemoryManager.deallocate(heap byte*& ptr) { | |
| 165 | 20250 | this.deallocations++; | |
| 166 | 20250 | this.defaultMemoryManager.deallocate(ptr); | |
| 167 | 20250 | } | |
| 168 | |||
| 169 | // Allocate the given number of dummy nodes with an allocator of the given block size and check that they are intact and | ||
| 170 | // destructed together with the allocator | ||
| 171 | 2 | f<bool> allocateDummyNodes(unsigned long nodeCount, unsigned long blockSize, unsigned long nodesPerBlock) { | |
| 172 | 2 | DESTRUCTED_DUMMY_NODES = 0l; | |
| 173 | 2 | CountingMemoryManager memoryManager; | |
| 174 | { | ||
| 175 | 2 | BlockAllocator<DummyNode> alloc = BlockAllocator<DummyNode>(memoryManager, blockSize); | |
| 176 | |||
| 177 | // Allocate nodes | ||
| 178 | 2 | Vector<DummyNode*> nodes; | |
| 179 | 101002 | for unsigned long i = 0l; i < nodeCount; i++ { | |
| 180 | 101000 | DummyNode* node = alloc.reserve<DummyNode>(); | |
| 181 | 101000 | assert node != nil<DummyNode*>; | |
| 182 | unsafe { | ||
| 183 | 101000 | __placement_new<DummyNode>(node, i, 1l); | |
| 184 | } | ||
| 185 | 101000 | nodes.pushBack(node); | |
| 186 | 101000 | } | |
| 187 | |||
| 188 | // Check that no node was overwritten by a later one | ||
| 189 | 101002 | for unsigned long i = 0l; i < nodeCount; i++ { | |
| 190 | 101000 | DummyNode* node = nodes.get(i); | |
| 191 | 101000 | assert node.line == i; | |
| 192 | 101000 | assert node.col == 1l; | |
| 193 | 101000 | } | |
| 194 | |||
| 195 | // Check if stats are correct | ||
| 196 | 2 | const unsigned long blockCount = (nodeCount + nodesPerBlock - 1l) / nodesPerBlock; | |
| 197 | 2 | assert alloc.getAllocationCount() == nodeCount; | |
| 198 | 2 | assert alloc.getTotalAllocatedSize() == blockCount * blockSize; | |
| 199 | 2 | assert memoryManager.allocations == blockCount; | |
| 200 | 2 | assert memoryManager.deallocations == 0l; | |
| 201 | |||
| 202 | // Block allocator gets destructed here and with that, all allocated nodes should be destructed | ||
| 203 | 2 | } | |
| 204 | 2 | assert DESTRUCTED_DUMMY_NODES == nodeCount; | |
| 205 | 2 | assert memoryManager.deallocations == memoryManager.allocations; | |
| 206 | 2 | return true; | |
| 207 | } | ||
| 208 | |||
| 209 | 1 | #[test] | |
| 210 | f<bool> testBlockAllocatorLarge() { | ||
| 211 | // Create allocator, that can hold 5 nodes per block | ||
| 212 | 1 | return allocateDummyNodes(100000l, sizeof<DummyNode>() * 5l, 5l); | |
| 213 | } | ||
| 214 | |||
| 215 | 1 | #[test] | |
| 216 | f<bool> testBlockAllocatorUnevenBlockSize() { | ||
| 217 | // Create allocator, that can hold 4.5 nodes per block | ||
| 218 | 1 | return allocateDummyNodes(1000l, sizeof<DummyNode>() * 9l / 2l, 4l); | |
| 219 | } | ||
| 220 | |||
| 221 | 1 | #[test] | |
| 222 | f<bool> testBlockAllocatorReleaseObjects() { | ||
| 223 | unsafe { | ||
| 224 | 1 | DESTRUCTED_DUMMY_NODES = 0l; | |
| 225 | } | ||
| 226 | 1 | DefaultMemoryManager memoryManager; | |
| 227 | 1 | Vector<DummyNode*> released; | |
| 228 | { | ||
| 229 | 1 | BlockAllocator<DummyNode> alloc = BlockAllocator<DummyNode>(memoryManager, sizeof<DummyNode>() * 2l); | |
| 230 | 6 | for unsigned long i = 0l; i < 5l; i++ { | |
| 231 | 5 | DummyNode* node = alloc.reserve<DummyNode>(); | |
| 232 | unsafe { | ||
| 233 | 5 | __placement_new<DummyNode>(node, i, 1l); | |
| 234 | } | ||
| 235 | 5 | } | |
| 236 | // The caller becomes responsible for destructing the released objects, so the allocator must not do it anymore | ||
| 237 | 1 | released = alloc.releaseObjects(); | |
| 238 | 1 | assert released.getSize() == 5l; | |
| 239 | 1 | assert alloc.getAllocationCount() == 0l; | |
| 240 | 6 | foreach DummyNode* node : released { | |
| 241 | 5 | sDestruct(*node); | |
| 242 | 5 | } | |
| 243 | 1 | } | |
| 244 | unsafe { | ||
| 245 | 1 | assert DESTRUCTED_DUMMY_NODES == 5l; | |
| 246 | } | ||
| 247 | 1 | return true; | |
| 248 | 1 | } | |
| 249 |