deadline and long overflow

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

deadline and long overflow

alarmnummer
I have a question regarding dealing with deadlines and long overflow.

For example the following from the SynchronousQueue:

final long deadline = timed ? System.nanoTime() + nanos : 0L;
What would happen if someone calls queue.offer(item, Long.MAX_VALUE, NANOS) then deadline overflows and becomes negative. I see the same approach in other parts e.g.

this.deadline = timed ? System.nanoTime() + nanos : 0L;
from the Phaser. Personally I like the simplicity; but my concern is regarding validity.

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

Re: deadline and long overflow

David Holmes-6

Hi Peter,

 

Doesn’t this “self-correct” when we do

 

nanos = deadline - System.nanoTime();

 

David

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Peter Veentjer
Sent: Wednesday, April 20, 2016 8:05 PM
To: [hidden email]
Subject: [concurrency-interest] deadline and long overflow

 

I have a question regarding dealing with deadlines and long overflow.

For example the following from the SynchronousQueue:

final long deadline = timed ? System.nanoTime() + nanos : 0L;

What would happen if someone calls queue.offer(item, Long.MAX_VALUE, NANOS) then deadline overflows and becomes negative. I see the same approach in other parts e.g.

this.deadline = timed ? System.nanoTime() + nanos : 0L;

from the Phaser. Personally I like the simplicity; but my concern is regarding validity.


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

Re: deadline and long overflow

Alex Otenko
In reply to this post by alarmnummer
Wouldn’t that be a deadline of 500-odd years?

Technically, overflow is a possibility. Practically - very unlikely.

Alex

On 20 Apr 2016, at 11:05, Peter Veentjer <[hidden email]> wrote:

I have a question regarding dealing with deadlines and long overflow.

For example the following from the SynchronousQueue:

final long deadline = timed ? System.nanoTime() + nanos : 0L;
What would happen if someone calls queue.offer(item, Long.MAX_VALUE, NANOS) then deadline overflows and becomes negative. I see the same approach in other parts e.g.

this.deadline = timed ? System.nanoTime() + nanos : 0L;
from the Phaser. Personally I like the simplicity; but my concern is regarding validity.
_______________________________________________
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: deadline and long overflow

Doug Lea
On 04/20/2016 06:32 AM, Alex Otenko wrote:
> Wouldn’t that be a deadline of 500-odd years?

Overflow issues can occur in half that time though (around 292 years).

>
> Technically, overflow is a possibility. Practically - very unlikely.
>

Right. There is a disclaimer about this in System.nanotime:
http://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime--

This could be repeated in every timing-related method, but isn't.

-Doug

> Alex
>
>> On 20 Apr 2016, at 11:05, Peter Veentjer <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>> I have a question regarding dealing with deadlines and long overflow.
>>
>> For example the following from the SynchronousQueue:
>>
>> final long deadline = timed ? System.nanoTime() + nanos :0L;
>> What would happen if someone calls queue.offer(item, Long.MAX_VALUE, NANOS)
>> then deadline overflows and becomes negative. I see the same approach in other
>> parts e.g.
>>
>> this.deadline = timed ? System.nanoTime() + nanos :0L;
>> from the Phaser. Personally I like the simplicity; but my concern is regarding
>> validity.
>> _______________________________________________
>> Concurrency-interest mailing list
>> [hidden email] <mailto:[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: deadline and long overflow

alarmnummer
Thanks for the replies.

The question is not about waiting given amount of time; but the calculation of the deadline itself which can become negative due to overflow. So imagine you call:

queue.poll(Long.MAX_VALUE, NANOS)

then the deadline will be < 0 due to overflow.

The question is if it can happen that a blocking call fails with a timeout, perhaps immediately due to this deadline becoming negative. I made some small examples and it seems to self correct like David suggested but it feels a bit funny.



On Wed, Apr 20, 2016 at 3:52 PM, Doug Lea <[hidden email]> wrote:
On 04/20/2016 06:32 AM, Alex Otenko wrote:
Wouldn’t that be a deadline of 500-odd years?

Overflow issues can occur in half that time though (around 292 years).


Technically, overflow is a possibility. Practically - very unlikely.


Right. There is a disclaimer about this in System.nanotime:
http://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime--

This could be repeated in every timing-related method, but isn't.

-Doug

Alex

On 20 Apr 2016, at 11:05, Peter Veentjer <[hidden email]
<mailto:[hidden email]>> wrote:

I have a question regarding dealing with deadlines and long overflow.

For example the following from the SynchronousQueue:

final long deadline = timed ? System.nanoTime() + nanos :0L;
What would happen if someone calls queue.offer(item, Long.MAX_VALUE, NANOS)
then deadline overflows and becomes negative. I see the same approach in other
parts e.g.

this.deadline = timed ? System.nanoTime() + nanos :0L;
from the Phaser. Personally I like the simplicity; but my concern is regarding
validity.
_______________________________________________
Concurrency-interest mailing list
[hidden email] <mailto:[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


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

Re: deadline and long overflow

Martin Buchholz-3
On Wed, Apr 20, 2016 at 6:57 AM, Peter Veentjer <[hidden email]> wrote:

> Thanks for the replies.
>
> The question is not about waiting given amount of time; but the calculation
> of the deadline itself which can become negative due to overflow. So imagine
> you call:
>
> queue.poll(Long.MAX_VALUE, NANOS)
>
> then the deadline will be < 0 due to overflow.
>
> The question is if it can happen that a blocking call fails with a timeout,
> perhaps immediately due to this deadline becoming negative. I made some
> small examples and it seems to self correct like David suggested but it
> feels a bit funny.

All of the time handling code in j.u.concurrent is overflow-aware.
It's not really overflow, it's "wraparound".  It's safe because it's
java, not C.  As long as all of the code that handles nanotime values
follows the advice in the javadoc
https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime--
everything is fine.

To compare two nanoTime values


 long t0 = System.nanoTime();
 ...
 long t1 = System.nanoTime();
one should use t1 - t0 < 0, not t1 < t0, because of the possibility of
numerical overflow.

It's hard to test that we haven't made a mistake somewhere, though.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: deadline and long overflow

Justin Sampson
Peter, I had exactly the same funny feeling as you when I first saw
this idiom. A few years back, Martin changed some of my timing code
in Guava's Monitor class from something like this:

  long timeoutNanos = unit.toNanos(time);
  long startNanos = System.nanoTime();
  ...
  long remainingNanos =
      timeoutNanos - (System.nanoTime() - startNanos);

to something like this:

  long timeoutNanos = unit.toNanos(time);
  long deadline = System.nanoTime() + timeoutNanos;
  ...
  long remainingNanos = deadline - System.nanoTime();

At first I thought that this would introduce some kind of overflow
error with MAX_VALUE, but I wrote a unit test for it and it passed!
Only then did I realize that these two constructs are exactly
identical in runtime behavior due to the arithmetic wraparound of
long values. Any overflow bugs triggered by one would have been
triggered by the other just as well.

(For anyone who thinks MAX_VALUE isn't interesting because it's a
centuries-long timeout, consider someone passing MAX_VALUE into an
API with the intention of "actually, don't timeout this call." If
there were an arithmetic overflow bug that caused it to, say,
timeout immediately instead of never, that would be a very
noticeable and reproducible issue.)

Now, that's not quite the end of the story. It turns out that
there's no overflow bug for MAX_VALUE as long as nanoTime() actually
progresses forward, but there IS an overflow bug for MIN_VALUE, and
there IS an overflow bug for MAX_VALUE if nanoTime() ever goes
backward.

For the MIN_VALUE case, consider for simplicity that the first call
to nanoTime() returns 0 and the second call returns 1. Then with
either of the constructs above, remainingNanos ends up equal to
MIN_VALUE-1, which is actually MAX_VALUE. Without additional guard
clauses, that could result in blocking forever rather than not at
all, which is what MIN_VALUE should mean (as with any non-positive
timeout). The fix is simply to check for time <= 0 before doing any
of these calculations, but this bug has actually slipped into the
some parts of the JDK before -- and all my testing and agonizing
over Martin's change in Guava helped find and fix one or two such
cases in the JDK! :)

For the MAX_VALUE case, there's only an overflow bug if nanoTime()
goes backward, causing some negative value to be subtracted from
MAX_VALUE in the code above. That should never happen in HotSpot,
but there have been occasional bugs and experimental "optimizations"
in other JVMs that allow it to be seen. JDK code is NOT written to
be robust to that possibility, which would slightly complicate the
code everywhere that a timeout is checked.

There is ONE remaining overflow situation that we really can't do
anything about: When the elapsed time between two calls to
nanoTime() actually exceeds 2^63-1. I'm personally willing to ignore
that one!

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: deadline and long overflow

Martin Buchholz-3
On Wed, Apr 20, 2016 at 12:26 PM, Justin Sampson <[hidden email]> wrote:
> For the MAX_VALUE case, there's only an overflow bug if nanoTime()
> goes backward, causing some negative value to be subtracted from
> MAX_VALUE in the code above. That should never happen in HotSpot,
> but there have been occasional bugs and experimental "optimizations"
> in other JVMs that allow it to be seen. JDK code is NOT written to
> be robust to that possibility, which would slightly complicate the
> code everywhere that a timeout is checked.

While JDK implementations are required to provide nanoTime
monotonicity, it is an onerous requirement and so relying on it is a
kind of stress test for VM implementers.  If I was writing application
code with "forever" timeouts, I would use MAX_VALUE/2 NANOSECONDS
which is still "forever enough".  We once investigated what it would
take to make jsr166 code robust against nanoTime occasionally going
backwards (invariably with MIN_VALUE or MAX_VALUE nanos), and the
changes required were too invasive (and untestable!)
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: deadline and long overflow

alarmnummer
I want to thank all, especially Martin, for their answers.

On Wed, Apr 20, 2016 at 10:35 PM, Martin Buchholz <[hidden email]> wrote:
On Wed, Apr 20, 2016 at 12:26 PM, Justin Sampson <[hidden email]> wrote:
> For the MAX_VALUE case, there's only an overflow bug if nanoTime()
> goes backward, causing some negative value to be subtracted from
> MAX_VALUE in the code above. That should never happen in HotSpot,
> but there have been occasional bugs and experimental "optimizations"
> in other JVMs that allow it to be seen. JDK code is NOT written to
> be robust to that possibility, which would slightly complicate the
> code everywhere that a timeout is checked.

While JDK implementations are required to provide nanoTime
monotonicity, it is an onerous requirement and so relying on it is a
kind of stress test for VM implementers.  If I was writing application
code with "forever" timeouts, I would use MAX_VALUE/2 NANOSECONDS
which is still "forever enough".  We once investigated what it would
take to make jsr166 code robust against nanoTime occasionally going
backwards (invariably with MIN_VALUE or MAX_VALUE nanos), and the
changes required were too invasive (and untestable!)


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

Re: deadline and long overflow

Alex Otenko
In reply to this post by Justin Sampson
It seems insane to pass MAX_VALUE or MAX_VALUE/2 where the caller means “forever”. Use the call without the timeout, that’s what they are for. Them behaving in (observably) the same way as the timed waits with MAX_VALUE passed in, is an implementation detail. Passing a value that has the intended meaning is the caller responsibility.

Alex

> On 20 Apr 2016, at 20:26, Justin Sampson <[hidden email]> wrote:
>
> Peter, I had exactly the same funny feeling as you when I first saw
> this idiom. A few years back, Martin changed some of my timing code
> in Guava's Monitor class from something like this:
>
>  long timeoutNanos = unit.toNanos(time);
>  long startNanos = System.nanoTime();
>  ...
>  long remainingNanos =
>      timeoutNanos - (System.nanoTime() - startNanos);
>
> to something like this:
>
>  long timeoutNanos = unit.toNanos(time);
>  long deadline = System.nanoTime() + timeoutNanos;
>  ...
>  long remainingNanos = deadline - System.nanoTime();
>
> At first I thought that this would introduce some kind of overflow
> error with MAX_VALUE, but I wrote a unit test for it and it passed!
> Only then did I realize that these two constructs are exactly
> identical in runtime behavior due to the arithmetic wraparound of
> long values. Any overflow bugs triggered by one would have been
> triggered by the other just as well.
>
> (For anyone who thinks MAX_VALUE isn't interesting because it's a
> centuries-long timeout, consider someone passing MAX_VALUE into an
> API with the intention of "actually, don't timeout this call." If
> there were an arithmetic overflow bug that caused it to, say,
> timeout immediately instead of never, that would be a very
> noticeable and reproducible issue.)
>
> Now, that's not quite the end of the story. It turns out that
> there's no overflow bug for MAX_VALUE as long as nanoTime() actually
> progresses forward, but there IS an overflow bug for MIN_VALUE, and
> there IS an overflow bug for MAX_VALUE if nanoTime() ever goes
> backward.
>
> For the MIN_VALUE case, consider for simplicity that the first call
> to nanoTime() returns 0 and the second call returns 1. Then with
> either of the constructs above, remainingNanos ends up equal to
> MIN_VALUE-1, which is actually MAX_VALUE. Without additional guard
> clauses, that could result in blocking forever rather than not at
> all, which is what MIN_VALUE should mean (as with any non-positive
> timeout). The fix is simply to check for time <= 0 before doing any
> of these calculations, but this bug has actually slipped into the
> some parts of the JDK before -- and all my testing and agonizing
> over Martin's change in Guava helped find and fix one or two such
> cases in the JDK! :)
>
> For the MAX_VALUE case, there's only an overflow bug if nanoTime()
> goes backward, causing some negative value to be subtracted from
> MAX_VALUE in the code above. That should never happen in HotSpot,
> but there have been occasional bugs and experimental "optimizations"
> in other JVMs that allow it to be seen. JDK code is NOT written to
> be robust to that possibility, which would slightly complicate the
> code everywhere that a timeout is checked.
>
> There is ONE remaining overflow situation that we really can't do
> anything about: When the elapsed time between two calls to
> nanoTime() actually exceeds 2^63-1. I'm personally willing to ignore
> that one!
>
> 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: deadline and long overflow

