Make split stacks (segmented stacks) optional #8345

Closed
bstrie opened this Issue Aug 6, 2013 · 13 comments

Comments

Projects
None yet
6 participants
@bstrie
Contributor

bstrie commented Aug 6, 2013

I know this has been discussed before, but I couldn't find a bug for it. I believe @thestinger is of the opinion that the constant overhead of split stacks and the narrow use case (spawning enormous numbers of I/O-bound tasks on 32-bit architectures) isn't acceptable, and will keep Rust from ever matching the performance of C++.

I remember at least some of the developers (pcwalton? brson?) saying that split stacks won't go away, but could become optional. I can't seem to find the dicussions, though.

Making segmented stacks optional should also simplify runtimeless Rust (#3608).

@alexcrichton

This comment has been minimized.

Show comment
Hide comment
@alexcrichton

alexcrichton Aug 6, 2013

Member

From a "runtimeless rust" perspective, this is a bit of a nuanced issue. I believe that there are a few viable modes of operation which may be desired for "split stacks":

  1. You use the default split stacks. This means LLVM is configured to emit calls to __morestack and you're linking to librustrt and libmorestack to provide the corresponding implementations. As the default mode, this will prevent running over the maximum stack limit, and you will automatically switch stacks once you hit the stack limit (as determined by the runtime).
  2. You do not want the default __morestack implementation, you are saying that you will provide your own. This implies that librustrt and libmorestack are not linked to by default. This means that LLVM will still emit instrumentation at the prologue of each function, but you will get a linker error if you don't link to a library with a function called __morestack.
  3. You don't even want instrumentation. This means that LLVM will cease emission of prologues, and rustrt/morestack aren't linked to by default.

I think that the vast majority of people will fall into option 1 (they're just using rust normally), and then a large portion of the remaining people will fall into bucket 3. In bucket 3 there are no assumptions made about the stack, and it's up to your own runtime to guarantee that you have enough. This could involve allocating guard pages, but regardless the compiler doesn't need to know about it.

@thestinger brings up a good point though in that option 2 should not be left out. There are many situations where stack overflow is a serious problem, and having checks against that is very beneficial. The downside of this option is the stack limit must be stored in one particular location (where LLVM expects it). I think that the most difficult part here will be clearly documenting what option 2 implies for each architecture. From a user's perspective they'll have to ensure that the stack limit is in the right place before calling any rust code (or use a #[no_split_stack] attribute).

From that, as an actionable item, I would propose the following following states based on crate attributes:

  • no attributes - the is the default behavior as it is today. You link against libstd by default, you've got segmented stacks, and the support for those comes from librustrt and libmorestack
  • no_std - this is as it is today, it simply disables linking against libstd by default (note that librustrt and libmorestack are still linked by default). You'd be able to still access the C++ runtime, but it wouldn't be there by default (it's just supporting split stacks through malloc, I'm not sure if this works right now)
  • no_default_morestack - disables linking to librustrt and libmorestack by default. This encompasses case 2 above, and it implies the no_std attribute (because libstd depends on librustrt)
  • no_split_stack - disables segmented stacks entirely for the crate as a whole (case 3). Furthermore, this implies no_default_morestack which in turn implies no_std.

What do others think about this? These attributes have diverged a bit from discussing optional split stacks to more of a runtimeless-rust, but most of this is still about split stacks so I decided to leave it here rather than on the metabug.

Member

alexcrichton commented Aug 6, 2013

From a "runtimeless rust" perspective, this is a bit of a nuanced issue. I believe that there are a few viable modes of operation which may be desired for "split stacks":

  1. You use the default split stacks. This means LLVM is configured to emit calls to __morestack and you're linking to librustrt and libmorestack to provide the corresponding implementations. As the default mode, this will prevent running over the maximum stack limit, and you will automatically switch stacks once you hit the stack limit (as determined by the runtime).
  2. You do not want the default __morestack implementation, you are saying that you will provide your own. This implies that librustrt and libmorestack are not linked to by default. This means that LLVM will still emit instrumentation at the prologue of each function, but you will get a linker error if you don't link to a library with a function called __morestack.
  3. You don't even want instrumentation. This means that LLVM will cease emission of prologues, and rustrt/morestack aren't linked to by default.

I think that the vast majority of people will fall into option 1 (they're just using rust normally), and then a large portion of the remaining people will fall into bucket 3. In bucket 3 there are no assumptions made about the stack, and it's up to your own runtime to guarantee that you have enough. This could involve allocating guard pages, but regardless the compiler doesn't need to know about it.

@thestinger brings up a good point though in that option 2 should not be left out. There are many situations where stack overflow is a serious problem, and having checks against that is very beneficial. The downside of this option is the stack limit must be stored in one particular location (where LLVM expects it). I think that the most difficult part here will be clearly documenting what option 2 implies for each architecture. From a user's perspective they'll have to ensure that the stack limit is in the right place before calling any rust code (or use a #[no_split_stack] attribute).

From that, as an actionable item, I would propose the following following states based on crate attributes:

  • no attributes - the is the default behavior as it is today. You link against libstd by default, you've got segmented stacks, and the support for those comes from librustrt and libmorestack
  • no_std - this is as it is today, it simply disables linking against libstd by default (note that librustrt and libmorestack are still linked by default). You'd be able to still access the C++ runtime, but it wouldn't be there by default (it's just supporting split stacks through malloc, I'm not sure if this works right now)
  • no_default_morestack - disables linking to librustrt and libmorestack by default. This encompasses case 2 above, and it implies the no_std attribute (because libstd depends on librustrt)
  • no_split_stack - disables segmented stacks entirely for the crate as a whole (case 3). Furthermore, this implies no_default_morestack which in turn implies no_std.

What do others think about this? These attributes have diverged a bit from discussing optional split stacks to more of a runtimeless-rust, but most of this is still about split stacks so I decided to leave it here rather than on the metabug.

@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Aug 6, 2013

Contributor

I don't think we should have no_split_stack at all. If we did, every function would have to be marked unsafe. It probably makes more sense to omit it on a function-by-function basis, and require that those functions be unsafe so that the caller is responsible for making sure there's enough stack space for them.

The solution to the 1-5% performance hit from the checks is to use guard pages and only insert the check when functions allocate more than the guard page size - it shouldn't be too hard to teach LLVM to omit them in those cases.

Contributor

thestinger commented Aug 6, 2013

I don't think we should have no_split_stack at all. If we did, every function would have to be marked unsafe. It probably makes more sense to omit it on a function-by-function basis, and require that those functions be unsafe so that the caller is responsible for making sure there's enough stack space for them.

The solution to the 1-5% performance hit from the checks is to use guard pages and only insert the check when functions allocate more than the guard page size - it shouldn't be too hard to teach LLVM to omit them in those cases.

@alexcrichton

This comment has been minimized.

Show comment
Hide comment
@alexcrichton

alexcrichton Aug 6, 2013

Member

Omitting no_split_stack doesn't quite sit well with me. It's certainly unreasonable to mark every function in a crate as unsafe (plus that defeats the whole point of unsafe analysis). I'm not worried here about the performance hit at all, I think that's an entirely separate discussion from this.

If rust is a language which wants to target everything, then I think it should be configurable in almost every way. I can think that perhaps various microcontrollers or kernels don't need to bother with stack protection and it just provides an extra burden to define.

That being said, it would be very easy to emulate no_split_stack by using no_default_morestack and then writing a no-op __morestack function. I think that that's a bit of a hacky solution which is encompassed better in no_split_stack.

Thinking about it though, I can't think of too many strategies that would actually be taken, so there would probably be just a few libraries (maybe officially maintained?) which provide this functionality.

  • First we've got the default librustrt
  • Then there could be the windows-like library which allocates guard pages and tells LLVM to skip checks on functions with < 1 page of stack space.
  • Finally there could be a library that just invokes a function on stack overflow

Regardless though, I think that there should be a no_split_stack attribute and there should be a large amount of documentation on the various directions you can take with stack management in rust.

Member

alexcrichton commented Aug 6, 2013

Omitting no_split_stack doesn't quite sit well with me. It's certainly unreasonable to mark every function in a crate as unsafe (plus that defeats the whole point of unsafe analysis). I'm not worried here about the performance hit at all, I think that's an entirely separate discussion from this.

If rust is a language which wants to target everything, then I think it should be configurable in almost every way. I can think that perhaps various microcontrollers or kernels don't need to bother with stack protection and it just provides an extra burden to define.

That being said, it would be very easy to emulate no_split_stack by using no_default_morestack and then writing a no-op __morestack function. I think that that's a bit of a hacky solution which is encompassed better in no_split_stack.

Thinking about it though, I can't think of too many strategies that would actually be taken, so there would probably be just a few libraries (maybe officially maintained?) which provide this functionality.

  • First we've got the default librustrt
  • Then there could be the windows-like library which allocates guard pages and tells LLVM to skip checks on functions with < 1 page of stack space.
  • Finally there could be a library that just invokes a function on stack overflow

Regardless though, I think that there should be a no_split_stack attribute and there should be a large amount of documentation on the various directions you can take with stack management in rust.

@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Aug 6, 2013

Contributor

Why bother having unsafe at all, if we're not guaranteeing other functions are memory safe? Memory safety has to be black or white, or Rust is no better than C++. A thread overrunning the stack and clobbering memory of other threads is a big deal.

An alternative is to forbid functions using more than N stack space, and reserve N space as guard pages. If you don't have virtual memory you need __morestack to provide memory safety though.

Contributor

thestinger commented Aug 6, 2013

Why bother having unsafe at all, if we're not guaranteeing other functions are memory safe? Memory safety has to be black or white, or Rust is no better than C++. A thread overrunning the stack and clobbering memory of other threads is a big deal.

An alternative is to forbid functions using more than N stack space, and reserve N space as guard pages. If you don't have virtual memory you need __morestack to provide memory safety though.

@bstrie

This comment has been minimized.

Show comment
Hide comment
@bstrie

bstrie Aug 7, 2013

Contributor

Nominating for Well-Covered (unless this is a backwards-incompatible issue and I'm oblivious).

Contributor

bstrie commented Aug 7, 2013

Nominating for Well-Covered (unless this is a backwards-incompatible issue and I'm oblivious).

@brson

This comment has been minimized.

Show comment
Hide comment
@brson

brson Aug 8, 2013

Contributor

The conclusion was that we would always use split stacks, but on 64-bit platforms with overcommit we would make the initial segment large enough that it doesn't need to grow in typical use. This was also already implemented in the old runtime.

For freestanding Rust the question is more open - certainly one can build without split stacks if they like.

Contributor

brson commented Aug 8, 2013

The conclusion was that we would always use split stacks, but on 64-bit platforms with overcommit we would make the initial segment large enough that it doesn't need to grow in typical use. This was also already implemented in the old runtime.

For freestanding Rust the question is more open - certainly one can build without split stacks if they like.

@bstrie

This comment has been minimized.

Show comment
Hide comment
@bstrie

bstrie Aug 8, 2013

Contributor

In that case I'm happy to close. Anyone can reopen this if they feel that there's more to discuss.

Contributor

bstrie commented Aug 8, 2013

In that case I'm happy to close. Anyone can reopen this if they feel that there's more to discuss.

@bstrie bstrie closed this Aug 8, 2013

@alexcrichton

This comment has been minimized.

Show comment
Hide comment
@alexcrichton

alexcrichton Aug 8, 2013

Member

Right now there's no way (that I know of) to build programs without split stacks, so if we want to support that shouldn't the issue stay open?

Member

alexcrichton commented Aug 8, 2013

Right now there's no way (that I know of) to build programs without split stacks, so if we want to support that shouldn't the issue stay open?

@thestinger thestinger reopened this Aug 8, 2013

@thestinger thestinger closed this Aug 8, 2013

@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Aug 8, 2013

Contributor

There's another issue open about the relevant part from here: #5768

Contributor

thestinger commented Aug 8, 2013

There's another issue open about the relevant part from here: #5768

@alexcrichton

This comment has been minimized.

Show comment
Hide comment
@alexcrichton

alexcrichton Aug 8, 2013

Member

That seems like a relevant issue, but not the same to me. That's talking more about a configurable stack size while this is talking about configuring whether a call to __morestack is even emitted.

I agree with @brson that for a freestanding rust it should be possible to build without split stacks, so reopening.

Member

alexcrichton commented Aug 8, 2013

That seems like a relevant issue, but not the same to me. That's talking more about a configurable stack size while this is talking about configuring whether a call to __morestack is even emitted.

I agree with @brson that for a freestanding rust it should be possible to build without split stacks, so reopening.

@alexcrichton alexcrichton reopened this Aug 8, 2013

@toddaaro

This comment has been minimized.

Show comment
Hide comment
@toddaaro

toddaaro Aug 17, 2013

Contributor

Something kind of relevant is that split stacks are not yet implemented in the new runtime, they loom large on the todo list though.

Contributor

toddaaro commented Aug 17, 2013

Something kind of relevant is that split stacks are not yet implemented in the new runtime, they loom large on the todo list though.

@catamorphism

This comment has been minimized.

Show comment
Hide comment
@catamorphism

catamorphism Sep 12, 2013

Contributor

Not in scope for a milestone

Contributor

catamorphism commented Sep 12, 2013

Not in scope for a milestone

@thestinger

This comment has been minimized.

Show comment
Hide comment
@thestinger

thestinger Nov 15, 2013

Contributor

Segmented stacks have been removed so this is no longer relevant.

Contributor

thestinger commented Nov 15, 2013

Segmented stacks have been removed so this is no longer relevant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment