JVM support to avoid StackOverflowError

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

JVM support to avoid StackOverflowError

Justin Sampson
Howdy,

I'm curious if any proposals are being floated to somehow deal with
the problem of StackOverflowError arising inside concurrent code.
While writing a new synchronizer I keep obsessing over possible
error conditions, and this is the one I can't flush out.

I can carefully code around OutOfMemoryError by only allocating at
safe places, and I can brush off ThreadDeath just by yelling at
users to never call Thread.stop(). But StackOverflowError is the one
kind of error that I really can't code around, because it can happen
legitimately at any method call. The best I can do at the moment is
to reassure myself that it's not my fault, because ReentrantLock
has the same issue: http://bugs.java.com/view_bug.do?bug_id=7011862

For the sake of discussion, here's one solution that comes to mind.

First, define a "stack-limited" method to be a method that is not
recursive and that only calls other stack-limited methods, so that
it is possible for the JVM to determine an upper bound on its stack
usage.

Next, introduce two new standard annotations:

@StackLimited on a method declaration indicates that the method is
explicitly stack-limited. It is a compile error for any such method
to call any other method that is not also explicitly stack-limited
or to introduce any possibility of recursive invocation.

@StackSensitive on a method declaration indicates that the method is
explicitly stack-limited, with all the constraints of @StackLimited,
and also tells the JVM to proactively check the available stack
space and throw StackOverflowError immediately on entry to the
method if there is not enough stack for all possible executions of
the method.

The idea would be to annotate the minimum set of methods to ensure
that a synchronizer is never left in an invalid state due to stack
overflow. That would mostly be putting @StackLimited on the methods
of Unsafe, LockSupport, and the j.u.c.atomic package, and putting
@StackSensitive on just one or two methods in any given synchronizer
such as AQS.

Is something like this plausible, or even already in the works?

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich
Ahhh, the noble goal of hardening a system against async exceptions like OOM and SOE. :) Honestly, I've yet to see code that is 100% hardened against OOM.  Frankly, I'm not sure this is possible in java given there's a big machine that's running beneath you (i.e. JVM, which can throw OOM in places you wouldn't necessary expect), and this goes for SOE as well.  I'd love to be proven wrong though.



On Fri, Jan 23, 2015 at 6:37 PM, Justin Sampson <[hidden email]> wrote:
Howdy,

I'm curious if any proposals are being floated to somehow deal with
the problem of StackOverflowError arising inside concurrent code.
While writing a new synchronizer I keep obsessing over possible
error conditions, and this is the one I can't flush out.

I can carefully code around OutOfMemoryError by only allocating at
safe places, and I can brush off ThreadDeath just by yelling at
users to never call Thread.stop(). But StackOverflowError is the one
kind of error that I really can't code around, because it can happen
legitimately at any method call. The best I can do at the moment is
to reassure myself that it's not my fault, because ReentrantLock
has the same issue: http://bugs.java.com/view_bug.do?bug_id=7011862

For the sake of discussion, here's one solution that comes to mind.

First, define a "stack-limited" method to be a method that is not
recursive and that only calls other stack-limited methods, so that
it is possible for the JVM to determine an upper bound on its stack
usage.

Next, introduce two new standard annotations:

@StackLimited on a method declaration indicates that the method is
explicitly stack-limited. It is a compile error for any such method
to call any other method that is not also explicitly stack-limited
or to introduce any possibility of recursive invocation.

@StackSensitive on a method declaration indicates that the method is
explicitly stack-limited, with all the constraints of @StackLimited,
and also tells the JVM to proactively check the available stack
space and throw StackOverflowError immediately on entry to the
method if there is not enough stack for all possible executions of
the method.

The idea would be to annotate the minimum set of methods to ensure
that a synchronizer is never left in an invalid state due to stack
overflow. That would mostly be putting @StackLimited on the methods
of Unsafe, LockSupport, and the j.u.c.atomic package, and putting
@StackSensitive on just one or two methods in any given synchronizer
such as AQS.

Is something like this plausible, or even already in the works?

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Alexander Terekhov-2
In reply to this post by Justin Sampson
dejavu

http://www.programd.com/41_f4661b62296395b6_1.htm
http://lists.boost.org/Archives/boost/2003/10/54449.php

regards,
alexander.

Justin Sampson <[hidden email]>@cs.oswego.edu on 24.01.2015
00:37:30

Sent by: [hidden email]


To: "[hidden email]"
       <[hidden email]>
cc:
Subject: [concurrency-interest] JVM support to avoid StackOverflowError


Howdy,

I'm curious if any proposals are being floated to somehow deal with
the problem of StackOverflowError arising inside concurrent code.
While writing a new synchronizer I keep obsessing over possible
error conditions, and this is the one I can't flush out.

I can carefully code around OutOfMemoryError by only allocating at
safe places, and I can brush off ThreadDeath just by yelling at
users to never call Thread.stop(). But StackOverflowError is the one
kind of error that I really can't code around, because it can happen
legitimately at any method call. The best I can do at the moment is
to reassure myself that it's not my fault, because ReentrantLock
has the same issue: http://bugs.java.com/view_bug.do?bug_id=7011862

For the sake of discussion, here's one solution that comes to mind.

First, define a "stack-limited" method to be a method that is not
recursive and that only calls other stack-limited methods, so that
it is possible for the JVM to determine an upper bound on its stack
usage.

Next, introduce two new standard annotations:

@StackLimited on a method declaration indicates that the method is
explicitly stack-limited. It is a compile error for any such method
to call any other method that is not also explicitly stack-limited
or to introduce any possibility of recursive invocation.

@StackSensitive on a method declaration indicates that the method is
explicitly stack-limited, with all the constraints of @StackLimited,
and also tells the JVM to proactively check the available stack
space and throw StackOverflowError immediately on entry to the
method if there is not enough stack for all possible executions of
the method.

The idea would be to annotate the minimum set of methods to ensure
that a synchronizer is never left in an invalid state due to stack
overflow. That would mostly be putting @StackLimited on the methods
of Unsafe, LockSupport, and the j.u.c.atomic package, and putting
@StackSensitive on just one or two methods in any given synchronizer
such as AQS.

Is something like this plausible, or even already in the works?

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Justin Sampson
In reply to this post by Vitaly Davidovich
Vitaly Davidovich wrote:

> Ahhh, the noble goal of hardening a system against async
> exceptions like OOM and SOE. :) Honestly, I've yet to see code
> that is 100% hardened against OOM. Frankly, I'm not sure this is
> possible in java given there's a big machine that's running
> beneath you (i.e. JVM, which can throw OOM in places you wouldn't
> necessary expect), and this goes for SOE as well. I'd love to be
> proven wrong though.

