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