Arithmetic overflow checking

[rop rop]

Hi,

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...
Is there any way to instruct the JVM to include it?

 

[Stefan Ram]

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...

One could use a JVM-based language with operator overloading.

Is there any way to instruct the JVM to include it?

One also could write a bytecode-to-bytecode transformer
that modifies arithmetic operations accordingly.

 

[markspace]

Hi,

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...
Is there any way to instruct the JVM to include it?

Nope, can't be done. And yes I've griped about this myself, so you're
in good (well, average at least) company.

 

[stefan]

Nope, can't be done.  And yes I've griped about this myself, so you're
in good (well, average at least) company.

OK...
What about patching the JVM to add this (sadly missing) "feature"?
It is open-source, isnt it?

Nobody has done this already?
Doesnt seems like a terribly big project, once I can locate the right
place to do it...

Any license aspects to consider, if I do it myself?

 

[markspace]

Doesnt seems like a terribly big project, once I can locate the right
place to do it...

lol. Yeah right.

http://openjdk.java.net/

Good luck kid.

 

[Tom Anderson]

Not automagically, at least if you want to avoid building a sourcecode-
preprocessor or tool that instruments your bytecode at class loading
time.

Actually, a load-time bytecode manipulator might be the most practical way
to do this. Modding the JVM is a non-starter for a few reasons, using an
alternative language is not even a solution, using a library or a set of
functions by convention is error-prone, but a bytecode weaver (using the
java.lang.instrument API, to be clear) could do the job, and would be a
fairly focused way of doing it - after the fairly small amount of
boilerplate, it would just be a matter of decoding all targeted bytecode
and rewriting it to check for overflow.

I didn't say it would be easy, just focused.

tom

 

[Roedy Green]

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...
Is there any way to instruct the JVM to include it?

the JVM does not detect it because most hardware does not. You pretty
well have to use long instead of int and mask off and check overflow.

 

[Roedy Green]

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...

If your hardware detects it, you could use some JNI and test the
status codes and return a object containing the result and overflow
info. Slow though.

 

[John B. Matthews]

Write the application in Ada.

In one popular implementation, the -gnato compiler option enables
numeric overflow checking:

<http://gcc.gnu.org/onlinedocs/gcc-4.6.1/gnat_ugn_unw/Switches-for-gcc.html#Switches-for-gcc>

The language defined attribute 'Machine_Overflows will indicate if
checking is available for fixed or floating point types:

<http://www.adaic.org/resources/add_content/standards/05rm/html/RM-K.html>

JGNAT targets the JVM, but I haven't used it.

 

[rop rop]

Modding the JVM is a non-starter for a few reasons...

Hi Tom,
Thanks for input.
Could you just elaborate on this, please... what is the main-problem
with actually patching the JVM?
Why is it so hard?
Without having looked into the source-code, this seems like the most
straight-forward and robust way to do it...
Is the code so hard to penetrate or what?

 

[Stefan Ram]

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...

Even if you would be willing to use method calls in your
source code, arithmetic overflow still could happen in
library methods called by you. So it would not be sufficient
to adjust only the source code written by you.

Otherwise, if for some reason this should be sufficient,
there is a Java 1.6 grammar for AntLR:

http://www.antlr.org/grammar/list

, so you could parse your source code with AntLR and this
grammar, then transform all the operators to method calls
(the precedence should already have been taken care of by
the parser) and write out the result as source code again.

 

[Eric Sosman]

Hi Tom,
Thanks for input.
Could you just elaborate on this, please... what is the main-problem
with actually patching the JVM?
Why is it so hard?
Without having looked into the source-code, this seems like the most
straight-forward and robust way to do it...
Is the code so hard to penetrate or what?

The first thing that comes to mind is altering a JVM so it does
not behave as described in the Java Virtual Machine Specification
means you no longer have a JVM. Specifically, from section 2.4.2:
"The built-in integer operators do not indicate (positive or negative)
overflow in any way; they wrap around on overflow." For good or for
ill, that's a requirement all JVM implementations must satisfy.