To be clear, I'm not talking about hardening the whole system
against arbitrary async exceptions. OOME and SOE _can_ be thrown
asynchronously, but there are also well-defined places that they
happen synchronously. It seems at least plausible to be able to
harden certain low-level library code against such synchronous
exceptions, especially certain blocks of code within synchronizers
where there's a risk of leaving the synchronizer locked.

I've searched a little in the archives and I can see the issue at
least mentioned a couple of times, but wanted to get a sense of
whether any solutions were being considered. The links that
Alexander sent are very interesting history! -- but they're about
C++ and I couldn't quite ascertain the final outcome.

To make the idea even more constrained, imagine a method that only
calls other final or static Java methods or intrinsified native
methods, whether directly or indirectly, without any recursion, none
of which do any heap allocation (no new objects, arrays, boxing,
lambdas, varargs, etc.). Conceptually, the JIT could inline the
whole call tree into a single method body with a single stack frame.

Any call to such a method would throw SOE right up front if the
stack has been exhausted, avoiding any SOE's in the middle. (Any
class loading and initialization that might be triggered by the body
of the method would have to be executed immediately on entry to the
method as well, since they can trigger arbitrary exceptions and
errors.)

The strawman proposal in my prior email was simply to provide an
annotation that would request for the JVM to implement such
fail-fast behavior for the annotated methods, with compile-time
verification that it should be possible for the runtime to do so.

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

oleksandr otenko
In reply to this post by Justin Sampson
> It is a compile error for any such method
> to ... introduce any possibility of recursive invocation.

How would you do that?


Alex


On 23/01/2015 23:37, Justin Sampson wrote:

> Howdy,
>
> I'm curious if any proposals are being floated to somehow deal with
> the problem of StackOverflowError arising inside concurrent code.
> While writing a new synchronizer I keep obsessing over possible
> error conditions, and this is the one I can't flush out.
>
> I can carefully code around OutOfMemoryError by only allocating at
> safe places, and I can brush off ThreadDeath just by yelling at
> users to never call Thread.stop(). But StackOverflowError is the one
> kind of error that I really can't code around, because it can happen
> legitimately at any method call. The best I can do at the moment is
> to reassure myself that it's not my fault, because ReentrantLock
> has the same issue: http://bugs.java.com/view_bug.do?bug_id=7011862
>
> For the sake of discussion, here's one solution that comes to mind.
>
> First, define a "stack-limited" method to be a method that is not
> recursive and that only calls other stack-limited methods, so that
> it is possible for the JVM to determine an upper bound on its stack
> usage.
>
> Next, introduce two new standard annotations:
>
> @StackLimited on a method declaration indicates that the method is
> explicitly stack-limited. It is a compile error for any such method
> to call any other method that is not also explicitly stack-limited
> or to introduce any possibility of recursive invocation.
>
> @StackSensitive on a method declaration indicates that the method is
> explicitly stack-limited, with all the constraints of @StackLimited,
> and also tells the JVM to proactively check the available stack
> space and throw StackOverflowError immediately on entry to the
> method if there is not enough stack for all possible executions of
> the method.
>
> The idea would be to annotate the minimum set of methods to ensure
> that a synchronizer is never left in an invalid state due to stack
> overflow. That would mostly be putting @StackLimited on the methods
> of Unsafe, LockSupport, and the j.u.c.atomic package, and putting
> @StackSensitive on just one or two methods in any given synchronizer
> such as AQS.
>
> Is something like this plausible, or even already in the works?
>
> Cheers,
> Justin
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich
In reply to this post by Justin Sampson

I'm having difficulty imagining how JIT, upon entry into a function, could verify that all call chains within the body will not blow the stack.  There's control flow, unreachable code that turns reachable, etc that it needs to account for.  It may have to load classes that it wouldn't have to otherwise in order to peek at methods' bytecode, and so on.

If you want to harden your lib, SOE should be easier to tackle as it's at least local to your thread of execution; OOM is a bit more challenging.

Common wisdom is you restart your app if you hit OOM/SOE as even if your lib handles it, it's unlikely callers do.

sent from my phone

On Jan 24, 2015 12:44 AM, "Justin Sampson" <[hidden email]> wrote:
Vitaly Davidovich wrote:

> Ahhh, the noble goal of hardening a system against async
> exceptions like OOM and SOE. :) Honestly, I've yet to see code
> that is 100% hardened against OOM. Frankly, I'm not sure this is
> possible in java given there's a big machine that's running
> beneath you (i.e. JVM, which can throw OOM in places you wouldn't
> necessary expect), and this goes for SOE as well. I'd love to be
> proven wrong though.

To be clear, I'm not talking about hardening the whole system
against arbitrary async exceptions. OOME and SOE _can_ be thrown
asynchronously, but there are also well-defined places that they
happen synchronously. It seems at least plausible to be able to
harden certain low-level library code against such synchronous
exceptions, especially certain blocks of code within synchronizers
where there's a risk of leaving the synchronizer locked.

I've searched a little in the archives and I can see the issue at
least mentioned a couple of times, but wanted to get a sense of
whether any solutions were being considered. The links that
Alexander sent are very interesting history! -- but they're about
C++ and I couldn't quite ascertain the final outcome.

To make the idea even more constrained, imagine a method that only
calls other final or static Java methods or intrinsified native
methods, whether directly or indirectly, without any recursion, none
of which do any heap allocation (no new objects, arrays, boxing,
lambdas, varargs, etc.). Conceptually, the JIT could inline the
whole call tree into a single method body with a single stack frame.

Any call to such a method would throw SOE right up front if the
stack has been exhausted, avoiding any SOE's in the middle. (Any
class loading and initialization that might be triggered by the body
of the method would have to be executed immediately on entry to the
method as well, since they can trigger arbitrary exceptions and
errors.)

The strawman proposal in my prior email was simply to provide an
annotation that would request for the JVM to implement such
fail-fast behavior for the annotated methods, with compile-time
verification that it should be possible for the runtime to do so.

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Alexander Terekhov-2
In reply to this post by Justin Sampson
> I couldn't quite ascertain the final outcome.

Well, C++ still has no support for no_cancel { } to suppress thread
cancelation inside the scope (and restore previous state by exiting the
scope), no support for no_throw { } being the same as no_cancel { } and in
addition making that any unexpected/unhandled exception immediately results
in abort() at throw point without stack unwinding, no support for
async_cancel_safe { } to enable async cancel (if cancel was not disabled
upstack) and expressing that only async cancel safe operations can be coded
inside the scope, no support for meaningful exception specifications
providing fencing from unexpected exceptions, etc.

regards,
alexander.

Justin Sampson <[hidden email]> on 24.01.2015 06:44:33

To: Vitaly Davidovich <[hidden email]>, Alexander
       Terekhov/Germany/IBM@IBMDE
cc: "[hidden email]"
       <[hidden email]>
Subject: RE: [concurrency-interest] JVM support to avoid
       StackOverflowError


Vitaly Davidovich wrote:

> Ahhh, the noble goal of hardening a system against async
> exceptions like OOM and SOE. :) Honestly, I've yet to see code
> that is 100% hardened against OOM. Frankly, I'm not sure this is
> possible in java given there's a big machine that's running
> beneath you (i.e. JVM, which can throw OOM in places you wouldn't
> necessary expect), and this goes for SOE as well. I'd love to be
> proven wrong though.

To be clear, I'm not talking about hardening the whole system
against arbitrary async exceptions. OOME and SOE _can_ be thrown
asynchronously, but there are also well-defined places that they
happen synchronously. It seems at least plausible to be able to
harden certain low-level library code against such synchronous
exceptions, especially certain blocks of code within synchronizers
where there's a risk of leaving the synchronizer locked.

I've searched a little in the archives and I can see the issue at
least mentioned a couple of times, but wanted to get a sense of
whether any solutions were being considered. The links that
Alexander sent are very interesting history! -- but they're about
C++ and I couldn't quite ascertain the final outcome.

To make the idea even more constrained, imagine a method that only
calls other final or static Java methods or intrinsified native
methods, whether directly or indirectly, without any recursion, none
of which do any heap allocation (no new objects, arrays, boxing,
lambdas, varargs, etc.). Conceptually, the JIT could inline the
whole call tree into a single method body with a single stack frame.

Any call to such a method would throw SOE right up front if the
stack has been exhausted, avoiding any SOE's in the middle. (Any
class loading and initialization that might be triggered by the body
of the method would have to be executed immediately on entry to the
method as well, since they can trigger arbitrary exceptions and
errors.)

The strawman proposal in my prior email was simply to provide an
annotation that would request for the JVM to implement such
fail-fast behavior for the annotated methods, with compile-time
verification that it should be possible for the runtime to do so.

Cheers,
Justin


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Justin Sampson
In reply to this post by Vitaly Davidovich
Consider this incredibly simple lock implementation:

public final class SimpleLock extends AbstractOwnableSynchronizer {
  private final AtomicBoolean state = new AtomicBoolean();
  public final boolean tryLock() {
    if (state.compareAndSet(false, true)) {
      setExclusiveOwnerThread(Thread.currentThread());
      return true;
    } else {
      return false;
    }
  }
  public final void unlock() {
    if (Thread.currentThread() != getExclusiveOwnerThread()) {
      throw new IllegalMonitorStateException();
    } else {
      setExclusiveOwnerThread(null);
      state.set(false);
    }
  }
}

It's possible for the CAS in tryLock() to succeed and then for the
very next line to blow up with a synchronous StackOverflowError,
leaving the state variable true even though tryLock() is throwing.
This is the only kind of case that I'm looking for advice about,
nothing more general.

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

But it seems so trivial to recognize that this tryLock() method
doesn't do any heap allocation, isn't recursive, and only calls
static or final methods, most of them being intrinsic. So I was just
wondering if it might be plausible to annotate such a method, as a
request to the compiler to confirm those facts and as a request to
the JVM to fail fast on entry by allocating enough stack space up
front.

I wasn't imagining any kind of suppression of errors or more general
handling of arbitrarily complicated code, just avoidance of common
errors by failing fast when it's easy to do so.

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Doug Lea
On 01/25/2015 07:06 AM, Justin Sampson wrote:

> So far the only responses have been "it's impossible to do anything
> so don't even try." If that's really the end of it then I'll rest
> easy knowing I've done my due diligence.

There have been JVM-level proposals to implement bandaids
for dealing with StackOverflow for j.u.c Locks, but as far
as I know, they are at best pointwise incomplete fixes.
As people have mentioned, it is a hard problem, in part because
the JVM can/does use the stack for class-loading, compilation,
etc, that can happen at any time.

If you can live with this uncertainty, you might also be able
to live with a hypothetical method
   boolean stackSpaceAvailable(int bytes)
that returns true if the stack could accommodate a
frame of the given size. Because this would require some
estimation uncertainty on top of other problems, I don't
think anyone has proposed it lately.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Aaron Grunthal
On 25.01.2015 17:06, Doug Lea wrote:

> On 01/25/2015 07:06 AM, Justin Sampson wrote:
>
>> So far the only responses have been "it's impossible to do anything
>> so don't even try." If that's really the end of it then I'll rest
>> easy knowing I've done my due diligence.
>
> There have been JVM-level proposals to implement bandaids
> for dealing with StackOverflow for j.u.c Locks, but as far
> as I know, they are at best pointwise incomplete fixes.
> As people have mentioned, it is a hard problem, in part because
> the JVM can/does use the stack for class-loading, compilation,
> etc, that can happen at any time.
>
> If you can live with this uncertainty, you might also be able
> to live with a hypothetical method
>    boolean stackSpaceAvailable(int bytes)

In the absence of such a method, wouldn't it be possible to design a
canary to execute before the method in question? Basically call a method
designed to use up a significant amount of stack space, larger than the
protected method itself, in a way that the compiler can't optimize away?

It would be trading performance for safety in that case.

> that returns true if the stack could accommodate a
> frame of the given size. Because this would require some
> estimation uncertainty on top of other problems, I don't
> think anyone has proposed it lately.
>
> -Doug
>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Peter Levart
In reply to this post by Doug Lea

On 01/25/2015 05:06 PM, Doug Lea wrote:
On 01/25/2015 07:06 AM, Justin Sampson wrote:

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

There have been JVM-level proposals to implement bandaids
for dealing with StackOverflow for j.u.c Locks, but as far
as I know, they are at best pointwise incomplete fixes.
As people have mentioned, it is a hard problem, in part because
the JVM can/does use the stack for class-loading, compilation,
etc, that can happen at any time.

If you can live with this uncertainty, you might also be able
to live with a hypothetical method
  boolean stackSpaceAvailable(int bytes)
that returns true if the stack could accommodate a
frame of the given size. Because this would require some
estimation uncertainty on top of other problems, I don't
think anyone has proposed it lately.

-Doug

So this would tipically be used before critical sections of code that should complete normally like:

if (!stackSpaceAvailable(whatWeMightNeedPlusSome))
    throw new StackOverflowError();

// critical code...



I don't know if stack space used is the same regardless of mode of execution of particular code (interpreted, compiled, inlined, ...), but if it is comparable in each case, one could do such "probing" before critical piece of code with simple recursive no-op method(s) like:


public static probeStack(int frames) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1);
}

public static probeStack(int frames, Object arg1) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1, arg1);
}

public static probeStack(int frames, Object arg1, Object arg2) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1, arg1, arg2);
}

...
...

Is JIT free to optimize away such code?

Peter



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich

I believe JIT would be free to optimize this out, e.g. tail recursion turned into loop.

sent from my phone

On Jan 25, 2015 12:16 PM, "Peter Levart" <[hidden email]> wrote:

On 01/25/2015 05:06 PM, Doug Lea wrote:
On 01/25/2015 07:06 AM, Justin Sampson wrote:

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

There have been JVM-level proposals to implement bandaids
for dealing with StackOverflow for j.u.c Locks, but as far
as I know, they are at best pointwise incomplete fixes.
As people have mentioned, it is a hard problem, in part because
the JVM can/does use the stack for class-loading, compilation,
etc, that can happen at any time.

If you can live with this uncertainty, you might also be able
to live with a hypothetical method
  boolean stackSpaceAvailable(int bytes)
that returns true if the stack could accommodate a
frame of the given size. Because this would require some
estimation uncertainty on top of other problems, I don't
think anyone has proposed it lately.

-Doug

So this would tipically be used before critical sections of code that should complete normally like:

if (!stackSpaceAvailable(whatWeMightNeedPlusSome))
    throw new StackOverflowError();

// critical code...



I don't know if stack space used is the same regardless of mode of execution of particular code (interpreted, compiled, inlined, ...), but if it is comparable in each case, one could do such "probing" before critical piece of code with simple recursive no-op method(s) like:


public static probeStack(int frames) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1);
}

public static probeStack(int frames, Object arg1) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1, arg1);
}

public static probeStack(int frames, Object arg1, Object arg2) throws StackOverflowError {
    if (frames > 0) probeStack(frames - 1, arg1, arg2);
}

...
...

Is JIT free to optimize away such code?

Peter



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich
In reply to this post by Aaron Grunthal

Suppose you had such method - how would one use it in a reliable manner? Somehow obtain current stack pointer, compute the distance to stack end zone and pass that in? How do you know how much stack space you'll need? Will you have to tune that as code is changed? Doesn't sound all that appealing.

Currently, modulo bugs, JVM actually allows unwinding (java) stack overflow exceptions reliably (well, just like other exceptions).  It installs special pages at the end of allocated stack which allow it to have some room of its own to do this.  Of course, this doesn't quite help with the "it can be thrown anywhere" scenario.

sent from my phone

On Jan 25, 2015 12:08 PM, "Aaron Grunthal" <[hidden email]> wrote:
On 25.01.2015 17:06, Doug Lea wrote:
On 01/25/2015 07:06 AM, Justin Sampson wrote:

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

There have been JVM-level proposals to implement bandaids
for dealing with StackOverflow for j.u.c Locks, but as far
as I know, they are at best pointwise incomplete fixes.
As people have mentioned, it is a hard problem, in part because
the JVM can/does use the stack for class-loading, compilation,
etc, that can happen at any time.

If you can live with this uncertainty, you might also be able
to live with a hypothetical method
   boolean stackSpaceAvailable(int bytes)

In the absence of such a method, wouldn't it be possible to design a canary to execute before the method in question? Basically call a method designed to use up a significant amount of stack space, larger than the protected method itself, in a way that the compiler can't optimize away?

It would be trading performance for safety in that case.

that returns true if the stack could accommodate a
frame of the given size. Because this would require some
estimation uncertainty on top of other problems, I don't
think anyone has proposed it lately.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich

By the way, just remembered that .NET has something akin to this, called constrained execution regions: https://msdn.microsoft.com/en-us/library/ms228973(v=vs.110).aspx

sent from my phone

On Jan 25, 2015 12:41 PM, "Vitaly Davidovich" <[hidden email]> wrote:

Suppose you had such method - how would one use it in a reliable manner? Somehow obtain current stack pointer, compute the distance to stack end zone and pass that in? How do you know how much stack space you'll need? Will you have to tune that as code is changed? Doesn't sound all that appealing.

Currently, modulo bugs, JVM actually allows unwinding (java) stack overflow exceptions reliably (well, just like other exceptions).  It installs special pages at the end of allocated stack which allow it to have some room of its own to do this.  Of course, this doesn't quite help with the "it can be thrown anywhere" scenario.

sent from my phone

On Jan 25, 2015 12:08 PM, "Aaron Grunthal" <[hidden email]> wrote:
On 25.01.2015 17:06, Doug Lea wrote:
On 01/25/2015 07:06 AM, Justin Sampson wrote:

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

There have been JVM-level proposals to implement bandaids
for dealing with StackOverflow for j.u.c Locks, but as far
as I know, they are at best pointwise incomplete fixes.
As people have mentioned, it is a hard problem, in part because
the JVM can/does use the stack for class-loading, compilation,
etc, that can happen at any time.

If you can live with this uncertainty, you might also be able
to live with a hypothetical method
   boolean stackSpaceAvailable(int bytes)

In the absence of such a method, wouldn't it be possible to design a canary to execute before the method in question? Basically call a method designed to use up a significant amount of stack space, larger than the protected method itself, in a way that the compiler can't optimize away?

It would be trading performance for safety in that case.

that returns true if the stack could accommodate a
frame of the given size. Because this would require some
estimation uncertainty on top of other problems, I don't
think anyone has proposed it lately.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Aaron Grunthal
In reply to this post by Vitaly Davidovich
Reliable? Not in the sense of hard guarantees or anything. It would be
more of an extra safety measure

Justin was asking for an extremely simple case where one could probably
deduce all the leaf methods by hand / with a debugger, add a factor 2
safety margin and hope for the best.

It's a fickle workaround, using the tools that are currently available
and not a proper solution.

Relying on a stack canary that survives a sufficiently advanced™ and
presumed hostile compiler already puts it on shaky ground.


If we want something that can be used for opportunistic recursion that
will abort and put things on a queue or simply wait if it runs out of
stack space (e.g. fork join pool?) then we would need JVM support.

On 25.01.2015 18:41, Vitaly Davidovich wrote:

> Suppose you had such method - how would one use it in a reliable manner?
> Somehow obtain current stack pointer, compute the distance to stack end
> zone and pass that in? How do you know how much stack space you'll need?
> Will you have to tune that as code is changed? Doesn't sound all that
> appealing.
>
> Currently, modulo bugs, JVM actually allows unwinding (java) stack
> overflow exceptions reliably (well, just like other exceptions).  It
> installs special pages at the end of allocated stack which allow it to
> have some room of its own to do this.  Of course, this doesn't quite
> help with the "it can be thrown anywhere" scenario.
>
> sent from my phone
>
> On Jan 25, 2015 12:08 PM, "Aaron Grunthal"
> <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     On 25.01.2015 17:06, Doug Lea wrote:
>
>         On 01/25/2015 07:06 AM, Justin Sampson wrote:
>
>             So far the only responses have been "it's impossible to do
>             anything
>             so don't even try." If that's really the end of it then I'll
>             rest
>             easy knowing I've done my due diligence.
>
>
>         There have been JVM-level proposals to implement bandaids
>         for dealing with StackOverflow for j.u.c Locks, but as far
>         as I know, they are at best pointwise incomplete fixes.
>         As people have mentioned, it is a hard problem, in part because
>         the JVM can/does use the stack for class-loading, compilation,
>         etc, that can happen at any time.
>
>         If you can live with this uncertainty, you might also be able
>         to live with a hypothetical method
>             boolean stackSpaceAvailable(int bytes)
>
>
>     In the absence of such a method, wouldn't it be possible to design a
>     canary to execute before the method in question? Basically call a
>     method designed to use up a significant amount of stack space,
>     larger than the protected method itself, in a way that the compiler
>     can't optimize away?
>
>     It would be trading performance for safety in that case.
>
>         that returns true if the stack could accommodate a
>         frame of the given size. Because this would require some
>         estimation uncertainty on top of other problems, I don't
>         think anyone has proposed it lately.
>
>         -Doug
>
>
>         _________________________________________________
>         Concurrency-interest mailing list
>         [hidden email]
>         <mailto:[hidden email]>
>         http://cs.oswego.edu/mailman/__listinfo/concurrency-interest
>         <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
>
>     _________________________________________________
>     Concurrency-interest mailing list
>     [hidden email]
>     <mailto:[hidden email]>
>     http://cs.oswego.edu/mailman/__listinfo/concurrency-interest
>     <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

oleksandr otenko
In reply to this post by Justin Sampson
So?

How about throwing SOE in unlock? And what do you do if JVM says nuh-uh,
you don't have enough stack to run unlock, even if you checked?

Alex


On 25/01/2015 12:06, Justin Sampson wrote:

