Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RangeError: bignum too big to convert into `long' #4460

Closed
herwinw opened this issue Jan 27, 2017 · 14 comments
Closed

RangeError: bignum too big to convert into `long' #4460

herwinw opened this issue Jan 27, 2017 · 14 comments

Comments

@herwinw
Copy link

herwinw commented Jan 27, 2017

The following script

require 'ipaddr'
r = IPAddr.new('1.2.3.4').to_range
r.hash

ocasionally generates the following exception:

RangeError: bignum too big to convert into `long'
    hash at org/jruby/RubyRange.java:296
  <main> at foo.rb:3

Related part of the code:

    @JRubyMethod(name = "hash")
    public RubyFixnum hash(ThreadContext context) {
        long hash = isExclusive ? 1 : 0;
        long h = hash;

        long v = invokedynamic(context, begin, MethodNames.HASH).convertToInteger().getLongValue(); // <-- Line 296
        hash ^= v << 1;
        v = invokedynamic(context, end, MethodNames.HASH).convertToInteger().getLongValue();
        hash ^= v << 9;
        hash ^= h << 24;
        return context.runtime.newFixnum(hash);
    }

Running r.begin.hash does not appear to break (it is hard to test however, since the exception doesn't happen every time)

Environment

Provide at least:

  • JRuby version (jruby -v) and command line (flags, JRUBY_OPTS, etc)
    jruby 9.1.7.0 (2.3.1) 2017-01-11 68056ae OpenJDK Server VM 25.111-b14 on 1.8.0_111-8u111-b14-2~bpo8+1-b14 +jit [linux-i386] (installed via rbenv, no extra command line options)

  • Operating system and platform (e.g. uname -a)
    Linux 3.16.0-4-amd64 break script engine #1 SMP Debian 3.16.36-1+deb8u2 (2016-10-19) x86_64 GNU/Linux (but running a 32-bit userspace)

@headius
Copy link
Member

headius commented Jan 27, 2017

Wow, that's super weird. Given that it only happens sometimes, I thought it might be JIT kicking in sometimes. But then running with the JIT off (-X-C) still produces the error, so it's not JIT related.

So given that there's very little outside the JIT that would be nondeterministic in JRuby, it seems like it must be some sort of concurrency problem, and I've marked the issue as such...but I have no idea where to look. It's pretty strange.

@herwinw
Copy link
Author

herwinw commented Jan 29, 2017

After some experiments, I don't think it's concurrency related.

First, I added some printf debugging (which sounds a lot better than System.err.println-debugging), the line with long v is changed to this:

        RubyInteger i = invokedynamic(context, begin, MethodNames.HASH).convertToInteger();
        System.err.println("Value: " + i.getBigIntegerValue());
        long v = i.getLongValue();

A few results of arrow up+return:

herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 9510487529465216614
RangeError: bignum too big to convert into `long'
    hash at org/jruby/RubyRange.java:298
  <main> at /home/herwin/jruby.rb:5
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 1284029946582245428
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 4410829216446578982
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 8596023285375428358
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 5914880351017520138
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 832718489497875144
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 6067146828247338566
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 12790352256001569680
RangeError: bignum too big to convert into `long'
    hash at org/jruby/RubyRange.java:298
  <main> at /home/herwin/jruby.rb:5
herwin@herwinw:~/code/jruby$ bin/jruby ~/jruby.rb 
Value: 17579396736871717122
RangeError: bignum too big to convert into `long'
    hash at org/jruby/RubyRange.java:298
  <main> at /home/herwin/jruby.rb:5

In other words: if the value of IPAddr#hash gets too big, the result does not fit into a long and the error occurs. The critical value appears to be somewhere between 8596023285375428358 and 9510487529465216614. It has been ages since I looked at the JVM specs, but I guess we have a bit more than the specs of the long allow us. Converting 8596023285375428358 fits in 63 bits, but 9510487529465216614 is 64 bits. My money is on the theory that long is 64 bits and requires 1 bit for the sign (where two's complement would be close enough too)

The implementation of IPAddr#hash looks like the regular hash value is left-shifted once, which would explain why this doesn't happen with other classes.

  def hash
    return ([@addr, @mask_addr].hash << 1) | (ipv4? ? 0 : 1)
  end

