Nebula
Loading...
Searching...
No Matches
rangeallocator.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
13//------------------------------------------------------------------------------
14#include "core/types.h"
15#include "util/bit.h"
16#include "util/array.h"
17#include <utility>
18namespace Memory
19{
20
24uint BinFromSize(uint size, uint bucket);
25
27{
31
32 static constexpr uint OOM = 0xFFFFFFFF;
33};
34
35static constexpr uint NUM_BUCKETS = 0x20;
36static constexpr uint NUM_BINS_PER_BUCKET = 0x10;
37
39{
40public:
44 RangeAllocator(uint size, SizeT maxNumAllocs);
47
49 void Clear();
50
52 bool Empty();
53
55 RangeAllocation Alloc(uint size, uint alignment = 1);
57 void Dealloc(const RangeAllocation& allocation);
58
59private:
61 uint InsertNode(uint size, uint offset);
63 void RemoveNode(uint nodeIndex);
64
66 {
68 resident(false)
69 , size(0)
70 , offset(0)
71 , binPrev(END)
72 , binNext(END)
73 , blockPrev(END)
74 , blockNext(END)
75 {};
79
80 static constexpr uint END = 0xFFFFFFFF;
83 };
84
86 {
87 BinIndex() : index(0) {};
88 struct
89 {
92 };
94 };
95
97 static BinIndex IndexFromSize(uint size, bool round = false);
98
102
106
109};
110
111//------------------------------------------------------------------------------
114inline
119
120//------------------------------------------------------------------------------
123inline
125{
126 this->size = size;
127 this->freeNodes.Resize(maxNumAllocs);
128 this->nodes.Resize(maxNumAllocs);
129
130 // Clear the allocator
131 this->Clear();
132}
133
134//------------------------------------------------------------------------------
137inline
141
142//------------------------------------------------------------------------------
145inline void
147{
148 // Reset bit masks
149 this->bucketUsageMask = 0x0;
150 memset(this->binMasks, 0x0, sizeof(this->binMasks));
151
152 // Reset bin heads
153 for (uint i = 0; i < NUM_BUCKETS * NUM_BINS_PER_BUCKET; i++)
154 {
156 }
157
158 // Clear nodes
159 for (uint i = 0; i < this->nodes.Size(); i++)
160 {
161 this->freeNodes[i] = this->nodes.Size() - i - 1;
162 }
163 this->freeNodeIterator = this->nodes.Size() - 1;
164 this->freeStorage = 0;
165
166 // Insert node covering the whole range
167 if (this->size > 0)
168 this->InsertNode(this->size, 0);
169}
170
171//------------------------------------------------------------------------------
174inline bool
176{
177 return this->freeStorage == this->size;
178}
179
180//------------------------------------------------------------------------------
183inline RangeAllocation
185{
186 // We are not allowed any more allocations
187 uint alignedSize = size + alignment - 1;
188 if (this->freeStorage < alignedSize)
189 {
190 return RangeAllocation{ .offset = RangeAllocation::OOM, .size = 0, .node = RangeAllocatorNode::END };
191 }
192
193 BinIndex minIndex = IndexFromSize(alignedSize, true);
194 uint bin = 0xFFFFFFFF;
195 uint bucket = minIndex.bucket;
196
197 if (this->bucketUsageMask & (1 << bucket))
198 {
199 bin = Util::Lsb(this->binMasks[bucket], minIndex.bin);
200 }
201
202 if (bin == 0xFFFFFFFF)
203 {
204 // Find next bit set after bucket in the usage mask
205 bucket = Util::Lsb(this->bucketUsageMask, bucket + 1);
206
207 // If this means we get 32, it means we're out of buckets that fit
208 if (bucket == 0xFFFFFFFF)
209 {
210 return RangeAllocation{ .offset = RangeAllocation::OOM, .size = 0, .node = RangeAllocatorNode::END };
211 }
212
213 // Find any bit, since this bucket has to fit
214 bin = Util::FirstOne(this->binMasks[bucket]);
215 }
216
217 BinIndex binIndex;
218 binIndex.bucket = bucket;
219 binIndex.bin = bin;
220
221 // Get linked list head
222 uint nodeIndex = this->binHeads[binIndex.index];
223 RangeAllocatorNode& node = this->nodes[nodeIndex];
224 n_assert(!node.resident);
225
226 // Save total size of node
227 uint totalSize = node.size;
228 uint baseOffset = node.offset;
229 node.size = alignedSize;
230 node.resident = true;
231 node.offset = Math::align(node.offset, alignment);
232
233 // Bump head of bin to next node
234 this->binHeads[binIndex.index] = node.binNext;
236 this->nodes[node.binNext].binPrev = RangeAllocatorNode::END;
237
238 // If bin head is empty after we grab the node, unmark the bin
239 if (this->binHeads[binIndex.index] == RangeAllocatorNode::END)
240 {
241 this->binMasks[binIndex.bucket] &= ~(1 << binIndex.bin);
242
243 // If all bins are busy, unmark the bucket bits
244 if (this->binMasks[binIndex.bucket] == 0)
245 {
246 this->bucketUsageMask &= ~(1 << binIndex.bucket);
247 }
248 }
249
250 // We subtract the entire size of the node
251 this->freeStorage -= totalSize;
252
253 // The remainder in the front is then added back
254 uint remainder = totalSize - node.size;
255 if (remainder > 0)
256 {
257 uint newNodeIndex = this->InsertNode(remainder, node.offset + size);
258 if (newNodeIndex != RangeAllocatorNode::END)
259 {
260 RangeAllocatorNode& newNode = this->nodes[newNodeIndex];
261
262 // If the current node has a next, repoint it to the new block
264 {
265 this->nodes[node.blockNext].blockPrev = newNodeIndex;
266 }
267 newNode.blockPrev = nodeIndex;
268 newNode.blockNext = node.blockNext;
269 node.blockNext = newNodeIndex;
270 }
271 }
272
273 return RangeAllocation{ .offset = node.offset, .size = alignedSize, .node = nodeIndex };
274}
275
276//------------------------------------------------------------------------------
279inline void
281{
282 RangeAllocatorNode& node = this->nodes[allocation.node];
283 n_assert(node.resident);
284 node.resident = false;
285
286 uint size = node.size;
287 uint offset = node.offset;
288
289 // Try to merge with left
291 {
292 RangeAllocatorNode& prev = this->nodes[node.blockPrev];
293 if (!prev.resident)
294 {
295 offset = prev.offset;
296 size += prev.size;
297
298 this->RemoveNode(node.blockPrev);
299 node.blockPrev = prev.blockPrev;
300 }
301 }
302
304 {
305 RangeAllocatorNode& next = this->nodes[node.blockNext];
306 if (!next.resident)
307 {
308 size += next.size;
309 this->RemoveNode(node.blockNext);
310 node.blockNext = next.blockNext;
311 }
312 }
313
314 uint leftNode = node.blockPrev;
315 uint rightNode = node.blockNext;
316 this->freeNodes[++this->freeNodeIterator] = allocation.node;
317
318 // Add merged node
319 uint mergedNode = this->InsertNode(size, offset);
320
321 // Connect adjacent nodes with newly inserted node
322 if (leftNode != RangeAllocatorNode::END)
323 {
324 this->nodes[leftNode].blockNext = mergedNode;
325 this->nodes[mergedNode].blockPrev = leftNode;
326 }
327
328 if (rightNode != RangeAllocatorNode::END)
329 {
330 this->nodes[rightNode].blockPrev = mergedNode;
331 this->nodes[mergedNode].blockNext = rightNode;
332 }
333}
334
335//------------------------------------------------------------------------------
338inline uint
340{
341 if (this->freeNodeIterator == 0xFFFFFFFF)
343
344 BinIndex index = IndexFromSize(size);
345
346 if (this->binHeads[index.index] == RangeAllocatorNode::END)
347 {
348 // Bin isn't used, flip bit for bucket and bin
349 this->binMasks[index.bucket] |= (1 << index.bin);
350 this->bucketUsageMask |= (1 << index.bucket);
351 }
352
353 // Get new node
354 uint headNodeIndex = this->binHeads[index.index];
355 uint newNodeIndex = this->freeNodes[this->freeNodeIterator--];
356 RangeAllocatorNode& newNode = this->nodes[newNodeIndex];
357
358 // Set the size and offset of the node memory
359 newNode.size = size;
360 newNode.offset = offset;
361 newNode.binNext = headNodeIndex;
363 newNode.resident = false;
364
365 this->freeStorage += size;
366
367 // Get node at head of bin
368 if (headNodeIndex != RangeAllocatorNode::END)
369 {
370 // If valid, repoint head node to point to the new node in the bin
371 RangeAllocatorNode& headNode = this->nodes[headNodeIndex];
372 headNode.binPrev = newNodeIndex;
373 }
374 this->binHeads[index.index] = newNodeIndex;
375
376 return newNodeIndex;
377}
378
379//------------------------------------------------------------------------------
382inline void
384{
385 // Get node to free
386 RangeAllocatorNode& node = this->nodes[nodeIndex];
387 node.resident = false;
388
389 // Add back the storage to the allocator
390 this->freeStorage -= node.size;
391
393 {
394 BinIndex index = IndexFromSize(node.size);
395
396 // Point head of
397 this->binHeads[index.index] = node.binNext;
399 {
400 this->nodes[node.binNext].binPrev = RangeAllocatorNode::END;
401 }
402
404 {
405 // If we are deleting the last node, make sure to unmark the bin
406 this->binMasks[index.bucket] &= ~(1 << index.bin);
407
408 if (this->binMasks[index.bucket] == 0x0)
409 {
410 // If all bins have been cleared, clear the entire bucket
411 this->bucketUsageMask &= ~(1 << index.bucket);
412 }
413 }
414 }
415 else
416 {
417 this->nodes[node.binPrev].binNext = node.binNext;
419 {
420 this->nodes[node.binNext].binPrev = node.binPrev;
421 }
422 }
423
424 this->freeNodes[++this->freeNodeIterator] = nodeIndex;
425}
426
427//------------------------------------------------------------------------------
430inline uint
432{
433#if __WIN32__
434 DWORD count = 0;
435 _BitScanReverse(&count, size);
436#else
437 int count = 31 - __builtin_clz(size);
438#endif
439 return count;
440}
441
442//------------------------------------------------------------------------------
445inline uint
446BinFromSize(uint size, uint bucket)
447{
448 uint mask = (size >> (bucket - 4)) & (NUM_BINS_PER_BUCKET - 1u);
449 return mask;
450}
451
452//------------------------------------------------------------------------------
455inline RangeAllocator::BinIndex
457{
460 ret.bin = BinFromSize(size, ret.bucket);
461 if (round)
462 {
463 uint mask = (1 << ret.bucket) | (ret.bin << (ret.bucket - 4));
464 if ((~mask & size) != 0)
465 ret.bin++;
466 }
467 return ret;
468}
469
470} // namespace Memory
Implements helper functions for checking bits.
Definition rangeallocator.h:39
~RangeAllocator()
Destructor.
Definition rangeallocator.h:138
RangeAllocator()
Default constructor.
Definition rangeallocator.h:115
void Clear()
Clear allocator.
Definition rangeallocator.h:146
uint size
Definition rangeallocator.h:99
Util::Array< RangeAllocatorNode > nodes
Definition rangeallocator.h:107
void RemoveNode(uint nodeIndex)
Remove node from bin.
Definition rangeallocator.h:383
uint InsertNode(uint size, uint offset)
Insert node at bin location, return node index.
Definition rangeallocator.h:339
uint bucketUsageMask
Definition rangeallocator.h:103
bool Empty()
Empty.
Definition rangeallocator.h:175
uint freeNodeIterator
Definition rangeallocator.h:101
static BinIndex IndexFromSize(uint size, bool round=false)
Get bin index from size.
Definition rangeallocator.h:456
RangeAllocation Alloc(uint size, uint alignment=1)
Allocate memory.
Definition rangeallocator.h:184
uint binMasks[NUM_BUCKETS]
Definition rangeallocator.h:104
uint freeStorage
Definition rangeallocator.h:100
Util::Array< uint > freeNodes
Definition rangeallocator.h:108
void Dealloc(const RangeAllocation &allocation)
Deallocate memory.
Definition rangeallocator.h:280
uint binHeads[NUM_BUCKETS *NUM_BINS_PER_BUCKET]
Definition rangeallocator.h:105
Nebula's dynamic array class.
Definition array.h:60
void Resize(SizeT num)
Set size. Grows array if num is greater than capacity. Calls destroy on all objects at index > num!
Definition array.h:1606
const SizeT Size() const
get number of elements in array
Definition array.h:880
#define n_assert(exp)
Definition debug.h:50
__forceinline unsigned int align(unsigned int alignant, unsigned int alignment)
Definition scalar.h:722
Allocates memory using the TLSF method (http://www.gii.upv.es/tlsf/files/ecrts04_tlsf....
Definition arenaallocator.h:31
static constexpr uint NUM_BINS_PER_BUCKET
Definition rangeallocator.h:36
static constexpr uint NUM_BUCKETS
Definition rangeallocator.h:35
uint BinFromSize(uint size, uint bucket)
Get bin from index.
Definition rangeallocator.h:446
uint BucketFromSize(uint size)
Get bucket from index.
Definition rangeallocator.h:431
uint Lsb(uint value, byte bit)
Definition bit.h:229
uint FirstOne(uint value)
Definition bit.h:169
Definition rangeallocator.h:27
uint offset
Definition rangeallocator.h:28
static constexpr uint OOM
Definition rangeallocator.h:32
uint size
Definition rangeallocator.h:29
uint node
Definition rangeallocator.h:30
Definition rangeallocator.h:66
uint offset
Definition rangeallocator.h:78
bool resident
Definition rangeallocator.h:76
static constexpr uint END
Definition rangeallocator.h:80
uint blockNext
Definition rangeallocator.h:82
uint size
Definition rangeallocator.h:77
RangeAllocatorNode()
Definition rangeallocator.h:67
uint blockPrev
Definition rangeallocator.h:82
uint binPrev
Definition rangeallocator.h:81
uint binNext
Definition rangeallocator.h:81
int SizeT
Definition types.h:49
unsigned int uint
Definition types.h:31
uint16_t uint16
Definition types.h:40
Definition rangeallocator.h:86
uint16 index
Definition rangeallocator.h:93
uint16 bucket
Definition rangeallocator.h:91
BinIndex()
Definition rangeallocator.h:87
uint16 bin
Definition rangeallocator.h:90