> Consider this incredibly simple lock implementation:
>
> public final class SimpleLock extends AbstractOwnableSynchronizer {
>    private final AtomicBoolean state = new AtomicBoolean();
>    public final boolean tryLock() {
>      if (state.compareAndSet(false, true)) {
>        setExclusiveOwnerThread(Thread.currentThread());
>        return true;
>      } else {
>        return false;
>      }
>    }
>    public final void unlock() {
>      if (Thread.currentThread() != getExclusiveOwnerThread()) {
>        throw new IllegalMonitorStateException();
>      } else {
>        setExclusiveOwnerThread(null);
>        state.set(false);
>      }
>    }
> }
>
> It's possible for the CAS in tryLock() to succeed and then for the
> very next line to blow up with a synchronous StackOverflowError,
> leaving the state variable true even though tryLock() is throwing.
> This is the only kind of case that I'm looking for advice about,
> nothing more general.
>
> So far the only responses have been "it's impossible to do anything
> so don't even try." If that's really the end of it then I'll rest
> easy knowing I've done my due diligence.
>
> But it seems so trivial to recognize that this tryLock() method
> doesn't do any heap allocation, isn't recursive, and only calls
> static or final methods, most of them being intrinsic. So I was just
> wondering if it might be plausible to annotate such a method, as a
> request to the compiler to confirm those facts and as a request to
> the JVM to fail fast on entry by allocating enough stack space up
> front.
>
> I wasn't imagining any kind of suppression of errors or more general
> handling of arbitrarily complicated code, just avoidance of common
> errors by failing fast when it's easy to do so.
>
> Cheers,
> Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich

Yeah, this is a losing proposition, I suspect.

But to play along, you could (a) run the code anyway with a catch block and hope that you overestimated how much stack is needed or (b) instruct the VM to shutdown, possibly a halt.  The additional complexity is how do you ensure your error handling code won't then bump up against the same situation, especially considering that JIT will most likely haven't compiled the handling code as it's cold.  You'd need to have some annotations to tell JIT to compile entire method, which would at least solve that problem, but wouldn't help in the general case.

sent from my phone

On Jan 26, 2015 6:42 AM, "Oleksandr Otenko" <[hidden email]> wrote:
So?

How about throwing SOE in unlock? And what do you do if JVM says nuh-uh, you don't have enough stack to run unlock, even if you checked?

Alex


On 25/01/2015 12:06, Justin Sampson wrote:
Consider this incredibly simple lock implementation:

public final class SimpleLock extends AbstractOwnableSynchronizer {
   private final AtomicBoolean state = new AtomicBoolean();
   public final boolean tryLock() {
     if (state.compareAndSet(false, true)) {
       setExclusiveOwnerThread(Thread.currentThread());
       return true;
     } else {
       return false;
     }
   }
   public final void unlock() {
     if (Thread.currentThread() != getExclusiveOwnerThread()) {
       throw new IllegalMonitorStateException();
     } else {
       setExclusiveOwnerThread(null);
       state.set(false);
     }
   }
}

It's possible for the CAS in tryLock() to succeed and then for the
very next line to blow up with a synchronous StackOverflowError,
leaving the state variable true even though tryLock() is throwing.
This is the only kind of case that I'm looking for advice about,
nothing more general.

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

But it seems so trivial to recognize that this tryLock() method
doesn't do any heap allocation, isn't recursive, and only calls
static or final methods, most of them being intrinsic. So I was just
wondering if it might be plausible to annotate such a method, as a
request to the compiler to confirm those facts and as a request to
the JVM to fail fast on entry by allocating enough stack space up
front.

I wasn't imagining any kind of suppression of errors or more general
handling of arbitrarily complicated code, just avoidance of common
errors by failing fast when it's easy to do so.

Cheers,
Justin


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

oleksandr otenko
Yes.

What I meant, is when do you check that unlock has enough stack? If it is just before unlock, then what do you do if you can't. Not sure if you need to halt - consequences of SOE are already unspecified.

And if you check whether you will be able to unlock at the time you attempt to lock, then how do you tell JVM to check the entire code path up to unlock to see if there will be enough stack by the time the code gets there.

Alex

On 26/01/2015 14:18, Vitaly Davidovich wrote:

Yeah, this is a losing proposition, I suspect.

But to play along, you could (a) run the code anyway with a catch block and hope that you overestimated how much stack is needed or (b) instruct the VM to shutdown, possibly a halt.  The additional complexity is how do you ensure your error handling code won't then bump up against the same situation, especially considering that JIT will most likely haven't compiled the handling code as it's cold.  You'd need to have some annotations to tell JIT to compile entire method, which would at least solve that problem, but wouldn't help in the general case.

sent from my phone

On Jan 26, 2015 6:42 AM, "Oleksandr Otenko" <[hidden email]> wrote:
So?

How about throwing SOE in unlock? And what do you do if JVM says nuh-uh, you don't have enough stack to run unlock, even if you checked?

Alex


On 25/01/2015 12:06, Justin Sampson wrote:
Consider this incredibly simple lock implementation:

public final class SimpleLock extends AbstractOwnableSynchronizer {
   private final AtomicBoolean state = new AtomicBoolean();
   public final boolean tryLock() {
     if (state.compareAndSet(false, true)) {
       setExclusiveOwnerThread(Thread.currentThread());
       return true;
     } else {
       return false;
     }
   }
   public final void unlock() {
     if (Thread.currentThread() != getExclusiveOwnerThread()) {
       throw new IllegalMonitorStateException();
     } else {
       setExclusiveOwnerThread(null);
       state.set(false);
     }
   }
}

