Floating the idea of allowing certain abort-only panics to be unwind

language design
#1

So, I was thinking about making a crate that basically converts stack overflow panics from abort-only to unwind panics. The reasoning behind this is that when writing certain recursive descent parsers (or recursive functions in general), it would be useful to put a limit on the possible number of recursions. The way this would work is that the user would call a function like init_stack_overflow_check() and annotate each function with something like #[check_stack], which inserts the proper checks.

The problem with this is that it's basically impossible to do correctly outside of the compiler. This is because large on-stack allocations (such as large arrays) would cause the abort panic to occur before my crate can catch it, as allocas occur within the function body. AFAIK it's impossible to insert code before the llvm allocas, although I may be wrong here and some trickery may allow it.

I was thinking that this wouldn't be a horrible check to allow into the compiler, if it is specifically asked for via a flag in the toml. After all, it's not different from a bounds check. However, bounds checks are also abort-only, so making this feature orthogonal would basically require making array bounds checks unwind as well.

Does anyone else find this feature useful, or am I alone in this? Personally I vastly prefer the crate solution with proc macros, because it allows the feature to be specifically applied. The sometimes-failing nature makes me feel that I need to present this idea to a broader audience first.

1 Like
#2

Even at the LLVM IR level it would be tricky to do this. Allocas in the entry block will get folded into the initial stack allocation in the prolog, even if there's e.g. a call instruction first. Allocas in other blocks won't, so you could move all the allocas out of the entry block, but allocas in other blocks are poorly optimized (it won't even combine adjacent ones), since they're only meant to handle niche cases like literal C alloca calls and VLAs, and doing that still won't handle stack space that LLVM automatically allocates to spill registers.

LLVM does have a mode where it checks available stack space in the prolog, and calls a function if there isn't enough space, in order to support segmented stacks. Rust used to use this. But I don't think that function is allowed to unwind.

#3

Bounds checking appears to unwind

#[allow(unconditional_panic)]
fn main() {
    dbg!(std::panic::catch_unwind(|| { [(); 0][1] }));
}

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 1', src/main.rs:3:40
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
[src/main.rs:3] std::panic::catch_unwind(|| { [(); 0][1] }) = Err(
    Any,
)
1 Like
#4

Ah, my bad, seems I didn't set up the playground settings correctly :stuck_out_tongue: I think this adds to the argument that stack overflow should be an an unwind panic, as a stack overflow is effectively and array-out-of-bounds error.

#5

If LLVM supported GCC's -fstack-check feature (it appears not to, unfortunately), we could compile Rust that way and then stack overflow would cause a predictable machine exception which could, in principle, be handled on an alternative signal stack and safely recovered from by unwinding.

It would require a lot of groundwork both in the compiler and the runtime, though, and I don't know what to do about conflicts with application handlers for SIGSEGV.

#6

I think the only zero-cost approach would be to compile code with async exception support, i.e. so that unwinding may be done an any instruction, and then start unwinding from the signal handler.

There's a further need to make sure that unwinding has enough stack space: the simplest approach here seems to allocate a large amount of pages as guard pages and turn them into normal stack to process the unwinding; alternatively, LLVM would need to be changed to support running EH code with a separate stack.

However this causes a semantic change since now all code can panic (due to register spilling), so functions with unsafe blocks would need an explicit prologue check for compatibility unless flagged as safe.

#7

I wonder if https://clang.llvm.org/docs/SafeStack.html could be used here. I’ll have to do more research in this area, and perhaps send a patch to llvm

#8

Interesting reading. Didn't know about such a feature. It looks like stack behavior inside WebAssembly.

Regarding your issue.

They are related semantically, but currently, stack overflow check is done by the virtual memory subsystem.

If you need stack so deep, perhaps it's better alternative to use software stack instead of hardware one.

You could use Vec::push and Vec::pop for this. And you define struct with fields that represents variables you would use otherwise, including array:

struct MyStackFrame {
   i: usize,
   arr:  [u8;1024],
}

And you could use &references to location on this software stack to avoid copying things around, but it could borrow checker nightmare thou :frowning:.

And you could use Vec::capacity to preallocate required frames, so no sudden allocations and nearly same performance as of native stack.

Using this approach would allow freeing this memory after the algorithm finishes.

On other side it's possible use thread::Builder::stack_size to create thread with bigger stack. But there are no way to release this memory beside ending thread.

Some may say that OS would swap out unused pages, but with same luck OS could decide to swap-out other(more important) part of application. Further more it's common practice in dev-ops to run servers with stack disabled for sake of performance(memory swapping is slow) and fail fast with OOM.

I don't know if unstable generators could help working with software stack, but perhaps something with macros could do.

That's just workarounds, I understand. But I belive it won't be possible to implement reall unwind on stack overflow in performant way.

#9

I'm wondering have you considered passing your array's size to your init_stack_overflow_check function?

Like following (playground):

fn stack_overflow_check<T:Sized>(t:&T){
     let size = std::mem::size_of::<T>();
     let size = size * 2;//to overcheck for next deepth level
     
     // perform check here
}

fn iter(x:usize) {
    let arr = [0u8;1024];
    stack_overflow_check(&arr);
    if x == 0 {
        return;
    }
    
    iter(x-1);
}

fn main() {
    iter(5);
}

P.S. Would actually like to be able to catch SO if that would not cause performace hit in non-error conditions.

And I'm conserned how long would it take to unwind said overflowed stack.