But, okay, you start with a JVM and alter it to produce a "KWN"
that behaves just like a JVM except in this one regard. Now a second
difficulty arises: You start running Java on the KWN, and almost at
once you get an arithmetic overflow exception. Investigating, you
find that it occurred in a hashCode() method that's computing the
time-honored sum x0+p*(x1+p*(x2+...)) with the fields x0,x1,... and
a prime p. The overflow is entirely benign, yet "Hello".hashCode()
stops your program in its tracks. So now you need a way to distinguish
expected (benign) overflow from unanticipated (injurious) overflow --
which means you need to alter not only the JVM but also Java. (Or maybe
you could do something with annotations; I'm not sure.) But the main
point is that all existing Java code expects overflow to wrap around,
and lots of that code actually relies on wraparound.

Finally, you've got definitional problems to sort out. For
example, is there an overflow in `int value = (int)Long.LONG_MAX;'?
You need to put on your Language Legislator hat and think about it
before you can decide how your KWN should behave.

Personally, I wish integer over- and under-flow would in fact
throw exceptions, and that the language had something like `unsigned'
to allow the programmer to suppress the exceptions when appropriate.
But that's a wish I don't expect to see fulfilled.

 

[Jukka Lahtinen]

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...

Without knowing anything about your application, I wonder if doing all
the arithmetics with the BigInteger class instead of the int or long
primitives would help. It shouldn't ever overflow according to the
javadocs.
Of course you may consider it not being practical and simple, and
at least changing all the primitive numbers would mean changes to the
code, but I haven't noticed any better suggestion so far.

 

[rop rop]

     The first thing that comes to mind is altering a JVM so it does
not behave as described in the Java Virtual Machine Specification
means you no longer have a JVM.  Specifically, from section 2.4.2:
"The built-in integer operators do not indicate (positive or negative)
overflow in any way; they wrap around on overflow."  For good or for
ill, that's a requirement all JVM implementations must satisfy.

     But, okay, you start with a JVM and alter it to produce a "KWN"
that behaves just like a JVM except in this one regard.  Now a second
difficulty arises: You start running Java on the KWN, and almost at
once you get an arithmetic overflow exception.  Investigating, you
find that it occurred in a hashCode() method that's computing the
time-honored sum x0+p*(x1+p*(x2+...)) with the fields x0,x1,... and
a prime p.  The overflow is entirely benign, yet "Hello".hashCode()
stops your program in its tracks.  So now you need a way to distinguish
expected (benign) overflow from unanticipated (injurious) overflow --
which means you need to alter not only the JVM but also Java.  (Or maybe
you could do something with annotations; I'm not sure.)  But the main
point is that all existing Java code expects overflow to wrap around,
and lots of that code actually relies on wraparound.

     Finally, you've got definitional problems to sort out.  For
example, is there an overflow in `int value = (int)Long.LONG_MAX;'?
You need to put on your Language Legislator hat and think about it
before you can decide how your KWN should behave.

     Personally, I wish integer over- and under-flow would in fact
throw exceptions, and that the language had something like `unsigned'
to allow the programmer to suppress the exceptions when appropriate.
But that's a wish I don't expect to see fulfilled.

Thanks for clarification Eric -- besides no longer being a
"JVM" (which I am aware of and dont care abt here),
I now start to see the technical problems

So one would also need a way to specify what classes overflow-checking
should apply to,
either a class-annotation,
or perhaps a runtime-flag
-Xcheckforoverflow.classes=my.firstpkg.*;my.secondpkg.*
or similar would be practical.

 

[Tom Anderson]

Could you just elaborate on this, please... what is the main-problem
with actually patching the JVM? Why is it so hard?

It would involve modifying a bytecode interpreter and two just-in-time
compilers, all three highly developed instances of their species, and all
written in C++. How much do you know about interpreters and compilers, and
how is your C++? I am a good Java programmer, but that task would be way
beyond me.

Without having looked into the source-code, this seems like the most
straight-forward and robust way to do it...

Prefixing a statement about some source code with 'without having looked
at the source-code' pretty much disqualifies it completely.

Tell you what: the source code to the x86 version of HotSpot is here:

http://hg.openjdk.java.net/jdk7/hotspot/hotspot/file/tip/src/cpu/x86/vm/

In particular, here's the table of assembly instructions used for each
bytecode in the interpreter:

http://hg.openjdk.java.net/jdk7/hotspot/hotspot/file/tip/src/cpu/x86/vm/templateTable_x86_32.cpp

Have a look at that, and let me know how hard you think it would be to
modify that to do overflow checking (and remember that you can't do it
everywhere, because existing code is written to use overflow - you have to
have some way of only doing it in specified bits of code).

tom

 

[Daniele Futtorovic]

The first thing that comes to mind is altering a JVM so it does
not behave as described in the Java Virtual Machine Specification
means you no longer have a JVM. Specifically, from section 2.4.2:
"The built-in integer operators do not indicate (positive or negative)
overflow in any way; they wrap around on overflow." For good or for
ill, that's a requirement all JVM implementations must satisfy.

But, okay, you start with a JVM and alter it to produce a "KWN"
that behaves just like a JVM except in this one regard. Now a second
difficulty arises: You start running Java on the KWN, and almost at
once you get an arithmetic overflow exception. Investigating, you
find that it occurred in a hashCode() method that's computing the
time-honored sum x0+p*(x1+p*(x2+...)) with the fields x0,x1,... and
a prime p. The overflow is entirely benign, yet "Hello".hashCode()
stops your program in its tracks. So now you need a way to distinguish
expected (benign) overflow from unanticipated (injurious) overflow --
which means you need to alter not only the JVM but also Java. (Or maybe
you could do something with annotations; I'm not sure.) But the main
point is that all existing Java code expects overflow to wrap around,
and lots of that code actually relies on wraparound.

Finally, you've got definitional problems to sort out. For
example, is there an overflow in `int value = (int)Long.LONG_MAX;'?
You need to put on your Language Legislator hat and think about it
before you can decide how your KWN should behave.

Personally, I wish integer over- and under-flow would in fact
throw exceptions, and that the language had something like `unsigned'
to allow the programmer to suppress the exceptions when appropriate.
But that's a wish I don't expect to see fulfilled.

Not to mention the mess if it's an app you plan to distribute.

 

[Gene Wirchenko]

the JVM does not detect it because most hardware does not. You pretty
well have to use long instead of int and mask off and check overflow.

Which hardware does not have overflow detection?

x86 does have an overflow flag.

Sincerely,

Gene Wirchenko

 

[Gene Wirchenko]

[snip]

I think the problem is more a matter of software knowing when overflow
should and should not be treated as an error.

Exactly. C does not do that sort of checking, and the meme has
spread widely. I would much prefer to have things blow up when wrong
than not blow up. It makes for smaller messes.

Sincerely,

Gene Wirchenko

 

[lewbloch]

[snip]

I think the problem is more a matter of software knowing when overflow
should and should not be treated as an error.

     Exactly.  C does not do that sort of checking, and the meme has
spread widely.  I would much prefer to have things blow up when wrong
than not blow up.  It makes for smaller messes.

the problem with that statement is that it's not wrong for Java
primitive integer types to wrap around.

It is, in fact, wrong for them to throw an overflow exception, as many
have pointed out in this thread.

 

[Eric Sosman]

[...]
I would not worry about the "simple" or "efficient" criteria. IMHO, if
one is deciding to apply overflow checking to every computation, one has
already abandoned the hope of efficiency.

I've used machines that raised overflow traps "for free," in
the sense that it was done by the hardware/firmware/microcode, just
like setting condition flags.

Flipping the mode bit that enabled or disabled traps for integer
arithmetic was relatively expensive, so programs tended to set it
one way or the other during initialization and then just leave it
alone. But it's not necessary to use a global bit to get this kind
of behavior: an instruction set might feature both an AddAndWrap and
an AddAndTrap instruction. True, that's not entirely free -- you
pay for extra decoding logic in the instruction pipeline, for example.
But the inefficiencies don't rise to the "abandon hope" level, IMHO.

Besides: What are the relative efficiencies of an error caught
and announced versus a wrong answer computed at great speed without
any indication that it's wrong?

(The machines I speak of were from forty-odd years ago and might
be dismissed as ancientry, but their lineal descendants are still
being made and sold. I don't know how today's editions deal with
overflow, but if you're curious you can write to the vendor. Their
headquarters are in Armonk, NY.)