Project

General

Profile

Actions

Bug #18518

closed

NoMemoryError + [FATAL] failed to allocate memory for twice 1 << large

Added by Eregon (Benoit Daloze) about 2 years ago. Updated about 1 year ago.

Status:
Rejected
Assignee:
-
Target version:
-
ruby -v:
ruby 3.0.2p107 (2021-07-07 revision 0db68f0233) [x86_64-linux]
[ruby-core:107291]

Description

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

Related issues 2 (0 open2 closed)

Related to Ruby master - Bug #18517: 0 << (2**40) is NoMemoryError but 0 << (2**80) is 0ClosedActions
Related to Ruby master - Bug #19323: Integer overflow in `Integer#<<`ClosedActions
Actions #1

Updated by Eregon (Benoit Daloze) about 2 years ago

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

Updated by Eregon (Benoit Daloze) about 2 years ago

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.

Updated by Eregon (Benoit Daloze) about 2 years ago

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.

Updated by Eregon (Benoit Daloze) about 1 year ago

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

Updated by Eregon (Benoit Daloze) about 1 year ago

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.

Updated by Eregon (Benoit Daloze) about 1 year ago

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?

Updated by headius (Charles Nutter) about 1 year ago

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).

Updated by nobu (Nobuyoshi Nakada) about 1 year ago

  • Status changed from Open to Rejected

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

Updated by Eregon (Benoit Daloze) about 1 year ago

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.

Updated by Eregon (Benoit Daloze) about 1 year ago

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)
Actions #12

Updated by Eregon (Benoit Daloze) about 1 year ago

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

Updated by mame (Yusuke Endoh) about 1 year ago

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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0