View Javadoc
1   /*
2    * Written by Doug Lea with assistance from members of JCP JSR-166
3    * Expert Group and released to the public domain, as explained at
4    * http://creativecommons.org/publicdomain/zero/1.0/
5    */
6   
7   /*
8    * Source:
9    * http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/Striped64.java?revision=1.9
10   */
11  
12  package com.google.common.hash;
13  
14  import com.google.common.annotations.GwtIncompatible;
15  import java.util.Random;
16  import javax.annotation.Nullable;
17  
18  /**
19   * A package-local class holding common representation and mechanics
20   * for classes supporting dynamic striping on 64bit values. The class
21   * extends Number so that concrete subclasses must publicly do so.
22   */
23  @GwtIncompatible
24  abstract class Striped64 extends Number {
25      /*
26       * This class maintains a lazily-initialized table of atomically
27       * updated variables, plus an extra "base" field. The table size
28       * is a power of two. Indexing uses masked per-thread hash codes.
29       * Nearly all declarations in this class are package-private,
30       * accessed directly by subclasses.
31       *
32       * Table entries are of class Cell; a variant of AtomicLong padded
33       * to reduce cache contention on most processors. Padding is
34       * overkill for most Atomics because they are usually irregularly
35       * scattered in memory and thus don't interfere much with each
36       * other. But Atomic objects residing in arrays will tend to be
37       * placed adjacent to each other, and so will most often share
38       * cache lines (with a huge negative performance impact) without
39       * this precaution.
40       *
41       * In part because Cells are relatively large, we avoid creating
42       * them until they are needed.  When there is no contention, all
43       * updates are made to the base field.  Upon first contention (a
44       * failed CAS on base update), the table is initialized to size 2.
45       * The table size is doubled upon further contention until
46       * reaching the nearest power of two greater than or equal to the
47       * number of CPUS. Table slots remain empty (null) until they are
48       * needed.
49       *
50       * A single spinlock ("busy") is used for initializing and
51       * resizing the table, as well as populating slots with new Cells.
52       * There is no need for a blocking lock; when the lock is not
53       * available, threads try other slots (or the base).  During these
54       * retries, there is increased contention and reduced locality,
55       * which is still better than alternatives.
56       *
57       * Per-thread hash codes are initialized to random values.
58       * Contention and/or table collisions are indicated by failed
59       * CASes when performing an update operation (see method
60       * retryUpdate). Upon a collision, if the table size is less than
61       * the capacity, it is doubled in size unless some other thread
62       * holds the lock. If a hashed slot is empty, and lock is
63       * available, a new Cell is created. Otherwise, if the slot
64       * exists, a CAS is tried.  Retries proceed by "double hashing",
65       * using a secondary hash (Marsaglia XorShift) to try to find a
66       * free slot.
67       *
68       * The table size is capped because, when there are more threads
69       * than CPUs, supposing that each thread were bound to a CPU,
70       * there would exist a perfect hash function mapping threads to
71       * slots that eliminates collisions. When we reach capacity, we
72       * search for this mapping by randomly varying the hash codes of
73       * colliding threads.  Because search is random, and collisions
74       * only become known via CAS failures, convergence can be slow,
75       * and because threads are typically not bound to CPUS forever,
76       * may not occur at all. However, despite these limitations,
77       * observed contention rates are typically low in these cases.
78       *
79       * It is possible for a Cell to become unused when threads that
80       * once hashed to it terminate, as well as in the case where
81       * doubling the table causes no thread to hash to it under
82       * expanded mask.  We do not try to detect or remove such cells,
83       * under the assumption that for long-running instances, observed
84       * contention levels will recur, so the cells will eventually be
85       * needed again; and for short-lived ones, it does not matter.
86       */
87  
88      /**
89       * Padded variant of AtomicLong supporting only raw accesses plus CAS.
90       * The value field is placed between pads, hoping that the JVM doesn't
91       * reorder them.
92       *
93       * JVM intrinsics note: It would be possible to use a release-only
94       * form of CAS here, if it were provided.
95       */
96      static final class Cell {
97          volatile long p0, p1, p2, p3, p4, p5, p6;
98          volatile long value;
99          volatile long q0, q1, q2, q3, q4, q5, q6;
100         Cell(long x) { value = x; }
101 
102         final boolean cas(long cmp, long val) {
103             return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
104         }
105 
106         // Unsafe mechanics
107         private static final sun.misc.Unsafe UNSAFE;
108         private static final long valueOffset;
109         static {
110             try {
111                 UNSAFE = getUnsafe();
112                 Class<?> ak = Cell.class;
113                 valueOffset = UNSAFE.objectFieldOffset
114                     (ak.getDeclaredField("value"));
115             } catch (Exception e) {
116                 throw new Error(e);
117             }
118         }
119 
120     }
121 
122   /**
123    * ThreadLocal holding a single-slot int array holding hash code. Unlike the JDK8 version of this
124    * class, we use a suboptimal int[] representation to avoid introducing a new type that can impede
125    * class-unloading when ThreadLocals are not removed.
126    */
127   static final ThreadLocal<int[]> threadHashCode = new ThreadLocal<>();
128 
129     /**
130      * Generator of new random hash codes
131      */
132     static final Random rng = new Random();
133 
134     /** Number of CPUS, to place bound on table size */
135     static final int NCPU = Runtime.getRuntime().availableProcessors();
136 
137     /**
138      * Table of cells. When non-null, size is a power of 2.
139      */
140     transient volatile Cell[] cells;
141 
142     /**
143      * Base value, used mainly when there is no contention, but also as
144      * a fallback during table initialization races. Updated via CAS.
145      */
146     transient volatile long base;
147 
148     /**
149      * Spinlock (locked via CAS) used when resizing and/or creating Cells.
150      */
151     transient volatile int busy;
152 
153     /**
154      * Package-private default constructor
155      */
156     Striped64() {
157     }
158 
159     /**
160      * CASes the base field.
161      */
162     final boolean casBase(long cmp, long val) {
163         return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val);
164     }
165 
166     /**
167      * CASes the busy field from 0 to 1 to acquire lock.
168      */
169     final boolean casBusy() {
170         return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1);
171     }
172 
173     /**
174      * Computes the function of current and new value. Subclasses
175      * should open-code this update function for most uses, but the
176      * virtualized form is needed within retryUpdate.
177      *
178      * @param currentValue the current value (of either base or a cell)
179      * @param newValue the argument from a user update call
180      * @return result of the update function
181      */
182     abstract long fn(long currentValue, long newValue);
183 
184     /**
185      * Handles cases of updates involving initialization, resizing,
186      * creating new Cells, and/or contention. See above for
187      * explanation. This method suffers the usual non-modularity
188      * problems of optimistic retry code, relying on rechecked sets of
189      * reads.
190      *
191      * @param x the value
192      * @param hc the hash code holder
193      * @param wasUncontended false if CAS failed before call
194      */
195     final void retryUpdate(long x, @Nullable int[] hc, boolean wasUncontended) {
196         int h;
197         if (hc == null) {
198             threadHashCode.set(hc = new int[1]); // Initialize randomly
199             int r = rng.nextInt(); // Avoid zero to allow xorShift rehash
200             h = hc[0] = (r == 0) ? 1 : r;
201         }
202         else
203             h = hc[0];
204         boolean collide = false;                // True if last slot nonempty
205         for (;;) {
206             Cell[] as; Cell a; int n; long v;
207             if ((as = cells) != null && (n = as.length) > 0) {
208                 if ((a = as[(n - 1) & h]) == null) {
209                     if (busy == 0) {            // Try to attach new Cell
210                         Cell r = new Cell(x);   // Optimistically create
211                         if (busy == 0 && casBusy()) {
212                             boolean created = false;
213                             try {               // Recheck under lock
214                                 Cell[] rs; int m, j;
215                                 if ((rs = cells) != null &&
216                                     (m = rs.length) > 0 &&
217                                     rs[j = (m - 1) & h] == null) {
218                                     rs[j] = r;
219                                     created = true;
220                                 }
221                             } finally {
222                                 busy = 0;
223                             }
224                             if (created)
225                                 break;
226                             continue;           // Slot is now non-empty
227                         }
228                     }
229                     collide = false;
230                 }
231                 else if (!wasUncontended)       // CAS already known to fail
232                     wasUncontended = true;      // Continue after rehash
233                 else if (a.cas(v = a.value, fn(v, x)))
234                     break;
235                 else if (n >= NCPU || cells != as)
236                     collide = false;            // At max size or stale
237                 else if (!collide)
238                     collide = true;
239                 else if (busy == 0 && casBusy()) {
240                     try {
241                         if (cells == as) {      // Expand table unless stale
242                             Cell[] rs = new Cell[n << 1];
243                             for (int i = 0; i < n; ++i)
244                                 rs[i] = as[i];
245                             cells = rs;
246                         }
247                     } finally {
248                         busy = 0;
249                     }
250                     collide = false;
251                     continue;                   // Retry with expanded table
252                 }
253                 h ^= h << 13;                   // Rehash
254                 h ^= h >>> 17;
255                 h ^= h << 5;
256                 hc[0] = h;                      // Record index for next time
257             }
258             else if (busy == 0 && cells == as && casBusy()) {
259                 boolean init = false;
260                 try {                           // Initialize table
261                     if (cells == as) {
262                         Cell[] rs = new Cell[2];
263                         rs[h & 1] = new Cell(x);
264                         cells = rs;
265                         init = true;
266                     }
267                 } finally {
268                     busy = 0;
269                 }
270                 if (init)
271                     break;
272             }
273             else if (casBase(v = base, fn(v, x)))
274                 break;                          // Fall back on using base
275         }
276     }
277 
278     /**
279      * Sets base and all cells to the given value.
280      */
281     final void internalReset(long initialValue) {
282         Cell[] as = cells;
283         base = initialValue;
284         if (as != null) {
285             int n = as.length;
286             for (int i = 0; i < n; ++i) {
287                 Cell a = as[i];
288                 if (a != null)
289                     a.value = initialValue;
290             }
291         }
292     }
293 
294     // Unsafe mechanics
295     private static final sun.misc.Unsafe UNSAFE;
296     private static final long baseOffset;
297     private static final long busyOffset;
298     static {
299         try {
300             UNSAFE = getUnsafe();
301             Class<?> sk = Striped64.class;
302             baseOffset = UNSAFE.objectFieldOffset
303                 (sk.getDeclaredField("base"));
304             busyOffset = UNSAFE.objectFieldOffset
305                 (sk.getDeclaredField("busy"));
306         } catch (Exception e) {
307             throw new Error(e);
308         }
309     }
310 
311     /**
312      * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
313      * Replace with a simple call to Unsafe.getUnsafe when integrating
314      * into a jdk.
315      *
316      * @return a sun.misc.Unsafe
317      */
318     private static sun.misc.Unsafe getUnsafe() {
319         try {
320             return sun.misc.Unsafe.getUnsafe();
321         } catch (SecurityException tryReflectionInstead) {}
322         try {
323             return java.security.AccessController.doPrivileged
324             (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
325                 public sun.misc.Unsafe run() throws Exception {
326                     Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
327                     for (java.lang.reflect.Field f : k.getDeclaredFields()) {
328                         f.setAccessible(true);
329                         Object x = f.get(null);
330                         if (k.isInstance(x))
331                             return k.cast(x);
332                     }
333                     throw new NoSuchFieldError("the Unsafe");
334                 }});
335         } catch (java.security.PrivilegedActionException e) {
336             throw new RuntimeException("Could not initialize intrinsics",
337                                        e.getCause());
338         }
339     }
340 }