More on stack safety

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

More on stack safety

Corey Richardson
I've written up more thoughts on stack safety at
http://cmr.github.io/blog/2013/10/28/more-on-stack-safety/. If no one
objects to it (meeting tomorrow!) or has any better ideas, I'll start
implementing it.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Niko Matsakis
If I understand correctly, what you are proposing is to offer fixed
size stacks and to use a guard page to check for stack overflow (vs a
stack preamble)?

My two thoughts are:

1. I do think segmented stacks offer several tangible benefits:

- Recursion limited only by available memory / address space
- Avoid chewing up address space on 32 bit builds

However, I can accept that on balance they are not worth the price,
given that point #2 is probably not that important for 64-bit systems.

It is sad to lose limitless recursion but typically one can rewrite
routines that recurse arbitrarily deep to use a stack on the heap,
though sometimes the code is very unnatural, and using a stack on the
heap will not play as well with lifetimes, since the compiler doesn't
know that you are obeying a stack discipline.

2. I think that our official semantics for stack overflow should be
task failure, not abort. There are some technical challenges to be
overcome with regard to the best way to signal/detect stack overflow,
and I'm fine with this being a "todo" item (possibly for a long time).
But abort is wrong.

One non-technical difficulty to failing on overflow is how to handle
user-defined destructors when there is no stack to run them on -- but
I think this is adequately addressed by keeping a red zone (so that
simple dtors work) and implementing Graydon's plan for handling
recursive failure otherwise. We also have to modify drop glue to not
be recursive (see point #1 about the convenience of limitless
recursion -- though of course drop glue must be ready for OOM as
well).


Niko

On Tue, Oct 29, 2013 at 01:23:22AM -0400, Corey Richardson wrote:
> I've written up more thoughts on stack safety at
> http://cmr.github.io/blog/2013/10/28/more-on-stack-safety/. If no one
> objects to it (meeting tomorrow!) or has any better ideas, I'll start
> implementing it.
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Corey Richardson
On Tue, Oct 29, 2013 at 7:08 AM, Niko Matsakis <[hidden email]> wrote:

> If I understand correctly, what you are proposing is to offer fixed
> size stacks and to use a guard page to check for stack overflow (vs a
> stack preamble)?
>
> My two thoughts are:
>
> 1. I do think segmented stacks offer several tangible benefits:
>
> - Recursion limited only by available memory / address space
> - Avoid chewing up address space on 32 bit builds
>
> However, I can accept that on balance they are not worth the price,
> given that point #2 is probably not that important for 64-bit systems.
>
> It is sad to lose limitless recursion but typically one can rewrite
> routines that recurse arbitrarily deep to use a stack on the heap,
> though sometimes the code is very unnatural, and using a stack on the
> heap will not play as well with lifetimes, since the compiler doesn't
> know that you are obeying a stack discipline.
>

I agree. This is why I think fixed-size stacks feel like a step
backwards. There's still room to have optional segmented stacks, but
it's going to require a lot of extra complexity to do right.

> 2. I think that our official semantics for stack overflow should be
> task failure, not abort. There are some technical challenges to be
> overcome with regard to the best way to signal/detect stack overflow,
> and I'm fine with this being a "todo" item (possibly for a long time).
> But abort is wrong.
>

I don't know how to go about doing this, but am open to it.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Igor Bukanov
In reply to this post by Niko Matsakis
On 29 October 2013 12:08, Niko Matsakis <[hidden email]> wrote:
> 1. I do think segmented stacks offer several tangible benefits:
>
> - Recursion limited only by available memory / address space

This is a weak argument. If one needs that much memory, then using an
explicit stack is a must as it allows for significantly more compact
memory presentation.

>
> 2. I think that our official semantics for stack overflow should be
> task failure, not abort.

Just for consideration, SpiderMonkey uses a lot of explicit stack
depth checks , see
http://mxr.mozilla.org/mozilla-central/ident?i=JS_CHECK_RECURSION&tree=mozilla-central&filter=
It would be nice if Rust would allow to avoid them. And if aborting is
the only good option for performance reasons then having an API to do
those checks manually is a must to have.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Niko Matsakis
On Tue, Oct 29, 2013 at 04:21:35PM +0100, Igor Bukanov wrote:
> This is a weak argument. If one needs that much memory, then using an
> explicit stack is a must as it allows for significantly more compact
> memory presentation.

