RFC: Revise or at least rename the `fixed_stack_segment` and `rust_stack` annotations

[nikomatsakis]

Currently, fns annotated with fixed_stack_segment (hereafter abbreviated as FSS) request a "large" stack (2MB, I think) from the system. They are supplied with a "larger" stack (3MB?). This overallocation typically ensures that if one FSS fn calls another, the second does not require a stack switch -- at least this is true if those calls occur quickly after the stack, without many intervening frames.

In addition, whenever an extern "C" fn is called, the cstack lint checks that the caller has a FSS annotation OR that the callee is annotated "rust_stack", meaning that it operates in the red-zone.

I propose a few revisions:

• A new #[stack] annotation to replace the existing two
• Small changes to the FSS allocation protocol in morestack
• Use of guard pages (if we don't already)

New annotation: #[stack]

I propose a revised annotation #[stack(size)] where size can be:

• A specific number of extra bytes.
• none -- the default, no extra bytes, useful for annotating extern fns (see below)
• small, medium, or large -- some arbitrarily chosen constants
• fixed -- requests a FSS (see below for more details)

This annotations requests extra stack space on top of the usual amount that is required for the fns allocas. It can be used to alleviate specific performance problems with stack-switching. For example, if it happens in profiles that fn A calls fn B many times and fn B often has to switch stacks, that can be expensive: annotating fn A with #[stack(medium)] or some such may address the issue.

Extern fn declarations can also be labelled with explicit #[stack] annotations. The cstack lint will ensure that amount of stack is available. The default is fixed. This mechanism replaces the current rust_stack annotation. Note that a stack(none) annotation would be used to indicate an extern fn that operates in the red zone.

FSS allocation mechanism

The current "overallocation" scheme for FSS is risky. If a C callback invokes a Rust fn, this scheme could lead to multiple FSS stacks being allocated. I think in general once we switch to a FSS, we should not switch stacks ever again.

To this end, we can signal a FSS by setting the stack limit to 0 (for downward growing stacks). FSS functions will not check for 2MB of space but rather check for a limit of 0, indicating a FSS. They will call into morestack requesting MAX_UINT bytes. Morestack will allocate a fixed segment and set stack limit to 0 and then return.

Guard pages

To prevent actual stack overrun, a guard page is used to catch programs that recurse too far (as is standard). Note that this also requires that we follow the typical protocol of "touching" the stack every 4K for functions with huge stack frames: hopefully LLVM has an option for this? It's not an unusual requirement afaik. (We probably want a guard page in all scenarios, not just FSS)

LLVM inlining

In an ideal world, we would modify the LLVM inliner to avoid inlining functions with a larger stack annotation into functions with a smaller one. This prevents "stack creep" and avoids the need for the manual #[inline(never)] annotations we currently have.

Parting thoughts

I am unsure about the proper interaction between "fixed" stack segments and other stack segment requests. Above I outlined a protocol where switching to a fixed segment never switches again. I am not sure how well this interacts with the idea that tasks should default to a large stack and so forth. This might require some tweaking.

Thoughts?

Paging @brson and @pcwalton for sure, though I'm sure others will have an opinion.

[metajack]

+1 for the new annotation syntax, except that I think that we should forbid #[stack] alone, as it's not clear at all what it's doing.

[alexcrichton]

Could you elaborate a bit more on how the guard pages will work? Is this attempting to remove calls to __morestack entirely? Right now that keeps us from overrunning the stack, but if we're using guard pages instead I presume we wouldn't use that function.

[thestinger]

It seems like we could simply use __morestack, but teach LLVM to omit the calls for functions under a configured size. The only issue I can see with guard pages it that it means the smallest stack size will likely be 8K, since we need to ask for 2 pages from mmap and mprotect the second.

[nikomatsakis]

I am not entirely sure what the precise interaction between guard pages and morestack should be. Guard pages cannot replace morestack entirely. Errors detected via guard pages are non-recoverable, unlike morestack which can allocate more stack and then switch the current stack pointer. So if we wish to dynamically grow our stacks, we need morestack. But if we just want to detect stack overrun and fail in response, a guard page is adequate -- and, of course, when running non-instrumented code (like C code) a guard page is basically the only protection you can have.

[alexcrichton]

It sounds like this is two different modes of compilation.

On one hand, you have segmented stacks that could be very small. The stack attribute would dictate what the __morestack requests for in terms of allocation size for the current function. This is basically what exists today except that you would have finer-grained control over the allocated stack size (with this new attribute).

On the other hand, you don't have segmented stacks at all. This would require using guard pages and having one monolithically growing stack (per thread? maybe this mode has no runtime anyway?). We would instruct LLVM to emit a function like windows' _chkstk. For all functions require less than one page of stack space, this function is omitted. For all functions requiring a page or more, this function would ensure that the stack space is available, allocating more if necessary.

I suppose though that one mixture of these two would be that when we allocate a "large stack segment" we could be sure to allocate one with a guard page at the end. This would ensure that the C function you're about to call doesn't overrun (as long as the overrunning function doesn't request more than 1 page of stack).

[nikomatsakis]

I agree they are distinct modes, but I don't think they need to be distinct modes of compilation. Even if you are using segmented stacks, there are times you want to shift (temporarily) to a large stack -- calling a C function being a notable example. The real question is whether, once you shift to a large stack chunk, you wish to continue allocating further stack chunks, or whether you are done switching at that point.

[thestinger]

@nikomatsakis: You can catch the SIGSEGV signal and check if it was caused by a specific guard page, but I guess you've already generated a corrupt program state by then.

[nikomatsakis]

@thestinger my point was that you can't recover from this state, except perhaps by killing the relevant task (killing the task would require some finesse but is possible, I imagine). You can't, for example, allocate a new chunk of stack and start using that instead.

[brson]

I'm generally ok with this plan, though it makes me a bit sad to say that once you hit an FSS you stop growing the stack.

All the fixed, medium, etc. attributes will require more rust-specific attributes in LLVM (each will be a different llvm annotation unless they've made their system more expressive recently). The more of these we have the harder time we're going to have upstreaming.

"FSS functions will not check for 2MB of space but rather check for a limit of 0, indicating a FSS" - this sounds like it requires an entirely different prologue, which requires a bunch of platform-specific llvm changes. This is more rust-specific code to upstream.

Having rust code operate when the stack limit is 0 means that we have to fall back to TLS to retrieve the task pointer in those cases. This will result in the runtime being slightly slower in C callbacks.

What do you mean 'we will probably want a guard page in all scenarios'? Why else is it required besides preventing overflow on the FSS?

I think we should not be inlining FSS functions into non-FSS functions and I'm not clear on the current semantics there.

[brson]

I guess the #[stack(small)] etc. annotations would leave open the possibility of stack overflow if all segments did not have guard pages. Putting guard pages on all segments seems like a huge waste though.

[nikomatsakis]

I think I was just concerned about handling the case where you call a C library that is improperly annotated and it runs over. Perhaps this is not worth guarding against. Also, minimizing LLVM churn might be a valid constraint, in which case this plan is not the best. In particular, I am not sure if the idea of "switching to FSS and never switching back" makes sense or not. Mostly though I am concerned about this scenario:

• You call into C code, switching to a (let's say) 3MB stack beacuse you requested a 2MB
• You get a callback after 1MB of stack is consumed and call another C function
• At this point, you have 2MB of stack left, but we'll switch to another 3MB stack

Perhaps rather than having FSS be a separate mode what is needed is to separate out the minimum stack you require vs the amount you allocate if that minimum is unavailable. That is, just tweak the current system, essentially. And I'd probably remove the word "fixed" and just have small/med/large. Made medium is the default, and it requires something like 512K but allocates 2MB, whereas large requires 1MB. Or something. Probably better to do some measurements of stack depth for popular C libraries to get an idea what good numbers are (and maybe have those thresholds be tweakable via runtime calls?)

[nikomatsakis]

Well, we can't tweak the thresholds we check, but we can tweak how much memory is allocated.

[nikomatsakis]

@brson and @pnkfelix and I had a discussion about this. I think that we settled on not having a notion of fixed vs unfixed but instead having a scheme like so:

• You can annotate functions with #[stack(SIZE)] where SIZE is either zero, small, medium, or large. If SIZE is omitted, then large is assumed. (?)
• On Rust fn items, these annotations override the normal stack request mechanism. They cause the header to check for C bytes of stack and then, if C bytes are not present, request R bytes of stack, where C and R depend on SIZE as defined in the table below.
• On extern fn items, these annotations document the expected stack requirements (perhaps a separate annotation would be clearer?). The default size if an extern fn is not annotated is large.
• The linter will check that every call to an extern fn annotated with #[stack(E)] occurs inside a Rust fn annotated with #[stack(F)] where F > E. As a special case, if E is zero, then the fn can be called from any Rust fn without error (this is the equivalent of today's #[rust_stack] annotation).
• A separate linter will warn about #[stack(zero)] being applied to a Rust fn item, which is almost certainly an error!

Stack-size table. Naturally I pulled these numbers out of thin air and we should actually do some empirical investigation to try and figure out useful thresholds.

Size    C     R
zero    0     0
small   256  512
medium  512  1MB
large   1MB  2MB

This scheme is relatively simple and consistent. Like any scheme, it can perform poorly in some pathological scenarios, but that is true of the fixed stack segment scheme as well. An advantage of this scheme is that it means that Rust code can always rely on the invariant that limitless recursion is permitted.

[alexcrichton]

Nominating for backcompat-lang and 1.0