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