src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java

Print this page
rev 12972 : 8140606: Update library code to use internal Unsafe
Reviewed-by: duke


 280      * of the basic Node class with hash, key, value, and next
 281      * fields. However, various subclasses exist: TreeNodes are
 282      * arranged in balanced trees, not lists.  TreeBins hold the roots
 283      * of sets of TreeNodes. ForwardingNodes are placed at the heads
 284      * of bins during resizing. ReservationNodes are used as
 285      * placeholders while establishing values in computeIfAbsent and
 286      * related methods.  The types TreeBin, ForwardingNode, and
 287      * ReservationNode do not hold normal user keys, values, or
 288      * hashes, and are readily distinguishable during search etc
 289      * because they have negative hash fields and null key and value
 290      * fields. (These special nodes are either uncommon or transient,
 291      * so the impact of carrying around some unused fields is
 292      * insignificant.)
 293      *
 294      * The table is lazily initialized to a power-of-two size upon the
 295      * first insertion.  Each bin in the table normally contains a
 296      * list of Nodes (most often, the list has only zero or one Node).
 297      * Table accesses require volatile/atomic reads, writes, and
 298      * CASes.  Because there is no other way to arrange this without
 299      * adding further indirections, we use intrinsics
 300      * (sun.misc.Unsafe) operations.
 301      *
 302      * We use the top (sign) bit of Node hash fields for control
 303      * purposes -- it is available anyway because of addressing
 304      * constraints.  Nodes with negative hash fields are specially
 305      * handled or ignored in map methods.
 306      *
 307      * Insertion (via put or its variants) of the first node in an
 308      * empty bin is performed by just CASing it to the bin.  This is
 309      * by far the most common case for put operations under most
 310      * key/hash distributions.  Other update operations (insert,
 311      * delete, and replace) require locks.  We do not want to waste
 312      * the space required to associate a distinct lock object with
 313      * each bin, so instead use the first node of a bin list itself as
 314      * a lock. Locking support for these locks relies on builtin
 315      * "synchronized" monitors.
 316      *
 317      * Using the first node of a list as a lock does not by itself
 318      * suffice though: When a node is locked, any update must first
 319      * validate that it is still the first node after locking it, and
 320      * retry if not. Because new nodes are always appended to lists,