If JRuby follows the model of Ruby for hashing, there is a random seed when the program starts. Paste IPAddr.new('1.2.3.4').hash a few times in a single IRB session and the result is stable, run ruby -ripaddr -e 'puts IPAddr.new("1.2.3.4").hash' a few times and the result changes every time. A great explanation why can be found at https://media.ccc.de/v/28c3-4680-en-effective_dos_attacks_against_web_application_platforms This would explain why it only happens sometimes.

@herwinw
Copy link
Author

herwinw commented Jan 29, 2017

And suddenly this cases reminds me that I still have to fix #4375. Well, not today

@herwinw
Copy link
Author

herwinw commented Jan 30, 2017

I'm not exactly an expert here, but I guess the following change to IPAddr#hash would result in "good enoug" hashes:

def hash
  return [@addr, @mask_addr].hash ^ (ipv4? ? 0 : 1)
end

I'm not sure if the ipv4 call would even have any added value here, the possible range of @addr for IPv4 addresses is completely disjunct from IPv6 addresses. And I don't think it would really be a problem if there is a certain IPv4 address that hashes to the same value as a certain IPv6 address, there is no definitive need for hashes to be unique.

Downside of this all is that things have to be fixed in the stdlib of MRI

@headius
Copy link
Member

headius commented Mar 3, 2017

Great research! Your patch might be good enough for 9.1.8.0, but I'm surprised that MRI doesn't have trouble with Bignum hashes too. Going to poke around a little bit.

@headius
Copy link
Member

headius commented Mar 3, 2017

Ok, I believe I'd figured out the problem.

MRI appears to allow #hash impls to return a Bignum if that Bignum's value can fit into an unsigned long's bits. Or at least that's how I interpret this code from MRI's bignum.c

long        
rb_big2long(VALUE x)
{       
    unsigned long num = big2ulong(x, "long");
        
    if (BIGNUM_POSITIVE_P(x)) {
        if (num <= LONG_MAX)
            return num;
    }
    else {
        if (num <= 1+(unsigned long)(-(LONG_MIN+1)))
            return -(long)(num-1)-1;
    }
    rb_raise(rb_eRangeError, "bignum too big to convert into `long'");
}

So this would seem to accommodate numbers from LONG_MIN to something like LONG_MIN * 2 -1 and allow our cases through.

However, the following patch does not seem to be quite right. I hate bit math, especially when dealing with the lack of unsigned numerics in Java.

