Bug #18518: NoMemoryError + [FATAL] failed to allocate memory for twice 1 << large

• Status: Rejected
• Priority: Normal
• Assignee: -
• Target version: -
• ruby -v: ruby 3.0.2p107 (2021-07-07 revision 0db68f0233) [x86_64-linux]
• Backport: 2.6: UNKNOWN, 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN

[Eregon (Benoit Daloze)]

Repro:

exp = 2**40 # also fails with bignum e.g. 2**64

def exc
  begin
    yield
  rescue NoMemoryError => e
    p :NoMemoryError
  end
end

p exp
exc { (1 << exp) }
exc { (-1 << exp) }
exc { (bignum_value << exp) }
exc { (-bignum_value << exp) }

Output:

$ ruby -v mri_oom.rb
ruby 3.0.2p107 (2021-07-07 revision 0db68f0233) [x86_64-linux]
mri_oom.rb:7: warning: assigned but unused variable - e
1099511627776
:NoMemoryError
[FATAL] failed to allocate memory

3.1.0 seems fine:

$ ruby -v mri_oom.rb
ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x86_64-linux]
mri_oom.rb:7: warning: assigned but unused variable - e
1099511627776
:NoMemoryError
:NoMemoryError
:NoMemoryError
:NoMemoryError

[Eregon (Benoit Daloze)]

• Related to Bug #18517: 0 << (2**40) is NoMemoryError but 0 << (2**80) is 0 added

[Eregon (Benoit Daloze)]

Actually I'm not sure this is properly fixed on 3.1.0, it looks brittle, for instance it fails in GitHub Actions on macOS:
https://github.com/ruby/spec/runs/4981061444?check_suite_focus=true

NoMemoryError might also be a bit weird for this.
How about raising RangeError or TypeError for any exponent which does not fit in a 32-bit signed int?
Such cases don't make much sense anyway.

[Eregon (Benoit Daloze)]

From this log it's clear this issue happens on 3.1.0 macOS:
https://github.com/eregon/rubyspec/runs/4981235909?check_suite_focus=true

2022-01-28T13:37:48.1570860Z Integer#<< (with n << m) when m is a bignum or larger than int
2022-01-28T13:37:48.1659830Z - returns -1 when m < 0 and n < 0
2022-01-28T13:37:48.1755940Z - returns 0 when m < 0 and n >= 0
2022-01-28T13:37:48.1856250Z - returns 0 when m > 0 bignum and n == 0
2022-01-28T13:40:01.6596730Z /Users/runner/work/_temp/353a7019-b804-42ad-941b-7043b8a7804b.sh: line 1:  1391 Killed: 9               ../mspec/bin/mspec -fs --timeout 90
2022-01-28T13:40:01.6597290Z - raises NoMemoryError when m > 0 and n != 0
2022-01-28T13:40:01.6671710Z ##[error]Process completed with exit code 137.

[Eregon (Benoit Daloze)]

This is still not fixed.
I think CRuby should check if RHS is bigger than 2**31 and if so raise an exception immediately instead of taking a lot of time and run into OOM:
https://github.com/ruby/ruby/commit/5df711844586312891bb466dbc72265490488d94#commitcomment-95187725

[Eregon (Benoit Daloze)]

FWIW on JRuby:

$ ruby -v
jruby 9.4.1.0-SNAPSHOT (3.1.0) 2022-12-19 6416265092 OpenJDK 64-Bit Server VM 17.0.5+8 on 17.0.5+8 +jit [x86_64-linux]
$ jruby -e 'p(1 << (2**64))'
RangeError: bignum too big to convert into `long'
$ jruby -e 'p(1 << (2**40))'
1 # JRuby bug: https://github.com/jruby/jruby/issues/7554

RangeError seems a fair error if the RHS does not fit in a 32-bit signed int, probably better than NoMemoryError.

[Eregon (Benoit Daloze)]

So on 32-bit platforms it already behaves as I would expect, from the log in https://bugs.ruby-lang.org/issues/19260?next_issue_id=19259&prev_issue_id=19261#note-1

1 << (2**40) #=> RangeError (shift width too big)

I think a shift width over 32 signed bits is too much for all platforms, and it would be useful if the behavior in that regard is the same for all platforms.
Nobody wants to wait a very long time only to get a NoMemoryError for such code, isn't it?

[headius (Charles Nutter)]

There's no practical reason to support left shift of greater than integer max, so I would support a fast check and RangeError. It would make more sense than just blowing up memory and raising NoMemoryError for something that should never work (1 << (2**32) produces a big integer at least 2^29 bytes wide, more than 0.5GB).

[nobu (Nobuyoshi Nakada)]

• Status changed from Open to Rejected

It is a test for the development branch and unrelated to users using released versions.

[Eregon (Benoit Daloze)]

nobu (Nobuyoshi Nakada) wrote in #note-8:

It is a test for the development branch and unrelated to users using released versions.

It might not be clear given the original bug report, but the behavior of NoMemoryError vs RangeError on CRuby for 1 << (2**40) is independent of dev/released version.
So in this issue I suggest https://bugs.ruby-lang.org/issues/18518#note-4:

I think CRuby should check if RHS is bigger than 2**31 and if so raise an exception (e.g. RangeError) immediately instead of taking a lot of time and run into OOM

Current behavior on ruby 3.2.0 (2022-12-25 revision a528908271) [x86_64-linux]:

$ ruby -e '1 << 2**40'
-e: failed to allocate memory (NoMemoryError)
$ ruby -e '1 << 2**64'
-e: failed to allocate memory (NoMemoryError)
$ ruby -e '1 << 2**128'
-e:1:in `<<': shift width too big (RangeError)
$ ruby -e '1 << 2**66'
-e: failed to allocate memory (NoMemoryError)
$ ruby -e '1 << 2**67'
-e:1:in `<<': shift width too big (RangeError)

So the limit for RangeError on CRuby seems between 2^66 and 2^67, at least locally on my computer.
Which makes sense given that's in bits, divided by 8 is the same as -3, so 67-3 = 64, CRuby can't allocate something that doesn't fit in size_t/64-bit.

Interestingly 1 << 2**32 does work on CRuby:

$ ruby -e 'p (1 << 2**32).bit_length'
4294967297 # works locally for me, which I did not expect
$ ruby -robjspace -e 'p ObjectSpace.memsize_of(1 << 2**32)'            
536870956

So OK let's keep this rejected and accept this limit is implementation-defined (2**67 on 64-bit CRuby, 2**35 I guess on 32-bit CRuby, 2**31 on JRuby+TruffleRuby) and I'll adapt the spec.

[Eregon (Benoit Daloze)]

CRuby actually can give NoMemoryError, RangeError but also ArgumentError (seems a bug:

$ ruby -e '1 << (2**67-1)'
-e:1:in `<<': integer overflow: 4611686018427387905 * 4 > 18446744073709551615 (ArgumentError)

[Eregon (Benoit Daloze)]

Spec fixed in https://github.com/ruby/ruby/compare/651a098ea1526b363e85fd8d3f30e9783f6c5de1...28cfc0c116b6c6e40bf3b391f026a51b3b208047, so only RangeError for when above the limit.

[Eregon (Benoit Daloze)]

• Related to Bug #19323: Integer overflow in `Integer#<<` added

[mame (Yusuke Endoh)]

Discussed at the dev meeting.

Are there any real-world use cases (other than rubyspec) where you would like to prohibit integer << large?

@matz (Yukihiro Matsumoto) was initially positive about prohibiting huge object generation as early failure. However, there was little reason to prohibit only Integer#<<, so he considered to prohibit any Bignum generation larger than a threshold size, such as Integer#*.
However, there was little reason to prohibit only Bignum, so he wanted that Array and String should be prohibited from generating objects larger than the threshold size.
However, we sometimes use File.read with a file larger than 2GB. We reached that it would be difficult to determine a reasonable size threshold. The discussion ran out of time here.