changeset 9577:b73937e96ae0

Fix for JDK-8010293. Avoid surprising observations (e.g. # elements traversed can reduce from previously observed) when traversing and resizing occurs due concurrently adding new entries. Contributed-by: Doug Lea <dl@cs.oswego.edu>, Peter Levart <peter.levart@gmail.com>, Paul Sandoz <paul.sandoz@Oracle.COM>
author psandoz
date Mon, 02 Sep 2013 11:59:57 +0200
parents 1ee4fcf28f11
children fa73fcb2b3d1
files src/share/classes/java/util/concurrent/ConcurrentHashMap.java test/java/util/concurrent/ConcurrentHashMap/toArray.java
diffstat 2 files changed, 243 insertions(+), 118 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Mon Sep 02 10:28:23 2013 +0200
+++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Mon Sep 02 11:59:57 2013 +0200
@@ -373,27 +373,26 @@
      * The table is resized when occupancy exceeds a percentage
      * threshold (nominally, 0.75, but see below).  Any thread
      * noticing an overfull bin may assist in resizing after the
-     * initiating thread allocates and sets up the replacement
-     * array. However, rather than stalling, these other threads may
-     * proceed with insertions etc.  The use of TreeBins shields us
-     * from the worst case effects of overfilling while resizes are in
+     * initiating thread allocates and sets up the replacement array.
+     * However, rather than stalling, these other threads may proceed
+     * with insertions etc.  The use of TreeBins shields us from the
+     * worst case effects of overfilling while resizes are in
      * progress.  Resizing proceeds by transferring bins, one by one,
-     * from the table to the next table. To enable concurrency, the
-     * next table must be (incrementally) prefilled with place-holders
-     * serving as reverse forwarders to the old table.  Because we are
-     * using power-of-two expansion, the elements from each bin must
-     * either stay at same index, or move with a power of two
-     * offset. We eliminate unnecessary node creation by catching
-     * cases where old nodes can be reused because their next fields
-     * won't change.  On average, only about one-sixth of them need
-     * cloning when a table doubles. The nodes they replace will be
-     * garbage collectable as soon as they are no longer referenced by
-     * any reader thread that may be in the midst of concurrently
-     * traversing table.  Upon transfer, the old table bin contains
-     * only a special forwarding node (with hash field "MOVED") that
-     * contains the next table as its key. On encountering a
-     * forwarding node, access and update operations restart, using
-     * the new table.
+     * from the table to the next table. However, threads claim small
+     * blocks of indices to transfer (via field transferIndex) before
+     * doing so, reducing contention.  Because we are using
+     * power-of-two expansion, the elements from each bin must either
+     * stay at same index, or move with a power of two offset. We
+     * eliminate unnecessary node creation by catching cases where old
+     * nodes can be reused because their next fields won't change.  On
+     * average, only about one-sixth of them need cloning when a table
+     * doubles. The nodes they replace will be garbage collectable as
+     * soon as they are no longer referenced by any reader thread that
+     * may be in the midst of concurrently traversing table.  Upon
+     * transfer, the old table bin contains only a special forwarding
+     * node (with hash field "MOVED") that contains the next table as
+     * its key. On encountering a forwarding node, access and update
+     * operations restart, using the new table.
      *
      * Each bin transfer requires its bin lock, which can stall
      * waiting for locks while resizing. However, because other
@@ -401,13 +400,19 @@
      * locks, average aggregate waits become shorter as resizing
      * progresses.  The transfer operation must also ensure that all
      * accessible bins in both the old and new table are usable by any
-     * traversal.  This is arranged by proceeding from the last bin
-     * (table.length - 1) up towards the first.  Upon seeing a
-     * forwarding node, traversals (see class Traverser) arrange to
-     * move to the new table without revisiting nodes.  However, to
-     * ensure that no intervening nodes are skipped, bin splitting can
-     * only begin after the associated reverse-forwarders are in
-     * place.
+     * traversal.  This is arranged in part by proceeding from the
+     * last bin (table.length - 1) up towards the first.  Upon seeing
+     * a forwarding node, traversals (see class Traverser) arrange to
+     * move to the new table without revisiting nodes.  To ensure that
+     * no intervening nodes are skipped even when moved out of order,
+     * a stack (see class TableStack) is created on first encounter of
+     * a forwarding node during a traversal, to maintain its place if
+     * later processing the current table. The need for these
+     * save/restore mechanics is relatively rare, but when one
+     * forwarding node is encountered, typically many more will be.
+     * So Traversers use a simple caching scheme to avoid creating so
+     * many new TableStack nodes. (Thanks to Peter Levart for
+     * suggesting use of a stack here.)
      *
      * The traversal scheme also applies to partial traversals of
      * ranges of bins (via an alternate Traverser constructor)
@@ -776,11 +781,6 @@
     private transient volatile int transferIndex;
 
     /**
-     * The least available table index to split while resizing.
-     */
-    private transient volatile int transferOrigin;
-
-    /**
      * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
      */
     private transient volatile int cellsBusy;
@@ -1376,7 +1376,8 @@
         }
         int segmentShift = 32 - sshift;
         int segmentMask = ssize - 1;
