3 ms·

If you're doing large stack allocations like this (or even if you're not, but care about correctness), you should be doing static analysis to prove absence of s

by addaon 4y ago

If you're doing large stack allocations like this (or even if you're not, but care about correctness), you should be doing static analysis to prove absence of stack overflows. One of the main advantages of heap allocation over stack allocation is that failure is reliably detectable; with a large stack allocation, especially with sparse access patterns, you're well on the way to shipping broken code.

kibwen 4y ago
One difficulty is that stack size is platform-dependent, so it's hard to prove that a stack won't overflow on every possible platform. At least with Rust, a stack overflow is a mandatory segfault at runtime (appears scary at first, but it's guaranteed not to wreak any havoc) on all major platforms, thanks to guard pages (which are present on every platform) and stack probes (which are supported in LLVM for major targets).
- gpderetta 4y ago
  Is it a straight up sigsegv or a catchable panic? I guess having to deal with exceptions at every memory op would be too big a burden on the optimizer, but maybe the exception could be restricted to the function prologue.
  - kibwen 4y ago
    It's not a panic and not recoverable in any way. I'm fuzzy on the details but AFAIK the specifics of LLVM means that it deliberately generates an illegal CPU instruction which manifests as a segfault.
- addaon 4y ago
  Yeah, it's pretty rare to have a program that's correct regardless of the behavior (and defects) of the layers below it -- supporting multiple platforms of course involves performing your verification activities on all of them. As you hint at, guard probes without stack probes don't provide guaranteed segfaults -- sparse access to stack allocations can skip the guard and smash another stack (or whatever) easily enough. And stack probes for large sparse allocations firmly make stack allocations more expensive than heap allocations (since pages must be allocated for the whole allocation, even if it's unused), which is a pretty huge downside.

by addaon 4y ago

kibwen 4y ago

One difficulty is that stack size is platform-dependent, so it's hard to prove that a stack won't overflow on every possible platform. At least with Rust, a stack overflow is a mandatory segfault at runtime (appears scary at first, but it's guaranteed not to wreak any havoc) on all major platforms, thanks to guard pages (which are present on every platform) and stack probes (which are supported in LLVM for major targets).

gpderetta 4y ago
Is it a straight up sigsegv or a catchable panic? I guess having to deal with exceptions at every memory op would be too big a burden on the optimizer, but maybe the exception could be restricted to the function prologue.
- kibwen 4y ago
  It's not a panic and not recoverable in any way. I'm fuzzy on the details but AFAIK the specifics of LLVM means that it deliberately generates an illegal CPU instruction which manifests as a segfault.
addaon 4y ago
Yeah, it's pretty rare to have a program that's correct regardless of the behavior (and defects) of the layers below it -- supporting multiple platforms of course involves performing your verification activities on all of them. As you hint at, guard probes without stack probes don't provide guaranteed segfaults -- sparse access to stack allocations can skip the guard and smash another stack (or whatever) easily enough. And stack probes for large sparse allocations firmly make stack allocations more expensive than heap allocations (since pages must be allocated for the whole allocation, even if it's unused), which is a pretty huge downside.