I considered this when I wrote the e-mail. I partially agree but not
fully. Let me expound some.

In general, both segmented stacks and an explicit stack on the heap
have the property that if you add more RAM, you can get more work
done. I agree that using a stack on the heap offers a better constant
factor (that is, a better work-to-RAM ratio), but that may not be the
relevant point for all use cases.

This debate is not new: we've been considering whether or not to keep
segmented stacks for a while. Originally I thought as you do, that one
should just not write recursion whose depth is proportional to the
input, for fear of overflow. In past compilers I've worked on we tried
to obey this rule, since people always managed to surprise us with the
complexity of inputs they would provide.

But I've been watching the code I write now and I've found that many
times a recursion-based solution is much cleaner. Moreover, since we
integrate recursion specially with the type system in the form of
lifetimes, it can also express things that are more awkward with a
heap vector.

All that said, probably the most important thing is that we have
graceful failure on stack overflow (even an abort is perhaps adequate,
though obviously a proper failure is better). This permits users to
start with recursion-based code and either convert to heap-based code
or allocate bigger stack frames when they start to hit limits.
Obviously no one is proposing segfaulting on stack overflow, so I
guess I will be satisfied. :)


Niko
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Igor Bukanov
In reply to this post by Niko Matsakis
On 29 October 2013 12:08, Niko Matsakis <[hidden email]> wrote:
> One non-technical difficulty to failing on overflow is how to handle
> user-defined destructors when there is no stack to run them on

From C++ experience the need to handle recursion comes from code like
parsers or tree-like structure navigation. In such cases the only
relevant destructors are those that release heap-allocated memory.
This suggests to have a module or function level annotation that
states that the code does not run custom destructors. Then the runtime
can provide a function like run_with_stack_check_enabled() that runs
such destructor-less code while allowing to recover from the stack
overflow. Then the only problem would be to properly release all
~temporaries.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Igor Bukanov
In reply to this post by Niko Matsakis
On 29 October 2013 16:43, Niko Matsakis <[hidden email]> wrote:
> But I've been watching the code I write now and I've found that many
> times a recursion-based solution is much cleaner. Moreover, since we
> integrate recursion specially with the type system in the form of
> lifetimes, it can also express things that are more awkward with a
> heap vector.

My "weak argument" was referring to the recursion that uses tons of
memory, not to the idea of using recursion at all. Clearly there are
some very practical cases like parsers where total recursion avoidance
is not an option if one wants to stay with maintainable code and yet
it is desirable to support deeply nested structures. The question is
how common those cases to justify a performance impact by default for
the rest of code. From the experience I suppose this is rare so it
should be fine to require special annotations and/or special setup
when calling into such code as long as the stack overflow in general
is not worse than an explicit abort.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Daniel Micay
In reply to this post by Niko Matsakis
On Tue, Oct 29, 2013 at 7:08 AM, Niko Matsakis <[hidden email]> wrote:
If I understand correctly, what you are proposing is to offer fixed
size stacks and to use a guard page to check for stack overflow (vs a
stack preamble)?

My two thoughts are:

1. I do think segmented stacks offer several tangible benefits:

- Recursion limited only by available memory / address space
- Avoid chewing up address space on 32 bit builds

However, I can accept that on balance they are not worth the price,
given that point #2 is probably not that important for 64-bit systems.

It is sad to lose limitless recursion but typically one can rewrite
routines that recurse arbitrarily deep to use a stack on the heap,
though sometimes the code is very unnatural, and using a stack on the
heap will not play as well with lifetimes, since the compiler doesn't
know that you are obeying a stack discipline.

2. I think that our official semantics for stack overflow should be
task failure, not abort. There are some technical challenges to be
overcome with regard to the best way to signal/detect stack overflow,
and I'm fine with this being a "todo" item (possibly for a long time).
But abort is wrong.

One non-technical difficulty to failing on overflow is how to handle
user-defined destructors when there is no stack to run them on -- but
I think this is adequately addressed by keeping a red zone (so that
simple dtors work) and implementing Graydon's plan for handling
recursive failure otherwise. We also have to modify drop glue to not
be recursive (see point #1 about the convenience of limitless
recursion -- though of course drop glue must be ready for OOM as
well).

