Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger (compressed)
Raif S. Naffah wrote:
> hello all,
>
> the attached patch adds support for GNU MP in BigInteger if/when configured.
>
> 2006-09-03 Raif S. Naffah <[EMAIL PROTECTED]>
>
> PR Classpath/28664
> * INSTALL: Added documentation about GNU MP.
> * configure.ac: Add support for configuring GNU MP.
> * native/jni/Makefile.am: Include java-math directory if required.
> * native/jni/java_math/.cvsignore: New file.
> * native/jni/java_math/Makefile.am: Likewise.
> * native/jni/java_math/java_math_BigInteger.c: Likewise.
> * native/jni/java_math: New folder.
> * include/java_math_BigInteger.h: New file.
> * java/math/BigInteger.java: Added support for native methods.
> * gnu/classpath/Configuration.java.in (WANT_NATIVE_BIG_INTEGER): New
> field.
>
> this was tested with current CVS head and cacao trunk (updated to revision
> 5285). Mauve tests for BigInteger, and crypto classes
> (gnu.testlet.java.security and gnu.testlet.javax.crypto) all pass with cacao
> but systematically, almost half of them, fail with jamvm (latest CVS head).
>
> a couple of more Mauve tests will be added soon, and another couple will be
> updated.
>
> Mark, would you be kind as to have a look at this before i commit?
>
> finally, thanks for Mark and Dalibor for their help and advice.
>
Some comments:
> +static void
> +_throw (JNIEnv *env, const char *exception, const char *msg)
> +{
> + jclass _theclass = (*env)->FindClass (env, exception);
> + TRACE("begin");
> + if (! _theclass)
> +{
> + (*env)->FatalError (env, "exception class not found");
> +}
> + (*env)->ThrowNew (env, _theclass, msg);
> + TRACE("end");
> +}
You should use JCL_ThrowException.
> + * a. Pass NULLs to the mp_set_memory_functions implying that GMP should use
> + *malloc, realloc and free for memory allocation, and if they fail GMP
> + *will print a message to the standard error output and terminates the
> + *program.
Should you use JCL_malloc, etc. there? Also, it's a little odd that
you're using JNI_OnLoad, and aren't just calling some native init method
when the BigInteger class is loaded.
> + For building, and using a GNU MP based implementation of the
> + java.math.BigInteger class, you will need, at least version 3.1
> + of GMP. http://swox.com/gmp/
That's bad grammar. If you omit the first and third comma it sounds a
little better.
As far as the implementation (and the comments about finalize, etc.
elsewhere in this thread) I wonder if it's possible here to use a direct
ByteBuffer to store your native state (I guess GMP is allocating
structures behind the scenes, and is sticking it into your mpz_ptr; BUT,
BigInteger is immutable, so you presumably know how large it is), then
you pass that ByteBuffer to all native methods, which pull out the
native pointer.
I'm really a fan of this approach, which I used to some success in my
kqueue Selector implementation (which hasn't been committed yet,
unfortunately), and I do encourage others to try it. The benefits of
doing it this way are legion:
- The GC will take care of freeing the native state for you.
- You don't need to finalize anything, and don't need to synchronize.
- Your native methods can be static, and what's more, they can be in
an entirely different class, so other VM implementors won't have to deal
with native methods being in java.math directly.
- You need exactly one JNI function call (GetDirectBufferAddress) and
no (or possibly little) reflection.
- You can debug your native state in Javaland, if you feel like it.
It makes your usage of JNI *much* more careful and simple.
Thanks.
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
Raif S. Naffah wrote: > > + with GMP969ms. > - without GMP 11,718ms. > What VM?
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
earlier, i wrote: > On Tuesday 05 September 2006 04:52, Jeroen Frijters wrote: > > Raif S. Naffah wrote: > > > On Monday 04 September 2006 20:40, Jeroen Frijters wrote: > > > > ... > > > > ...*All* native method calls that use the > > > > native_ptr need to be synchronized. > > > > > > i'm sorry but it is still not obvious to me why this should > > > be so. every instance of a BigInteger has its own value of > > > native_ptr. what are we protecting by synchronizing the > > > methods? > > > > The case where an attacker calls finalize *while* the native code is > > currently running and manipulating the data structure that is being > > freed at the same time by the finalize method. > > but isn't synchronizing the finalize() method enough to prevent this > scenario? no it isn't. i'll have a look at your suggested pattern and re-submit the patch. thanks + cheers; rsn pgpd0NxtYnm2Y.pgp Description: PGP signature
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
On Tuesday 05 September 2006 04:52, Jeroen Frijters wrote: > Raif S. Naffah wrote: > > On Monday 04 September 2006 20:40, Jeroen Frijters wrote: > > > ... > > > ...*All* native method calls that use the > > > native_ptr need to be synchronized. > > > > i'm sorry but it is still not obvious to me why this should > > be so. every instance of a BigInteger has its own value of > > native_ptr. what are we protecting by synchronizing the > > methods? > > The case where an attacker calls finalize *while* the native code is > currently running and manipulating the data structure that is being > freed at the same time by the finalize method. but isn't synchronizing the finalize() method enough to prevent this scenario? cheers; rsn pgpI5RxRGTGWl.pgp Description: PGP signature
RE: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
Raif S. Naffah wrote: > On Monday 04 September 2006 20:40, Jeroen Frijters wrote: > > ... > > ...*All* native method calls that use the > > native_ptr need to be synchronized. > > i'm sorry but it is still not obvious to me why this should > be so. every instance of a BigInteger has its own value of > native_ptr. what are we protecting by synchronizing the > methods? The case where an attacker calls finalize *while* the native code is currently running and manipulating the data structure that is being freed at the same time by the finalize method. Regards, Jeroen
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
On Monday 04 September 2006 20:40, Jeroen Frijters wrote: > ... > ...*All* native method calls that use the > native_ptr need to be synchronized. i'm sorry but it is still not obvious to me why this should be so. every instance of a BigInteger has its own value of native_ptr. what are we protecting by synchronizing the methods? cheers; rsn pgpjkLY3TR9Sj.pgp Description: PGP signature
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger (compressed)
hello Robert, On Sunday 03 September 2006 23:30, Robert Lougher wrote: > ... > Try commenting out the code in the function: > > setDoublePrecision() located in jamvm/src/os/linux/i386/init.c > > This changes the precision of the FPU to 64 bits from extended 80-bit > precision which is the Linux default. > > This is necessary to completely conform to the Java specification. > See http://www.vinc17.org/research/extended.en.html for a bug report > on various OS VMs. > > GMP appears to be very sensitive to the compiler used. I would guess > it would also produce wrong results if the processor mode was changed. > Perhaps cacao does not do this. Can you also try the test given in > the above page? before commenting out the code of setDoublePrecision(): $ ./bin/jamvm -cp ~/. test z = 9.007199254740994E15 d = 0.0 after: $ ./bin/jamvm -cp ~/. test z = 9.007199254740996E15 d = 2.0 unfortunately, after commenting out the code, the tests' failure pattern is unchanged. as for cacao, here is the tests's output: $ ./bin/cacao -cp ~/. test z = 9.007199254740994E15 d = 0.0 > Thanks, > > Rob. > > On 9/3/06, Raif S. Naffah <[EMAIL PROTECTED]> wrote: > > hello Robert, > > > > On Sunday 03 September 2006 15:26, Robert Lougher wrote: > > > Hi, > > > > > > What architecture were you running JamVM on? > > > > here is the uname related lines in my jamvm config.log: > > > > uname -m = i686 > > uname -r = 2.6.17-1.2174_FC5smp > > uname -s = Linux > > uname -v = #1 SMP Tue Aug 8 16:00:39 EDT 2006 cheers; rsn pgpTC68fon7fP.pgp Description: PGP signature
RE: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
Raif S. Naffah wrote;
> i followed the advice given in [1] and synchronized the code
> in the BigInteger finalize() method which now looks like so:
This is not yet sufficient. *All* native method calls that use the
native_ptr need to be synchronized.
It is also not very good practice to synchronize on the object itself
and you really shouldn't have a finalize method that is non-final
(otherwise untrusted code can leak unmanaged memory by allocating
BigInteger subclasses that override the finalize and don't call the base
class method).
When working with a pointer to native memory (or a handle) the only
reliable pattern is really:
class BigInteger
{
private NativeData nd = new NativeData();
private static final class NativeData
{
private Pointer native_data;
synchronized int Compare(BigInteger x, BigInteger y)
{
return natCompare(x.nd.native_data, y.nd.native_data);
}
protected synchronized void finalize()
{
natFinalize(native_data);
}
private native void natFinalize(Pointer p);
private native int natCompare(Pointer x, Pointer y);
}
}
Regards,
Jeroen
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
> On Sunday 03 September 2006 18:02, Jeroen Frijters wrote:
> > ...
> > Most people do not understand the (security) implications of using
> > native code in combination with handles and most of the code out there
> > is simply wrong (as is the current patch). See [1].
>
> i'll have to read this document first.
>
> > Regards,
> > Jeroen
> >
> > [1]
> > http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/java_finalizers.pd
> > f
and later,
On Sunday 03 September 2006 22:29, Jeroen Frijters wrote:
>
> The finalizer looks dangerous. For example, a subclass could call
> finalize multiple times, resulting in multiple calls to free() (which
> may or may not be exploitable). Note that you cannot solve this by only
> fixing the finalizer (see the PDF I linked to previously).
i had a look at the slides and i wrote a small Mauve test (attached) to test
some changes to the code of both the finalize() and natFinalize() methods.
unfortunately i was not able to test it --the VM (cacao) throws a SIGSEV on
the second finalize.
i followed the advice given in [1] and synchronized the code in the BigInteger
finalize() method which now looks like so:
protected void finalize() throws Throwable
{
try
{
synchronized (this)
{
if (USING_NATIVE)
this.natFinalize();
}
}
finally
{
super.finalize();
}
}
in addition, the natFinalize() code now looks like so:
_this = (mpz_ptr)(*env)->GetObjectField (env, this, native_ptr);
if (_this != NULL)
{
mpz_clear (_this);
free (_this);
_this = NULL;
}
those changes should address your concern about calling free() multiple times.
a future version of the native code, could follow more closely the other
suggestions in [1] and also would allow less fragmentation of memory by, for
example:
a. allocating a pool of data structure from which needed mpz_t for BigIntegers
and work variables can be pulled.
b. when a natInitialize() method or a work mpz_t is needed, an entry in the
pool can be marked as in-use.
c. replace the natFinalize() with returning the associated mpz_t to the pool.
d. add an implementation of the JNI 1.2 On_Unload method which frees the pool.
cheers;
rsn
/* finalize.java
Copyright (C) 2006 Free Software Foundation, Inc.
This file is part of Mauve.
Mauve is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
Mauve is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with Mauve; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.
*/
// Tags: JDK1.2
package gnu.testlet.java.math.BigInteger;
import gnu.testlet.TestHarness;
import gnu.testlet.Testlet;
import java.math.BigInteger;
/**
* tests for the BigInteger.finalize() method.
*/
public class finalize
implements Testlet
{
public void test(TestHarness harness)
{
harness.checkPoint("finalize");
try
{
BadBigInteger x = new BadBigInteger("104");
x.finalize();
x.finalize();
}
catch (Throwable x)
{
harness.debug(x);
harness.fail("finalize: " + x);
}
}
class BadBigInteger extends BigInteger
{
BadBigInteger(String s)
{
super(s);
}
public void finalize() throws Throwable
{
super.finalize();
}
}
}
pgpLVRTD97GIK.pgp
Description: PGP signature
Re: Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger (compressed)
Hi, Try commenting out the code in the function: setDoublePrecision() located in jamvm/src/os/linux/i386/init.c This changes the precision of the FPU to 64 bits from extended 80-bit precision which is the Linux default. This is necessary to completely conform to the Java specification. See http://www.vinc17.org/research/extended.en.html for a bug report on various OS VMs. GMP appears to be very sensitive to the compiler used. I would guess it would also produce wrong results if the processor mode was changed. Perhaps cacao does not do this. Can you also try the test given in the above page? Thanks, Rob. On 9/3/06, Raif S. Naffah <[EMAIL PROTECTED]> wrote: hello Robert, On Sunday 03 September 2006 15:26, Robert Lougher wrote: > Hi, > > What architecture were you running JamVM on? here is the uname related lines in my jamvm config.log: uname -m = i686 uname -r = 2.6.17-1.2174_FC5smp uname -s = Linux uname -v = #1 SMP Tue Aug 8 16:00:39 EDT 2006 cheers; rsn
RE: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
Raif S. Naffah wrote: > the attractiveness of the native code is performance. to > quickly see how the > new methods improve for example RSA key generation, one can > modify the code > in TestOfRSAKeyGeneration (Mauve) to call the generate() > method N times and > print the duration --on my machine i get for 5 rounds: > > + with GMP969ms. > - without GMP 11,718ms. Hmm. That is indeed significant. However, looking at the profile for generate(), it spends nearly all its time in BigInteger.isProbablePrime() and I ran a few comparisons between our implementation of isProbablePrime() and Sun's and we're not that much slower (on IKVM only about 50% slower), I'm not sure what to make of that. > > - Can you prove there aren't any security holes in your native code? > > there are none to my knowledge. The finalizer looks dangerous. For example, a subclass could call finalize multiple times, resulting in multiple calls to free() (which may or may not be exploitable). Note that you cannot solve this by only fixing the finalizer (see the PDF I linked to previously). Regards, Jeroen
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
hello Sven, On Sunday 03 September 2006 19:46, Sven de Marothy wrote: > On Sun, 2006-09-03 at 10:02 +0200, Jeroen Frijters wrote: > > Raif S. Naffah wrote: > > > the attached patch adds support for GNU MP in BigInteger > > > if/when configured. > > > > How/why is the native version better? Is it really worthwhile to > > complicate the code this way? Where are the benchmarks that prove the > > native code is faster? > > Valid questions, indeed... indeed. see my previous reply to Jeroen about the performance. > ... > What I'd like to propose here is that in any case, the choice of > implementation should be strictly a build-time option, and the > two implementations kept entirely seperate. i thought having the java code in one place is clearer, and helps showing the common elements... but this is my opinion. > I'm not very happy about the alternatives: Having two implementations in > one class (as in the proposed patch), or moving the actual impl into yet > another VM* class. (Indeed I've been increasingly critical recently over > that part. I've still not worked out an exact solution, but suffice to > say that I'll be proposing some changes in that area soon). from the sound of it, it looks like now is the time! > Anyway enough disgression, I hope I didn't sound harsh, Raif! :)... not at all. cheers; rsn pgp1XgzgloFe0.pgp Description: PGP signature
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
hello Jeroen, On Sunday 03 September 2006 18:02, Jeroen Frijters wrote: > ... > How/why is the native version better? Is it really worthwhile to > complicate the code this way? Where are the benchmarks that prove the > native code is faster? the attractiveness of the native code is performance. to quickly see how the new methods improve for example RSA key generation, one can modify the code in TestOfRSAKeyGeneration (Mauve) to call the generate() method N times and print the duration --on my machine i get for 5 rounds: + with GMP969ms. - without GMP 11,718ms. > I assume it is already widely know that I dislike native code (because > of how IKVM works), but let me try to explain why native code sucks for > all VMs: > > - Some VMs are hardened against stack overflow, this means that stack > overflow in Java or VM code will not result in terminating the process, > but simply a StackOverflowException. Is the native code you are > introducing similarly harneded? no it is not. > - Some VMs are hardened against OOM, this means that memory allocation > failures (both in Java and in the VM) will not result in terminating the > process, but simply a OutOfMemoryError. Is the native code you are > introducing similarly harneded? no it is not. > - Native memory allocation potentially fragments the heap and this can > have significant performance implications. > - Can you prove there aren't any security holes in your native code? there are none to my knowledge. > Most people do not understand the (security) implications of using > native code in combination with handles and most of the code out there > is simply wrong (as is the current patch). See [1]. i'll have to read this document first. > Regards, > Jeroen > > [1] > http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/java_finalizers.pd > f -- cheers; rsn pgp6yVFG73SSP.pgp Description: PGP signature
RE: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
On Sun, 2006-09-03 at 10:02 +0200, Jeroen Frijters wrote: > Raif S. Naffah wrote: > > the attached patch adds support for GNU MP in BigInteger > > if/when configured. > > How/why is the native version better? Is it really worthwhile to > complicate the code this way? Where are the benchmarks that prove the > native code is faster? Valid questions, indeed. I don't purport to have the answers to them, but IIRC, Kaffe has (or formerly had) a GNU MP-based implementation which supposedly was faster. However, I wouldn't automatically think this was the case, given the large overhead of JNI calls. (GOTO [1] for a longer rambling about that) What I'd like to propose here is that in any case, the choice of implementation should be strictly a build-time option, and the two implementations kept entirely seperate. I'm not very happy about the alternatives: Having two implementations in one class (as in the proposed patch), or moving the actual impl into yet another VM* class. (Indeed I've been increasingly critical recently over that part. I've still not worked out an exact solution, but suffice to say that I'll be proposing some changes in that area soon). [1] Considering a usage; multiplying two 1024-bit numbers to generate a 2048-bit crypto key or such. Each number is 32 ints, and using ordinary long multiplication (which is what we do currently) that means 32*32 = 1024 int multiplications. Which might sound like a lot, but now consider that a JNI call has an overhead of at least few hundred instructions or so, then the native routine would have to perform at least 20% faster than JIT-compiled code to break even. Which may be the case, but not necessarily. An example I have real numbers for is the NIO charset converters (a similar type of job: Fast individual operations performed in bulk quantities). Benchmarking the GNU iconv-based converter versus the pure java one on JamVM -Certainly the best possible scenario for the native code; since Jam has excellent JNI speed, and interpreted java code. In that case the Java-based converters are still faster, due to the JNI overhead. The break-even point on my machine was about 2k characters. With a VM like Cacao that'll be much higher (about more than twice the JNI overhead, and 5x or so faster java code). Another drawback of native code IMHO (which Jeroen doesn't mention) is that you also create an undesireable situation where better VMs perform worse, since the VMs in general can't optimize the native code (e.g. method inlining). (Creating a VM that can inline dynamically loaded native library methods is left as an exercise for the reader ;)) Anyway enough disgression, I hope I didn't sound harsh, Raif! :) If it's faster we should definitely have an implementation. My main point is that I'd just like to see the implementations kept seperate. (Too bad there's not a SPI for this. Brings me back to my old gripe that I really wish you could make constructors create subclasses.) /Sven
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger (compressed)
hello Robert, On Sunday 03 September 2006 15:26, Robert Lougher wrote: > Hi, > > What architecture were you running JamVM on? here is the uname related lines in my jamvm config.log: uname -m = i686 uname -r = 2.6.17-1.2174_FC5smp uname -s = Linux uname -v = #1 SMP Tue Aug 8 16:00:39 EDT 2006 cheers; rsn pgpDx62OSIWcJ.pgp Description: PGP signature
RE: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger(compressed)
Raif S. Naffah wrote: > the attached patch adds support for GNU MP in BigInteger > if/when configured. How/why is the native version better? Is it really worthwhile to complicate the code this way? Where are the benchmarks that prove the native code is faster? I assume it is already widely know that I dislike native code (because of how IKVM works), but let me try to explain why native code sucks for all VMs: - Some VMs are hardened against stack overflow, this means that stack overflow in Java or VM code will not result in terminating the process, but simply a StackOverflowException. Is the native code you are introducing similarly harneded? - Some VMs are hardened against OOM, this means that memory allocation failures (both in Java and in the VM) will not result in terminating the process, but simply a OutOfMemoryError. Is the native code you are introducing similarly harneded? - Native memory allocation potentially fragments the heap and this can have significant performance implications. - Can you prove there aren't any security holes in your native code? Most people do not understand the (security) implications of using native code in combination with handles and most of the code out there is simply wrong (as is the current patch). See [1]. Regards, Jeroen [1] http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/java_finalizers.pd f
Re: [cp-patches] RFC: PR Classpath/28664 - GNU MP based BigInteger (compressed)
Hi, What architecture were you running JamVM on? Rob. On 9/3/06, Raif S. Naffah <[EMAIL PROTECTED]> wrote: hello all, the attached patch adds support for GNU MP in BigInteger if/when configured. 2006-09-03 Raif S. Naffah <[EMAIL PROTECTED]> PR Classpath/28664 * INSTALL: Added documentation about GNU MP. * configure.ac: Add support for configuring GNU MP. * native/jni/Makefile.am: Include java-math directory if required. * native/jni/java_math/.cvsignore: New file. * native/jni/java_math/Makefile.am: Likewise. * native/jni/java_math/java_math_BigInteger.c: Likewise. * native/jni/java_math: New folder. * include/java_math_BigInteger.h: New file. * java/math/BigInteger.java: Added support for native methods. * gnu/classpath/Configuration.java.in (WANT_NATIVE_BIG_INTEGER): New field. this was tested with current CVS head and cacao trunk (updated to revision 5285). Mauve tests for BigInteger, and crypto classes (gnu.testlet.java.security and gnu.testlet.javax.crypto) all pass with cacao but systematically, almost half of them, fail with jamvm (latest CVS head). a couple of more Mauve tests will be added soon, and another couple will be updated. Mark, would you be kind as to have a look at this before i commit? finally, thanks for Mark and Dalibor for their help and advice. cheers; rsn
