Always Bump Downwards (2019)
fitzgeraldnick.com
Always Bump Downwards (2019)
1–10 of 74 posts
Re: Always Bump Downwards (2019)
#2Since the title is less than perfectly perspicuous:
It's about "bump allocators", where you allocate memory just by incrementing/decrementing a pointer (and don't free it until you're ready to free up all the memory all at once).
These can either allocate "upwards", starting at low addresses and giving you memory at higher addresses for successive allocations, or "downwards", going the other way.
The claim being made is that "downwards" is better, because the bounds checks you need to do turn out to be more efficient that way; allocation ends up using fewer instructions, fewer registers, and fewer conditional jumps.
Re: Always Bump Downwards (2019)
#3Somewhat aside, I love the graphical display of the benchmark results: https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards... --I think I'll start doing that when I run benchmarks in the future.
Re: Always Bump Downwards (2019)
#4So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow?
Update:
>To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code:
I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result of arbitrary decision”.
Re: Always Bump Downwards (2019)
#5Somewhat aside, I love the graphical display of the benchmark results: https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards... --I think I'll start doing that when I run benchmarks in the future.
Notably, that graph starts at 25 which seems misleading.
Re: Always Bump Downwards (2019)
#6So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result…
I don't think Rust is the issue here. The same integer overflow can occur in any language and should be checked. Integer overflow and underflow is one of the most common security bugs after memory access errors. It is more that bump allocators are so efficient that a relatively inexpensive overflow check can be a significant fraction of their runtime.
Re: Always Bump Downwards (2019)
#7Somewhat aside, I love the graphical display of the benchmark results: https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards... --I think I'll start doing that when I run benchmarks in the future.
Notably, that graph starts at 25 which seems misleading.
Eh it was clearly labeled, and I pretty quickly gleaned that it was like 5 microseconds faster
Re: Always Bump Downwards (2019)
#8So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result…
I think the lesson is "safety comes at a cost. If you bump downwards you can avoid those safety checks"
I don't think the lesson is "let's just write unsafe code"
Re: Always Bump Downwards (2019)
#9So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result…
I don't think Rust is the issue here. The same integer overflow can occur in any language and should be checked. Integer overflow and underflow is one of the most common security bugs after memory access errors. It is more that bump allocators are so efficient that a relatively inexpensive overflow check can be a significant fraction of their runtime.
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:
addr &= ~ALIGN_MASK;
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++;
}
addr = ((addr - 1) | ALIGN_MASK) + 1;
Either of these is worse than just addr &= ~7.
Re: Always Bump Downwards (2019)
#10So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result…
I think the lesson is "safety comes at a cost. If you bump downwards you can avoid those safety checks" I don't think the lesson is "let's just write unsafe code"
Caller asks for a 500 megabyte downward bump allocation in a 32 bit system. Do you check for underflow or not?