If we want to unwind on task failure, we'll need to disable the `prune-eh` pass that bubbles up `nounwind` since every function will be able to unwind. I think it will cause a very significant increase in code size.

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Ziad Hatahet

--
Ziad


On Tue, Oct 29, 2013 at 1:24 PM, Daniel Micay <[hidden email]> wrote:
On Tue, Oct 29, 2013 at 7:08 AM, Niko Matsakis <[hidden email]> wrote:
If I understand correctly, what you are proposing is to offer fixed
size stacks and to use a guard page to check for stack overflow (vs a
stack preamble)?

My two thoughts are:

1. I do think segmented stacks offer several tangible benefits:

- Recursion limited only by available memory / address space
- Avoid chewing up address space on 32 bit builds

However, I can accept that on balance they are not worth the price,
given that point #2 is probably not that important for 64-bit systems.

It is sad to lose limitless recursion but typically one can rewrite
routines that recurse arbitrarily deep to use a stack on the heap,
though sometimes the code is very unnatural, and using a stack on the
heap will not play as well with lifetimes, since the compiler doesn't
know that you are obeying a stack discipline.

2. I think that our official semantics for stack overflow should be
task failure, not abort. There are some technical challenges to be
overcome with regard to the best way to signal/detect stack overflow,
and I'm fine with this being a "todo" item (possibly for a long time).
But abort is wrong.

One non-technical difficulty to failing on overflow is how to handle
user-defined destructors when there is no stack to run them on -- but
I think this is adequately addressed by keeping a red zone (so that
simple dtors work) and implementing Graydon's plan for handling
recursive failure otherwise. We also have to modify drop glue to not
be recursive (see point #1 about the convenience of limitless
recursion -- though of course drop glue must be ready for OOM as
well).

If we want to unwind on task failure, we'll need to disable the `prune-eh` pass that bubbles up `nounwind` since every function will be able to unwind. I think it will cause a very significant increase in code size.

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev



_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Daniel Micay
I don't think anything but (correct) strict static analysis would have helped in that case. Embedded systems often avoid dynamic memory allocation completely, because dynamic out-of-memory conditions would be unacceptable. That's likely why there was so much data on the stack in the first place. A growable segmented stack is the opposite of robustness, in a case like that.

Unwinding on out-of-stack is more robust than aborting, but losing the entire context of a task is often going to be totally unacceptable. If every function call can unwind, it also makes it much harder to write memory-safe low-level code. In a web browser, it's going to be okay for most tasks to unwind. It's not going to be a very viable solution for truly robust embedded systems.

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Niko Matsakis
In reply to this post by Daniel Micay
On Tue, Oct 29, 2013 at 04:24:49PM -0400, Daniel Micay wrote:
> If we want to unwind on task failure, we'll need to disable the `prune-eh`
> pass that bubbles up `nounwind` since every function will be able to
> unwind. I think it will cause a very significant increase in code size.

That's too bad, but safety and sensible error recovery comes first. As
pcwalton said, if you have an image decoder that has a bug which leads
to infinite recursion, it's just not acceptable for that to crash your
*entire process*.

That said, I imagine we could recover some code size improvements by
having an LLVM pass that (1) identified when function X calls function
Y unconditionally; (2) combined the overflow check for X and Y; and
then (3) removes exception handling around calls to Y. Obviously this
would be more complex.


Niko
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Ben Kloosterman
In reply to this post by Niko Matsakis



On Tue, Oct 29, 2013 at 7:08 PM, Niko Matsakis <[hidden email]> wrote:
If I understand correctly, what you are proposing is to offer fixed
size stacks and to use a guard page to check for stack overflow (vs a
stack preamble)?

My two thoughts are:

1. I do think segmented stacks offer several tangible benefits:

- Recursion limited only by available memory / address space
- Avoid chewing up address space on 32 bit builds

However, I can accept that on balance they are not worth the price,
given that point #2 is probably not that important for 64-bit systems.

It is sad to lose limitless recursion but typically one can rewrite
routines that recurse arbitrarily deep to use a stack on the heap,
though sometimes the code is very unnatural, and using a stack on the
heap will not play as well with lifetimes, since the compiler doesn't
know that you are obeying a stack discipline.

Fixed stacks can be expanded once you have precise collection ( help will come from LLVM eventually...).

What i think hasnt been discussed ( though it has previously) is  how much of a penalty segmented stacks represent and what it could be ..

In terms of memory allocations a faster expansion or greater reuse from a segment pool  ( Why does the scheduler segment pool  start empty. I would have thought you would have  2Meg worth pre allocated - one runs in the context of a microbench the other allocated before hand ( like C stacks) ) .  a 4^N expansion of each stack  would result in more contigous stacks. And if stack is unused for a long time hand some segments back.  

In terms of the stack size check  , as has been mentioned you can do more with some analysis  , each method gives an indication of worst cases stack growth , these can then be added together to reduces checks by 80% and hence significantly reduce the performance impact .

Though obviously for production release soon you will get there faster with fixed stacks earlier. 

Ben 

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Patrick Walton-2
On 10/29/13 11:43 PM, Ben Kloosterman wrote:
> What i think hasnt been discussed ( though it has previously) is  how
> much of a penalty segmented stacks represent and what it could be ..

No, we tried all sorts of optimizations. Look in the history at the
scheduler code. That path was heavily optimized in the common case.

> In terms of memory allocations a faster expansion or greater reuse from
> a segment pool  ( Why does the scheduler segment pool  start empty. I
> would have thought you would have  2Meg worth pre allocated - one runs
> in the context of a microbench the other allocated before hand ( like C
> stacks) ) .  a 4^N expansion of each stack  would result in more
> contigous stacks. And if stack is unused for a long time hand some
> segments back.

We tried it. The performance cost was still very high compared to C.

I know Jonathan Shapiro also thinks that we didn't try hard enough, but
when you're competing against C function calls (2 ns?) there is
extremely little wiggle room. Even 10 instructions means you're at least
2x slower.

> In terms of the stack size check  , as has been mentioned you can do
> more with some analysis  , each method gives an indication of worst
> cases stack growth , these can then be added together to reduces checks
> by 80% and hence significantly reduce the performance impact .

Citation for the 80% number?

Patrick

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Sebastian Sylvan
In reply to this post by Corey Richardson
On Mon, Oct 28, 2013 at 10:23 PM, Corey Richardson <[hidden email]> wrote:
I've written up more thoughts on stack safety at
http://cmr.github.io/blog/2013/10/28/more-on-stack-safety/. If no one
objects to it (meeting tomorrow!) or has any better ideas, I'll start
implementing it.
 
Consider this: *if* you're only executing tasks that you know will never block (either due to IO, a concurrency primitive, or due to pre-emption) then you would only need a single stack per OS thread. These can be therefore be "big" (e.g. 1GB, lazily allocated, with logic to shrink it occasionally?).
 
This holds true if only 90% of tasks are non-blocking. For blocking tasks you can't use large stacks without risking that the task will block while holding on to all that address space (and even physical memory). So, if 90% of tasks run without blocking, you could run the remaining 10% of tasks with segmented stacks. Do all the usual heroic analysis to minimize cost of segmented stacks, but know that it only affects tasks that block, which would be a minority in this scheme.
 
One way to make sure that most tasks don't block is to make co-operative scheduling the default. IME you tend to have a lot of blocking at the bottom of a thread (for coordination), and then a whole bunch of work happening in functions that never touch any IO or OS primitives (and really don't need to be pre-empted either). If you can make sure the scheduler never pre-empts these tasks they can switch to a big stack as soon as they enter a function that doesn't block (known statically).
 
This way the vast majority of code executes without ever checking for stack sizes manually, and you still don't gobble up massive amounts of address space.
 
The big issue here then is really that rust tasks can be pre-empted, and therefore you can't guarantee that *any* function is free from blocking (which means you can't assign it a large stack, since it may go to sleep while holding it). IMO co-operative tasks (by default) is worth considering as a solution here. Then tag functions that don't block (transitively), and let those functions run on large stacks (unless you statically know that the current segmented stack space is enough.. you can save the switching cost in those cases).
 
Seb
 

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Ben Kloosterman



 
The big issue here then is really that rust tasks can be pre-empted, and therefore you can't guarantee that *any* function is free from blocking (which means you can't assign it a large stack, since it may go to sleep while holding it). IMO co-operative tasks (by default) is worth considering as a solution here. 

