Four impls of thread-safe Array#at for JRuby

0.soft_ordering.diff

diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java
index 04fbeef..1c32bb39 100644
--- a/core/src/main/java/org/jruby/RubyArray.java
+++ b/core/src/main/java/org/jruby/RubyArray.java
@@ -71,6 +71,7 @@ import org.jruby.util.io.EncodingUtils;
 
 import java.io.IOException;
 import java.lang.reflect.Array;
+import java.lang.reflect.Field;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
@@ -87,6 +88,7 @@ import static org.jruby.runtime.Helpers.hashEnd;
 import static org.jruby.runtime.Helpers.murmurCombine;
 import static org.jruby.runtime.Visibility.PRIVATE;
 import static org.jruby.RubyEnumerator.SizeFn;
+import static org.jruby.util.unsafe.UnsafeHolder.U;
 
 /**
  * The implementation of the built-in class Array in Ruby.
@@ -842,12 +844,7 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
     }
 
     public IRubyObject eltOk(long offset) {
-        try {
-            return eltInternal((int)offset);
-        } catch (ArrayIndexOutOfBoundsException ex) {
-            concurrentModification(getRuntime(), ex);
-            return null; // not reached
-        }
+        return eltInternal((int)offset);
     }
 
     public IRubyObject eltSetOk(long offset, IRubyObject value) {
@@ -875,7 +872,19 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
     }
 
     public IRubyObject eltInternal(int offset) {
-        return values[begin + offset];
+        // A moment-in-time tuple of [begin, values] is always safe
+        int serial, begin;
+        IRubyObject[] values;
+
+        serial = this.serial;
+
+        while (true) {
+            if ((serial & 1) == 1) serial = spin(this);
+            begin = this.begin;
+            values = this.values;
+            if (serial != this.serial) continue;
+            return values[begin + offset];
+        }
     }
 
     public IRubyObject eltInternalSet(int offset, IRubyObject item) {
@@ -4930,6 +4939,42 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return context.sites.Array;
     }
 
+    protected static int takeToken(RubyArray ths) {
+        int s = U.getIntVolatile(ths, OFFSET);
+        int plus;
+
+        while ((s & 1) == 1 ||
+                !U.compareAndSwapInt(ths, OFFSET, s, plus = s + 1)) {
+
+            s = spin(ths);
+        }
+
+        return plus;
+    }
+
+    private static int spin(RubyArray ths) {
+        Thread.yield();
+        return U.getIntVolatile(ths, OFFSET);
+    }
+
+    private static void releaseToken(RubyArray ths, int token) {
+        U.putOrderedInt(ths, OFFSET, token + 1);
+    }
+
+    private volatile int serial = 0;
+    private static final long OFFSET;
+
+    static {
+        Field field;
+        try {
+            field = RubyArray.class.getDeclaredField("serial");
+        } catch (Exception ex) {
+            throw new RuntimeException(ex);
+        }
+
+        OFFSET = U.objectFieldOffset(field);
+    }
+
     @Deprecated
     public IRubyObject compatc19() {
         return compact19();

1.unsafe.diff

diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java
index 04fbeef..effb373 100644
--- a/core/src/main/java/org/jruby/RubyArray.java
+++ b/core/src/main/java/org/jruby/RubyArray.java
@@ -71,6 +71,7 @@ import org.jruby.util.io.EncodingUtils;
 
 import java.io.IOException;
 import java.lang.reflect.Array;
+import java.lang.reflect.Field;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
@@ -87,6 +88,7 @@ import static org.jruby.runtime.Helpers.hashEnd;
 import static org.jruby.runtime.Helpers.murmurCombine;
 import static org.jruby.runtime.Visibility.PRIVATE;
 import static org.jruby.RubyEnumerator.SizeFn;
+import static org.jruby.util.unsafe.UnsafeHolder.U;
 
 /**
  * The implementation of the built-in class Array in Ruby.
@@ -842,11 +844,15 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
     }
 
     public IRubyObject eltOk(long offset) {
+        int token = takeToken(this);
+
         try {
             return eltInternal((int)offset);
         } catch (ArrayIndexOutOfBoundsException ex) {
             concurrentModification(getRuntime(), ex);
             return null; // not reached
+        } finally {
+            releaseToken(this, token);
         }
     }
 
@@ -4930,6 +4936,43 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return context.sites.Array;
     }
 
+    protected static int takeToken(RubyArray ths) {
+        int s = U.getIntVolatile(ths, OFFSET);
+        int plus;
+
+        while ((s & 1) == 1 ||
+                !U.compareAndSwapInt(ths, OFFSET, s, plus = s + 1)) {
+
+            s = spin(ths);
+        }
+
+        return plus;
+    }
+
+    private static int spin(RubyArray ths) {
+        Thread.yield();
+        return U.getIntVolatile(ths, OFFSET);
+    }
+
+    private static void releaseToken(RubyArray ths, int token) {
+        U.putOrderedInt(ths, OFFSET, token + 1);
+    }
+
+    private volatile int serial = 0;
+    private static final long OFFSET;
+
+    static {
+        final Field field;
+        final int modifiers;
+        try {
+            field = RubyArray.class.getDeclaredField("serial");
+        } catch (Exception ex) {
+            throw new RuntimeException(ex);
+        }
+
+        OFFSET = U.objectFieldOffset(field);
+    }
+
     @Deprecated
     public IRubyObject compatc19() {
         return compact19();

2.updater.diff

diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java
index 04fbeef..2ef910a 100644
--- a/core/src/main/java/org/jruby/RubyArray.java
+++ b/core/src/main/java/org/jruby/RubyArray.java
@@ -79,6 +79,7 @@ import java.util.Iterator;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.RandomAccess;
+import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
 
 import static org.jruby.RubyEnumerator.enumeratorize;
 import static org.jruby.RubyEnumerator.enumeratorizeWithSize;
@@ -842,11 +843,15 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
     }
 
     public IRubyObject eltOk(long offset) {
+        int token = takeToken();
+
         try {
             return eltInternal((int)offset);
         } catch (ArrayIndexOutOfBoundsException ex) {
             concurrentModification(getRuntime(), ex);
             return null; // not reached
+        } finally {
+            releaseToken(token);
         }
     }
 
@@ -4930,6 +4935,28 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return context.sites.Array;
     }
 
+    private volatile int serial = 0;
+    private static final AtomicIntegerFieldUpdater SERIAL = AtomicIntegerFieldUpdater.newUpdater(RubyArray.class, "serial");
+
+    private int takeToken() {
+        int s = SERIAL.get(this);
+        int plus;
+
+        while ((s & 1) == 1 ||
+                !SERIAL.compareAndSet(this, s, plus = s + 1)) {
+
+            Thread.yield();
+            s = SERIAL.get(this);
+        }
+
+        return plus;
+    }
+
+    private void releaseToken(int token) {
+        assert (token & 1) == 1;
+        SERIAL.lazySet(this, token + 1);
+    }
+
     @Deprecated
     public IRubyObject compatc19() {
         return compact19();

3.atomic_integer.diff

diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java
index 04fbeef..ee3b85a 100644
--- a/core/src/main/java/org/jruby/RubyArray.java
+++ b/core/src/main/java/org/jruby/RubyArray.java
@@ -79,6 +79,7 @@ import java.util.Iterator;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.RandomAccess;
+import java.util.concurrent.atomic.AtomicInteger;
 
 import static org.jruby.RubyEnumerator.enumeratorize;
 import static org.jruby.RubyEnumerator.enumeratorizeWithSize;
@@ -842,11 +843,15 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
     }
 
     public IRubyObject eltOk(long offset) {
+        int token = takeToken();
+
         try {
             return eltInternal((int)offset);
         } catch (ArrayIndexOutOfBoundsException ex) {
             concurrentModification(getRuntime(), ex);
             return null; // not reached
+        } finally {
+            releaseToken(token);
         }
     }
 
@@ -4930,6 +4935,27 @@ public class RubyArray extends RubyObject implements List, RandomAccess {
         return context.sites.Array;
     }
 
+    private AtomicInteger serial = new AtomicInteger(0);
+
+    private int takeToken() {
+        int s = serial.get();
+        int plus;
+
+        while ((s & 1) == 1 ||
+                !serial.compareAndSet(s, plus = s + 1)) {
+
+            Thread.yield();
+            s = serial.get();
+        }
+
+        return plus;
+    }
+
+    private void releaseToken(int token) {
+        assert (token & 1) == 1;
+        serial.lazySet(token + 1);
+    }
+
     @Deprecated
     public IRubyObject compatc19() {
         return compact19();