This is the mail archive of the mailing list for the Java project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

RE: [Patch] Some fixes for bounds checking arithmetic.

There's an orthogonal but related issue that might be worth mentioning.
Last I looked some of the routines that involve this
bounds checking show up fairly high on profiles for SPECjbb and probably
also real code.  Most of the bounds checking is done with tests like

if (a > b || c > d || e > f)

My guess would be that on most architectures, it would be better to compile
this as

if ((long)((b - a) | (d - c) | (f - e)) < 0)

i.e. or sign bits together, and do a single test and branch on the result.
This reduces the number of branches, and thus avoids filling up branch
prediction tables with this sort of stuff.  It also clearly allows
all the expressions to be scheduled in parallel.

Last I checked, gcc didn't seem to do this, even on Itanium where it
probably matters more than X86.  (On Itanium, it has started getting close
by almost proper use of the predicate registers.)  Even with perfect
analysis, it often can't quite, since the later checks may involve loads, and
it doesn't know those are safe to evaluate out of order.

Has anyone timed something along these lines?  Is this an argument
for a set of macros/inline functions at a slightly lower level, e.g.

if (SUB_COMPARE3(a, b, c, d, e, f)) ...

so that all the subscript checks use a standard set of macros/inline functions
for the comparison so that this becomes easy to tune?  The macros
could presumably also add the __builtin_expect calls which should
presumably be there, but aren't.


> -----Original Message-----
> From: Ralph Loader []
> Sent: Monday, September 22, 2003 11:43 PM
> To:
> Subject: [Patch] Some fixes for bounds checking
> arithmetic.
> libgcj contains many places where checking of array index arguments
> passed to methods is done incorrectly.
> The attached patch fixes those in that it is not 
> difficult
> to write test cases for.
> One of the test cases in the patch is commented out - it causes a
> warning during the link, which seems to cause the test to fail
> extraneously.  If someone can tell me how to turn off or ignore the
> warning message, I will do so and uncomment the test case.
> This patch passes a make check in libjava.
> There are many other instances of incorrect bounds checking that would
> require a 64 bit machine with gigabytes of memory (which I 
> don't have),
> in order to write proper test cases.
> Alternatively, I could fix those without test cases.  Would that be
> acceptable?
> Ralph.
> 2003-09-23  Ralph Loader  <>
> 	* java/lang/ (getChars):
> 	Fix validation of array indexes.
> 	(getBytes, regionMatches, startsWith, valueOf): Likewise.
> 	* testsuite/libjava.lang/ New file.
>  	* testsuite/libjava.lang/String_overflow.out: New file.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]