re Co operative tasks , I have bad memories of 3.X apps which could  lock the whole  OS/GUI  when in a tight loop ? Certainly not a solution for single core systems , even on dual system it can be an issue.  On quad+ there is some merit  but history has shown every addin /lib will use as many resources as they can ( eg flash add animations )  and not yield willingly.  It can be done but you need to check tasks with a schedule service task and if they dont behave pre-empt / reduce priority. 
 
Ben


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Niko Matsakis
Currently, Rust does not pre-empty. I still hope we can leverage the
O/S for pre-emption rather than having to implement it ourselves.


Niko

On Thu, Oct 31, 2013 at 10:07:51PM +0800, Ben Kloosterman wrote:

> >
> > The big issue here then is really that rust tasks can be pre-empted, and
> > therefore you can't guarantee that *any* function is free from blocking
> > (which means you can't assign it a large stack, since it may go to sleep
> > while holding it). IMO co-operative tasks (by default) is worth considering
> > as a solution here.
> >
>
> re Co operative tasks , I have bad memories of 3.X apps which could  lock
> the whole  OS/GUI  when in a tight loop ? Certainly not a solution for
> single core systems , even on dual system it can be an issue.  On quad+
> there is some merit  but history has shown every addin /lib will use as
> many resources as they can ( eg flash add animations )  and not yield
> willingly.  It can be done but you need to check tasks with a schedule
> service task and if they dont behave pre-empt / reduce priority.
>
> Ben

> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Ben Kloosterman
In reply to this post by Patrick Walton-2



In terms of the stack size check  , as has been mentioned you can do
more with some analysis  , each method gives an indication of worst
cases stack growth , these can then be added together to reduces checks
by 80% and hence significantly reduce the performance impact .

Citation for the 80% number?


Actually it was a guess based on the algoirithm in my head  but i did just find a paper which showed up to 89% of checks can be removed. 


Segmented stacks for Apache with highly concurrent workload.

" At 0.1% of call sites, checkpoints
caused a new stack chunk to be linked, at a cost of 27
instructions. At 0.4–0.5% of call sites, a large stack chunk
was linked unconditionally in order to handle an external
function, costing 20 instructions. At 10% of call sites, a
checkpoint determined that a new chunk was not required,
which cost 6 instructions. The remaining 89% of call sites
were unaffected. Assuming all instructions are roughly equal
in cost, the result is a 71–73% slowdown when considering
function calls alone. Since call instructions make up only
5% of the program’s instructions, the overall slowdown is
approximately 3% to 4%"

This is also interesting for a compiler that implements it.

Note im in the big stack and tune it down camp was just trying to work out why  segments were so bad. 

Ben

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: More on stack safety

Sebastian Sylvan
In reply to this post by Ben Kloosterman


On Thu, Oct 31, 2013 at 7:07 AM, Ben Kloosterman <[hidden email]> wrote:


 
The big issue here then is really that rust tasks can be pre-empted, and therefore you can't guarantee that *any* function is free from blocking (which means you can't assign it a large stack, since it may go to sleep while holding it). IMO co-operative tasks (by default) is worth considering as a solution here. 

re Co operative tasks , I have bad memories of 3.X apps which could  lock the whole  OS/GUI  when in a tight loop ? Certainly not a solution for single core systems , even on dual system it can be an issue.  On quad+ there is some merit  but history has shown every addin /lib will use as many resources as they can ( eg flash add animations )  and not yield willingly.  It can be done but you need to check tasks with a schedule service task and if they dont behave pre-empt / reduce priority. 
 
 
 

I do think there definitely needs to be a solution for actually pre-emptible threads (whether backed by OS or done in the language runtime). E.g. you might put third party code in there if it's something that will run for a long time. I'm just not sure that most tasks within your own code needs to be pre-empted to ensure they don't misbehave - you're in charge of them, make sure they don't soak up cycles for an unbounded period of time to avoid having starving the other tasks (the language RT would probably spawn up more OS threads if that happens, I'd imagine, which gets you back into the same area of eating up virtual address space by having more OS threads than HW threads, each of which has a dedicated "large stack" to run non-blocking tasks on)!

 


--
Sebastian Sylvan

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev