RubyRandom is not thread-safe

Details

Type: Bug
Status: Resolved
Priority: Minor
Resolution: Fixed
Affects Version/s: JRuby 1.7.0.pre1
Fix Version/s: JRuby 1.7.0.pre2
Component/s: Core Classes/Modules
Labels:
None

Number of attachments :
0

Description

RubyRandom is not thread-safe and is throwing java.lang.ArrayIndexOutOfBoundsException exception under concurrent load.

To reproduce:

bin/jruby -e'Array.new(100).map {Thread.new{500000.times

{rand}

}}.map(&:join)'

Exception in thread "RubyThread-52: -e:1" java.lang.ArrayIndexOutOfBoundsException: 624
at org.jruby.util.Random.genrandInt32(Random.java:145)
at org.jruby.util.Random.genrandReal(Random.java:158)
at org.jruby.RubyRandom$RandomType.genrandReal(RubyRandom.java:135)
at org.jruby.RubyRandom.randFloat(RubyRandom.java:348)
at org.jruby.RubyRandom.randCommon19(RubyRandom.java:269)
at org.jruby.RubyKernel.rand19(RubyKernel.java:1537)
at org.jruby.RubyKernel$INVOKER$s$0$1$rand19.call(RubyKernel$INVOKER$s$0$1$rand19.gen)
at org.jruby.internal.runtime.methods.JavaMethod$JavaMethodN.call(JavaMethod.java:636)
at org.jruby.internal.runtime.methods.DynamicMethod.call(DynamicMethod.java:196)
at java.lang.invoke.MethodHandle.invokeExact(MethodHandle.java)
at java.lang.invoke.MethodHandle.invokeExact(MethodHandle.java)
at java.lang.invoke.MethodHandle.invokeExact(MethodHandle.java)
at ruby._dash_e.block_2$RUBY$file_(-e:1)
at ruby$_dash_e$block_2$RUBY$file.call(ruby$dash_e$block_2$RUBY$file_)
at org.jruby.runtime.CompiledBlock19.yield(CompiledBlock19.java:139)
at org.jruby.runtime.Block.yield(Block.java:130)
at org.jruby.RubyFixnum.times(RubyFixnum.java:265)
at java.lang.invoke.MethodHandleImpl$GuardWithCatch.invoke_L4(MethodHandleImpl.java:1146)
at java.lang.invoke.MethodHandleImpl$GuardWithCatch.invoke_L4(MethodHandleImpl.java:1146)
at ruby._dash_e.block_1$RUBY$file_(-e:1)
at ruby$_dash_e$block_1$RUBY$file.call(ruby$dash_e$block_1$RUBY$file_)
at org.jruby.runtime.CompiledBlock19.yield(CompiledBlock19.java:163)
at org.jruby.runtime.CompiledBlock19.call(CompiledBlock19.java:91)
at org.jruby.runtime.Block.call(Block.java:89)
at org.jruby.RubyProc.call(RubyProc.java:269)
at org.jruby.RubyProc.call(RubyProc.java:223)
at org.jruby.internal.runtime.RubyRunnable.run(RubyRunnable.java:101)
at java.lang.Thread.run(Thread.java:722)

I run into this by having Array#shuffle throwing concurrent modification errors, because it is catching ArrayIndexOutOfBoundsException thrown by the RubyRandom and re-throwing them as Array concurrency exceptions.

To reproduce:
bin/jruby -e'arr = Array.new(1000); Array.new(100).map {Thread.new{1000.times

{arr.shuffle}

}}.map(&:join)'

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

thedarkone added a comment - 13/Jul/12 8:56 AM

Don't know enough about rand, but maybe this can be fixed by wrapping org.jruby.util.Random.genrandInt32() with a try/catch block and simply retrying on ArrayIndexOutOfBoundsException exception (or is this risking internal rand generator corruption?).

Show

thedarkone added a comment - 13/Jul/12 8:56 AM Don't know enough about rand, but maybe this can be fixed by wrapping org.jruby.util.Random.genrandInt32() with a try/catch block and simply retrying on ArrayIndexOutOfBoundsException exception (or is this risking internal rand generator corruption?).

Hide

Permalink

Charles Oliver Nutter added a comment - 20/Jul/12 10:13 PM

This should be something we fix in genrandInt32...it shouldn't cause an AIOOB like this.

Show

Charles Oliver Nutter added a comment - 20/Jul/12 10:13 PM This should be something we fix in genrandInt32...it shouldn't cause an AIOOB like this.

Hide

Permalink

Charles Oliver Nutter added a comment - 20/Jul/12 10:16 PM

Yes, I think the random number generator's entry points need to be synchronized, or else we need some good volatile trickery.

Show

Charles Oliver Nutter added a comment - 20/Jul/12 10:16 PM Yes, I think the random number generator's entry points need to be synchronized, or else we need some good volatile trickery.

Hide

Permalink

Charles Oliver Nutter added a comment - 24/Jul/12 11:45 AM

commit 507a7f086e706cd93c98dde763b88abd9ecf842a
Author: Charles Oliver Nutter <headius@headius.com>
Date:   Tue Jul 24 11:41:51 2012 -0500

    Fix JRUBY-6775: RubyRandom is not thread-safe
    
    I opted to simply synchronize around the logic in question. The
    primary issue is the potential for "left" to get decremented below
    zero under concurrency while it is in use. I tried to figure out
    an AtomicInteger-based algorithm for guaranteeing both that left
    would never cause a <0 array dereference *and* would not produce
    the same random number twice, but was unable to find a way due
    to the multiple state changes that happen.
    
    Synchronization does slow things down a bit, but perhaps not
    enough to worry about:
    
    Before (single thread):
    
    system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(1).map {Thread.new{50000000.times{rand}}}.map(&:join) } }'
      3.670000   0.130000   3.800000 (  3.317000)
      3.880000   0.150000   4.030000 (  3.761000)
      4.550000   0.150000   4.700000 (  4.495000)
      4.500000   0.160000   4.660000 (  4.460000)
      4.500000   0.150000   4.650000 (  4.452000)
    
    After (single thread):
    
    system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(1).map {Thread.new{50000000.times{rand}}}.map(&:join) } }'
      4.420000   0.130000   4.550000 (  4.031000)
      4.460000   0.170000   4.630000 (  4.353000)
      5.000000   0.160000   5.160000 (  4.954000)
      4.980000   0.160000   5.140000 (  4.924000)
      5.070000   0.160000   5.230000 (  5.020000)
    
    After (100 threads, same workload):
    
    system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(100).map {Thread.new{500000.times{rand}}}.map(&:join) } }'
     13.900000   5.400000  19.300000 (  8.227000)
     12.900000   5.250000  18.150000 (  7.938000)
     13.800000   5.680000  19.480000 (  8.903000)
     13.540000   5.750000  19.290000 (  8.627000)
     13.390000   5.560000  18.950000 (  8.331000)

:100644 100644 8c3f071... d14719d... M	src/org/jruby/util/Random.java

Show

Charles Oliver Nutter added a comment - 24/Jul/12 11:45 AM commit 507a7f086e706cd93c98dde763b88abd9ecf842a Author: Charles Oliver Nutter <headius@headius.com> Date: Tue Jul 24 11:41:51 2012 -0500 Fix JRUBY-6775: RubyRandom is not thread-safe I opted to simply synchronize around the logic in question. The primary issue is the potential for "left" to get decremented below zero under concurrency while it is in use. I tried to figure out an AtomicInteger-based algorithm for guaranteeing both that left would never cause a <0 array dereference *and* would not produce the same random number twice, but was unable to find a way due to the multiple state changes that happen. Synchronization does slow things down a bit, but perhaps not enough to worry about: Before (single thread): system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(1).map {Thread.new{50000000.times{rand}}}.map(&:join) } }' 3.670000 0.130000 3.800000 ( 3.317000) 3.880000 0.150000 4.030000 ( 3.761000) 4.550000 0.150000 4.700000 ( 4.495000) 4.500000 0.160000 4.660000 ( 4.460000) 4.500000 0.150000 4.650000 ( 4.452000) After (single thread): system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(1).map {Thread.new{50000000.times{rand}}}.map(&:join) } }' 4.420000 0.130000 4.550000 ( 4.031000) 4.460000 0.170000 4.630000 ( 4.353000) 5.000000 0.160000 5.160000 ( 4.954000) 4.980000 0.160000 5.140000 ( 4.924000) 5.070000 0.160000 5.230000 ( 5.020000) After (100 threads, same workload): system ~/projects/jruby $ jruby -rbenchmark -e '5.times { puts Benchmark.measure { Array.new(100).map {Thread.new{500000.times{rand}}}.map(&:join) } }' 13.900000 5.400000 19.300000 ( 8.227000) 12.900000 5.250000 18.150000 ( 7.938000) 13.800000 5.680000 19.480000 ( 8.903000) 13.540000 5.750000 19.290000 ( 8.627000) 13.390000 5.560000 18.950000 ( 8.331000) :100644 100644 8c3f071... d14719d... M src/org/jruby/util/Random.java

People

Assignee:

Charles Oliver Nutter

Reporter:

thedarkone

Vote (0)

Watch (3)

Dates

Created:

13/Jul/12 8:50 AM

Updated:

24/Jul/12 11:45 AM

Resolved:

24/Jul/12 11:45 AM