3270                 tb = t.prev, tn = (TreeNode<K,V>)t.next;
3271             if (tb != null && tb.next != t)
3272                 return false;
3273             if (tn != null && tn.prev != t)
3274                 return false;
3275             if (tp != null && t != tp.left && t != tp.right)
3276                 return false;
3277             if (tl != null && (tl.parent != t || tl.hash > t.hash))
3278                 return false;
3279             if (tr != null && (tr.parent != t || tr.hash < t.hash))
3280                 return false;
3281             if (t.red && tl != null && tl.red && tr != null && tr.red)
3282                 return false;
3283             if (tl != null && !checkInvariants(tl))
3284                 return false;
3285             if (tr != null && !checkInvariants(tr))
3286                 return false;
3287             return true;
3288         }
3289 
3290         private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3291         private static final long LOCKSTATE;
3292         static {
3293             try {
3294                 LOCKSTATE = U.objectFieldOffset
3295                     (TreeBin.class.getDeclaredField("lockState"));
3296             } catch (ReflectiveOperationException e) {
3297                 throw new Error(e);
3298             }
3299         }
3300     }
3301 
3302     /* ----------------Table Traversal -------------- */
3303 
3304     /**
3305      * Records the table, its length, and current traversal index for a
3306      * traverser that must process a region of a forwarded table before
3307      * proceeding with current table.
3308      */
3309     static final class TableStack<K,V> {
3310         int length;


6313                 }
6314                 for (Node<K,V> p; (p = advance()) != null; )
6315                     r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6316                 result = r;
6317                 CountedCompleter<?> c;
6318                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6319                     @SuppressWarnings("unchecked")
6320                     MapReduceMappingsToIntTask<K,V>
6321                         t = (MapReduceMappingsToIntTask<K,V>)c,
6322                         s = t.rights;
6323                     while (s != null) {
6324                         t.result = reducer.applyAsInt(t.result, s.result);
6325                         s = t.rights = s.nextRight;
6326                     }
6327                 }
6328             }
6329         }
6330     }
6331 
6332     // Unsafe mechanics
6333     private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6334     private static final long SIZECTL;
6335     private static final long TRANSFERINDEX;
6336     private static final long BASECOUNT;
6337     private static final long CELLSBUSY;
6338     private static final long CELLVALUE;
6339     private static final int ABASE;
6340     private static final int ASHIFT;
6341 
6342     static {
6343         try {
6344             SIZECTL = U.objectFieldOffset
6345                 (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6346             TRANSFERINDEX = U.objectFieldOffset
6347                 (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6348             BASECOUNT = U.objectFieldOffset
6349                 (ConcurrentHashMap.class.getDeclaredField("baseCount"));
6350             CELLSBUSY = U.objectFieldOffset
6351                 (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6352 
6353             CELLVALUE = U.objectFieldOffset


 280      * of the basic Node class with hash, key, value, and next
 281      * fields. However, various subclasses exist: TreeNodes are
 282      * arranged in balanced trees, not lists.  TreeBins hold the roots
 283      * of sets of TreeNodes. ForwardingNodes are placed at the heads
 284      * of bins during resizing. ReservationNodes are used as
 285      * placeholders while establishing values in computeIfAbsent and
 286      * related methods.  The types TreeBin, ForwardingNode, and
 287      * ReservationNode do not hold normal user keys, values, or
 288      * hashes, and are readily distinguishable during search etc
 289      * because they have negative hash fields and null key and value
 290      * fields. (These special nodes are either uncommon or transient,
 291      * so the impact of carrying around some unused fields is
 292      * insignificant.)
 293      *
 294      * The table is lazily initialized to a power-of-two size upon the
 295      * first insertion.  Each bin in the table normally contains a
 296      * list of Nodes (most often, the list has only zero or one Node).
 297      * Table accesses require volatile/atomic reads, writes, and
 298      * CASes.  Because there is no other way to arrange this without
 299      * adding further indirections, we use intrinsics
 300      * (jdk.internal.misc.Unsafe) operations.
 301      *
 302      * We use the top (sign) bit of Node hash fields for control
 303      * purposes -- it is available anyway because of addressing
 304      * constraints.  Nodes with negative hash fields are specially
 305      * handled or ignored in map methods.
 306      *
 307      * Insertion (via put or its variants) of the first node in an
 308      * empty bin is performed by just CASing it to the bin.  This is
 309      * by far the most common case for put operations under most
 310      * key/hash distributions.  Other update operations (insert,
 311      * delete, and replace) require locks.  We do not want to waste
 312      * the space required to associate a distinct lock object with
 313      * each bin, so instead use the first node of a bin list itself as
 314      * a lock. Locking support for these locks relies on builtin
 315      * "synchronized" monitors.
 316      *
 317      * Using the first node of a list as a lock does not by itself
 318      * suffice though: When a node is locked, any update must first
 319      * validate that it is still the first node after locking it, and
 320      * retry if not. Because new nodes are always appended to lists,


3270                 tb = t.prev, tn = (TreeNode<K,V>)t.next;
3271             if (tb != null && tb.next != t)
3272                 return false;
3273             if (tn != null && tn.prev != t)
3274                 return false;
3275             if (tp != null && t != tp.left && t != tp.right)
3276                 return false;
3277             if (tl != null && (tl.parent != t || tl.hash > t.hash))
3278                 return false;
3279             if (tr != null && (tr.parent != t || tr.hash < t.hash))
3280                 return false;
3281             if (t.red && tl != null && tl.red && tr != null && tr.red)
3282                 return false;
3283             if (tl != null && !checkInvariants(tl))
3284                 return false;
3285             if (tr != null && !checkInvariants(tr))
3286                 return false;
3287             return true;
3288         }
3289 
3290         private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
3291         private static final long LOCKSTATE;
3292         static {
3293             try {
3294                 LOCKSTATE = U.objectFieldOffset
3295                     (TreeBin.class.getDeclaredField("lockState"));
3296             } catch (ReflectiveOperationException e) {
3297                 throw new Error(e);
3298             }
3299         }
3300     }
3301 
3302     /* ----------------Table Traversal -------------- */
3303 
3304     /**
3305      * Records the table, its length, and current traversal index for a
3306      * traverser that must process a region of a forwarded table before
3307      * proceeding with current table.
3308      */
3309     static final class TableStack<K,V> {
3310         int length;


6313                 }
6314                 for (Node<K,V> p; (p = advance()) != null; )
6315                     r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6316                 result = r;
6317                 CountedCompleter<?> c;
6318                 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6319                     @SuppressWarnings("unchecked")
6320                     MapReduceMappingsToIntTask<K,V>
6321                         t = (MapReduceMappingsToIntTask<K,V>)c,
6322                         s = t.rights;
6323                     while (s != null) {
6324                         t.result = reducer.applyAsInt(t.result, s.result);
6325                         s = t.rights = s.nextRight;
6326                     }
6327                 }
6328             }
6329         }
6330     }
6331 
6332     // Unsafe mechanics
6333     private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
6334     private static final long SIZECTL;
6335     private static final long TRANSFERINDEX;
6336     private static final long BASECOUNT;
6337     private static final long CELLSBUSY;
6338     private static final long CELLVALUE;
6339     private static final int ABASE;
6340     private static final int ASHIFT;
6341 
6342     static {
6343         try {
6344             SIZECTL = U.objectFieldOffset
6345                 (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6346             TRANSFERINDEX = U.objectFieldOffset
6347                 (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6348             BASECOUNT = U.objectFieldOffset
6349                 (ConcurrentHashMap.class.getDeclaredField("baseCount"));
6350             CELLSBUSY = U.objectFieldOffset
6351                 (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6352 
6353             CELLVALUE = U.objectFieldOffset