-        @SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
+        @SuppressWarnings("unchecked")
+        Segment<K,V>[] segments = (Segment<K,V>[])
             new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
         for (int i = 0; i < segments.length; ++i)
             segments[i] = new Segment<K,V>(LOAD_FACTOR);
@@ -1419,8 +1420,10 @@
         long size = 0L;
         Node<K,V> p = null;
         for (;;) {
-            @SuppressWarnings("unchecked") K k = (K) s.readObject();
-            @SuppressWarnings("unchecked") V v = (V) s.readObject();
+            @SuppressWarnings("unchecked")
+            K k = (K) s.readObject();
+            @SuppressWarnings("unchecked")
+            V v = (V) s.readObject();
             if (k != null && v != null) {
                 p = new Node<K,V>(spread(k.hashCode()), k, v, p);
                 ++size;
@@ -1438,8 +1441,8 @@
                 int sz = (int)size;
                 n = tableSizeFor(sz + (sz >>> 1) + 1);
             }
-            @SuppressWarnings({"rawtypes","unchecked"})
-                Node<K,V>[] tab = (Node<K,V>[])new Node[n];
+            @SuppressWarnings("unchecked")
+            Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
             int mask = n - 1;
             long added = 0L;
             while (p != null) {
@@ -2199,8 +2202,8 @@
                 try {
                     if ((tab = table) == null || tab.length == 0) {
                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
-                        @SuppressWarnings({"rawtypes","unchecked"})
-                            Node<K,V>[] nt = (Node<K,V>[])new Node[n];
+                        @SuppressWarnings("unchecked")
+                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                         table = tab = nt;
                         sc = n - (n >>> 2);
                     }
@@ -2245,7 +2248,7 @@
             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                    tab.length < MAXIMUM_CAPACITY) {
                 if (sc < 0) {
-                    if (sc == -1 || transferIndex <= transferOrigin ||
+                    if (sc == -1 || transferIndex <= 0 ||
                         (nt = nextTable) == null)
                         break;
                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
@@ -2265,10 +2268,13 @@
         Node<K,V>[] nextTab; int sc;
         if ((f instanceof ForwardingNode) &&
             (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
-            if (nextTab == nextTable && tab == table &&
-                transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
-                U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
-                transfer(tab, nextTab);
+            while (transferIndex > 0 && nextTab == nextTable &&
+                   (sc = sizeCtl) < -1) {
+                if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) {
+                    transfer(tab, nextTab);
+                    break;
+                }
+            }
             return nextTab;
         }
         return table;
@@ -2290,8 +2296,8 @@
                 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                     try {
                         if (table == tab) {
-                            @SuppressWarnings({"rawtypes","unchecked"})
-                                Node<K,V>[] nt = (Node<K,V>[])new Node[n];
+                            @SuppressWarnings("unchecked")
+                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                             table = nt;
                             sc = n - (n >>> 2);
                         }
@@ -2318,36 +2324,27 @@
             stride = MIN_TRANSFER_STRIDE; // subdivide range
         if (nextTab == null) {            // initiating
             try {
-                @SuppressWarnings({"rawtypes","unchecked"})
-                    Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
+                @SuppressWarnings("unchecked")
+                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                 nextTab = nt;
             } catch (Throwable ex) {      // try to cope with OOME
                 sizeCtl = Integer.MAX_VALUE;
                 return;
             }
             nextTable = nextTab;
-            transferOrigin = n;
             transferIndex = n;
-            ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
-            for (int k = n; k > 0;) {    // progressively reveal ready slots
-                int nextk = (k > stride) ? k - stride : 0;
-                for (int m = nextk; m < k; ++m)
-                    nextTab[m] = rev;
-                for (int m = n + nextk; m < n + k; ++m)
-                    nextTab[m] = rev;
-                U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
-            }
         }
         int nextn = nextTab.length;
         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
         boolean advance = true;
         boolean finishing = false; // to ensure sweep before committing nextTab
         for (int i = 0, bound = 0;;) {
-            int nextIndex, nextBound, fh; Node<K,V> f;
+            Node<K,V> f; int fh;
             while (advance) {
+                int nextIndex, nextBound;
                 if (--i >= bound || finishing)
                     advance = false;
-                else if ((nextIndex = transferIndex) <= transferOrigin) {
+                else if ((nextIndex = transferIndex) <= 0) {
                     i = -1;
                     advance = false;
                 }
@@ -2361,29 +2358,22 @@
                 }
             }
             if (i < 0 || i >= n || i + n >= nextn) {
+                int sc;
                 if (finishing) {
                     nextTable = null;
                     table = nextTab;
                     sizeCtl = (n << 1) - (n >>> 1);
                     return;
                 }
-                for (int sc;;) {
-                    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
-                        if (sc != -1)
-                            return;
-                        finishing = advance = true;
-                        i = n; // recheck before commit
-                        break;
-                    }
+                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
+                    if (sc != -1)
+                        return;
+                    finishing = advance = true;
+                    i = n; // recheck before commit
                 }
             }
-            else if ((f = tabAt(tab, i)) == null) {
-                if (casTabAt(tab, i, null, fwd)) {
-                    setTabAt(nextTab, i, null);
-                    setTabAt(nextTab, i + n, null);
-                    advance = true;
-                }
-            }
+            else if ((f = tabAt(tab, i)) == null)
+                advance = casTabAt(tab, i, null, fwd);
             else if ((fh = f.hash) == MOVED)
                 advance = true; // already processed
             else {
@@ -3223,6 +3213,18 @@
     /* ----------------Table Traversal -------------- */
 
     /**
+     * Records the table, its length, and current traversal index for a
+     * traverser that must process a region of a forwarded table before
+     * proceeding with current table.
+     */
+    static final class TableStack<K,V> {
+        int length;
+        int index;
+        Node<K,V>[] tab;
+        TableStack<K,V> next;
+    }
+
+    /**
      * Encapsulates traversal for methods such as containsValue; also
      * serves as a base class for other iterators and spliterators.
      *
@@ -3246,6 +3248,7 @@
     static class Traverser<K,V> {
         Node<K,V>[] tab;        // current table; updated if resized
         Node<K,V> next;         // the next entry to use
+        TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
         int index;              // index of bin to use next
         int baseIndex;          // current index of initial table
         int baseLimit;          // index bound for initial table
@@ -3267,16 +3270,17 @@
             if ((e = next) != null)
                 e = e.next;
             for (;;) {
-                Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
+                Node<K,V>[] t; int i, n;  // must use locals in checks
                 if (e != null)
                     return next = e;
                 if (baseIndex >= baseLimit || (t = tab) == null ||
                     (n = t.length) <= (i = index) || i < 0)
                     return next = null;
-                if ((e = tabAt(t, index)) != null && e.hash < 0) {
+                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                     if (e instanceof ForwardingNode) {
                         tab = ((ForwardingNode<K,V>)e).nextTable;
                         e = null;
+                        pushState(t, i, n);
                         continue;
                     }
                     else if (e instanceof TreeBin)
@@ -3284,10 +3288,49 @@
                     else
                         e = null;
                 }
-                if ((index += baseSize) >= n)
-                    index = ++baseIndex;    // visit upper slots if present
+                if (stack != null)
+                    recoverState(n);
+                else if ((index = i + baseSize) >= n)
+                    index = ++baseIndex; // visit upper slots if present
             }
         }
+
+        /**
+         * Saves traversal state upon encountering a forwarding node.
+         */
+        private void pushState(Node<K,V>[] t, int i, int n) {
+            TableStack<K,V> s = spare;  // reuse if possible
+            if (s != null)
+                spare = s.next;
+            else
+                s = new TableStack<K,V>();
+            s.tab = t;
+            s.length = n;
+            s.index = i;
+            s.next = stack;
+            stack = s;
+        }
+
+        /**
+         * Possibly pops traversal state.
+         *
+         * @param n length of current table
+         */
+        private void recoverState(int n) {
+            TableStack<K,V> s; int len;
+            while ((s = stack) != null && (index += (len = s.length)) >= n) {
+                n = len;
+                index = s.index;
+                tab = s.tab;
+                s.tab = null;
+                TableStack<K,V> next = s.next;
+                s.next = spare; // save for reuse
+                stack = next;
+                spare = s;
+            }
+            if (s == null && (index += baseSize) >= n)
+                index = ++baseIndex;
+        }
     }
 
     /**
@@ -4719,6 +4762,7 @@
     abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
         Node<K,V>[] tab;        // same as Traverser
         Node<K,V> next;
+        TableStack<K,V> stack, spare;
         int index;
         int baseIndex;
         int baseLimit;
@@ -4747,16 +4791,17 @@
             if ((e = next) != null)
                 e = e.next;
             for (;;) {
-                Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
+                Node<K,V>[] t; int i, n;
                 if (e != null)
                     return next = e;
                 if (baseIndex >= baseLimit || (t = tab) == null ||
                     (n = t.length) <= (i = index) || i < 0)
                     return next = null;
-                if ((e = tabAt(t, index)) != null && e.hash < 0) {
+                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                     if (e instanceof ForwardingNode) {
                         tab = ((ForwardingNode<K,V>)e).nextTable;
                         e = null;
+                        pushState(t, i, n);
                         continue;
                     }
                     else if (e instanceof TreeBin)
@@ -4764,10 +4809,41 @@
                     else
                         e = null;
                 }
-                if ((index += baseSize) >= n)
-                    index = ++baseIndex;    // visit upper slots if present
+                if (stack != null)
+                    recoverState(n);
+                else if ((index = i + baseSize) >= n)
+                    index = ++baseIndex;
             }
         }
+
+        private void pushState(Node<K,V>[] t, int i, int n) {
+            TableStack<K,V> s = spare;
+            if (s != null)
+                spare = s.next;
+            else
+                s = new TableStack<K,V>();
+            s.tab = t;
+            s.length = n;
+            s.index = i;
+            s.next = stack;
+            stack = s;
+        }
+
+        private void recoverState(int n) {
+            TableStack<K,V> s; int len;
+            while ((s = stack) != null && (index += (len = s.length)) >= n) {
+                n = len;
+                index = s.index;
+                tab = s.tab;
+                s.tab = null;
+                TableStack<K,V> next = s.next;
+                s.next = spare; // save for reuse
+                stack = next;
+                spare = s;
+            }
+            if (s == null && (index += baseSize) >= n)
+                index = ++baseIndex;
+        }
     }
 
     /*
@@ -5226,7 +5302,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") ReduceKeysTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    ReduceKeysTask<K,V>
                         t = (ReduceKeysTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5273,7 +5350,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") ReduceValuesTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    ReduceValuesTask<K,V>
                         t = (ReduceValuesTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5318,7 +5396,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    ReduceEntriesTask<K,V>
                         t = (ReduceEntriesTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5371,7 +5450,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
+                    @SuppressWarnings("unchecked")
+                    MapReduceKeysTask<K,V,U>
                         t = (MapReduceKeysTask<K,V,U>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5424,7 +5504,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
+                    @SuppressWarnings("unchecked")
+                    MapReduceValuesTask<K,V,U>
                         t = (MapReduceValuesTask<K,V,U>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5477,7 +5558,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
+                    @SuppressWarnings("unchecked")
+                    MapReduceEntriesTask<K,V,U>
                         t = (MapReduceEntriesTask<K,V,U>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5530,7 +5612,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
+                    @SuppressWarnings("unchecked")
+                    MapReduceMappingsTask<K,V,U>
                         t = (MapReduceMappingsTask<K,V,U>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5582,7 +5665,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceKeysToDoubleTask<K,V>
                         t = (MapReduceKeysToDoubleTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5631,7 +5715,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceValuesToDoubleTask<K,V>
                         t = (MapReduceValuesToDoubleTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5680,7 +5765,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceEntriesToDoubleTask<K,V>
                         t = (MapReduceEntriesToDoubleTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5729,7 +5815,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceMappingsToDoubleTask<K,V>
                         t = (MapReduceMappingsToDoubleTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5778,7 +5865,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceKeysToLongTask<K,V>
                         t = (MapReduceKeysToLongTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5827,7 +5915,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceValuesToLongTask<K,V>
                         t = (MapReduceValuesToLongTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5876,7 +5965,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceEntriesToLongTask<K,V>
                         t = (MapReduceEntriesToLongTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5925,7 +6015,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceMappingsToLongTask<K,V>
                         t = (MapReduceMappingsToLongTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -5974,7 +6065,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceKeysToIntTask<K,V>
                         t = (MapReduceKeysToIntTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -6023,7 +6115,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceValuesToIntTask<K,V>
                         t = (MapReduceValuesToIntTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -6072,7 +6165,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceEntriesToIntTask<K,V>
                         t = (MapReduceEntriesToIntTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -6121,7 +6215,8 @@
                 result = r;
                 CountedCompleter<?> c;
                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
-                    @SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
+                    @SuppressWarnings("unchecked")
+                    MapReduceMappingsToIntTask<K,V>
                         t = (MapReduceMappingsToIntTask<K,V>)c,
                         s = t.rights;
                     while (s != null) {
@@ -6137,7 +6232,6 @@
     private static final sun.misc.Unsafe U;
     private static final long SIZECTL;
     private static final long TRANSFERINDEX;
-    private static final long TRANSFERORIGIN;
     private static final long BASECOUNT;
     private static final long CELLSBUSY;
     private static final long CELLVALUE;
@@ -6152,8 +6246,6 @@
                 (k.getDeclaredField("sizeCtl"));
             TRANSFERINDEX = U.objectFieldOffset
                 (k.getDeclaredField("transferIndex"));
-            TRANSFERORIGIN = U.objectFieldOffset
-                (k.getDeclaredField("transferOrigin"));
             BASECOUNT = U.objectFieldOffset
                 (k.getDeclaredField("baseCount"));
             CELLSBUSY = U.objectFieldOffset
--- a/test/java/util/concurrent/ConcurrentHashMap/toArray.java	Mon Sep 02 10:28:23 2013 +0200
+++ b/test/java/util/concurrent/ConcurrentHashMap/toArray.java	Mon Sep 02 11:59:57 2013 +0200
@@ -30,21 +30,46 @@
 
 import java.util.*;
 import java.util.concurrent.*;
+import java.util.function.BiConsumer;
+import java.util.stream.IntStream;
+
+import static java.util.stream.Collectors.toList;
 
 public class toArray {
 
     public static void main(String[] args) throws Throwable {
+        // Execute a number of times to increase the probability of
+        // failure if there is an issue
+        for (int i = 0; i < 16; i++) {
+            executeTest();
+        }
+    }
+
+    static void executeTest() throws Throwable {
         final Throwable throwable[] = new Throwable[1];
-        final int maxSize = 1000;
-        final ConcurrentHashMap<Integer, Integer> m
-            = new ConcurrentHashMap<Integer, Integer>();
+        final ConcurrentHashMap<Integer, Integer> m = new ConcurrentHashMap<>();
 
-        final Thread t1 = new Thread() { public void run() {
-            for (int i = 0; i < maxSize; i++)
-                m.put(i,i);}};
+        BiConsumer<Integer, Integer> workFunction = (o, b) -> {
+            for (int i = o; i < b; i++)
+                m.put(i, i);
+        };
 
-        final Thread t2 = new Thread() {
-            public Throwable exception = null;
+        // Create workers equal to the number of processors
+        // Each worker will put globally unique keys into the map
+        final int nWorkers = Runtime.getRuntime().availableProcessors();
+        final int sizePerWorker = 1024;
+        final int maxSize = nWorkers * sizePerWorker;
+        List<Thread> workers = IntStream.range(0, nWorkers).
+                map(w -> w * sizePerWorker).
+                mapToObj(w -> (Runnable) () -> workFunction.accept(w, w + sizePerWorker)).
+                map(Thread::new).collect(toList());
+
+        // The foreman keeps checking that the size of the arrays
+        // obtained from the key and value sets is never less than the
+        // previously observed size and is never greater than the maximum size
+        // NOTE: these size constraints are not specific to toArray and are
+        // applicable to any form of traversal of the collection views
+        final Thread foreman = new Thread() {
             private int prevSize = 0;
 
             private boolean checkProgress(Object[] a) {
@@ -66,16 +91,24 @@
                         if (checkProgress(m.keySet().toArray(empty))) return;
                     }
                 } catch (Throwable t) {
-                   throwable[0] = t;
+                    throwable[0] = t;
                 }}};
 
-        t2.start();
-        t1.start();
+        foreman.start();
+        workers.stream().forEach(Thread::start);
 
-        t1.join();
-        t2.join();
+        workers.stream().forEach(toArray::join);
+        foreman.join();
 
         if (throwable[0] != null)
             throw throwable[0];
     }
+
+    static void join(Thread t) {
+        try {
+            t.join();
+        } catch (InterruptedException e) {
+            throw new RuntimeException(e);
+        }
+    }
 }