It's possible for the CAS in tryLock() to succeed and then for the
very next line to blow up with a synchronous StackOverflowError,
leaving the state variable true even though tryLock() is throwing.
This is the only kind of case that I'm looking for advice about,
nothing more general.

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

But it seems so trivial to recognize that this tryLock() method
doesn't do any heap allocation, isn't recursive, and only calls
static or final methods, most of them being intrinsic. So I was just
wondering if it might be plausible to annotate such a method, as a
request to the compiler to confirm those facts and as a request to
the JVM to fail fast on entry by allocating enough stack space up
front.

I wasn't imagining any kind of suppression of errors or more general
handling of arbitrarily complicated code, just avoidance of common
errors by failing fast when it's easy to do so.

Cheers,
Justin



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Vitaly Davidovich

Yeah, I think you'd check right before calling unlock (but, how do you ensure the caller could reach that far and not hit SOE - turtles all the way down!).

The reason I mention halt is that you may not want to even attempt going any further, e.g. not risk handler code mucking things up further.  But yeah, this is so murky I don't think it's tractable  (nevermind how one would even test all the various failure cases reliably).

Having come across various coding standards for safety critical software (not java though), there seems to be a lot of focus on static analysis verification,  such as prohibiting recursion.  Otherwise, I think you let things fail fast and backups (or some failover mechanism) take over.

sent from my phone

On Jan 26, 2015 10:02 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes.

What I meant, is when do you check that unlock has enough stack? If it is just before unlock, then what do you do if you can't. Not sure if you need to halt - consequences of SOE are already unspecified.

And if you check whether you will be able to unlock at the time you attempt to lock, then how do you tell JVM to check the entire code path up to unlock to see if there will be enough stack by the time the code gets there.

Alex

On 26/01/2015 14:18, Vitaly Davidovich wrote:

Yeah, this is a losing proposition, I suspect.

But to play along, you could (a) run the code anyway with a catch block and hope that you overestimated how much stack is needed or (b) instruct the VM to shutdown, possibly a halt.  The additional complexity is how do you ensure your error handling code won't then bump up against the same situation, especially considering that JIT will most likely haven't compiled the handling code as it's cold.  You'd need to have some annotations to tell JIT to compile entire method, which would at least solve that problem, but wouldn't help in the general case.

sent from my phone

On Jan 26, 2015 6:42 AM, "Oleksandr Otenko" <[hidden email]> wrote:
So?

How about throwing SOE in unlock? And what do you do if JVM says nuh-uh, you don't have enough stack to run unlock, even if you checked?

Alex


On 25/01/2015 12:06, Justin Sampson wrote:
Consider this incredibly simple lock implementation:

public final class SimpleLock extends AbstractOwnableSynchronizer {
   private final AtomicBoolean state = new AtomicBoolean();
   public final boolean tryLock() {
     if (state.compareAndSet(false, true)) {
       setExclusiveOwnerThread(Thread.currentThread());
       return true;
     } else {
       return false;
     }
   }
   public final void unlock() {
     if (Thread.currentThread() != getExclusiveOwnerThread()) {
       throw new IllegalMonitorStateException();
     } else {
       setExclusiveOwnerThread(null);
       state.set(false);
     }
   }
}

It's possible for the CAS in tryLock() to succeed and then for the
very next line to blow up with a synchronous StackOverflowError,
leaving the state variable true even though tryLock() is throwing.
This is the only kind of case that I'm looking for advice about,
nothing more general.

So far the only responses have been "it's impossible to do anything
so don't even try." If that's really the end of it then I'll rest
easy knowing I've done my due diligence.

But it seems so trivial to recognize that this tryLock() method
doesn't do any heap allocation, isn't recursive, and only calls
static or final methods, most of them being intrinsic. So I was just
wondering if it might be plausible to annotate such a method, as a
request to the compiler to confirm those facts and as a request to
the JVM to fail fast on entry by allocating enough stack space up
front.

I wasn't imagining any kind of suppression of errors or more general
handling of arbitrarily complicated code, just avoidance of common
errors by failing fast when it's easy to do so.

Cheers,
Justin



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: JVM support to avoid StackOverflowError

Justin Sampson
Vitaly Davidovich wrote:

> Yeah, I think you'd check right before calling unlock (but, how do
> you ensure the caller could reach that far and not hit SOE -
> turtles all the way down!).

You'd really have to check before calling lock() to make sure
there's enough stack for unlock()... So basically, the futility in
any attempt to harden lock() and unlock() individually is that
they're called in pairs from higher-level code. We'd have to find a
way to make lock() fail-fast if there's not enough stack for the
corresponding unlock().

I'm satisfied with that explanation for now, though I may revisit
the discussion later in regard to the specific code I'm writing. :)

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
123