changeset 8941:291a872e1763

Fix issues with CHM: - Stack overflow when find entries in tables with lots of forwarding nodes - Iteration ecountering less elements due to encountering unexpected forwarding nodes created when resizing - more use of volatile to be on the conservative side Contributed-by: Doug Lea <dl@cs.oswego.edu>
author psandoz
date Fri, 05 Jul 2013 10:04:00 +0200
parents 6e9498188316
children 0692528c6d2e
files src/share/classes/java/util/concurrent/ConcurrentHashMap.java
diffstat 1 files changed, 48 insertions(+), 30 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Tue Jul 02 15:53:32 2013 -0700
+++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Fri Jul 05 10:04:00 2013 +0200
@@ -560,9 +560,9 @@
     /*
      * Encodings for Node hash fields. See above for explanation.
      */
-    static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
-    static final int TREEBIN   = 0x80000000; // hash for roots of trees
-    static final int RESERVED  = 0x80000001; // hash for transient reservations
+    static final int MOVED     = -1; // hash for forwarding nodes
+    static final int TREEBIN   = -2; // hash for roots of trees
+    static final int RESERVED  = -3; // hash for transient reservations
     static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
 
     /** Number of CPUS, to place bounds on some sizings */
@@ -589,7 +589,7 @@
         final int hash;
         final K key;
         volatile V val;
-        Node<K,V> next;
+        volatile Node<K,V> next;
 
         Node(int hash, K key, V val, Node<K,V> next) {
             this.hash = hash;
@@ -714,8 +714,9 @@
      * errors by users, these checks must operate on local variables,
      * which accounts for some odd-looking inline assignments below.
      * Note that calls to setTabAt always occur within locked regions,
-     * and so do not need full volatile semantics, but still require
-     * ordering to maintain concurrent readability.
+     * and so in principle require only release ordering, not need
+     * full volatile semantics, but are currently coded as volatile
+     * writes to be conservative.
      */
 
     @SuppressWarnings("unchecked")
@@ -729,7 +730,7 @@
     }
 
     static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
-        U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
+        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
     }
 
     /* ---------------- Fields -------------- */
@@ -2132,20 +2133,29 @@
         }
 
         Node<K,V> find(int h, Object k) {
-            Node<K,V> e; int n;
-            Node<K,V>[] tab = nextTable;
-            if (k != null && tab != null && (n = tab.length) > 0 &&
-                (e = tabAt(tab, (n - 1) & h)) != null) {
-                do {
+            // loop to avoid arbitrarily deep recursion on forwarding nodes
+            outer: for (Node<K,V>[] tab = nextTable;;) {
+                Node<K,V> e; int n;
+                if (k == null || tab == null || (n = tab.length) == 0 ||
+                    (e = tabAt(tab, (n - 1) & h)) == null)
+                    return null;
+                for (;;) {
                     int eh; K ek;
                     if ((eh = e.hash) == h &&
                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
                         return e;
-                    if (eh < 0)
-                        return e.find(h, k);
-                } while ((e = e.next) != null);
+                    if (eh < 0) {
+                        if (e instanceof ForwardingNode) {
+                            tab = ((ForwardingNode<K,V>)e).nextTable;
+                            continue outer;
+                        }
+                        else
+                            return e.find(h, k);
+                    }
+                    if ((e = e.next) == null)
+                        return null;
+                }
             }
-            return null;
         }
     }
 
@@ -2318,10 +2328,11 @@
         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;
             while (advance) {
-                if (--i >= bound)
+                if (--i >= bound || finishing)
                     advance = false;
                 else if ((nextIndex = transferIndex) <= transferOrigin) {
                     i = -1;
@@ -2337,14 +2348,19 @@
                 }
             }
             if (i < 0 || i >= n || i + n >= nextn) {
+                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) {
-                            nextTable = null;
-                            table = nextTab;
-                            sizeCtl = (n << 1) - (n >>> 1);
-                        }
-                        return;
+                        if (sc != -1)
+                            return;
+                        finishing = advance = true;
+                        i = n; // recheck before commit
+                        break;
                     }
                 }
             }
@@ -2386,6 +2402,10 @@
                                 else
                                     hn = new Node<K,V>(ph, pk, pv, hn);
                             }
+                            setTabAt(nextTab, i, ln);
+                            setTabAt(nextTab, i + n, hn);
+                            setTabAt(tab, i, fwd);
+                            advance = true;
                         }
                         else if (f instanceof TreeBin) {
                             TreeBin<K,V> t = (TreeBin<K,V>)f;
@@ -2417,13 +2437,11 @@
                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
+                            setTabAt(nextTab, i, ln);
+                            setTabAt(nextTab, i + n, hn);
+                            setTabAt(tab, i, fwd);
+                            advance = true;
                         }
-                        else
-                            ln = hn = null;
-                        setTabAt(nextTab, i, ln);
-                        setTabAt(nextTab, i + n, hn);
-                        setTabAt(tab, i, fwd);
-                        advance = true;
                     }
                 }
             }
@@ -2549,7 +2567,7 @@
                     U.compareAndSwapInt(this, SIZECTL, sc, -2))
                     transfer(tab, null);
             }
-            else if ((b = tabAt(tab, index)) != null) {
+            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                 synchronized (b) {
                     if (tabAt(tab, index) == b) {
                         TreeNode<K,V> hd = null, tl = null;