diff --git a/core/src/main/java/org/jruby/RubyBignum.java b/core/src/main/java/org/jruby/RubyBignum.java
index c26e65b..bfc8ae0 100644
--- a/core/src/main/java/org/jruby/RubyBignum.java
+++ b/core/src/main/java/org/jruby/RubyBignum.java
@@ -158,12 +158,19 @@ public class RubyBignum extends RubyInteger {
      *
      */
     public static long big2long(RubyBignum value) {
-        BigInteger big = value.getValue();
+        long num = big2ulong(value);
 
-        if (big.compareTo(LONG_MIN) < 0 || big.compareTo(LONG_MAX) > 0) {
-            throw value.getRuntime().newRangeError("bignum too big to convert into `long'");
+        if (value.value.signum() > 0) {
+            if (num <= Long.MAX_VALUE) {
+                return num;
+            }
+        } else {
+            if (num / 2 < Long.MAX_VALUE) {
+                return num;
+            }
         }
-        return big.longValue();
+
+        throw value.getRuntime().newRangeError("bignum too big to convert into `long'");
     }
 
     /** rb_big2ulong

I'll take another stab at this tomorrow, but if you get to it before me I wouldn't complain.

@headius
Copy link
Member

headius commented Mar 3, 2017

I should rephrase; changing our big2long logic appears to break other specs. This may mean we're not supposed to be using big2long for the places that fail.

1)
Array#fill with (filler, index, length) raises an ArgumentError or RangeError for too-large sizes FAILED
Expected RangeError but no exception was raised ([1, 2, 3] was returned)
/home/headius/projects/jruby/spec/ruby/core/array/fill_spec.rb:212:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/array/fill_spec.rb:77:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

2)
Array#first raises a RangeError when count is a Bignum FAILED
Expected RangeError but no exception was raised ([] was returned)
/home/headius/projects/jruby/spec/ruby/core/array/first_spec.rb:37:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/array/first_spec.rb:4:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

3)
Enumerable#first raises a RangeError when passed a Bignum FAILED
Expected RangeError but no exception was raised ([] was returned)
/home/headius/projects/jruby/spec/ruby/core/enumerable/first_spec.rb:22:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/enumerable/first_spec.rb:5:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

4)
Integer#chr without argument raises a RangeError is self is less than 0 FAILED
Expected RangeError but no exception was raised ("\x00" was returned)
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:14:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:3:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

5)
Integer#chr without argument when Encoding.default_internal is nil raises a RangeError is self is greater than 255 FAILED
Expected RangeError but no exception was raised ("\x00" was returned)
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:48:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:3:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

6)
Integer#chr with an encoding argument raises a RangeError is self is less than 0 FAILED
Expected RangeError but no exception was raised ("\x00" was returned)
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:165:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/core/integer/chr_spec.rb:143:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

7)
StringScanner#peek raises a RangeError when the passed argument is a Bignum FAILED
Expected RangeError but no exception was raised ("" was returned)
/home/headius/projects/jruby/spec/ruby/library/stringscanner/shared/peek.rb:23:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/library/stringscanner/peek_spec.rb:5:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

8)
StringScanner#peep raises a RangeError when the passed argument is a Bignum FAILED
Expected RangeError but no exception was raised ("" was returned)
/home/headius/projects/jruby/spec/ruby/library/stringscanner/shared/peek.rb:23:in `block in (root)'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyEnumerable.java:1596:in `all?'
org/jruby/RubyFixnum.java:299:in `times'
org/jruby/RubyArray.java:1734:in `each'
/home/headius/projects/jruby/spec/ruby/library/stringscanner/peep_spec.rb:5:in `<main>'
org/jruby/RubyKernel.java:979:in `load'
org/jruby/RubyBasicObject.java:1687:in `instance_eval'
org/jruby/RubyArray.java:1734:in `each'

@headius
Copy link
Member

headius commented Mar 3, 2017

For the record I'm mostly ok with the IPAddr patch, but I'd really like to fix our big2long logic properly.

@headius
Copy link
Member

headius commented Mar 3, 2017

I'm going to go with the IPAddr patch for now. The spec failures above show how sensitive this big2long logic is to changes, and we shouldn't rush that into 9.1.8.0 at the last minute.

We should undo the IPAddr patch after fixing this properly in 9.2.

@headius
Copy link
Member

headius commented Mar 3, 2017

I have applied your temporary patch to ipaddr.rb.

There's also a simpler workaround that doesn't involve stdlib, since this is simply a flaw in how our Range handles start or end hash resulting in a Bignum:

class X
  def <=>(other)
    1
  end

  def hash
    1<<63
  end
end

p ((X.new)..1).hash

We raise the error above while MRI handles this ok.

@headius headius modified the milestones: JRuby 9.2.0.0, JRuby 9.1.8.0 Mar 3, 2017
headius added a commit to jruby/ruby that referenced this issue Mar 14, 2017
Temporary patch to work around Range not supporting Bignum hashes.
headius added a commit to jruby/ruby that referenced this issue Mar 14, 2017
Temporary patch to work around Range not supporting Bignum hashes.
@herwinw
Copy link
Author

herwinw commented Oct 23, 2017

It looks like the IPAddr class has been moved from the core to a gem (see https://github.com/ruby/ipaddr), which means the temporary changes will be ineffective in a near future.

@headius
Copy link
Member

headius commented Oct 31, 2017

@herwinw The new gemified stdlib will be for Ruby 2.5+, and we will work with them to get JRuby-specific versions released. Until then, though, we'll still ship our own copy of stdlib.

We will also work to get the hack out of JRuby.

@headius
Copy link
Member

headius commented Nov 29, 2017

Link #4875

@headius
Copy link
Member

headius commented Nov 29, 2017

The secret missing logic was in Range#hash, which should be using the equivalent of rb_hash to calculate hash values from Ruby objects. Fix coming.

headius added a commit to jruby/ruby that referenced this issue Nov 29, 2017
headius added a commit to jruby/ruby that referenced this issue Nov 29, 2017
@headius headius modified the milestones: JRuby 9.2.0.0, JRuby 9.1.15.0 Nov 29, 2017
ahorek pushed a commit to ahorek/ruby that referenced this issue Dec 17, 2018
Temporary patch to work around Range not supporting Bignum hashes.
ahorek pushed a commit to ahorek/ruby that referenced this issue Dec 17, 2018
headius added a commit to jruby/ruby that referenced this issue Feb 12, 2019
Temporary patch to work around Range not supporting Bignum hashes.
headius added a commit to jruby/ruby that referenced this issue Feb 12, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants