If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong.
You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go.
If the requests are small, you will hit the end of your arena long before you worry about pointer overflow at the zero address or at address 0xFF..FF!
That said, aligning down is a shade faster than up. To align down to a boundary divisible by ALIGN_MASK + 1 we just truncate some low order bits to zero:
addr &= ~ALIGN_MASK;
If the bits are already zero, the address doesn't move; all is cool.
but aligning up, where we don't care about overflow, requires handling the case where the address is already aligned and doesn't have to move:
if (addr & ALIGN_MASK) {
addr |= ALIGN_MASK;
addr++;
}
Or a trick like this where we bias the address with an offset of -1 during the masking calculation:
addr = ((addr - 1) | ALIGN_MASK) + 1;
(We could get underflow here if addr is the zero address (null pointer on most systems), but it's reversible if the pointer arithmetic is done as unsigned. Zero aligns to zero: it goes to 0xFFF..FFF which stays the same after | 7, and then increments back to zero.)
I would definitely be in favor of an even faster `SmallBump` variant which assumes that the allocations are small w.r.t. usize::MAX for some additional speed.
I also wouldn't mind the a default "fast" bump allocator library to do all tricks it can without sacrificing safety.
And maybe the heap has fixed alignment so you have one that only needs 4 and one that needs 16. Indeed maybe you grow from top and bottom depending. And maybe this is all a giant premature optimization - including the panic about up vs down. My previous career was console video games and maybe this kind of handwringing isn’t required for whatever the fuck this is.
Comments
It's not integer overflow but pointer overflow.
If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong.
You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go.
If the requests are small, you will hit the end of your arena long before you worry about pointer overflow at the zero address or at address 0xFF..FF!
That said, aligning down is a shade faster than up. To align down to a boundary divisible by ALIGN_MASK + 1 we just truncate some low order bits to zero:
If the bits are already zero, the address doesn't move; all is cool.but aligning up, where we don't care about overflow, requires handling the case where the address is already aligned and doesn't have to move:
Or a trick like this where we bias the address with an offset of -1 during the masking calculation: (We could get underflow here if addr is the zero address (null pointer on most systems), but it's reversible if the pointer arithmetic is done as unsigned. Zero aligns to zero: it goes to 0xFFF..FFF which stays the same after | 7, and then increments back to zero.)Either of these is worse than just addr &= ~7.
I would definitely be in favor of an even faster `SmallBump` variant which assumes that the allocations are small w.r.t. usize::MAX for some additional speed.
I also wouldn't mind the a default "fast" bump allocator library to do all tricks it can without sacrificing safety.
And maybe the heap has fixed alignment so you have one that only needs 4 and one that needs 16. Indeed maybe you grow from top and bottom depending. And maybe this is all a giant premature optimization - including the panic about up vs down. My previous career was console video games and maybe this kind of handwringing isn’t required for whatever the fuck this is.
Eh, sure it is. Until it isn't. I'm not using this libraries, but I'm glad they exist.
Since we're both thinking about this...
Is rust warning you about pointer overflow? My understanding is that rust is complaining about integer overflow but perhaps that's insufficient?
(I don't actually know which solution is better/worse from perf perspective besides author's post)
Or you just add ALIGNMENT-1 and then mask. So if alignment is 16 then you add 15.
Oh right; that's how I've always done it, just forgot. Right. Still, it's an extra addition compared to just masking down.