Josh Humphries
This isn't always an option. For example, ExecutorService#awaitTermination has no such overload.

----
Josh Humphries
Manager, Shared Systems  |  Platform Engineering
Atlanta, GA  |  678-400-4867

On Thu, Apr 28, 2016 at 10:58 AM, Alex Otenko <[hidden email]> wrote:
It seems insane to pass MAX_VALUE or MAX_VALUE/2 where the caller means “forever”. Use the call without the timeout, that’s what they are for. Them behaving in (observably) the same way as the timed waits with MAX_VALUE passed in, is an implementation detail. Passing a value that has the intended meaning is the caller responsibility.

Alex

> On 20 Apr 2016, at 20:26, Justin Sampson <[hidden email]> wrote:
>
> Peter, I had exactly the same funny feeling as you when I first saw
> this idiom. A few years back, Martin changed some of my timing code
> in Guava's Monitor class from something like this:
>
>  long timeoutNanos = unit.toNanos(time);
>  long startNanos = System.nanoTime();
>  ...
>  long remainingNanos =
>      timeoutNanos - (System.nanoTime() - startNanos);
>
> to something like this:
>
>  long timeoutNanos = unit.toNanos(time);
>  long deadline = System.nanoTime() + timeoutNanos;
>  ...
>  long remainingNanos = deadline - System.nanoTime();
>
> At first I thought that this would introduce some kind of overflow
> error with MAX_VALUE, but I wrote a unit test for it and it passed!
> Only then did I realize that these two constructs are exactly
> identical in runtime behavior due to the arithmetic wraparound of
> long values. Any overflow bugs triggered by one would have been
> triggered by the other just as well.
>
> (For anyone who thinks MAX_VALUE isn't interesting because it's a
> centuries-long timeout, consider someone passing MAX_VALUE into an
> API with the intention of "actually, don't timeout this call." If
> there were an arithmetic overflow bug that caused it to, say,
> timeout immediately instead of never, that would be a very
> noticeable and reproducible issue.)
>
> Now, that's not quite the end of the story. It turns out that
> there's no overflow bug for MAX_VALUE as long as nanoTime() actually
> progresses forward, but there IS an overflow bug for MIN_VALUE, and
> there IS an overflow bug for MAX_VALUE if nanoTime() ever goes
> backward.
>
> For the MIN_VALUE case, consider for simplicity that the first call
> to nanoTime() returns 0 and the second call returns 1. Then with
> either of the constructs above, remainingNanos ends up equal to
> MIN_VALUE-1, which is actually MAX_VALUE. Without additional guard
> clauses, that could result in blocking forever rather than not at
> all, which is what MIN_VALUE should mean (as with any non-positive
> timeout). The fix is simply to check for time <= 0 before doing any
> of these calculations, but this bug has actually slipped into the
> some parts of the JDK before -- and all my testing and agonizing
> over Martin's change in Guava helped find and fix one or two such
> cases in the JDK! :)
>
> For the MAX_VALUE case, there's only an overflow bug if nanoTime()
> goes backward, causing some negative value to be subtracted from
> MAX_VALUE in the code above. That should never happen in HotSpot,
> but there have been occasional bugs and experimental "optimizations"
> in other JVMs that allow it to be seen. JDK code is NOT written to
> be robust to that possibility, which would slightly complicate the
> code everywhere that a timeout is checked.
>
> There is ONE remaining overflow situation that we really can't do
> anything about: When the elapsed time between two calls to
> nanoTime() actually exceeds 2^63-1. I'm personally willing to ignore
> that one!
>
> 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


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